一懂缕、梯度下降
1.1滞详、基本思想
梯度下降(gradient descent)是利用函數一階梯度信息尋找函數局部最優(yōu)解的常用的優(yōu)化方法暂筝。
對于函數,其梯度為
右遭,函數沿著梯度的方向增長最快做盅,增長的速度為其2-范數
缤削。為求函數的極小值窘哈,可采用負梯度方向上更新參數
,其中每次迭代的步長為
亭敢,即學習率滚婉。
下圖展示了函數的圖像及其梯度下降過程。
1.2帅刀、算法缺陷
盡管梯度下降算法十分簡明让腹,且對于大量問題是有效的远剩,但是也存在一些缺陷,包括:
-
易陷入局部極小值(local minimum)骇窍,甚至鞍點瓜晤。這是由于在局部極小值和鞍點,函數梯度
為零腹纳,參數不再更新痢掠。
陷入極小值或鞍點的情形 -
有可能在最優(yōu)點附近振蕩而無法收斂。這是由于固定的學習率
嘲恍,無法隨著梯度的變化而進行調整足画。
不同學習率對算法迭代的影響
對前一問題,可以通過引入動量(momentum)來解決佃牛;對后一問題淹辞,可以通過動態(tài)調整學習率來解決。
對于這些改進有相當多的成熟算法可以使用俘侠,下圖為torch.optim子包中的梯度下降算法及變形的關系圖象缀,并對各算法及其使用加以說明。
1.3爷速、SGD
在實際問題中攻冷,由于樣本數據量往往較大,如果每次都求全部樣本數據的梯度遍希,計算量會很大等曼,由此每次隨機抽取部分樣本進行更新,就可以大大加快更新速度凿蒜,這就是隨機梯度下降(stochastic gradient descent, SGD)禁谦。
關于SGD收斂性的證明和分析
在分析前對目標函數有兩個假設和兩個引理:
假設1:
目標函數二階可導且Hessian矩陣有界,其中
該假設說明了是強凸的废封,且是Lipschitz連續(xù)的州泊。
假設2:
(1)是
的無偏估計;
(2)關于
的方差
漂洋,其中
引理1:當
滿足假設1時遥皂,迭代過程中有如下不等式始終成立:
引理2:當
滿足假設1和假設2時,迭代過程中有如下不等式始終成立:
以下證明:當假設1和假設2滿足時刽漂,隨機梯度下降每次迭代的步長固定為演训,且滿足
,則
【證明】由假設1贝咙,是強凸的样悟,則具有性質
由引理2可得
兩邊同減去,并對
取期望,得到
兩邊同時減去窟她,得到
將迭代帶入上式可得
證畢陈症。
通過上式可以得到如下結論:
(1)固定步長的隨機梯度下降算法不能保證收斂到最小值點。
(2)固定步長的隨機梯度下降算法的收斂速度是sublinear的震糖。
這也印證了之前所說的兩個缺陷录肯。
二、改進型算法
2.1吊说、Momentum Optimizer
由于固定步長的學習率收斂速度慢嘁信,甚至無法收斂,Momentum Optimizer引入了一個momentum vector疏叨,每次參數的更新不僅與本次計算的梯度相關潘靖,還與之前的梯度相關,這樣會更加朝著有利于收斂到最優(yōu)解的方向蚤蔓,收斂速度更快卦溢。其更新公式如下:
其中是一個超參數, 可知Momentum 更新速度是GD的
倍秀又。
2.2 Nesterov Accelarated Gradient
Nesterov Accelarated Gradient, NAG是在Momentum 優(yōu)化的基礎上改進得到的算法单寂,與Momentum最大的不同在于:m每次更新時加上的梯度不同,NAG每次加上當前位置之后一點點 位置的梯度吐辙,這樣會更加正確指向最優(yōu)點的方向宣决,收斂速度更快。更新公式如下:
下圖說明了NAG比Momentum更好的原因昏苏,而且在極值點附近尊沸,如果超過了極值點,NAG會把更新的方向往回拉贤惯,而不是繼續(xù)向前洼专,這有利于減小振蕩加速收斂。
2.3孵构、AdaGrad Optimizer
AdaGrad Optimizer 即自適應梯度下降法屁商,是在梯度下降的基礎上動態(tài)調整學習率,第次迭代的學習率為
其中表示第
次迭代的梯度颈墅,
,
為預設的常數蜡镶。
此時參數更新的方式為
通過這樣的操作,保證了隨著迭代次數的增加恤筛,參數的更新速度會越來越慢官还,因此可以減小振蕩,避免因步長太大而無法收斂到極值點叹俏。同時有個缺點就是在復雜函數優(yōu)化中妻枕,容易過早收斂到局部極小值點僻族。
2.4粘驰、RMSProp
RMSProp (root mean square propagation) 是AdaGrad的拓展屡谐,利用衰減因子定義指數加權平均,即RMSProp通過只累加最近一次的梯度來解決AdaGrad更新過快的問題蝌数,第
次迭代的學習率為
此時參數更新的方式為
由兩部分組成:一部分是之前的梯度累積和愕掏,另一部分是當前梯度大小(主要作用)顶伞,離當前越遠的梯度對當前的影響越小饵撑。
2.5、Adam
Adam (adptive moment estimation) 結合了 Momentum和RMSProp的思想唆貌,它記錄了之前梯度的指數平均和之前梯度平方和的指數平均滑潘,第次迭代的學習率為
此時參數更新的方式為
綜合來說 Adam 是上述優(yōu)化方法中最優(yōu)的一個,當不知道如何選擇時锨咙,就選Adam吧语卤。
三、總結與實踐
以上幾種算法的區(qū)別總結在下表中酪刀,其形象優(yōu)劣亦可通過動圖看出粹舵。
優(yōu)化器類 | 優(yōu)化算法 | 改變量表達式 | 學習率表達式 |
---|---|---|---|
torch.optim.SGD | SGD | ||
torch.optim.SGD | Momentum | ||
torch.optim.SGD | NAG | ||
torch.optim.Adagrad | AdaGrad | ||
torch.optim.RMSProp | RMSProp | ||
torch.optim.Adam | Adam |
下面通過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()
以下用優(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
豈曰無衣施籍?與子同袍。王于興師概漱,修我戈矛丑慎,與子同仇!——《詩經·秦風》