谈谈优化算法之一（动量法、Nesterov法、自然梯度法）

stonstad · 发表于 2021-7-4 07:35

是时候谈谈优化算法了。不管是求解优化目标还是为了调参，只要问题从理论层面上升到实际操作层面，就离不开优化算法。本节讲主要围绕梯度下降（Gradient Descent）算法展开。
动量法(Momentum)

普通的梯度下降法解决常规问题就足够了，如线性回归，但当问题变复杂，普通的梯度下降法就会面临很多局限。具体来说，对于普通的梯度下降法公式 $\theta\leftarrow\theta-\eta \nabla_{\theta} J(\theta)$ ， $\eta$ 表示学习率，含义是每一时间步上梯度调整的步长（step-size）。当接近最优值时梯度会比较小，由于学习率固定，普通的梯度下降法的收敛速度会变慢，有时甚至陷入局部最优。这时如果考虑历史梯度，将会引导参数朝着最优值更快收敛，这就是动量算法的基本思想。
陷入局部最优或在平原部分缓步前行
结合物理学上的动量思想，在梯度下降问题中引入动量项m和折扣因子，公式变为 $m\leftarrow\gamma m+\eta\nabla_{\theta}J(\theta)$ ， $\theta \leftarrow\theta-m$ 。其中，表示历史梯度的影响力，越大，历史梯度对现在的影响也越大。直观上来说，要是当前时刻的梯度与历史梯度方向趋近，这种趋势会在当前时刻加强，否则当前时刻的梯度方向减弱。若用 $G_{t}$ 表示第t轮迭代的动量， $g_t=\eta\nabla_{\theta}J(\theta)$ 表示第t轮迭代的更新量，当 $t\rightarrow\infty$ ， $G_\infty=\frac{g_0}{1-\gamma}$ ，该式的含义是如果梯度保持不变，最终的更新速度会是梯度项乘以学习率的 $\frac{1}{1-\gamma}$ 倍。举例来说， $\gamma=0.9$ 时，动量算法最终的更新速度是普通梯度下降法的10倍，意味着在穿越“平原”和“平缓山谷”从而摆脱局部最小值时，动量法更有优势。
考虑一个二元函数的例子， $z=x^2+50y^2$ ，利用动量法求最小值。
二元函数的三维可视化图

$\eta=0.016,\gamma=0.7$ 时，在等高线图上的曲线如下：
图（a）

$\eta=0.016,\gamma=0.9$ 时，曲线如下：
图（b）
观察比较（a）（b）时可知，当折扣率变大时，对历史梯度的记忆更多，下一步梯度方向会没这么容易改变过来（从图上直观理解，（b）扭转程度不如（a），即（b）的震荡更明显）。
牛顿动量（Nesterov）算法

观察上图（b）可发现，尽管算法最终找到了最优值，但在过程中由于y方向的梯度比x方向大很多，所以轨迹在y方向存在强烈的震荡抖动。于是Yurii Nesterov在1983年提出了牛顿动量法，改进在于不是在 $\theta$ 做梯度更新，而是前瞻一步，超前一个动量单位处： $\theta+\beta m$ 。则梯度修正公式变为： $m\leftarrow \gamma m+\eta\nabla_{\theta}J(\theta+\beta m)$ ， $\theta\leftarrow \theta-m$ 。
Nesterov与普通动量更新的比较
在上图中，表示普通动量法的梯度更新向量，表示Nesterov梯度更新向量。直观分析可知，会比超前，即牛顿动量法更新会比动量法快。另一方面，当 $\gamma m$ 项越过最优点（optimum）时， $\eta \nabla_1$ 指向另一侧梯度上升方向，而 $\eta \nabla_2$ 指向梯度下降方向，故牛顿动量法能减弱震荡。
同样以之前的二元函数做例子，使用Nesterov法参数设置 $\eta=0.012,\gamma=0.7$ 时效果如下：

Nesterov算法更新过程录屏
https://www.zhihu.com/video/1092523728449224704
自然梯度法（Natural Gradient Descent）

当优化问题的两个坐标轴尺度差异较大时，动量法在更新过程中会出现震荡问题，Nesterov算法给出了初步解决，但这两种方法有一个共性，就是都是从参数的角度去优化模型的，那有没有可能从模型本身角度来考虑呢？——这就是自然梯度法。在强化学习的Natural Actor-Critic算法和TRPO算法中，自然梯度法是强有力的优化工具。
自然梯度法用到Fisher信息矩阵（Fisher Information Matrix）对KL散度进行近似表示，首先介绍一下Fisher信息矩阵。 $E_{J(\theta)}$ 表示以 $J(\theta)$ 概率计算得到的期望，Fisher信息矩阵定义为 $F_{\theta}=E_{J(\theta)}[\nabla_{\theta}logJ(\theta)\nabla_{\theta}logJ(\theta)^T]$ 。以KL散度表示两个模型之间的距离，有近似关系式 $KL(J(\theta)||J(\theta+\Delta\theta))\approx \frac{1}{2}\Delta \theta^TF_{\theta}\Delta\theta$ 。以参数视角看待梯度下降时，可以把每一轮的优化看作这样一个子优化问题：

$min_{\Delta\theta}J(\theta+\Delta\theta)\approx J(\theta)+\nabla_{\theta}J(\theta)\Delta\theta$

$s.t. |\Delta \theta|<\epsilon$
使用自然梯度法以模型距离视角看待问题时，条件限制项变为了 $s.t. KL(J(\theta)||J(\theta+\Delta\theta))<\epsilon$
以Fisher矩阵替代并采用拉格朗日乘子法解带约束的优化问题，原问题变为

$min_{\Delta\theta}J(\theta)+\nabla_{\theta}J(\theta)\Delta\theta+\lambda(\frac{1}{2}\Delta\theta^TF_{\theta}\Delta\theta-\epsilon)$
对 $\Delta{\theta}$ 求导，得 $\Delta \theta=-\frac{1}{\lambda}F_{\theta}^{-1}\nabla_{\theta}J(\theta)$ ，故优化方向可以看作 $F_{\theta}^{-1}\nabla_{\theta}J(\theta)$ 的反方向。
时隔一年，终于把代码传上来啦：
参考：《Hands-On Machine Learning with Scikit-Learn and TensorFlow》第11章

FeastSC · 发表于 2021-7-4 07:40

厉害！

johnsoncodehk · 发表于 2021-7-4 07:48

看着网课一头雾水，看着你的这个文章之后豁然开朗（氮素，，牛顿动量法的图下面第二行是不是应该是delta2比delta1超前呢？）

Mecanim · 发表于 2021-7-4 07:50

delta2是更靠近local minimal呀

kirin77 · 发表于 2021-7-4 07:50

你好，在最后使用拉格朗日乘子法的时候，约束条件应该是－1/2θFθ＜ε 吧，为什么乘进去以后这个负号没有了呢？希望指教，谢谢啦

RhinoFreak · 发表于 2021-7-4 07:55

应该是KL散度近似时没有负号，已修改，谢谢指正啦

zt3ff3n · 发表于 2021-7-4 07:59

在牛顿法里面感觉有问题啊，示例里面theta + beta*m 是比 theta小的，因为此时m小于0啊。

Doris232 · 发表于 2021-7-4 08:00

在牛顿法里面感觉有问题啊，示例里面theta + beta*m 是比 theta小的，因为此时m小于0啊。

TheLudGamer · 发表于 2021-7-4 08:07

应该是theta - beta*m吧

Ylisar · 发表于 2021-7-4 08:08

您好，我是公众号”黄含驰“的号主，可否转载您这篇文章呢？会详细标明出处的！我虽然公众号只有750粉，但只有10多天认真写过公众号，未来会持续努力，向你们学习！

		自动登录	找回密码
密码			立即注册

谈谈优化算法之一（动量法、Nesterov法、自然梯度法）

本帖子中包含更多资源