机器学习中的优化方法

优化方法

SGD
$g_t=\triangledown \theta_{t-1}f(\theta_{t-1})$
$\triangle \theta_t=-\eta * g_t$
Momentum
$m_t=\mu * m_{t-1} + g_t$
$\triangle \theta_t=-\eta * m_t$
Nesterov
$g_t = \triangledown \theta_{t-1}f(\theta_{t-1}) - \eta * \mu * m_{t-1}$
$m_t=\mu * m_{t-1} + g_t$
$\triangle \theta_t=-\eta * m_t$
Adagrad
$n_t = n_{t-1}+{g_t}^2$
$\triangle \theta_t = -\frac{ \eta }{\sqrt {n_t + \varepsilon}} * g_t = -\frac{ \eta }{\sqrt {\sum_{r=1}^{t}{g_r}^2 + \varepsilon}} * g_t$
Adadelta
$n_t = v * n_{t-1} + (1-v) * {g_t}^2$
$\triangle \theta_t = -\frac{ \eta }{\sqrt {n_t + \varepsilon}} * g_t$
Adam
指数加权平均
$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t$
$v_t = \beta_2 v_{t-1} + (1-\beta_2){g_t}^2$
带偏差修正的指数加权平均
$\widehat{m_t} = \frac{m_t}{1-{\beta_1}^t}$
$\widehat{v_t} = \frac{v_t}{1-{\beta_2}^t}$
$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\widehat{v_t}}+\varepsilon}\widehat{m_t}$

前提
- 牛顿法是为了求解函数值为零的时候变量的取值问题的。
- 如果函数一阶可导，那么函数取得极值时，一阶导数为０。
- 所以求解函数的极值就可以转换为求该函数一阶导数等于０时的变量的取值。
- 即 $f'(x)$ 在 $x_0$ 的一阶泰勒展开 $f'(x) = f'(x_0) + f''(x_0)(x-x_0)=0$
与梯度下降不同，梯度下降的目的是直接求解目标函数极小值，而牛顿法则变相地通过求解目标函数一阶导为零的参数值，进而求得目标函数最小值。
具体地，当要求解 f(θ)的极值时，如果 f 二阶可导，那么可以通过迭代公式。
$\theta = \theta -\frac{f'(\theta)}{f''(\theta) }$
当θ是向量时，牛顿法可以使用下面式子表示：
$\theta = \theta - H^{-1} \triangledown_{\theta}f(\theta)$
其中H叫做海森矩阵， $H^{-1}$ 表示的是海森矩阵的逆矩阵，其实就是目标函数对参数θ的二阶导数

优点：海森矩阵的逆就好比梯度下降法的学习率参数alpha。牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。
牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。
缺点：计算海森矩阵的逆比较困难，消耗时间和计算资源。因此有了拟牛顿法。

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。
其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。