最近在了解机器学习算法的知识，看了一些关于梯度更新的文章，在这里想把几种常见的梯度更新的算法介绍一下，顺便加深一下自己的印象。对于确定迭代算法的迭代方向，一般是计算其当前负梯度乘上步长进行迭代，以此迭代求出全局最小值。此称为梯度下降法，基本公式如下：
\[x_{n+1}=x_n-t\nabla f(x_n)\]这种迭代方法的主要原理是由于函数在固定一点的负梯度是其下降最快的地方，所以以此方向进行下一次迭代，但是由于迭代的步长 $t$ 是固定的，有时会出现步长过大以致于无法进入全局最小值或者步长过小以致于无法跳出局部最小值，所以说步长也应该是需要迭代更新的。下面是几种迭代步长的算法：
Line Search
Exact Line Search
Exact Line Search的算法公式如下：
\[x_{n+1}=x_n-t_n\nabla f(x_n)\] \[t_n={\arg\min}_{t}f(x_n-t\nabla f(x_n))\]这种更新步长的方式实际上是在每次迭代时选择能让迭代后的函数值最小的步长，所以这种方法的效果是最好的，但恰恰因为此，这种方法的计算量是最复杂的，相当于每次迭代都要解一个优化问题，所以这种方法仅仅理论上可行，现实中没人使用它。
Backtracking Line Search
Backtracking Line Search的算法如下：
\[x_{n+1}=x_n-a_n\nabla f(x_n)\] \[repeat\quad t:=\beta t\quad if\quad f(x_n+t\nabla f(x_n))<f(x_n)-\alpha t||\nabla f(x_n)||^2\]其中 $\alpha\in(0,0.5)$，$\beta\in(0,1)$。这种方法通过自适应迭代调整每一步的步长，以此更快更好的收敛到全局最小值。其步长更新的原理为从大到小搜索，相当于牺牲了Exact Line Search的精确性，通过迭代代替优化，极大的降低了计算的复杂性，又能保证结果在一个允许的区间内。
Newton’s Method
Newton’s Method
Exact Line search的算法公式如下：
\[x_{n+1}=x_n-t_n\nabla f(x_n)\] \[t_n=[\nabla^2f(x_n)]^{-1}\]步长的更新条件是由泰勒展开作为逼近推倒而来的：
\[f(x_n+s) \approx f(x_n)+\nabla f(x_n)^Ts+\frac{1}{2}s^T\nabla^2f(x_n)s\]为了求出 $f(x_n+s)$ 的最小值，即另右边近似的导数为零，即：
\[\nabla f(x_n)+\nabla^2f(x_n)s=0\] \[s=-[\nabla^2f(x_n)]^{-1}\nabla f(x_n)\]Barzilai–Borwein
Barzilai–Borwein算法是另一种用来确定迭代步长的方法，实际的原理也是基于牛顿法计算的步长，但是用其他表达来逼近，避免了计算繁琐的Hessian矩阵。这个方法的主要目标是确定 $t_n$ 使得：
\[-t_n\nabla f(x_n)\approx -[\nabla^2f(x_n)]^{-1}\nabla f(x_n)\]将式子归纳整理，可以通过一下优化问题解出 $t_n$ 的值：
\[t_n={\arg\min}_r\frac{1}{2}||s^{n-1}-y^{n-1}r||^2\] \[t_n=\frac{(s^{n-1})^Ty^{n-1}}{(y^{n-1})^Ty^{n-1}}\]其中 $s^{n-1}:=x^n-x^{n-1}$ 以及 $y^{n-1}:=\nabla f(x_n)-\nabla f(x_{n-1})$。Barzilai–Borwein算法在处理大规模数据上比较有竞争力，但是算法计算量相对还是复杂。
Adaptive Method
Momentum
Momentum算法正如其名，核心思想是模拟物理上的运动量（Momentum）的特征，在同一方向上步长会逐渐变大，改变方向时步长会减小，这与运动规律类似。Momentum算法的公式如下：
\[x_{n+1}=x_n-v_n\] \[v_n=mv_{n-1}+t\nabla f(x_n)\] \[v_0=t\nabla f(x_n)\]其中 $t$ 为固定步长，$m$ 是Momentum系数，用于模拟运动中的摩擦阻力，一般设定为0.9。在计算参数更新时会考虑前一次更新的方向，如果当前梯度方向与上一次更新一致，则会增强其下降速度，若当前梯度与上一次更新不一致，则会减缓下降速度。这种算法的优点是稳定性高，且可以摆脱局部最小值。
AdaGrad
AdaGrad算法的Ada指的是Adaptive，即自适应，这种算法采取了步长衰减的技巧，会依照梯度去调整步长，其基本公式如下：
\[x_{n+1}=x_n-\frac{t}{\sqrt{\omega+\epsilon}}\nabla f(x_n)\] \[\omega=\sum_{r=1}^{n}||\nabla f(x_n)||^2\]其中 $t$ 为固定步长，在乘上 $\frac{1}{\sqrt{\omega+\epsilon}}$ 为更新项，$\epsilon$ 为平滑值，为了使分母不等于0，一般设为1e-08。 $\omega$ 为前面所有迭代的梯度值的平方和，前期梯度较小的时候 $n$ 较小，步长能被放大，后期梯度越来越大，能够控制步长变小。后期可能为出现分母过于接近零使得训练结束，所以另有通过均方根来代替平方和的RMSprop算法：
\[x_{n+1}=x_n-\frac{t}{\sqrt{\omega _n}+\epsilon}\nabla f(x_n)\] \[\omega _n=\phi\omega _{n-1}+(1-\phi)||\nabla f(x_n)||^2\]在实际应用中一般取 $\phi=0.9$。
Adam
Adam算法的全称是Adaptive Moment Estimation，从字面意思就能看出，Adam结合了AdaGrad和Momentum两种算法的特点，基本公式如下：
\[m_n={\beta}_1m_{n-1}+(1-{\beta}_1)\nabla f(x_n)\] \[v_n={\beta}_2v_{n-1}+(1-{\beta}_2)||\nabla f(x_n)||^2\]Adam的作者发现算法偏移量容易趋近零，所以提出了修正方程以消除偏移量：
\[\bar{m}_n=\frac{m_n}{1-{\beta}_1^n}\] \[\bar{v}_n=\frac{v_n}{1-{\beta}_2^n}\]更新主公式则为：
\[x_{n+1}=x_n-\frac{t}{\sqrt{\bar{v}_n}+\epsilon}\bar{m}_n\]Adam作为现在应用最广泛的优化算法，在tensorflow，Pytorch框架中也颇受青睐。