深度学习优化算法总结

深度学习的优化算法

1. 优化的目标

   优化提供了一种最大程度减少深度学习损失函数的方法，但本质上，优化和深度学习的目标不同。

   优化关注的是最小化目标；深度学习是在给定有限数据量的情况下寻找合适的模型。

2. 优化算法

   1. gradient descent（梯度下降）

      考虑一类连续可微实值函数$f:\mathbb{R}\to \mathbb{R}$，利用泰勒展开，可以得到：
      $$f(x+ϵ)=f(x)+ϵf^{\prime }(x)+O({ϵ}^2)$$
      在一阶近似中，$f(x+ϵ)$ 可通过$x$处的函数值$f(x)$和一阶导数$f^{\prime }(x)$得出。假设在负梯度方向上移动的$ϵ$会减少$f$。为了简化问题，选择固定步长$\eta >0$，然后取$ϵ=-\eta f^{\prime }(x)$，将其带入泰勒展开式后，得到
      $$f(x-\eta f^{\prime }(x))=f(x)-\eta f^{\prime 2}(x)+O({\eta }^2{f}^{\prime 2}(x))$$
      若$f^{\prime }(x)\ne 0$，则$\eta f^{\prime 2}(x)>0$。另外，总是可以找到令$\eta$足够小使得高阶项变的不相关，因此
      $$f(x-\eta f^{\prime }(x))<f(x)$$
      这意味着，如果使用
      $$x\leftarrow x-\eta f^{\prime }(x)$$
      来迭代x，函数$f(x)$的值可能会下降。

      因此，在梯度下降中，首先选用初始值$x$和$\eta >0$，然后使用它们连续迭代$x$，直到停止条件达成。例如：当梯度$|f^{\prime }(x)|$的幅度足够小或迭代次数达到某个值。

      其中，步长$\eta$叫做学习率，是超参数，其决定目标函数能否收敛到局部最小值，以及何时收敛到最小值。

   2. SGD（随机梯度下降）

      深度学习中，目标函数通常是训练数据集中每个样本的损失函数的平均值。

      给定$n$个样本，假设$f_i(x)$是关于索引$i$的训练样本的损失函数，其中$X$是参数向量，得到目标函数：
      $$f(X)=\frac{1}{n}\sum _{i=1}^n{f}_i(X)$$
      $X$的目标函数的梯度为：
      $$\nabla f(X)=\frac{1}{n}\sum _{i=1}^n\nabla f_i(X)$$
      如果采用梯度下降法，每个自变量迭代的计算代价为$O(n)$，其随$n$线性增长，因此，当训练数据集规模较大时，每次迭代的梯度下降的计算代价将更高。

      SGD可降低每次迭代时的计算代价。在随机梯度下降的每次迭代中，对数据样本随机均匀采样一个索引$i$，其中i∈{1,...,n}i \in \{ 1,...,n \}i∈{1,...,n}，并计算梯度$\nabla f_i(X)$来更新$X$：
      $$x\leftarrow x-\eta \nabla f_i(X)$$
      其中，$\eta$是学习率。

      可以发现，每次迭代的计算代价从梯度下降的$O(n)$下降到了常数$O(1)$。

      此外，随机梯度$\nabla f_i(x)$是对完整梯度$\nabla f(x)$的无偏估计。
      $$\mathbb{E}\nabla f_i(X)=\frac{1}{n}\sum _{i=1}^n\nabla f_i(X)=\nabla f(X)$$
      这意味着，平均而言，随机梯度是对梯度的良好估计。

   3. minibatch-SGD（小批量随机梯度下降）

      处理单个观测值需要我们执行许多单一矩阵-矢量（甚至矢量-矢量）乘法，这耗费很大，而且对应深度学习框架也要巨大的开销。这既适用于计算梯度以更新参数时，也适用于用神经网络预测。既，当执行$\mathbf{w}\leftarrow \mathbf{w}-{\eta }_t{\mathbf{g}}_t$时，消耗巨大，其中：
      $${\mathbf{g}}_t={\partial }_{\mathbf{w}}f({\mathbf{x}}_t,\mathbf{w}).$$
      可以通过将其应用于一个小批量观测值来提高次操作的计算效率。也就是说，将梯度$g_t$替换为一个小批量而不是单个观测值。
      $${\mathbf{g}}_t={\partial }_{\mathbf{w}}\frac{1}{|{\mathcal{B}}_t|}\sum _{i\in {\mathcal{B}}_t}f({\mathbf{x}}_i,\mathbf{w}).$$
      分析${\mathbf{g}}_t$的统计属性的影响：

      1. 梯度的期望保持不变：${\mathbf{x}}_t$和小批量${\mathcal{B}}_t$的所有元素都是从训练集中随机抽出的。
      2. 方差显著降低：小批量梯度由正在被平均计算的$b:=|{\mathcal{B}}_t|$个独立梯度组成，其标准差降低了$b^{-\frac{1}{2}}$。

      实践中我们选择一个足够大的小批量，它可以提供良好的计算效率同时仍适合GPU的内存。

   4. momentum（动量法）

      1. 泄露平均值

         在小批量随机梯度下降中，定义某次时间$t$的梯度下降计算公式：
         $${\mathbf{g}}_{t,t-1}={\partial }_{\mathbf{w}}\frac{1}{|{\mathcal{B}}_t|}\sum _{i\in {\mathcal{B}}_t}f({\mathbf{x}}_i,{\mathbf{w}}_{t-1})=\frac{1}{|{\mathcal{B}}_t|}\sum _{i\in {\mathcal{B}}_t}{\mathbf{h}}_{i,t-1}.$$
         小批量随机梯度下降可以作为加速计算的手段，同时其也有很好的副作用，即平均梯度减小了方差。
         $${\mathbf{v}}_t=\beta {\mathbf{v}}_{t-1}+{\mathbf{g}}_{t,t-1}$$
         其中，$\beta \in (0,1)$。这将有效的将瞬间梯度替换为“过去“多个梯度的平均值。$\mathbf{v}$被称为动量，其累加了过去的梯度。其中，可以${\mathbf{v}}_t$扩展到
         $$\begin{array}{r}{\mathbf{v}}_t={\beta }^2{\mathbf{v}}_{t-2}+\beta {\mathbf{g}}_{t-1,t-2}+{\mathbf{g}}_{t,t-1}=\dots ,=\sum _{\tau =0}^{t-1}{\beta }^{\tau }{\mathbf{g}}_{t-\tau ,t-\tau -1}.\end{array}$$
         其中，较大的$\beta$相当于长期平均值，较小的$\beta$相当于梯度只是略有修正。新的梯度替换不在指向模型中下降最陡的方向，而是指向过去梯度的加权平均值的方向。

         1. 在优化问题不佳的情况下（例如函数某处”很平“，导数很小），具有动量的梯度可以借用之前的梯度来进行“加速”。
         2. 其允许我们对随后的梯度计算平均值，以获得更稳定的下降方向。

      2. 动量法

         对于minibatch-SGD，使用${\mathbf{v}}_t$而不是梯度${\mathbf{g}}_t$可以生成以下更新等式:
         $$\begin{array}{rl}{\mathbf{v}}_t& \leftarrow \beta {\mathbf{v}}_{t-1}+{\mathbf{g}}_{t,t-1},\\ {\mathbf{x}}_t& \leftarrow {\mathbf{x}}_{t-1}-{\eta }_t{\mathbf{v}}_t.\end{array}$$
         注意，对于$\beta =0$，我们恢复常规的梯度下降。

      3. 有效样本权重

         ${\mathbf{v}}_t={\sum }_{\tau =0}^{t-1}{\beta }^{\tau }{\mathbf{g}}_{t-\tau ,t-\tau -1}$。极限条件下，${\sum }_{\tau =0}^{\infty }{\beta }^{\tau }=\frac{1}{1-\beta }$。

         即，不同于在梯度下降或者随机梯度下降中取步长$\eta$，我们选取步长$\frac{\eta }{1-\beta }$，同时处理潜在表现可能会更好的下降方向。这是集两种好处于一身的做法。

      4. 小结：

      • 动量法用过去梯度的平均值来替换梯度，这大大加快了收敛速度。

      • 对于无噪声梯度下降和嘈杂随机梯度下降，动量法都是可取的。

      • 动量法可以防止在随机梯度下降的优化过程停滞的问题。

      • 由于对过去的数据进行了指数降权，有效梯度数为$\frac{1}{1-\beta }$。

      • 动量法的实现非常简单，但它需要我们存储额外的状态向量（动量$\mathbf{v}$）。

   5. AdaGrad

      1. 稀疏特征和学习率

         需要明确：为了使训练模型获得良好的准确性，我们大多希望在训练的过程中降低学习率，速度通常为$\mathcal{O}(t^{-\frac{1}{2}})$或更低。 对于稀疏特征（即只在偶尔出现的特征）的模型训练，只有在不常见的特征出现时，与其相关的参数才会得到有意义的更新。 鉴于学习率下降，我们可能最终会面临这样的情况：常见特征的参数相当迅速地收敛到最佳值，而对于不常见的特征，我们仍缺乏足够的观测以确定其最佳值。 换句话说，学习率要么对于常见特征而言降低太慢，要么对于不常见特征而言降低太快。

         解决此问题的一个方法是记录我们看到特定特征的次数，然后将其用作调整学习率。 即我们可以使用大小为${\eta }_i=\frac{{\eta }_0}{\sqrt{s(i,t)+c}}$的学习率，而不是$\eta =\frac{{\eta }_0}{\sqrt{t+c}}$。在这里$s(i,t)$计下了我们截至$t$时观察到功能$i$的次数。

         AdaGrad算法 通过将粗略的计数器$s(i,t)$替换为先前观察所得梯度的平方之和来解决这个问题。它使用$s(i,t+1)=s(i,t)+{\left({\partial }_{i}f(\mathbf{x})\right)}^2$来调整学习率。

         这有两个好处：

         1. 不再需要决定梯度何时算足够大。
         2. 其会随梯度的大小自动变化。通常对应于较大梯度的坐标会显著缩小，而其他梯度较小的坐标则会得到更平滑的处理。

      2. AdaGrad算法：

         使用变量${\mathbf{s}}_t$来累加过去的梯度方差：
         $$\begin{array}{rl}{\mathbf{g}}_t& ={\partial }_{\mathbf{w}}l(y_t,f({\mathbf{x}}_t,\mathbf{w})),\\ {\mathbf{s}}_t& ={\mathbf{s}}_{t-1}+{\mathbf{g}}_t^2,\\ {\mathbf{w}}_t& ={\mathbf{w}}_{t-1}-\frac{\eta }{\sqrt{{\mathbf{s}}_t+ϵ}}\cdot {\mathbf{g}}_t.\end{array}$$
         $\eta$是学习率，$ϵ$是一个为维持数值稳定性而添加的常数，用来确保不会除以$0$。最后，初始化${\mathbf{s}}_0=0$。

         就像在动量法中需要跟踪一个辅助变量一样，在AdaGrad算法中，我们允许每个坐标有单独的学习率。与SGD算法相比，这并没有明显增加AdaGrad的计算代价，因为主要计算用在$l(y_t,f({\mathbf{x}}_t,\mathbf{w}))$及其导数。

         注意，在${\mathbf{s}}_t$中累加平方梯度意味着${\mathbf{s}}_t$基本上以线性速率增长（由于梯度从最初开始衰减，实际上比线性慢一些）。这产生了一个学习率$\mathcal{O}(t^{-\frac{1}{2}})$，但是在单个坐标的层面上进行了调整。对于凸问题，这完全足够了。然而，在深度学习中，我们可能希望更慢地降低学习率。这引出了许多AdaGrad算法的变体。

      3. 小结：

         • AdaGrad算法会在单个坐标层面动态降低学习率。

         • AdaGrad算法利用梯度的大小作为调整进度速率的手段：用较小的学习率来补偿带有较大梯度的坐标。

         • 在深度学习问题中，由于内存和计算限制，计算准确的二阶导数通常是不可行的。梯度可以作为一个有效的代理。

         • 如果优化问题的结构相当不均匀，AdaGrad算法可以帮助缓解扭曲。

         • AdaGrad算法对于稀疏特征特别有效，在此情况下由于不常出现的问题，学习率需要更慢地降低。

         • 在深度学习问题上，AdaGrad算法有时在降低学习率方面可能过于剧烈。

   6. RMSProp

      1. RMSProp算法

         Adagrad算法的关键问题之一就是学习率按预定时间表$\mathcal{O}(t^{-\frac{1}{2}})$显著降低。 而且，Adagrad算法将梯度${\mathbf{g}}_t$的平方累加成状态矢量${\mathbf{s}}_t={\mathbf{s}}_{t-1}+{\mathbf{g}}_t^2$。因此，由于缺乏规范化，没有约束力，${\mathbf{s}}_t$持续增长，几乎上是在算法收敛时呈线性递增。

         解决此问题的一种方法是使用${\mathbf{s}}_t/t$。对${\mathbf{g}}_t$的合理分布来说，它将收敛。遗憾的是，限制行为生效可能需要很长时间，因为该流程记住了值的完整轨迹。

         另一种方法是按动量法中的方式使用泄漏平均值，即${\mathbf{s}}_t\leftarrow \gamma {\mathbf{s}}_{t-1}+(1-\gamma ){\mathbf{g}}_t^2$，其中参数$\gamma >0$。保持所有其它部分不变就产生了RMSProp算法。公式：
         $$\begin{array}{rl}{\mathbf{s}}_t& \leftarrow \gamma {\mathbf{s}}_{t-1}+(1-\gamma ){\mathbf{g}}_t^2,\\ {\mathbf{x}}_t& \leftarrow {\mathbf{x}}_{t-1}-\frac{\eta }{\sqrt{{\mathbf{s}}_t+ϵ}}\odot {\mathbf{g}}_t.\end{array}$$
         常数$ϵ>0$通常设置为$10^{-6}$，以确保不会因除以零或步长过大而受到影响。鉴于这种扩展，现在可以自由控制学习率$\eta$，而不考虑基于每个坐标应用的缩放。就泄漏平均值而言，可以采用与之前在动量法中适用的相同推理。

         扩展${\mathbf{s}}_t$定义可获得:
         $$\begin{array}{rl}{\mathbf{s}}_t& =(1-\gamma ){\mathbf{g}}_t^2+\gamma {\mathbf{s}}_{t-1}\\ & =(1-\gamma )\left({\mathbf{g}}_t^2+\gamma {\mathbf{g}}_{t-1}^2+{\gamma }^2{\mathbf{g}}_{t-2}+\dots ,\right).\end{array}$$
         同之前一样，使用$1+\gamma +{\gamma }^2+\dots ,=\frac{1}{1-\gamma }$。因此，权重总和标准化为$1$且观测值的半衰期为${\gamma }^{-1}$。

      2. 小结

         • RMSProp算法与Adagrad算法非常相似，因为两者都使用梯度的平方来缩放系数。
         • RMSProp算法与动量法都使用泄漏平均值。但是，RMSProp算法使用该技术来调整按系数顺序的预处理器。
         • 在实验中，学习率需要由实验者调度。
         • 系数$\gamma$决定了在调整每坐标比例时历史记录的时长。

   7. Adadelta

      1. Adadelta算法

         Adadelta是AdaGrad的另一种变体，主要区别在于其减少了学习率适应坐标的数量。

         此外，广义上Adadelta被称为没有学习率，因为它使用变化量本身作为未来变化的校准。简而言之，Adadelta使用两个状态变量，${\mathbf{s}}_t$用于存储梯度二阶导数的泄露平均值，$\Delta {\mathbf{x}}_t$用于存储模型本身中参数变化二阶导数的泄露平均值。

         以下是Adadelta的技术细节。
         首先获得泄露更新：
         $$\begin{array}{rl}{\mathbf{s}}_t& =\rho {\mathbf{s}}_{t-1}+(1-\rho ){\mathbf{g}}_t^2.\end{array}$$
         与 RMSProp的区别在于，本算法使用重新缩放的梯度${\mathbf{g}}_t^{\prime }$执行更新，即
         $$\begin{array}{rl}{\mathbf{x}}_t& ={\mathbf{x}}_{t-1}-{\mathbf{g}}_t^{\prime }.\end{array}$$
         对于调整后的梯度${\mathbf{g}}_t^{\prime }$：
         $$\begin{array}{rl}{\mathbf{g}}_t^{\prime }& =\frac{\sqrt{\Delta {\mathbf{x}}_{t-1}+ϵ}}{\sqrt{{\mathbf{s}}_t+ϵ}}\odot {\mathbf{g}}_t,\end{array}$$
         其中$\Delta {\mathbf{x}}_{t-1}$是重新缩放梯度的平方${\mathbf{g}}_t^{\prime }$的泄漏平均值。首先将$\Delta {\mathbf{x}}_0$初始化为$0$，然后在每个步骤中使用${\mathbf{g}}_t^{\prime }$更新它，即
         $$\begin{array}{rl}\Delta {\mathbf{x}}_t& =\rho \Delta {\mathbf{x}}_{t-1}+(1-\rho ){{\mathbf{g}}_t^{\prime }}^2,\end{array}$$
         $ϵ$（例如$10^{-5}$这样的小值）是为了保持数字稳定性而加入的。

      2. 小结

         • Adadelta没有学习率参数。相反，它使用参数本身的变化率来调整学习率。

         • Adadelta需要两个状态变量来存储梯度的二阶导数和参数的变化。

         • Adadelta使用泄漏的平均值来保持对适当统计数据的运行估计。

   8. Adam算法

      1. Adam算法：

         Adam算法的关键组成部分之一是：使用指数加权移动平均值来估算梯度的动量和二次矩，即它使用状态变量：
         $$\begin{array}{rl}{\mathbf{v}}_t& \leftarrow {\beta }_1{\mathbf{v}}_{t-1}+(1-{\beta }_1){\mathbf{g}}_t,\\ {\mathbf{s}}_t& \leftarrow {\beta }_2{\mathbf{s}}_{t-1}+(1-{\beta }_2){\mathbf{g}}_t^2.\end{array}$$
         这里${\beta }_1$和${\beta }_2$是非负加权参数。常将它们设置为${\beta }_1=0.9$和${\beta }_2=0.999$。也就是说，方差估计的移动远远慢于动量估计的移动。注意，如果我们初始化${\mathbf{v}}_0={\mathbf{s}}_0=0$，就会获得一个相当大的初始偏差。可以通过使用${\sum }_{i=0}^t{\beta }^i=\frac{1-{\beta }^t}{1-\beta }$来解决这个问题。

         相应地，标准化状态变量由下式获得
         $${\hat{\mathbf{v}}}_t=\frac{{\mathbf{v}}_t}{1-{\beta }_1^t}\text{ and }{\hat{\mathbf{s}}}_t=\frac{{\mathbf{s}}_t}{1-{\beta }_2^t}.$$
         有了正确的估计，我们现在可以写出更新方程。首先，我们以非常类似于RMSProp算法的方式重新缩放梯度以获得
         $${\mathbf{g}}_t^{\prime }=\frac{\eta {\hat{\mathbf{v}}}_t}{\sqrt{{\hat{\mathbf{s}}}_t}+ϵ}.$$
         与RMSProp不同，我们的更新使用动量${\hat{\mathbf{v}}}_t$而不是梯度本身。此外，由于使用$\frac{1}{\sqrt{{\hat{\mathbf{s}}}_t}+ϵ}$而不是$\frac{1}{\sqrt{{\hat{\mathbf{s}}}_t+ϵ}}$进行缩放，两者会略有差异。前者在实践中效果略好一些，因此与RMSProp算法有所区分。通常，选择$ϵ=10^{-6}$，这是为了在数值稳定性和逼真度之间取得良好的平衡。最后，简单更新：
         $${\mathbf{x}}_t\leftarrow {\mathbf{x}}_{t-1}-{\mathbf{g}}_t^{\prime }.$$
         回顾Adam算法，其设计灵感很清楚：

         首先，动量和规模在状态变量中清晰可见，其相当独特的定义使我们移除偏项（这可以通过稍微不同的初始化和更新条件来修正）。其次，RMSProp算法中两项的组合都非常简单。最后，明确的学习率$\eta$使我们能够控制步长来解决收敛问题。

      2. Yogi

         Adam算法也存在一些问题：即使在凸环境下，当${\mathbf{s}}_t$的二次矩估计值爆炸时，它可能无法收敛。为此，有人为${\mathbf{s}}_t$提出了改进的更新和参数初始化。论文中建议重写Adam算法更新如下：
         $${\mathbf{s}}_t\leftarrow {\mathbf{s}}_{t-1}+(1-{\beta }_2)\left({\mathbf{g}}_t^2-{\mathbf{s}}_{t-1}\right).$$
         每当${\mathbf{g}}_t^2$具有值很大的变量或更新很稀疏时，${\mathbf{s}}_t$可能会太快地“忘记”过去的值。一个有效的解决方法是将${\mathbf{g}}_t^2-{\mathbf{s}}_{t-1}$替换为${\mathbf{g}}_t^2\odot \mathrm{sgn}({\mathbf{g}}_t^2-{\mathbf{s}}_{t-1})$。这就是Yogi更新，现在更新的规模不再取决于偏差的量。
         $${\mathbf{s}}_t\leftarrow {\mathbf{s}}_{t-1}+(1-{\beta }_2){\mathbf{g}}_t^2\odot \mathrm{sgn}({\mathbf{g}}_t^2-{\mathbf{s}}_{t-1}).$$
         论文中，作者还进一步建议用更大的初始批量来初始化动量，而不仅仅是初始的逐点估计。

      3. 小结

         • Adam算法将许多优化算法的功能结合到了相当强大的更新规则中。

         • Adam算法在RMSProp算法基础上创建的，还在小批量的随机梯度上使用EWMA。

         • 在估计动量和二次矩时，Adam算法使用偏差校正来调整缓慢的启动速度。

         • 对于具有显著差异的梯度，我们可能会遇到收敛性问题。我们可以通过使用更大的小批量或者切换到改进的估计值${\mathbf{s}}_t$来修正它们。Yogi提供了这样的替代方案。

   9. 算法小结

      1. Gradient Descent: 提供了优化模型的一种理论方法。
      2. SGD: 随机梯度下降在解决优化问题时比梯度下降更有有效。
      3. Minibatch-SGD：在一个小批量中使用更大的观测数据集，可以通过向量化提供额外的效率。这是高效的多机、多GPU和并行处理的关键。
      4. Momentum: 添加一种机制，用于汇聚过去历史梯度来加速收敛。
      5. Adagrad: 用过对每个坐标缩放实现高效的计算预处理器。
      6. RMSProp: Adagrad算法的一个变体，通过学习率的调整来分离每个坐标的缩放。
      7. Adadelta: Adagrad算法的一个变体，其减少了学习率适应坐标的数量。广义上Adadelta被称为没有学习率。
      8. Adam: 是2、3、4、5和6的集大成者。