算法速学速用大辞典 pdf_随机梯度蒙特卡洛算法-重要性采样
大家好，借知乎宣傳一篇NeurIPS 2020文章。為了少占用大家時(shí)間，我會用通俗的動圖描述算法，拋磚引玉。文章的理論性質(zhì)和潛力值得讓數(shù)學(xué)大神加以改進(jìn)并被計(jì)算機(jī)大牛發(fā)揚(yáng)光大。
A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions?arxiv.org話不多說，先放一個(gè)模擬圖，一個(gè)分布有9個(gè)mode，中間一個(gè)概率最大，邊上次之，角上四個(gè)最小。如果你能準(zhǔn)確采樣分布，你就能獲得正確的預(yù)測分布。這在避免第二類統(tǒng)計(jì)錯(cuò)誤（把不對的歸為是對的）和增強(qiáng)學(xué)習(xí)中有巨大前景。深度學(xué)習(xí)中一個(gè)標(biāo)準(zhǔn)的采樣算法是隨機(jī)梯度朗之萬動力學(xué)（SGLD），如圖所示，粒子會在坑中逗留很久，坑越深，逗留時(shí)間指數(shù)變長。也就是說，采樣這個(gè)分布是極其慢的。
有研究者嘗試過一個(gè)簡單實(shí)用的idea，即采用周期性cosine學(xué)習(xí)率獲得不錯(cuò)的實(shí)驗(yàn)表現(xiàn)。大學(xué)習(xí)率explore新區(qū)域，小學(xué)習(xí)率獲得局部采樣。圖下可見，效果比SGLD提升了不少。
Zhang - ICLR 2020當(dāng)然， @Zhanxing Zhu 老師的變溫tempering算法，對non-convex問題也很有潛力。對于preconditioned SGLD @Chunyuan Li，它對Hessian條件數(shù)糟糕的情況做了很好的改進(jìn)。
更著名的算法是經(jīng)典的并行回火(Parallel tempering/ replica exchange)算法。思想是引入兩個(gè)（或多個(gè)）隨機(jī)過程，高溫過程探索全局(exploration)，低溫過程采樣(exploitation)。當(dāng)高溫過程能量（loss）值比低溫過程沒差很多時(shí)，參數(shù)有一定概率去互換（swap）。利用跳躍（jump）的方式解決爬坡難的問題。
由于逃脫local trap需要的代價(jià)是指數(shù)級別（和深度有關(guān)），因此這個(gè)算法用較小代價(jià)獲得了指數(shù)加速。此算法如此流行且重要甚至都出現(xiàn)在阿里數(shù)學(xué)競賽試題里（忘了哪一版了）。
Deng, ICML 2020直觀想象，如何跨越能量壁壘是加速采樣的重中之中。而現(xiàn)實(shí)下，魚和熊掌不可得兼，exploration and exploitation常常只能取舍。多個(gè)過程/引入跳躍無疑會很好的克服這一問題。但如果只用一個(gè)過程不帶跳如何達(dá)到理論上最大的潛能呢？傳統(tǒng)MCMC領(lǐng)域公認(rèn)的一個(gè)答案是：重要性采樣（importance sampling）：
即如果 分布很難采樣，但 分布容易的多，同時(shí)你還能獲得分布之間的關(guān)系 （Radon nikodym導(dǎo)數(shù)，importance weight）。那么你可以通過間接采樣來大大加速 的模擬。
什么樣的
分布比分布容易采樣呢？Neal在Annealed Importance Sampling提出用高溫的思路將分布變平。 這篇文章采用的則是統(tǒng)計(jì)物理里面的multicanonical ensemble和Wang-Landau里面的思路，將原分布（下圖綠線）除以目標(biāo)分布的能量pdf（也將作為importance weight）來將分布變平（下圖紅線）。從而降低能量壁壘。該思想已經(jīng)在統(tǒng)計(jì)物理和生物信息學(xué)領(lǐng)域獲得極大成功，被王永雄、劉軍教授（兩位COPSS獎(jiǎng)：統(tǒng)計(jì)菲獎(jiǎng)，一年一人，coadvisor的老板和師兄）評價(jià)為最適合加速蒙特卡洛的算法。
盡管目標(biāo)分布的能量pdf剛開始不知道，但獲得能量pdf比獲得分布信息要容易的多（比如一個(gè)Gaussian mixture with equal weight, 估計(jì)單個(gè)mode的能量pdf很容易，而這個(gè)信息已經(jīng)足夠；進(jìn)一步的話，不equall weight也不是啥問題）。我們可以用stochastic approximation（可以想象成EM算法的進(jìn)階版）一邊采樣一邊優(yōu)化隱變量。均衡情況下，隱變量收斂到能量pdf，目標(biāo)參數(shù)弱收斂到更容易采樣的
分布。神奇的是，此算法擁有簡潔的形式（比原算法只多了下面一行迭代，相比之下Adam需要額外5層迭代）和極佳的穩(wěn)定性，隱變量可以收斂到唯一fixed point而無關(guān)凸性（EM算法常見問題就是隱變量local trap且極其不穩(wěn)定）。該算法和擬牛頓算法有一絲相似。但擬牛頓不改進(jìn)能量函數(shù)只是估計(jì)Hessian，因此只能獲得漸進(jìn)超線性的表現(xiàn)；而我們的算法步步改變幾何形狀的做法，潛在的指數(shù)加速了收斂（為啥指數(shù)階的話，由于分析很難，我還是引一篇reference吧）。
下面是路徑展示：此算法引入一個(gè)隱變量，這個(gè)隱變量代表分布的能量pdf，原始分布除以這個(gè)隱變量可以獲得更平的分布因而更容易模擬，你能看出高能區(qū)似乎也有很多樣本，由于他們對應(yīng)的importance weight很小，因此結(jié)合importance weight
還是可以恢復(fù)原始分布。能量pdf剛開始未知，但是一些初步的學(xué)習(xí)后便可以獲得巨大的加速效果。Deng - NeurIPS 2020這份工作是統(tǒng)計(jì)物理里面Wang-Landau算法從Metropolis kernel 到Langevin kenel的拓展，為一類重要的加速技巧adaptive biasing force做了鋪墊。為了能應(yīng)用在深度學(xué)習(xí)領(lǐng)域，我們順便把隨機(jī)梯度的版本也一并做了出來。simulation比肩甚至可能超越parallel temerping的性能證明了其巨大的潛能。
此文章最大的novelty在于methodology development。如果你看到simulation的潛能不覺得新奇就可以無視后續(xù)了。本篇文章更側(cè)重講方法論，因而只提供了一些簡單的DNN實(shí)驗(yàn)，實(shí)驗(yàn)中高loss下，能量PDF的估計(jì)會變得困難，比如
。折中去大幅提升實(shí)驗(yàn)性能的辦法有很多，就不在這篇文章探討了。應(yīng)用的工作留給更專業(yè)的同學(xué)進(jìn)行了。改變幾何形狀帶來的理論增益遠(yuǎn)超Hessian估計(jì)，動量，或者高階數(shù)值離散格式。比如深度學(xué)習(xí)中的基石算法SGD with decaying learing rate其本質(zhì)就是模擬退火，通過步步改變幾何形狀使得概率mass聚集在global minima附近，相比之下所謂ADAM/ RMSprop這類算法在大問題下基本就不work了。當(dāng)然，這么大的收益也也需要更高階的數(shù)學(xué)技巧來分析，大量PDE和黎曼幾何是免不了了。既有挑戰(zhàn)性，也有無限潛力。呼喚真
數(shù)學(xué)大神關(guān)注此問題。用learning rate decay來實(shí)現(xiàn)模擬退火已經(jīng)是業(yè)界公認(rèn)最實(shí)用的技巧之一，而與它一樣強(qiáng)大的parallel tempering在DNN領(lǐng)域如何高效的實(shí)驗(yàn)和調(diào)參還完全是一片空白。希望工程背景強(qiáng)大的同學(xué)也關(guān)注一波。
1. Max Welling, Yee Whye Teh. Bayesian Learning via Stochastic Gradient Langevin Dynamics. ICML'11
2. R. Zhang, C. Li, J. Zhang, C. Chen, A. Wilson. Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning. ICLR'20
3. W. Deng, Q. Feng, L. Gao, F. Liang, G. Lin. Non-convex Learning via Replica Exchange Stochastic Gradient MCMC. ICML'20.
4. W. Deng, G. Lin, F. Liang. A Contour Stochastic Gradient Langevin Dynamics Algorithm for Simulations of Multi-modal Distributions. NeurIPS'20.
=========
Nov. 6補(bǔ)充： 英文blog見Dynamic Importance Sampling
總結(jié)
以上是生活随笔為你收集整理的算法速学速用大辞典 pdf_随机梯度蒙特卡洛算法-重要性采样的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
