8.3 基本算法
之前我们已经介绍了梯度下降（第4.3节），即沿着整个训练集的梯度方向下降。这可以使用随机梯度下降很大程度地加速，沿着随机挑选的小批量数据的梯度下降方向，就像第5.9节和第8.1.3节中讨论的一样。
8.3.1 随机梯度下降
随机梯度下降（SGD）及其变种很可能是一般机器学习中应用最多的优化算法，特别是在深度学习中。如第8.1.3节中所讨论的，按照数据生成分布抽取m个小批量（独立同分布的）样本，通过计算它们梯度均值，我们可以得到梯度的无偏估计。
算法8.1展示了如何沿着这个梯度的估计下降。
* * *
算法8.1 随机梯度下降（SGD）在第k个训练迭代的更新。
* * *
Require：学习率
Require：初始参数θ
while停止准则未满足do
从训练集中采包含m个样本的小批量，其中x(i)对应目标为y(i)。
计算梯度估计：
应用更新：
end while
* * *
SGD算法中的一个关键参数是学习率。之前，我们介绍的SGD使用固定的学习率。在实践中，有必要随着时间的推移逐渐降低学习率，因此我们将第k步迭代的学习率记作。
这是因为SGD中梯度估计引入的噪声源（m个训练样本的随机采样）并不会在极小点处消失。相比之下，当我们使用批量梯度下降到达极小点时，整个代价函数的真实梯度会变得很小，之后为0，因此批量梯度下降可以使用固定的学习率。保证SGD收敛的一个充分条件是
且
实践中，一般会线性衰减学习率直到第τ次迭代：
其中。在τ步迭代之后，一般使保持常数。
学习率可通过试验和误差来选取，通常最好的选择方法是监测目标函数值随时间变化的学习曲线。与其说是科学，这更像是一门艺术，我们应该谨慎地参考关于这个问题的大部分指导。使用线性策略时，需要选择的参数为和τ。通常τ被设为需要反复遍历训练集几百次的迭代次数。通常应设为大约的1％。主要问题是如何设置。若太大，学习曲线将会剧烈振荡，代价函数值通常会明显增加。温和的振荡是良好的，容易在训练随机代价函数（例如使用Dropout的代价函数）时出现。如果学习率太小，那么学习过程会很缓慢。如果初始学习率太低，那么学习可能会卡在一个相当高的代价值。通常，就总训练时间和最终代价值而言，最优初始学习率会高于大约迭代100次后达到最佳效果的学习率。因此，通常最好是检测最早的几轮迭代，选择一个比在效果上表现最佳的学习率更大的学习率，但又不能太大导致严重的震荡。
SGD及相关的小批量亦或更广义的基于梯度优化的在线学习算法，一个重要的性质是每一步更新的计算时间不依赖训练样本数目的多寡。即使训练样本数目非常大时，它们也能收敛。对于足够大的数据集，SGD可能会在处理整个训练集之前就收敛到最终测试集误差的某个固定容差范围内。
研究优化算法的收敛率，一般会衡量额外误差（excess error），即当前代价函数超出最低可能代价的量。SGD应用于凸问题时，k步迭代后的额外误差量级是，在强凸情况下是。除非假定额外的条件，否则这些界限不能进一步改进。批量梯度下降在理论上比随机梯度下降有更好的收敛率。然而，Cramér-Rao界限（Cramér，1946；Rao，1945）指出，泛化误差的下降速度不会快于）。Bottou and Bousquet（2008b）因此认为对于机器学习任务，不值得探寻收敛快于）的优化算法——更快的收敛可能对应着过拟合。此外，渐近分析掩盖了随机梯度下降在少量更新步之后的很多优点。对于大数据集，SGD只需非常少量样本计算梯度从而实现初始快速更新，远远超过了其缓慢的渐近收敛。本章剩余部分介绍的大多数算法在实践中都受益于这种性质，但是损失了常数倍）的渐近分析。我们也可以在学习过程中逐渐增大小批量的大小，以此权衡批量梯度下降和随机梯度下降两者的优点。
了解SGD更多的信息，请查看Bottou（1998）。
8.3.2 动量
虽然随机梯度下降仍然是非常受欢迎的优化方法，但其学习过程有时会很慢。动量方法（Polyak，1964）旨在加速学习，特别是处理高曲率、小但一致的梯度，或是带噪声的梯度。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿该方向移动。动量的效果如图8.5所示。
从形式上看，动量算法引入了变量ν充当速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称动量（momentum）来自物理类比，根据牛顿运动定律，负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中，我们假设是单位质量，因此速度向量ν也可以看作粒子的动量。超参数α∈［0，1）决定了之前梯度的贡献衰减得有多快。更新规则如下：
速度ν累积了梯度元素。相对于，越大，之前梯度对现在方向的影响也越大。带动量的SGD算法如算法8.2所示。
图8.5 动量的主要目的是解决两个问题：Hessian矩阵的病态条件和随机梯度的方差。我们通过此图说明动量如何克服这两个问题的第一个。等高线描绘了一个二次损失函数（具有病态条件的Hessian矩阵）。横跨轮廓的红色路径表示动量学习规则所遵循的路径，它使该函数最小化。在该路径的每个步骤画一个箭头，表示梯度下降将在该点采取的步骤。可以看到，一个病态条件的二次目标函数看起来像一个长而窄的山谷或具有陡峭边的峡谷。动量正确地纵向穿过峡谷，而普通的梯度步骤则会浪费时间在峡谷的窄轴上来回移动。比较图4.6，它也显示了没有动量的梯度下降的行为
* * *
算法8.2 使用动量的随机梯度下降（SGD）。
* * *
Require：学习率，动量参数α
Require：初始参数θ，初始速度ν
while没有达到停止准则do
从训练集中采包含m个样本的小批量，对应目标为。
计算梯度估计：
计算速度更新：
应用更新：
end while
* * *
之前，步长只是梯度范数乘以学习率。现在，步长取决于梯度序列的大小和排列。当许多连续的梯度指向相同的方向时，步长最大。如果动量算法总是观测到梯度g，那么它会在方向−g上不停加速，直到达到最终速度，其中步长大小为
因此将动量的超参数视为有助于理解。例如，α＝0.9对应着最大速度10倍于梯度下降算法。
在实践中，α的一般取值为0.5、0.9和0.99。和学习率一样，α也会随着时间不断调整。一般初始值是一个较小的值，随后会慢慢变大。随着时间推移调整α没有收缩重要。
我们可以将动量算法视为模拟连续时间下牛顿动力学下的粒子。这种物理类比有助于直觉上理解动量和梯度下降算法是如何表现的。
粒子在任意时间点的位置由θ(t)给定。粒子会受到净力f(t)。该力会导致粒子加速：
与其将其视为位置的二阶微分方程，我们不如引入表示粒子在时间t处速度的变量ν(t)，将牛顿动力学重写为一阶微分方程：
由此，动量算法包括通过数值模拟求解微分方程。求解微分方程的一个简单数值方法是欧拉方法，通过在每个梯度方向上小且有限的步来简单模拟该等式定义的动力学。
这解释了动量更新的基本形式，但具体什么是力呢？力正比于代价函数的负梯度。该力推动粒子沿着代价函数表面下坡的方向移动。梯度下降算法基于每个梯度简单地更新一步，而使用动量算法的牛顿方案则使用该力改变粒子的速度。我们可以将粒子视作在冰面上滑行的冰球。每当它沿着表面最陡的部分下降时，它会累积继续在该方向上滑行的速度，直到其开始向上滑动为止。
另一个力也是必要的。如果代价函数的梯度是唯一的力，那么粒子可能永远不会停下来。想象一下，假设理想情况下冰面没有摩擦，一个冰球从山谷的一端下滑，上升到另一端，永远来回振荡。要解决这个问题，我们添加另一个正比于−ν(t)的力。在物理术语中，此力对应于黏性阻力，就像粒子必须通过一个抵抗介质，如糖浆。这会导致粒子随着时间推移逐渐失去能量，最终收敛到局部极小点。
为什么要特别使用−ν(t)和黏性阻力呢？部分原因是因为−ν(t)在数学上的便利——速度的整数幂很容易处理。然而，其他物理系统具有基于速度的其他整数幂的其他类型的阻力。例如，颗粒通过空气时会受到正比于速度平方的湍流阻力，而颗粒沿着地面移动时会受到恒定大小的摩擦力。这些选择都不合适。湍流阻力正比于速度的平方，在速度很小时会很弱，不够强到使粒子停下来。非零值初始速度的粒子仅受到湍流阻力，会从初始位置永远地移动下去，和初始位置的距离大概正比于O(log t)，因此我们必须使用速度较低幂次的力。如果幂次为零，相当于干摩擦，那么力太强了。当代价函数的梯度表示的力很小但非零时，由于摩擦导致的恒力会使得粒子在达到局部极小点之前就停下来。黏性阻力避免了这两个问题——它足够弱，可以使梯度引起的运动直到达到最小，但又足够强，使得坡度不够时可以阻止运动。
8.3.3 Nesterov动量
受Nesterov加速梯度算法（Nesterov，1983，2004）启发，Sutskever et al.（2013）提出了动量算法的一个变种。这种情况的更新规则如下：
其中参数α和发挥了和标准动量方法中类似的作用。Nesterov动量和标准动量之间的区别体现在梯度计算上。Nesterov动量中，梯度计算在施加当前速度之后。因此，Nesterov动量可以解释为往标准动量方法中添加了一个校正因子。完整的Nesterov动量算法如算法8.3所示。
* * *
算法8.3 使用Nesterov动量的随机梯度下降（SGD）。
* * *
Require：学习率，动量参数α
Require：初始参数θ，初始速度ν
while没有达到停止准则do
从训练集中采包含m个样本的小批量，对应目标为y(i)。
应用临时更新：
计算梯度（在临时点）：
计算速度更新：
应用更新：
end while
* * *
在凸批量梯度的情况下，Nesterov动量将额外误差收敛率从O(1/k)（k步后）改进到O(1/k2)，如Nesterov（1983）所示。可惜，在随机梯度的情况下，Nesterov动量没有改进收敛率。