机器学习：优化算法（一）—— 梯度下降

梯度下降法一般原理

梯度下降法(gradient descent)是求解无约束最优化问题的一种最常用的迭代算法。当目标函数是凸函数时，梯度下降法的解是全局最优解。一般情况下，其解不保证是全局最优解，收敛速度也未必是很快的。

无约束最优化问题

假设$f(x)$是$\mathbb{R}^n$上具有一阶连续偏导的函数，求解无约束最优化问题：

$$x^*=\underset{x \in \mathbb{R}^n}{min}\ f(x)$$

求解步骤

1、选取合适的初值$x_0$，置k=0
2、计算梯度 $g_k$，若 $\left | g_k \right | < \varepsilon$，则停止计算，得到$x^*=x_k$，否则沿负梯度方向(目标函数下降最快的方向)更新参数 $x\leftarrow x-\eta \nabla_xf(x)$

各种梯度下降法的变形

以下实例，以平方损失函数作为目标函数：

$$\underset{\theta }{min}\ L(\theta)$$ $$L(\theta) = \frac{1}{2m}\sum_{i=1}^{m}(\hat{y}_i-y_i)^2$$

• $y_i$：第i个样本的实际值
• $\hat{y}_i$：第i个样本的预测值
• $\theta$：模型参数

在进入正题之前，先通过以下两个动画来感知一下不同梯度下降方法的实际效果：

批量梯度下降/最速梯度下降法(Batch Gradient Descent，BGD)

批量梯度下降法（Batch Gradient Descent，简称BGD）是梯度下降法最原始的形式，它的具体思路是每次迭代时都使用所有的样本来来更新模型参数，其数学形式如下：

$$\theta _k = \theta _{k-1} - \eta \nabla_{\theta}L ,\ k=0,1,2...$$

• $k$：迭代次数
• $\eta $: 学习率
• $\nabla_{\theta} L$: 损失函数关于参数的梯度

训练过程示意图：

• 优点：易于并行实现
• 缺点：
  • 样本很多时，训练过程很慢；
  • 固定的学习率，太小速度慢，太大容易发生震荡

随机梯度下降法(stochastic gradient descent，SGD)

批量梯度下降在每次迭代过程都需要计算所有训练样本，当样本数量很大时训练过程会很慢，一种解决思路是使用随机梯度下降法Stochastic Gradient Descent，简称SGD），每次迭代从样本中随机选取一个样本来更新模型参数（m=1）:

$$\theta _k = \theta _{k-1} - \eta \frac{1}{2}(\hat{y_i}-y_i)\frac{\partial y_i}{\partial \theta}$$

训练过程:

• 优点：训练速度快
• 缺点：
  • 不易于并行实现，容易受噪声影响
  • 固定的学习率，太小速度慢，太大容易发生震荡

小批量梯度下降法(Mini-batch Gradient Descent，MBGD)

MBGD融合了BGD和SGD的优点，既方便并行实现又不易受到噪声影响，每次迭代从样本中随机选取小批量的样本来更新模型参数（b<m）（是一种用样本来估计总体的方法）:

$$L(\theta) = \frac{1}{2b}\sum_{i=1}^{b}(\hat{y}_i-y_i)^2$$ $$\theta _k = \theta _{k-1} - \eta \nabla_{\theta}L ,\ k=0,1,2...$$

• 优点：训练速度快、易于并行实现
• 缺点：固定的学习率，不能适应各个参数、训练过程

实践中的梯度下降一般会线性衰减学习率直到第$\tau $次迭代:

$$\eta _k = (1-\alpha )\eta _0 + \alpha \epsilon _{\tau }$$

• $\alpha=\frac{k}{\tau}$：:$\tau$步迭代之后会使学习率保持不变。

动量算法

动量算法是一种模拟动力学的梯度下降方法，旨在加速学习，特别是处理高曲率、小但一致的梯度，或是带噪声的梯度。

想象在冰面上滑行的冰球，每当它沿着冰面最陡的部分下降时，它会累积该方向上的滑行速度。与此类似，如果将损失函数值看做是冰面的高度，将损失函数的负梯度看做是冰球所受重力，将更新参数的步长看做是冰球的速度，那么步长会累积指数衰减的历史梯度：

$$\begin{align*} &v\leftarrow \alpha v-\eta \nabla_{\theta}L\\ &\theta \leftarrow \theta +v \end{align*}$$

• $v$：速度，累积了指数衰减的历史梯度；
• $\alpha \in [0,1)$:超参数，一般取0.5,0.9,0.99，决定了历史梯度的贡献衰减的有多快，越大衰减的越慢，之前梯度对现在方向的影响也越大

如果动量算法总是观测到梯度$g$，那么它在方向$-g$上不停加速直至达到最终速度，步长为$\frac{\eta \left | g \right |}{1-\alpha }$，对应着动量算法比梯度下降法快$\frac{1}{1-\alpha }$倍。

优点：训练速度快
缺点：引入了额外的超参数

---

学习率对模型的性能有显著影响，是难以设置的超参数之一。损失函数高度敏感与参数空间中的某些方向，而不敏感于其他方向，动量算法可以一定程度缓解这些问题，但必须引入额外的超参数。改进思路是使用自适应的学习率：

1. 对不同参数设置不同的学习率
2. 随着训练过程自动调整学习率

下面要讲的几种方法正是基于这样的思路对梯度下降算法进行了改进。

AdaGred算法

AdaGred算法按照历史梯度和的平方根比例缩放学习率，实现对不同参数学习率有不同的衰减速度，历史偏导较大的参数有较大的衰减速度：

$$\begin{align*} &\theta _{k,i} = \theta _{k-1,i} - \frac{\eta }{\sqrt{G_{k-1,i}+\delta }}g_{k-1,i}\\ &g_{k,i} = \frac{\partial L}{\partial \theta _i}\\ &G_{k,i} = \sum_{j=1}^{k}g_{k,i} \end{align*}$$

• $G_{k,i}$：$\theta_i$历史k次偏导和的平方根;
• $\delta$:平滑项，防止除零操作，一般取值1e−8;

RMSProp算法

RMSProp算法改变AdaGred算法中梯度累积为指数加权平均，以在非凸设定下效果更好。

$$G_{k,i} = \rho G_{k-1,i} + (1-\rho)g_{k-1,i}^2$$

Adam