梯度下降算法

转自 https://www.jianshu.com/p/c7e642877b0e

本文将从一个下山的场景开始，先提出梯度下降算法的基本思想，进而从数学上解释梯度下降算法的原理，最后实现一个简单的梯度下降算法的实例！

梯度下降的场景假设

梯度下降法的基本思想可以类比为一个下山的过程。假设这样一个场景：一个人被困在山上，需要从山上下来(i.e. 找到山的最低点，也就是山谷)。但此时山上的浓雾很大，导致可视度很低。因此，下山的路径就无法确定，他必须利用自己周围的信息去找到下山的路径。这个时候，他就就可以利用特度下降算法来帮助自己下山。具体来说就是，以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着山的高度下降的地方走，同理，如果我们的目标是上山，也就是爬到山顶，那么此时应该是朝着最陡峭的方向往上走。然后没走一段距离，都反复采用同一个方法，最后就能成功的抵达山谷。

我们同时可以假设这座山对陡峭的地方是无法通过肉眼立马观察出来的，而是需要一个复杂的工具来测量，同时，这个人此时正好用友测量出最陡峭方向的能力。所以，此人没走一段距离，都需要一段时间来测量所在位置最陡峭的方向，这是比较耗时的。那么为了在太阳下山之前到达山地，就要尽可能的减少测量方向的次数。这是一个两难的选择，如果测量的频繁，可以保证下山的方向是绝对正确的，但有非常耗时，如果测量的过好，又有偏离轨道的风险。所以需要找到一个合适的测量方向的频率，来确保下山方向不错误，同时又不至于耗时太多！

梯度下降

梯度下降的基本过程就和下山的场景类似。

---

首先，们有一个可微分的函数。这个函数就代表这一座山。我们的目标就是找到这个函数的最小值，也就是山底。治具之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，就能让函数值下降的最快！因此梯度的方向就是函数之变化最快的方向。

所以，我们重复利用这个方法，反复求去梯度，最后就能达到局部的最小值，这就类似于我们下山的过程。而求去梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。那么为什么梯度的方向就是最陡峭的方向呢？接下来我们从微分开始讲起。

微分

看待微分的意义，可以有不同的角度，最常用的两种是：

• 函数图像中，某点切线的斜率

• 函数的变化率

  几个微分的例子：

  • $$\frac{d(x^2)}{dx} = 2x$$
  • $$\frac{d(-2y^5)}{dy}=-10y^4$$
  • $$\frac{d(5-θ)^2}{dθ} = -2(5-θ)$$

上面的例子都是单变量的微分，当一个函数有多个变量的时候，就有了多变量的微分，即分别对每个变量进行求微分。

• $$\frac{δ}{δx}(x^2y^2)=2xy^2$$
• $$\frac{δ}{δx}(-2y^5+z^2)=-10y^4$$
• $$\frac{δ}{δθ_2}(5θ_1+2θ_2-12θ_3)=2$$
• $$\frac{δ}{δθ_2}(0.55-(5θ_1+2θ_2-12θ_3))=-2$$

梯度

梯度时机上就是多变量微分的一般化。

下面这个例子：

$$J(Θ)=0.55-(5θ_1+2θ_2-12θ_3)$$ $$▽J(Θ)=<\frac{δJ}{δθ_1},\frac{δJ}{δθ_2},\frac{δJ}{δθ_3}>$$ $$=<-5, -2, 12>$$

我们可以看到，梯度就是分别对每个变量进行微分，然后用逗号分隔开，梯度是用<>包括起来的，说明梯度其实是一个向量。

梯度是微积分中一个很重要的概念，之前提到过梯度的意义

• 在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定的切线的斜率
• 在多边量函数中，梯度是一个向量，向量有方向，梯度的方向就支出了函数在给定点上升最快的方向

这就说明了为什么我们要千方百计的求取梯度！我们需要到达山底，就需要在每一步观测到此时最陡峭的地方，梯度就恰巧告诉了我们这个方向，这正是我们所需要的。所以我们只要沿着梯度的方向一直走，就能走到局部最低点！

梯度下降算法的数学解释

上面我们花了大量篇幅介绍梯度下降算法的基本思想和场景假设，以及梯度的概念和思想。下面我们就开始从数学上解释梯度下降算法的计算过程和思想！

$$Θ^1 = Θ^0 -α▽J(Θ) \qquad evaluated at\qquad Θ^0$$

此公式的意义：

J是关于$Θ$的一个函数，我们当前所处的位置为$Θ^0$点，要从这个点走到$J(Θ)$的最小值点，也就是山底。首先我们先确定前进的方向，也就是梯度的反方向，然后走一段距离的步长，也就是$α$，走完这个步长，就达到了$Θ^1$这个点！

下面就这个公式的几个常见疑问：

• $α$ 是什么?

  $α$ 在梯度下降算法中被称为 学习率 或者 步长 ，意味着我们可以通过$α$ 来控制每一步走的距离，以保证不要步子跨的太大，而错过了最低点。同时也要保证不要走的太慢，导致太阳下山了，还没有走到山下。所以 $α$ 的选择在梯度下降算法中往往很重要！$α$ 不能太大也不能太小，太大走不到最低点，太小可能迟迟走不到最低点。

  

• 为什么要梯度横溢一个负号？

  梯度前加一个负号，就意味着朝着梯度相反的方向前进！我们在前文提到，梯度的方向时机就是函数在此点上升最快的方向！而我们需要朝着下降最快的方向走，自然就是负的梯度方向，所以此处需要加上负号

梯度下降算法的实例

我们已经基本了解梯度下降算法的计算过程，那么我们就来看几个梯度下降算法的小实例，首先从单变量的函数开始

单变量函数的梯度下降

我们假设一个单变量的函数：

​ $J(θ) = θ^2$

​ 函数的微分：

​ $J^′(θ)=2θ$

​ 初始化起点为：

​ $θ^0 = 1$

​ 学习率：

​ $α = 0.4$

根据梯度下降的计算公式：

​ $Θ^1 = Θ^0 -α▽J(Θ) \qquad evaluated at \qquad Θ^0$

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

​ $θ^0=1$

​ $θ^1=θ^0-α*J^′(θ)$

​ $= 1-0.4 * 2$

​ $=0.2$

​ $θ^2=θ^1-α*J^′(θ)$

​ $=0.2-0.4*0.4$

​ $=0.04$

​ $θ^3=0.008$

​ $θ^4=0.0016$

如图，经过四次运算，也就是走了四步，基本就抵达了函数的最低点，也就是山底

​

多变量函数的梯度下降

我们假设有一个目标函数：

​ $J(Θ)=θ_1^2+θ_2^2$

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

我们假设初始化起点

​ $Θ^0 = (1,3)$

初始化的学习率为：

​ $α = 0.1$

函数的梯度为：

​ $▽J(Θ)=<2θ_1, 2θ_2>$

进行多次迭代：

​ $Θ^0=(1,3)$

​ $Θ^1=Θ^0-α*▽J(Θ)$

​ $=(1, 3) - 0.1*(2, 6)$

​ $=(0.8, 2.4)$

​ $Θ^2=(0.8, 2.4)-0.1*(1.6, 4.8)$

​ $=(0.64, 1.92)$

​ $Θ^3 = (0.512, 1.536)$

​ $Θ^4=(0.4096, 1.2288)$

​ …

​ $Θ^{10} = (0.1073741824, 0.3221224372)$

​ …

​ $Θ^{50} = (1.1417981541647683e^{-05}, 3.425394462494306e^{-05})$

​ …

​ $Θ^{100} = (1.6296287810675902e^{-10}, 4.888886343202771e^{-10})$

我们发现已经基本靠近函数的最小值点：

​

梯度下降算法的实现（线性回归）

下面我们将用Python实现一个简单的梯度下降算法。场景是一个线性回归的例子；假设我们有一系列的点，如下图所示：

​

我们将用梯度下降算法来拟合出这条直线！

首先，我们需要定义一个代价函数，在这里我们选用 均方根代价函数：

​ $J(\Theta) = \frac{1}{2m}\sum_{i=1}^{m}(h_\Theta(x_i) - y_i^{'})$

公式说明：

• m是数据集中点的个数

• $\frac{1}{2}$ 是一个常量，这样是为了求梯度的时候，二次方乘下来就和这里的 $\frac{1}{2}$ 抵消了，自然就没有多余的常数系数，方便后续的计算，同时对结果不会有影响

• $y_i^{'}$ 是数据中对应 $x_i$ 的真实坐标值

• $h$ 是我们的预测函数，根据每一个输入 $x_i$ ,根据 $\Theta$ 计算得到预测值 $y_i$ , 即：

  $$y_i = h_\Theta(x_i) = \theta_0 + \theta_1x_i$$

我们可以根据代价函数看到，代价函数中的变量有练个，所以是一个多变量的梯度下降问题，秋姐出代价函数的梯度，也就是分别对两个变量进行微分

​ $\nabla J(\Theta) = \langle \frac{\delta J}{\delta \theta_0} , \frac{\delta J}{\delta \theta_1} \rangle$

​ $\frac{\delta J}{\delta \theta_0} = \frac{1}{m} \sum_{i=1}^{m}(h_\Theta(x_i) - y_i^{'})$

​ $= \frac{1}{m} \sum_{i=1}^{m}(y_i - y_i^{'})$

​ $\frac{\delta J}{\delta \theta_1} = \frac{1}{m} \sum_{i=1}^{m}(h_\Theta(x_i) - y_i^{'})x_i$

​ $= \frac{1}{m} \sum_{i=1}^{m}(y_i - y_i^{'})x_i$

明确了代价函数和梯度，以及预测函数的形式，我们就可以写代码了。但是在这之前，需要说明一点，就是为了方便代码编写，我们会将所有的公式都转换成矩阵形式，python中计算矩阵是非常方便的，同事代码页会变的非常简洁。

为了转换为矩阵的的计算，我们观测到预测函数的形式

​ $y_i = h_\Theta(x_i) = \theta_0 + \theta_1x_i$

我们有两个变量，为了这个公式的矩阵化，我们可以给每个点x增加一维，这一维的值固定为1，这一维将乘到 $\theta_0$上这样就方便我们统一矩阵化计算:

$$\vec{X} = \begin{pmatrix} 1 & x_1 \\\\ 1 & x_{2} \\\\ \vdots & \vdots \\\\ 1 & x_m \end{pmatrix} \qquad \vec{Y^\prime} = \begin{pmatrix} y_1^\prime \\\\ y_2^\prime \\\\ \vdots \\\\ y_m^\prime \end{pmatrix}$$ $$\vec{\Theta}=\begin{pmatrix} \theta_0 \\\\ \theta_1 \end{pmatrix}$$ $$\vec{Y} = \vec{X} \cdot \vec{\Theta} = \begin{pmatrix} y_1 \\\\ y_2 \\\\ \vdots \\\\\ y_m \end{pmatrix}$$

然后我们将代价函数和梯度转化向量成绩形式：

$$J(\Theta) = \frac{1}{2m}(\vec{Y} - \vec{Y^\prime})^T \cdot (\vec{Y} - \vec{Y^\prime})$$ $$\nabla J(\Theta) = \frac{1}{m}\vec{X}^T \cdot (\vec{Y} - \vec{Y^\prime})$$

说明：

• $\vec{\Theta}$ 为需要迭代求解的最优参数
• $\vec{X}、\vec{Y}^\prime$ 为已知的数据集
• $\vec{Y}$ 为当前 $\vec{\Theta}$ 参数下的预测值

Coding Time

首先，我们需要定义数据集合学习率：

import numpy as np
import matplotlib.pyplot as plt

# Prepare data

# Size of the points dataset.
m = 20

X0 = np.ones((m, 1))
X1 = np.arange(1, m+1).reshape(m, 1)
X = np.hstack((X0, X1))

# Points y-coordinate
y = np.array([
    3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
    11, 13, 13, 16, 17, 18, 17, 19, 21
]).reshape(m, 1)

y = np.array([
    3, 8, 5, 5, 2, 4, 7, 8, 11, 8, 12,
    11, 13, 13, 16, 17, 6, 17, 19, 21
]).reshape(m, 1)

plt.scatter(X1, y, marker='o', s=50, c='g')
plt.show()
# The Learning Rate alpha.
alpha = 0.01

接下来我们定义梯度函数：

def gradient_function(theta, X, y):
    '''Gradient of the function J definition.'''
    diff = np.dot(X, theta) - y
    return (1./m) * np.dot(np.transpose(X), diff)

最后就是算法的核心部分，梯度下降迭代计算

def gradient_descent(X, y, alpha):
    '''Perform gradient descent.'''
    theta = np.array([1, 1]).reshape(2, 1)
    gradient = gradient_function(theta, X, y)
    while not np.all(np.absolute(gradient) <= 1e-5):
        theta = theta - alpha * gradient
        gradient = gradient_function(theta, X, y)
    return theta

当梯度小于1e-5时，说明已经进入了比较平滑的状态，类似于山谷的状态，这时候再继续迭代效果也不大了，所以这个时候可以退出循环！

进行方法调用：

optimal = gradient_descent(X, y, alpha)
print('optimal:', optimal)

plt.scatter(X1, y, marker='o', s=50, c='g')
plt.plot([0,20], [optimal[0,0], 20*optimal[1,0]+optimal[0,0]], c='blue')
print optimal[1,0],optimal[0,0]
plt.show()

最终可看到结果如下：

​

作者小结

​ 至此，我们就基本介绍完了梯度下降法的基本思想和算法流程，并且用python实现了一个简单的梯度下降算法拟合直线的案例！
最后，我们回到文章开头所提出的场景假设:
这个下山的人实际上就代表了反向传播算法，下山的路径其实就代表着算法中一直在寻找的参数Θ，山上当前点的最陡峭的方向实际上就是代价函数在这一点的梯度方向，场景中观测最陡峭方向所用的工具就是微分 。在下一次观测之前的时间就是有我们算法中的学习率α所定义的。
可以看到场景假设和梯度下降算法很好的完成了对应！

看过不少梯度下降文章，这一篇讲解的最系统直观，自己记录一下；感谢作者！