機(jī)器學(xué)習(xí)算法之蒙特卡洛

1、大家聽(tīng)說(shuō)過(guò)的算法，比如快速排序法、二分查找法，或是像梯度下降 法、K近鄰算法，這些算法都有比較嚴(yán)格的邏輯要求，使用起來(lái)有些繁瑣。這里我們介紹一個(gè)很簡(jiǎn)單卻又通常行之有效的算法：蒙特卡洛方法。 嚴(yán)格來(lái)說(shuō)，蒙特卡洛方法并不是特指某一種具體的算法，而是對(duì)遵循某種 思想的算法的統(tǒng)稱(chēng)，應(yīng)該是一 “類(lèi)”算法?！霸谠囼?yàn)不變的條件下，重復(fù)試驗(yàn)多次，隨機(jī)事件的頻率近似于它的 概率”，這個(gè)統(tǒng)計(jì)學(xué)規(guī)律在數(shù)學(xué)上被稱(chēng)作“大數(shù)定律”，也很符合我們的 自然直觀。蒙特卡洛方法正是在這個(gè)規(guī)律的指導(dǎo)下，應(yīng)用隨機(jī)手段來(lái)逼近 一些難以直接求解的數(shù)值?！懊商乜宸椒ā边@個(gè)名稱(chēng)看起來(lái)奇奇怪怪的，其實(shí)當(dāng)中的“蒙特卡 洛”指的就是著名賭城蒙特

2、卡洛，傳聞是由于該方法的發(fā)明者之一烏拉姆 的叔叔常在此處輸錢(qián)而得名一一不得不說(shuō)這個(gè)命名確實(shí)是很隨意哈哈。但 是認(rèn)真來(lái)說(shuō)，賭博與概率/統(tǒng)計(jì)的學(xué)科發(fā)展相依相伴，貫穿始終，既是統(tǒng)計(jì) 學(xué)的發(fā)源地，又是概率論的演練場(chǎng)，以賭城之名來(lái)命名這樣一個(gè)完全依賴(lài) 于隨機(jī)性的方法，也果然是相得益彰，十分到位。說(shuō)到這里不得不提一嘴 的是，同為著名賭城，拉斯維加斯也有自己的“冠名算法”，本文就不做 詳述了，感興趣的同學(xué)可以自行了解。1.蒙特卡洛方法的原理實(shí)際上之前我們已經(jīng)提到過(guò)了，蒙特卡洛方法的有效性是建立在大數(shù) 定律的基礎(chǔ)上的，也就是說(shuō)我們需要通過(guò)模擬這樣一個(gè)不斷重復(fù)的隨機(jī)過(guò) 程，來(lái)獲得與正常的反復(fù)隨機(jī)試驗(yàn)相同的結(jié)果，

3、因此該方法也被稱(chēng)為“蒙 特卡洛模擬法”。隨著實(shí)驗(yàn)次數(shù)（即隨機(jī)樣本）的增加，從統(tǒng)計(jì)學(xué)意義上來(lái)說(shuō)，得到的 結(jié)果會(huì)越來(lái)越精確，與正確結(jié)果的誤差會(huì)越來(lái)越小。之所以說(shuō)是“統(tǒng)計(jì)學(xué) 意義上”，是因?yàn)檫@種方法并不保證2001次隨機(jī)試驗(yàn)的結(jié)果一定比 2000次隨機(jī)試驗(yàn)的結(jié)果更加準(zhǔn)確，甚至不能保證比1次實(shí)驗(yàn)的結(jié)果更準(zhǔn)確；但總體來(lái)看，實(shí)驗(yàn)次數(shù)越多，得到的結(jié)果確實(shí)更加可信。通過(guò)上面的分析我們可以看出，蒙特卡洛方法使用的場(chǎng)景是相對(duì)比較 靈活的，并且更適合對(duì)數(shù)據(jù)的精度要求并不太嚴(yán)格的場(chǎng)合。一般來(lái)講，工 業(yè)領(lǐng)域的精度要求是完全可以被蒙特卡洛方法滿(mǎn)足的。2.兩個(gè)應(yīng)用實(shí)例 這兩個(gè)實(shí)例本質(zhì)上是一樣的2.1求n的值凡講到蒙特卡洛方

4、法，這幾乎都是一個(gè)必被提及的應(yīng)用實(shí)例。正方形與其內(nèi)切圓上圖所示，陰影部分是一個(gè)半徑為 1的圓形，另有一個(gè)邊長(zhǎng)為2的正方 形與之相切。我們從小就知道，圓面積公式為：= ITT3其中，S1為圓面積，r為圓半徑，n則是一個(gè)常數(shù)。正方形面積公式為：其中，S2為正方形面積，l為正方形邊長(zhǎng)。顯然，對(duì)于特定的正方形，其內(nèi)切圓的直徑一定與正方形邊長(zhǎng)相等，也就是說(shuō)圓半徑是正方形邊長(zhǎng)的一半：。這樣，我們只要再知道S1和S2的比值，就可以根據(jù)上面這兩個(gè)面積公式求出n的具體數(shù)值了。更進(jìn)一步地，由于圓形和正方形都具有特殊的對(duì)稱(chēng)性，因此我們可以只考 察一部分圖形，同樣可以得到相同的結(jié)果：正方形與其內(nèi)切圓-部分那么問(wèn)題的關(guān)

5、鍵就在于，這個(gè)比值到底應(yīng)該怎么求呢？方法有很多，最容易想到的就是對(duì)圓形求積分，得到對(duì)應(yīng)的面積。對(duì)計(jì)算 機(jī)來(lái)講，我們可以返璞歸真，用積分的思想，將圖中這個(gè)扇形劃分為大量 小“矩形”，對(duì)小矩形面積求和即可得到扇形面積。但是還有一種更加直接的方法。我們可以在圖示的正方形中直接隨機(jī)撒下 一些點(diǎn)，然后統(tǒng)計(jì)落在扇形內(nèi)部的點(diǎn)的個(gè)數(shù)，這個(gè)個(gè)數(shù)比上我們?nèi)鱿碌狞c(diǎn) 的總個(gè)數(shù)，也就近似等于扇形面積與正方形面積之比。正方形與其內(nèi)切圓-部分-隨機(jī)撒點(diǎn)結(jié)合上述分析，我們可以得到 n值的計(jì)算式:好了，鋪墊了這么多，接下來(lái)讓我們直接上代碼: import ran dom REPEAT = 2 0000 # 實(shí)驗(yàn)次數(shù) count

6、 = 0 #用于記錄落在扇形內(nèi)部的隨機(jī)點(diǎn)數(shù) f-or i i n range ( REPEAT ): x = random.random()并生成.吼1，H)區(qū)間內(nèi)的均勻分布隨機(jī)數(shù). y = random.random(). if xx + y*y ratio = co Jilt / REPEAT PI = 4 * ratio PI3.13B8可以看到，最后得到的n值與實(shí)際值是比較接近的。2.2求積分同樣地，在很多情境下，對(duì)于一些比較難以求出解析式的積分，或是即使 知道解析式計(jì)算起來(lái)也比較麻煩的積分，我們并不需要一味地求出準(zhǔn)確積 分，而只需要通過(guò)蒙特卡洛方法得到一個(gè)粗糙的近似值即可，大大降低了

7、 計(jì)算的成本。實(shí)際上，第一個(gè)例子的扇形面積可以從積分的角度考慮，而這個(gè)例子中的 積分也同樣可以從面積的角度考慮，二者本質(zhì)上并無(wú)區(qū)別。這里我們就以一個(gè)簡(jiǎn)單的積分為例，演示一下用蒙特卡洛方法求解積分的 過(guò)程。x的平方圖中所示函數(shù)為，所以應(yīng)該等于1/3,也就是0.666。放碼過(guò)來(lái)看看:import ndomdef solve_integral(repeat = 200Q0) - float count = 0For 1 in rangerepeat):x = random.randomf)y = ra ndom.random()count += 1ratio = count / repeat integral = ratio 1 return inte-gralif _name_ = _main_:Pepeat = irbtfinputf請(qǐng)輸入實(shí)瞼次數(shù)：) print ( 5olve_integral( re p-eat)#請(qǐng)輸入實(shí)驗(yàn)次數(shù)；509090芾 0.6660663.總結(jié) 本文簡(jiǎn)單介紹了一種簡(jiǎn)單的隨機(jī)算法一