完整搜尋頁面 →

交叉熵方法:用取樣與重新擬合來規劃

選讀・DLCV 13・世界模型:影片、潛在動態與規劃 的補充資料(第 3/3 則)。主線不依賴這則補充;引用編號對應本頁底部的參考文獻。

導覽:本頁與本系列: 導覽:本頁與本系列

本頁內容

補充資料 · 3

  1. ELBO 與重新參數化技巧:訓練潛在狀態
  2. JEPA 系列的其他模型:I-JEPA、V-JEPA 與 V-JEPA 2.1
  3. 交叉熵方法:用取樣與重新擬合來規劃

電腦視覺深度學習

  1. 02 · 深度影像分類
  2. 03 · 物件偵測:從 R-CNN 到 DETR
  3. 09 · 深度影像復原:低階視覺
查看完整課程樹 →

白話版。 在一個粗略的猜測附近丟 64 支飛鏢,看哪 8 支最靠近靶心,把瞄準點移到這 8 支的中央,縮小散布範圍,再丟一次。幾輪之後飛鏢就會集中在一個不錯的位置,而你從頭到尾都不需要知道靶面的斜率。

精確版。 規劃器要在動作序列 a=(a0,…,aH−1)a=(a_0,\dots,a_{H-1}) 上最小化成本 J(a)J(a),其中 JJ 是從目前狀態出發、用模型向前推演算出來的。它維護序列上的一個高斯分布 N(μ,diag⁡σ2)\mathcal N(\mu,\operatorname{diag}\sigma^2),並重複四個步驟:

  1. 從高斯分布取樣 NN 條序列 a(1),…,a(N)a^{(1)},\dots,a^{(N)}(並裁切到允許的動作範圍);
  2. 對每一條用模型推演計算 J(a(i))J(a^{(i)});
  3. 保留成本最低的 KK 條,即菁英(elites),組成集合 E\mathcal E;
  4. 重新擬合:μ←1K∑a∈Ea\mu\leftarrow\frac1K\sum_{a\in\mathcal E}a,σ←std⁡E(a)\sigma\leftarrow\operatorname{std}_{\mathcal E}(a)(逐時間步計算)。

這裡 HH 是視野長度,NN 是每一輪的樣本數,K<NK\lt N 是菁英數。第 4 步是把高斯分布以最大概似法擬合到菁英上,這個選擇會最小化菁英樣本與高斯分布族之間的交叉熵,方法的名稱也由此而來。Rubinstein 把它發展成針對組合與連續問題的最佳化方法,建立在 Kullback–Leibler 交叉熵與重要性取樣(importance sampling)之上 [35];de Boer 等人寫了一篇導論,也涵蓋罕見事件模擬 [36]。PETS 在 MPC 中使用了以 CEM 為基礎的規劃 [29]。若跑 RR 輪,每次規劃的成本是 R N HR\,N\,H 個模型步,而且不需要梯度,所以 JJ 可以不可微,NN 條推演也能平行執行。本章的 CPU 實驗在 σ\sigma 上加了 0.050.05 的下限,避免分散度太早塌縮(下面的程式碼也這樣做);在 MPC 中,則會把平均向前移一步,當作下一個時間步的起始猜測。

程式碼 · Python · 29 行
import numpy as np

rng = np.random.default_rng(0)
A = np.array([[1.0, 0.1], [0.0, 0.94]])       # known model: position, velocity
B = np.array([0.005, 0.1])
H, N, K = 15, 64, 8                           # horizon, samples per round, elites

def cost(x0, U):                              # U: (N, H) action sequences -> (N,) costs
    x = np.broadcast_to(x0, (len(U), 2)).copy()
    c = np.zeros(len(U))
    for t in range(H):
        x = x @ A.T + U[:, t, None] * B
        c += x[:, 0] ** 2 + 0.15 * x[:, 1] ** 2 + 0.02 * U[:, t] ** 2
    return c + 20 * x[:, 0] ** 2

x0 = np.array([1.5, 0.0])
mean, std = np.zeros(H), np.ones(H)
for i in range(5):
    U = np.clip(rng.normal(mean, std, (N, H)), -1, 1)
    c = cost(x0, U)
    elite = U[np.argsort(c)[:K]]
    mean, std = elite.mean(axis=0), elite.std(axis=0) + 0.05   # refit to the elites
    print(f"round {i}: best {c.min():.3f}, mean of elites {np.sort(c)[:K].mean():.3f}, "
          f"mean std {std.mean():.3f}")

U = np.clip(rng.normal(0.0, 1.0, (5 * N, H)), -1, 1)           # same budget, no refitting
print(f"random shooting, {5 * N} samples: best {cost(x0, U).min():.3f}")
print(f"zero actions: {cost(x0, np.zeros((1, H)))[0]:.3f}")
print(f"cost of the final mean sequence: {cost(x0, mean[None])[0]:.3f}")

輸出:

程式碼 · 8 行
round 0: best 47.314, mean of elites 53.939, mean std 0.570
round 1: best 42.572, mean of elites 45.558, mean std 0.408
round 2: best 37.952, mean of elites 39.610, mean std 0.325
round 3: best 35.143, mean of elites 37.146, mean std 0.231
round 4: best 34.089, mean of elites 35.691, mean std 0.210
random shooting, 320 samples: best 46.672
zero actions: 78.750
cost of the final mean sequence: 35.669

第一輪就是單純的隨機射擊(random shooting)。之後每一輪都從一個已經移向低成本區域、並且變窄的分布取樣(平均標準差 0.570→0.2100.570\to0.210),所以最佳成本從 47.31447.314 降到 34.08934.089。用同樣 320320 個樣本做隨機射擊只能達到 46.67246.672,什麼都不做則要 78.75078.750。這些數字來自這個玩具例子,不是基準測試結果。

何時會失敗。 單一高斯分布只涵蓋一個盆地,當成本有多個盆地時,它可能鎖定錯的那一個;樣本太少或散布太小,會讓它無法探索;搜尋空間也會隨視野 HH 增大。最重要的是,CEM 會非常賣力地最佳化模型的成本,所以找到模型錯誤和找到好動作一樣容易(見「規劃、不確定性與模型被利用」一節)。

參考文獻

  1. J. Ding et al., “Understanding world or predicting future? A comprehensive survey of world models,” ACM Computing Surveys, vol. 58, no. 3, 2025. doi arXiv
  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, ch. 13 “Sequential Data”. book
  3. R. Szeliski, Computer Vision: Algorithms and Applications, 2nd ed., Springer, 2022. book
  4. R. S. Sutton, “Dyna, an integrated architecture for learning, planning, and reacting,” ACM SIGART Bulletin, vol. 2, no. 4, 1991. doi
  5. T. M. Moerland, J. Broekens, A. Plaat and C. M. Jonker, “Model-based reinforcement learning: a survey,” Foundations and Trends in Machine Learning, vol. 16, no. 1, 2023. doi arXiv
  6. D. Ha and J. Schmidhuber, “Recurrent world models facilitate policy evolution,” NeurIPS, 2018; interactive version “World Models,” arXiv:1803.10122. paper interactive
  7. D. Hafner et al., “Learning latent dynamics for planning from pixels,” ICML, 2019. paper
  8. D. Hafner, T. Lillicrap, J. Ba and M. Norouzi, “Dream to control: learning behaviors by latent imagination,” ICLR, 2020. arXiv
  9. D. Hafner, T. Lillicrap, M. Norouzi and J. Ba, “Mastering Atari with discrete world models,” ICLR, 2021. arXiv
  10. D. Hafner, J. Pasukonis, J. Ba and T. Lillicrap, “Mastering diverse control tasks through world models,” Nature, vol. 640, 2025. doi arXiv
  11. N. Hansen, H. Su and X. Wang, “TD-MPC2: scalable, robust world models for continuous control,” ICLR, 2024. arXiv
  12. V. Micheli, E. Alonso and F. Fleuret, “Transformers are sample-efficient world models,” ICLR, 2023. arXiv
  13. E. Alonso et al., “Diffusion for world modeling: visual details matter in Atari,” NeurIPS, 2024. arXiv
  14. J. Schrittwieser et al., “Mastering Atari, Go, chess and shogi by planning with a learned model,” Nature, vol. 588, 2020. doi arXiv
  15. C. Finn, I. Goodfellow and S. Levine, “Unsupervised learning for physical interaction through video prediction,” NIPS, 2016. arXiv
  16. M. Babaeizadeh, C. Finn, D. Erhan, R. H. Campbell and S. Levine, “Stochastic variational video prediction,” arXiv:1710.11252, 2017. arXiv
  17. A. Hu et al., “GAIA-1: a generative world model for autonomous driving,” technical report, arXiv:2309.17080, 2023. arXiv
  18. S. Yang et al., “Learning interactive real-world simulators,” arXiv:2310.06114, 2023. arXiv
  19. J. Bruce et al., “Genie: generative interactive environments,” arXiv:2402.15391, 2024. arXiv
  20. Google DeepMind, “Genie 3: a new frontier for world models,” blog post, August 5, 2025. blog
  21. NVIDIA (N. Agarwal et al.), “Cosmos world foundation model platform for physical AI,” arXiv:2501.03575, 2025. arXiv
  22. S. Motamed, L. Culp, K. Swersky, P. Jaini and R. Geirhos, “Do generative video models understand physical principles?,” arXiv:2501.09038, 2025. arXiv
  23. B. Kang et al., “How far is video generation from world model: a physical law perspective,” ICML, 2025. arXiv
  24. M. Assran et al., “Self-supervised learning from images with a joint-embedding predictive architecture,” CVPR, 2023. doi arXiv
  25. A. Bardes et al., “Revisiting feature prediction for learning visual representations from video,” arXiv:2404.08471, 2024. arXiv
  26. M. Assran et al., “V-JEPA 2: self-supervised video models enable understanding, prediction and planning,” arXiv:2506.09985, 2025. arXiv
  27. L. Mur-Labadia et al., “V-JEPA 2.1: unlocking dense features in video self-supervised learning,” arXiv:2603.14482, 2026. arXiv
  28. G. Zhou, H. Pan, Y. LeCun and L. Pinto, “DINO-WM: world models on pre-trained visual features enable zero-shot planning,” arXiv:2411.04983, 2024. arXiv
  29. K. Chua, R. Calandra, R. McAllister and S. Levine, “Deep reinforcement learning in a handful of trials using probabilistic dynamics models,” NeurIPS, 2018. arXiv
  30. M. Janner, J. Fu, M. Zhang and S. Levine, “When to trust your model: model-based policy optimization,” NeurIPS, 2019. arXiv
  31. Z. Zhu et al., “Is Sora a world simulator? A comprehensive survey on general world models and beyond,” arXiv:2405.03520, 2024. arXiv
  32. Y. Guan et al., “World models for autonomous driving: an initial survey,” arXiv:2403.02622, 2024. arXiv
  33. D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” International Conference on Learning Representations (ICLR), 2014; arXiv:1312.6114. arXiv
  34. D. J. Rezende, S. Mohamed and D. Wierstra, “Stochastic backpropagation and approximate inference in deep generative models,” ICML, 2014. paper
  35. R. Y. Rubinstein, “The cross-entropy method for combinatorial and continuous optimization,” Methodology and Computing in Applied Probability, vol. 1, no. 2, 1999. doi
  36. P.-T. de Boer, D. P. Kroese, S. Mannor and R. Y. Rubinstein, “A tutorial on the cross-entropy method,” Annals of Operations Research, vol. 134, no. 1, 2005. doi