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

卷积神经网络一般力求能够做到 end to end 的训练, end to end 训练也是目前深度学习的主流. 训练中主要采用 Back Propagation 算法, 而 BP 算法是我们早就学过的梯度下降算法的一种实现. 因此, CNN 中的各种优化算法还是在梯度下降算法上面做手脚. 在目前各种主流的深度学习工具中也都内置了各种常见的优化算法. 然而, 把优化算法封装到黑盒中直接使用不利于对于问题的理解和更准确地找到好的优化方向. 这篇文章的主要目的是总结和比较深度学习中各种常用的优化算法. 希望能对神经网络的优化起到一点点帮助, 探究一下黑盒中的内容.

Batch Gradient Descent

这种方法就是我们从高数中学到的方法, 其方法可以描述为, 使用我们拿到的所有的数据计算梯度, 然后使用这个梯度对参数进行更新. 在凸函数中, 只要学习率足够小, 肯定能够找到全局最优点, 在非凸函数中也可以保证找到局部最优.
\[ \theta=\theta - \eta \cdot \nabla_{\theta}J\left(\theta\right) \]

1
2
# Vanilla Batch Gradient Descent
x += -learning_rate * dx

缺点:

  1. 训练数据太多的时候无法全部放入内存
  2. 训练数据多的时候计算梯度的时间非常久
  3. 无法进行 online 的更新

优点:

  1. 方法简单
  2. 能够保证收敛到全局最优值(凸函数)/局部最优值(非凸函数)

Stochastic Gradient Descent

和 Batch Gradient Descent 相反, SGD 又走入了另外一个极端, SGD 拿到一个数据之后, 马上计算梯度, 然后对参数进行更新.
\[ \theta = \theta - \eta \cdot J\left(\theta; x^{\left(i\right)}, y^{\left(i\right)}\right) \]

1
2
# SGD
x += - learning_rate * dx

缺点:

  1. 无法利用矩阵操作加速计算过程

优点:

  1. 收敛速度快(因为在Batch 的方法中, 每次计算梯度会计算很多相似的样本得到的梯度, 这部分是冗余的)
  2. 可以 online 更新
  3. 有可能逃出一个比较差的局部最优而收敛到一个更好的局部最优甚至是全局最优

Mini-batch Gradient Descent

Mini-batch 的方法是在上述两个方法中取了个折衷, 每次从全部的熟练数据中取一个 mini-batch 的数据计算
\[ \theta = \theta - \eta \cdot J\left(\theta; x^{\left(i:i+n\right)}, y^{\left(i:i+n\right)}\right) \]
目前, mini-batch 的方法是深度学习中主流方法, 各种深度学习工具默认也是这种方法. 也可以把上述两种方法看成是 mini-batch 的特例, Batch 的方法, 就是 mini-batch size 是整个数据集, SGD 方法就是 min-batch=1 的情况.

目前遇到的问题

上述 3 各方法遇到的问题是:

  1. 如何选择一个合适的 learning rate 是非常困难的
  2. 目前有一些通过 schedule 的方式来设置 learning rate 的方法, 即预先设计好计算了一定数量的迭代之后减小 learning rate, 但是, 由于是在训练之前就要设置好, 因此, 无法根据训练时的时间情况进行调整. 实践中也证明这种 schedule 的方法非常不可靠.
  3. 上述方法中, 对于每一个参数的 learning rate 都是相同的, 这种做法是不合理的. 试想, 如果训练数据是稀疏的, 而且, 特征数据出现的频率变化很大, 那么, 比较合理的做法是, 对于出现频率低的特征设置较大的学习速率, 对于出现频率较大的特征数据设置较小的学习速率.
  4. 近期的的研究表明, 深层神经网络之所以比较难训练, 并不是因为容易进入 local minimum, 相反, 由于网络结构非常复杂, 在绝大多数情况下, 即使是 local minimum 也可以得到非常好的结果. 而之所以难训练是因为学习过程容易陷入到马鞍面中, 即在坡面上, 一部分点是上升的, 一部分点是下降的. 而这种情况比较容易出现在平坦区域, 在这种区域中, 所有方向的梯度值都几乎是 0.

Momentum

Momentum update 是一种加快收敛速度的方法(注意, 这里说的不是计算速度). 这个方法来自于物理中的启发. loss function 看做是一座山, 对于参数的初始化看做是在这个山坡上面随机放一个小球. 这个小球的初始速度为 0, 其相对于地面(或者更严格的说是山谷, 也是Loss Function 优化过程中的局部最优点)的势能为 \(U=mgh\), 其中, \(m\) 是小球的质量, \(g\) 是重力加速度, h 是小球的位置相对于山谷最低点的高度. 因为 \(m\) 和 \(g\) 都是常数, 因此, 势能正比与高度 \(h\). 优化过程看以看做是模拟这个小球在山坡上的状态. 小球来自于地球引力的受力为 \(F=mg\), 而这恰好是 Loss Function 的梯度. 另外一方面, 小球的整体受力为 \(F=ma, a \ne g\), 因为其中还有摩擦力等其它因素.
\[ \begin{align} v_t & = \gamma v_{t-1} + \eta \cdot \nabla_{\theta}J\left(\theta\right) \cr \theta & = \theta - v_t &\end{align} \]

1
2
3
# Momentum update
v = mu * v - learning_rate * dx # integrate velocity
x += v # integrate position

这里的变量 mu 就是我们在各种深度学习框架中/论文中见到的 momentum. 一般设置为 0.9, 0.99 等. 然而, 把 mu 理解为摩擦(或者加上其它的因素)更好. mu 的作用是在小球在山坡上滚动的过程中来降低小球的动能. 否则, 如果没有这个因素, 那么, 小球永远不会停下来, 优化过程也永远不会停止.

Nesterov Momentum

在小球向下滚动的过程中, 我们希望小球能够提前知道在哪些地方坡面会上升, 这样, 在遇到上升坡面之前, 小球就开始减速. 这方方法就是 Nesterov Momentum. 是最近比较流行的一种与传统的 Momentum 稍有不同的方法, Nesterov Momentum 在凸优化中有较强的理论保证收敛, 并且,在实践中, Nesterov Momentum也比单纯的 Momentum 的效果要好. 核心思想是: 注意到 momentum 方法, 如果只看 mu * v 项, 那么, 当前的 x 经过 momentum 的作用会变成 x+ mu*v. 因此, 可以把 x+ mu*v 这个位置看做是当前优化的一个”展望”位置, 所以, 可以在 x+ mu*v 求导, 而不是原始的 x


1
2
3
4
x_ahead = x + mu * v
# evaluate dx_ahead (the gradient at x_ahead instead of at x)
v = mu * v - learning_rate * dx_ahead
x += v

Learning Rate 设置方法

在优化的过程中, 如果学习率设置的过大, 那么, 小球就会在山谷之间跳来跳去, 无法到达最低点, 如果是非常缓慢地降低学习速率, 那么, 虽然小球跳来跳去的现象会有缓解, 但是, 效果不明显, 浪费了计算资源, 而如果快速降低学习速率, 那么, 小球可能会很快到达一个(不是那么好的)局部最优点, 而不能到达一个更好的局部最优点. 通常, 在实验中有下面三种方法:

Step decay 每隔几个epoch减少一次learning rate, 一般是每运行5个epoch左右把learning rate减少一半, 或者是每隔20个epoch减少为原来的1/10. 然而,具体的learning rate 的调整方法还是要看网络的设计和模型. 另外, 还有一种方法是, 在训练的过程中观察training error和validation error, 当validation error不再减小的时候, 减小learning rate.

Exponential decay 的数学描述是 \(\alpha=\alpha_0e^{-kt}\), 其中 \(\alpha_0,k\) 是超参数, \(t\) 是迭代次数.

1/t decay 的数学描述是\(\alpha=\frac{\alpha_0}{1+kt}\) 其中 \((\alpha_0,k\)) 是超参数, \(t\) 是迭代次数.

PS: 我一般使用第一种方法.

逐个调整参数

上面讨论过的所有的方法都是所有的参数都使用相同的调整策略. 调整学习率的代价一般比较高, 因此, 有许多研究还是如何自动调学习率, 甚至是调整每一个需要优化的参数的学习率. 在这些方法中往往会引入更多的超参数, 但是, 这些方法对超参数的设置并不是那么敏感, 因此, 总会比上面讨论过的调整学习率的方法要好用.

AdaGrad

AdaGrad 会在学习的过程中自动调整 learning rate, 对于出现频率低的参数使用较大的 learning rate, 出现频率高的参数使用较小的 learning rate. 因此, 这种方法对于训练数据比较稀疏的情况比较适用. AdaGrad 可以提高 SGD 的鲁棒性.
AdaGrad 实现上述目的的方法是对于各个参数, 使用其当前累积的梯度去 normalize 当前的学习速率.
为了方便表示累积梯度, 把梯度记为:
\[ g_{t,i} = \nabla_{\theta} J\left(\theta_i\right) \]
相应地, 原始参数更新的过程变为:
\[ \theta_{t+1, i} = \theta_{t,i} - \eta \cdot g_{t,i} \]
考虑到使用累积梯度去 normalize learning rate, 则上述参数更新过程变为:
\[ \theta_{t+1, i} = \theta_{t,i} - \frac{\eta}{\sqrt{G_{t,ii}+\epsilon}} \cdot g_{t,i} \]

1
2
3
# Assume the gradient dx and parameter vector x
cache += dx**2
x += - learning_rate * dx / (np.sqrt(cache) + eps)

cache 的大小和gradient的大小相同, 记录的是每个参数的梯度的平方和. 之后,cache 用来以 element-wise 的方式 normalize 参数的更新. 从上面的代码中可以看出, 梯度较高的权重的有效 learning rate 会减小, 相应的梯度较低的权重的有效 learning rate 会增大. 这里, 让我感到不解的是, sqrt 操作非常重要,如果没有 sqrt 操作, 该算法的效果非常差. eps 用来避免出现除 0 错误的,一般设置为 \(10^{-4}\) 到 \(10^{-8}\) 之间. (这种方法,在 CNN 中训练中极为常见, 比如在 batch normalization 中也是通过这种方法避免出现除 0 的错误). Adagrad 的缺点是,在深度学习中, 这种方法导致学习率的调整太激进, 因此常常过早结束了学习过程.

AdaDelta

AdaGrad 方法比较激进, 会过早结束优化过程, AdaDelta 的目的就是为了解决这个问题. 在 AdaGrad 中对 learning rate 进行 normalize 的参数是使用之前所有时间得到的梯度的累积, AdaDelta 的思想是通过设置窗口 w, 只使用部分时间的梯度累积.
在实际使用中, 其算法并没有存储前 w 个梯度然后计算, 而是类似与 moving average 的方法. 在任意一个时间 t, 当前的 normalize 的参数是 t-1 时刻的参数和当前的梯度做加权求和.
\[ E\left[g^2\right]_t = \gamma E\left[g^2\right]_{t-1} + \left(1-\gamma\right) g_t^2 \]
现在, 使用 \(E\left[g^2\right]_t\) 去 normalize learning rate
\[ \nabla \theta_t = - \frac{\eta}{\sqrt{E\left[g^2\right]_t+\epsilon}}g_t \]
最终的更新方法为:
\begin{align} \nabla\theta_t & = -\frac{RMS\left[\nabla\theta\right]_{t-1}}{RMS\left[g\right]_t}g_t \cr \theta_{t+1} & = \theta_t + \nabla\theta_t \end{align}
其中, \(RMS[x]_t=\sqrt{E\left[x^2\right]_t+\epsilon}\)
可以看到, 在 AdaDelta 中, 根本不需要设置 learning rate, 因为其自身可以计算learning rate.

RMSProp

RMSProp是一个非常高效的算法, 但是目前并没有发表. Hinton 老爷子果然任性. RMSProp 对 AdaGrad 稍作改进, 是的算法不再像 AdaGrad 那么激进 它使用的是 moving average of squared gradients, 有关 moving average 的相关解释可以参考 batch normalization 的实现说明. 其思想和 AdaDelta 也很像.
\[ \begin{align} E\left[g^2\right]_t & = 0.9E\left[ g^2 \right]_{t-1}+0.1g_t^2 \cr \theta_{t+1} & = \theta_t - \frac{\eta}{\sqrt{E\left[g^2\right]_t+\epsilon}}g_t \end{align} \]

1
2
cache = decay_rate * cache + (1 - decay_rate) * dx**2
x += - learning_rate * dx / (np.sqrt(cache) + eps)

decay_rate 是超参数, 一般可以设置为\(0.9,0.99,0.999\). 其中, x+= 操作和Adagrad完全相同, 但是, 变量cache是leaky的,所以, RMSProp 仍然根据每个权重的gradient来调整learning rate.

Adam

Adam 是最近提出的一种算法, 该算法和(下面将要介绍的)带有momentum的RMSprop比较类似, 过程类似于:

1
2
3
m = beta1*m + (1-beta1)*dx
v = beta2*v + (1-beta2)*(dx**2)
x += - learning_rate * m / (np.sqrt(v) + eps)

该方法和 RMSProp 唯一的区别是 “smooth” 过程, 这里使用的是 m 来做 smooth 操作, 而不是使用原始的 gradient vector dx. 论文中推荐的超参数为 eps=1e-6, bata1=0.9, beta2=0.999, 在实践中, 推荐使用Adam方法. Adam 算法通常会比 RMSProp 算法效果好. 另外,也可以尝试 SGD+Nesterov Momentum. 完整的Adam算法中还包括 bias 的纠正机制, 这是因为,在刚开始的几个steps中,mv 都要初始化, 并且在 warm up 之前他们都 biased at zero. 更多的细节可以参考论文原文.

怎样选择

通过以上分析, 理论上可以说, 在数据比较稀疏的时候, adaptive 的方法能得到更好的效果, 例如, adagrad, adadelta, rmsprop, adam 等. 在数据稀疏的情况下, adam 方法也会比 rmsprop 方法收敛的结果要好一些, 所以, 通常在没有其它更好的理由的前框下, 我会选用 adam 方法, 可以比较快地得到一个预估结果. 但是, 在论文中, 我们看到的大部分还是最原始的 mini-batch 的 SGD 方法. 因为马鞍面的存在等问题, SGD 方法有时候较难收敛. 另外, SGD 对于参数的初始化要求也比较高. 所以, 如果要是想快速收敛的话, 建议使用 adam 这类 adaptive 的方法.

Reference

cs231n