2020-04-25

Optimization Method in DL

SGD

$$
\theta_{t+1,i} = \theta_{t,i} - \eta·g_{t,i}
$$

• 缺点：

  • SGD 最大的缺点是下降速度慢。

  • 可能会在沟壑（“盆地”）的两边持续震荡，停留在一个局部最优点，可能无法从中出来，也就无法继续优化。（所以需要细心的初始化参数）。

  • 遇到“鞍点/平原”，可能停止更新（梯度都是 $ 0 $）。

  • 受初始化影响比较大（初始化不好，可能会遇到“盆地/鞍点/平原”）。

SGD-Momentum

• 在鞍点处的梯度为 $ 0 $，但不是极小点，SGD 此时停留在这里，网络不再学习。为了解决这个问题，想到：可以保留之前一步（不是累计）的更新方向，再用当前的更新方向对其进行微调，这就出现了 SGD-Momentum （动量可以理解为之前的梯度的加权累计）。

• 受到物理学中的动量的启发：之前的梯度可以作为当前梯度的参考。所以，参数的更新不再只是当前的梯度，而是 当前的梯度 对 之前累积的梯度 进行微调之后得到的梯度。更新公式如下：

$$
\begin{align*}
\begin{split}
m_t &= \gamma \cdot m_{t-1} + \nabla_\theta J( \theta) \\
\theta_{t+1} &= \theta_{t} - \eta \cdot m_t
\end{split}
\end{align*}
$$

其中 $γ$ 为动量参数，$η$ 为学习率。

def momentum(x_start, step, g, discount = 0.7):   
    x = np.array(x_start, dtype='float64')
    pre_grad = np.zeros_like(x)
    for i in range(50):
        grad = g(x)
        pre_grad = pre_grad * discount + grad
        x -= pre_grad * step
        
        print '[ Epoch {0} ] grad = {1}, x = {2}'.format(i, grad, x)
        if abs(sum(grad)) < 1e-6:
            break;
    return x

• 优点：

  • 跳出 “盆地/平原/鞍点”。

  • 加速收敛

    • 如果参数的某些维度的梯度方向变化不大，那么动量将一直在同一个方向上累积，可以加速更新。

  • 减小震荡

    • 如果参数的某些维度的梯度方向变化较大，那么之前累计的动量可以（适当的）中和这种变化，从而减少梯度方向变化较大的维度上的更新幅度。

• 注意：

  • lr 越小越稳定。太大了很难收敛到最小值上，但是太小的话收敛就太慢了。

  • 动量参数不能太小，0.9 以上表现比较好，但是又不能太大，太大了无法停留在最小值处。

NAG (Nesterov Accelerated Gradient)

• SGD-Momentum 中，之前积累的动量并没有直接改变当前的梯度，Nesterov 的改进就是让之前的动量直接影响当前的动量。这样做的好处是：。更新公式如下：

$$

\begin{align*}
\begin{split}
m_t &= \gamma \cdot m_{t-1} + \nabla_\theta J(\theta_{t} - \eta \cdot m_{t-1}) \\
\theta_{t+1} &= \theta_{t} - \eta \cdot m_t
\end{split}
\end{align*}

$$

• 步骤

  • 先用之前积累的动量更新参数。

  • 用 更新过的参数的梯度 和 之前积累的梯度（就是动量），进行 SGD-Momentum

• Nesterov 项在梯度更新时做出校正，避免前进太快，同时提高灵敏度。(路遥知马力——Momentum)

def nesterov(x_start, step, g, discount = 0.7):   
    x = np.array(x_start, dtype='float64')
    pre_grad = np.zeros_like(x)
    for i in range(50):
        x_future = x - step * discount * pre_grad
        grad = g(x_future)
        pre_grad = pre_grad * 0.7 + grad 
        x -= pre_grad * step

        print '[ Epoch {0} ] grad = {1}, x = {2}'.format(i, grad, x)
        if abs(sum(grad)) < 1e-6:
            break;
    return x
nesterov([150,75], 0.012, g)

• 优点：更快的收敛速度。

  • 原因：利用了目标函数二阶导的信息。

• 结论：在原始形式中，Nesterov Accelerated Gradient（NAG）算法相对于 Momentum 的改进在于，以“向前看”看到的梯度而不是当前位置梯度去更新。经过变换之后的等效形式中，NAG 算法相对于 Momentum 多了一个本次梯度相对上次梯度的变化量，这个变化量本质上是对目标函数二阶导的近似。由于利用了二阶导的信息，NAG 算法才会比 Momentum 具有更快的收敛速度。比Momentum更快：揭开Nesterov Accelerated Gradient的真面目

• 参考

  • Gradient Descent With Momentum - Mark Chang’s Blog

AdaGrad

• 二阶动量：该维度上，迄今为止所有梯度值的平方和。

• 并没有使用 Momentum，只是对学习率进行了缩放。在 Adagrad 的更新规则中，学习率 η 会随着每次迭代而根据历史梯度的变化而变化。

$$
\begin{align*}
\begin{split}
v_t &= v_{t-1} + g_{t,i}^2 \\
\theta_{t+1,i} &= \theta_{t,i} - \frac{\eta}{\sqrt{v_t+\epsilon}}·g_{t,i}
\end{split}
\end{align*}
$$

$ v_t \in {\Bbb R}^{d \times d} $ 是一个对角矩阵，每个对角线位置 $i,i$ 的值累加到 $t$ 次迭代的对应参数 $θ_i$ 梯度平方和。$\epsilon$ 是平滑项，防止除零操作，一般取值 $1e−8$ 。为什么分母要进行平方根的原因是去掉平方根操作算法的表现会大打折扣。

• 分母作为 Regularizer 项的工作机制如下：

  • 训练前期，梯度较小，使得 Regularizer 项很大，放大梯度。（对于偶尔更新的参数，我们了解的信息太少，希望能从每个偶然出现的样本身上多学一些，即学习速率大一些。）

  • 训练后期，梯度较大，使得 Regularizer 项很小，缩小梯度。（对于经常更新的参数，我们已经积累了大量关于它的知识，不希望被单个样本影响太大，希望学习速率慢一些。）

• 另外，由于 Regularizer 是专门针对 Gradient 的，所以有利于解决 Gradient Vanish/Expoloding 问题。所以在深度神经网络中使用会非常不错。

• 当然，AdaGrad 本身有不少缺陷：

  • 初始化 $W$ 影响初始化梯度，初始化 $W$ 过大，会导致初始梯度被惩罚得很小。此时可以人工加大 $η$ 的值，但过大的 $η$ 会使得 Regularizer 过于敏感，调节幅度很大。

  • 训练到中后期，递推路径上累加的梯度平方和越大越多，迅速使得 Gradinet 被惩罚逼近 $0$ ，提前结束训练。

RMSprop

与 AdaGrad 只有一处不同：不是简单的计算之前不同迭代步骤的梯度平方和，而是计算：上一个时刻的加权平均和 和 这个时刻的梯度平方和 的 加权和。（这一点和 Adadelta 很像：不累积全部历史梯度，而只关注过去一段时间窗口的下降梯度。(Adam那么棒，为什么还对SGD念念不忘 (1) —— 一个框架看懂优化算法）

$$
\begin{align*}
\begin{split}
v_t &= \gamma \cdot v_{t-1} + (1 -\gamma) \cdot g_{t,i}^2 \\
\theta_{t+1,i} &= \theta_{t,i} - \frac{\eta}{\sqrt{v_t+\epsilon}}·g_{t,i}
\end{split}
\end{align*}
$$

所以，当 $ g{t,i}^2 < v{t-1} $ 的时候，$ v_t $ 将变小，这样就不会出现 AdaGrad 中 $ v_t $ 持续变大，导致后来无法学习的现象。

• 【优化算法】一文搞懂RMSProp优化算法

• optimization - Adadelta idea 1 vs RMSprop - Cross Validated

Adadelta

AdaDelta 解決了 AdaGrad 會發生的兩個問題：

(1) Learning Rate 只會隨著時間而一直遞減下去

(2) \triangle x 與 x 的單位不同

更新公式：

$$
\begin{align*}
\begin{split}
\theta_{t+1} &= \theta_t + \triangle\theta_t \\
&= \theta_t - \frac{RMS[\triangle \theta]_{t-1}}{RMS[g]_t} \cdot g_t \\
RMS[g]_t &= \sqrt{E[g^2]_t + \epsilon} \\
RMS[\triangle \theta]_t &= \sqrt{E[\triangle \theta^2]_t + \epsilon} \\
E[g^2]_t &= \gamma \cdot E[g^2]_{t-1} + (1-\gamma) \cdot g^2_t \\
E[\triangle\theta_t^2]_t &= \gamma \cdot E[\triangle\theta_t^2]_{t-1} + (1-\gamma) \cdot \triangle\theta_t^2
\end{split}
\end{align*}
$$

• 特点

  • Adadelta 只累加固定大小的项，并且也不直接存储这些项，仅仅是近似计算对应的平均值

  • 不需要设置初始学习率

  • 训练初中期，加速效果不错，很快

  • 训练后期，反复在局部最小值附近抖动

• 参考

  • AdaDelta - Mark Chang’s Blog

  • Optimization Method — AdaDelta « MARK CHANG’S BLOG

  • 梯度下降算法中的Adagrad和Adadelta

  • [1212.5701v1] ADADELTA: An Adaptive Learning Rate Method

Adam (Adaptive Moments)

引入 momentum 。

$$
\begin{align*}
\begin{split}
m_t &= beta_1 * m_{t-1} + (1 - beta_1) * g \\
m_t &= m_t / (1-beta1^t) \\
v_t &= beta_2 * v_{t-1} + (1 - beta_2) * g^2 \\
v_t &= v_t / (1-beta2^t) \\
x_{t+1} &= x_t - lr_t * m_t / (\sqrt{v_t} + \epsilon) \\
\end{split}
\end{align*}
$$

在初期 $m_t = 0, v_t=0$ ，这个估计是有问题的。因此需要进行误差修正。

其它

Adadelta, RMSProp, Adam 由于使用的是过去二阶动量的加权平均和，所以不能保证学习率单调递减，如果数据变化比较大，会出现学习率一会大，一会小的现象，导致学习很不稳定。这也是 Adam 被批评的一个原因。（不过很多文献中指出：Adam 最后的步长往往不是过大而是过小了。事实上，[3] 中的实验也证明了 Adam 训练末期过小的步长是导致泛化性能差的重要原因。Adam 究竟还有什么问题 —— 深度学习优化算法概览(二)）

参考

• CS231n Convolutional Neural Networks for Visual Recognition

• 卷积神经网络中的优化算法比较 | Memo

• Adam那么棒，为什么还对SGD念念不忘 (1) —— 一个框架看懂优化算法

• Adam 究竟还有什么问题 —— 深度学习优化算法概览(二)

• 梯度下降优化算法概述 · Lee’s Space Station

• 深度学习最全优化方法总结比较（SGD，Adagrad，Adadelta，Adam，Adamax，Nadam）

• An overview of gradient descent optimization algorithms

• 深度学习中5种最优化算法的可视化与理解

• adadelta算法 - Google 搜索

• [Optimization]Deep Learning中的梯度下降优化算法

Related

• Initialization in DL

• Normalization in DL

Deep Learning