[论文阅读]综述梯度下降优化算法_耀世娱乐-耀世注册登录官方入口

论文标题：《An overview of gradient descent optimization algorithms》

主要讲述常见的梯度下降优化算法的变化过程，包括SGD、Momentum、NAG、AdaGrad、RMSProp/AdaDelta、Adam、Nadam。

上述优化算法均遵循以下基本框架，这是迭代过程的核心公式。

定义当前时刻待优化参数 $\ heta_t \\in R^d$ ，损失函数为 $J(\ heta)$ ，学习率为 $\\eta$ ，参数更新框架为：

1. 计算损失函数关于当前参数的梯度： $g_t=\\bigtriangledown J(\ heta_t)$
2. 根据历史梯度计算一阶动量和二阶动量：
$m_t=\\phi(g_1,g_2,...,g_t)$ , $V_t=\\psi(g_1,g_2,...,g_t)$
3. 计算当前时刻的下降梯度：
$\\Delta \ heta_t=-\\eta\\cdot\\frac{m_t}{\\sqrt{V_t}}$
4. 根据下降梯度更新参数： $\ heta_{t+1}=\ heta_t+\\Delta\ heta_t$

那么在不同的优化算法中，究竟是哪里发生了变化呢？我们接着往下看，每一个算法都可以对照这个基本框架进行理解。

著名的随机梯度下降算法，SGD中没有阐述动量的概念，即没有考虑历史梯度。所以在SGD中，当前时刻的一阶动量即为当前时刻的梯度 $m_t=g_t$ ，且二阶动量 $V_t=E$ ，所以SGD的参数更新公式为：

$\\Delta \ heta_t=-\\eta\\cdot\\frac{m_t}{\\sqrt{V_t}}=-\\eta\\cdot\\frac{g_t}{\\sqrt{E}}=-\\eta\\cdot g_t$
$\ heta_{t+1}=\ heta_t+\\Delta\ heta_t=\ heta_t-\\eta\\cdot g_t$

完全是按照基本框架来的！

批量梯度下降(Batch gradient descent)、随机梯度下降(SGD)、小批量梯度下降(Mini-batch gradient descent) 其实都是一回事，区别在于对多少样本数量计算梯度，BGD是对所有样本计算梯度（一次性传入所有样本，计算损失函数，进而计算梯度），理论上可以找到全局最优解；SGD是对一个样本计算梯度（一次随机选取一个样本进行计算），每次都是往局部最优的方向下降；MBGD是对一个批次样本计算梯度（一次传入一个批次的样本数据进行计算），依然是往局部最优的方向下降。

当样本量很大时，一次性读入所有样本显然是不可取的。所以通常使用SGD或者说BGD，但两者都不可避免会发生震荡，随着每次传入样本的不同，计算得到的梯度也会不同，自然就会产生震荡。

在介绍Momentum前，先介绍一下指数加权移动平均(Exponentially Weighted Moving Average，EWMA)：

假设 $v_{t-1}$ 是 $t-1$ 时刻的指数加权移动平均值， $\ heta_t$ 是 $t$ 时刻的观测值，那么 $t$ 时刻的指数加权平均值为：

$v_t=\\beta v_{t-1}+(1-\\beta)\ heta_t=(1-\\beta)\ heta_t+\\sum_{i=1}^{t-1}(1-\\beta)\\beta^i\ heta_{t-i}$

其中 $0\\leq\\beta<1$ ， $v_0=0$ 。显然，由上式可知， $t$ 时刻的指数加权移动平均值其实可以看作前 $t$ 时刻所有观测值的指数加权平均值，除了第 $t$ 时刻的观测值权重为 $1-\\beta$ 外，其他时刻的观测值权重为 $(1-\\beta)\\beta^i$ 。由于通常对于那些权重小于 $\\frac1e$ 的观测值可以忽略不计，所以忽略掉那些观测值以后，上式可以看做在求指数加权移动平均值。

那么哪些项的权重会小于 $\\frac 1e$ 呢？由于

$\\lim_{n \\rightarrow +\\infty}{(1-\\frac1n)}^n=\\frac1e\\approx0.3679$

若令 $n=\\frac1{1-\\beta}$ ，则

$\\lim_{n \\rightarrow +\\infty}{(1-\\frac1n)}^n=\\lim_{\\beta \\rightarrow 1}{(\\beta)}^{\\frac{1}{1-\\beta}}=\\frac1e\\approx0.3679$

所以，当 $\\beta \\rightarrow 1$ 时，那些 $i\\geq\\frac1{1-\\beta}$ 的 $\ heta_{t-i}$ 的权重 $(1-\\beta)\\beta^i$ 一定小于 $\\frac1e$ 。例如当 $t=20$ ， $\\beta=0.9$ 时， $\ heta_1,\ heta_2,...,\ heta_9,\ heta_{10}$ 的权重都是小于 $\\frac1e$ ，因此可以忽略不计，那么此时就相当于在求 $\ heta_{11},\ heta_{12},...,\ heta_{19},\ heta_{20}$ 这最近10个时刻的加权移动平均值。所以指数移动平均值可以近似看做在求最近 $\\frac1{1-\\beta}$ 个时刻的加权移动平均值， $\\beta$ 常取 $\\geq0.9$ 。

但是，当 $t$ 较小时，指数加权移动平均值的偏差较大，例如：设 $\ heta_1=40$ ， $\\beta=0.9$ ，那么 $v_1=\\beta v_0 + (1-\\beta)\ heta_1=0.9*0+0.1*40=4$ ，显然 $v_1$ 和 $\ heta_1$ 相差太大，所以通常会加上一个修正因子 $1-\\beta^t$ ，加入修正因子后的公式为

$v_t=\\frac{\\beta v_{t-1}+(1-\\beta)\ heta_t}{1-\\beta^t}$

显然，当 $t$ 很小时，修正因子 $1-\\beta^t$ 会起作用，当 $t$ 足够大时 $\\beta^t \\rightarrow0,(1-\\beta^t)\\rightarrow1$ ，修正因子会自动退场。

SGD with Momentum：Momentum认为梯度下降过程可以加入惯性，也就是在SGD基础上引入一阶动量。而所谓的一阶动量就是该时刻梯度的指数加权移动平均值：

$\\eta\\cdot m_t:=\\beta\\cdot m_{t-1}+\\eta\\cdot g_t$

其中 $g_t$ 并不严格按照指数加权移动平均的定义采用权重 $1-\\beta$ ，而是使用自定义的学习率 $\\eta$ 。此时，依然没有采用二阶动量，所以 $V_t=E$ ，则Momentum的参数更新公式为

$\\Delta\ heta_t=-\\eta\\cdot\\frac{m_t}{\\sqrt E}=-\\eta\\cdot m_t=-(\\beta m_{t-1}+\\eta g_t)$
$\ heta_{t+1}=\ heta_t-(\\beta m_{t-1}+\\eta g_t)$

Momentum算法就是这样，它依然是遵循基本框架的。该算法的主要目的就是为了抑制SGD的震荡而提出的。

除了利用惯性（一阶动量）跳出局部“沟壑”以外，还可以尝试“往前走一步”。

想象一下，你走到一个盆地，四周都是略高的小山，你觉得没有下坡的方向，那就只能待在原地了。可是如果你爬上高地，就会发现外面的世界还很广阔。因此，我们不能停留在当前位置去观察未来的方向，而要“向前多看一步”。

在Momentum中， $t$ 时刻的主要下降方向是由历史梯度（惯性/一阶动量）决定的，当前时刻的梯度权重较小，那不如先看看如果跟着惯性走了一步，那个时候“外面的世界”是怎么样的。也即在Momentum的基础上将当前时刻的梯度 $g_t$ 换成下一时刻的梯度 $\\bigtriangledown J(\ heta_t-\\beta m_{t-1})$ ，此时仍然没有使用二阶动量，所以 $V_t=E$ ，NAG的参数更新公式为：

$\\Delta \ heta_t=-\\eta\\cdot \\frac{m_t}{\\sqrt E}=-\\eta\\cdot m_t=-(\\beta m_{t-1}+\\eta\\bigtriangledown J(\ heta_t-\\beta m_{t-1}))$
$\ heta_{t+1}=\ heta_t-(\\beta m_{t-1}+\\eta\\bigtriangledown J(\ heta_t-\\beta m_{t-1}))$

将NAG于Momentum对照起来，就能看出其中的不同点，以及NAG的核心思想。

此前，均没有使用二阶动量。二阶动量的出现，才意味着“自适应学习率”优化算法时代的到来。SGD及其变种均以同样的学习率更新每个纬度的参数，但深度神经网络往往包含大量的参数，这些参数并不是总会用得到。对于经常更新的参数，我们已经积累了大量关于它的只是，不希望受到单个样本太大的影响，希望学习速率慢一些；对于偶尔更新的参数，我们了解的信息太少，希望能从每个偶然出现的样本身上多学一些，即学习速率大一些。因此，AdaGrad诞生了，它就是考虑了对不同维度的参数采用不同的学习率。

具体地，对于那些更新幅度很大的参数，通常历史累计梯度的平方和会很大；相反地，对于那些更新幅度很小的参数，通常其历史累计梯度的平方和会很小。所以在固定学习率的基础上除以历史累计梯度的平方和就能使得那些更新幅度很大的参数的学习率变小，同样也能使得那些更新幅度很小的参数学习率变大。

所以，AdaGrad的参数更新公式为

$v_{t,i}=\\sum_{t=1}^t g_{t,i}^2$
$\\Delta\ heta_{t,i}=-\\frac{\\eta}{\\sqrt{v_{t,i}+\\epsilon}}g_{t,i}$
$\ heta_{t+1,i}=\ heta_{t,i}-\\frac{\\eta}{\\sqrt{v_{t,i}+\\epsilon}}g_{t,i}$

其中 $g_{t,i}^2$ 表示第 $t$ 时刻第 $i$ 纬度参的梯度值的平方， $\\epsilon$ 是防止分母等于0的平滑项（常取一个很小的值 $1e-8$ ）。显然，上式中的 $\\frac{\\eta}{\\sqrt{v_{t,i}+\\epsilon}}$ 这个整体可以看做是学习率，分母中的历史累计梯度值 $v_{t,i}$ 越大的参数学习率越小。

上式仅仅是第 $t$ 时刻第 $i$ 纬度参数的更新公式，对于第 $t$ 时刻所有纬度参数的整体更新公式为：

$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \\in R^{d\ imes d}$
$\\Delta \ heta_t=-\\frac{\\eta}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$
$\ heta_{t+1}=\ heta_t-\\frac{\\eta}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$

注意，由于 $V_t$ 是对角矩阵，所以 $\\epsilon$ 只用来平滑 $V_t$ 对角线上的元素。

缺点：随着迭代的进行，历史累计梯度平方和 $v_{t,i}$ 会越来越大，这样会使得所有纬度参数的学习率都不断减小（甚至导致梯度消失），无论更新幅度如何。

由于AdaGrad单调递减的学习率变化过于激进，我们考虑一个改变二阶动量计算方法的策略：不累计全部历史梯度，而只关注过去一段时间窗口的下降梯度，采用Momentum中的指数加权移动平均的思想。这也就是AdaDelta名称中Delta的来历。

先看最简单直接版的RMSProp，RMSProp就是在AdaGrad的基础上将普通的历史累计梯度平方和换成历史累计梯度平方和的指数加权移动平均值，所以只需将AdaGrad中 $v_{t,i}$ 的公式改成指数加权移动平均的形式即可，也即：

$v_{t,i}=\\beta v_{t-1,i}+ (1-\\beta)g_{t,i}^2$
$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \\in R^{d\ imes d}$
$\\Delta \ heta_t=-\\frac{\\eta}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$
$\ heta_{t+1}=\ heta_t-\\frac{\\eta}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$

而AdaDelta除了对二阶动量计算指数加权移动平均以外，还对当前时刻的下降梯度 $\\Delta \ heta_t$ 的平方也计算一次指数加权移动平均，具体地：

$E[\\Delta \ heta^2]_{t,i}=\\gamma E[\\Delta \ heta^2]_{t-1,i}+ (1-\\gamma)\\Delta\ heta_{t,i}^2$

由于 $\\Delta \ heta_{t,i}^2$ 目前是未知的，所以只能用 $t-1$ 时刻的指数加权移动平均来近似替换，也即

$E[\\Delta \ heta^2]_{t-1,i}=\\gamma E[\\Delta \ heta^2]_{t-2,i}+ (1-\\gamma)\\Delta\ heta_{t-1,i}^2$

除了计算出 $t-1$ 时刻的指数加权移动平均以外，AdaDelta还用此值替换预先设置的学习率 $\\eta$ 。

因此，AdaDelta的参数更新公式为：

$v_{t,i}=\\beta v_{t-1,i}+ (1-\\beta)g_{t,i}^2$
$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \\in R^{d\ imes d}$
$E[\\Delta \ heta^2]_{t-1,i}=\\gamma E[\\Delta \ heta^2]_{t-2,i}+ (1-\\gamma)\\Delta\ heta_{t-1,i}^2$
$\\Theta_t=diag(E[\\Delta\ heta^2]_{t-1,1},E[\\Delta\ heta^2]_{t-1,2},...,E[\\Delta\ heta^2]_{t-1,d})\\in R^{d\ imes d}$
$\\Delta \ heta_t=-\\frac{\\sqrt{\\Theta_t+\\epsilon}}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$
$\ heta_{t+1}=\ heta_t-\\frac{\\sqrt{\\Theta_t+\\epsilon}}{\\sqrt{V_t + \\epsilon}}\\cdot g_t$

显然，对于AdaDelta算法来说，已经不需要自己预设学习率 $\\eta$ 了，只需要预设 $\\beta$ 和 $\\gamma$ 这两个指数加权移动平均值的衰减率即可。

讲到这里，Adam和Nadam的出现就很自然而然了——它们是前述方法的集大成者。

回顾上面内容，Momentum在SGD基础上加了一阶动量，AdaGrad在SGD基础上加了二阶动量。那么把一阶动量和二阶动量都用起来，就是Adam了。

具体地，首先计算一阶动量： $m_t=\\beta_1 m_{t-1}+(1-\\beta_1)g_t$

然后，类似RMSProp/AdaDelta计算二阶动量

$v_{t,i}=\\beta_2 v_{t-1,i}+ (1-\\beta_2)g_{t,i}^2$
$V_t=diag(v_{t,i},v_{t,2},...,v_{t,d}) \\in R^{d\ imes d}$

然后分别加上指数加权移动平均值的修正因子

$\\hat m_t=\\frac{m_t}{1-\\beta_1^t}$
$\\hat v_{t,i}=\\frac{v_{t,i}}{1-\\beta_2^t}$
$\\hat V_t=diag(\\hat v_{t,i},\\hat v_{t,2},...,\\hat v_{t,d}) \\in R^{d\ imes d}$

最后，Adam的参数更新公式为：

$\\Delta \ heta_t=-\\frac{\\eta}{\\sqrt{\\hat V_t + \\epsilon}}\\cdot \\hat m_t$
$\ heta_{t+1}=\ heta_t-\\frac{\\eta}{\\sqrt{\\hat V_t + \\epsilon}}\\cdot \\hat m_t$

由于Adam没有将Nesterov集成进来，而Nadam则是在Adam的基础上将Nesterov集成进来，即Nadam=Nesterov+Adam。

具体思想如下：由于Nesterov的核心在于，计算当前时刻的梯度 $g_t$ 时使用了“未来梯度”（往前走一步） $\\bigtriangledown J(\ heta_t - \\beta m_{t-1})$ ，Nadam基于此提出了一种公式变形的思路，大意可以这样理解：只要能在梯度计算中考虑到“未来因素”，就算是达到了Nesterov的效果。既然如此，就不一定非要在计算 $g_t$ 时使用“未来因素”，可以在其他地方也考虑使用“未来因素”。

具体地，首先Nadam在Adam的基础上将 $\\hat m_t$ 展开

$\ heta_{t+1}=\ heta_t-\\frac{\\eta}{\\sqrt{{\\hat V_t}+\\epsilon}}\\cdot \\hat m_t=\ heta_t-\\frac{\\eta}{\\sqrt{{\\hat V_t}+\\epsilon}}\\cdot (\\frac{\\beta_1 m_{t-1}}{1-\\beta_1^t}+\\frac{(1-\\beta_1)g_t}{1-\\beta_1^t})$

此时，如果将第 $t-1$ 时刻的动量 $m_{t-1}$ 用第 $t$ 时刻的动量 $m_t$ 近似代替的话，那么就算引入了“未来因素”，所以将 $m_{t-1}$ 替换成 $m_t$ 即可得到Nadam的表达式

$\ heta_{t+1}=\ heta_t-\\frac{\\eta}{\\sqrt{{\\hat V_t}+\\epsilon}}\\cdot (\\frac{\\beta_1 m_{t}}{1-\\beta_1^t}+\\frac{(1-\\beta_1)g_t}{1-\\beta_1^t})=\ heta_t-\\frac{\\eta}{\\sqrt{{\\hat V_t}+\\epsilon}}\\cdot (\\frac{\\beta_1 \\hat m_{t}}{1-\\beta_1^t}+\\frac{(1-\\beta_1)g_t}{1-\\beta_1^t})$

上述总结了优化算法SGD、Momentum、NAG、AdaGrad、RMSProp/AdaDelta、Adam、Nadam的参数更新公式，均可以套用第一节描述的基本框架。虽然，后面的算法是建立在前面算法基础上，不断演变而来，但并不是说Adam或者Nadam算法就是最好的。优化算法的选择应结合具体的应用实际。