梯度下降与优化方法(BGD & SGD & Momentum & AdaGrad & RMSProp & Adam)

SGD

SGD指stochastic gradient descent,即随机梯度下降。是梯度下降的batch版本。

对于训练数据集,我们首先将其分成n个batch,每个batch包含m个样本。我们每次更新都利用一个batch的数据,而非整个训练集。即:

$$ x_{t+1}=x_{t}+\Delta x_{t} $$

$$\Delta x_{t}=-\eta g_{t} $$

其中,η为学习率,gt为x在t时刻的梯度。
这么做的好处在于:

当训练数据太多时,利用整个数据集更新往往时间上不显示。batch的方法可以减少机器的压力,并且可以更快地收敛。
当训练集有很多冗余时(类似的样本出现多次),batch方法收敛更快。以一个极端情况为例,若训练集前一半和后一半梯度相同。那么如果前一半作为一个batch,后一半作为另一个batch,那么在一次遍历训练集时,batch的方法向最优解前进两个step,而整体的方法只前进一个step。

Momentum

SGD方法的一个缺点是,其更新方向完全依赖于当前的batch,因而其更新十分不稳定。解决这一问题的一个简单的做法便是引入momentum。

momentum即动量,它模拟的是物体运动时的惯性,即更新的时候在一定程度上保留之前更新的方向,同时利用当前batch的梯度微调最终的更新方向。这样一来,可以在一定程度上增加稳定性,从而学习地更快,并且还有一定摆脱局部最优的能力:

$$\Delta x_{t}=\rho \Delta x_{t-1} – \eta g_{t} $$

其中,ρ 即momentum,表示要在多大程度上保留原来的更新方向,这个值在0-1之间,在训练开始时,由于梯度可能会很大,所以初始值一般选为0.5;当梯度不那么大时,改为0.9。η 是学习率,即当前batch的梯度多大程度上影响最终更新方向,跟普通的SGD含义相同。ρ 与 η 之和不一定为1。

“冲量”这个概念源自于物理中的力学,表示力对时间的积累效应。

在普通的梯度下降法x += v中,每次x的更新量v为v = – dx * lr,其中dx为目标函数func(x)对x的一阶导数。
当使用冲量时,则把每次x的更新量v考虑为本次的梯度下降量- dx * lr与上次x的更新量v乘上一个介于[0, 1]的因子momentum的和,即v = – dx * lr + v * momemtum。
从公式上可看出:

当本次梯度下降- dx * lr的方向与上次更新量v的方向相同时,上次的更新量能够对本次的搜索起到一个正向加速的作用。
当本次梯度下降- dx * lr的方向与上次更新量v的方向相反时,上次的更新量能够对本次的搜索起到一个减速的作用。

Nesterov Momentum

这是对传统momentum方法的一项改进,由Ilya Sutskever(2012 unpublished)在Nesterov工作的启发下提出的。

其基本思路如下图(转自Hinton的coursera公开课lecture 6a):
《梯度下降与优化方法(BGD & SGD & Momentum & AdaGrad & RMSProp & Adam)》
首先,按照原来的更新方向更新一步(棕色线),然后在该位置计算梯度值(红色线),然后用这个梯度值修正最终的更新方向(绿色线)。上图中描述了两步的更新示意图,其中蓝色线是标准momentum更新路径。

公式描述为:
$$\Delta x_{t}=\rho \Delta x_{t-1} – \eta \Delta f(x_{t} + \rho \Delta x_{t-1})$$

Adagrad

上面提到的方法对于所有参数都使用了同一个更新速率。但是同一个更新速率不一定适合所有参数。比如有的参数可能已经到了仅需要微调的阶段,但又有些参数由于对应样本少等原因,还需要较大幅度的调动。

Adagrad就是针对这一问题提出的,自适应地为各个参数分配不同学习率的算法。其公式如下:
$$\Delta x_{t}= – \frac{\eta}{\sqrt{\sum_{\tau=1}^t{g_{\tau}^2}+\epsilon}}g_t$$
其中gt 同样是当前的梯度,连加和开根号都是元素级别的运算。eta 是初始学习率,由于之后会自动调整学习率,所以初始值就不像之前的算法那样重要了。而ϵ是一个比较小的数,用来保证分母非0。

其含义是,对于每个参数,随着其更新的总距离增多,其学习速率也随之变慢。

Adadelta

Adagrad算法存在三个问题

其学习率是单调递减的,训练后期学习率非常小
其需要手工设置一个全局的初始学习率
更新xt时,左右两边的单位不同一
Adadelta针对上述三个问题提出了比较漂亮的解决方案。

首先,针对第一个问题,我们可以只使用adagrad的分母中的累计项离当前时间点比较近的项,如下式:
$$E[g^2]t = \rho E[g^2]{t-1} + (1-\rho)g^2_t$$
$$\Delta x_t = – \frac{\eta}{\sqrt{E[g^2]_t+\epsilon}}g_t$$

这里ρ是衰减系数,通过这个衰减系数,我们令每一个时刻的$g_t$随之时间按照ρ指数衰减,这样就相当于我们仅使用离当前时刻比较近的$g_t$信息,从而使得还很长时间之后,参数仍然可以得到更新。
针对第三个问题,其实sgd跟momentum系列的方法也有单位不统一的问题。sgd、momentum系列方法中:
$$\Delta x 的单位 \propto g的单位 \propto \frac{\partial f}{\partial x} \propto \frac{1}{x的单位}$$
类似的,adagrad中,用于更新Δx的单位也不是x的单位,而是1。
而对于牛顿迭代法:
$$\Delta x = H^{-1}_t g_t$$
其中H为Hessian矩阵,由于其计算量巨大,因而实际中不常使用。其单位为:
$$\Delta x \propto H^{-1}g \propto \frac{\frac{\partial f}{\partial x}}{\frac{\partial ^2 f}{\partial ^2 x}} \propto x的单位$$

注意,这里f无单位。因而,牛顿迭代法的单位是正确的。
所以,我们可以模拟牛顿迭代法来得到正确的单位。注意到:
$$\Delta x = \frac{\frac{\partial f}{\partial x}}{\frac{\partial ^2 f}{\partial ^2 x}} \Rightarrow \frac{1}{\frac{\partial ^2 f}{\partial ^2 x}} = \frac{\Delta x}{\frac{\partial f}{\partial x}}
$$

这里,在解决学习率单调递减的问题的方案中,分母已经是$\frac{\partial f}{\partial x}$的一个近似了。这里我们可以构造Δx的近似,来模拟得到$H_{−1}$的近似,从而得到近似的牛顿迭代法。具体做法如下:
$$\Delta x_t = – \frac{\sqrt{E[\Delta x^2]_{t-1}}}{\sqrt{E[g^2]_t+\epsilon}}g_t$$
可以看到,如此一来adagrad中分子部分需要人工设置的初始学习率也消失了,从而顺带解决了上述的第二个问题。

tensorflow 中相关的类

《梯度下降与优化方法(BGD & SGD & Momentum & AdaGrad & RMSProp & Adam)》

参考文献

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注