從SGD到NadaMax,十種優化算法原理及實現

來源丨https://zhuanlan.zhihu.com/p/81020717本文僅用於學術分享，若侵權，請聯繫後臺作刪文處理。

無論是什麼優化算法，最後都可以用一個簡單的公式抽象：

 是參數，而  是參數的增量，而各種優化算法的主要區別在於對  的計算不同，本文總結了下面十個優化算法的公式，以及簡單的Python實現：

SGD

Momentum

Nesterov Momentum

AdaGrad

RMSProp

AdaDelta

Adam

AdaMax

Nadam

NadaMax

雖然有湊數的嫌疑，不過還是把SGD也順帶說一下，就算做一個符號說明了。常規的隨機梯度下降公式如下：

其中  是學習率，  是損失關於參數的梯度（有的資料中會寫成  等形式），不過相比SGD，用的更多的還是小批量梯度下降（mBGD）算法，不同之處在於一次訓練使用多個樣本，然後取所有參與訓練樣本梯度的平均來更新參數，公式如下：

其中  是第  次訓練中  個樣本損失關於參數梯度的均值，如無特別聲明，下文所出現  也遵循該定義

另外  或者  在下面的優化算法中，只是作為一個傳入的變量，其具體的計算是由其他模塊負責，可以參考下面兩個連結：

Numpy實現神經網絡框架(3)——線性層反向傳播推導及實現https://zhuanlan.zhihu.com/p/67854272卷積核梯度計算的推導及實現https://zhuanlan.zhihu.com/p/64248652Momentum，也就是動量的意思。該算法將梯度下降的過程視為一個物理系統，下圖是在百度圖片中找的（侵刪）如上圖所示，在該物理系統中有一個小球（質點），它所處的水平方向的位置對應為  的值，而垂直方向對應為損失。設其質量  ，在第  時刻，在單位時間內，該質點受外力而造成的動量改變為：(1.1)到(1.2)是因為  ，所以約去了。另外受到的外力可以分為兩個分量：重力沿斜面向下的力  和粘性阻尼力 所以這裡  ，另外  的方向與損失的梯度方向相反，並取係數為  ，得到：可以看出來是一個變相的等比數列之和，且公比小於1，所以存在極限，當  足夠大時，  趨近於 

import numpy as np

class Momentum(object):
def __init__(self, alpha=0.9, lr=1e-3):
self.alpha = alpha # 動量係數
self.lr = lr # 學習率
self.v = 0 # 初始速度為0

def update(self, g: np.ndarray): # g = J'(w) 為本輪訓練參數的梯度
self.v = self.alpha * self.v - self.lr * g # 公式
return self.v # 返回的是參數的增量，下同

以上是基於指數衰減的實現方式，另外有的Momentum算法中會使用指數加權平均來實現，主要公式如下：不過該方式因為  ，剛開始時  會比期望值要小，需要進行修正，下面的Adam等算法會使用該方式Nesterov Momentum是Momentum的改進版本，與Momentum唯一區別就是，Nesterov先用當前的速度  更新一遍參數，得到一個臨時參數  ，然後使用這個臨時參數計算本輪訓練的梯度。相當於是小球預判了自己下一時刻的位置，並提前使用該位置的梯度更新 ：為了更加直觀，還是上幾個圖吧，以下是Momentum算法  的更新過程：那麼Nesterov Momentum就提前使用這個梯度進行更新：整體來看Nesterov的表現要好於Momentum，至於代碼實現的話因為主要變化的是  ，所以可以之前使用Momentum的代碼AdaGrad全稱為Adaptive Subgradient，其主要特點在於不斷累加每次訓練中梯度的平方，公式如下：其中  是一個極小的正數，用來防止除0，而  ，  是矩陣的哈達瑪積運算符，另外，本文中矩陣的平方或者兩矩陣相乘都是計算哈達瑪積，而不是計算矩陣乘法從公式中可以看出，隨著算法不斷迭代，  會越來越大，整體的學習率會越來越小。所以，一般來說AdaGrad算法一開始是激勵收斂，到了後面就慢慢變成懲罰收斂，速度越來越慢對於代碼實現，首先將  展開得到：通常  ，所以在第一次訓練時(2.2)式為：因為每次訓練  的值是不確定的，所以要防止處0，但是可以令  ，這樣就可以在(2.2)式中去掉  將  代入(2.3)式，可以得到：可知  恆大於0，因此不必在計算  中額外加入  ，代碼如下：

class AdaGrad(object):
def __init__(self, eps=1e-8, lr=1e-3):
self.r = eps # r_0 = epsilon
self.lr = lr

def update(self, g: np.ndarray):
r = r + np.square(g)
return -self.lr * g / np.sqrt(r)

RMSProp是AdaGrad的改進算法，其公式和AdaGrad的區別只有  的計算不同，先看公式可以看出，與AdaGrad不同，RMSProp只會累積近期的梯度信息，對於「遙遠的歷史」會以指數衰減的形式放棄並且AdaGrad算法雖然在凸函數(Convex Functions)上表現較好，但是當目標函數非凸時，算法梯度下降的軌跡所經歷的結構會複雜的多，早期梯度對當前訓練沒有太多意義，此時RMSProp往往表現更好以下是將  展開後的公式：與AdaGrad一樣，令  ，從而去掉計算  時的  ，實現代碼：

class RMSProp(object):
def __init__(self, lr=1e-3, beta=0.999, eps=1e-8):
self.r = eps
self.lr = lr
self.beta = beta

def update(self, g: np.ndarray):
r = r * self.beta + (1-self.beta) * np.square(g)
return -self.lr * g / np.sqrt(r)

AdaDelta是與RMSProp相同時間對立發展出來的一個算法，在實現上可以看作是RMSProp的一個變種，先看公式：可以看到該算法不需要設置學習率  ，這是該算法的一大優勢。除了同樣以  來累積梯度的信息之外，該算法還多了一個  以指數衰減的形式來累積  的信息然後去掉(3.1)中的  ，得到：

class AdaDelta(object):
def __init__(self, beta=0.999, eps=1e-8):
self.r = eps
self.s = eps
self.beta = beta

def update(self, g: np.ndarray):
g_square = (1-self.beta) * np.square(g) # (1-beta)*g^2
r = r * self.beta + g_square
frac = s / r
res = -np.sqrt(frac) * g
s = s * self.beta + frac * g_squaretmp # 少一次乘法。。。
return res

更多關於AdaDelta的信息，可以參考這篇文章：自適應學習率調整：AdaDelta（https://www.cnblogs.com/neopenx/p/4768388.html）Adam的名稱來自Adaptive Momentum，可以看作是Momentum與RMSProp的一個結合體，該算法通過計算梯度的一階矩估計和二階矩估計而為不同的參數設計獨立的自適應性學習率，公式如下：(4.1)和(4.2)在Momentum和RMSProp中已經介紹過了，而不直接使用  計算  卻先經過(4.3)和(4.4)式是因為通常會設  ，所以此時梯度的一階矩估計和二階矩估是有偏的，需要進行修正雖然沒辦法避免修正計算，但是還是可以省去一些計算過程，初始化時令：因為  ，可知當  足夠大時修正將不起作用（也不需要修正了）：

class Adam(object):
def __init__(self, lr=1e-3, alpha=0.9, beta=0.999, eps=1e-8):
self.s = 0
self.r = eps
self.lr = lr
self.alpha = alpha
self.beta = beta
self.alpha_i = 1
self.beta_i = 1

def update(self, g: np.ndarray):
self.s = self.s * self.alpha + (1-self.alpha) * g
self.r = self.r * self.beta + (1-self.beta) * np.square(g)
self.alpha_i *= self.alpha
self.beta_i *= self.beta_i
lr = -self.lr * (1-self.beta_i)**0.5 / (1-self.alpha_i)
return lr * self.s / np.sqrt(self.r)

首先回顧RSMSProp中  的展開式並且令  ，得到：
可以看到這相當於是一個  的  範數，也就是說  的各維度的增量是根據該維度上梯度的  範數的累積量進行縮放的。如果用  範數替代就得到了Adam的不同變種，不過其中  範數對應的變種算法簡單且穩定對於  範數，第  輪訓練時梯度的累積為：由此再來遞推  ：需要注意，這個max比較的是梯度各個維度上的當前值和歷史最大值，具體可以結合代碼來看，最後其公式總結如下：另外，因為  是累積的梯度各個分量的絕對值最大值，所以直接用做分母且不需要修正，代碼如下：

class AdaMax(object):
def __init__(self, lr=1e-3, alpha=0.9, beta=0.999):
self.s = 0
self.r = 0
self.lr = lr
self.alpha = alpha
self.alpha_i = 1
self.beta = beta

def update(self, g: np.ndarray):
self.s = self.s * self.alpha + (1-self.alpha) * g
self.r = np.maximum(self.r*self.beta, np.abs(g))
self.alpha_i *= self.alpha
lr = -self.lr / (1-self.alpha_i)
return lr * self.s / self.r

Adam可以看作是Momentum與RMSProp的結合，既然Nesterov的表現較Momentum更優，那麼自然也就可以把Nesterov Momentum與RMSProp組合到一起了，首先來看Nesterov的主要公式：為了令其更加接近Momentum，將(5.1)和(5.2)修改為：接著，按照(5.4)式的套路，將  替換成  ，得到：同樣令  ，消去(5.8)式種的  ：

class Nadam(object):
def __init__(self, lr=1e-3, alpha=0.9, beta=0.999, eps=1e-8):
self.s = 0
self.r = eps
self.lr = lr
self.alpha = alpha
self.beta = beta
self.alpha_i = 1
self.beta_i = 1

def update(self, g: np.ndarray):
self.s = self.s * self.alpha + (1-self.alpha) * g
self.r = self.r * self.beta + (1-self.beta) * np.square(g)
self.alpha_i *= self.alpha
self.beta_i *= self.beta_i
lr = -self.lr * (1-self.beta_i)**0.5 / (1-self.alpha_i)
return lr * (self.s * self.alpha + (1-self.alpha) * g) / np.sqrt(self.r)

按照同樣的思路，可以將Nesterov與AdaMax結合變成NadaMax，回顧以下(5.8)式：用(6.2)式替換掉(6.1)式中標紅部分，得到：

class NadaMax(object):
def __init__(self, lr=1e-3, alpha=0.9, beta=0.999):
self.s = 0
self.r = 0
self.lr = lr
self.alpha = alpha
self.alpha_i = 1
self.beta = beta

def update(self, g: np.ndarray):
self.s = self.s * self.alpha + (1-self.alpha) * g
self.r = np.maximum(self.r*self.beta, np.abs(g))
self.alpha_i *= self.alpha
lr = -self.lr / (1-self.alpha_i)
return lr * (self.s * self.alpha + (1-self.alpha) * g) / self.r

[1]: 《機器學習算法背後的理論與優化》 ISBN 978-7-302-51718-4

[2]: Adam: A Method for Stochastic Optimization(https://arxiv.org/abs/1412.6980)

[3]: Incorporating Nesterov Momentum into Adam(https://openreview.net/forum?id=OM0jvwB8jIp57ZJjtNEZ&noteId=OM0jvwB8jIp57ZJjtNEZ)

[4]: An overview of gradient descent optimization algorithms(https://ruder.io/optimizing-gradient-descent/index.html)

想要了解更多資訊，請掃描下方二維碼，關注機器學習研究會

                                          

轉自：極市平臺