Salacai's Blog

背景

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

根据泰勒公式，$f(x)$ 在 $x_k$ 处展开二阶导：

$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)$

其中，一阶导梯度和二阶导 $Hessian$ 矩阵如下：

$\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. 梯度下降法

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

迭代公式如下：

$\theta = \theta - \eta \ \cdot \ \nabla_\theta J(\theta)$

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

缺点：

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

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

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

1.1 随机梯度下降法

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

$\theta = \theta - \eta \ \cdot \ \nabla_\theta J(x^{i}, y^{i};\theta)$

缺点：

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

优点：

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

1.2 小批量梯度下降法

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

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

优点：

• 计算量减小；

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

缺点：

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

1.3 Momentum

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

$v_t = \gamma \ \cdot \ v_{t - 1} + \eta \ \cdot \ \nabla_\theta J(\theta) \\ \theta = \theta - v_t$

优点：

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

1.4 Nesterov

1.5 Adagrad

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

$\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优化算法不同的是它不是计算所有的梯度平方累加和，而是使用历史梯度平方累加的均值代替。

$\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算法与以上优化算法相比，区别还是比较大的，在参数更新的过程中，首先计算了有偏一阶矩和二阶矩，然后修正一阶矩和二阶矩的偏差，再用修正后的一阶和二阶矩求解参数更新量，最后利用参数更新量对参数进行更新。

$\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. 牛顿法

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

将泰勒二阶导展开式两边同时对 $x$ 求导：

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

令函数的梯度为 0：

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

可解得：

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

迭代公式如下：

$x_{k+1} = x_k - H_{k}^{-1} g_k$

Reference

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