优化算法串讲

Posted on | In | |

基本框架

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

  • g_t = \delta J(\theta_t)
  • 根据历史梯度计算一阶动量和二阶动量
    Mt = FI(g_1,g_2,\dots,g_t),V_t = FI(g_1,g_2,\dots,g_t)
  • 计算当前时刻的下降梯度：
    \delta J(\theta_t) = -\ita \dot \frac{m_t}{\sqrt{V_t}}
  • 根据下降梯度更新参数
    \theta_(t+1) = \theta_t + \delta \theta_t

随机梯度下降法（Stochastic Gradient Descent, SGD）

SGD中没有动量的概念，也没有考虑历史梯度，所以他一阶动量即为当前时刻的梯度，二阶动量V_t为E，所以SGD参数的更新公式为：
\delta \theta_t = - \ita \dot \frac{g_t}{\sqrt(E)} = -\ita \dot g_t
\theta_(t+1) = \theta_t + \delta \theta_t = \theta_t - \ita \dot g_t
由于SGD只使用当前时刻的梯度更新参数，没有考虑到历史梯度，所以很容易陷入局部最优解。于是便提出了Momentum来解决SGD陷入局部最优的问题。

指数加权移动平均值(Exponentially Weighted Moving Average,EWMA)

虽然解决局部最优问题要考虑历史梯度，但也并将所有历史梯度都要考虑在内，只要考虑离当前时刻相近的梯度即可。

通过EMWA来将距离较远的梯度筛选掉，只让距离近的梯度对当前梯度产生影响

Momentum(SGD with Momentum)

NAG

不考虑当前时刻的梯度，用当前的下降梯度减去历史梯度惯性，得到“下一步”的梯度。此时仍然没有使用到二阶动量

AdaGrad

二阶动量的出现意味着“自适应学习率”优化算法时代的到来。

对于更新幅度很大的参数，通常历史累计梯度的平方和会很大，更新幅度小的参数，累计历史梯度的平方和会很小。所以在一个固定学习率的基础上除以历史累计梯度的平方和就能使更新幅度大的参数学习率变小，同样也能使用更新幅度小的参数学习率变大。
但时间步足够长之后，所有参数的累积梯度平方和都会变大，以至于所有参数的学习率都不断减小。
于是便出现了不累计全部历史梯度，只关注过去一段时间窗口的下降梯度，筛选的过程同样是使用EMWA实现的。

RMSProp

RMSProp就是在AdaGrad的基础上将普通历史累计梯度平方和换成历史累计梯度平方和的指数加权移动平均值

AdaDelta

针对RMSProp中的学习率进行改进。计算出历史下降梯度的指数加权移动平均，并替换预先设置的学习率，所以在AdaDelta中不需要设置学习率，只要设置好\beta和\alpha的衰减率即可。

Adam

Momentum在SGD的基础上增加了一阶动量，AdaGrad在SGD基础上增加了二阶动量，一阶动量二阶动量都用起来就是Adam了。

Nadam

Nadam是在Adam的基础上将Nesterov集成进来。将t-1时刻的动量m_(t-1)用t时刻的动量m_t近似替代，就引入了“未来因素”