大家好,我是huanhu_data,我們經(jīng)常在各類算法中看到”蒙特卡羅”(Monte Carlo)的字樣, 比如MCMC(Markov Chain Monte Carlo) , 還有AlphaGo使用的蒙特卡洛搜索樹. 其實(shí), “蒙特卡羅”并不是一個(gè)特定算法, 它是一個(gè)思想或者方法的統(tǒng)稱. 聽起來很神秘, 其實(shí)用正常”人話”就能簡(jiǎn)單解釋. 維基百科對(duì)蒙特卡羅方法(英語(yǔ):Monte Carlo method)給出的解釋是: 二十世紀(jì)四十年代中期由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明,而被提出的一種以概率統(tǒng)計(jì)理論為指導(dǎo)的一類非常重要的數(shù)值計(jì)算方法。是指使用隨機(jī)數(shù)(或更常見的偽隨機(jī)數(shù))來解決很多計(jì)算問題的方法。 與它對(duì)應(yīng)的是確定性算法。 所以說, 蒙特卡羅算出的值, 不是精確的而是一個(gè)估計(jì), 但是在人們可以接受的錯(cuò)誤范圍. 下面是維基百科上一個(gè)很直觀的例子: 使用蒙特卡洛方法估算π值. 放置30000個(gè)隨機(jī)點(diǎn)后,π的估算值與真實(shí)值相差0.07%. 這張圖其實(shí)很簡(jiǎn)單, 就像我們玩飛鏢一樣, 隨機(jī)地在一個(gè)方形平面上投擲30000個(gè)飛鏢, 事先我們并不知道圓周率π的值究竟是多少, 但是我們知道這里有1/4的圓, 于是我們把紅色面積上的點(diǎn)數(shù)m, 和藍(lán)色面積上的點(diǎn)數(shù)n, 以及圓周率π的關(guān)系, 可以寫出一個(gè)約等于的式子: π ≈ 4m/(n+m) 隨著m+n的投射點(diǎn)的逐漸增加, π值的計(jì)算也越來越精確, 最后我們就估計(jì)出一個(gè)不錯(cuò)的比較精確的π值啦 大家看這個(gè)是不是在哪里很熟悉? 沒錯(cuò), 就是大數(shù)定律的思想嘛… 只不過大數(shù)定理強(qiáng)調(diào)統(tǒng)計(jì)學(xué)中的極限和期望, Monte Carlo方法這是計(jì)算機(jī)中的模擬, 用有限隨機(jī)數(shù)去計(jì)算估計(jì)值. 所以Monte Carlo只是這種思想的統(tǒng)稱, 與特定算法結(jié)合會(huì)有不同表現(xiàn)形式. 當(dāng)然Monte Carlo不只是能估計(jì)值那么簡(jiǎn)單, 它可以用來估計(jì)未知分布, 未知模型參數(shù), 等等, 所以在很多抽樣方法中有Monte Carlo的身影, 比如大名鼎鼎的MCMC. 接下來我們環(huán)湖醫(yī)院數(shù)據(jù)中心來趴一趴蒙特卡羅方法的歷史: 20世紀(jì)40年代,在馮·諾伊曼,斯塔尼斯拉夫·烏拉姆和尼古拉斯·梅特羅波利斯在洛斯阿拉莫斯國(guó)家實(shí)驗(yàn)室為核武器計(jì)劃工作時(shí),發(fā)明了蒙特卡洛方法。因?yàn)闉趵返氖迨褰?jīng)常在蒙特卡洛賭場(chǎng)輸錢得名,而蒙特卡羅方法正是以概率為基礎(chǔ)的方法。 蒙特卡羅方法的名字來源于摩納哥的一個(gè)城市蒙地卡羅,該城市以賭博業(yè)聞名,大家都知道, 賭錢這個(gè)問題, 一般是沒有精確解的. 但是, 只要你是個(gè)老賭徒, 那最后, 你會(huì)對(duì)整個(gè)賭局有更全面的認(rèn)識(shí), 不是嗎? |
|