【总结】Update Rules_综合

经验总结

在这里插入图片描述

梯度下降

我们先说下 『优化』 的概念，优化指改变 $x$ 以最小化或最大化某个函数 $f (x)$ 的任务

导数在优化中有着不可替代作用，原因在于它表明如何缩放输入的小变化才能在输出获得相应的变化， $f(x+?)=f(x)+?f′(x)+of(x+\epsilon)=f(x)+\epsilon f'(x)+o$ （考虑泰勒展开）。因此，导数对于最小化一个函数很有用，它告诉我们如何改变 $x$ 来略微地改善 $y$

我们知道对于足够小的 $?\epsilon$ ，有 $f[x???sign(f′(x))]?f(x)f[x-\epsilon\cdot sign(f'(x))]\leqslant f(x)$ ，于是我们可以将 $x$ 往导数的反方向移动一小步来减小 $f (x)$ ，这样的技术就被称为 『梯度下降』

我们给出一个简单的数学证明，也给出梯度下降的度示意图
请添加图片描述
在这里插入图片描述
到这里我们就解释清楚了一个问题 为什么反梯度方向即为函数下降最快的方向。这个问题很重要，你会反复的遇到这个问题，被问到这个问题。个人觉得这是网上所有内容，对于这个问题解释最直接和切中要点的答案（解释来源于花书）

接着通过上面证明，我们发现一个问题， $f^{'} (x) = 0$ 的时候导数将无法提供信息往哪个方向移动。 $f^{'} (x) = 0$ 是驻点，一个局部最小点，因此不可能通过移动无穷小的步长来减小 $f (x)$ 。同理，一个局部最大点意味着不可能通过移动无穷小的步长来增大 $f (x)$ 。但是，还有一些情况，这个驻点既不是最大点也不是最小点，这些点被称为 『鞍点』

在这里插入图片描述
在深度学习的背景下，函数可能可能含有许多不是全局最优的局部极小点，或者还有很多处于非常平坦区域内的鞍点，尤其在输入是多维的时候，这都是棘手的问题。因此，我们通常寻找使 $f$ 非常小的点，但这在任何形式意义下并不一定是最小点

在这里插入图片描述
我们经常最小化具有多维输入的函数： $f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R}$ ，为了使最小化的概念有意义，输出必须是一维的（标量）

针对具有多维输入的函数，梯度是相对于一个向量求导的导数—— $f$ 的导数是包含所有偏导数的向量，记为 $▽xf(x)\bigtriangledown_xf(\bm x)$ ，梯度的第 $i$ 个元素是 $f$ 关于 $x_i$ 的偏导数。在多维情况下，临界点是梯度中所有元素都为零的点

在 $u\bm u$ （单位向量）方向的方向导数是函数 $f$ 在 $u\bm u$ 方向的斜率，换句换说，方向导数是函数 $f(x+αu)f(\bm x+\alpha\bm u)$ 关于 $α\alpha$ 的导数，在 $α=0\alpha=0$ 时取得。使用链式法则，我们可以看到当 $α=0\alpha=0$ 时， $??αf(x+αu)=uT▽xf(x)\frac{\partial}{\partial\alpha}f(\bm x+\alpha\bm u)=\bm u^T\bigtriangledown_xf(\bm x)$

为了最小化 $f$ ，我们希望找到使 $f$ 下降最快的方向，于是我们需要计算方向导数
$minu,uTu=1uT▽xf(x)=minu,uTu=1∣∣u∣∣2∣∣▽xf(x)∣∣cosθ(dotproduct)=minucosθ\begin{aligned} \underset{u,u^Tu=1}{min}u^T\bigtriangledown_xf(\bm x)&=\underset{u,u^Tu=1}{min}||u||_2||\bigtriangledown_xf(\bm x)||cos\theta \ (dot\ product) \\ &=\underset{u}{min}\ cos\theta \end{aligned}$

当 $u$ 与梯度方向相反时取得最小，换句话说，梯度向量指向上坡，负梯度向量指向下坡

最快下降建议新的点为 $x′=x??▽xf(x)\bm{x'}=\bm x -\epsilon\bigtriangledown_xf(\bm x)$ ，这里 $?\epsilon$ 是学习率。下降在梯度的每一个元素为零时收敛

Batch Gradient Descent

批量梯度下降就是在更新参数时使用所有的样本进行更新，因为每次都使用完全相同的样本集导致了很多的冗余计算

Mini-Batch Gradient Descent and Stochastic Gradient Descent

机器学习算法中的代价函数通常可以分解成每个样本的代价函数的总和。例如，训练数据的负条件对数似然可以写成

$J(θ)=Ex,y?p^dataL(x,y,θ)=1m∑i=1mL(x(i),y(i),θ)J(\theta)=\mathbb E_{x, y\sim\hat pdata}L(\bm x, y, \theta)=\frac{1}{m}\sum^m_{i=1}L(\bm x^{(i)}, y^{(i)}, \bm\theta)$

其中， $L$ 是每个样本的损失 $L(x,y,θ)=?logp(y∣x;θ)L(\bm x, y, \theta)=-logp(y|\bm x;\theta)$

对于这些相加的代价函数，梯度下降需要计算 $▽θJ(θ)=1m∑i=1m▽θL(x(i),y(i),θ)\bigtriangledown_\bm\theta J(\bm\theta)=\frac{1}{m}\sum^m_{i=1}\bigtriangledown_\bm\theta L(\bm x^{(i), y^{(i)}, \theta})$
这个运算的计算代价是 $O (m)$ ，这样存在一个问题，随着训练集规模增长为数十亿的样本，计算一步梯度也会消耗相当长的时间

于是，我们就有了小批量梯度下降，其核心是，梯度是期望。期望可使用小规模的样本近似估计。具体而言，在算法的每一步，我们从训练集中均匀抽出一个小批量样本， $B={x(1),?,xm′}\mathbb B=\left\{ \bm x^{(1)},\cdots,\bm x^{m'} \right\}$ 。小批量的数目 $m^{'}$ 通常是一个相对较小的数，从一到一百。重要的是，当训练集大小 $m$ 增长时， $m^{'}$ 通常是固定的。我们可能在拟合几十亿的样本时，每次更新计算只用到几个样本

梯度估计可以表示成 $g=1m′▽θ∑i=1m′L(x(i),y(i),θ)\bm g =\frac{1}{m'}\bigtriangledown_\bm\theta\sum_{i=1}^{m'}L(\bm x^{(i)}, y^{(i)}, \bm\theta)$
然后小批量梯度下降算法使用如下的梯度下降估计： $θ←θ??g\bm\theta\leftarrow\bm\theta-\epsilon\bm g$

对于固定大小的模型，每一步小批量梯度下降更新的计算量不取决于训练集的大小 $m$ 。在实践中，当训练集大小增长时，我们通常会使用一个更大的模型，但这并不是必须的。因为当 $m$ 趋于无穷大时，该模型最终会在随机梯度下降抽样完训练集上的所有样本之前收敛到可能的最优测试误差。从这点看，我们可以认为用 MBGD 训练模型的渐近代价是关于 $m$ 的函数的 $O (1)$ 级别

随机梯度下降就是小批量梯度下降 $batch\_size=1$

Momentum-SGD

动量方法旨在加速学习，特别是处理高曲率、小且一致的梯度，或者带噪声的梯度。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿该方向移动

在这里插入图片描述
从形式上看，动量算法引人入变量 $v\bm v$ 充当高速度角色——它代表参数在参数空间移动的方向和速率。速度被设为负梯度的指数衰减平均。名称 『动量』 来自物理类比，根据牛顿运动定律，负梯度是移动参数空间中粒子的力。动量在物理学上定义为质量乘以速度。在动量学习算法中，我们假设是单位质量，因此速度向量 $v\bm v$ 也可以看作是粒子的动量。超参数 $α∈[0,1)\alpha\in[0,1)$ 决定了之前的梯度的贡献衰减得有多快。更新规则如下：
$v←αv??▽θ(1m∑i=1mL(f(x(i);θ),y(i)))θ←θ+v\bm v\leftarrow\alpha\bm v-\epsilon\bigtriangledown_\bm\theta\left(\frac{1}{m}\sum_{i=1}^mL(\bm f(\bm x^{(i)};\bm\theta),\bm y^{(i)})\right)\\ \bm\theta\leftarrow\bm\theta+\bm v$
速度 $v\bm v$ 积累了梯度元素 $▽θ(1m∑i=1mL(f(x(i);θ),y(i))\bigtriangledown_\bm\theta(\frac{1}{m}\sum_{i=1}^mL(\bm f(\bm x^{(i)};\theta),\bm y^{(i)})$ ，相对于 $?\epsilon$ ， $α\alpha$ 越大，之前梯度对现在方向的影响也越大

在这里插入图片描述
之前，步长只是梯度范数乘以学习率。现在，步长取决于梯度序列的大小和排列。当许多连续的提都指向相同的方向时，步长最大。如果动量算法总是观测到梯度 $g\bm g$ ，那么它会在方向 $? g$ 上不停加速，直到达到最终速度，其步长大小为 $?∣∣g∣∣1?α\frac{\epsilon||\bm g||}{1-\alpha}$
可以将动量的超参数视为 $11?α\frac{1}{1-\alpha}$ ，假如 $α=0.9\alpha=0.9$ ，则对应最大速度 $10$ 倍于梯度下降算法

在实践中， $α\alpha$ 的一般取值为 $0.5$ 、 $0.9$ 和 $0.99$ 。和学习率一样， $α\alpha$ 也会随着时间不断调整，一半初始值是一个比较小的值，随后慢慢变大

我们可以类比一下物理学上观察动量和梯度下降算法是如何表现的

粒子在任意时间点的位置由 $θ(t)\bm\theta(t)$ 给定，粒子会受到净力 $f(t)\bm f(t)$ ，该力导致粒子加速度为 $f(t)=?2?t2θ(t)\bm f(t)=\frac{\partial^2}{\partial t^2}\bm\theta(t)$
与其视为位置的二阶微分方程，我们不如引入表示粒子在时间 $4$ 处速度的变量 $v(t)\bm v(t)$ ，将牛顿动力学重写为一阶微分方程 $v(t)=??tθ(t)f(t)=??tv(t)\bm v(t)=\frac{\partial}{\partial t}\bm\theta(t)\\ \ \\ \bm f(t)=\frac{\partial}{\partial t}\bm v(t)$
由此，动量算法包括通过数值模拟求解微分方程。求解微分方程的一个简单数值方法是欧拉方法，通过在每个梯度上小且有限的步来简单模拟该等式定义的动力学

这解释了动量更新的基本形式，但具体什么是力呢？力正比于代价函数的负梯度 $?▽θJ(θ)-\bigtriangledown_\bm\theta J(\bm\theta)$ ，该力推动例子沿着代价函数表面下坡的方向移动。梯度下降算法基于每个梯度简单地更新一步，而使用动量算法的牛顿方案则使用该力改变粒子的速度。我们可以将粒子视作在冰面上滑行的冰球，每当它沿着表面最陡的部分下降时，它会累积继续在该方向上滑行的速度，直到其开始向上滑动为止

同样，粘性阻力在这个方法下也是必要的。如果代价函数的梯度是唯一的力，那么粒子可能永远不会停下来。于是，我们添加一个正比于 $?v(t)-\bm v(t)$ 的力，这会导致粒子随着是假推移逐渐失去能量，最终收敛到局部最小点，而不是在山谷来回振荡

Nesterov 动量

受 Nesterov 加速梯度的算法的启发，Sutskever 提出了动量算法的一个变种，这种情况下的更新规则为 $v←αv??▽θ[1m∑i=1mL(f(x(i);θ+αv),y(i))]θ←θ+v\bm v\leftarrow\alpha\bm v-\epsilon\bigtriangledown_\bm\theta\left[\frac{1}{m}\sum_{i=1}^mL(\bm f(\bm x^{(i)};\bm\theta+\alpha\bm v),\bm y^{(i)})\right]\\ \bm\theta\leftarrow\bm\theta+\bm v$
Nesterov 动量和标准动量之间的区别体现在梯度计算上——Nesterov 动量中，梯度计算在施加当前速度之后

在这里插入图片描述
为什么做这样的改动呢？我们可以根据如下图所示内容作出解释：既然动量法中每一步都要用到历史梯度和当前梯度这两个内容，那么我们可以先按照历史梯度前进一小步，然后按照超前点的位置再来修正梯度，这时和标准动量起到的效果是一样的
请添加图片描述
在理论上，Nesterov 对于凸函数能得到更好的收敛，在实践中也确实比标准动量表现更好一些

AdaGrad

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

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

RMSProp

RMSProp 修改 AdaGrad 以在非凸设定下效果更好，改变梯度累积为指数加权的移动平均

AdaGrad 旨在应用于凸问题时快速收敛，但是存在一些问题：

当应用于非凸函数训练神经网络时，学习轨迹可能穿过了很多不同的结构，最终到达一个局部是凸碗的区域
AdaGrad 根据平方梯度的整个历史收缩学习率，可能使得学习率在达到这样的凸结构前就变得太小

RMSProp 使用衰减平均以丢弃遥远过去的历史，使其能够在找到凸碗状结构后快速收敛，它就像一个初始化于该碗状结构的 AdamGrad 算法

在这里插入图片描述

Adam

早期算法背景下，Adam 也许最好被看作结合 RMSProp 和具有一些重要区别的动量的变种

首先，在 Adam 中，动量直接并入了梯度一阶矩（指数加权）的估计。将动量加入 RMSProp 最直观的方法是将动量应用于缩放后的梯度。结合缩放的动量使用没有明确的理论动机。其次，Adam 包括偏置修正，修正从原点初始化的一阶矩（动量项）和（非中心的）二阶矩估计

RMSProp 也是使用了（非中心的）二阶矩估计，但是没有修正因子，因此二阶矩可能在训练初期有很高的偏置
在这里插入图片描述