机器学习各优化算法的简单总结

1 梯度下降

1.1 SGD

算法介绍

SGD（Stochasitic Gradient Descent）很简单，就是沿着梯度的反方向更新参数，优化目标函数。优化公式如下：
$d_i = g(\theta_{i-1})$
$\theta_i = \theta_{i-1} - \lambda d_i$
其中$d_i$为当前位置的梯度，也就是损失函数关于参数的一阶导数

优点

操作简单，计算量小，在损失函数是凸函数的情况下能够保证收敛到一个较好的全局最优解

缺点

• $\lambda$是个定值（在最原始的版本），它的选取直接决定了解的好坏，过小会导致收敛太慢，过大会导致震荡而无法收敛到最优解。
• 对于非凸问题，只能收敛到局部最优，并且没有任何摆脱局部最优的能力（一旦梯度为0就不会再有任何变化）
  

  对于非凸的优化问题，我们可以将其转化为对偶问题，对偶函数一定是凹函数，但是这样求出来的解并不等价于原函数的解，只是原函数的一个确下界

1.2 Momentum

算法介绍

Momentum改进自SGD，让每一次的参数更新方向不仅取决于当前位置的梯度，还受到上一次参数更新方向的影响。 $d_i = \beta d_{i-1} + (1-\beta)g(\theta_{i-1})$ $\theta_i = \theta_{i-1} - \lambda d_i$Momentum的意思就是动量，也就意味着上一次更新的方向对本次更新仍然有影响。

优点

一定程度上缓解了SGD收敛不稳定的问题，并且有一定的摆脱局部最优的能力（当前梯度为0时，仍可能按照上次迭代的方向冲出局部最优点），直观上理解，它可以让每次迭代的“掉头方向不是那个大“。

缺点

这里又多了另外一个超参数 $\beta$需要我们设置，它的选取同样会影响到结果。

$\beta$一般取0.9

1.3 Nestrov Momentum

算法介绍

Nestrov Momentum的意义在于，既然下一次一定会更新 $\lambda d_{i}^{’}$，那么求梯度的时候就可以用提前位置的梯度 $g\left(\theta_{i-1}-\lambda d_{i}^{’}\right)$，则： $d_{i}^{’} = \beta d_{i-1} + (1-\beta)g(\theta_{i-1})$ $d_i = \beta d_{i-1} + (1-\beta)g(\theta_{i-1} - \lambda d_{i}^{’})$ $\theta_i = \theta_{i-1} - \lambda d_i$

优点

实验中，一般用Nestrov Momentum比较多，由于结合了二阶导数的信息，收敛比Momentum要更快一些。

缺点

仍然是多了一个超参数需要调整

2 自适应方法

2.1 Adagrad

算法介绍

$c_i = c_{i-1} + g^2(\theta_{i-1})$ $\theta_i = \theta_{i-1} - \frac{\lambda}{\sqrt{c_i + \varepsilon}} g(\theta_{i-1})$其中， $c_i$是一个cache，保存了各位置梯度的平方， $\varepsilon$一般取值为 $10^{-4}～10^{-8}$，为了防止分母取零。

优点

Adagrad不需要手动调节学习率 $\lambda$，因为整体来看，学习率为 $\frac{\lambda}{\sqrt{c_i+\epsilon}}$，它会根据 $c_i$的大小发生自适应的变化（不同位置上变化的幅度不同）。

缺点

• 学习率单调递减，在迭代后期可能导致学习率变得特别小而导致收敛及其缓慢。
• 同样的，我们还需要手动设置初始$\lambda$

2.2 RMSprop

算法介绍

$c_i = \beta c_{i-1} + (1-\beta)g^2(\theta_{i-1})$
$\theta_i = \theta_{i-1} - \frac{\lambda}{\sqrt{c_i + \varepsilon}}g(\theta_{i-1})$

优点

• 可以看出，Rmsprop与Adagrad类似，只不过cache的计算略微复杂一些，利用了一个衰减因子$\beta$，这样可以使得c_i并不是一直处于增大的情况，可以解决Adagrad学习率迅速减小的问题。其中，衰减因子$\beta$通常取值为[0.9，0.99，0.999]。
• 不再需要手动调整学习率，可以根据$c_i$的变化自动调整

缺点

同样的，我们还需要手动设置初始$\lambda$

2.3 Adadelta

算法介绍

$c_i = \gamma c_{i-1} + (1-\gamma)g^2(\theta_{i-1})$
$d_i = -\frac{\sqrt{\Delta_{i-1}+\varepsilon}}{\sqrt{c_{i}+\varepsilon}}g(\theta_{i-1})$
$\theta_i = \theta_{i-1} + d_i$
$\Delta_i = \gamma \Delta_{i-1} + (1-\gamma)d_{i}^2$

优点

• Adadelta与Rmsprop类似，自适应的学习率
• 不需要手动设置$\lambda$

缺点

后期容易在小范围内产生震荡

2.4 Adam

算法介绍

$d_i = \beta_1 d_{i-1} + (1-\beta_1)g(\theta_{i-1})$
$c_i = \beta_2 c_{i-1} + (1-\beta_2)g^2(\theta_{i-1})$
$\hat{d_i} = \frac{d_i}{1-\beta_{1}^t}$
$\hat{c_i} = \frac{c_i}{1-\beta_{2}^t}$
$\theta_i = \theta_{i-1} - \frac{\lambda}{\sqrt{\hat{c_i}+ \varepsilon}} \hat{m_i}$
在参数更新的最初几步中，由于初始化$d_0=0$与$c_0=0$，为了防止最初几步的更新向0偏差，Adam利用$\beta_i$的t次幂来修正这种偏差（t每次更新加1）。

优点

结合Momentum和Adaprop，稳定性好，同时相比于Adagrad，不用存储全局所有的梯度，适合处理大规模数据

缺点

有三个超参数需要调整

通常$\beta_1$取值为0.9，$\beta_2$取值为0.999，$\varepsilon$取值为$10^{-8}$

3 牛顿法与拟牛顿法

3.1 牛顿法

算法介绍

牛顿法和梯度下降法类似，也是求解无约束最优化问题的方法。
$d_i = g(\theta_{i-1})$
$\theta_i = \theta_{i-1} - \lambda H_{i-1}^{-1} d_i$
其中，$H_{i-1}$是优化目标函数L在第i-1步的海森矩阵。

优点

收敛速度较快（考虑到了二阶导数的信息）

缺点

牛顿法的缺点就是$H^{-1}$计算比较复杂，因此有其他改进的方法，例如拟牛顿法。

3.2 拟牛顿法

算法介绍

拟牛顿法用一个矩阵$G$来近似代替$H^{-1}$（或$B$来代替$H$），其中$G$满足拟牛顿条件：
$G_{i+1}y_i = \delta_i (B_{i+1} \delta_i = y_i)$
其中$y_i=g\left(\theta_{i+1}\right)-g\left(\theta_{i}\right)$，$\delta_i=x_{i+1}-x_{i}$。因此按照拟牛顿条件，每次只需更新$G_{i+1}$(或$B_{i+1}$)即可，使得$G_{i+1}=G_i+\Delta G_i$。
牛顿法有多种的具体实现，其中DFP算法选择更新$G$，BFGS选择更新$B$。