抽樣與蒙地卡羅(二)：蒙地卡羅方法與重要性抽樣
Sampling and Monte Carlo (02)： Monte Carlo Method & Importance Sampling
前言
為甚麼要介紹蒙地卡羅? 上一篇提到，這是為了更好地去理解機器學習甚至強化學習所需的準備。我們可以將強化學習、深度學習想像成一連串的路徑，這些路徑代表了所有通往解答 (無論是最佳解答或是區域最佳解)的可能過程，我們需要兩樣東西來找出一個最好的路徑，其一是知道怎麼樣去搜尋是最有效率的，其二則是需要確保你在完善的環境下去執行這個搜尋，環境包含了擁有充足的資料，且有高品質的資料等等。關於第一點，台大在 Coursera 上有一門課叫做【人工智慧：搜尋方法與邏輯推論】，由于天立老師開設，對於進入到更深層次的 ML/DL/RL 打下深厚的基礎：
第一點當然就是許多機器學習中提到的最佳化理論等學科，而第二點實際上有很多種形式，最好的方法就是你真的能蒐集到實際的資料，但大多數時候這件事是非常困難的，因此基於一些統計學觀點上的模擬就變得十分重要。蒙地卡羅的核心實際上就是這些模擬的過程，如果這個過程本身具有隨機性，或是能夠被轉換成某種隨機數，我們就可以透過蒙地卡羅來做模擬，進而用這些模擬出的資料去訓練模型。
Integration Approximation 積分近似
最簡單呈現蒙地卡羅的概念應該從圓開始，過去(還沒有出現電腦以前)我們估計圓的方法有很多，比方說把一個圓想像成多個多邊形的組合，分別對這些多邊形計算面積再加總，當然能估計到多麼精確就是另外一回事了。然而，電腦出現以後，我們就有了另外一種想法，假設我今天在給定的區域中，比如一個邊長是圓直徑的正方形中隨機產生一堆數字，我只要計算落在圓內的比例(至於如何知道是在圓內，只要估計該點與圓點的距離是否等於邊長即可)，就可以知道圓面積是多少，也就可以推算出圓周率等等的。我們看維基百科上的示例：
隨著取樣樣本越多，得到的值就越接近真實值。這樣的做法實際上很像我們在做積分很像，一個函數的積分實際上可以想像成求曲線下的面積，如果我們可以在該曲線下取樣無限大的樣本，理論上就可以無限趨近其真實面積；因此，蒙地卡羅實際上是一種很廣泛的稱呼，只要透過大量取樣來逼近某真實狀況的方式，都可以稱作蒙地卡羅。
最簡單的積分估計方式，我們可以任意抓出一個函數與一個正方形，在正方形上面均勻採樣，計算落在要計算曲線內的點個數，就可以估算出積分值，圖解如下：
我們把這種作法稱為簡單的蒙地卡羅積分方法，換算成數學的概念寫成：
pdf 為函數的機率密度函數，當然我們這邊都先以均勻分布為主，也就是 1/(b-a)，而為甚麼可以這樣寫呢? 這邊先看一下直觀上的理解：
到這邊不難理解，均勻取值夠大的時候，會產生出許多 f(Xi)，這些值可以拿來做為面積的計算基礎。而數學上，這是根據機率論中的中央極限定理，我們複習一下，中央極限定理(Central Limit Theorem，CLT)說，只要隨機獨立地取樣夠多的樣本，這些相互獨立的隨機變數會依照分布收斂成常態分布。我們知道，想要求一個函數的積分，實際上是求這個連續分布的期望值，也就是 E[f(x)] = F，換句話說當蒙地卡羅方法在估計一個積分函數時，實際上是將其視為一個均勻隨機變量的期望：
因此，當我們想用程式實現它時，遵照以下步驟 :
這邊我們透過蒙地卡羅積分來估計一下指數分布在閉區間 0~5 的積分值是多少 (為了簡單，本篇程式碼皆使用一維樣本) :
輸出如下，可以看到隨著樣本數增多，估計誤差從3.8%降到了0.6% :
當然，回到公式本身，我們也可以不要以均勻分布作為取樣分布，而是可以自己發揮創意，但通常以簡單起見，均勻分布的模擬還是很常見的。
Variance Reduction 方差縮減
首先我們要先知道甚麼是方差縮減，以及為何它很重要。
當我們針對 E[f(x)] 進行完估計後，我們可以進一步得到其變異數 Var(E[f(x)])。一般情況下，我們除了考慮估計值的無偏性，也需要考慮估計值的變異程度，亦即我們不希望估計出的值平均雖接近真實值，但內部差異過大而導致不穩定，這部分的概念有點類似機器學習中所說的 Bias-Variance Trade off :
一個比較直觀的做法當然是增加樣本量，通常一個蒙地卡羅估計方法中，抽樣一萬個樣本與抽樣一百萬是有天壤之別的，但後者可想而知會增加計算負擔，何況我們也不希望這個方法有如上帝之手，可以演化所有的發展路徑，因此我們希望在一個盡可能小樣本的情況下來減少估計的方差。
這邊介紹兩個主要的方法來進行方差縮減 :
【Antithetic Variable 對偶變量】
先看一個簡單的公式 :
假設我們生成兩次同分布的變量 X1, X2，我們知道當 X1 與 X2 為負相關的時候，樣本共變異數為負數，造成方差的平均會比其互相獨立時要小，因此這邊的思路上，可以想要如何生成負相關的隨機變量來做估計。
透過逆變換法得知，我們可以將一個隨機分布的變量用均勻分布擬合出來 :
又因為我們知道當 U~U(0,1)，可得(1-U)~U(0,1)，且U與1-U負相關，我們可以透過以下的方式來生成兩組負相關的擬合用樣本 :
這兩者為獨立同分布，但此時並不保證 Y 與 Y’ 負相關，因此我們還需要確定 Fx(.)函數是單調 (monotone) 的，因為以下定理 :
數理統計學就談過此定理，這邊不再贅述，因此當 f 為單調， -f 亦為單調，因此可以得出 :
因此我們確定 Y 與 Y’ 負相關，此時即可利用此生成方法來協助抽樣。如果我們需要產生 n 個樣本來做蒙地卡羅估計，我們只需要用以上的方法生成一對負相關的樣本，並重複執行 n/2 次即可。此時，通過這樣的方法得到的樣本方差會比原先來得小。
**由於指數分配的反函數不滿足以上條件，基本上我們沒法在這裡實作這個簡單的分配，但對於某些特定複雜函數，此方法仍然好用。
【Control Variate 控制變量法】
另一種思路是，我們能否通過一些已知量的估計來減少未知量的誤差？首先針對估計量 E[f(x)]，我們引入一個已知期望值的函數 g，即 E[g(x)] = u，且f 與 g 相關 。
我們可以確定兩個算式 :
第一個算式說明結合後的估計量是無偏估計，因此我們可以確保估計出來的參數可靠，第二條算式則是第一條算式的自然結果。而由上述的兩條算式，可以得知要讓估計出來的方差最小，我們必須令 :
此時的最小值就變成 :
此時呢，我們就稱 g(X) 為我們要估計的函數 f(x) 的控制變量。
到這邊算式看上去都滿直觀明瞭的，但這邊有一個重點，我在本段一開始說了，且 f 和 g 相關，這個意思從最後我們得出的最小估計方差來看很明顯，當Cov(f(x), g(x)) 最小，得出的方差就會最小。而這個方法一切的精華就在於，如何找出一個強相關的函數來完成這個算式。
顯而易見，該算法的優勢在於不需計算反函數，因此某些時刻能夠突破對偶變量法帶來的不便，但難點在於強相關函數的選擇有許多，甚至有時會發生找不到強相關函數的窘境，因此使用起來就需要一些創意性。
舉個例子，如果估計 e^U 函數 :
我們可以簡單選擇均勻分布做強相關函數，因此 :
則方差減少量為 :
整體來說，減少比率為98%
Importance Sampling 重要性抽樣
透過一般蒙地卡羅的估計來計算積分有個最大的缺點，當目標函數並不是太過均勻分布的時候，這種方法就會失效，因此，我們可以考慮透過 "加權" 的方式來調整方法，加權的方式當然也是通過其他函數來協助實現的。
首先，我們定義一個 g 函數，稱之為重要函數，因此有 :
換言之，我們就可以將問題透過引入重要函數，轉換成另一個相似的目標，原先的蒙地卡羅估計方法流程就變成了 :
- 從重要函數 g(x) 中採樣樣本 X
- 計算 E[q(x)]，其中 q(x) 稱為我們的權重函數，亦即對採樣過後的樣本 X，進行權重調整
此方法簡潔有力，也能夠跳脫均勻分布的限制，可說是對基本蒙地卡羅近似的一個推廣，唯一缺點就是對高維分布仍沒有太多優勢，主要是因為難以找到參考分布的緣故。
這邊實作一次看看，假設我們要估計一個積分 :
積分計算器顯示的答案是 0.5247971432602705，我們透過重要性採樣來估計看看，誤差會是多少，首先，我們先稍微用圖來看一下，不同提議分配對於積分估計的影響如何 :
我們可以看到在0~1的區間中，紅色與綠色的分布與目標函數是接近一些的，注意這邊不是指積分值上的相似，因此面積的重疊不代表任何意義，而是做為重要性函數所提供的權重調整，必須使得抽樣分布的比例與目標函數在該積分區間的比例近似。基本上對於目標函數的估計，是透過從重要函數中採樣並經過權重調整而得來的，因此重要函數的選擇特別重要，必須同時兼顧亦於採樣，且與目標函數形狀吻合等特點。
在這裡用三種分布來模擬，注意第三種分布的抽樣採用了逆變換；此外為了避免柯西分布取值為正負無限，透過代碼來限制取樣點，因此實際樣本數量會略少，從均勻分布轉換而來，讀者可以自己嘗試推導，補上實作代碼 :
輸出結果如下 :
柯西分布雖然掉了一些樣本點，但不妨礙其表現，整體而言指數分布表現的反而是最差的，這是因為在取樣比例上，對於靠近 1 的部分取樣比例偏高。
我們拿方程三與簡單蒙地卡羅比較看看，也同步比較估計方差是否有減少，這邊將原先一維的估計量拓展成五維來進行比較 :
可以自己嘗試看看，最終的方差縮減了 75% 左右，每次估計的誤差值也低於簡單蒙地卡羅的結果。
Stratified Sampling 分層抽樣
最後這邊的思路就比較簡單，既然簡單蒙地卡羅抽樣會因為目標函數不平均的問題而失效，那麼如果把目標函數分成 k 個均勻的積分段，再次進行蒙地卡羅積分，一切不就解決了嗎? 當然，我們也不希望這麼簡單，為了使估計的方差縮小，我們必須考慮抽樣多次後總和的方差，須小於原先的簡單估計
這邊的思路相對簡單些，就不透過程式碼實作了。
結語
在往下以前，先來順一下到目前為止的思路。首先，抽樣的本質其實與模擬分不開，因此蒙地卡羅或後面將會提到的馬可夫鏈等，實際上都能夠視為實現抽樣的工具之一。當我們能夠去模擬出真實分布的樣本資料，我們就更有信心再其上進行一些研究，退一萬步說，透過好的抽樣也可以強化訓練樣本的品質，並減少機器學習訓練上的成本。
此外，強化學習大量引入了根據環境變化而改變策略這一想法，而針對環境變化如何找出最佳策略這一回事，在傳統的機器學習中已經著墨許多，但如何理解環境將如何變化，做出不同的情境測試(Scenario Test)，這是過去比較少提及的，而抽樣正好可以扮演其中的關鍵角色，透過模擬多種情境並運行相應策略，執行 A/B Testing 以評估策略是否成功，這些都是實際上會應用到的問題，當然，在工業級的問題中目前應用的比較成功，能否在商業級的問題上使用，則有待前輩們的引路前行。
思路目前至此，接下來我們就要往更深一層的概念發展，透過引入條件機率等概念，去理解如何針對未來的情境進行模擬，因此下一篇將會進行到馬可夫網絡與MCMC方法的介紹。
** 憋了三四個月終於又出來一篇，還是趁著長假寫的，只能說工作以後真的不容易，時間被剝得非常零碎，幾乎沒有空暇好好充電，何況以往寫一篇大約投入時間就是一周，現在明顯感受到知識的匱乏(工作後就把知識還給學校)，整理這些知識並想辦法實作花費的時間更多，何況我還水了不知道多少程式碼(看看之前的投影梯度下降就知道)。只能說勉勵自己不要被職場給沖走，希望能與各位資料科學的愛好者繼續共同前行！
