深度学习中的常见优化算法

背景

对一个多元函数 f(x)f(x) 求最小值,当无法准确求出其准确结果时,需要用到其导数。

根据泰勒公式,f(x)f(x)xkx_k 处展开二阶导:

f(x)f(xk)+xf(xk)(xxk)T+12(xxk)Tx2f(xk)(xxk)f(x) \approx f(x_k) + \nabla_x f'(x_k)(x - x_k)^T + \frac{1}{2} (x - x_k)^T \nabla_x^2f''(x_k) (x - x_k)

其中,一阶导梯度和二阶导 HessianHessian 矩阵如下:

gk=f(xk)=(f(xk)x1,f(xk)x2,,f(xk)xn)Hk1=f(xk)1=(2f(xk)2x122f(xk)x1xn2f(xk)xixj2f(xk)xnx12f(xk)2xn2)\begin{aligned} {g_{k} = f^{\prime} \left(x_{k}\right) = \left(\frac{\partial f\left(x_{k}\right)}{\partial x_{1}}, \frac{\partial f\left(x_{k}\right)}{\partial x_{2}}, \ldots, \frac{\partial f\left(x_{k}\right)}{\partial x_{n}}\right)} \\ {H_{k}^{-1}=f^{\prime \prime}\left(x_{k}\right)^{-1}=\left(\begin{array}{ccc}{\frac{\partial^{2} f\left(x_{k}\right)}{\partial^{2} x_{1}^{2}}} & {\cdots} & {\frac{\partial^{2} f\left(x_{k}\right)}{\partial x_{1} \partial x_{n}}} \\ {\vdots} & {\frac{\partial^{2} f\left(x_{k}\right)}{\partial x_{i} \partial x_{j}}} & {\vdots} \\ {\frac{\partial^{2} f\left(x_{k}\right)}{\partial x_{n} \partial x_{1}}} & {\cdots} & {\frac{\partial^{2} f\left(x_{k}\right)}{\partial^{2} x_{n}^{2}}}\end{array}\right)} \end{aligned}

1. 梯度下降法

梯度下降法只用到了一阶导,其思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以只要函数沿着负梯度的方向上迭代移动就可以找到最小值。

迭代公式如下:

θ=θη  θJ(θ)\theta = \theta - \eta \ \cdot \ \nabla_\theta J(\theta)

梯度下降法给出了函数下降的方向,沿着该方向可以找到最小值。

缺点:

  • 靠近极小值时收敛速度减慢;

  • 每次计算全部数据的梯度,会导致运算量加大;

  • 对于凸误差函数,批梯度下降法能够保证收敛到全局最小值,对于非凸函数,则收敛到一个局部最小值。

1.1 随机梯度下降法

根据每一条训练样本更新参数:

θ=θη  θJ(xi,yi;θ)\theta = \theta - \eta \ \cdot \ \nabla_\theta J(x^{i}, y^{i};\theta)

缺点:

  • SGD以高方差频繁地更新,导致目标函数具有波动性。

优点:

  • 计算速度快。
  • 波动性使得SGD可以跳到新的和潜在更好的局部最优点。

1.2 小批量梯度下降法

每次使用一批数据进行梯度的计算,而非计算全部数据的梯度。

θ=θη  1mθJ(xi,yi;θ)\theta = \theta - \eta \ \cdot \ \frac{1}{m}\nabla_\theta J(x^{i}, y^{i};\theta)

优点:

  • 计算量减小;

  • 每次不是朝着真正梯度最小的方向,这样反而可以跳出局部的最优解。

缺点:

  • 梯度更新的方向完全依赖于当前的batch,因而其参数更新十分不稳定。

1.3 Momentum

SGD可能在局部最优点附近更新时发生震荡。在随机梯度下降法的基础上,保留上一轮参数更新的增量,同时利用当前batch的梯度微调最终的更新方向。

vt=γ  vt1+η  θJ(θ)θ=θvtv_t = \gamma \ \cdot \ v_{t - 1} + \eta \ \cdot \ \nabla_\theta J(\theta) \\ \theta = \theta - v_t

优点:

  • 在一定程度上缓解随机梯度下降法收敛不稳定的问题。

1.4 Nesterov

1.5 Adagrad

即adaptive gradient,是一种自适应学习率的梯度法。 上面提到的优化方法每次更新都使用了同一个学习率,而该算法记录并调整每次迭代过程中的前进方向和距离(梯度平方累加和),逐渐减小学习率。

g=1mθJ(xi,yi;θ)r=r+g  gθ=θηδ+r  g\begin{aligned} & 梯度:g = \frac{1}{m}\nabla_\theta J(x^{i}, y^{i};\theta) \\ & 累计梯度平方和:r = r + g \ \cdot \ g \\ & 更新参数:\theta = \theta - \frac{\eta}{\delta + \surd r} \ \cdot \ g \end{aligned}

缺点:

  • 梯度平方累加和是一直增大的,学习率是单调递减的,最后变小以至于最终变得无限小,在学习率无限小时,Adagrad算法将无法取得额外的信息。

优点:

  • 学习率时刻保持变化。

1.5 Adadelta

Adadelta是Adagrad的扩展算法,用来处理Adagrad学习率单调递减的问题。与Adagrad优化算法不同的是它不是计算所有的梯度平方累加和,而是使用历史梯度平方累加的均值代替。

gk=1mθJ(xi,yi;θ)E[g2]k=ρE[g2]k1+(1ρ)gk2θ=θηδ+r  g\begin{aligned} & 梯度:g_k = \frac{1}{m}\nabla_\theta J(x^{i}, y^{i};\theta) \\ & 累计梯度平方期望:E[g^2]_k = \rho E[g^2]_{k-1} + (1 - \rho)g_k^2 \\ & 更新参数:\theta = \theta - \frac{\eta}{\delta + \surd r} \ \cdot \ g \end{aligned}

1.6 RMSProp

1.7 Adam

Adam算法与以上优化算法相比,区别还是比较大的,在参数更新的过程中,首先计算了有偏一阶矩和二阶矩,然后修正一阶矩和二阶矩的偏差,再用修正后的一阶和二阶矩求解参数更新量,最后利用参数更新量对参数进行更新。

gk=1mθJ(xi,yi;θ)sk=ρ1sk1+(1ρ1)gkrk=ρ2rk1+(1ρ2)gk gks^=s1ρ1t^=t1ρ2θ=θη  s^δ+r^  g\begin{aligned} & 梯度:g_k = \frac{1}{m}\nabla_\theta J(x^{i}, y^{i};\theta) \\ & 一阶矩:s_k = \rho_1 s_{k-1} + (1 - \rho_1)g_{k} \\ & 二阶矩:r_k = \rho_2 r_{k-1} + (1 - \rho_2)g_{k} \cdot \ g_{k} \\ & 修正一阶矩:\hat s = \frac{s}{1 - \rho_1} \\ & 修正二阶矩:\hat t = \frac{t}{1 - \rho_2} \\ & 更新参数:\theta = \theta - \eta \ \cdot \ \frac{\hat s}{\delta + \surd \hat r} \ \cdot \ g \end{aligned}

2. 牛顿法

牛顿法考虑了梯度和梯度的变化率,函数的二阶导为零可以对局部凸的函数找到极值,对不凹不凸的函数可能找到鞍点。

将泰勒二阶导展开式两边同时对 xx 求导:

f(x)=f(xk)+2f(xk)(xxk)\nabla f(x) = \nabla f(x_k) + \nabla^2f(x_k) (x - x_k)

令函数的梯度为 0:

f(xk)+2f(xk)(xxk)=0\nabla f(x_k) + \nabla^2f(x_k) (x - x_k) = 0

可解得:

x=xkHk1gkx = x_k - H_{k}^{-1} g_k

迭代公式如下:

xk+1=xkHk1gkx_{k+1} = x_k - H_{k}^{-1} g_k

Reference

https://blog.csdn.net/google19890102/article/details/69942970