Question

4.1 随机梯度下降 SGD

4.1.1 算法

1. 随机梯度下降沿着随机挑选的mini-batch数据的梯度下降方向推进，可以很大程度的加速训练过程。

2. 随机梯度下降SGD及其变种可能是机器学习中用的最多的优化算法。

3. 算法：

   • 输入：学习率 $ \epsilon $

   • 初始参数： $ \vec\theta_0 $

   • 算法步骤：

     迭代，直到满足停止条件。迭代步骤为：

     • 从训练集中随机采样 $ m $ 个样本 $ \{\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_m\} $ 构成mini-batch，对应的标记为 $ \{y_1,y_2,\cdots,y_m\} $ 。

     • 计算mini-batch上的梯度作为训练集的梯度的估计：

       $ \hat{\mathbf{\vec g}}\leftarrow \frac 1m \nabla_{\vec\theta}\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta),y_i) $

     • 更新参数： $ \vec\theta \leftarrow \vec\theta-\epsilon\hat{\mathbf{\vec g}} $

4. 在深度学习中，通常的停止条件是：运行指定数量的迭代步或者epoch， 或者在验证集上的某个度量（如：损失函数、错误率、auc 等）不再提升。

4.1.2 学习率

1. SGD中一个关键参数是学习率。前面介绍的SGD算法步骤使用固定的学习率 $ \epsilon $ ，实践中有必要随着时间的推移而降低学习率。

   使用标准的梯度下降到达极小点时，整个代价函数的真实梯度非常小，甚至为零。由于SGD 使用mini-batch的梯度作为整体梯度的估计，因此引入了噪源。

   该噪源并不会在极小值处消失，使得在极小点时，梯度的估计可能会比较大。因此：标准的梯度下降可以使用固定的学习率，而SGD必须使用逐渐降低的学习率。

   假设在极小点时，梯度的估计值 $ \hat{\mathbf{\vec g}} $ 由于引入了噪源导致较大：

   • 如果采取降低学习率的方法，则步长 $ \epsilon\hat{\mathbf{\vec g}} $ 会很小，这就会导致参数 $ \vec\theta $ 在极小点附近宅幅震荡直至收敛。
   • 如果没有采取降低学习率的方法，则步长 $ \epsilon\hat{\mathbf{\vec g}} $ 会很大，这会导致参数 $ \vec\theta $ 在极小点附近宽幅震荡而且很难收敛。

2. 第 $ k $ 步的学习率记做 $ \epsilon_k $ ，则对于学习率，保证SGD收敛的一个充分条件是： $ \sum_{k=1}^{\infty}\epsilon_k=\infty $ ，且 $ \sum_{k=1}^{\infty}\epsilon_k^{2}\lt \infty $ 。

3. 在实践中，学习率一般线性衰减到第 $ \tau $ 次迭代，之后由于学习率足够小则可以保持不变：

   $ \epsilon_k=\begin{cases} (1-\frac k\tau)\epsilon_0+\frac k\tau\epsilon_\tau&,0\le k\le \tau\\ \epsilon_{\tau}&,k\ge \tau \end{cases} $

   其中： $ \tau $ 是预先指定的（如 1000）， $ \epsilon_0,\epsilon_{\tau} $ 为常数。

   学习率不能够衰减到零，因为一旦 $ \epsilon $ 衰减到零，则很难说明模型收敛是因为学习率为零，还是梯度为零。

4. $ \epsilon_0,\epsilon_{\tau},\tau $ 可以通过试验来选取。

   • $ \epsilon_{\tau} $ 通常被设置为 $ \epsilon_0 $ 的大约 1%， 即降低到足够低的位置。

   • $ \tau $ 决定了学习率衰减的速度：经过多少个迭代步，使得学习率降低到足够低的位置。

   • $ \epsilon_0 $ 被称作初始学习率，它的选择是个重要因素：

     • 如果太大，则学习曲线将会剧烈震荡，代价函数值会明显增加。因为学习率太大，则容易发生超调现象。即：参数剧烈震荡，导致代价函数发散或者震荡。

       注意：温和的震荡是良好的。

     • 如果太小，则学习过程会非常缓慢，学习可能会卡在一个相当高的代价函数值上。

     • 通常最好检测最早的几轮迭代，使用一个高于此时效果最佳学习率的一个学习率，但是又不能太高以至于导致严重的不稳定性。

   

5. 学习速率的选择更像是一门艺术，而不是科学。

4.1.3 性质

1. SGD以及其它的mini-batch算法的最重要性质是：每一步参数更新的计算时间（就是计算梯度的时间）不会随着训练样本数量的增加而增加。

   • 即使训练样本数量非常庞大时，算法也能收敛。
   • 对于足够大的数据集，SGD可能在处理整个训练集的所有样本之前就收敛到测试集误差的允许范围之内了

2. 研究优化算法的收敛率，会衡量额外误差excess error： $ J(\vec\theta)-\min_{\vec\theta}J(\vec\theta) $ 。它刻画了：目标函数当前值到目标函数最小值的距离。

   • SGD应用于凸问题时， $ k $ 步迭代之后的额外误差量级是 $ O(\frac{1}{\sqrt k}) $ ，在强凸情况下是 $ O(\frac 1k) $ 。除非给定额外条件，否则这些界限无法进一步改进。
   • Cramer-Rao界限指出：泛化误差的下降速度不会快于 $ O(\frac 1k) $ 。
   • Bottou and Bousquet认定：对于机器学习任务，不值得探寻收敛快于 $ O(\frac 1k) $ 的优化算法。更快的收敛可能对应于过拟合。

   本章中剩余介绍的大多数算法都实现了实践中的好处，但是丢失了常数倍 $ O(\frac 1k) $ 的渐进收敛率。

3. 可以结合标准梯度下降和SGD两者的优点，在学习过程中逐渐增大mini-batch的大小。

4.2 动量方法

4.2.1 算法

1. 应用了学习率衰减的SGD算法存在一个问题：有些时候学习率会很小，但是明明可以应用一个较大的学习率，而SGD 并不知道这一情况。

   其解决方法是采用动量方法。

2. 动量方法积累了之前梯度的指数级衰减的移动平均，然后继续沿着该方向移动。

   • 它是一种移动平均，权重是指数级衰减的：近期的权重较大，远期的权重很小。
   • 动量方法取这些加权梯度的均值，根据该均值的方向决定参数的更新方向。

3. 动量方法是一种框架，它可以应用到随机梯度下降SGD 算法中。

4. 动量方法引入了变量 $ \mathbf{\vec v} $ 充当速度的角色：它刻画了参数在参数空间移动的方向和速度。

   定义速度为负梯度的指数衰减平均，其更新规则为：

   $ \mathbf{\vec v}\leftarrow \alpha\mathbf{\vec v}-\epsilon\nabla_{\vec\theta} J(\vec\theta)\\ \vec\theta\leftarrow \vec\theta+\mathbf{\vec v} $

   超参数 $ \alpha \in[0,1) $ 描述了衰减权重的底数，从近期到远期的衰减权重为 $ \alpha,\alpha^{2},\alpha^{3},\cdots $

   • $ \alpha $ 决定了梯度衰减有多快。
   • $ \alpha $ 越大，则早期的梯度对当前的更新方向的影响越大；反之，则越小。

5. 令 $ \vec\theta $ 为位移， $ J(\vec\theta) $ 为参数空间的势能，作用力 $ \vec {\mathbf F}=-\epsilon\nabla_{\vec\theta} J(\vec\theta) $ 。根据动量定理：

   $ \vec {\mathbf F}\Delta t=\Delta (m\times \mathbf{\vec v}) $

   • 令粒子为单位质量，时间间隔为单位时间，则有 $ \vec {\mathbf F} =\Delta ( \mathbf{\vec v}) $ ，即： $ -\epsilon\nabla_{\vec\theta} J(\vec\theta)=\mathbf{\vec v}_{t_1}-\mathbf{\vec v}_{t_0} $ 。

     则得到更新公式： $ \mathbf{\vec v}\leftarrow \mathbf{\vec v}-\epsilon\nabla_{\vec\theta} J(\vec\theta) $ 。

   • 引入一个速度衰减系数 $ \alpha $ ，它对上一刻的速度进行降权，则有： $ \mathbf{\vec v}\leftarrow \alpha\mathbf{\vec v}-\epsilon\nabla_{\vec\theta} J(\vec\theta) $ 。

   • 这段时间位移的增量为： $ \mathbf{\vec v}\Delta t=\mathbf{\vec v} $ ，因此有位移更新公式： $ \vec\theta\leftarrow \vec\theta+\mathbf{\vec v} $ 。

     • 由于这个单位时间内，速度发生了变化，因此应该用平均速度。但是由于速度的变化不大，因此用最新的速度也可以。
     • 当前时刻的最新速度等于下一时刻的起始速度，因此无论用起始速度还是最新速度，位移的更新序列都是相同的。

   • 动量方法更新规则的物理意义为：速度更新，位移更新。

6. 下图给出了非动量的方法与动量方法的路径图。代价函数为一个二次函数，它的黑塞矩阵具有不良的条件数。

   红色路径表示动量方法的路径图，黑色箭头给出了在这些点非动量方法的更新方向和步长。

   • 可以看到：动量方法能够快速、正确地到达极小值，而非动量方法会浪费大量的时间在某些方向上宽幅震荡。

   • 原因是：动量方法中，经过加权移动平均之后，在指向极小值的方向上的速度 $ \mathbf{\vec v} $ 不断加强，在垂直于极小值的方向上速度 $ \mathbf{\vec v} $ 不断抵消。

     最终参数会沿着极小值方向快速到达极小值，而在垂直极小值方向波动很小。

   

7. 使用动量的SGD算法：

   • 输入：

     • 学习率 $ \epsilon $
     • 动量参数 $ \alpha $
     • 初始参数 $ \vec\theta_0 $
     • 初始速度 $ \mathbf{\vec v}_0 $

   • 算法步骤：

     迭代，直到满足停止条件。迭代步骤为：

     • 从训练集中随机采样 $ m $ 个样本 $ \{\mathbf{\vec x}_1,\mathbf{\vec x}_2,\cdots,\mathbf{\vec x}_m\} $ 构成mini-batch，对应的标记为 $ \{y_1,y_2,\cdots,y_m\} $ 。

     • 计算mini-batch上的梯度作为训练集的梯度的估计：

       $ \hat{\mathbf{\vec g}}\leftarrow \frac 1m \nabla_{\vec\theta}\sum_{i=1}^{m}L(f(\mathbf{\vec x}_i;\vec\theta),y_i) $

     • 更新速度： $ \mathbf{\vec v}\leftarrow \alpha\mathbf{\vec v}-\epsilon\hat{\mathbf{\vec g}} $

     • 更新参数： $ \vec\theta \leftarrow \vec\theta+\mathbf{\vec v} $

4.2.2 衰减因子

1. 非动量方法的步长只是梯度范数乘以学习率。采用动量之后，步长取决于梯度序列、衰减因子、学习率。

   • 当有许多连续的梯度指向相同的方向时，步长最大。

     可以理解为：不同单位时刻的作用力沿着同一个方向连续的次数越多，则质点的速度会较大（不停沿着同一个方向加速）。而步长就是质点的速度。

   • 动量方法中，如果梯度始终为常量 $ \mathbf{\vec g} $ ，则它会在方向 $ -\mathbf{\vec g} $ 上不停地加速，直到最终的步长为： $ \frac {\epsilon||\mathbf{\vec g}||}{1-\alpha} $ 。

     通过求解速度序列 $ \mathbf{\vec v}_n=\alpha\mathbf{\vec v}_{n-1}-\epsilon \mathbf{\vec g} $ 的解析表达式可以得到

2. 实践中， $ \alpha $ 取值一般为 0.5、0.9、0.99。

   • 和学习率一样， $ \alpha $ 也可以随着时间变化。通常初始时采用一个较小的值，后面慢慢变大。
   • 随着时间推移，改变 $ \alpha $ 没有收缩 $ \epsilon $ 更重要。因为只要 $ 0\lt \alpha \lt 1 $ ，则最终 $ \lim_{t\rightarrow +\infty }\alpha ^t =0 $ 。因此最终参数更新主导的还是 $ -\epsilon \hat{\vec{\mathbf g}} $ 。

4.2.3 Nesterov 动量

1. Nesterov动量是动量方法的变种，也称作Nesterov Accelerated Gradient（NAG）。区别在于：计算mini-batch的梯度时，采用更新后的参数 $ \vec\theta+\alpha\mathbf{\vec v} $ 。

   它可以视作向标准动量方法中添加了一个校正因子：

   $ \mathbf{\vec v}\leftarrow \alpha\mathbf{\vec v}-\epsilon\nabla_{\vec\theta}J(\vec\theta+\alpha\mathbf{\vec v})\\ \vec\theta\leftarrow \vec\theta+\mathbf{\vec v} $

2. 在凸batch梯度情况下，Nesterov动量将额外误差收敛率从 $ O(\frac 1k) $ 改进到 $ O(\frac 1{k^{2}}) $ 。

   但是在随机梯度的情况下，Nesterov动量并没有改进收敛率。