優化方法小結

将各類型優化方法總結下友善查閱，大體分為：一階梯度依賴的，二階梯度依賴的；不依賴梯度的優化方法。

1）一階梯度依賴的優化方法

1.1）GD：Gradient Descent

這個很好了解，根據梯度 ▽wf(w) ▽ w f ( w ) 來指導下一步優化方向。

梯度來源于 f f 沿着某方向l=(e0,e1,...,ei)l=(e0,e1,...,ei)的方向導數： ∂f∂w|l=⟨∂f∂w,l⟩ ∂ f ∂ w | l = ⟨ ∂ f ∂ w , l ⟩ .

其中變化（增長）最快的方向及導數值稱為梯度： ▽wf(w)=(∂f∂w0,∂f∂w1,..,∂f∂wi) ▽ w f ( w ) = ( ∂ f ∂ w 0 , ∂ f ∂ w 1 , . . , ∂ f ∂ w i )

w=w−η▽wf(w) w = w − η ▽ w f ( w )

1.2）Moment GD

[帶有動量的GD](On the momentum term in gradient descent learning algorithms)，其基本思路是，設想如果目前的梯度方向與曆史累積的方向相同，是不是可以加大這個方向上的步幅，以加快收斂速度；若震蕩的梯度，則是不是可以互相抵消，避免多走彎路，以加快收斂速度。[同向累計，反向抵消]如下， γ=0.9 γ = 0.9

{vt=γvt−1+η▽ww=w−vt { v t = γ v t − 1 + η ▽ w w = w − v t

另外一種更新方式如下（需要見證下，來自安德魯的課程）：

{vt=γvt−1+(1−γ)▽ww=w−ηvt { v t = γ v t − 1 + ( 1 − γ ) ▽ w w = w − η v t

[ bias correct ]

假設一個時間變量 vt v t ，如果

vt=γvt−1+(1−γ)▽tw v t = γ v t − 1 + ( 1 − γ ) ▽ w t

→E[vt]=E[(1−γ)∑tj=1γt−j▽jw] → E [ v t ] = E [ ( 1 − γ ) ∑ j = 1 t γ t − j ▽ w j ]

→E[vt]=E[▽tw](1−γ)∑tj=1γt−j+ϵ → E [ v t ] = E [ ▽ w t ] ( 1 − γ ) ∑ j = 1 t γ t − j + ϵ

→E[vt]=E[▽tw](1−γt)+ϵ → E [ v t ] = E [ ▽ w t ] ( 1 − γ t ) + ϵ

得到 vt v t 的期望值是 ▽tw ▽ w t 的期望的指數衰減值。

若修正 vt=vt1−γt→E[vt]∝E[▽tw]+ϵ v t = v t 1 − γ t → E [ v t ] ∝ E [ ▽ w t ] + ϵ

1.3) NAG

NAG:Nesterov accelerated gradient [A method for unconstrained convex minimization problem with the rate of convergence o(1/k2)]

基本想法是，提前預知下一步的位置是上坡，則減小步幅，提前預支下一步的位置是下坡，則增大步幅。

{vt=γvt−1+η▽wf(w−γvt−1)w=w−vt { v t = γ v t − 1 + η ▽ w f ( w − γ v t − 1 ) w = w − v t

1.4) RMSprop

RMSprop GD :root mean square

是Hitton提出的，基本思路是Bias-correct，不過是利用 E[v] E [ v ] 與 ▽2w ▽ w 2 的正相關關系，找到梯度的期望來指導目前的參數更新。

假設 vt=γvt−1+(1−γ)▽2w v t = γ v t − 1 + ( 1 − γ ) ▽ w 2

則 →E[v]=E[▽2w](1−γ)+ϵ → E [ v ] = E [ ▽ w 2 ] ( 1 − γ ) + ϵ

{vt=γvt−1+(1−γ)▽2ww=w−η▽wvt√ { v t = γ v t − 1 + ( 1 − γ ) ▽ w 2 w = w − η ▽ w v t

1.5) Adam

Adam GD：adaptive moment estimation [2015-Adam, A Method for Stochastic Optimization]

結合了moment和RMSP的兩者優點，如下：

⎧⎩⎨⎪⎪⎪⎪⎪⎪vt=γ1vt−1+(1−γ1)▽wst=γ2st−1+(1−γ2)▽2ww=w−ηvtst√+ϵ→vt=vt1−γ1→st=st1−γ2γ1=0.9;γ2=0.999 { v t = γ 1 v t − 1 + ( 1 − γ 1 ) ▽ w → v t = v t 1 − γ 1 s t = γ 2 s t − 1 + ( 1 − γ 2 ) ▽ w 2 → s t = s t 1 − γ 2 w = w − η v t s t + ϵ γ 1 = 0.9 ; γ 2 = 0.999

并且在online-learning時，Adam也是收斂的。

1.6) AdaGrad

AdaGrad Descent [ Adaptive Subgradient Methods for Online Learning

and Stochastic Optimization]

基本思路： 自适應學習率，能夠對頻繁更新的參數采取更小的步幅；對更新不頻繁的參數采取更大的步幅。非常适合稀疏資料的學習。其中 Gi G i 表示到update當時為止，所有已計算的梯度的平方和。

wi=wi−ηGi+ϵ−−−−−√▽wi w i = w i − η G i + ϵ ▽ w i

1.7) AdaDelt

AdaDelt GD [ An Adaptive Learning Rate Method]

AdaGrad存在問題：平方和的累和會一直增加下去，導緻分母部分無限大，梯度被削弱至非常小，參數不再更新。而AdaDelt則剛好為解決這問題而誕生，借助指數衰減平均 E[▽2w]t=γE[▽2w]t−1+(1−γ)▽2wt E [ ▽ w 2 ] t = γ E [ ▽ w 2 ] t − 1 + ( 1 − γ ) ▽ w t 2 的思路來避免所有曆史梯度^2的平均加和。

首先參數的增量值 △xt,i △ x t , i 用梯度的期望來表示為： △xt,i=−ηE[▽2wi]t+ϵ√▽wt,i △ x t , i = − η E [ ▽ w i 2 ] t + ϵ ▽ w t , i

然後增量值的期望值也用指數衰減平均表示 E[△2x]t=γE[△2x]t−1+(1−γ)△2xt E [ △ x 2 ] t = γ E [ △ x 2 ] t − 1 + ( 1 − γ ) △ x t 2

用梯度的期望，增量值的期望估計(當次的不知道，用前一次的來估計)，以及目前梯度來指導學習的方向。

→wt,i=wt−1,i−E[△2xi]t−1+ϵ−−−−−−−−−−−√E[▽2wi]t+ϵ−−−−−−−−−√▽wt,i → w t , i = w t − 1 , i − E [ △ x i 2 ] t − 1 + ϵ E [ ▽ w i 2 ] t + ϵ ▽ w t , i

作者在原文裡解釋，是用一階導數去估計二階導數Hassion矩陣。

補充閱讀

AdaMax

Nadam:Nesterov Momentum into Adam

DFP

DFBS

AdamW

估計函數的二階導數，其實好多方法都是對二階導數的估計得來的，比如DFP/DFBS/AdaDelt。

2）二階梯度依賴的優化方法

各種适應性，在有道雲筆記上有部分内容。

牛頓下降法

求解 argminxf(x) a r g m i n x f ( x ) ，等價于找到 f′(x)=0 f ′ ( x ) = 0 對應的 x∗ x ∗ 值。

要想找到函數的零值點，可以根據其泰勒展開 f(x)=f(xk)+(x−xk)f′(xk) f ( x ) = f ( x k ) + ( x − x k ) f ′ ( x k ) 作近似逼近，另f=0，得到 xk+1=xk−f(xk)f′(xk) x k + 1 = x k − f ( x k ) f ′ ( x k ) ，由于導數是描述增幅的，那麼對應的 xk+1 x k + 1 就相應的比 xk x k 要更靠近零值點，如下圖。

那麼回到等價問題上，找到函數 f′(x) f ′ ( x ) 的零值點，我們對 f′(x) f ′ ( x ) 在某處 xk x k 做一階展開 f′(x)=f′(xk)+(x−xk)f′′(xk) f ′ ( x ) = f ′ ( x k ) + ( x − x k ) f ″ ( x k ) ，于是得到疊代關系 xk+1=xk−f′(xk)f′′(xk) x k + 1 = x k − f ′ ( x k ) f ″ ( x k ) 可以不斷逼近 f′(x) f ′ ( x ) 的零值點。

3）不依賴梯度的優化方法

3.1）Gradient Boost

Gradient Boost的梯度方向是由最終label與目前的預測label之間的差距給出的，詳細見GB

3.2）Constractive Divergence

對比散度類方法，主要是根據條件随機場的收斂性，可以根據下次采樣比目前狀态更靠近穩定最優解，來給出優化方向，詳細見RBM。

梯度相關的trick

1） ReLU等激活函數的各種類型。

2） Gradient Clip，常用在RNN類方法中。

3） Batch Normalize，對所有網絡都使用。（Group Normalization, Switchable Normalization等改進的方法）

4） 正則化方法及各種變形改進。（DIN裡面有個根據資料對梯度作限制的正則，非常有意思）

未完待續

後續會補充能查到的資料，并且會講解如何在TF裡面實作自定義的Gradient Optimize Operation。