機器學習各優化演算法的簡單總結

01-30

梯度下降

SGD

SGD（Stochasitic Gradient Descent）很簡單，就是沿著梯度的反方向更新參數，優化目標函數。優化公式如下

$begin{align} &d_i = gleft(theta_{i-1}right) &theta_i=theta_{i-1}-lambda d_i end{align}$

其中 $d_i$ 為當前位置的梯度。

Momentum

Momentum改進自SGD，讓每一次的參數更新方向不僅取決於當前位置的梯度，還受到上一次參數更新方向的影響。

$begin{align} &d_i = beta d_{i-1}-lambda gleft(theta_{i-1}right) &theta_i=theta_{i-1}+ d_i end{align}$

Momentum的意思就是動量，也就意味著上一次更新的方向對本次更新仍然有影響。

Nestrov Momentum

Nestrov Momentum的意義在於，既然下一次一定會更新 $beta d_{i-1}$ ，那麼求梯度的時候就可以用提前位置的梯度 $gleft(theta_{i-1}+beta d_{i-1}right)$ ，則

$begin{align} &d_i = beta d_{i-1}-lambda gleft(theta_{i-1}+beta d_{i-1}right) &theta_i=theta_{i-1}+ d_i end{align}$

實驗中，一般用Nestrov Momentum比較多，收斂比Momentum要更快一些。

自適應方法

Adagrad

$begin{align} &c_i=c_{i-1}+g^2left(theta_{i-1}right) &theta_i=theta_{i-1}-frac{lambda}{sqrt{c_i+epsilon}}gleft(theta_{i-1}right) end{align}$

其中， $c_i$ 是一個cache，保存了各位置梯度的平方， $epsilon$ 一般取值為 $10^{-4}$ ～ $10^{-8}$ ，為了防止分母取零。可以看出，Adagrad不需要手動調節學習率 $lambda$ ，因為整體來看，學習率為 $frac{lambda}{sqrt{c_i+epsilon}}$ ，它會根據 $c_i$ 的大小發生自適應的變化（不同位置上變化的幅度不同）。但是因為 $g^2left(theta_{i-1}right)$ 一直是正數，所以總的來說，學習率也一直是在變小，最後可能會導致參數無法更新。

Rmsprop

$begin{align} &c_i=gamma c_{i-1}+left(1-gammaright)g^2left(theta_{i-1}right) &theta_i=theta_{i-1}-frac{lambda}{sqrt{c_i+epsilon}}gleft(theta_{i-1}right) end{align}$

可以看出，Rmsprop與Adagrad類似，只不過cache的計算略微複雜一些，利用了一個衰減因子 $gamma$ ，這樣可以使得 $c_i$ 並不是一直處於增大的情況，可以解決Adagrad學習率迅速減小的問題。其中，衰減因子 $gamma$ 通常取值為[0.9，0.99，0.999]。

Adadelta

$begin{align}&c_i=gamma c_{i-1}+left(1-gammaright)g^2left(theta_{i-1}right)&d_i = -frac{sqrt{Delta_{i-1}+epsilon}}{sqrt{c_i+epsilon}}g(theta_{i-1})&theta_i=theta_{i-1}+d_i&Delta_i = gammaDelta_{i-1}+(1-gamma)d_i^2end{align}$

Adadelta與Rmsprop類似，但是連初始的學習速率 $lambda$ 都不用設置。

Adam

$begin{align} &m_i=beta_1m_{i-1}+left(1-beta_1right)gleft(theta_{i-1}right) &v_i=beta_2v_{i-1}+left(1-beta_2right)g^2left(theta_{i-1}right) &hat{m_i}=frac{m_i}{1-beta_1^t} &hat{v_i}=frac{v_i}{1-beta_2^t} &theta_i=theta_{i-1}-frac{lambda}{sqrt{hat{v_i}+epsilon}}hat{m_i} end{align}$

與Rmsprop類似，Adam除了利用一個衰減因子 $beta_2$ 計算cache以外，還類似Momentum，利用了上一次的參數更新方向，所以可以說Adam是帶Momentum的Rmsprop。在參數更新的最初幾步中，由於 $m_i$ 與 $v_i$ 是初始化為0的，為了防止最初幾步的更新向0偏差，Adam利用 $beta_i$ 的 $t$ 次冪來修正這種偏差（ $t$ 每次更新加1）。其中，通常 $beta_1$ 取值為0.9， $beta_2$ 取值為0.999， $epsilon$ 取值為 $10^{-8}$ 。

牛頓法與擬牛頓法

牛頓法

牛頓法和梯度下降法類似，也是求解無約束最優化問題的方法，收斂速度較快（考慮到了二階導數的信息）。

$begin{align} &d_i = gleft(theta_{i-1}right) &theta_i=theta_{i-1}-lambda H_{i-1}^{-1}d_i end{align}$

其中， $H_{i-1}$ 是優化目標函數 $L$ 在第 $i-1$ 步的海森矩陣。牛頓法的缺點就是 $H^{-1}$ 計算比較複雜，因此有其他改進的方法，例如擬牛頓法。

擬牛頓法

擬牛頓法用一個矩陣 $G$ 來近似代替 $H^{-1}$ （或 $B$ 來代替 $H$ ），其中 $G$ 滿足擬牛頓條件：

$G_{i+1}y_i=delta_i$ （ $B_{i+1}delta_i=y_i$ ）

其中 $y_i=gleft(theta_{i+1}right)-gleft(theta_{i}right)$ ， $delta_i=x_{i+1}-x_{i}$ 。因此按照擬牛頓條件，每次只需更新 $G_{i+1}$ (或 $B_{i+1}$ )即可，使得 $G_{i+1}=G_i+Delta G_i$ 。

牛頓法有多種的具體實現，其中DFP演算法選擇更新 $G$ ，BFGS選擇更新 $B$ ，這裡就不細講了。

參考

CS231n Convolutional Neural Networks for Visual Recognition
ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION
《統計學習方法》李航
Newton - Wikipedia