梯度下降法

梯度下降法

梯度下降法(Gradient Descent)是求解机器学习算法模型参数(即无约束最优化问题)最常用的方法之一。梯度下降法是一种迭代算法,它的基本思想是:选取一个适当的初值 \(x^0\) 后不断地进行迭代,在迭代的每一步中求解目标函数的梯度向量,然后以负梯度方向更新 \(x\) 的值,最后求得目标函数的极小值。

### 2019.03.17 更新 ###

在《统计学习方法》梯度下降法这一节的最后,作者总结道 当目标函数是凸函数时,梯度下降法的解是全局最优解。 当时这里有点不懂,遂问老师,最后从老师那里得到了答案。我们知道,随机梯度下降法求得的是目标函数(深度学习中这个目标函数一般是损失函数)的极小值,极小值不一定是最小值,所以一般求得的不是最优解。但凸函数是个例外,它只有一个极值,所以一定是最值。还有一个问题是,如果一个函数只有极大值不存在极小值,这时应该怎么办呢?对于这种情况,我们可以采用梯度上升法。并且由于损失函数是我们自己设计的,所以我们总是可以选取一个合适的损失函数使它具有极小值。

========== 以下是原文 ==========

方向导数和梯度

在正式说梯度下降法之前,让我们先复习一下微积分中方向导数和梯度的概念。

方向导数(Directional Derivative)

在微积分中,我们用方向导数来表示一个函数在某点沿任意方向的变化率。对一元函数 \(f(x)\) 来说,若极限 \(\lim_{\Delta x\to 0}\frac{f(x_0+\Delta x)-f(x_0)}{\Delta x}\) 存在,则称函数 \(f(x)\) 在点 \(x_0\) 处可导,并将该极限作为函数 \(f(x)\) 在点 \(x_0\) 处的导数,记为 \(f(x_0)'\)。如果把所有可导的点及其导数放在一起形成一个映射,我们就称这个映射为导函数(在不引起混淆的情况下,我们一般把导函数简称为导数)。因此,对一元函数来说,导数的意义就是函数在某点的变化率,此时函数 \(f(x)\) 只有一个变化方向(即 \(x\) 方向)。

到了二元函数 \(f(x,y)\) ,情况会变得稍微复杂些,因为不止一个方向。但类似的,有如下定义,若极限 \(\lim_{\Delta x\to 0}\frac{f(x0+\Delta x,y_0)-f(x_0,y_0)}{\Delta x}\) 存在,则称函数 \(f(x,y)\) 在点 \((x_0,y_0)\) 处有关于 \(x\) 的一阶偏导,记为 \(\frac{\partial f}{\partial x}\)。相应的,关于参数 \(y\) 的一阶偏导为 \(\frac{\partial f}{\partial y}\)。同理,如果我们把所有关于 \(x\) 可导的点及其偏导数放在一起形成的映射就是函数 \(f(x,y)\) 的关于参数 \(x\) 的偏导函数(在不引起混淆的情况下,我们一般将偏导函数简称为偏导数)。可以看出,偏导数其实就是函数在某个特定方向上的变化率(方向固定、点任意),如偏导数 \(\frac{\partial f}{\partial x}\) 表示的就是函数 \(f(x,y)\)\(x\) 方向上的变化率。

那么问题来了?如果点固定、方向任意,是否有一个函数能够表示原函数在某个点上沿任意方向的变化率呢?有!这个函数就是方向导数。以二元函数为例,对于方向导数我们有如下定义,设二元函数 \(f(x,y)\) 在点 \(P(x_0,y_0)\) 处有定义,\(l\) 是从 \(P_0\) 出发的射线,点 \(P(x,y)\)\(l\) 上任意一点、\(P\)\(P_0\) 之间的距离为 \(\rho\),如果极限 \(\lim_{x\to x_0}\frac{f(P)-f(P_0)}{\rho}\) 存在,则称此极限为函数 \(f\) 在点 \(P_0\) 沿方向 \(l\) 的方向导数,记作 \(f_l(P_0)\)。由定义可以看出,射线 \(l\) 可以表示为向量 \((x,y)\),在方向导数存在的情况下,理论上可以取遍平面中的任意方向。

更一般地,对于方向导数有我们以下定义:

\(n\) 元函数 \(f(x_1,x_2,...,x_n)\) 在点 \(P(x_1^0,x_1^0,...,x_n^0)\) 处有定义,\(l\) 是从 \(P_0\) 出发的射线,点 \(f(x_1,x_2,...,x_n)\)\(l\) 上任意一点、\(P\)\(P_0\) 之间的距离为 \(\rho\),如果极限 \(\lim_{x\to x_0}\frac{f(P)-f(P_0)}{\rho}\) 存在,则称此极限为函数 \(f\) 在点 \(P_0\) 沿方向 \(l\) 的方向导数,记作 \(f_l(P_0)\)

梯度(Gradient)

通过上面的讨论,我们知道方向导数可以用于描述一个函数 \(f\)\(n\) 维空间中的某个点沿任意方向的变化率。但通常情况下,人们往往更关注当函数在某个点变化率最大的方向,即函数上升和下降最快的方向。

梯度正是一个表示函数 \(f\)\(n\) 维空间中某个点变化率最大的方向,一般用一个向量 \((x_1,x_2,...x_n)\) 表示。对一个多元函数的每个参数分别求偏导[1],然后将所有的偏导组合成一个向量,得到的向量就是梯度。比如二元函数 \(f(x,y)\) 的两个偏导分别是 \(\frac{\partial f}{\partial x}\)\(\frac{\partial f}{\partial y}\),那么它的梯度就是 \(( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y})\),记作 \(\nabla f\)\(grad f\)

梯度下降

梯度下降法(Gradient Descent),顾名思义就是一种利用梯度来不断减少函数值的方法。在机器学习中,它常常被用于更新模型的参数。

其实可以把梯度下降看作是一个下山的过程:想象此刻我们正在山顶,想要尽可能快得下山。由于不知道路线,所以决定走一步算一步,也就是每当走到一个位置时,求解当前的梯度,然后沿着梯度的负方向(也就是当前最陡峭的位置)往下走一步,走到下一个位置的时候再重复上面的过程,不断重复,直到走到我们以为的山脚,实际上这并不一定是真正的山脚,很有可能只是某一个局部山峰的低处,也就是说梯度下降求得的是极小值而不是最小值。

在机器学习中,梯度下降的方式有很多,比较出名的有批梯度下降(batch gradient descent)、随机梯度下降(stochastic gradient descent)和小批梯度下降(mini-batch gradient descent)。

批梯度下降(batch gradient descent)

批梯度下降是把整个数据集遍历一遍算一次损失函数,分别求解函数对各个参数的梯度,然后更新参数。这种方法每更新一次梯度都需要把数据集中的所有样本都扫描一遍,因此计算开销特别大,速度较慢,而且不支持在线学习。

随机梯度下降(stochastic gradient descent)

还有一种方法是每扫描到一个样本就计算一下损失函数,然后求梯度向量更新参数。这种方法叫随机梯度下降,随机梯度下降的速度比较快,但是收敛性能不太好,也就是会在最优点附近晃来晃去,hit 不到最优点。

小批量梯度下降(mini-batch gradient descent)

小批量梯度下降是对上面两种方法的折衷,这种方法是先把数据分为若干个批,按批来更新参数。这样,一个批中的一组数据共同决定了本次梯度的方向,下降起来不容易跑偏,减少了随机性。另一方面,分批处理要比遍历整个数据集的工作量要小很多,因此速度也相对较快。所以现在的用的优化器 SGD(stochastic gradient descent)一般都是基于 mini-batch 的。

对于随机梯度下降(stochastic gradient descent,下面简称 SGD),我们将经常遇到以下这些概念:

  1. batchsize: 批大小,表示每个批中包含样本的个数,即每次训练会在训练集中取一个批(batchsize 个样本)进行训练。
  2. iteration: 一次迭代,一个 iteration 表示训练完了一个批(batchsize 个样本)。
  3. epoch: 完成一个 epoch 表示整个数据集被训练一遍,如 epoch 为 50 时,就表示整个数据集被训练了 50 遍。

注:
[1] 前提是这个函数要有一阶连续导数

参考资料

  1. 方向导数 - 百度百科
  2. 梯度 - 百度百科
  3. 深度学习中的batch、epoch、iteration的含义
  4. 梯度下降(Gradient Descent)小结
  5. 《统计学习方法》李航
  6. ML Cheatsheet
  7. An overview of gradient descent optimization algorithms
  8. 理解深度学习中的学习率及多种选择策略