蒙特卡洛梯度估計方法(MCGE)簡述

動機機器學習中最常見的優化算法是基於梯度的優化方法，當目標函數是一個類似如下結構的隨機函數 F(θ) 時：

優化該類目標函數，最核心的計算問題是對隨機函數 F(θ) 的梯度進行估計，即：

隨機函數梯度估計在機器學習以及諸多領域都是核心計算問題，比如：變分推斷，一種常見的近似貝葉斯推斷方法；強化學習中的策略梯度算法；實驗設計中的貝葉斯優化和主動學習方法等。其中，對於函數期望類目標問題，最常見的是基於蒙特卡洛採樣的方法。

背景知識要了解基於蒙特卡洛採樣的梯度估計方法，首先先了解蒙特卡洛採樣方法和隨機優化方法。

MCS 是一種經典的求解積分方法，公式（1）中的問題通常可以用 MCS 近似求解如下：

其中， 採樣自分布 p(x;θ)，由於採樣的不確定性和有限性，這裡  是一個隨機變量，公式（3）是公式（1）的蒙特卡洛估計器（MCE）。這類方法非常適用於求解形式如公式（1）的積分問題，尤其是當分布 p(x;θ) 非常容易進行採樣的時候。

1. 一致性，根據大數定理，當所採樣的樣本數量非常多時，MCE 的估計值將會收斂到積分的真值處。2. 無偏性，MCE 是對所求積分的一個無偏估計，簡單推導如下：

3. 小方差，當幾個估計方法都是無偏估計時，我們通常會選擇方差較小的 MCE，因為更小方差的 MCE 會估計地更準，從而使得優化地效率更高、準確性更好。

4. 可計算性，很多機器學習問題都是高維問題，如何提高 MCE 的可計算性，比如：減少採樣、提高並行能力等變得十分重要。如圖 1 所示，隨機優化問題通常包含兩個過程，一是仿真過程，輸入優化變量，獲得響應值 F(θ)，然後計算出，其中是個隨機變量 ；二是優化過程，基於梯度，迭代更新優化變量。不同於確定性優化，隨機優化算法包含兩個部分的隨機性：應用基於蒙特卡洛採樣的梯度估計方法（MCGE）在很多研究領域都起到了核心作用，本節總結一下其在機器學習領域中的典型應用。

變分推斷（Variational Inference, VI）

VI 是貝葉斯推斷中的一大類方法，在統計機器學習（貝葉斯視角）中具有廣泛的應用。從上圖中可以看出，變分推斷 (VI) 的思想非常簡單。假設一個變分分布簇，在概率空間中找到一個離真實分布最近的分布。VI 巧妙地將一個推斷問題轉化為了優化問題，優化目標是 KL(Q||P)，即待求分布 Q 和真實後驗分布 P 的距離，優化的變量是分布 Q 的描述參數。

VI 方法綜述將在另外一篇文章中詳細介紹，本文只簡單說明其目標函數是一個形如公式（1）的問題。考慮一個生成模型問題 p(z)p(x|z)，其中 z 是隱變量，x 是觀測變量，p(z) 是先驗分布，p(x|z) 是似然函數。根據貝葉斯公式：

其中 p(x)=ʃp(z)p(z|x)，稱為 evidence，通常 p(x) 是一個不可積的多重積分，導致後驗分布 p(z|x) 無法獲得解析解。如上述思路所述，假設後驗分布用一個變分分布 q(z|x;θ) 來近似，通過構造如下優化問題：

來求解使得兩個分布距離最小的變分分布參數 θ，從而得到近似後驗分布。

因為真實後驗分布是未知的，直接優化公式（6）是一件比較有挑戰的事情，VI 巧妙地將其轉化為優化 ELBO 的問題。

由 KL 散度的定義可知，KL(q(z|x;ф)||p(z|x;θ))≥0，同時 logp(x;θ) 是個常數，所以求優化問題（6）等價於求如下優化問題：

相當於求解 log evidence lower bound，即 eblo。繼續推導如下：

公式（10）的形式如公式（1），可以用 MCGE 進行梯度估計，從而優化求解。

變分推斷方法是一個熱門研究領域，而核心問題是如何高效求解 elbo 優化問題，在統計物理、資訊理論、貝葉斯推斷、機器學習等諸多領域由廣泛的應用。

強化學習是機器學習中一大類熱門研究領域，尤其是 AlphaGo 的橫空出世，為強化學習帶來了更多的關注和更多的研究人員。本文將不對強化學習的任務和各種概念進行贅述，強化學習中的一大類問題是無模型的策略搜索問題，即通過優化累計回報的均值學習到最優策略。所謂累計回報的均值形式如下：

公式（11）形式亦如公式（1），可以用 MCGE 進行梯度估計，從而優化求解。實驗設計是個非常廣泛的領域，主要是研究如何為實驗設置合適的配置，比如：自動機器學習中的超參數調優（HPO）、神經架構搜索（NAS），通過主動學習（Active Learning）選擇更加合適的樣本進行標註，老虎機問題的求解（Bandit）等等。

這類任務中經常會遇到一個問題，如何選擇下一個更好的配置，使得選擇之後比選擇之前性能的概率會有所提升。因此需要優化如下問題：

公式（12）形式亦如公式（1），可以用 MCGE 進行梯度估計，從而優化求解。

簡單總結一下，優化是機器學習訓練中最重要的部分，而其中很多優化問題都是形如公式（1）的問題，而 MCGE 是解決這類問題的有效手段，接下來介紹兩種經典的 MCGE 方法。

方法綜述公式（1）中的積分內是一個分布和代價函數的乘積，在對其梯度進行近似估計時，可以從兩個方面進行求導。由此，可以將梯度估計方法大致分為兩類：

根據公式（2）待估計的梯度是，直接計算會非常困難，一個直觀的思路是研究如何將期望的梯度轉化為梯度的期望，從而可以利用 MCS 做無偏近似估計。本文將會介紹兩種經典的方法，來解決這個問題。

Score Function Gradient Estimator (SFGE)

SFGE 是最經典的方法，也是適用性最好的方法，在強化學習中的策略梯度優化問題裡，有一個算法叫做 REINFORCE，正是基於 SFGE 來做的。SFGE 也常常被用於解決目標函數不可導的優化問題以及一些黑盒優化問題。

所謂的 score function 是，之所以選擇這個函數，是因為以下兩點原因：

1. score function 的期望為 0，證明如下：

這樣會帶來非常多的便利，比如：一種降低估計方差的思路，將代價函數 f(x) 改造為 f(x)-b，其中 b 是所謂的 baseline。因為 score function 的期望為 0，所以：

2. score function 的方差是 Fisher 信息量。

其中，。

從上述推導中可以看到，通過引入 score function，可以成功地將期望的梯度變換為梯度的期望，從而實現梯度的近似估計。

這中間有一個過程是將積分和微分操作的位置進行了對換，此操作並非可以隨意進行，需要滿足一定的條件，但一般的機器學習問題都會滿足。

代價函數 f(x) 可以是任意函數。比如可微的，不可微的；離散的，連續的；白箱的，黑箱的等。這個性質是其最大的優點，使得很多不可微的甚至沒有具體函數的黑箱優化問題都可以利用梯度優化求解。

分布函數 p(x;θ) 必須對 θ 是可微的，從公式中也看得出來。

分布函數必須是便於採樣的，因為梯度估計都是基於 MC 的，所以希望分布函數便於採樣。

SFGE 的方差受很多因素影響，包括輸入的維度和代價函數。

SFGE 由於其對代價函數沒有限制，具有非常廣闊的應用場景，以下是幾個非常熱門的應用：

策略梯度優化算法 REINFORCE 及其變種

基於 GAN 的自然語言生成

基於自動微分的黑盒變分推斷

Pathwise Gradient Estimator (PGE)

不同於 SFGE 對代價函數沒有任何約束，PGE 要求代價函數可微，雖然 SFGE 更具一般性，但 PGE 會有更好的性質。PGE在機器學習領域有一個重要的方法是 reparameterization trick，它是著名的深度生成模型 VAE 中一個重要的步驟。

PGE 的思路是將待學習的參數從分布中變換到代價函數中，核心是做分布變換（即所謂的 reparameterization ，重參數化），計算原來分布下的期望梯度時，由於變換後的分布不包含求導參數，可將求導和積分操作進行對換，從而基於 MC 對梯度進行估計。

如上述公式，從一個含參 θ 分布中採樣，等同於從一個簡單無參分布中採樣，然後進行函數變換，並且此函數的參數也是 θ。變換前，採樣是直接從所給分布中進行，而採用重參數化技巧後，採樣是間接地從一個簡單分布進行，然後再映射回去，這個映射是一個確定性的映射。其中，映射有很多中思路，比如：逆函數、極變換等方法。

PGE 的一個重要理論依據是 Law of the Unconscious Statistician (LOTUS) ，即：

從定理中可以看到，計算一個函數的期望，可以不知道其分布，只需要知道一個簡單分布，以及從簡單分布到當前分布的映射關係即可。

基於 Law of the Unconscious Statistician (LOTUS) 對 PGE 進行推導，如下：

其中 。從推導中可以看出，分布中的參數被 push 到了代價函數中，從而可以將求導和積分操作進行對換。分布變換是統計學中一個基本的操作，在計算機中實際產生各種常見分布的隨機數時，都是基於均勻分布的變換來完成的。有一些常見的分布變換可參見下表：

總結蒙特卡洛採樣（MCS）是求解函數期望的常用近似方法，優點是簡單易用，通過一定的變換，可以對期望的梯度進行估計，從而完成對代價函數的優化，實現很多任務。但 MCS 的缺點也非常明顯，為了保證一定的估計效果，往往需要很大量的採樣規模，對於大數據、高維度等實際問題來說，過多的採樣會導致算法效率極低，從而降低了算法的實用性。從這個角度來說，如何研究一些新方法，來提高期望或者期望梯度的近似估計效率是一個非常重要的問題。最後，推薦兩篇 2019 年的工作 [4] [5]，旨在嘗試解決這個問題。 上述研究雖然有一定的局限性，但嘗試了新的思路來解決這一問題。其中第 [5] 篇，嘗試用一些 Uncertainty Qualification (UQ) 的方法，比如用一些不確定性傳播的估計方法，對期望進行確定性估 計，而非隨機採樣估計，在一定的假設下，確實有非常顯著的效果。

參考文獻

[1] Mohamed, S., Rosca, M., Figurnov, M., & Mnih, A. (2019). Monte Carlo Gradient Estimation in Machine Learning. ArXiv Preprint ArXiv:1906.10652. 

[2] Fu, M. C. (2005). Stochastic Gradient Estimation, 105–147. 

[3] Shakir's Machine Learning Blog http://blog.shakirm.com 

[4] Postels, J., Ferroni, F., Coskun, H., Navab, N., & Tombari, F. (2019). Sampling-free Epistemic Uncertainty Estimation Using Approximated Variance Propagation. ArXiv Preprint ArXiv:1908.00598. 

[5] Wu, A., Nowozin, S., Meeds, T., Turner, R. E., Lobato, J. M. H., & Gaunt, A. (2019). Deterministic Variational Inference for Robust Bayesian Neural Networks. In ICLR 2019 : 7th International Conference on Learning Representations.