通俗理解梯度下降法

简介

机器学习的本质就是模型+优化，本篇blog主要是简单介绍一种优化算法——梯度下降法。相比于其他的优化算法，该算法的适用性较高，尤其在深度网络的学习中，主流的优化算法就是梯度下降法。虽然说该方法适用性高，但是仍有一定的局限性，比如对于非凸函数收敛于局部最小，梯度消失，梯度爆炸等问题，但总的来说该算法的应用还是十分广泛的。

场景假设

  首先，我们先假设一个场景：一个人被放在山上，现在他想找到一条下山的路到达山脚，但是这个人没有地图，也不知道所处位置和方向。另外山上还起了大雾，导致能见度很低，因此没有办法直接找到一条合适的路径，只能自己一步步摸索，那么这个时候，便可利用梯度下降算法来帮助自己下山。

  具体怎么做呢，首先以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着下降方向走一步，然后又继续以当前位置为基准，再找最陡峭的地方，再走直到最后到达最低处。虽然这么走不一定是最短路径，但是每一步都能保证自己离山脚更进一步，这就是梯度下降法的核心：一步步慢慢的靠近最小值点，不一定最快，但一定有效。那么一定会有同学问了，如果我想找到f(x)的最高点怎么办？同样，我们可以利用梯度下降的方法找-f(x)最小点即可。

数学基础知识回顾

一元函数的导数与泰勒展开

  在微积分中, 函数 $f(x)$ 在点 $x_{0}$ 上的导数定义为:

$$\quad f^{\prime}\left(x_{0}\right)=\lim _{x \rightarrow x_{0}} \frac{f(x)-f\left(x_{0}\right)}{x-x_{0}}$$

  它在几何上指的就是函数 $f(x)$ 在 $x_{0}$ 上的切线方向.通常来说，为了计算某个函数 $f(x)$ 的最大值或者最小值，通常都会计算它的导数 $f^{\prime}(x)$ ，然后求解方程 $f^{\prime}(x)=0$ 就可以得到函数的临界点，进一步判断这些临界点是否是最大值或者最 小值。但是临界点并不一定是全局最大值或者全局最小值，基至不是局部的最大值或者局部最小值。

例如：函数 $f(x)=x^{3},$ 它的导数是 $f^{\prime}(x)=3 x^{2},$ 因此 $x=0$ 是它的临界点。但 $x=0$ 则不是这个函数的局部最大值或者局部最小值点, 因为 $f(x)<0, \forall x<0$ 且 $f(x)>0, \forall x>0$。从 Taylor 级数的角度来看, $\quad f(x)$ 在 $x_{0}$ 附近的 Taylor 级数是

$$f(x)=f\left(x_{0}\right)+f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)+\frac{f^{\prime \prime}\left(x_{0}\right)}{2}\left(x-x_{0}\right)^{2}+O\left(\left|x-x_{0}\right|^{3}\right)$$

  对于临界点 $x_{0}$ 而言，它满足条件 $f^{\prime}\left(x_{0}\right)=0$ 。当 $f^{\prime \prime}\left(x_{0}\right)>0$ 时, 可以得到 $x_{0}$ 是 $f(x)$ 的局部最小值;当$f^{\prime \prime}\left(x_{0}\right)<0$时, 可以得到 $x_{0}$ 是 $f(x)$ 的局部最大值。而对于上面的例子 $f(x)=x^{3}$ 而言，临界点 0 的二阶导数则是 $f^{\prime \prime}(0)=0$, 因此使用上面的方法则无法判断临界点 0 是否是局部极值。

多元函数的梯度与泰勒展开

  对于多元函数 $f(\mathbf{x})=f\left(x_{1}, \cdots, x_{n}\right)$ 而言，同样可以计算它们的”导数”，也就是偏导数和梯度。i.e. 它的梯度可以定义为：

$$\nabla f(\mathbf{x})=\left(\frac{\partial f}{\partial x_{1}}(\mathbf{x}), \cdots, \frac{\partial f}{\partial x_{n}}(\mathbf{x})\right)$$

而多元函数 $f(\mathbf{x})$ 在点 $\mathbf{x}_{0}$ 上的 Taylor 级数是：

$$f(\mathbf{x})=f\left(\mathbf{x}_{0}\right)+\nabla f\left(\mathbf{x}_{0}\right)\left(\mathbf{x}-\mathbf{x}_{0}\right)+\frac{1}{2}\left(\mathbf{x}-\mathbf{x}_{0}\right)^{T} H\left(\mathbf{x}-\mathbf{x}_{0}\right)+O\left(\left|\mathbf{x}-\mathbf{x}_{0}\right|^{3}\right)$$

其中 $H$ 表示 Hessian 矩阵。如果 $x_{0}$ 是临界点，并且 Hessian 矩阵是正定矩阵的时候, $f(\mathbf{x})$ 在 $x_{0}$ 处达到局部极小值。

梯度下降法

  从数学上的角度来看，梯度的方向是函数增长速度最快的方向，那么梯度的反方向就是函数减少最快的方向。那么，如果想计算一个函数的最小值，就可以使用梯度下降法的思想来做。
  假设希望求解目标函数 $f(\mathbf{x})=f\left(x_{1}, \cdots, x_{n}\right)$ 的最小值, 可以从一个初始点 $\mathbf{x}^{(0)}=\left(x_{1}^{(0)}, \cdots, x_{n}^{(0)}\right)$ 开始, 基于学习率 $\eta>0$ 构建一个迭代过程：当 $i \geq 0$ 时

$$x_{1}^{(i+1)}=x_{1}^{(i)}-\eta \cdot \frac{\partial f}{\partial x_{1}}\left(\mathbf{x}^{(i)}\right)$$ $$··········$$ $$x_{n}^{(i+1)}=x_{n}^{(i)}-\eta \cdot \frac{\partial f}{\partial x_{n}}\left(\mathbf{x}^{(i)}\right)$$

其中 $\mathbf{x}^{(i)}=\left(x_{1}^{(i)}, \cdots, x_{n}^{(i)}\right),$ 一旦达到收禽条件的话, 迭代就结束。

  从梯度下降法的迭代公式来看, 下一个点的选择与当前点的位置和它的梯度相关。反之，如果要计算函数 $f(\mathbf{x})=f\left(x_{1}, \cdots, x_{n}\right)$ 的最大值, 沿着梯度的反方向前进即可,也就是说：

$$x_{1}^{(i+1)}=x_{1}^{(i)}+\eta \cdot \frac{\partial f}{\partial x_{1}}\left(\mathbf{x}^{(i)}\right)$$ $$··········$$ $$x_{n}^{(i+1)}=x_{n}^{(i)}+\eta \cdot \frac{\partial f}{\partial x_{n}}\left(\mathbf{x}^{(i)}\right)$$

其中, $\mathbf{x}^{(i)}=\left(x_{1}^{(i)}, \cdots, x_{n}^{(i)}\right)$ 。整体来看，无论是计算函数的最大值或者最小值，都需要构建 一个迭代关系 $g$ ，那就是：

$$\mathbf{x}^{(0)} \stackrel{g}{\longrightarrow} \mathbf{x}^{(1)} \stackrel{g}{\longrightarrow} \mathbf{x}^{(2)} \stackrel{g}{\longrightarrow} \cdots$$

也就是说对于所有的 $i \geq 0,$ 都满足迭代关系 $x^{(i+1)}=g\left(x^{(i)}\right)$ 。所以, 在以上的两个方法 中，我们可以写出函数 g 的表达式为：

$$g(\mathbf{x})=\left\{\begin{array}{ll} \mathbf{x}-\eta \nabla f(\mathbf{x}) & \text { 梯度下降法 } \\ \mathbf{x}+\eta \nabla f(\mathbf{x}) & \text { 梯度上升法 } \end{array}\right.$$

但在实际应用时，当我们求解最大值时，可以对函数取反，求其最小值。

实例测试

单变量函数的梯度下降法

在这么我们举一个简单的例子，对于目标函数：

$$J(\theta)=\theta^{2}$$

对函数进行微分，直接求导就可以得到

$$J^{\prime}(\theta)=2 \theta$$

初始化，也就是起点，起点可以随意的设置，这里设置为

$$\theta^{0}=1$$

学习率也可以随意的设置，这里设置为0.4

$$\alpha=0.4$$

根据梯度下降的计算公式

$$\Theta^{1}=\Theta^{0}-a \nabla J(\Theta) \quad 初始值为\Theta^{0}$$

我们开始进行梯度下降的迭代计算过程:

$$\begin{aligned} \theta^{0} &=1 \\ \theta^{1} &=\theta^{0}-\alpha * J^{\prime}\left(\theta^{0}\right) \\ &=1-0.4 * 2 \\ &=0.2 \\ \theta^{2} &=\theta^{1}-\alpha * J^{\prime}\left(\theta^{1}\right) \\ &=0.04 \\ \theta^{3} &=0.008 \\ \theta^{4} &=0.0016 \end{aligned}$$

在上面的计算过程中，初始参数$\theta^{0}$，学习率$\alpha$我们是随意选择的，但因为本次的例子较为简单，所以效果还不错。但在实际应用中，目标函数往往会十分复杂，对于初始值的选择也十分重要，在后面我会介绍如何选取合适的初始值。

多变量函数的梯度下降

我们假设有一个目标函数

$$J(\Theta)=\theta_{1}^{2}+\theta_{2}^{2}$$

现在要通过梯度下降法计算这个函数的最小值。我们通过观察就能发现最小值其实就是 (0，0)点。但是接下来，我们会从 梯度下降算法开始一步步计算到这个最小值！ 我们假设初始的起点为：

$$\Theta^{0}=(1,3)$$

初始的学习率为：

$$\alpha=0.1$$

函数的梯度为：

$$\nabla J(\Theta)=\left\langle 2 \theta_{1}, 2 \theta_{2}\right\rangle$$

进行多次迭代：

$$\begin{aligned} \Theta^{0} &=(1,3) \\ \Theta^{1} &=\Theta^{0}-\alpha \nabla J(\Theta) \\ &=(1,3)-0.1(2,6) \\ &=(0.8,2.4) \\ \Theta^{2} &=(0.8,2.4)-0.1(1.6,4.8) \\ &=(0.64,1.92) \\ \Theta^{3} &=(0.512,1.536) \\ \Theta^{4} &=(0.4096,1.2288000000000001) \\ \vdots & \\ \Theta^{10} &=(0.10737418240000003,0.32212254720000005) \\ \vdots & \\ \Theta^{50} &=\left(1.1417981541647683 \mathrm{e}^{-05}, 3.425394462494306 \mathrm{e}^{-05}\right) \\ \vdots & \\ \Theta^{100} &=\left(1.6296287810675902 \mathrm{e}^{-10}, 4.888886343202771 \mathrm{e}^{-10}\right) \end{aligned}$$

梯度下降法的种类

批量梯度下降

  这是梯度下降法刚刚提出时的主流类型，但是现在已经不经常使用了，因为这种优化算法会使用整个数据集去计算代价函数的梯度去更新参数，如果数据集非常的大，批量梯度下降法会很慢，而且数据量这么大往往无法载入内存，但好处就是，在每次迭代完成之后能够保证每次的优化都是有效的。在随机初始化参数后，按如下方式计算代价函数的梯度，直到数据收敛：

$$\theta_{j}:=\theta_{j}-\alpha \frac{1}{m} \sum_{i=1}^{m}\left(h_{\theta}\left(x^{(i)}\right)-y^{(i)}\right) x_{j}^{(i)}$$

上图是每次迭代后的等高线图，每个不同颜色的线表示代价函数不同的值。运用梯度下降会快速收敛到圆心，即唯一的一个全局最小值。

随机梯度下降

  相比于批量梯度下降法，随机梯度下降法具有更快的计算速度。首先，随机梯度下降的第一步是随机化整个数据集。在每次迭代仅选择其中一部分训练样本去计算代价函数的梯度，然后更新参数。即使是大规模数据集，随机梯度下降法也会很快收敛。由于数据点可能存在的误差，随机梯度下降得到结果的准确性可能不会是最好的，但是计算结果的速度很快。具体的计算方式如下：

其中，m代表训练样本的数量，如下图所示，随机梯度下降法不像批量梯度下降法那样收敛，而是游走到接近全局最小值的区域终止：

小批量梯度下降

  小批量梯度下降法是最广泛使用的一种算法，该算法每次随机使用m个训练样本（称之为一批）进行训练，能够更快得出准确的答案。小批量梯度下降法不是使用完整数据集，在每次迭代中仅使用m个训练样本去计算代价函数的梯度。一般小批量梯度下降法所选取的样本数量在50到256个之间，视具体应用而定，具体的计算方式如下：

其中，b表示一批训练样本的个数，m是训练样本的总数。

局限性

非凸函数局部收敛

如果想要利用梯度下降法找到目标函数的全局最小值，那么该函数必须是凸函数(参考链接：什么是凸函数),如果不是凸函数，那么利用梯度下降法就有可能收敛于局部最小值，如下图所示

函数最终会收敛在上面的点，而非我们需要的最小值点！但是在实际应用中，很多目标函数都是非凸函数，尤其是神经网络，那么我们该如何解决这个问题呢？据我所知，当前还没有完美的解决方案，一般采用合适的学习率或者搭配一些其他的优化算法，使得计算出来的结果（可能是局部最优解）仍具有良好的效果，从而用该值作为我们优化算法的最优值，可能在算法上讲的并不是很清楚，有点像是黑盒子，但事实证明确实很有效。

学习率选取不合适

在本文的演示的例子中，因为目标函数较为简单，所以在随便拿了一个学习率后，仍然有不错的效果，但是实际应用时，如果学习率选取不当，会造成严重的后果，如下图所示：

如果学习率选取过大，那么计算结果就会在收敛点处震荡，而无法收敛到最小值；如果学习率选的过小，那么计算时间就会过长，占用大量资源，同时还有可能陷入局部最小而无法跳出。

梯度爆炸与梯度消失

  梯度爆炸与梯度消失是神经网络经常出现的一个问题，但究其本质还是梯度下降法的局限性，在这里简单介绍下，后面涉及到神经网络时再具体讲解。对函数求导数是基于链式，而链式法则是一个连乘的形式，所以当层数越深的时候，梯度将以指数形式传播。梯度消失问题和梯度爆炸问题一般随着网络层数的增加会变得越来越明显。在根据损失函数计算的误差通过梯度反向传播的方式对深度网络权值进行更新时，得到的梯度值接近0或特别大，也就是梯度消失或爆炸。梯度消失或梯度爆炸在本质原理上其实是一样的。
  梯度爆炸将导致参数大小会出现很大的震荡，无法收敛；梯度消失将导致优化算法失效。

优化

目前主流的梯度下降法是小批量梯度下降法（ps:可能部分的算法称之为sgd）,每次均利用部分的数据对函数进行优化，从而快速的达到收敛。

如图所示，该种算法每次迭代并不是最有效的，因此我们可以对其增设“动量”。
回顾一下梯度下降法每次的参数更新公式:

$$\begin{aligned} W &:=W-\alpha \nabla W \\ b &:=b-\alpha \nabla b \end{aligned}$$

可以看到，每次更新仅与当前梯度值相关, 并不涉及之前的梯度。而动量梯度下降法则对各个mini-batch求得的梯度 $\nabla W, \nabla b$ 使用指数加权平均得到 $V_{\nabla w}, V_{\nabla b_{\bullet}}$ 并使用新的参数更新之前的参数。
例如，在100次梯度下降中求得的梯度序列为:

$$\left\{\nabla W_{1}, \nabla W_{2}, \nabla W_{3} \ldots \ldots \ldots \nabla W_{99}, \nabla W_{100}\right\}$$

则其对应的动量梯度分别为：

$$\begin{array}{c} V_{\nabla W_{0}}=0 \\ V_{\nabla W_{1}}=\beta V_{\nabla W_{0}}+(1-\beta) \nabla W_{1} \\ V_{\nabla W_{2}}=\beta V_{\nabla W_{1}}+(1-\beta) \nabla W_{2} \\ ·········· \\ V_{\nabla W_{100}}=\beta V_{\nabla W_{99}}+(1-\beta) \nabla W_{100} \end{array}$$

使用指数加权平均之后梯度代替原梯度进行参数更新。因为每个指数加权平均后的梯度含有之前梯度的信息, 动量梯度下降法因此得名。其效果如下：

简单的来说，增设动量之后，将优化时的左右的摆动减小，让目标函数收敛的更快。