選自BAIR
參與：路雪、蔣思源
近日伯克利大學官方博客發文提出小批量MH（Minibatch Metropolis-Hastings），即一種進行MH 測試的新方法，該方法根據數據集規模將MH 測試的成本從O(N) 減少到O(1)，它不僅對全局統計量沒有要求，同時還不需要使用末端限定。伯克利大學使用新型修正分佈直接將有噪聲的小批估計量轉換為平滑的 MH 測試分佈。
我們在過去幾年中經歷了一次大型數據洪流，它對人工智能的興起起到了重要作用。下面列出部分大型數據集：
ImageNet：1400 萬張圖像，可用於分類和物體檢測。
Movielens：兩千萬用戶對電影的評級，可用於協同過濾（collaborative filtering）。
Udacity 車輛數據集：至少 223 GB，可用於自動駕駛汽車的訓練。
Yahoo 數據集：13.5 TB 用戶-新聞交互（user-news interaction）數據集，可用於研究人類行為。
隨機梯度下降（SGD）推動了基於這些數據集進行大型模型開發的進程。 SGD 非常適合大型數據集：它僅需要使用一個固定的 minibatch 大小，就可以在整個數據集上估計損失函數的梯度值，每次遍歷數據集，都能實現對模型的更新。
但是 SGD 也存在局限性。我們在構建模型時，使用數據集 x 和模型參數 θ構建損失函數 L_θ(x)，並嘗試對參數θ執行梯度下降而極小化損失函數。這一便捷方法使優化變得容易，但是也容易產生多種問題，如過擬合（over-fitting）、過分敏感的係數值，以及可能較慢的收斂速度。一個更魯棒的方法是將θ 上的推斷問題看作充分的後驗推斷（posterior inference），從損失函數中推斷出聯合分佈p(x,θ)，然後計算後驗概率p(θ|x )。這是貝葉斯建模方法，具體來說，當應用到深度模型上時，這就是貝葉斯神經網絡方法。 Zoubin Ghahramani 近期公佈的教程討論了該方法的優點。
模型的後驗概率 p(θ|x) 對於大多數問題都是很難處理的（非封閉式）。機器學習領域有兩種方法可以解決難處理後驗：變分貝葉斯方法（Variational Bayesian）和馬爾可夫蒙特卡羅（MCMC）方法。在變分方法中，該後驗逼近於一個更簡單的分佈（如正態分佈），並且最小化其與真正後驗之間的距離。在 MCMC 方法中，該後驗被近似為一個相關樣本序列（點或粒子密度）。變分貝葉斯方法已經得到廣泛應用，但也常常引起顯著的誤差。詳見論文《Online but Accurate Inference for Latent Variable Models with Local Gibbs Sampling》 和 《Auto-Encoding Variational Bayes》。變分貝葉斯方法比直接對參數執行 SGD 的計算成本高，雖然只是一個小的常數因子，但該常數乘 1-10 天就變的很重要了。
MCMC 方法沒有這樣的偏差。你可以將 MCMC 粒子想像成量子力學中的粒子：你只能觀察到個體實例，並且它們遵循一種任意複雜度（arbitrarily-complex）的聯合分佈。你可以通過多個樣本推斷出有用的統計數據、應用正則項等。但是MCMC 方法在大數據集上有一個最主要的問題：除了遵循吉布斯採樣（Gibbs sampling）的共軛模型中的一個重要類別以外，並沒有其他有效方式能在小批量數據上進行一般MCMC方法所要求的Metropolis-Hastings 測試（稍後我們將定義／複習MH 測試）。因此研究者必須設計模型使推斷變得易於處理，如受限玻爾茲曼機（RBM）使用一種分層式、無向的設計以使用吉布斯採樣。近期的一個突破是，變分自編碼器（VAE）使用變分方法使概率性自編碼器（probabilistic auto-encoders）可以支持更通用的後驗分佈。但是，具備 VAE 的變分模型和其他變分模型一樣，必鬚麵對一個現實，即該模型是一個最優近似（best-fit approximation），（通常）沒有對近似程度進行量化。儘管 MCMC 方法通常能提供更好的精度，但是由於缺乏高效、可擴展的 MH 測試，導致該方法近期在自編碼器應用中被邊緣化。
近期關於隨機梯度朗格文動力學（SGLD）和隨機梯度漢密爾頓蒙特卡羅（SGHMC）的論文（《Bayesian Learning via Stochastic Gradient Langevin Dynamics》和《Stochastic Gradient Hamiltonian Monte Carlo》）鍛造了SGD 和貝葉斯建模之間的橋樑。這些方法包括對典型 SGD 更新的少許優化，即從近似於貝葉斯模型後驗 p(θ|x) 的概率分佈中生成樣本。這些方法將 SGD 轉換成 MCMC 方法，但是這種轉換要求進行 MH 測試以獲取準確結果，這也是這篇博客的主題。
由於這些發展，近期關於可擴展性 MCMC，尤其是一般 MCMC 模型所要求的在大數據集上進行的 MH 測試的相關研究興趣正在升溫。通常情況下，MH 測試需要掃描整個數據集，每需要一個數據樣本的時候都需要應用該測試。對大數據集來說，這是很難做到的。 Korattikara et al. 和 Bardenet et al. 的兩篇 ICML 2014 論文（Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget 和 Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach）試圖降低 MH 測試的成本。他們都使用 concentration bound，且都獲得了和完整數據集掃描相關的常數因子改進。其他相關工作改善了性能，但是模型的假設太強而限制了它的應用，尤其是對深度網絡。這些方法都比不上 SGD 的性能，即從固定規模的小批數據中生成後驗樣本。
在本文中，我們描述了進行MH 測試的新方法，該方法根據數據集規模將MH 測試的成本從O(N) 減少到O(1)，並且沒有對全局統計量的需求、不使用末端限定（將導致測試所需數據呈長尾分佈）。我們使用新型修正分佈（correction distribution）直接將有噪聲的小批估計量「變成」平滑的 MH 測試分佈。我們的方法是真正的「黑箱」法，因為它僅使用一個較小的期望批量大小為每一個 MH 測試提供精確的估計。這種方法甚至可應用到無限數據流中。
它在現有的 SGD 上可以實現「piggy-backed」，以通過 SGLD 或 SGHMC 提供完整的後驗樣本，其成本幾乎與 SGD 樣本一樣。因此，現在使用和 SGD 優化相同的成本來實現完整的貝葉斯神經網絡建模是可能的。我們的方法還有可能替代變分方法和 VAE，以更低的成本提供無偏後驗樣本。
為了解釋該方法，我們來看一下 MH 測試在 MCMC 模型中的作用。
馬爾可夫鏈蒙特卡羅方法回顧
馬爾可夫鏈
MCMC 方法旨在從難以計算的目標分佈中抽取樣本。它們使用馬爾可夫鏈生成樣本，馬爾可夫鏈包含代表狀態的結點和狀態之間轉換的概率分佈。
一個關鍵概念是馬爾可夫假設（Markovian assumption），該假設表明在時間 t+1 處於某個狀態的概率完全可以通過目前時間為 t 的狀態推斷出來。在數學上，θ_t 代表馬爾可夫鏈在時間為 t 時的狀態，我們可以推斷出 p(θ_t+1|θ_t,…,θ_0)=p(θ_t+1|θ_t)。通過使用這些概率分佈，我們能夠對較大時間步 T 生成一個樣本鏈
。
由於處於狀態 θ_t+1 的概率直接依賴於 θ_t，因此二者的樣本也是相互關聯的。令人驚訝的是，在適當的假設條件下，通過很多樣本的限制，馬爾可夫鏈的樣本分佈近似於目標分佈。
Metropolis-Hastings
最通用和強大的 MCMC 方法是 Metropolis-Hastings。它使用一個測試來過濾樣本。為了準確定義它，我們令 p(θ) 代表我們想要逼近的目標分佈。一般而言，從該分佈中直接抽取樣本比較困難。 Metropolis-Hastings 使用一種更簡單的提議分佈（proposal distribution）q(θ′|θ) 來生成樣本。這裡，θ 代錶鍊表當前的樣本，θ′ 代表提議的樣本。對於簡單情況，通常使用以 θ 為均值的高斯提議（Gaussian proposal）。
如果我們僅使用高斯提議來生成樣本，那麼我們就無法逼近目標 p，因為這些樣本會形成隨機遊走（random walk）。 MH 測試通過使用以下測試過濾樣本，聰明地解決了這一問題。設定一個統一的隨機變量 u∈[0,1]，並確定以下公式是否為真：
如果該公式為真，則我們接受 θ′。反之，我們拒絕並重新使用舊的樣本 θ。注意：
不需要歸一化常數（獨立於 θ 和 θ′）的知識，因為它在 p(θ′)/p(θ) 係數中可以相互抵消。這一屬性十分有用，因為歸一化常數可以說是令分佈變得難以處理的最大原因。
p(θ′) 的值越高，接受的概率越大。
為使該測試的工作原理更加直觀，我們可以查看下圖，其展示了樣本逼近目標後驗概率的過程。該實例來自 Max 和 Teh 2011 年的論文《Bayesian Learning via Stochastic Gradient Langevin Dynamics》。
MH 在高斯樣本上的行為示例。參數是 θ∈R^2，其中 x 軸、y 軸分別代表 θ_1 和 θ_2。目標後驗的輪廓顯示在第四幅圖中；概率質量集中在點 (0,1) 和 (1,-1) 間的對角線上（該後驗依賴於高斯抽樣）。上面四幅圖展示了在 MCMC 鏈中 50 個樣本、500 個樣本、5000 個樣本後的 MH 測試累進。在 5000 個樣本之後，我們可以很清楚地看到樣本集中於後驗概率更高的區域。
減少 Metropolis-Hastings 數據使用
當我們將貝葉斯後驗推斷和大數據集放在一起會發生什麼？ （或許我們會對上圖中的樣本感興趣，除了該後驗以更多的數據點為基礎。）然後，我們的目標就是使樣本近似於大數據集N 上的分佈p(θ|x_1, …,x_N)。根據貝葉斯法則，p_0(θ)p(x_1,…,x_N|θ)/p(x_1,…,x_N)，其中 p_0 為先驗概率。我們還假設 x_i 與給定的θ是條件獨立的。因此 MH 測試變成：
或者，採用對數和重新排列後（忽視最小運算符，此處它在技術上不是必需的），我們得到：
現在問題很明顯了：計算所有的 p(x_i|θ′) 項成本高昂，而由於它依賴於θ′，我們每次抽樣時必須計算所有的 p(x_i|θ′) 項。
最樸素的解決辦法是應用同樣的測試，但是使用小批量 b 元素：
不幸地是，這種方法無法從恰當的目標分佈中抽樣，詳見論文《On Markov chain Monte Carlo methods for tall data》（Bardenet et al. (2017)）第 6.1 節。
更好的策略初始可令批量等於的 b 個樣本點，然後估算批測試與使用全部數據相比的置信度。如果遍歷 b 個數據點，並且已經發現我們提出的樣本θ′遠遠不如當前的樣本θ，我們會立刻拒絕該樣本。如果θ′顯著地表現更好，我們就應該接受。如果結果比較模糊，我們就需要擴大測試批量的規模，例如擴展到 2b 個元素，然後再評估測試的可信度。隨後再清洗數據並不斷重複該過程。之前，Korattikara et al. (2014) 和 Bardenet et al. (2014) 已經提出基於該框架的算法。
上述方法的弱點在於需要重複測試，每次擴大測試批量大小必須減少可容忍的測試誤差。不幸的是，上述方法很可能會使測試批量逐漸增長到全部數據集，它們最多提供常數因子加速全部數據集上測試。
我們的貢獻：小批量 Metropolis-Hastings
改變接受函數（Acceptance Function）
為了設定我們的測試，首先需要定義對數轉換概率 Δ：
該對數比率可分解為預樣本項的和，所以當我們通過在小批量數據上的計算而逼近它的值時，我們就可以得到全部數據值外加一些噪聲的無偏估計量，該逼近過程為基於中心極限定理的漸進正態過程。
應用我們 MH 測試的第一步是使用一個不同的接受函數。正如Δ項所表達的，經典的 MH 測試接受藍線所給出的概率轉換。
函數 f 和 g 作為 Metropolis-Hastings 的接受測試。給定當前樣本θ和提議樣本θ'，豎軸代表接受θ'的概率。
我們並不使用經典測試，而是使用 Sigmoid 函數。使用該函數的合理性可能並不那麼顯而易見，但是我們有一些優雅的理論解釋了為什麼使用這種替代函數作為 MH 的接受測試仍然能使 MCMC 方法語義正確。這些理論表明，在同等程度的假設下，樣本
的分佈接近於目標分佈。
上圖為標準 logistic 隨機變量的分佈密度，X_log 表示沿著等價 MH 測試表達式（X_log+Δ>0）為 Sigmoid 接受函數。
我們現在的接受測試為 Sigmoid 函數。注意 Sigmoid 函數是標準 logistic 隨機變量的累積分佈函數，上圖展示了分佈密度。我們能證明在 Sigmoid 接受函數以下的 MH 測試可以變弱為是否對於一個抽樣的 X_log 值，X_log+Δ>0。
新的 MH 測試
該 Logistic 函數十分優秀，但是我們不希望計算Δ，因為它依賴於所有的 P(x_i| θ′) 項。當我們使用小批量數據估計Δ時，我們就引進了一個額外的誤差，即近似正態誤差 X_normal。如下圖所述，我們研究工作的關鍵成果是使用小批量的分佈來估計Δ（近似高斯分佈）已經非常接近所期望的分佈 X_log。
我們前面得到的 logistic CDF 曲線（紅色）和正態 CDF 曲線（黃色），它們的標準差為 1.7。
我們並不像以前的研究一樣追求末端限定，而是使用一個附加的修正變量 X_correction 直接連接這兩個分佈：
小批量 MH 測試的圖示。我們在右邊有完整的數據測試，但是我們不能使用它，因為Δ是難以處理的。相反，我們有Δ+X_normal（左邊），並且只需要添加一個修正項 X_correction。
我們希望令 LHS 和 RHS 相等，所以我們就添加了修正項 X_correction，該修正項是以 0 為均值的對稱隨機變量（symmetric random variable）。添加獨立的隨機變量將會給出一個分佈為卷積被加數分佈的隨機變量。所以尋找正確的分佈就涉及到 logistic 分佈和正態分佈的「解卷積」。這一過程並不是常常都能進行的，它需要滿足一些條件（例如正態分佈的末端必須弱於 Logistic 分佈），但幸運的是基本上我們都能滿足這些條件。在 UAI 2017 的論文中，我們展示了修正的分佈能通過做表（tabulation）逼近本質的單精度和浮點精度。
在我們的論文中，我們同樣證明了理論上的結果限定了測試誤差的邊界，並且實驗結果表示我們的方法能令高斯混合模型的後驗估計十分精確，同時它在使用Logistic 回歸對MNIST 數字進行分類時有極高的樣本效率。
上方直方圖展示了用於 Metropolis-Hastings 三種基準算法和不同批量大小的關係。其中除了使用 1 百萬數據點生成以外，後驗分佈和前面 Jupyter Notebook 中的案例是相似的。左邊是我們的結果，其他兩個圖分別來自 Korattikara et al. (2014) 和 Bardenet et al. (2014)。我們的算法每一次迭代使用的均值是 172 個數據點。
我們希望我們的測試對於其他在大數據使用 MCMC 方法的研究者有所幫助。我們同樣將該測試的開源實現版併入 UC Berkeley 所開發的 BIDMach 機器學習庫。
測試的開源實現版： https://github.com/BIDData/BIDMach/blob/master/src/main/scala/BIDMach/updaters/MHTest.scala
BIDMach 機器學習庫： https://github.com/BIDData/BIDMach
原文地址： http://bair.berkeley.edu/blog/2017/08/02/minibatch-metropolis-hastings/