Industry news

深度学习里的一些优化算法

（本文参考AI圣经《深度学习》一书，仅作为学习交流）
本文梳理SGD，标准动量SGD，Nesterov动量SGD算法，以及Adagrad, AdaDelta，Adam，RMSProp，Nesterov动量RMSProp自适应学习率算法
在深度学习中我们定义了损失函数以后，会采取各种各样的方法来降低损失函数。不过损失函数的数值只是我们用来优化模型中参数的一个参考量，我们是通过优化损失函数来间接地优化模型参数，并提高模型的度量指标。假设我们需要优化的目标函数为 $J( heta)$ :
$J( heta)=E_{(x,y)\hat{p}_{data}}L(f(x; heta),y)$
其中 $L$ 是每个样本的损失函数， $f(x; heta),y)$ 是输入 $x$ 时所预测的输出， $y$ 是目标输出， $\hat{p}_{data}$ 是训练集上的经验分布。但理论上希望 $p_{data}$ 是真实的数据生成分布。在机器学习中，我们用经验分布来代替真实分布，毕竟你无法收集到所有的样本数据，而是仅采用训练集进行训练。但我们仍然不知道数据的分布是怎么样的，我们只能通过求期望，并将期望损失最小化来将这个机器学习问题转换为一个优化问题。我们优化的目的就是为了最小化经验风险：
$E_{(x,y)\hat{p}_{data}}L(f(x; heta),y)=\frac{1}{m}\sum^{m}_{i=1}L(f(x^{(i)}; heta),y^{(i)})$
其中 $m$ 是训练样本的数目。
基于这种最小化平均训练误差的训练过程被称为经验风险最小化。

在深度学习的训练中，训练集中的样本数量往往是成千上万的，通过遍历每一个样本对期望进行计算所需要的计算量是非常大的。在实际中，往往是在训练集中少量采样一些数据拿来计算，然后求出这些样本的平均值。
实际上可以找到两个理由来支撑为何采用小批量算法：
第一，n个样本的均值的标准差是 $\sigma/\sqrt{n}$ ，其中 $\sigma$ 是样本值真实的标准差。分母 $\sqrt{n}$ 说明样本数量的贡献是低于线性的，可以算一下，我们用100个样本和用10000个样本来计算均值标准差，多用了100倍的数据，却只降低了10倍的标准差。如果能够迅速求出估计值，而不是缓慢计算准确值，会加快算法的收敛速度。
第二，训练集中经常会存在冗余的情况，完全有可能出现相同数据，如果重复了m次，那么用小批量算法就可以少花m倍的时间。

随机梯度下降法（SGD）是一种非常经典的优化算法，常应用在机器学习中，尤其是深度学习中。首先从训练集中随机选取m个样本的生成得到一个小批量，然后计算他们的梯度均值。

算法:SGD在k个训练迭代的参数更新
输入：学习率 $\epsilon_k$
输入：初始参数 $heta$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度估计： $\hat{g}\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)}, heta),y^{(i)})$
更新参数： $heta\leftarrow heta-\epsilon\hat{g}$
end while

SGD中的超参数是学习率，在实际的训练中，我们需要逐步地降低学习率，因此将第 $k$ 步的学习率记为 $\epsilon_k$ ，通常采用指数衰减的策略对学习率进行调整。

动量是一个物理学中类比过来的概念，它是为了解决经典的SGD收敛速度慢的问题而提出的。它能够保留上一轮更新中的参数更新增量，并加入该轮的梯度。
参数更新变为： $heta \leftarrow heta+v$
$v$ 的更新为： $v \leftarrow \alpha v-\epsilon abla_{ heta}J( heta)$
其中 $\alpha$ 是动量参数， $abla_{ heta}J( heta)$ 是当前轮次计算得到的梯度。
可以发现参数 $heta$ 更新不再是仅仅加上梯度变化 $\hat{g}= abla_{ heta}J( heta)$ ，而是加了个速度 $v$ ，这个 $v$ 就表示引入的动量元素，通过式子也可以看出来：第一，它可以保留上一次的梯度信息，通过动量参数 $\alpha$ 来控制上一次的更新量对本次更新量的影响，注意到它是一个非负项，所以它起到了“惯性”的作用，上一次的增量大则带给本次更新的增量影响就大；如果上一次的增量小，那么它带给本次更新的增量影响就小。
可以对SGD算法和动量SGD算法进行对比：
经典SGD算法：
1.直接用梯度更新参数 $heta$ .
$heta\leftarrow heta-\epsilon\hat{g}$
动量SGD算法：

计算速度 $v$ 更新. 2. 利用速度 $v$ 来更新参数 $heta$ .
$\begin{aligned} &v \leftarrow \alpha v-\epsilon \hat{g}\\ & heta\leftarrow heta+v \end{aligned}$

给出动量SGD算法流程如下：

算法:引入动量的SGD在k个训练迭代的参数更新
输入：学习率 $\epsilon$ ，动量参数 $\alpha$
输入：初始参数 $heta$ ,初始速度 $v$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度估计： $\hat{g}\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)}, heta),y^{(i)})$
计算速度更新： $v \leftarrow \alpha v-\epsilon \hat{g}$
更新参数： $heta\leftarrow heta+v$
end while

Nesterov动量SGD算法与标准动量算法类似，只不过在计算梯度前对参数 $heta$ 进行了校正。使得在计算梯度之前给参数 $heta$ 加上一个动量因子，而不是原模原样地把上一次的 $heta$ 拿来求解梯度。可以做一下对比：
标准动量SGD算法中的梯度估计：
1.直接用上一次更新得到的 $heta$ 求梯度
$\hat{g}\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)}, heta),y^{(i)})$
Nesterov动量SGD算法中的梯度估计：
1.用上一次更新得到的 $heta$ 先求一个临时参数.
2.用临时参数求梯度.
$\begin{aligned} &\widetilde{ heta}\leftarrow heta+\alpha v\\ &\hat{g}\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},\widetilde{ heta}),y^{(i)})\\ \end{aligned}$

给出Nesterov动量的SGD算法流程如下：

算法:引入Nesterov动量的SGD在k个训练迭代的参数更新
输入：学习率 $\epsilon$ ，动量参数 $\alpha$
输入：初始参数 $heta$ ,初始速度 $v$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算临时参数： $\widetilde{ heta}\leftarrow heta+\alpha v$
计算梯度估计： $\hat{g}\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},\widetilde{ heta}),y^{(i)})$
计算速度更新： $v \leftarrow \alpha v-\epsilon \hat{g}$
更新参数： $heta\leftarrow heta+v$
end while

学习率本身就是很难调试的一个超参数，这是工业界公认的事情。动量算法只能在一定程度上缓解调参的压力，但代价是多引入了一个超参数。总有人会想有没有更简便的方法，于是就提出来了Adagrad, AdaDelta, Adam, RMSProp, 动量RMSProp等自适应学习率算法。本节梳理各个算法流程，并进行对比。

算法:Adagrad算法
输入：全局学习率 $\epsilon$
输入：初始参数 $heta$
输入：小常数 $\delta$ ，为了数值稳定大约设置为 $10^{-7}$
初始化梯度累积量 $r=0$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度估计： $g\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{ heta}),y^{(i)})$
累积平方梯度： $r \leftarrow r+g \odot g$
计算参数更新量： $\Delta heta \leftarrow-\frac{\epsilon}{\delta+\sqrt{r}}\odot g$
更新参数： $heta\leftarrow heta+\Delta heta$
end while

Adagrad算法可以说是与SGD算法的框架非常像了，我们来对比一下区别之处：
SGD算法中的参数更新：
1.直接用梯度来更新参数 $heta$
$heta\leftarrow heta-\epsilon g$
Adagrad算法中的参数更新：
1.梯度累积变量与梯度内积累加得到累积平方梯度.
2.利用累积平方梯度计算参数更新量 $\Delta heta$ 。
3.利用参数更新量 $\Delta heta$ 更新参数 $heta$ .
$\begin{aligned} &r \leftarrow r+g \odot g\\ &\Delta heta \leftarrow-\frac{\epsilon}{\delta+\sqrt{r}}\odot g\\ & heta\leftarrow heta+\Delta heta \end{aligned}$

算法:AdaDelta算法在第k轮的迭代
输入：衰减率 $\rho$ , 全局学习率 $\epsilon$
输入：初始参数 $heta_k$
初始化梯度累积量 $E[g^2]_0=0,E[\Delta heta ^2]_0=0$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度： $g_k \leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{ heta}),y^{(i)})$
累积梯度平方期望： $E[g^2]_k \leftarrow \rho E[g^2]_{k-1}+(1-\rho)g^2_k$
计算参数更新量： $\Delta heta_k \leftarrow-\frac{ \sqrt{E[\Delta heta^2]_{k-1}+\epsilon}}{\sqrt{E[g^2]_k+\epsilon}}g_k=\frac{RMS[\Delta heta]_{k-1}}{RMS[g]_{k}}g_k$
缓存累积更新： $E[\Delta heta^2]_k \leftarrow \rho E[\Delta heta^2]_{k-1}+(1-\rho)\Delta heta^2$
更新参数： $heta_{k+1}\leftarrow heta_k+\Delta heta_k$
end while

AdaDelta算法是adagrad算法的延伸和改进，他们的不同之处在于：
Adagrad算法中的参数更新：
1.梯度累积变量与梯度内积累加得到累积平方梯度.
2.利用累积平方梯度计算参数更新量 $\Delta heta$ 。
3.利用参数更新量 $\Delta heta$ 更新参数 $heta$ .
$\begin{aligned} &r \leftarrow r+g \odot g\\ &\Delta heta \leftarrow-\frac{\epsilon}{\delta+\sqrt{r}}\odot g\\ & heta\leftarrow heta+\Delta heta \end{aligned}$
AdaDelta算法中的参数更新：
1.计算累积平方期望 $E[g^2]_k$ .
2.计算参数更新量 $\Delta heta_k$ .
3.缓存累积更新 $E[\Delta heta^2]_k$ .
4.利用参数更新量 $\Delta heta$ 更新参数 $heta$ .
$\begin{aligned} &E[g^2]_k \leftarrow \rho E[g^2]_{k-1}+(1-\rho)g^2_k \\ &\Delta heta_k \leftarrow-\frac{ \sqrt{E[\Delta heta^2]_{k-1}+\epsilon}}{\sqrt{E[g^2]_k+\epsilon}}g_k=\frac{RMS[\Delta heta]_{k-1}}{RMS[g]_{k}}g_k\\ &E[\Delta heta^2]_k \leftarrow \rho E[\Delta heta^2]_{k-1}+(1-\rho)\Delta heta^2\\ & heta_{k+1}\leftarrow heta_k+\Delta heta_k\\ \end{aligned}$

算法:RMSProp算法
输入：全局学习率 $\epsilon$ ，衰减率 $\rho$
输入：初始参数 $heta$
输入：小常数 $\delta$ ，为了数值稳定大约设置为 $10^{-6}$
初始化梯度累积量 $r=0$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度估计： $g\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{ heta}),y^{(i)})$
累积平方梯度： $r \leftarrow \rho r+(1-\rho)g \odot g$
计算参数更新量： $\Delta heta \leftarrow-\frac{\epsilon}{\sqrt{\delta+r}}\odot g$
更新参数： $heta\leftarrow heta+\Delta heta$
end while

RMSProp算法实际上对AdaGrad算法做出了改进，修改了累积平方梯度和参数更新量的计算方法，在非凸情况下比AdaGrad效果较好。
RMSProp算法和AdaGrad算法区别在于：
AdaGrad算法：
1.梯度累积变量与梯度内积累加得到累积平方梯度.
2.利用累积平方梯度计算参数更新量 $\Delta heta$ 。
$\begin{aligned} &r \leftarrow r+g \odot g\\ &\Delta heta \leftarrow-\frac{\epsilon}{\delta+\sqrt{r}}\odot g\\ \end{aligned}$
RMSProp算法：
1.梯度累积变量与梯度内积累加得到累积平方梯度.
2.利用累积平方梯度计算参数更新量 $\Delta heta$ 。
$\begin{aligned} &r \leftarrow \rho r+(1-\rho)g \odot g\\ &\Delta heta \leftarrow-\frac{\epsilon}{\sqrt{\delta+r}}\odot g\\ \end{aligned}$

算法:Nesterov动量RMSProp算法
输入：全局学习率 $\epsilon$ ，衰减率 $\rho$ ，动量系数 $\alpha$
输入：初始参数 $heta$ , 初始速度参数 $v$
初始化梯度累积量 $r=0$
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算临时参数： $\widetilde{ heta} \leftarrow heta+\alpha v$
计算梯度估计： $g\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{\widetilde{ heta}}),y^{(i)})$
累积平方梯度： $r \leftarrow \rho r+(1-\rho)g \odot g$
计算速度更新： $v \leftarrow \alpha v-\frac{\epsilon}{\sqrt{r}}\odot g$
更新参数： $heta\leftarrow heta+v$
end while

给出RMSProp算法与动量RMSProp算法的区别：
RMSProp算法：
1.梯度累积变量与梯度内积累加得到累积平方梯度.
2.利用累积平方梯度计算参数更新量 $\Delta heta$ .
3.利用参数更新量 $\Delta heta$ 更新参数 $heta$ .
$\begin{aligned} &r \leftarrow \rho r+(1-\rho)g \odot g\\ &\Delta heta \leftarrow-\frac{\epsilon}{\sqrt{\delta+r}}\odot g\\ & heta\leftarrow heta+\Delta heta \\ \end{aligned}$
Nesterov动量RMSProp算法：
1.计算临时参数 $\widetilde{ heta}$
2.利用临时参数计算梯度g$$
3.计算累积平方梯度 $r$
4.计算速度更新 $v$
5.利用速度更新参数 $heta$

$\begin{aligned} & \widetilde{ heta} \leftarrow heta+\alpha v\\ &g\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{\widetilde{ heta}}),y^{(i)})\\ &r \leftarrow \rho r+(1-\rho)g \odot g\\ &v \leftarrow \alpha v-\frac{\epsilon}{\sqrt{r}}\odot g\\ & heta\leftarrow heta+v \\ \end{aligned}$

算法:Adam算法
输入：全局学习率 $\epsilon$ （建议默认0.001）
输入：矩估计的指数衰减率， $\rho_1,\rho_2$ 在区间 $[0,1)$ 内（建议默认0.9和0.999）
输入：用于数值稳定的小常数 $\delta$ (建议默认 $10^{-7}$ )
输入：初始参数 $heta$
初始化一阶和二阶矩变量s=0, r=0
初始化时间步t=0
while 未满足停止条件 do
从训练集中采集包含m个样本 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 的小批量，其中数据 $x^{(i)}$ 和对应目标 $y^{(i)}$
计算梯度： $g\leftarrow \frac{1}{m} abla_{ heta}L(f(x^{(i)},{ heta}),y^{(i)})$
$t \leftarrow t+1$
更新有偏一阶矩估计： $s \leftarrow \rho_1s+(1-\rho_1)g$
更新有偏二阶矩估计： $r \leftarrow \rho_2r+(1-\rho_2)g\odot g$
修正一阶矩的偏差： $\hat{s} \leftarrow \frac{s}{1-\rho^t_1}$
修正二阶矩的偏差： $\hat{r} \leftarrow \frac{r}{1-\rho^t_2}$
计算更新量： $\Delta heta \leftarrow -\epsilon\frac{\hat{s}}{\sqrt{\hat{r}}+\delta}$
计算更新： $heta \leftarrow heta+\Delta heta$
end while