常见优化算法 PART 1

梯度下降法

根据泰勒级数的定义：
$$ f(x + \Delta x) = f(x) + f'(x) \Delta x + {f^{(2)}(x) \over 2} \Delta x^2 + O(\Delta x^3) $$
如果将自变量x沿着方向D移动步长$\eta$后变为$x+\eta D$，由一阶泰勒公式展开式可得：
$$ f(x + \eta D) = f(x) + f'(x) \eta D $$
为了找到函数$f(x)$的最小值，我们希望x的本次移动能够使得目标函数$f(x)$减小的尽可能多，也即在给定步长$\eta$后我们希望：
$$ max_D\{ f(x) - f(x + \eta D) = -f'(x) \eta D\} $$
等式右边的$ -f'(x) D$表示函数在x处的负梯度与移动方向D的乘积，为了使得这两个向量的乘积最大，需要让D等于负梯度$ -f'(x) D$方向，加上步长$\eta$，x需要沿着负梯度的方向前进：
$$ x^{(t+1)} = x^{(t)} - \eta f'(x^{(t)}) $$
这便是最原始的梯度下降法的更新公式，它存在如下几处劣势[10]：

其中步长$\eta$的选择十分关键，步长太短，收敛速度十分慢；步长太大，则收敛到极小值附近时容易出现振荡甚至无法收敛(diverge)；
第一个缺点的一种解决方案是应用退火算法等 learning rate schedule 来调整训练过程中的学习率，但是这种方法需要事先确定特定的learning rate schedule，无法自适应不同的数据集特性（比如稀疏性数据等）；
它对所有的参数设置相同的学习率，而我们希望对于出现频次比较低的特征每次更新的幅度大一些；
对于非凸函数容易陷入局部极小值或者鞍点（该点处任何维度上的梯度均接近0）处。

上图表示的是SGD算法在靠近最优值附近时所产生的振荡现象。其中椭圆线表示目标函数在参数空间的等高线，中心位置是最优值位置，蓝色折线为SGD优化时参数的变化路径，因为任何一点的负梯度方向必垂直于经过该点等高线在此处的切线方向，导致这里的负梯度方向在红色轴上的分量几乎为0，因此导致往最优值处的移动速度非常缓慢。

梯度下降算法一般不直接用在机器学习或深度学习的模型优化上，因为它首先是求出每个训练样本给目标函数带来的负梯度值，然后求出梯度平均值用于模型参数的更新，这带来的问题是模型更新的速度很缓慢，为了解决这个问题，出现了在 mini-batch 的SGD算法，它每次取全部训练数据集中的一个mini-batch的平均梯度值用于模型参数更新。

动量项

对于优化问题$min J(\theta)$原始的梯度下降法迭代更新的公式为：
$$ v_t = \eta \nabla_{\theta} J(\theta) \\ \theta = \theta - v_t $$
动量项从步伐 $v_t$上下手，它的思想是：如果当前的梯度方向$v_t$与上一次的梯度方向$v_{t-1}$相同，则加大步伐；如果相反，则缩小步伐。它的出发点是期望减小SGD收敛过程的振荡现象从而加快收敛：
$$ \begin{align} & v_1 = \eta \nabla_{\theta} J(\theta_0) \\ & v_t = \gamma v_{t-1} + \eta \nabla_{\theta} J(\theta_{t-1}) \\ & \theta = \theta - v_t \end{align} $$
如果我们将上面的$v_t$全部展开，则为：
$$ \begin{align} v_{t} &= \eta \sum_{i=0}^{t-1} \gamma^{i} \nabla J(\theta_{k-1-i}) \\ & = \eta (\gamma^{0} \nabla J(\theta_{t-1}) + \gamma^{1} \nabla J(\theta_{t-2}) + \dots + \gamma^{t-2} \nabla J(\theta_1) + \gamma^{t-1} \nabla J(\theta_0)) \end{align} $$
因此，实际上$v_t$是对所有历史梯度值$\nabla J(\theta_i), i = t-1, t-2, \ldots, 1, 0$的线性组合，组合权重为:

$\eta (\gamma^{0}, \gamma^{1}, \dots, \gamma^{t-1})$

因为因子$\gamma \in (0, 1)$，因此随着更新次数$t$的增加，过去的梯度值$\nabla J(\theta_i)$对$v_t$的影响以指数级的方式递减。

对比上图[3]中momentum下和上一节SGD下参数的更新路径可以发现，由于$v_{t-1}$的作用，使跟SGD相比，更新幅度$v_t$减小，且更新方向与最优目标方向逐渐接近（参见下一节中momentum的作用示意图），减小了振荡现象，加快了收敛速度。

Nesterov加速

Nesterov是动量项方法的变体，它们的区别[3]在于：

The standard momentum method first computes the gradient at the current location and then takes a big jump in the direction of the updated accumulated gradient;
Nesterov first make a big jump in the direction of the previous accumulated gradient. Then measure the gradient where you end up and make a correction.

它在动量项的基础上，用$\theta_{t-1} - \gamma v_{t-1}$替代了原始动量项中的$\theta_{t-1}$，如果该估计点的梯度$\nabla_{\theta} J(\theta_{t-1} - \gamma v_{t-1}) $与之前的$v_{t-1}$方向相反，则当前步长$v_t$会被压缩，它的出发点依然是是希望函数在接近最小值时减小振荡，不同的地方在于Nesterov事先估计后一步的梯度方向，避免犯错后纠正：
$$ \begin{align} & \theta_{t-1} = \theta_{t-2} - v_{t-1} \\ & v_t = \gamma v_{t-1} + \eta \nabla_{\theta} J(\theta_{t-1} - \gamma v_{t-1}) \\ & \theta_t = \theta_{t-1} - v_t \end{align} $$
结合下图来理解上面的更新公式：我们现在站在$\theta_1$这个位置，在动量项方法中，我们综合考虑之前的更新方向$v_{t-1}$和当前位置的梯度方向$ \nabla_{\theta} J(\theta_1)$，然后决定本次更新的幅度$v_t$，而Nesterov加速法则按照之前的更新方向$v_{t-1}$再往前探一探，如果探测的结果$\nabla_{\theta} J(\theta_1 - \gamma v_{t-1})$与上一次的更新方向相反，则减小当前的更新力度。

两种更新方式的对比如下图所示：

Adagrad

Adagrad的出发点是：它为每个参数自动计算不同的学习率，使得频繁出现的参数的每次更新幅度小一些，而不频繁出现的参数的每次更新幅度大一些，它适合用在稀疏数据的模型优化上，更新公式为：
$$ \theta_{t+1,i} = \theta_{t,i} - {\eta \over {\sqrt{\epsilon + \sum_{k=1}^t g_{k, i}^2}}} g_{t,i} $$
其中$\theta_{t,i}$表示参数向量$\theta$中第$i$个参数分量在$t$时刻的值，$g_{k,i}$记录的是第$k$次迭代时梯度在第$i$个参数分量上的取值：

$g_{k} = \nabla_{\theta} J(\theta_{k}), \; k = 1,2, \ldots, t$ $\epsilon$是为了保证分母部分不为0，因此一般取一个很小的非零值即可。对于参数向量中每个参数分量$\theta_{t,i}$更新时，当前梯度在对应梯度分量上的取值$g_{t,i}$除了需要乘上一个学习率$\eta$之外，还需要除以**对应参数分量的历史梯度分量平方的累加值** $ \sum_{k=1}^t g_{k, i}^2$，以保证对不同出现频率的特征给予不同的学习率。Adagrad方法最大的缺点在于：分母部分的$g_{k, i}^2$因为始终是非负数，随着迭代次数的增加，其累计和可能会越来越大，从而导致更新幅度接近于0，导致参数收敛缓慢。 ## RMSprop法上一节说到，Adagrad中分母部分的$g_{k, i}^2$因为始终是非负数，随着迭代次数的增加，其累计和可能会越来越大，从而导致参数更新幅度很小，RMSprop法的**出发点**正是为了解决这个问题，它在对$g_{k, i}^2$进行累加时乘上了一个小于1的系数，更新公式如下： $$ \begin{align} & E[g^2]_{t,i} = \gamma E[g^2]_{t-1,i} + (1 - \gamma)g^2_{t,i} \\ & \theta_{t+1,i} = \theta_{t,i} - {\eta \over {\sqrt{\epsilon +E[g^2]_{t,i}}}} g_{t,i} \end{align} $$

参数$\gamma$一般取0.9，这样当前的梯度影响$(1 - \gamma)g^2_{t,i}$对分母部分改变的比较小，从而减缓分母增大的速度，但是初始学习率$\eta$的选择仍然很关键。RMSprop算法适合于优化在线和非平稳目标 （指目标分布随时间而变化的分布[7][8]），比如RNN类网络结构的训练。

AdaDelta

AdaDelta的出发点是希望改善AdaGrad方法存在的两个缺点[6]：

… ADAGRAD, this method can be sensitive to initial conditions of the parameters and the corresponding gradients. If the initial gradients are large, the learning rates will be low for the remainder of training. This can be combated by increasing the global learning rate, making the ADAGRAD method sensitive to the choice of learning rate. Also, due to the continual accumulation of squared gradients in the denominator, the learning rate will continue to decrease throughout training, eventually decreasing to zero and stopping training completely.

总结来看就是：初始全局学习率$\eta$的选择问题和随着更新次数的增加，分母部分累加项会越来越大，从而整体学习率接近于0，造成参数更新缓慢。

为了改善这两点，AdaDelta分别引入了两个思路[6]：

1、Accumulate Over Window
不像AdaGrad中对所有历史（包括当前的）梯度值累加，AdaDelta只考虑过去$w$大小窗口内的历史梯度值，从而避免累加梯度值递增。又考虑到存储前$w$个历史梯度值的效率问题，因此用 exponentially decaying average of the squared gradients方法来实现，具体为对当前的梯度值平方$g^2_t$和过去的梯度值平方$ \mathrm{E}[g^2]_{t-1}$进行一个加权求和：
$$ \mathrm{E}[g^2]_t = \rho \mathrm{E}[g^2]_{t-1} + (1 – \rho) g^2_t $$

2、Correct Units with Hessian Approximation
$$ \Delta x_t = -\frac{\sqrt{\mathrm{E}[\Delta x^2]_{t-1} + \epsilon}}{\sqrt{\mathrm{E}[g^2]_{t} + \epsilon}} g_t $$
其中$ \mathrm{E}[\Delta x^2]_t = \rho \mathrm{E}[\Delta x^2]_{t-1} + (1 – \rho) \Delta x^2_t$。

完整的AdaDelta算法流程为[6]：

相比于之前的算法，AdaDelta算法具有如下优点[6]：

不需要手动设置全局学习率$\eta$;
每个参数分量独立的计算动态的自适应学习率；
对于大梯度值、数据噪声、模型结构的选择具有较好的鲁棒性；
对于模型超参数的选择不敏感；
能够同时应用于本机或分布式计算；

梯度下降法

动量项

Nesterov加速

Adagrad

AdaDelta

参考文献