Question

1. 假设代价函数高度敏感于参数空间中的某些方向，则优化算法最好针对不同的参数设置不同的学习率。

   • 代价函数变化明显的参数方向（偏导数较大）：学习率较小，使得更新的步长较小。
   • 代价函数变化不明显的参数方向（偏导数较小）：学习率较大，使得更新的步长较大。

2. 对于标准的batch 梯度下降优化算法，沿着负梯度的方向就是使得代价函数下降的方向。

   • 如果不同的方向设置了不同的学习率，则前进的方向不再是负梯度方向，有可能出现代价函数上升。
   • 对于mini-batch 梯度下降，由于对梯度引入了躁扰，因此可以针对不同的方向设置不同的学习率。

3. 选择哪个算法并没有一个统一的共识，并没有哪一个算法表现的最好。

   目前流行的优化算法包括：SGD，具有动量的SGD，RMSProp，AdaDelta，Adam。选用哪个算法似乎主要取决于使用者对于算法的熟悉程度，以便调节超参数。

5.1 delta-bar-delta

1. delta-bar-delta算法是一个自适应学习率的算法，其策略是：对于代价函数，如果其偏导数保持相同的符号，则该方向的学习率应该增加；如果偏导数变化了符号，则该方向的学习率应该减小。

   偏导数符号变化，说明更新的方向发生了反向。如果此时降低了学习率，则会对震荡执行衰减，会更有利于到达平衡点（偏导数为0的位置）。

2. delta-bar-delta算法只能用于标准的梯度下降中。mini-batch算法对于梯度的估计不是精确的，因此对于正负号的判断会出现较大偏差。

   对于mini-batch 随机梯度下降，有一些自适应学习率的算法。包括：AdaGrad、RMSProp、Adam 等算法。

5.2 AdaGrad

1. AdaGrad算法会独立设置参数空间每个轴方向上的学习率。

   • 如果代价函数在某个方向上具有较大的偏导数，则这个方向上的学习率会相应降低。
   • 如果代价函数在某个方向上具有较小的偏导数，则这个方向上的学习率会相应提高。

2. AdaGrad算法的思想是：参数空间每个方向的学习率反比于某个值的平方根。这个值就是该方向上梯度分量的所有历史平方值之和。

   $ \mathbf{\vec r}\leftarrow \mathbf{\vec r}+\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}}\\ \vec\theta \leftarrow \vec\theta -\frac{\epsilon}{ \sqrt{{\mathbf{\vec r}}}}\odot\hat{\mathbf{\vec g}} $

   其中 $ \odot $ 表示两个向量的逐元素的相乘。

   • 用平方和的平方根而不是均值，因为分量可能为负值。
   • 用历史结果累加，因为考虑的是该方向上的平均表现，而不仅仅是单次的表现。

3. AdaGrad算法：

   • 输入：

     • 全局学习率 $ \epsilon $
     • 初始参数 $ \vec\theta_0 $
     • 小常数 $ \delta $ （为了数值稳定，大约为 $ 10^{-7} $ ）

   • 算法步骤：

     • 初始化梯度累计变量 $ \mathbf{\vec r}=\mathbf{\vec 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 r}\leftarrow \mathbf{\vec r}+\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $

       • 计算更新（逐元素）： $ \Delta\vec\theta\leftarrow -\frac{\epsilon}{\delta+\sqrt{{\mathbf{\vec r}}}}\odot\hat{\mathbf{\vec g}} $

       • 更新参数： $ \vec\theta \leftarrow \vec\theta+\Delta\vec\theta $

4. 由于随迭代次数的增加， $ r_i $ 的值也会增加，因此 $ \frac{\epsilon}{\delta+\sqrt{{\mathbf{\vec r}}}} $ 随着迭代的推进而降低。这起到了一个学习率衰减的效果。

   另一方面，不同方向的分量 $ r_i $ 不同，平均来说梯度分量越大的方向的学习率下降的最快。这起到了一个自适应的效果。

5. 效果：

   • 在凸优化中，AdaGrad算法效果较好。

   • AdaGrad算法在某些深度学习模型上效果不错，但大多数情况下效果不好。

     在训练深度神经网络模型的实践中发现：AdaGrad 学习速率减小的时机过早，且减小的幅度过量。因为学习率与历史梯度的平方和的开方成反比，导致过快、过多的下降。

5.3 RMSProp

5.3.1 RMSProp 原始算法

1. RMSProp是AdaGrad的一个修改：将梯度累计策略修改为指数加权的移动平均。

   $ \mathbf{\vec r}\leftarrow \rho\mathbf{\vec r}+(1-\rho)\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}}\\ \vec\theta \leftarrow \vec\theta -\frac{\epsilon}{ \sqrt{\mathbf{\vec r}}}\odot\hat{\mathbf{\vec g}} $

   其中 $ \rho $ 为衰减速率，它决定了指数加权移动平均的有效长度。

2. 标准的RMSProp算法：

   • 输入：

     • 全局学习率 $ \epsilon $
     • 衰减速率 $ \rho $
     • 初始参数 $ \vec\theta_0 $
     • 小常数 $ \delta $ （为了数值稳定，大约为 $ 10^{-6} $ ）

   • 算法步骤：

     • 初始化梯度累计变量 $ \mathbf{\vec r}=\mathbf{\vec 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 r}\leftarrow \rho\mathbf{\vec r}+(1-\rho)\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $

       • 计算更新（逐元素）： $ \Delta\vec\theta\leftarrow -\frac{\epsilon}{\delta+\sqrt{\mathbf{\vec r}}}\odot\hat{\mathbf{\vec g}} $

       • 更新参数： $ \vec\theta \leftarrow \vec\theta+\Delta\vec\theta $

3. 实践证明RMSProp是一种有效、实用的深度神经网络优化算法，目前它是深度学习业界经常采用的优化方法之一。

5.3.2 RMSProp 原始算法性质

1. 假设迭代过程中，梯度刚好是固定的某个量，令 $ \mathbf{\vec c}=\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $ 。对于某个方向，假设其分量为 $ c=g^2 $ 。

   对于RMSProp 算法：根据等比数列求和公式，该方向的比例因子为： $ r=c\left(1-\rho^{\tau}\right) $ ，其中 $ \tau $ 为迭代次数。

   • 该方向的学习率为：

     $ \bar \epsilon=\frac{\epsilon}{\delta+\sqrt{c(1-\rho^\tau)}} $
     • 随着 $ \tau $ 的增大， $ \bar\epsilon $ 会减小，因为分母在增加。
     • $ r $ 在 $ \tau $ 逐渐增大时，从 $ c(1-\rho) $ 增加到 $ c $ ，其取值范围有限。它使得 $ \bar\epsilon $ 取值从 $ \frac{\epsilon}{\delta+\sqrt{c(1-\rho)}} $ 降低到 $ \frac{\epsilon}{\delta+\sqrt{c}} $ 。

   • 当某个方向的导数 $ g $ 相对于 $ \delta $ 较大时，更新步长为（考虑到 $ r=g^2(1-\rho^\tau) $ ）：

     $ \frac{\epsilon}{\delta+\sqrt{r}}g\sim \frac{\epsilon}{\sqrt{1-\rho^\tau}} $
     • 它与梯度无关，只与迭代次数 $ \tau $ 有关。
     • 随着 $ \tau $ 增大，从 $ \frac{\epsilon}{\sqrt{1-\rho}} $ 降低到 $ \epsilon $ 。
     • RMSProP 算法确保了在梯度较大时，学习的步长不会很小。

   • 当导数 $ g $ 非常小以至于和 $ \delta $ 相差无几时，此时更新步长与梯度有关。

     但是由于此时梯度非常小，算法可能已经收敛。

2. 对于AdaGrad算法的情况：根据等差数列的求和公式，该方向的比例因子为： $ r=\tau c $ ，其中 $ \tau $ 为迭代次数。

   • 该方向的学习率为：

     $ \bar\epsilon=\frac{\epsilon}{\delta+\sqrt{\tau c}} $
     • 随着 $ \tau $ 的增大， $ \bar\epsilon $ 会减小，因为分母在增加。
     • $ r $ 在 $ \tau $ 逐渐增大时，从 $ c $ 增加到 $ +\infty $ 。从而使得 $ \bar\epsilon $ 取值从 $ \frac{\epsilon}{\delta+\sqrt{c}} $ 降低到 $ 0 $ 。

   • 当该方向的梯度对于 $ \delta $ 较大时，更新步长为：

     $ \frac{\epsilon}{\delta+\sqrt{r}}g\sim \frac{\epsilon}{\sqrt{\tau}} $

     它与梯度无关，只与迭代次数 $ \tau $ 有关。随着 $ \tau $ 增大，从 $ \epsilon $ 降低到 $ 0 $ 。

     因此，即使此时的梯度仍然较大，学习的步长仍然接近 0 。

3. RMSProp 算法 vs AdaGrad 算法：

   • AdaGrad 算法中，随着迭代次数的增加，其学习率降低到 0。 而RMSProp 算法中，学习率降低到一个较大的渐进值 $ \frac{\epsilon}{\delta+\sqrt{c}} $ 。
   • AdaGrad 算法中，随着迭代次数的增加，更新步长降低到 0 。而RMSProp 算法中，更新步长降低到一个较大的值 $ \epsilon $ 。

5.3.3 RMSProp 动量算法

1. RMSProp 也可以结合 Nesterov 动量算法。

   本质上 Nesterov 算法（包括其他的动量算法）是关于如何更新参数 $ \vec\theta $ 的算法，它并不涉及任何学习率 $ \epsilon $ 的选取。RMSProp 算法是关于如何选取学习率 $ \epsilon $ 的算法，它并不涉及如何更新参数 $ \vec\theta $ 。因此二者可以结合。

2. RMSProp 动量算法

   • 输入：

     • 全局学习率 $ \epsilon $
     • 衰减速率 $ \rho $
     • 动量系数 $ \alpha $
     • 初始参数 $ \vec\theta_0 $
     • 初始速度 $ \mathbf{\vec v}_0 $

   • 算法步骤：

     • 初始化梯度累计变量 $ \mathbf{\vec r}=\mathbf{\vec 0} $

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

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

       • 计算临时更新： $ \tilde {\vec\theta}\leftarrow \vec\theta+\alpha\mathbf{\vec v} $

         这是因为 Nesterov动量算法使用更新后的参数来计算代价函数。如果使用原始的动量算法，则不需要这一步。

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

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

       • 累计平方梯度： $ \mathbf{\vec r}\leftarrow \rho\mathbf{\vec r}+(1-\rho)\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $

       • 计算速度更新（逐元素）： $ \mathbf{\vec v}\leftarrow \alpha\mathbf{\vec v}-\frac{\epsilon}{\sqrt{\mathbf{\vec r}}}\odot\hat{\mathbf{\vec g}} $

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

5.3.4 AdaDelta

1. AdaDelta 也是 AdaGrad 的一个修改。

   AdaDelta 将梯度平方和的累计策略修改为：只考虑过去窗口 $ window $ 内的梯度。

2. RMSProp 可以认为是一种软化的AdaDelta，衰减速率 $ \rho $ 决定了一个软窗口： $ window = \frac 1{1-\rho} $ 。

   • 加权梯度平方和主要由 $ window $ 内的梯度决定。
   • 更早的梯度由于衰减，其贡献非常小。

5.4 Adam

1. Adam来自于Adaptive moments，它是另一种引入了动量的RMSProp算法。

5.4.1 Adam 算法

1. Adam算法：

   • 输入：

     • 学习率 $ \epsilon $ （建议默认为 0.001）
     • 矩估计的指数衰减速率 $ \rho_1,\rho_2 $ ，它们都位于区间 $ [0,1) $ （建议默认值分别为： 0.9 和 0.999）
     • 用于数值稳定的小常数 $ \delta $ （建议默认为 $ 10^{-8} $ ）
     • 初始参数 $ \vec\theta_0 $

   • 算法步骤：

     • 初始化一阶和二阶矩变量 $ \mathbf{\vec s}=\mathbf{\vec 0,\mathbf{\vec r}=\mathbf{\vec 0}} $

     • 初始化时间步 $ t=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) $

       • $ t\leftarrow t+1 $

       • 更新有偏一阶矩估计： $ \mathbf{\vec s}\leftarrow\rho_1\mathbf{\vec s}+(1-\rho_1)\hat{\mathbf{\vec g}} $ 。

         它是梯度的指数加权平均，用于计算梯度。

       • 更新有偏二阶矩估计： $ \mathbf{\vec r}\leftarrow \rho_2\mathbf{\vec r}+(1-\rho_2)\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $ 。

         它是梯度平方的指数加权平均，用于计算学习率。

       • 修正一阶矩的偏差： $ \hat{\mathbf{\vec s}}\leftarrow \frac{\mathbf{\vec s}}{1-\rho_1^{t}} $ 。

         它使得修正之后的结果更接近真实的梯度。

       • 修正二阶矩的偏差： $ \hat{\mathbf{\vec r}}\leftarrow \frac{\mathbf{\vec r}}{1-\rho_2^{t}} $ 。

         它使得修正之后的结果更接近真实的梯度平方。

       • 计算更新（逐元素）： $ \Delta\vec\theta=- \frac{\epsilon}{\sqrt{\hat{\mathbf{\vec r}}}+\delta} \hat{\mathbf{\vec s}} $

       • 更新参数： $ \vec\theta \leftarrow \vec\theta+\Delta\vec\theta $

2. RMSProp 算法中，通过累计平方梯度（采用指数移动平均）来修正学习率。

   而 Adam算法中，不仅采用同样的方式来修正学习率，还通过累计梯度（采用指数移动平均） 来修正梯度。

3. 动量的计算可以类似Nesterov动量的思想：计算mini-batch的梯度时，采用更新后的参数 $ \vec\theta+\Delta\vec\theta $ 。

   此时称作NAdam 算法。

5.4.2 Adam 算法性质

1. 假设迭代过程中，梯度刚好是固定的某个量，则有： $ \mathbf{\vec c}=\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}} $ 。对于某个方向，假设其分量为 $ c=g^2 $ ，则对于 Adam 算法有：

   $ s=g(1-\rho_1^t)\\ r=c(1-\rho_2^t)\\ \hat s=\frac{s}{1-\rho_1^t}=g\\ \hat r=\frac{r}{1-\rho_2^t}=c\\ \Delta \theta=-\epsilon \frac{\hat s}{\sqrt{\hat r}+\delta}\sim -\epsilon \frac{g}{\sqrt{g^2}}=\epsilon $

   • 无论梯度的大小如何，Adam 算法的参数更新步长几乎都是 $ \epsilon $

     相比较而言，AdaGrad 和 RMSProp 算法的参数更新步长随时间在减少。

   • 虽然最终结果不包含 $ \rho_1,\rho_2 $ ，但是这是由于假定梯度保持不变这一特殊情况推导的。

     实际中梯度很少保持不变，因此 $ \rho_1,\rho_2 $ 还是比较重要。

2. Adam 算法之所以需要使用一阶矩的修正和二阶矩的修正，是为了剔除时间因子 $ t $ 的影响。

3. 在某些情况下，Adam 可能导致训练不收敛。主要原因是：随着时间窗口的变化，遇到的数据可能发生巨变。这就使得 $ \sqrt{\hat r} $ 可能会时大时小，从而使得调整后的学习率 $ \hat \epsilon = \frac{ \epsilon}{\sqrt{\hat r}+\delta} $ 不再是单调递减的。

   这种学习率的震荡可能导致模型无法收敛。

   AdaDelta、RMSProp 算法也都存在这样的问题。

   解决方案为：对二阶动量的变化进行控制，避免其上下波动（确保 $ r $ 是单调递增的)：

   $ \mathbf{\vec r}\leftarrow \max \{\rho_2\mathbf{\vec r}+(1-\rho_2)\hat{\mathbf{\vec g}}\odot\hat{\mathbf{\vec g}},\mathbf{\vec r}\} $

4. 实践证明，虽然在训练早期Adam 具有很好的收敛速度，但是最终模型的泛化能力并不如使用朴素的SGD 训练得到的模型好：Adam 训练的模型得到的测试集误差会更大。

   • 其主要原因可能是：训练后期，Adam 的更新步长过小。

   • 一种改进策略为：在训练的初期使用Adam 来加速训练，并在合适的时期切换为SGD 来追求更好的泛化性能。

     这种策略的缺陷是：切换的时机不好把握，需要人工经验来干预。

5.5 SGD 及其变种的比较

1. 下图为SGD 及其不同的变种在代价函数的等高面中的学习过程。这里batch-size为全体样本大小。

   • AdaGrad、Adadelta、RMSprop 从最开始就找到了正确的方向并快速收敛。
   • SGD 找到了正确的方向，但是收敛速度很慢。
   • SGD 的动量算法、Netsterov 动量算法（也叫做NAG) 最初都偏离了正确方向，但最终都纠正到了正确方向。

   

2. 下图为SGD 及其不同的变种在代价函数的鞍点上的学习过程。这里batch-size为全体样本大小。

   • SGD、SGD 的动量算法、Netsterov 动量算法（也叫做NAG) 都受到鞍点的严重影响。

     • SGD 最终停留在鞍点。

       如果采用mini-batch，则mini-batch 引入的梯度噪音，可以使得SGD 能够逃离鞍点。

     • SGD 的动量算法、Netsterov 动量算法最终逃离了鞍点。

   • Adadelta 、Adagrad、RMSprop 都很快找到了正确的方向。