隨機加權算法

加權隨機算法是深度學習中的常見算法,一般套用在以下場景:有一個集合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) 的最優收斂速率。

相關詞條

熱門詞條

聯絡我們