数值优化算法

⑴ 优化算法

动量法、AdaGrad、RMSProp、AdaDelta、Adam

在7.2节（梯度下降和随机梯度下降）中我们提到，目标函数有关自变量的梯度代表了目标函数在自变量当前位置下降最快的方向。因此，梯度下降也叫作最陡下降（steepest descent）。在每次迭代中，梯度下降根据自变量当前位置，沿着当前位置的梯度更新自变量。然而，如果自变量的迭代方向 仅仅取决于自变量当前位置，这可能会带来一些问题 。

可以看到，同一位置上，目标函数在竖直方向（ 轴方向）比在水平方向（ 轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们 需要一个较小的学习率 从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上 朝最优解移动变慢 。

试着将学习率调大一点，此时自变量在竖直方向不断越过最优解并逐渐发散。

动量法的提出是为了解决梯度下降的上述问题。

其中，动量超参数 满足 。当 时，动量法等价于小批量随机梯度下降。

因此，在实际中，我们常常将 看作是最近 个时间步的 的值的加权平均。

现在，我们对动量法的速度变量做变形：

优化算法中，⽬标函数⾃变量的每⼀个元素在相同时间步都使⽤同⼀个学习率来⾃我迭代。在“动量法”⾥我们看到当x1和x2的梯度值有较⼤差别时，需要选择⾜够小的学习率使得⾃变量在梯度值较⼤的维度上不发散。但这样会导致⾃变量在梯度值较小的维度上迭代过慢。动量法依赖指数加权移动平均使得⾃变量的更新⽅向更加⼀致，从而降低发散的可能。 本节我们介绍AdaGrad算法，它根据⾃变量在每个维度的梯度值的⼤小来调整各个维度上的学习率，从而避免统⼀的学习率难以适应所有维度的问题。

AdaGrad算法会使⽤⼀个小批量随机梯度gt按元素平⽅的累加变量st。在时间步0，AdaGrad将s0中每个元素初始化为0。在时间步t，⾸先将小批量随机梯度gt按元素平⽅后累加到变量st：

其中⊙是按元素相乘。接着，我们将⽬标函数⾃变量中每个元素的学习率通过按元素运算重新调整⼀下：

其中η是学习率，ϵ是为了维持数值稳定性而添加的常数，如10的-6次方。这⾥开⽅、除法和乘法的运算都是按元素运算的。这些按元素运算使得⽬标函数⾃变量中 每个元素都分别拥有⾃⼰的学习率 。

需要强调的是，小批量随机梯度按元素平⽅的累加变量st出现在学习率的分⺟项中。因此，

然而，由于st⼀直在累加按元素平⽅的梯度，⾃变量中每个元素的学习率在迭代过程中⼀直在降低（或不变）。 所以，当学习率在迭代早期降得较快且当前解依然不佳时，AdaGrad算法在迭代后期由于学习率过小，可能较难找到⼀个有⽤的解 。

当学习率在迭代早期降得较快且当前解依然不佳时，AdaGrad算法在迭代后期由于 学习率过小 ，可能较难找到⼀个有⽤的解。为了解决这⼀问题，RMSProp算法对AdaGrad算法做了⼀点小小的修改。

不同于AdaGrad算法⾥状态变量st是 截⾄时间步t所有小批量随机梯度gt按元素平⽅和 ，RMSProp算法将这些梯度 按元素平⽅做指数加权移动平均 。具体来说，给定超参数0 ≤ γ < 1，RMSProp算法在时间步t > 0计算：

和AdaGrad算法⼀样，RMSProp算法将⽬标函数⾃变量中每个元素的学习率通过按元素运算重新调整，然后更新⾃变量：

其中η是学习率，ϵ是为了维持数值稳定性而添加的常数，如10的-6次方。因为RMSProp算法的状态变量st是对平⽅项gt ⊙ gt的指数加权移动平均， 所以可以看作是最近1/(1 − γ)个时间步的小批量随机梯度平⽅项的加权平均。如此⼀来，⾃变量每个元素的学习率在迭代过程中就不再⼀直降低（或不变）。

除了RMSProp算法以外，另⼀个常⽤优化算法AdaDelta算法也针对AdaGrad算法在迭代后期可能较难找到有⽤解的问题做了改进。有意思的是，AdaDelta算法没有学习率这⼀超参数。

AdaDelta算法也像RMSProp算法⼀样，使⽤了小批量随机梯度gt按元素平⽅的指数加权移动平均变量st。在时间步0，它的所有元素被初始化为0。给定超参数0 ≤ ρ < 1（对应RMSProp算法中的γ），在时间步t > 0，同RMSProp算法⼀样计算：

与RMSProp算法不同的是，AdaDelta算法还维护⼀个 额外的状态变量∆xt ，其元素同样在时间步0时被初始化为0。我们使⽤∆xt−1来计算⾃变量的变化量：

最后，我们使⽤∆xt来记录⾃变量变化量 按元素平⽅的指数加权移动平均：

Adam算法在RMSProp算法基础上对小批量随机梯度也做了指数加权移动平均。
Adam算法使⽤了 动量变量vt 和RMSProp算法中 小批量随机梯度按元素平⽅的指数加权移动平均变量st ，并在时间步0将它们中每个元素初始化为0。给定超参数0 ≤ β1 < 1（算法作者建议设为0.9），时间步t的动量变量vt即小批量随机梯度gt的指数加权移动平均：

接下来，Adam算法使⽤以上 偏差修正 后的变量 v ˆ t 和 s ˆ t ，将模型参数中每个元素的学习率通过按元素运算重新调整：

其中 η 是学习率， ϵ 是为了维持数值稳定性而添加的常数，如10的-8次方。和AdaGrad算法、RMSProp算法以及AdaDelta算法⼀样，⽬标函数⾃变量中每个元素都分别拥有⾃⼰的学习率。最后，使⽤ 迭代⾃变量：

⑵ 优化算法

  SGD算法中的一个关键参数是学习率。之前，我们介绍的SGD使用固定的学习率。在实践中，有必要随着时间的推移逐渐降低学习率，因此我们将第 k 步迭代的学习率记作 ϵ k 。
  这是因为SGD中梯度估计引入的噪声源（m 个训练样本的随机采样）并不会在极小点处消失。相比之下，当我们使用批量梯度下降到达极小点时，整个代价函数的真实梯度会变得很小，之后为 0，因此批量梯度下降可以使用固定的学习率。保证SGD收敛的一个充分条件是

  若 ϵ 0 太大，学习曲线将会剧烈振荡，代价函数值通常会明显增加。温和的振荡是良好的，容易在训练随机代价函数（例如使用Dropout的代价函数）时出现。如果学习率太小，那么学习过程会很缓慢。如果初始学习率太低，那么学习可能会卡在一个相当高的代价值。通常，就总训练时间和最终代价值而言，最优初始学习率会高于大约迭代 100 次左右后达到最佳效果的学习率。因此，通常最好是检测最早的几轮迭代，选择一个比在效果上表现最佳的学习率更大的学习率，但又不能太大导致严重的震荡。

  虽然随机梯度下降仍然是非常受欢迎的优化方法，但其学习过程有时会很慢。动量方法 (Polyak, 1964) 旨在加速学习，特别是处理高曲率、小但一致的梯度，或是带噪声的梯度。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿该方向移动。动量的效果如图8.5所示

  受 Nesterov 加速梯度算法 (Nesterov, 1983, 2004) 启发，提出了动量算法的一个变种。这种情况的更新规则如下：

  其中参数 α 和 ϵ 发挥了和标准动量方法中类似的作用。Nesterov 动量和标准动量之间的区别体现在梯度计算上。Nesterov 动量中，梯度计算在施加当前速度之后。因此，Nesterov 动量可以解释为往标准动量方法中添加了一个校正因子。完整的Nesterov动量算法如算法3.2所示

  初始点能够决定算法是否收敛，有些初始点十分不稳定，使得该算法会遭遇数值困难，并完全失败。当学习收敛时，初始点可以决定学习收敛得多快，以及是否收敛到一个代价高或低的点。此外，差不多代价的点可以具有区别极大的泛化误差，初始点也可以影响泛化。
  也许完全确知的唯一特性是初始参数需要在不同单元间 ‘‘破坏对称性’’。如果具有相同激活函数的两个隐藏单元连接到相同的输入，那么这些单元必须具有不同的初始参数。如果它们具有相同的初始参数，然后应用到确定性损失和模型的确定性学习算法将一直以相同的方式更新这两个单元。即使模型或训练算法能够使用随机性为不同的单元计算不同的更新（例如使用Dropout的训练），通常来说，最好还是初始化每个单元使其和其他单元计算不同的函数。这或许有助于确保没有输入模式
丢失在前向传播的零空间中，没有梯度模式丢失在反向传播的零空间中。每个单元计算不同函数的目标促使了参数的随机初始化。我们可以明确地搜索一大组彼此互不相同的基函数，但这经常会导致明显的计算代价。例如，如果我们有和输出一样多的输入，我们可以使用 Gram-Schmidt 正交化于初始的权重矩阵，保证每个单元计算彼此非常不同的函数。在高维空间上使用高熵分布来随机初始化，计算代价小并且不太可能分配单元计算彼此相同的函数。
  通常情况下，我们可以为每个单元的偏置设置启发式挑选的常数，仅随机初始化权重。额外的参数（例如用于编码预测条件方差的参数）通常和偏置一样设置为启发式选择的常数。
  我们几乎总是初始化模型的权重为高斯或均匀分布中随机抽取的值。高斯或均匀分布的选择似乎不会有很大的差别，但也没有被详尽地研究。然而，初始分布的大小确实对优化过程的结果和网络泛化能力都有很大的影响。
  更大的初始权重具有更强的破坏对称性的作用，有助于避免冗余的单元。它们也有助于避免在每层线性成分的前向或反向传播中丢失信号——矩阵中更大的值在矩阵乘法中有更大的输出。如果初始权重太大，那么会在前向传播或反向传播中产生爆炸的值。在循环网络中，很大的权重也可能导致混沌（chaos）（对于输入中很小的扰动非常敏感，导致确定性前向传播过程表现随机）。在一定程度上，梯度爆炸问题可以通过梯度截断来缓解（执行梯度下降步骤之前设置梯度的阈值）。较大的权
重也会产生使得激活函数饱和的值，导致饱和单元的梯度完全丢失。这些竞争因素决定了权重的理想初始大小。
  也有助于避免在每层线性成分的前向或反向传播中丢失信号——矩阵中更大的值在矩阵乘法中有更大的输出。如果初始权重太大，那么会在前向传播或反向传播中产生爆炸的值。在循环网络中，很大的权重也可能导致混沌（chaos）（对于输入中很小的扰动非常敏感，导致确定性前向传播过程表现随机）。在一定程度上，梯度爆炸问题可以通过梯度截断来缓解（执行梯度下降步骤之前设置梯度的阈值）。较大的权重也会产生使得激活函数饱和的值，导致饱和单元的梯度完全丢失。这些竞争因素决定了权重的理想初始大小。
  有些启发式方法可用于选择权重的初始大小。一种初始化 m 个输入和 n 输出的全连接层的权重的启发式方法是从分布 U(−1/√ m ,
1/√ m ) 中采样权重，而 Glorot and Bengio 建议使用标准初始化

  后一种启发式方法初始化所有的层，折衷于使其具有相同激活方差和使其具有相同梯度方差之间。这假设网络是不含非线性的链式矩阵乘法，据此推导得出。现实的神经网络显然会违反这个假设，但很多设计于线性模型的策略在其非线性对应中的效果也不错。
  数值范围准则的一个缺点是，设置所有的初始权重具有相同的标准差，例如1/√ m ，会使得层很大时每个单一权重会变得极其小。Martens (2010) 提出了一种被称为稀疏初始化（sparse initialization）的替代方案，每个单元初始化为恰好有 k 个非零权重。这个想法保持该单元输入的总数量独立于输入数目 m，而不使单一权重元素的大小随 m 缩小。稀疏初始化有助于实现单元之间在初始化时更具多样性。但是，获得较大取值的权重也同时被加了很强的先验。因为梯度下降需要很长时间缩小 ‘‘不正确’’ 的大值，这个初始化方案可能会导致某些单元出问题，例如maxout单元有几个过滤器，互相之间必须仔细调整。

  Delta-bar-delta 算法 (Jacobs, 1988) 是一个早期的在训练时适应模型参数各自学习率的启发式方法。该方法基于一个很简单的想法，如果损失对于某个给定模型参数的偏导保持相同的符号，那么学习率应该增加。如果对于该参数的偏导变化了符号，那么学习率应减小。当然，这种方法只能应用于全批量优化中。

  AdaGrad 算法，如算法8.4所示，独立地适应所有模型参数的学习率，缩放每个参数反比于其所有梯度历史平方值总和的平方根 (Duchi et al., 2011)。具有损失最大偏导的参数相应地有一个快速下降的学习率，而具有小偏导的参数在学习率上有相对较小的下降。净效果是在参数空间中更为平缓的倾斜方向会取得更大的进步。

  在凸优化背景中，AdaGrad 算法具有一些令人满意的理论性质。然而，经验上已经发现，对于训练深度神经网络模型而言，从训练开始时积累梯度平方会导致有效学习率过早和过量的减小。AdaGrad在某些深度学习模型上效果不错，但不是全部。

  RMSProp 算法 (Hinton, 2012) 修改 AdaGrad 以在非凸设定下效果更好，改变梯度积累为指数加权的移动平均。AdaGrad旨在应用于凸问题时快速收敛。当应用于非凸函数训练神经网络时，学习轨迹可能穿过了很多不同的结构，最终到达一个局部是凸碗的区域。AdaGrad 根据平方梯度的整个历史收缩学习率，可能使得学习率在达到这样的凸结构前就变得太小了。RMSProp 使用指数衰减平均以丢弃遥远过去的历史，使其能够在找到凸碗状结构后快速收敛，它就像一个初始化于该碗状结构的 AdaGrad 算法实例。
  RMSProp 的标准形式如算法8.5所示，结合 Nesterov 动量的形式如算法8.6所示。相比于 AdaGrad，使用移动平均引入了一个新的超参数ρ，用来控制移动平均的长度范围。经验上，RMSProp 已被证明是一种有效且实用的深度神经网络优化算法。目前它是深度学习从业者经常采用的优化方法之一。

  Adam (Kingma and Ba, 2014) 是另一种学习率自适应的优化算法，最好被看作结合 RMSProp 和具有一些重要区别的动量的变种。首先，在 Adam 中，动量直接并入了梯度一阶矩（指数加权）的估计。将动量加入 RMSProp 最直观的方法是将动量应用于缩放后的梯度。结合缩放的动量使用没有明确的理论动机。其次，Adam 包括偏置修正，修正从原点初始化的一阶矩（动量项）和（非中心的）二阶矩的估计（算法8.7）。RMSProp 也采用了（非中心的）二阶矩估计，然而缺失了修正因子。因此，不像 Adam，RMSProp 二阶矩估计可能在训练初期有很高的偏置。Adam 通常被认为对超参数的选择相当鲁棒，尽管学习率有时需要从建议的默认修改。

  目前，最流行并且使用很高的优化算法包括 SGD、具动量的 SGD、RMSProp、具动量的 RMSProp、AdaDelta 和 Adam。