酷播亮新聞
因隨機性的到來
闊然開朗
1
蒙特卡羅賭場
蒙特卡羅（Monte Carlo）是摩納哥公國（Principality of Monaco）的一座城市。摩納哥公國坐落在法國的東南方，總面積為2.02平方公里，是世界上第二小的國家，也是一個從地圖上看容易被忽略的國家。
摩納哥的位置非常小，不仔細看都發現不了
但就在這裡，卻誕生了一個聞名世界的大賭場——蒙特卡羅大賭場（Monte Carlo Casino）。
蒙特卡羅賭場的開張其實有這麼一段歷史。19世紀50年代，摩納哥有2個小鎮宣布獨立，稅收大幅減少，摩納哥皇室陷入破產邊緣。無奈之下，卡羅琳王妃（Florestan一世的妻子）提出了一個設想：仿造巴特洪堡賭場（Bad Homburg Casino），建造一個賭場以創造更大的收入。
但是因賭場地理位置偏僻，而且當時的摩納哥缺乏良好的交通條件，旅遊者並不喜歡過來進行度假。這也導致賭場開張後，一直處於虧損狀態，幾任老闆到最後無法支撐，放棄經營。
卡羅琳王妃不忍心看到這個局面，千辛萬苦請來了巴特洪堡賭場的實際經營者弗朗索瓦·布朗（Fran?ois Blanc），並建立了一家專門的公司來運營賭場。作為新公司主要的大股東，布朗利用其強大的人際關係網路，迅速募集資金，大規模擴建賭場。為了吸引遊客，布朗還提議把當地名字Spelugues改了。後來當地改名為Monte Carlo，以向當時的執政者查爾斯三世（Charles III, Prince of Monaco）致敬。
傍晚時分，靜謐的蒙特卡羅賭場
重新豪裝後的蒙特卡羅賭場吸引來了無數賭客，成為當時有名的不夜城。
在蒙特卡羅賭場中，輪盤（Roulette）一直是最受歡迎的項目，因為賭客一直覺得這種賭法有較大的獲勝機會。原來輪盤上有37個格子，其中有18紅格，18個黑格，1個綠格。賭客隨意押注紅格或者黑格。理論上說，出現紅色的概率和黑格的概率是一樣的，一旦出現黑色的次數超過了5次，那都是一個非常小概率的事件，而在這種情況下很多賭徒會賭紅色，即執行這類反方向的策略。
輪盤賭具
這或許就是人類思維和數據思維差異。實際上，每一次輪盤的轉動都是獨立事件，前面一次小球停留的位置，和下一次小球停留的位置不會有任何關聯。無論小球停在紅色或者黑色的位置，都是隨機的，並不會受到之前結果的影響。
當然，從更宏觀的角度來說，無論賭局規則怎麼變化，賭場必定要賺錢的。賭場精心設計各種規則的賭局，讓人們樂在其中的同時，賭場收取少許手續費。正是這種少許的手續費，讓賭場經營者得以生存和擴大，而賭客之間則進行負和博弈，從長期來看，賭客是虧損的。
2
蒙特卡羅方法誕生
時間來到1946年，也是蒙特卡羅大賭場誕生的90周年。
塔尼斯拉夫·烏拉姆（Stanislaw Ulam）是一位波蘭裔美國科學家，他當時在洛斯阿拉莫斯國家實驗室（Los Alamos National Laboratory, LANL）進行核武器的研發。此時科學家們在研究輻射防護（radiation shielding），期望計算中子穿越物質的距離。儘管已經通過實驗獲得大量的數據，LANL實驗室的科學家們卻無法用傳統確定性的方法來解決這個問題。
後來因為身體原因，烏拉姆便休假療養身體，無聊之際打牌閑度時光。有一天，烏拉姆還是在打牌，突然他想到了一個問題：如果我想從52張牌當中拿到同花順，這個概率是多少呢？
相信把做數學推導作為無聊消遣的人也不多，此時烏拉姆就放下手牌，拿起紙和筆熟練地利用組合公式進行概率計算。經過很長時間的計算，烏拉姆發現這件事情沒那麼簡單（可能是因為不下去了）。
他又想意識到另一個問題：理論計算太複雜了，有沒有一個更加實際的方法來算？比如我模擬100次，看看出現同花順的次數有多少次，這樣就可以近似得到同花順出現的概率了。
烏拉姆於是開始聯想到中子擴散現象上，同時想到了如何將差分方程等價轉換為一系列隨機模擬過程。在這短暫的時間內，人類一扇新的知識大門悄然打開。
烏拉姆急沖沖地把這個方法告訴給他的同事，著名數學家馮·諾依曼（John von Neumann），馮諾依曼確定這個方法是一個重大突破，並且很快在ENIAC（ENIAC是世界上最早期的計算機）電腦上完成了編程。
ENIAC，世界上最早期的電腦，可以佔據一個超大房間
為了保密起見，需要給這個程序起一個名字。烏拉姆和馮諾依曼的同事，著名物理學家尼古拉斯·梅特羅波利斯（Nicholas Metropolis）提議名字取為Monte Carlo，以紀念蒙特卡羅大賭場，原因是烏拉姆的叔叔不了解概率，經常在那裡輸錢。
但這個蒙特卡羅方法（Monte Carlo Method）需要大量的隨機數，而真實的隨機數並沒有那麼多，怎麼辦呢？當然在數學家們面前這不可能成為一個障礙，馮諾依曼順手解決了這個問題，進一步發展了隨機數生成器技術（Pseudorandom number generator, PRNG）。
隨後，蒙特卡羅方法被大量地用於曼哈頓計劃（Manhattan Project）中的各項計算和模擬，解決了大量以往確定性方法不能解決的計算問題。20世紀50年代，在LANL實驗室中被用於氫彈的研發，再往後開始在各個領域被大規模地運用，帶來了一場新的思想革命。人們發現，除了傳統確定性方法以外，原來還有一種有效的計算方法，叫蒙特卡羅方法。
曼哈頓計劃集中了大量優秀的科學家，利用核裂變反應來研製原子彈，最後取得圓滿成功
3
蒙特卡羅演算法是怎麼回事
事實上，蒙特卡羅方法非常簡潔。我們用一個例子來說明，如何用蒙特卡羅方法近似得到圓周率？
我們先設置一個1×1的空間，在這個空間中以點(0,0)為圓心，畫一個半徑為1的圓，在1×1空間中留下四分之一圓。
從理論上分析，在1×1的空間的空間中，有這樣的關係：
只要得到四分之一圓的面積與正方形的面積之比，所以可以知道圓周率是多少。
從蒙特卡羅方法的角度看，在1×1這個區間上可均勻地投放大量的點。這些點投到四分之一圓內的概率，近似等於投到四分之一圓內點的比例，即：
所以，我們可以通過計算點個數的方式，來近似得到圓周率的數值。
把大量的點投在1×1的空間中，計算落在圓弧內的數量，以估算圓周率π
這種數點的方式雖然簡單，但看起來不是那麼靠譜，能否證明蒙特卡羅方法的有效性呢？
實際上已經證明，隨著模擬次數N的增加，蒙特卡羅所得到的近似值與目標值的誤差將以N-0.5的速度降低，結果將越來越精確（可用方差的定義展開進行證明）。
誤差隨著模擬次數的增加而不斷下降，速率為N
-0.5
4
蒙特卡羅演算法的案例
隨著蒙特卡羅方法的成熟及更廣泛的使用，便出現了很多基於蒙特卡羅方法的新演算法，用一個時髦的名詞就是：蒙特卡羅「硬分叉」了。
蒙特卡羅積分（Monte Carlo intergration）
在低維的情況下，用確定性的方法來計算積分效果非常好。但到高維的時候，一方面計算難度呈指數級增加，產生維數災難（curse of dimensionality），另一方面在多維的情況下，邊界的確定非常困難，100維以上基本不可能用確定性方法來計算。
蒙特卡羅方法跳出了維數災難的想法，提供了一個新的思路：在高維空間中產生大量的點，採用類似近似計算圓周率的方法，計算高維積分。使用蒙特卡羅方法，誤差將以N-0.5的速度降低，不管維數是多少，只要提升4倍數量的點，誤差將降低一半。因此蒙特卡羅方法非常適合運用在高維的積分計算當中。
如何計算小沙堆體積？用蒙特卡羅積分法即可
蒙特卡羅定位（Monte Carlo localization）
在室外定位，自從有了GPS以後，基本上沒有問題了。但是由於沒有信號的支持，室內定位還是屬於一個難點。
隨著掃地機器人的普及，也讓越來越多人了解到人工智慧是相當厲害的。但對於一個掃地機器人來說，假設它在已經通過前期的掃描獲知屋子室內地圖的情況下，它是怎麼做到確定自己所在的位置呢？
為什麼要問這個問題？也許這個問題是不用考慮的，因為機器人往哪個方向車輪轉動了多少圈它都可以記錄下來。雖然如此，這種記錄實際上是有一定誤差的，比如輪子轉動了1圈，在光滑的地面只能向前移動0.1米，而在粗糙的地面可以向前0.11米，如果沒有及時糾正，隨著時間的積累這個誤差將越來越大。
蒙特卡羅定位法（Monte Carlo localization）又稱粒子濾波定位法（particle filter localization），可以有效地解決這類室內定位的問題。我們以一個實例來看一下這個演算法的運用。首先我們把一個機器人放到一個一維的空間上，如圖所示。
一個可愛的機器人，它會識別眼前的環境
在這個一維空間上，機器人通過前期的探索，已經知道這個空間一共有3個外觀都是一樣的門，並記錄了門口的樣子。
問題來了，機器人怎麼確定自己在哪裡呢？
Step 1：機器人在這個一維空間上隨機生成大量的粒子，每一個粒子分別代表一種位置的可能性（稍後將闡述實際含義）。
Step 2：機器人通過攝像頭髮現自己站在一個門口前面。由於機器人已經知道室內地圖，知道門口具體在哪幾個位置，因此機器人重新分配所有粒子的權重，將室內地圖門口所在位置範圍的粒子權重相應提升上來。
Step 3：機器人根據權重分布，重新生成新的粒子。權重越大的地方獲得的粒子越多。
假設機器人繼續往前移動一小段距離：
Step 4：機器人到了一個沒有門口的地方，同時所有的粒子跟隨著機器人移動。
Step 5：機器人發現眼前沒有東西。由於機器人已經知道室內地圖，知道門口具體在哪幾個位置，因此機器人重新分配所有粒子的權重，將室內地圖門口所在位置範圍的粒子權重相應降低下來。
Step 6：機器人根據權重分布，重新生成新的粒子。權重越大的地方獲得的粒子越多。
可以發現，經過這兩輪操作以後，粒子分布集中程度提升了，可以預見粒子將越來越集中。這個方法精巧地運用了蒙特卡羅的隨機特徵，不斷產生新的粒子來記錄位置概率。粒子分布集中的位置，也就是機器人所在的位置。
蒙特卡羅搜索樹（Monte Carlo tree search, MCTS）
蒙特卡羅方法還發展成了蒙特卡羅搜索樹的方法，能夠有效幫助在遊戲中搜索出最佳策略。MCTS每生成一個新的策略，演算法將基於這個新策略進行大量的隨機實驗來模擬運用新策略以後的影響，比如比賽勝率或者分數。然後按照一定的指標進行樹節點的擴展。
MCTS的一個最著名的例子，當屬由DeepMind團隊研發的、擊敗人類世界圍棋頂尖高手的AlphaGo。
AlphaGo當中的MCTS
元啟發式演算法（Metaheuristic）
自從蒙特卡羅方法誕生後，元啟發式演算法的發展才正式開始。比如模擬退火演算法（Simulated Annealing）、遺傳演算法（Genetic Algorithm）、螞蟻演算法（Ant Colony Optimization）等等，這些帶有隨機性的演算法都是解決組合優化問題的好方法。
2006年NASA在ST5航天器上搭載了一個特別的天線，其形狀由進化演算法設計而成
在過去漫長的歲月當中，人們都認為必須要經過嚴謹的推理和計算，才能得到最後正確的答案。直到最近的數十年，隨著計算機的誕生，還有烏拉姆、馮諾依曼以及眾多理解蒙特卡羅方法的科學家的努力下，隨機性的運用才逐漸走進我們的視野。人們意想不到地發現隨機性是一個如此重要的思維，隨機性並非如想像中那樣是一個不好的事物，合理地利用隨機性，能夠幫助我們探索前所未有的世界。
蒙特卡羅方法的發明，是人類思維史上的一個重大突破。一個隨機性的構想，打破了過去的思考空白區，開啟了人類新的思維空間。
本文系網易新聞·網易號「各有態度」特色內容
部分資料來源於網路
轉載請在公眾號中，回復「轉載」
—–這裡是數學思維的聚集地——
