繼續《深度學習》花書總結，本章主要介紹採樣的蒙特卡洛方法，準備結合斯坦福CS 228 - Probabilistic Graphical Models課程相關內容一起總結。

首先，我們為什麼需要採樣（sampling)呢？因為我們通常要進行許多求和或者積分的近似計算，精確求值很困難，所以要進行採樣來減小計算花費，比如前一章（結構化概率模型——深度學習第十六章）介紹的配分函數就涉及到積分運算，就需要進行近似計算。

假設我們數據的概率分佈是 ，我們要求在這一分佈上函數 的期望，即 ，蒙特卡洛方法即是通過從 中採樣n個樣本 ，並用經驗平均值(empirical average)來近似s，即 。Fun fact: 蒙特卡洛(Monte Carlo)名字來源於位於摩納哥的蒙特卡洛賭場，就是下圖中這個酒店，最初由美國曼哈頓計劃中的物理學家們當做一種祕密代號。

為什麼我們可以採用經驗平均值來近似真實的期望呢？一是 是無偏估計(unbiased estimation)，即 ，且根據大數定理，如果樣本 是獨立同分布，則 ，另一方面， 的方差與採樣量n是成反比的，當採樣量足夠多時，我們可以很好的近似真實期望。

觀察求和形式 我們可以發現如何選取 和 並不是唯一的，即我們總可以將其分解為 的形式而不改變求和結果，我們可以將 當做新的 而 當做新的 。因此，我們可以從分佈 中取樣，並利用 求 的期望，這一方法被稱作重要採樣importance sampling。那麼我們什麼時候需要importance sampling而不是直接從 中取樣呢？有時是因為相較於 ， 更方便採樣，或者 可使預測的方差更小。通過importance sampling的式子我們可以得到， ，即 也是無偏估計，並且當 ，其中 是使 歸一的常數， ，即當分佈q取為 時，我們僅需要從中採樣一個樣本就可計算真實期望。當然，最優的 需要計算原求和，我們又回到最初的問題，實際上無法採用，不過這有助於理解選取合適的 可以有效的減小方差。

前一章我們提到對於有向圖可以用ancestral sampling的方法採樣，而對於無向圖由於沒法進行拓撲排序不能用ancestral sampling，解決方法之一是利用馬爾可夫鏈蒙特卡羅方法(Markov Chain Monte Carlo， 簡稱MCMC)。

Markov Chain的核心思想是我們最初可以隨機的選取初始狀態，再不斷的更新這一狀態，最終使其分佈近似於真實分佈 。假設Markov Chain可以由一序列狀態 來表示，其中 ，代表系統可取的各種狀態。初始狀態滿足 分佈，而之後的分佈是依賴於前一時間點的條件概率分佈，即 。Markov假設對於每一步i， 是相同的，即當前狀態僅依賴於前一時刻狀態，而不依賴於其他歷史狀態。我們可以用轉移矩陣來表示這一概率 ，假設初始的 分佈為 ，則經過t步採樣後，概率分佈為 ，其極限 被稱作平穩分佈(stationary distribution)，在進入平穩分佈後，後續的每一步 ，即進入穩態分佈後，隨著更多的採樣的進行，分佈並不會再進行改變。那麼，在什麼條件下，存在穩態分佈呢？以下兩條構成充分條件:

1.不可約性(Irreducibility)，在有限步驟中，可以從任一狀態S到達另一狀態S。這一條件保證不存在我們無法離開的黑洞狀態。

2.非週期性(Aperiodicity)，任意時刻可以返回任意狀態，即對於 ， 。這一條件保證我們不存在這樣的轉移矩陣 ，即在兩個狀態間來回變動而不能達到平穩分佈。

為了滿足以上條件，通常在利用MCMC方法時，我們採取基於能量的模型 。

假設我們有了轉移矩陣為T且平穩分佈為p的Markov Chain，我們怎麼進行MCMC取樣呢？

假設初始狀態為 ，則我們先進行B次步進，使Markov Chain達到穩態，這一過程稱為burn in，這一過程所需的時間稱為混合時間mixing time。達到穩態後，我們再進行若干次Markov Chain採樣，並利用這些樣本來近似估計期望。當然實際應用中，達到穩態後，連續兩次取樣間還是強相關的，所以通常是採取每n次連續markov chain操作後取一個樣本。為了使取樣是相互獨立的，我們也可以同時進行多個Markov Chain取樣。

那麼如何選取合適的轉移操作使平穩分佈接近真實分佈p呢？一種方法是吉布斯採樣(Gibbs Sampling)，即對於每一個變數，從依賴於圖中其鄰居節點的條件概率分佈p中採樣，對於相互條件獨立的變數，我們也可以同時進行Gibbs Sampling。以如下所示的簡單的無向圖作為例子。

• 隨機初始化a,s,b。
• 將下述步驟重複n次：
• 從P(a|s)中採樣a，從P(b|s)中採樣b，由於a,b在s給定的條件下是條件獨立的，所以a,b的採樣可以同時進行。
• 從P(s|a,b)中採樣s。

Gibbs Sampling是Metropolis-Hastings採樣演算法的一種特殊形式，關於這一類採樣方法為什麼會收斂於真實分佈p可參見斯坦福cs228講義Sampling methods中的推導。

利用MCMC方法的難點是如何判斷我們已經達到穩態了，暫時還沒有明確的理論指導markov chain是否到達穩態，何時能到達穩態，所以需要一些直觀判斷方法如人為的檢驗樣本或觀察連續採樣間的關聯。

另一個難點是混合時間過長，尤其是對於維數較多，變數間關聯較強或者有若干峯值的概率分佈，其混合時間很長。對於有若干峯值的情況，我們可以通過引入一個反比於溫度（來源於統計物理概念）的參數 來改變基於能量的模型的分佈 ，當 時，我們可以有效地混合不同峯值的分佈。

總結一下，這一章主要介紹了用於近似某些求和或積分運算的蒙特卡洛採樣方法如無向圖中的Gibbs Sampling方法，下一章我們會看到如何將這些方法應用到配分函數的計算中, to be continued。

註：截圖均來自Ian Goodfellow等合著的Deep Learning一書，推薦閱讀原書。

推薦閱讀：

相關文章