Dive into Deep Learning-优化算法(2)_dive into deeplearning

1. 梯度下降

• 为什么梯度下降可以优化目标函数：以一维梯度下降为例$f:\mathbb{R}\to \mathbb{R}$，利用泰勒展开，可以得到：$f(x+ϵ)=f(x)+ϵf^{\prime }(x)+O({ϵ}^2)$，此时假定步长$\eta >0$，取$ϵ=-\eta f^{\prime }(x)$，代入泰勒展开式中可以得到$f(x-\eta f^{\prime }(x))=f(x)-\eta f^{\prime 2}(x)+O({\eta }^2{f}^{\prime 2}(x))$，由于式中$\eta f^{\prime 2}(x)>0$，所以总可以调整$\eta$使得高阶项影响变小，$f(x-\eta f^{\prime }(x))<f(x)$，所以如果我们使用$x\leftarrow x-\eta f^{\prime }(x)$就可以使得函数$f(x)$的值减小；
• 学习率：上式中的$\eta$，需要在更新缓慢和迭代震荡中选择合适的值；
• 多元梯度下降，和上面类似，只是对于输入$x=[x_1,x_2,\cdots ,x_d{]}^T$，目标函数$f:{\mathbb{R}}^d\to \mathbb{R}$，相应的梯度也是多元的，$\nabla f(x)=[\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\cdots ,\frac{\partial f(x)}{\partial x_d}{]}^T$，对应的泰勒展开$f(x+ϵ)=f(x)+{ϵ}^T\nabla f(x)+O(||ϵ|{|}^2)$
• 自适应方法(牛顿法)：上面的例子可以看出学习率比较敏感，需要仔细调整，借助泰勒展开，$f(x+ϵ)=f(x)+{ϵ}^T\nabla f(x)+\frac{1}{2}{ϵ}^T{\nabla }^{2}f(x)ϵ+O(||ϵ|{|}^3)$，其中将$H={\nabla }^{2}f(x)$定义为$f$的Hessian矩阵，$d\times d$，其中H的储存代价对于深度学习来说很高，不适用，现在暂时不考虑适用性问题，$f$的最小值处$\nabla f=0$，可以得到$\nabla f(x)+Hϵ=0$，得到$ϵ=-H^{-1}\nabla f(x)$，更新$x:x=x-\eta H^{-1}\nabla f(x)$

2. 随机梯度下降

• 深度学习中目标函数是训练数据集中每个样本损失函数的平均值即$f(x)=\frac{1}{n}{\sum }_{i=1}^n{f}_i(x)$，其中$n$是样本数目，对应的梯度计算为$\nabla f(x)=\frac{1}{n}{\sum }_{i=1}^n\nabla f_i(x)$，一次迭代的计算代价为$O(n)$；
• 随机梯度下降$SGD$在每次迭代中都随机采样一个索引$i$，之后计算梯度$x\leftarrow x-\eta \nabla f_i(x)$来进行更新，每次迭代的复杂度降为$O(1)$，而且随机梯度$\nabla f_i(x)$是完整梯度$\nabla f(x)$的无偏估计${\mathbb{E}}_i\nabla f_i(x)=\frac{1}{n}{\sum }_{i=1}^n{f}_i(x)=\nabla f(x)$，但是此时梯度下降每次迭代都存在噪声，而且当迭代到最小值附近的时候仍然会收到噪声的影响，需要动态的调整学习率；
• 动态学习率：与时间相关的学习率$\eta (t)$来取代常量$\eta$

3. 小批量随机梯度下降

• 核心是为了计算效率；
• 平均梯度减小了方差；

4. 动量法

• $v_t=\beta v_{t-1}+g_{t,t-1}$，其中$g_{t,t-1}$为此时的梯度，$v_t$是动量，累加了过去的梯度，每次迭代$x_t\leftarrow x_{t-1}-{\eta }_t{v}_t$
• 有效的场景：在不同维度方向上的变量的梯度大小差异比较大的时候有效，此时假设不使用动量，那么大的学习率将会使大梯度变量方向发散，小的学习率会使小梯度方向变化缓慢；
• 加快了收敛速度；
• 由于对过去的数据进行了指数降权，有效梯度数为$\frac{1}{1-\beta }$；

5. AdaGrad算法

• 稀疏特征：在模型训练中偶尔出现的，例如语言模型训练时罕见词，在训练的时候，对应常见特征的参数收敛快，而罕见特征的参数收敛慢，换句话说，学习率要么对于常见特征而言降低太慢，要么对于不常见特征而言降低太快；
• 一个解决办法是记录看到的特定特征的次数，并以此来调整学习率，例如$s(i,t)$表示截止$t$时观察到的功能$i$的次数，学习率由原来$\eta =\frac{{\eta }_0}{\sqrt{t+c}}\to \frac{{\eta }_0}{\sqrt{s(i,t)+c}}$，允许每个维度拥有自己的学习率；
• AdaGrad算法就是将粗略的计数器$s(i,t)$替换为先前观察所得梯度的平方之和来解决这个问题，使用$s(i,t+1)=s(i,t)+({\partial }_{i}f(x){)}^2$来调整学习率；
• $g_t={\partial }_{w}l(y_t,f(x_t,w)),s_t=s_{t-1}+g_t^2,w_t=w_{t-1}-\frac{\eta }{\sqrt{s_t+ϵ}}\cdot g_t$；

6. RMSProp算法

• Adagrad算法中$s_t$是梯度平方的累加，会持续增长，几乎是线性递增，迭代后期学习率下降很快，加爵该问题按照动量的方式，公式如下：
• $s_t\leftarrow \gamma s_{t-1}+(1-\gamma )g_t^2，x_t\leftarrow x_{t-1}-\frac{\eta }{\sqrt{s_t+ϵ}}\odot g_t$；

7. Adadelta算法

• 是AdaGrad的另一种变体，使用了两个状态变量，$s_t$用于存储梯度二阶导数的泄露平均值，$\Delta x_t$用于存储模型本身中参数变化二阶导数的泄露平均值，也就是调整之后梯度的平方泄露平方值，公式如下：
• $s_t=\rho s_{t-1}+(1-\rho )g_t^2$，调整之后的梯度为$g_t^{\prime }=\frac{\sqrt{\Delta x_{t-1}+ϵ}}{\sqrt{s_t+ϵ}}\odot g_t$，$\Delta x_t=\rho \Delta x_{t-1}+(1-\rho )g_t^{\prime 2}$，然后使用缩放之后的梯度进行更新$x_t=x_{t-1}-g_t^{\prime }$；
• 在某种程度上，Adadelta没有学习率参数。相反，它使用参数本身的变化率来调整学习率

8. Adam算法

• 公式如下：
• 动量和二次矩的指数加权移动平均值计算$v_t\leftarrow {\beta }_1{v}_{t-1}+(1-{\beta }_1)g_t,s_t\leftarrow {\beta }_2{s}_{t-1}+(1-{\beta }_2)g_t^2$，因为如果初始化$v_0=s_0=0$会获得一个相当大的初始偏差，所以通过使用${\sum }_{i=0}^t{\beta }^i=\frac{1-{\beta }^t}{1-\beta }$来解决，相应的标准化状态变量${\hat{v}}_t=\frac{v_t}{1-{\beta }_1^t},{\hat{s}}_t=\frac{s_t}{1-{\beta }_2^t}$，有了这两个状态之后，对梯度进行重新缩放$g_t^{\prime }=\frac{\eta {\hat{v}}_t}{\sqrt{{\hat{s}}_t}+ϵ}$，最后对变量进行更新$x_t\leftarrow x_{t-1}-g_t^{\prime }$

ref
https://zh.d2l.ai/chapter_optimization/adam.html