隨機加權算法

加權隨機算法是深度學習中的常見算法，一般套用在以下場景：有一個集合S，裡面比如有A,B,C,D這四項。這時我們想隨機從中抽取一項，但是抽取的機率不同，比如我們希望抽到A的機率是50%,抽到B和C的機率是20%,D的機率是10%。一般來說，我們可以給各項附一個權重，抽取的機率正比於這個權重。

基本介紹

• 中文名：隨機加權算法
• 套用領域：深度學習

研究現狀

隨著大數據的逐漸普及，機器學習處理的數據規模也呈現爆炸式增長． 批處理方法是經典的最佳化算法之一，由於每次梯度的計算都要窮舉一次全部樣本，不得不多次遍歷所有樣本，導致其已經不能滿足快速高效處理數據的需求．為了解決這一問題，研究者們提出隨機最佳化方法，每步疊代僅對單個樣本進行最佳化，有效節省疊代過程中的計算時間和記憶體開銷． 尤其是Shalev-Shwarts 等提出隨機梯度下降算法(Stochastic Gradient Descent，SGD)，又被稱為Pegasos． 該算法在求解支持向量機問題時具有絕對優勢，可以在幾秒鐘內處理完文本資料庫RCV1 的80 萬個樣本． 但是，SGD 在求解強凸最佳化問題時僅能獲得O(logT /T) 的收斂速率，並未達到理論分析上的最優收斂速率O(1 /T)． 另一方面，SGD在強凸條件下的瞬時收斂速率也一直未獲得令人滿意的理論結果。

實際套用

在實際操作中，SGD 每次疊代僅需要最佳化單個樣本，與批處理方法相比，雖然減小計算量，但是卻存在方差，隨著疊代次數的增加，方差也逐漸累加，收斂速率不可避免地受到影響。研究表明，越來越多的研究者在已有最佳化算法中加入減小方差策略，提出新的算法，並獲得更好的收斂速率。因此，減小方差策略成為提升已有最佳化算法收斂速率的主要手段。Johnson 等提出SVRG(StochasticVariance Reduced Gradient)，求解光滑損失強凸最佳化問題時，在減小方差的同時獲得指數階的最優收斂速率，但SVRG 將目標函式看成一個整體，仍然屬於黑箱方法。因此，Xiao 等將SVRG 中的減小方差技巧推廣到Proximal 形式，得到隨機算法Prox-SVRG(Proximal SVRG)。 與SVRG 一樣，Prox-SVRG 在減小方差的同時獲得最優收斂速率，而且還保證最佳化問題的結構性。但是，上述2 種算法在修正梯度的過程中需要計算全梯度，從而不得不多次窮舉全部樣本。求解光滑問題的減小方差策略推廣到非光滑一般凸最佳化問題中，在每次疊代過程中僅使用部分樣本代替全部樣本，用於修正梯度，並獲得該類最佳化問題關於方差的最優收斂速率。

加速策略

在最佳化領域中，強凸問題的收斂速率的階不會優於O(1 /T)，但標準SGD 目前僅具有O(logT /T)收斂速率，並未達到理論上的最優收斂速率。為此，Rakhlin 等提出α-suffix 平均的技巧，僅使用α-suffix 平均代替算法1 平均輸出的後半部分。在未改變SGD 疊代步驟的前提下，達到最優收斂速率O(1 /T)。為了克服這一缺點，Lacoste-Julien 等提出一種加權平均技巧，僅對算法的輸出使用加權平均，就使SGD 達到O(1 /T) 的最優收斂速率。