优化器Optimal

未完成！！！！！！

神经网络的训练主要是通过优化损失函数来更新参数，而面对庞大数量的参数的更新，优化函数的设计就显得尤为重要，下面介绍一下几种常用的优化器及其演变过程：

【先说明一下要用到符号的含义】：

损失函数里一般有两种参数，一种是控制输入信号量的权重(Weight, 简称$ w $），另一种是调整函数与真实值距离的偏差（Bias，简称$ b $），在这里我们将参数统一表示为$ \theta_t \in R^{d} $，损失函数为$J(\theta)$，学习率为$\eta$ 。损失函数关于当前参数的梯度：$g_t = \nabla J(\theta_t)$

损失函数用来衡量机器学习模型的精确度。一般来说，损失函数的值越小，模型的精确度就越高。想要使损失函数最小化，就要用到梯度的概念。梯度是指向变化最快的方向。知道了该往哪里走，接下来就是该走多长，这用学习率$\eta$来控制

【1】梯度下降

参数更新公式：$\theta_{t+1} = \theta_t - g_t $
原始梯度下降法在迭代每一次梯度下降的过程中，都对所有样本数据的梯度进行计算，理论上可以找到全局最优解。虽然最终得到的梯度下降的方向较为准确，但是运算会耗费过长的时间。两种改进方法为：
1.小批量样本梯度下降（Mini Batch GD)
小批量的意思就是算法在每次梯度下降的过程中，只选取一部分的样本数据进行计算梯度，可以明显地减少梯度计算的时间。
2. 随机梯度下降（Stochastic GD)
随机梯度下降算法只随机抽取一个样本进行梯度计算，每次都是往局部最优的方向下降，由于每次梯度下降迭代只计算一个样本的梯度，因此运算时间比小批量样本梯度下降算法还要少很多，但由于训练的数据量太小（只有一个），因此下降路径很容易受到训练数据自身噪音的影响。（只选取一个样本求梯度也能基本收敛的原因好像和期望有关）。

随着每次传入样本的不同，计算得到的梯度也会不同，这就造成了偏差，所以Mini Batch和SGD都不可避免会发生震荡

虽然梯度是指向变化最快的方向，但还是有优化空间的，主要是因为我们算的是每个点的梯度，而我们梯度的步长并不是无限小。而有了这个确定的步长，下降路径就不会和最优路径重合。

从上图我们可以看到，梯度的下降过程是震荡的，一次梯度的下降是横向向量和纵向向量的和，我们的目的是使梯度指向最优点的方向并增加步长，而这可以通过将横向向量变长，纵向向量变短来实现，而考虑到向量是有方向的，在垂直方向上，前后两个向量是反向的，相加后就可以实现纵向向量变短的目的，在水平方向上，前后两个向量是同向的，相加后就可以实现横向向量的变长，这正是接下来介绍的动量法的思想，将历史信息考虑进去。

【2】Momentum--动量法

Momentum认为梯度下降过程可以加入惯性，就是将历史梯度考虑进来：
参数更新公式如下：
$m_{t+1} = \beta m_t + \eta g_t $
$\theta_{t+1} = \theta_t - m_{t+1} $
如果将$m_{t+1} $写开来就是：$m_{t+1} = \eta\sum_{i=1}^t g_t $
此时$\theta_{t+1} = \theta_t -\eta\sum_{i=1}^t g_t $

【3】Nesterov Accelerated Gradient

上述图片来自论文《An overview of gradient descent optimization algorithms》Momentum首先计算当前的梯度（图3中的蓝色小矢量），然后向更新的累积梯度（蓝色大矢量）方向大跳，而NAG首先向之前的累积梯度（棕色矢量）方向大跳，测量梯度，然后进行校正（绿色矢量）。这种预见性的更新可以防止我们走得太快，并导致反应能力的提高。
在Momentum的基础上将当前时刻的梯度$g_t$换成下一时刻的梯度$\nabla J(\theta_t - \beta m_{t-1})$
参数更新公式为：
$m_{t+1} = \beta m_t + \eta\nabla J(\theta_t - \beta m_{t-1}) $
$\theta_{t+1} = \theta_t - m_{t+1} $

【4】AdaGrad（Adaptive gradient algorithm 自适学习率应梯度下降）

Adagrad 算法解决的问题：算法不能根据参数的重要性而对不同的参数进行不同程度的更新的问题。
SGD及其变种均以同样的学习率更新每个纬度的参数，但深度神经网络往往包含大量的参数，这些参数并不是总会用得到。对于经常更新的参数，我们已经积累了大量关于它的只是，不希望受到单个样本太大的影响，希望学习速率慢一些；对于偶尔更新的参数，我们了解的信息太少，希望能从每个偶然出现的样本身上多学一些，即学习速率大一些。因此，AdaGrad诞生了，它就是考虑了对不同维度的参数采用不同的学习率。

以前，一次性对所有参数$\theta$ 进行更新，因为每个参数$\theta_i $ 都使用相同的学习率$\eta$ 。由于Adagrad在每个时间步骤$t$对每个参数$\theta_i $使用不同的学习率，我们首先展示Adagrad的每个参数更新，然后将其矢量化。为简洁起见，定义$g_{t,i}$为目标函数的梯度，即在时间步长$t$时对参数$\theta_i $的梯度。

参数更新公式：
$ v_{t,i} = \sum_{i=1}^t{g_{t,i}^2} $
$V_t = diag(v_{t,1},v_{t,2},\cdots,v_{t,d}\in R^{d \times d}) $
$ \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt V_t+\epsilon} $

另一种公式表示：

$ E[g^2]_t=E[g^2]_{t-1}+g_t^2$
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{E[g^2]_t+\epsilon}}\times g_t$

特点：前期：较小的时候，分母较大，能够放大梯度。后期：较大的时候，分母较小，能够约束梯度。适合处理稀疏梯度 \\缺点：因为所有梯度一直是累加的，故学习率会一直减小趋于0

【5】RMSprop

RMSprop和下一个提到的优化器都是要解决Adagrad的缺点提出的改进算法，既然Adagrad的缺点是梯度平方的累加，那我们就减少累加的梯度，具体使用指数衰减移动平均算法来实现。

参数更新：
$ v_{t,i} = \beta v_{t-1,i} + (1-\beta)g_{t,i}^2 $
$V_t = diag(v_{t,1},v_{t,2},\cdots,v_{t,d}\in R^{d \times d}) $
$ \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt V_t+\epsilon} $

另一种公式表示：

$ E[g^2]_t=\beta E[g^2]_{t-1}+(1-\beta)g_t^2$
$\theta_{t+1}=\theta_t-\frac{\eta}{\sqrt{E[g^2]_t+\epsilon}}\times g_t$

【6】Adadelta

RMSprop优化器虽然可以对不同的权重参数自适应的改变学习率，但仍要指定超参数$\eta$，AdaDelta优化器对RMSProp算法进一步优化：AdaDelta算法额外维护一个状态变量$\delta x_t$，并使用$RMS[\delta x]_t$代替RMSprop中的学习率参数$\eta$，使AdaDelta优化器不需要指定超参数.
参数更新公式：
$ E[g^2]_t = \beta E[g^2]_{t-1} + (1-\beta )g_t^2 $ \ 注：符号$E[]$表示期望
$E[\Delta x^2]_{t-1}=\beta \times E[\Delta x^2]_{t-2}+(1-\beta)\times \Delta x_{t-2}^2$
$RMS[g]_t=\sqrt{E[g^2]_t+\epsilon}$
$RMS[\Delta x]_{t-1}=\sqrt{E[\Delta x^2]_{t-1}+\epsilon}$
$\theta_{t+1} = \theta_t - \frac {RMS[\Delta x]_{t-1}}{RMS[g]_t} \otimes g_t$

【7】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 $
$ \hat m_t = \frac{m_t}{1-\beta_1^t} $
$ \hat v_t = \frac{v_t}{1-\beta_2^t} $
$ \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat v_t} +\epsilon} \hat m_t $

【8】AdaMaX

$ m_t = \beta_1 m_{t-1}+(1-\beta_1)g_t $
$ \begin{equation}\begin{split} u_t &= \beta_2^{\infty}v_{t-1} + (1-\beta_2^\infty)\vert g_t \vert^\infty \\ &=max(\beta_2 \cdot v_{t-1},\vert g_t \vert) \end{split}\end{equation} $
$ \theta_{t+1}=\theta_t - \frac{\eta}{u_t}\hat m_t $

【9】Nadam

$ m_t=\gamma m_{t-1}+\eta g_t $
Adam为：$ \theta_{t+1}=\theta-(\gamma m_{t-1}+\eta g_t) $
对Adam的改进为：$ \theta_{t+1}=\theta-(\gamma m_t+\eta g_t) $
$\theta_{t+1}=\theta_t - \frac{\eta}{\sqrt{\hat v_t} + \epsilon}(\beta_1 \hat m_t + \frac{(1-\beta_1)g_t}{1-\beta_1^t}) $

参考资料：
[https://zhuanlan.zhihu.com/p/110104333]([论文阅读] 综述梯度下降优化算法)
[https://zhuanlan.zhihu.com/p/68468520](梯度下降算法（Gradient Descent)的原理和实现步骤)
https://zhuanlan.zhihu.com/p/351134007
论文《An overview of gradient descent optimization algorithms》