蒙特卡羅方法如何化簡為繁

本文不用公式，僅僅是想說明這種方法的基本思想以及潛在應(yīng)用。由于該方法應(yīng)用廣泛，技術(shù)細(xì)節(jié)值得深入研究，因此需要一系列文章來闡述，本號后面會陸續(xù)展開。

1
引 言

蒙特卡羅（Monte Carlo，MC）方法，是指使用隨機(jī)性（貌似變繁了）來解決很多確定性問題（貌似是簡單的）的方法。它們使用重復(fù)性隨機(jī)采樣的過程來進(jìn)行未知參數(shù)的數(shù)值估計，是以概率統(tǒng)計理論為指導(dǎo)的數(shù)值計算方法。

MC 允許對涉及許多隨機(jī)變量的復(fù)雜情況進(jìn)行建模，其用途極為廣泛，并在物理學(xué)、博弈論和金融領(lǐng)域帶來了許多開創(chuàng)性的成果。2016 年，打敗人類頂級圍棋手的 AlphaGo 橫空出世，背后的兩大核心技術(shù)之一就是蒙特卡羅樹搜索方法。

蒙特卡羅方法種類繁多，但是它們都有共同點，即它們依靠隨機(jī)數(shù)生成來解決確定性問題。本篇概述 MC 的一些基本思想，并對它們潛在的應(yīng)用有所了解。

想象一下在坐標(biāo)網(wǎng)格上的一個 正方形區(qū)域。在該網(wǎng)格上繪制了一些形狀，假設(shè)你并不知道它的解析表達(dá)式。但是，你可以查詢示性函數(shù)的值 ，其中 是點的坐標(biāo)，當(dāng)該點在形狀中則函數(shù)輸出是 ，反之輸出 。那么，你將如何估計形狀的面積呢？

盡管這種關(guān)于隨機(jī)采樣的直觀想法很簡單，但它在實際應(yīng)用中卻廣受親睞，例如從法律到氣候預(yù)測的許多領(lǐng)域都有廣泛應(yīng)用，并且與本文的主題（機(jī)器學(xué)習(xí)和統(tǒng)計）可能是最相關(guān)。它的正式名稱正是: 蒙特卡羅方法。

當(dāng)遇到一個由確定性原則組成的問題時，比如形狀的面積、函數(shù)的分布、在游戲中玩家下一步應(yīng)該選擇什么操作等，蒙特卡羅方法可以假設(shè)可以通過概率和隨機(jī)性來對這些問題建模。

? 蒙特卡羅方法依賴于來自某個分布的重復(fù)性隨機(jī)采樣來獲得數(shù)值結(jié)果。這是一種方法，而不是一個具體的算法。

蒙特卡羅方法怎么來的？其實它并不是人名，而是摩納哥的著名賭城。蒙特卡羅法作為一種計算方法，是由美國數(shù)學(xué)家烏拉姆（Stanislaw Ulam）與美籍匈牙利數(shù)學(xué)家馮·諾伊曼（John von Neumann）在 20 世紀(jì) 40 年代中葉，為研制核武器的需要而首先提出來的。烏拉姆在洛斯阿拉莫斯國家實驗室從事核武器項目時，提出了馬爾可夫鏈蒙特卡羅方法。烏拉姆取得突破后，約翰·馮·諾伊曼立刻意識到了它的重要性。馮·諾依曼在首臺計算機(jī) ENIAC 上編寫程序以執(zhí)行蒙特卡羅計算。

但實際上，該方法的基本思想早就被統(tǒng)計學(xué)家所采用了，例如早在 18 世紀(jì)，法國數(shù)學(xué)家蒲豐（或布豐）提出了用隨機(jī)投針來計算圓周率的方法。下面，我們用這個類似思想但更簡單的方法來計算 。

同時也作為一個基于形狀的示例，請思考不使用任何數(shù)學(xué)方法（僅使用蒙特卡羅采樣）來找出圓形面積的公式。隨機(jī)采樣可以用作找到函數(shù)積分（曲線下的面積）的簡易方法。重要的是，圓周率 的值也可以通過蒙特卡羅采樣來近似計算，

下面，我們來用幾行簡單的 Python 代碼來模擬一下，

import?numpy?as?np?
import?matplotlib.pyplot?as?plt?

n?=?5000
x?=?np.random.rand(n,?2)
inside?=?x[np.sqrt(x[:,0]2+x[:,1]2)<1]
estimate?=?4*len(inside)/len(x)?
print?('Estimate?of?pi:{}'.format(estimate))?

plt.style.use("bmh")
plt.figure(figsize?=(8,8))?
plt.scatter(x[:,?0],?x[:,?1],?s=.85,?c='red')
plt.scatter(inside[:,?0],?inside[:,?1],?s=.5,?c='blue')
plt.show()

Estimate of pi:3.128

通常，蒙特卡羅方法涉及的采樣方法可以分為三類，

• 直接采樣。無需任何先驗信息即可從分布中直接進(jìn)行抽樣。
• 重要性抽樣。如果分布太復(fù)雜而無法從中進(jìn)行采樣時，則使用更簡單的近似函數(shù)進(jìn)行采樣。這是貝葉斯優(yōu)化和代理優(yōu)化的核心思想。
• 拒絕采樣。在滿足某些標(biāo)準(zhǔn)的情況下接受采樣點。將采樣一個數(shù)據(jù)作為一個提議，通過一個接受概率來確定要不要接受這個提議。

第一類直接采樣方法就是上面逼近形狀面積的方法，而其他兩類方法后續(xù)文章再作具體介紹。

2MCMC

通?？梢栽趦煞N情況下使用蒙特卡羅采樣：

• 優(yōu)化問題。要找到最佳狀態(tài)，就需要在探索（exploration）與開發(fā)（exploitation）之間保持一定平衡。當(dāng)蒙特卡羅采樣（探索）與另一種機(jī)制配合使用來控制開發(fā)，它可能是找到最優(yōu)值的有力工具。
• 概率和函數(shù)逼近問題。蒙特卡羅采樣法是一種間接評估某些概率或函數(shù)的很好方法，特別是當(dāng)通過其他方法很難實現(xiàn)這點時。

由于蒙特卡羅方法的基本思想很簡單，但是可能會以相當(dāng)復(fù)雜和創(chuàng)造性的方式來使用，因此最好通過幾個示例來揭示其思路。

首先，請考慮馬爾可夫鏈蒙特卡羅（MCMC）方法，該方法嘗試從目標(biāo)分布生成隨機(jī)樣本，但是不知道分布具體是什么。馬爾可夫鏈（Markov Chains）可以用于表示這些分布。具體來說，馬爾可夫鏈?zhǔn)且粋€圖，其中每個節(jié)點都是一個狀態(tài)，以及轉(zhuǎn)移到另一個狀態(tài)的概率 。

考慮一下某個天氣惡劣的城市，用馬爾可夫鏈表示天氣，假設(shè)那里的天氣狀況是風(fēng)、冰雹/雪、雷暴或降雨。每天都可以根據(jù)當(dāng)天天氣來預(yù)測第二天的天氣。例如，如果今天下雪，則明天有 的概率會刮風(fēng)，以及 的概率會下雨。

要在馬爾可夫鏈上遍歷，我們從一個位置 開始，以指定的概率移至另一個 。接著， 會成為新的 ，然后重復(fù)該過程。盡管此示例以一個很小的馬爾可夫鏈為例，但是具有數(shù)千個或數(shù)十萬個節(jié)點的巨大圖則可以用于建模更加復(fù)雜的概率關(guān)系。

如果我們經(jīng)過大量時間（例如 10,000 個模擬天）遍歷馬爾可夫鏈，就會達(dá)到一種概率平衡。這意味著，根據(jù)大數(shù)定律，我們可以簡單地基于我們遍歷的節(jié)點狀態(tài)中有多少在下雨來估計下雨的概率。

例如，如果通過馬爾可夫鏈在 10,000 多個狀態(tài)中轉(zhuǎn)移收到了以下結(jié)果：

• Wind 節(jié)點遍歷 2754 次
• Thunderstorm 節(jié)點遍歷 1034 次
• Hail/Snow 節(jié)點遍歷 4301 次
• Raining 節(jié)點遍歷 1911 次

根據(jù)這個模型，我們可以得到如下概率：

• P(Wind) = 0.2754
• P(Thunderstorm) = 0.1034
• P(Hail/Snow) = 0.4031
• P(Raining) = 0.1911

然后，你可以簡單地從分布中進(jìn)行相應(yīng)采樣，即從馬爾可夫鏈中以一定概率隨機(jī)抽取一個狀態(tài)，而無需動態(tài)遍歷該狀態(tài)。通過蒙特卡羅采樣以后，即馬爾可夫鏈的反復(fù)迭代和隨機(jī)遍歷，該系統(tǒng)能夠折疊起來表示概率分布。

? 小結(jié): 可以構(gòu)造馬爾可夫鏈來建模無法直接采樣的復(fù)雜關(guān)系，然后對其進(jìn)行簡化以找到其潛在的概率分布。

有許多完善的 MCMC 算法，例如 Metropolis-Hastings 算法或 Gibbs 采樣。都是試圖對系統(tǒng)的潛在概率進(jìn)行建模。

3應(yīng) 用

要將理論投入到實際應(yīng)用，可以看一下蒙特卡羅樹搜索（MCTS），它是用于智力游戲的強(qiáng)化學(xué)習(xí)系統(tǒng)的關(guān)鍵部分。早期的游戲系統(tǒng)，例如 IBM 深藍(lán)在 1997 年擊敗國際象棋冠軍 加里·卡斯帕羅夫（Gary Kasparov）的最初勝利，是基于類似 minimax 的算法，該算法可以遍歷基于當(dāng)前局面的所有可能下法，并確定能夠取得絕對勝利（或最高機(jī)率）的下法。

隨著游戲變得更加復(fù)雜（最著名的是圍棋游戲甚至是 DOTA 之類的射擊游戲），遍歷所有可能的場景在目前的計算力上是不可行時，也是不明智的。取而代之的是，明智的做法是讓玩家利用已知動作來探索潛在的有益動作，同時放棄極有可能失敗的動作。

讓我們來像這樣構(gòu)造一棵樹，其中每個節(jié)點代表某種游戲狀態(tài)?？梢酝ㄟ^采取某些行動在節(jié)點之間轉(zhuǎn)移。從游戲的初始狀態(tài)開始，我們可以采用幾個可能的節(jié)點。

價值神經(jīng)網(wǎng)絡(luò)試圖在每一步上都賦予價值:?給定這一步，智能體獲勝的概率是多少？請注意，一開始，由于價值網(wǎng)絡(luò)尚未經(jīng)過訓(xùn)練，因此將給出隨機(jī)的猜測。但是，隨著系統(tǒng)經(jīng)歷足夠多的游戲，它將可以更智能地分析某些動作的效果。

可以執(zhí)行簡單的加權(quán)蒙特卡羅采樣，而不是簡單地選擇概率最高的節(jié)點。如果網(wǎng)絡(luò)認(rèn)為節(jié)點 2 將有 90％ 的獲勝機(jī)會，則它有更大的機(jī)會被選中，但仍然還是有可能會選擇節(jié)點 3 和 1。該方式訓(xùn)練了一個如何選擇潛在節(jié)點的策略。

其背后的邏輯是，某個動作的可預(yù)見價值受到可能性的限制（也許對手會做出意想不到的動作）。這樣可能有利于發(fā)現(xiàn)會帶來更多好處的動作，此外，僅僅利用已知動作而不冒險探索其他可能空間會導(dǎo)致競爭性和惰性模型的出現(xiàn)，這點是復(fù)雜的強(qiáng)化學(xué)習(xí)環(huán)境中并不希望看到的。

然后，被選中節(jié)點將進(jìn)一步擴(kuò)展，并重復(fù)該過程，直到游戲終止。將概率納入決策制定過程中，而不是確定性地選擇最佳價值，這有助于強(qiáng)化學(xué)習(xí)平衡開發(fā)和探索兩者之間的取舍。

如果我們從統(tǒng)計學(xué)的角度來看這一點，則使用蒙特卡羅采樣對最佳概率分布 進(jìn)行建模，以選擇一個具有一定可預(yù)見值 的節(jié)點。

蒙特卡羅樹搜索（MCTS）是 DeepMind 開發(fā)的強(qiáng)化學(xué)習(xí)系統(tǒng) AlphaGo 擊敗頂級圍棋選手的功臣。此外，MCTS 在其他地方也具有廣泛的應(yīng)用。

模擬退火是蒙特卡羅方法的另一種應(yīng)用，在尋找全局最優(yōu)值的任務(wù)中充當(dāng)非梯度函數(shù)優(yōu)化的一種有效方法。像應(yīng)用其他問題的蒙特卡羅方法一樣，搜索空間是離散的，因為我們并不打算嘗試優(yōu)化連續(xù)值。

在那些以固定的時間內(nèi)找到近似全局最優(yōu)值比其精確值更有價值的問題中，模擬退火實際上可能比梯度下降之類的算法更可取。

模擬退火的思想來自冶金學(xué)，退火是對材料的受控加熱或冷卻，以增加其尺寸并消除缺陷。同樣，模擬退火控制系統(tǒng)中的能量，這決定了在探索新可能性時愿意承擔(dān)多少風(fēng)險。

溫度從某個初始值開始，這代表了各種計時器。在每個狀態(tài) 處，模擬退火會以概率 轉(zhuǎn)移至某個相鄰狀態(tài) ，其中概率由兩個狀態(tài)的值（正在向 增大還是減??？）以及當(dāng)前溫度 決定。

當(dāng)溫度隨著每個時間步長降低，模型的探索性就會降低，從而變得更具開發(fā)性。模擬退火允許從探索到開發(fā)的逐步過渡，這對于發(fā)現(xiàn)全局最優(yōu)是非常有益的。

蒙特卡羅采樣和貝葉斯方法用于對概率函數(shù) 進(jìn)行建模。實際上，像 Metropolis-Hastings 算法通常是將馬爾可夫鏈蒙特卡羅方法用于查找轉(zhuǎn)移閾值。這是自然的，因為模擬退火將解視為狀態(tài)以及一種適合馬爾可夫鏈建模的環(huán)境，并試圖找到最佳的轉(zhuǎn)移概率。

通常，蒙特卡羅方法或類似蒙特卡羅的方法會出現(xiàn)在我們最不期望的地方。盡管它是一種簡單的機(jī)制，但它在無數(shù)的應(yīng)用程序中都有著深厚而復(fù)雜的根源。

4小 結(jié)

• 蒙特卡羅方法基于以下思想: 將隨機(jī)性引入系統(tǒng)通?？梢杂行У亟鉀Q問題。
• 蒙特卡羅方法涉及的采樣通常分為三類: 直接采樣，重要性采樣以及拒絕采樣。
• 蒙特卡羅方法的兩個常見應(yīng)用包括優(yōu)化以及對復(fù)雜概率和函數(shù)的估計。
• 在離散（非連續(xù)）以及確定性問題中，蒙特卡羅方法利用隨機(jī)性+概率、大數(shù)定律以及高效采樣框架來解決這些問題。
  
  

  .?相關(guān)閱讀?.

  一個例子理解 AlphaGo 的技術(shù)原理

?參考資料?