优化算法总结

机器学习中的无约束优化算法，包括最小二乘、梯度下降、牛顿/拟牛顿法；样本量不算很大，且存在解析解，可选用最小二乘法，速度快；样本量大时使用梯度下降或牛顿法，二者区别是梯度下降是梯度求解，牛顿法是二阶Hessian矩阵的逆或者伪逆矩阵求解，相对而言，牛顿法收敛快，但每次迭代比梯度下降长

1、最小二乘

待补充....

2、梯度下降

在机器学习算法中，模型实例化后就可以给出明确的目标函数，我们的目标是使得目标函数的表达逼近真实值，在优化目标函数时，最开始的就是梯度下降。
[图片上传失败...(image-1fa3d0-1569724487072)]

梯度下降的思想：

因为变量空间中的某一点沿着梯度方向具有最大的变化率，因此每一步沿着梯度下降的方向去减小函数值，能更快达到优化目标(如极大/极小值)。

梯度下降的步骤

确认优化模型和损失函数
相关参数初始化 (如起始位置(默认0)、步长(学习率)、终止距离)
确定当前位置的梯度
确定当前下降距离
根据下降的梯度进行更新

以线性回归为例：

对应假设函数为：

$h_\theta(x_0, x_1,...x_n)=\sum_{i=0}^n \theta_i x_i$

损失函数为：

$J(\theta)= \frac{1}{2}\sum_{j=0}^n(h_\theta(x^j)-y_j)^{2}$

$\theta$ 初始都设置为0，步长为0.1, 终止距离为1e-5或者1e-8
当前位置梯度：

$\frac{\partial}{\partial\theta}J(\theta_0, \theta_1, ..., \theta_n)$

下降距离：

$\alpha \frac{\partial}{\partial\theta}J(\theta_0, \theta_1, ..., \theta_n)$

参数更新：

$\theta = \theta - \alpha\frac{\partial}{\partial \theta}J(\theta)$

3、梯度下降家族

上文中的梯度下降(BGD)存在一个问题，就是在使用梯度更新参数时，全部样本参与梯度运算，当样本量很大时更新参数变慢和困难

$\theta_j:=\theta_j + \alpha \sum_{i=1}^n(y^{(i)}-h_\theta(x^{(i)}))x_j^{(i)}$

因此就有了SGD和Mini-Batch GD
其中SGD是每次只选择一个样本进行参数的更新

for i = 1 to m{
　　 $\theta_j := \theta_j + \alpha(y^{i}-h_{\theta}(x^{(i)}))x_j^{(i)}$
}

Mini-Batch是每次取其中小批量样本进行参数的更新，是BGD和SGD的折中方案。

4、从SGD到Adam

在深度学习领域，优化算法得到了极大的发展，脉络是SGD -> SGDM -> NAG ->AdaGrad -> AdaDelta -> Adam -> Nadam。
总体而言，优化算法的步骤可分为几个部分：
待优化的参数： $\omega$ ，目标函数： $J(\omega)$ ，初始学习率 $\alpha$ ，对每个epoch $t$

计算目标函数关于当前参数的梯度： $g_t=\nabla f(w_t)$

根据历史梯度计算一阶动量和二阶动量
$m_t=\phi(g_1, g_2,...g_t) 　V_t=\psi(g_1, g_2,...g_t)$

计算当前时刻的下降梯度： $\eta_t=\alpha \cdot m_t/\sqrt V_t$

根据下降梯度进行更新： $\omega_{t+1}=\omega_t - \eta_t$

而不同的优化算法对于步骤3和4基本一致，主要差别体现在1和2上

SGD 没有动量的概念，则 $m_t = g_t$ ， $V_t = I^2$ ,带入3就是 $\eta_t = \alpha \cdot g_t$ ，SGD的缺点是慢，可能会造成在沟壑两边震荡，停留在局部最优点。
SGD with Momentum
改进点在于2，在SGD基础上引入了一阶动量， $m_t = \beta_1 \cdot m_{t-1} + (1-\beta_1)\cdot g_t$ ，一阶动量是各个时刻梯度方向的指数移动平均，约等于 $1/(1-\beta_1)$ 个时刻的梯度向量和的平均值。若 $\beta_1$ 为0.9则 $t$ 时刻的梯度由当前时刻与前10个时刻的梯度共同决定，此时之前的时刻就占主导地位。
SGD with Nesterov Acceleration
改进点在1，因为在SGD with Momentum中当前下降的方向由之前的累积动量决定，因为一个思路是直接改变梯度的方向，不直接计算梯度而是计算按照积累动量走一步后的下降方向：

$g_t= \nabla f(\omega_t - \alpha \cdot m_{t-1}/\sqrt {V_{t-1}})$

再用下一个点的梯度方向与历史积累动量相结合，计算2中当前时刻积累的动量。

AdaGrad
引入了二阶动量，即自适应学习率，我们希望经常更新的参数，学习率低一些，偶尔更新的参数，学习率大些，度量更新频率的就是二阶动量：

$V_t=\sum_{i=1}^t g_{t}^2$

此时的学习率有 $\alpha$ 变成了 $\alpha /\sqrt{V_t}$ ，单调递减，至0.

AdaDelta / RMSProp
对于二阶动量，不累积全部梯度，只关注一段时间窗口的下降梯度

$V_t=\beta_2 * V_{t-1}+(1-\beta_2) g_t^2$

Adam
结合了一阶动量和二阶动量，SGD的一阶动量

$m_t=\beta_1 \cdot m_{t-1} + (1-\beta_1) \cdot g_t$

加上AdaDelta的二阶动量：

$V_t=\beta_2 * V_{t-1} + (1-\beta_2)g_t^2$

Nadam
在adam的基础上又加上了Nesterov

$g_t=\nabla f(\omega_t - \alpha \cdot m_{t-1}/{\sqrt{V_t}})$

需要指出的是，常用的Adam和SGD，但是Adam肯能存在不收敛和错过全局最优解的问题，所以优先使用SGD，也可以先用Adam快速下降，再SGD调优，不过涉及什么时候切换算法，切换后用什么样的学习率的问题(Adam用自适应的，SDG得人为给定)

5、牛顿/拟牛顿法

未完待续....

6、梯度爆炸、梯度消失问题

在深度网络中，使用梯度下降会引发梯度爆炸和梯度消失的问题，梯度消失是因为反向传播过程中对梯度的求解会产生sigmoid导数和参数的连乘，sigmoid导数的最大值为0.25，权重一般初始都在0，1之间，乘积小于1，多层的话就会有多个小于1的值连乘，导致靠近输入层的梯度几乎为0，得不到更新。梯度爆炸是也是同样的原因，只是如果初始权重大于1，或者更大一些，多个大于1的值连乘，将会很大或溢出，导致梯度更新过大，模型无法收敛。
解决梯度爆炸和梯度消失的方法有：

正则

$Loss = (y-\omega^T x)^{2} + \alpha ||W||^{2}$

正则的方法主要是针对梯度爆炸，加入正则项使得权值 $\omega$ 不至于太大，一定程度上避免梯度爆炸的发生。

改变激活函数
一般是Relu激活函数，因为在正数部分其导数为1也就解决了累乘时梯度爆炸和梯度消失的问题，同时因计算方便也加速了网络的训练。因负数部分直接置为0会导致一些神经元无法激活，因此可采用Leaky Relu
BN
Batch Normalization即批规范化，
BN加速网络收敛速度，提升训练稳定性的效果
更加详细的关于BN的解释见：
残差结构
残差网络的设计就是为了解决神经网络层数增加时造成的梯度消失问题，
类似lstm由*变+

参考文章：
https://zhuanlan.zhihu.com/p/32230623
https://www.cnblogs.com/pinard/p/5970503.html