深度學習(一):優(yōu)化方法

一懂缕、梯度下降

1.1滞详、基本思想

梯度下降(gradient descent)是利用函數一階梯度信息尋找函數局部最優(yōu)解的常用的優(yōu)化方法暂筝。
對于函數f(x),其梯度為\nabla f(x)=\frac{\partial f}{\partial x}右遭,函數沿著梯度的方向增長最快做盅,增長的速度為其2-范數||\nabla f||缤削。為求函數的極小值窘哈,可采用負梯度方向上更新參數 x_{k+1}=x_{k}-\eta \nabla f(x),其中每次迭代的步長為\eta亭敢,即學習率滚婉。

下圖展示了函數f(x)=-(cos^2 x_0 + cos^2 x_1)^2的圖像及其梯度下降過程。

函數圖像及其梯度下降過程

1.2帅刀、算法缺陷

盡管梯度下降算法十分簡明让腹,且對于大量問題是有效的远剩,但是也存在一些缺陷,包括:

  • 易陷入局部極小值(local minimum)骇窍,甚至鞍點瓜晤。這是由于在局部極小值和鞍點,函數梯度\nabla f為零腹纳,參數不再更新痢掠。

    陷入極小值或鞍點的情形

  • 有可能在最優(yōu)點附近振蕩而無法收斂。這是由于固定的學習率\eta嘲恍,無法隨著梯度的變化而進行調整足画。

    不同學習率對算法迭代的影響

對前一問題,可以通過引入動量(momentum)來解決佃牛;對后一問題淹辞,可以通過動態(tài)調整學習率來解決。
對于這些改進有相當多的成熟算法可以使用俘侠,下圖為torch.optim子包中的梯度下降算法及變形的關系圖象缀,并對各算法及其使用加以說明。

torch.optim子包中的梯度下降算法及變形

1.3爷速、SGD

在實際問題中攻冷,由于樣本數據量往往較大,如果每次都求全部樣本數據的梯度遍希,計算量會很大等曼,由此每次隨機抽取部分樣本進行更新,就可以大大加快更新速度凿蒜,這就是隨機梯度下降(stochastic gradient descent, SGD)禁谦。

關于SGD收斂性的證明和分析

在分析前對目標函數有兩個假設和兩個引理:

假設1:
目標函數二階可導且Hessian矩陣有界 m I \preceq F^{\prime \prime}(w) \preceq M I,其中m,M\geq0

該假設說明了F是強凸的废封,且是Lipschitz連續(xù)的州泊。

假設2:
(1)g\left(\boldsymbol{w}_{k}, \xi_{k}\right)F^{\prime}\left(\boldsymbol{w}_{k}\right)的無偏估計;
(2)g\left(\boldsymbol{w}_{k}, \xi_{k}\right)關于\xi_{k}的方差\operatorname{Var}_{\xi_{k}}\left[g\left(\boldsymbol{w}_{k}, \xi_{k}\right)\right] \leqslant V漂洋,其中V\geq0

引理1:當F滿足假設1時遥皂,迭代過程中有如下不等式始終成立:
\begin{aligned} \mathbb{E}_{\xi_{k}}\left[F\left(\boldsymbol{w}_{k+1}\right)\right]-F\left(\boldsymbol{w}_{k}\right) \leqslant &-\eta_{k} F^{\prime}\left(\boldsymbol{w}_{k}\right)^{\top} \mathbb{E}_{\xi_{k}}\left[g\left(\boldsymbol{w}_{k}, \xi_{k}\right)\right] +\frac{1}{2} \eta_{k}^{2} M \mathbb{E}_{\xi_{k}}\left[\left\|g\left(\boldsymbol{w}_{k}, \xi_{k}\right)\right\|_{2}^{2}\right] \end{aligned}

引理2:當F滿足假設1和假設2時,迭代過程中有如下不等式始終成立:
\mathbb{E}_{\xi_{k}}\left[F\left(\boldsymbol{w}_{k+1}\right)\right]-F\left(\boldsymbol{w}_{k}\right) \leqslant-\left(1-\frac{1}{2} \eta_{k} M\right) \eta_{k}\left\|F^{\prime}\left(\boldsymbol{w}_{k}\right)\right\|_{2}^{2}+\frac{1}{2} \eta_{k}^{2} M V

以下證明:當假設1和假設2滿足時刽漂,隨機梯度下降每次迭代的步長固定為\eta_{k}=\eta_{0}演训,且滿足0<\eta_{0} \leqslant \frac{1}{M},則 \mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right] \leqslant \frac{\eta_{0} M V}{2 m}+\left(1-\eta_{0} m\right)^{k-1}\left(\mathbb{E}\left[F\left(\boldsymbol{w}_{0}\right)-F^{*}\right]-\frac{\eta_{0} M V}{2 m}\right)

【證明】由假設1贝咙,F是強凸的样悟,則具有性質\left\|F^{\prime}\left(\boldsymbol{w}_{k}\right)\right\|_{2}^{2} \geqslant 2 m\left(F\left(\boldsymbol{w}_{k}\right)-F^{*}\right)

由引理2可得
\begin{aligned} \mathbb{E}_{\xi(k)}\left[F\left(\boldsymbol{w}_{k+1}\right)\right]-F\left(\boldsymbol{w}_{k}\right) & \leqslant-\left(1-\frac{1}{2} \eta_{0} M\right) \eta_{k}\left\|F^{\prime}\left(\boldsymbol{w}_{k}\right)\right\|_{2}^{2}+\frac{1}{2} \eta_{0}^{2} M V \\ & \leqslant-\frac{1}{2} \eta_{0}\left\|F^{\prime}\left(\boldsymbol{w}_{k}\right)\right\|_{2}^{2}+\frac{1}{2} \eta_{0}^{2} M V \\ & \leqslant-\eta_{0} m\left(F\left(\boldsymbol{w}_{k}\right)-F^{*}\right)+\frac{1}{2} \eta_{0}^{2} M V \end{aligned}

兩邊同減去F^*,并對\xi^{(1)}, \xi^{(2)}, \cdots, \xi^{(k)}取期望,得到\mathbb{E}\left[F\left(\boldsymbol{w}_{k+1}\right)-F^{*}\right] \leqslant\left(1-\eta_{0} m\right) \mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]+\frac{1}{2} \eta_{0} M V

兩邊同時減去\frac{\eta_{0} M V}{2 m}窟她,得到
\begin{aligned} \mathbb{E}\left[F\left(\boldsymbol{w}_{k+1}\right)-F^{*}\right]-\frac{\eta_{0} M V}{2 m} & \leqslant\left(1-\eta_{0} m\right) \mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]+\frac{1}{2} \eta_{0} M V-\frac{\eta_{0} M V}{2 m} \\ &=\left(1-\eta_{0} m\right)\left(\mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]-\frac{\eta_{0} M V}{2 m}\right) \end{aligned}
k,\cdots,2,1迭代帶入上式可得
\begin{aligned} \mathbb{E}\left[F\left(\boldsymbol{w}_{k+1}\right)-F^{*}\right]-\frac{\eta_{0} M V}{2 m} & \leqslant\left(1-\eta_{0} m\right) \mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]+\frac{1}{2} \eta_{0} M V-\frac{\eta_{0} M V}{2 m} \\ &=\left(1-\eta_{0} m\right)^{k-1}\left(\mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]-\frac{\eta_{0} M V}{2 m}\right) \end{aligned}
證畢陈症。
通過上式可以得到如下結論:
(1)固定步長的隨機梯度下降算法不能保證收斂到最小值點。\lim _{k \rightarrow \infty} \mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]=\frac{\eta_{0} M V}{2 m}
(2)固定步長的隨機梯度下降算法的收斂速度是sublinear的震糖。
\lim _{k \rightarrow \infty} \frac{\mathbb{E} \left[F\left(\boldsymbol{w}_{k+1}\right)-F^{*}\right]}{\mathbb{E}\left[F\left(\boldsymbol{w}_{k}\right)-F^{*}\right]}=1
這也印證了之前所說的兩個缺陷录肯。

二、改進型算法

2.1吊说、Momentum Optimizer

由于固定步長的學習率收斂速度慢嘁信,甚至無法收斂,Momentum Optimizer引入了一個momentum vector疏叨,每次參數的更新不僅與本次計算的梯度相關潘靖,還與之前的梯度相關,這樣會更加朝著有利于收斂到最優(yōu)解的方向蚤蔓,收斂速度更快卦溢。其更新公式如下:
\begin{array}{c}{m \leftarrow \beta m+\eta \nabla f(w)} \\ {w \leftarrow w-m}\end{array}
其中\beta是一個超參數, 可知Momentum 更新速度是GD的\frac{1} {1-\beta}倍秀又。

2.2 Nesterov Accelarated Gradient

Nesterov Accelarated Gradient, NAG是在Momentum 優(yōu)化的基礎上改進得到的算法单寂,與Momentum最大的不同在于:m每次更新時加上的梯度不同,NAG每次加上當前位置之后一點點 位置的梯度吐辙,這樣會更加正確指向最優(yōu)點的方向宣决,收斂速度更快。更新公式如下:
\begin{array}{c}{m \leftarrow \beta m+\eta \nabla f(w+\beta m)} \\ {w \leftarrow w-m}\end{array}
下圖說明了NAG比Momentum更好的原因昏苏,而且在極值點附近尊沸,如果超過了極值點,NAG會把更新的方向往回拉贤惯,而不是繼續(xù)向前洼专,這有利于減小振蕩加速收斂。

NAG vs Momentum

2.3孵构、AdaGrad Optimizer

AdaGrad Optimizer 即自適應梯度下降法屁商,是在梯度下降的基礎上動態(tài)調整學習率,第t次迭代的學習率為
\eta_{t}=\frac{l}{\sqrt{g_{0}^{2}+g_{1}^{2}+\cdots+g_{t-1}^{2}+\varepsilon}}
其中g_{t-1}表示第t次迭代的梯度颈墅,l,\varepsilon為預設的常數蜡镶。
此時參數更新的方式為{ w \leftarrow w-\eta_t g_{t-1}}
通過這樣的操作,保證了隨著迭代次數的增加恤筛,參數的更新速度會越來越慢官还,因此可以減小振蕩,避免因步長太大而無法收斂到極值點叹俏。同時有個缺點就是在復雜函數優(yōu)化中妻枕,容易過早收斂到局部極小值點僻族。

2.4粘驰、RMSProp

RMSProp (root mean square propagation) 是AdaGrad的拓展屡谐,利用衰減因子定義指數加權平均a_{t}^{(2)},即RMSProp通過只累加最近一次的梯度來解決AdaGrad更新過快的問題蝌数,第t次迭代的學習率為
\eta_{t}=\frac{1}{\sqrt{a_{t}^{(2)}+\varepsilon}}
此時參數更新的方式為{ w \leftarrow w-\eta_t g_{t-1}}
a_{t}^{(2)}由兩部分組成:一部分是之前的梯度累積和愕掏,另一部分是當前梯度大小(主要作用)顶伞,離當前越遠的梯度對當前的影響越小饵撑。

2.5、Adam

Adam (adptive moment estimation) 結合了 Momentum和RMSProp的思想唆貌,它記錄了之前梯度的指數平均和之前梯度平方和的指數平均滑潘,第t次迭代的學習率為
\eta_{t} \propto \frac{1}{\sqrt{\frac{a_{t}^{(2)}+\varepsilon}{1-\left(\rho^{(2)}\right)^{t}}}}
此時參數更新的方式為{ w \leftarrow w-\eta_t \frac{a_{t}^{(1)}} {1-(\rho^{(1)})^t}}
綜合來說 Adam 是上述優(yōu)化方法中最優(yōu)的一個,當不知道如何選擇時锨咙,就選Adam吧语卤。

三、總結與實踐

以上幾種算法的區(qū)別總結在下表中酪刀,其形象優(yōu)劣亦可通過動圖看出粹舵。

優(yōu)化器類 優(yōu)化算法 改變量表達式 學習率表達式
torch.optim.SGD SGD { w \leftarrow w-\eta \nabla f(w)} \eta = const
torch.optim.SGD Momentum { w \leftarrow w-(\beta m+\eta \nabla f(w))} \eta = const
torch.optim.SGD NAG { w \leftarrow w-(\beta m+\eta \nabla f(w+\beta m))} \eta = const
torch.optim.Adagrad AdaGrad { w \leftarrow w-\eta_t g_{t-1}} \eta_{t} \propto \frac{1}{\sqrt{\sum_{\tau=0}^{t-1} g_{\tau}^{2}+\varepsilon}}
torch.optim.RMSProp RMSProp { w \leftarrow w-\eta_t g_{t-1}} \eta_{t}=\frac{1}{\sqrt{a_{t}^ {(2)}+\varepsilon}}
torch.optim.Adam Adam { w \leftarrow w-\eta_t \frac{a_{t}^{(1)}} {1-(\rho^{(1)})^ t}} \eta_{t} \propto \frac{1}{\sqrt{\frac{a_{t}^{(2)}+\varepsilon}{1-\left(\rho^{(2)}\right)^{t}}}}

下面通過pytorch的優(yōu)化包來實踐優(yōu)化的過程。Himmelblau函數是常見的測試優(yōu)化器性能的函數骂倘,它有4個值為零的極小值點眼滤,其函數實現和圖像如下所示:

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def him(x):
    return (x[0]**2+x[1]-11)**2 + (x[0]+x[1]**2-7)**2

x = np.arange(-6,6,0.1)
y = np.arange(-6,6,0.1)
X,Y = np.meshgrid(x,y)
Z = him([X,Y])

fig = plt.figure()
ax = fig.gca(projection='3d')
ax.plot_surface(X,Y,Z,cmap='rainbow')
ax.set_xlabel('x[0]')
ax.set_ylabel('x[1]')
ax.set_zlabel('f')
fig.show()
Himmelblau 函數圖像

以下用優(yōu)化器 torch.optim.Adam 來最小化Himmelblau 函數,共迭代20000次历涝,每迭代1000次诅需,輸出一次結果。

import torch
x = torch.tensor([0.,0.],requires_grad=True)
optimizer = torch.optim.Adam([x,])
for step in range(20001):
    f = him(x)
    optimizer.zero_grad()
    f.backward()
    optimizer.step()
    if step % 1000 == 0:
        print('step:{}, x:{}, f(x):{}'.format(step,x.tolist(),f))

初試值為(0,0)時荧库,結果如下诱担,最后收斂到極小值0。

step:0, x:[0.0, 0.0], f(x):170.0
step:1000, x:[1.270142912864685, 1.118398904800415], f(x):88.53223419189453
step:2000, x:[2.332378387451172, 1.9535709619522095], f(x):13.7662353515625
step:3000, x:[2.8519949913024902, 2.114161729812622], f(x):0.6711392402648926
step:4000, x:[2.981964111328125, 2.0271568298339844], f(x):0.014927156269550323
step:5000, x:[2.9991261959075928, 2.0014777183532715], f(x):3.9870232285466045e-05
step:6000, x:[2.999983549118042, 2.0000221729278564], f(x):1.1074007488787174e-08
step:7000, x:[2.9999899864196777, 2.000013589859009], f(x):4.150251697865315e-09
step:8000, x:[2.9999938011169434, 2.0000083446502686], f(x):1.5572823031106964e-09
step:9000, x:[2.9999964237213135, 2.000005006790161], f(x):5.256879376247525e-10
step:10000, x:[2.999997854232788, 2.000002861022949], f(x):1.8189894035458565e-10
step:11000, x:[2.9999988079071045, 2.0000014305114746], f(x):5.547917680814862e-11
step:12000, x:[2.9999992847442627, 2.0000009536743164], f(x):1.6370904631912708e-11
step:13000, x:[2.999999523162842, 2.000000476837158], f(x):5.6843418860808015e-12
step:14000, x:[2.999999761581421, 2.000000238418579], f(x):1.8189894035458565e-12
step:15000, x:[3.0, 2.0], f(x):0.0
step:16000, x:[3.0, 2.0], f(x):0.0
step:17000, x:[3.0, 2.0], f(x):0.0
step:18000, x:[3.0, 2.0], f(x):0.0
step:19000, x:[3.0, 2.0], f(x):0.0
step:20000, x:[3.0, 2.0], f(x):0.0

初試值為(-1,0)時电爹,結果如下蔫仙,最后收斂到極其接近于極小值0。

step:0, x:[-1.0, 0.0], f(x):164.0
step:1000, x:[-2.065551996231079, 1.1903401613235474], f(x):89.31765747070312
step:2000, x:[-2.703892469406128, 2.321927547454834], f(x):20.508712768554688
step:3000, x:[-2.800236940383911, 2.973504066467285], f(x):0.9571946263313293
step:4000, x:[-2.8048553466796875, 3.124056816101074], f(x):0.002129464643076062
step:5000, x:[-2.8051087856292725, 3.1312758922576904], f(x):5.7411853049416095e-08
step:6000, x:[-2.805112838745117, 3.1313014030456543], f(x):5.68707037018612e-09
step:7000, x:[-2.805114984512329, 3.131305694580078], f(x):2.143679012078792e-09
step:8000, x:[-2.8051164150238037, 3.1313085556030273], f(x):7.466951501555741e-10
step:9000, x:[-2.805117130279541, 3.131310224533081], f(x):2.4942892196122557e-10
step:10000, x:[-2.805117607116699, 3.1313111782073975], f(x):7.275957614183426e-11
step:11000, x:[-2.8051178455352783, 3.1313116550445557], f(x):2.637534635141492e-11
step:12000, x:[-2.8051180839538574, 3.131312131881714], f(x):5.6843418860808015e-12
step:13000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:14000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:15000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:16000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:17000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:18000, x:[-2.8051180839538574, 3.131312608718872], f(x):2.2737367544323206e-13
step:19000, x:[-2.8051180839538574, 3.131312370300293], f(x):2.2737367544323206e-13
step:20000, x:[-2.8051180839538574, 3.131312608718872], f(x):2.2737367544323206e-13

另外一階優(yōu)化方法還包括AdaDelta丐箩、Adamax等摇邦,二階方法還包括牛頓法及其衍生方法,等有時間再加以補充屎勘。

參考資料

[1] https://yq.aliyun.com/articles/616375
[2] 史春奇等 著. 機器學習算法背后的理論與優(yōu)化. 北京:清華大學出版社,2019
[3] 肖智清 著. 神經網絡與PyTorch實戰(zhàn). 北京:機械工業(yè)出版社, 2018
[4] Ian Goodfellow 等 著, 趙申劍等 譯, 深度學習. 北京:人民郵電出版社, 2017

豈曰無衣施籍?與子同袍。王于興師概漱,修我戈矛丑慎,與子同仇!——《詩經·秦風》

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市竿裂,隨后出現的幾起案子玉吁,更是在濱河造成了極大的恐慌,老刑警劉巖腻异,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件进副,死亡現場離奇詭異,居然都是意外死亡悔常,警方通過查閱死者的電腦和手機影斑,發(fā)現死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來机打,“玉大人矫户,你說我怎么就攤上這事〔醒” “怎么了吏垮?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長罐旗。 經常有香客問我膳汪,道長,這世上最難降的妖魔是什么九秀? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任遗嗽,我火速辦了婚禮,結果婚禮上鼓蜒,老公的妹妹穿的比我還像新娘痹换。我一直安慰自己,他們只是感情好都弹,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布娇豫。 她就那樣靜靜地躺著,像睡著了一般畅厢。 火紅的嫁衣襯著肌膚如雪冯痢。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天框杜,我揣著相機與錄音浦楣,去河邊找鬼。 笑死咪辱,一個胖子當著我的面吹牛振劳,可吹牛的內容都是我干的。 我是一名探鬼主播油狂,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼历恐,長吁一口氣:“原來是場噩夢啊……” “哼寸癌!你這毒婦竟也來了?” 一聲冷哼從身側響起弱贼,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤蒸苇,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后哮洽,有當地人在樹林里發(fā)現了一具尸體填渠,經...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡弦聂,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年鸟辅,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片莺葫。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡匪凉,死狀恐怖,靈堂內的尸體忽然破棺而出捺檬,到底是詐尸還是另有隱情再层,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布堡纬,位于F島的核電站聂受,受9級特大地震影響,放射性物質發(fā)生泄漏烤镐。R本人自食惡果不足惜蛋济,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望炮叶。 院中可真熱鬧碗旅,春花似錦、人聲如沸镜悉。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽侣肄。三九已至旧困,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間稼锅,已是汗流浹背癣籽。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工顿颅, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓识椰,卻偏偏與公主長得像,于是被迫代替她去往敵國和親曼振。 傳聞我的和親對象是個殘疾皇子珍坊,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內容