数值优化算法【2】-- 梯度下降算法

本节介绍梯度下降（gradient descent）的工作原理。虽然梯度下降在深度学习中很少被直接使用，但理解梯度的意义，以及沿着梯度反方向更新模型参数以降低目标函数值的原理，是后面各种优化方法的基础。 梯度下降法又被称为最速下降法，是获得数值解的一种常用算法，主要分为批量梯度下降（Batch Gradient Descent）、随机梯度下降（Stochastic Gradient Descent）以及小批量梯度下降（Mini-Batch Gradient Descent）三种不同的形式。

一、理解梯度下降

（1）一维梯度下降

先以简单的一维梯度下降为例，解释梯度下降算法可能降低目标函数值的原因。

假设连续可导的函数 $ J: \mathbb{R} \rightarrow \mathbb{R} $ 的输入和输出都是标量。给定绝对值足够小的数 $ \epsilon $ ，根据泰勒展开公式，得到以下的近似：

J(x+ϵ)≈J(x)+ϵJ′(x).J(x + \epsilon) \approx J(x) + \epsilon J'(x) .

这里 $ J’(x) $ 是函数 $ J $ 在 $ x $ 处的梯度，一维函数的梯度是一个标量，和导数等价。

接下来，找到一个常数 $ \eta > 0 $ ，使得 $ \left|\eta J’(x)\right| $ 足够小，那么可以将 $ \epsilon $ 替换为 $ -\eta J’(x) $ 并得到 $$ J(x - \eta J’(x)) \approx J(x) - \eta J’(x)^2 $$ 。

如果导数 $ J’(x) \neq 0 $ ，那么 $ \eta J’(x)^2>0 $ ，所以 $$ J(x - \eta J’(x)) \lesssim J(x) $$ 。这意味着，如果通过 $$ x \leftarrow x - \eta J’(x) $$ 来迭代 $ x $ ，函数 $ J(x) $ 的值可能会降低。因此在梯度下降中，我们先选取一个初始值 $ x $ 和常数 $ \eta > 0 $ ，然后不断通过上式来迭代 $ x $ ，直到达到停止条件，例如 $ J’(x)^2 $ 的值已足够小或迭代次数已达到某个值。对于机器学习和深度学习任务，此处的 $ x $ 即为我们要学习的模型参数。

下面我们以目标函数 $ J(x)=x^2 $ 为例来看一看梯度下降是如何工作的。虽然我们知道最小化 $ J(x) $ 的解析解为 $ x=0 $ ，但这里依然使用这个简单函数来观察 $ x $ 是如何被迭代的。使用 $ x=10 $ 作为初始值，并设 $ \eta=0.2 $ 。使用梯度下降对 $ x $ 迭代10次，可见最终 $ x $ 的值较接近最优解。下图绘制出了自变量 $ x $ 的迭代轨迹。

（2）学习率的概念

上述梯度下降算法中的正数 $ \eta $ 通常叫作学习率。这是一个超参数，需要人工设定。如果使用过小的学习率，会导致 $ x $ 更新缓慢从而需要更多的迭代才能得到较好的解。

下面展示使用学习率 $ \eta=0.05 $ 时自变量 $ x $ 的迭代轨迹。可见，同样迭代10次后，当学习率过小时，最终 $ x $ 的值依然与最优解存在较大偏差。

如果使用过大的学习率， $ \left|\eta J’(x)\right| $ 可能会过大从而使一阶泰勒展开公式不再成立：这时我们无法保证迭代 $ x $ 会降低 $ J(x) $ 的值。举个例子，当设学习率 $ \eta=1.1 $ 时，可以看到 $ x $ 不断越过最优解 $ x=0 $ 并逐渐发散。

（3）多维梯度下降

在了解了一维梯度下降之后，我们再考虑一种更广义的情况：目标函数的输入为向量，输出为标量。

假设目标函数 $ J: \mathbb{R}^d \rightarrow \mathbb{R} $ 的输入是一个 $ d $ 维向量 $ \boldsymbol{x} = [x_1, x_2, \ldots, x_d]^\top $ 。目标函数 $ J(\boldsymbol{x}) $ 有关 $ \boldsymbol{x} $ 的梯度是一个由 $ d $ 个偏导数组成的向量：

∇xJ(x)=[∂J(x)∂x1,∂J(x)∂x2,…,∂J(x)∂xd]⊤\nabla_{\boldsymbol{x}} J(\boldsymbol{x}) = \bigg[\frac{\partial J(\boldsymbol{x})}{\partial x_1}, \frac{\partial J(\boldsymbol{x})}{\partial x_2}, \ldots, \frac{\partial J(\boldsymbol{x})}{\partial x_d}\bigg]^\top

为表示简洁，我们用 $ \nabla J(\boldsymbol{x}) $ 代替 $ \nabla_{\boldsymbol{x}} J(\boldsymbol{x}) $ 。梯度中每个偏导数元素 $ \partial J(\boldsymbol{x})/\partial x_i $ 代表着 $ J $ 在 $ \boldsymbol{x} $ 有关输入 $ x_i $ 的变化率。为了测量 $ J $ 沿着单位向量 $ \boldsymbol{u} $ （即 $ |\boldsymbol{u}|=1 $ ）方向上的变化率，在多元微积分中，我们定义 $ J $ 在 $ \boldsymbol{x} $ 上沿着 $ \boldsymbol{u} $ 方向的方向导数为

DuJ(x)=lim⁡h→0J(x+hu)−J(x)h.\text{D}_{\boldsymbol{u}} J(\boldsymbol{x}) = \lim_{h \rightarrow 0} \frac{J(\boldsymbol{x} + h \boldsymbol{u}) - J(\boldsymbol{x})}{h}.

依据方向导数性质，以上方向导数可以改写为

DuJ(x)=∇J(x)⋅u\text{D}_{\boldsymbol{u}} J(\boldsymbol{x}) = \nabla J(\boldsymbol{x}) \cdot \boldsymbol{u}

方向导数 $ \text{D}{\boldsymbol{u}} J(\boldsymbol{x}) $ 给出了 $ J $ 在 $ \boldsymbol{x} $ 上沿着所有可能方向的变化率。为了最小化 $ J $ ，我们希望找到 $ J $ 能被降低最快的方向。因此，我们可以通过单位向量 $ \boldsymbol{u} $ 来最小化方向导数 $ \text{D}{\boldsymbol{u}} J(\boldsymbol{x}) $ 。

由于 $ \text{D}{\boldsymbol{u}} J(\boldsymbol{x}) = |\nabla J(\boldsymbol{x})| \cdot |\boldsymbol{u}| \cdot \text{cos} (\theta) = |\nabla J(\boldsymbol{x})| \cdot \text{cos} (\theta) $ ，其中 $ \theta $ 为梯度 $ \nabla J(\boldsymbol{x}) $ 和单位向量 $ \boldsymbol{u} $ 之间的夹角，当 $ \theta = \pi $ 时， $ \text{cos}(\theta) $ 取得最小值 $ -1 $ 。因此，当 $ \boldsymbol{u} $ 在梯度方向 $ \nabla J(\boldsymbol{x}) $ 的相反方向时，方向导数 $ \text{D}{\boldsymbol{u}} J(\boldsymbol{x}) $ 被最小化。因此，我们可能通过梯度下降算法来不断降低目标函数 JJ 的值：

x←x−η∇J(x)\boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla J(\boldsymbol{x})

同样，其中 $ \eta $ （取正数）称作学习率。

下面我们构造一个输入为二维向量 $ \boldsymbol{x} = [x_1, x_2]^\top $ 和输出为标量的目标函数 $ J(\boldsymbol{x})=x_1^2+2x_2^2 $ 。那么，梯度 $ \nabla J(\boldsymbol{x}) = [2x_1, 4x_2]^\top $ 。我们将观察梯度下降从初始位置 $ [-5,-2] $ 开始对自变量 $ \boldsymbol{x} $ 的迭代轨迹，图为学习率= $ 0.1 $ 时自变量的迭代轨迹。使用梯度下降对自变量 $ \boldsymbol{x} $ 迭代20次后，可见最终 $ \boldsymbol{x} $ 的值较接近最优解 $ [0,0] $ 。

二、批量梯度下降法

在每一次迭代中，最早的梯度下降使用整个训练数据集来计算梯度，因此它有时也被称为批量梯度下降（batch gradient descent）。批量梯度下降法遍历全部数据集计算一次损失函数，然后反向传播计算每个参数的梯度，而后对参数进行更新迭代。

（1）优点：

  • 一次迭代对所有样本计算，利用矩阵进行计算，实现了并行。
  • 全数据集确定的梯度方向能够更好地代表样本总体，向极值收敛的速度快。
  • 当目标函数为凸函数时，BGD一定能够得到全局最优。

（2）缺点：

  • 当样本数目m很大时，每迭代一步都需要对所有样本计算，单轮(epoch)训练过程会很慢。

  • 不支持在线学习，即样本更新时需要重新计算。

三、随机梯度下降法

在深度学习里，目标函数通常是训练数据集中有关各个样本的损失函数的平均。设 $ f_i(\boldsymbol{x}) $ 是有关“索引”为 $ i $ 的训练数据样本的损失函数， $ n $ 是训练数据样本数， $ \boldsymbol{x} $ 是模型的参数向量，那么目标函数定义为

J(x)=1n∑i=1nJi(x).J(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n J_i(\boldsymbol{x}).

目标函数在 $ \boldsymbol{x} $ 处的梯度计算为：

∇J(x)=1n∑i=1n∇Ji(x).\nabla J(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla J_i(\boldsymbol{x}).

如果使用梯度下降，每次自变量迭代的计算开销为 $ \mathcal{O}(n) $ ，它随着 $ n $ 线性增长。因此，当训练数据样本数很大时，梯度下降每次迭代的计算开销很高。

随机梯度下降（stochastic gradient descent，SGD）减少了每次迭代的计算开销。在随机梯度下降的每次迭代中，我们随机均匀采样的一个样本索引 $ i\in{1,\ldots,n} $ ，并计算梯度 $ \nabla J_i(\boldsymbol{x}) $ 来迭代 $ \boldsymbol{x} $ ：

x←x−η∇fi(x).\boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla f_i(\boldsymbol{x}).

这里 $ \eta $ 同样是学习率。可以看到每次迭代的计算开销从梯度下降的 $ \mathcal{O}(n) $ 降到了常数 $ \mathcal{O}(1) $ 。值得强调的是，随机梯度 $ \nabla J_i(\boldsymbol{x}) $ 是对梯度 $ \nabla J(\boldsymbol{x}) $ 的无偏估计：

Ei∇Ji(x)=1n∑i=1n∇Ji(x)=∇J(x).E_i \nabla J_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla J_i(\boldsymbol{x}) = \nabla J(\boldsymbol{x}).

这意味着，平均来说，随机梯度是对梯度的一个良好的估计。下图在梯度中添加均值为0的随机噪声，用来模拟随机梯度下降，以此来比较它与梯度下降的区别。

可以看到，随机梯度下降中自变量的迭代轨迹相对于梯度下降中的来说更为曲折。这是由于实验所添加的噪声使模拟的随机梯度的准确度下降。在实际中，这些噪声通常指训练数据集中的无意义的干扰。

随机梯度下降法每次迭代使用一个样本来对参数进行更新，每看一个数据就算一次损失函数，然后求梯度、更新参数，由于其梯度有一定的游走特性，因此称为随机梯度下降（stochastic gradient descent）。

随机梯度下降法速度较快，但收敛性能不太好，可能在最优点附近晃来晃去，但达不到最优点。两次参数的更新也有可能互相抵消掉，造成目标函数震荡的比较剧烈。

（1）优点：

  • 由于不是在全部训练数据上计算损失函数，而是在每轮迭代中随机优化某一条训练数据上的损失函数，从而每轮参数的更新速度大大加快。

（2）缺点：

  • 准确度下降。由于即使在目标函数为强凸函数的情况下，SGD仍旧无法做到线性收敛。
  • 由于单个样本并不能代表全体样本趋势，因此可能会收敛于局部最优，而非全局最优。
  • 不易于并行实现。

（3）为什么SGD收敛速度比BGD快？

  • 假设有30W个样本，对于BGD而言，每次迭代需要计算30W个样本才能对参数进行一次更新，需要求得最小值可能需要多次迭代（假设这里是10）。
  • 而对于SGD，每次更新参数只需一个样本，因此若使用这30W个样本进行参数更新，则参数会被更新（迭代）30W次，而在这期间， SGD可能就已经收敛到一个合适的最小值上了。
  • 也就是说，在收敛时，BGD计算了10×30W次，而SGD只计算了1×30W次。 从迭代的次数上来看，SGD迭代的次数较多，在解空间的搜索过程看起来很盲目。

四、小批量梯度下降法

（1）原理

为克服上述两种极端方法的缺点，现在一般采用一种折中手段，即小批量梯度下降。该方法把样本数据分为若干个批，按批来更新参数。一个批中的数据共同决定了本次梯度的方向，下降起来就不容易跑偏，减少了随机性。另一方面因为批的样本数与整个数据集相比小了很多，计算量也不是很大。

需要注意的是，现在很多软件和库中的优化器SGD虽然是随机梯度下降的缩写，但指的是小批量梯度下降。

（2）公式推导

设目标函数 $ J(\boldsymbol{x}): \mathbb{R}^d \rightarrow \mathbb{R} $ 。在迭代开始前的时间步设为0。该时间步的自变量记为 $ \boldsymbol{x}_0\in \mathbb{R}^d $ ，通常由随机初始化得到。在接下来的每一个时间步 $ t>0 $ 中，小批量随机梯度下降随机均匀采样一个由训练数据样本索引组成的小批量 $ \mathcal{B}_t $ 。我们可以通过重复采样（sampling with replacement）或者不重复采样（sampling without replacement）得到一个小批量中的各个样本。前者允许同一个小批量中出现重复的样本，后者则不允许如此，且更常见。对于这两者间的任一种方式，都可以使用

gt←∇JBt(xt−1)=1∣B∣∑i∈Bt∇Ji(xt−1)\boldsymbol{g}_t \leftarrow \nabla J_{\mathcal{B}_t}(\boldsymbol{x}_{t-1}) = \frac{1}{|\mathcal{B}|} \sum_{i \in \mathcal{B}_t}\nabla J_i(\boldsymbol{x}_{t-1})

来计算时间步 $ t $ 的小批量 $ \mathcal{B}t $ 上目标函数位于 $ \boldsymbol{x}{t-1} $ 处的梯度 $ \boldsymbol{g}_t $ 。这里 $ |\mathcal{B}| $ 代表批量大小，即小批量中样本的个数，是一个超参数。同随机梯度一样，重复采样所得的小批量平均梯度 $ \boldsymbol{g}t $ 也是对梯度 $ \nabla J(\boldsymbol{x}{t-1}) $ 的无偏估计。给定学习率 $ \eta_t $（取正数），小批量随机梯度下降对自变量的迭代如下：

xt←xt−1−ηtgt\boldsymbol{x}_t \leftarrow \boldsymbol{x}_{t-1} - \eta_t \boldsymbol{g}_t

基于随机采样得到的梯度的方差在迭代过程中无法减小，因此在实际中，（小批量）随机梯度下降的学习率可以在迭代过程中自我衰减，例如 $ \eta_t=\eta t^\alpha $（通常 $ \alpha=-1 $ 或者 $ -0.5 $）、 $ \eta_t = \eta \alpha^t $（如 $ \alpha=0.95 $）或者每迭代若干次后将学习率衰减一次。如此一来，学习率和（小批量）随机梯度乘积的方差会减小。而梯度下降在迭代过程中一直使用目标函数的真实梯度，无须自我衰减学习率。

小批量随机梯度下降中每次迭代的计算开销为 $ \mathcal{O}(|\mathcal{B}|) $ 。当批量大小为1时，该算法即为随机梯度下降；当批量大小等于训练数据样本数时，该算法即为梯度下降。当批量较小时，每次迭代中使用的样本少，这会导致并行处理和内存使用效率变低。这使得在计算同样数目样本的情况下比使用更大批量时所花时间更多。当批量较大时，每个小批量梯度里可能含有更多的冗余信息。为了得到较好的解，批量较大时比批量较小时需要计算的样本数目可能更多，例如增大迭代周期数。

（3）batch size

小批量梯度下降法的关键是批次中样本数的选择，即batch size的选择问题：

（1）在合理地范围内，增大batch size的好处：

  • 内存利用率提高了，大矩阵乘法的并行化效率提高。
  • 跑完一次epoch（全数据集）所需的迭代次数减少，对于相同数据量的处理速度进一步加快。
  • 在一定范围内，一般来说batch Size越大，其确定的下降方向越准，引起训练震荡越小。

（2）盲目增大batch size的坏处：

  • 内存利用率提高了，但是内存容量可能撑不住了。
  • 跑完一次epoch（全数据集）所需的迭代次数减少，要想达到相同精度，其所花费时间大大增加了，从而对参数的修正也就显得更加缓慢。
  • batch size增大到一定程度，其确定的下降方向已经基本不再变化。

五、三种梯度下降法的图示

下图显示了三种梯度下降算法的收敛过程：

  • 批量梯度下降法的梯度计算来自于所有样本，单次迭代计算量大，但其下降方向比较准确和稳定，最终能够收敛于最优点
  • 随机梯度下降法的梯度计算来自于单个样本，单次迭代计算量小，但其下降方向随机性较强，而且可能永远无法收敛于最优点
  • 小批量梯度下降法的梯度计算来自于多个样本，单次迭代计算量可配置，其下降方向随机性减小，能够收敛于最优点或附近。

在这里插入图片描述

六、梯度下降法常用术语的定义

在机器学习任务中，常采用梯度下降算法来优化训练，其中常用到batch size、epoch、iteration等概念。

（1）批（batch）和批大小（batch size）。

批（batch）是机器学习训练过程中的最小数据组织单位，批大小（batch size）指该数据组织单位中的样本数量。在机器学习的训练任务中，损失函数通常是由一组样本数据加权得到的，这一组样本数据就被称为一个批次，而批次中样本的数量，就被称为batch size。也就是说一个批次（batch）中的样本一起进行训练，或者说一次迭代使用且只能使用一个批次的样本数据。

例如：某样本集含10万个样本，希望做1000个批次（batchs=1000）训练，每个批次从训练集中抽取100个（batch size = 100）的样本。

对于批量梯度下降算法而言，批大小（batch size）等于样本总数；对于随机梯度下降算法而言，批大小（batch size）等于1；对于小批量梯度下降算法而言，批大小（batch size)由用户指定，通常为2的N次方。

（2）迭代（iteration）和迭代次数（iteration number）。

一次迭代（iteration）指的是使用一个批次（batch）样本完成一次训练，每次迭代（iteration）更新一次参数。因此：

  • 单轮迭代次数（iterations per epoch) = 样本总数 / 批大小（batch size）
  • 总迭代次数( total iterations) = 单轮迭代次数 * 总轮数

（3）epoch：轮

使用训练集中的全部样本训练一次称为一轮（epoch）。

通俗的讲，轮数（epoch的值）就是整个数据集被训练迭代了几次。 例如：

  • 训练集有500个样本，批大小（batch size）= 10 ，那么训练完整个样本集：iteration=50，epoch=1.