深度学习（一）：优化方法

作者: fromeast | 来源:发表于2019-08-15 21:14 被阅读48次

一、梯度下降

1.1、基本思想

梯度下降(gradient descent)是利用函数一阶梯度信息寻找函数局部最优解的常用的优化方法。
对于函数 $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$ 为零，参数不再更新。

陷入极小值或鞍点的情形
有可能在最优点附近振荡而无法收敛。这是由于固定的学习率 $\eta$ ，无法随着梯度的变化而进行调整。

不同学习率对算法迭代的影响

对前一问题，可以通过引入动量(momentum)来解决；对后一问题，可以通过动态调整学习率来解决。
对于这些改进有相当多的成熟算法可以使用，下图为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连续的。

假设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，每次参数的更新不仅与本次计算的梯度相关，还与之前的梯度相关，这样会更加朝着有利于收敛到最优解的方向，收敛速度更快。其更新公式如下：
$\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 优化的基础上改进得到的算法，与Momentum最大的不同在于：m每次更新时加上的梯度不同，NAG每次加上当前位置之后一点点位置的梯度，这样会更加正确指向最优点的方向，收敛速度更快。更新公式如下：
$\begin{array}{c}{m \leftarrow \beta m+\eta \nabla f(w+\beta m)} \\ {w \leftarrow w-m}\end{array}$
下图说明了NAG比Momentum更好的原因，而且在极值点附近，如果超过了极值点，NAG会把更新的方向往回拉，而不是继续向前，这有利于减小振荡加速收敛。

NAG vs Momentum

2.3、AdaGrad Optimizer

AdaGrad Optimizer 即自适应梯度下降法，是在梯度下降的基础上动态调整学习率，第 $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}}$
通过这样的操作，保证了随着迭代次数的增加，参数的更新速度会越来越慢，因此可以减小振荡，避免因步长太大而无法收敛到极值点。同时有个缺点就是在复杂函数优化中，容易过早收敛到局部极小值点。

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 是上述优化方法中最优的一个，当不知道如何选择时，就选Adam吧。

三、总结与实践

以上几种算法的区别总结在下表中，其形象优劣亦可通过动图看出。

优化器类	优化算法	改变量表达式	学习率表达式
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的优化包来实践优化的过程。Himmelblau函数是常见的测试优化器性能的函数，它有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 函数图像

以下用优化器 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

另外一阶优化方法还包括AdaDelta、Adamax等，二阶方法还包括牛顿法及其衍生方法，等有时间再加以补充。

参考资料

[1] https://yq.aliyun.com/articles/616375
[2] 史春奇等著. 机器学习算法背后的理论与优化. 北京:清华大学出版社,2019
[3] 肖智清著. 神经网络与PyTorch实战. 北京：机械工业出版社, 2018
[4] Ian Goodfellow 等著, 赵申剑等译, 深度学习. 北京：人民邮电出版社, 2017

岂曰无衣？与子同袍。王于兴师，修我戈矛，与子同仇！——《诗经·秦风》

深度学习（一）：优化方法

一、梯度下降

1.1、基本思想

1.2、算法缺陷

1.3、SGD

关于SGD收敛性的证明和分析

二、改进型算法

2.1、Momentum Optimizer

2.2 Nesterov Accelarated Gradient

2.3、AdaGrad Optimizer

2.4、RMSProp

2.5、Adam

三、总结与实践

参考资料

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

深度学习-推荐系统-CV-NLP

深度学习与神经网络

深度学习·神经网络·计算机视觉