[数据结构与算法] 梯度下降算法总结

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 梯度下降算法总结 -> 正文阅读

[数据结构与算法]梯度下降算法总结

文章目录

参考：梯度下降算法原理讲解

1. 概述

梯度下降（gradient descent）在机器学习中应用十分的广泛，不论是在线性回归还是Logistic回归中，它的主要目的是通过迭代找到目标函数的最小值，或者收敛到最小值。
本文将从一个下山的场景开始，先提出梯度下降算法的基本思想，进而从数学上解释梯度下降算法的原理，解释为什么要用梯度，最后实现一个简单的梯度下降算法的实例！

2. 梯度下降算法

2.1 场景假设

梯度下降法的基本思想可以类比为一个下山的过程。

假设这样一个场景：一个人被困在山上，需要从山上下来（找到山的最低点，也就是山谷）。但此时山上的浓雾很大，导致可视度很低；因此，下山的路径就无法确定，必须利用自己周围的信息一步一步地找到下山的路。这个时候，便可利用梯度下降算法来帮助自己下山。怎么做呢，首先以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着下降方向走一步，然后又继续以当前位置为基准，再找最陡峭的地方，再走直到最后到达最低处；同理上山也是如此，只是这时候就变成梯度上升算法了

2.2 梯度下降

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

首先，我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值，也就是山底。根据之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，然后沿着此方向向下走，对应到函数中，就是找到给定点的梯度，然后朝着梯度相反的方向，就能让函数值下降的最快！因为梯度的方向就是函数之变化最快的方向（在后面会详细解释）
所以，我们重复利用这个方法，反复求取梯度，最后就能到达局部的最小值，这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。那么为什么梯度的方向就是最陡峭的方向呢？接下来，我们从微分开始讲起：

2.2.1 微分

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

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

几个微分的例子：

单变量的微分，函数只有一个变量时
1. $\frac{d(x^2)}{dx}=2x$
2. $\frac{d(-2y^5)}{dy}=-10y^4$
3. $\frac{d(5-\theta)^2}{d\theta}=-2(5-\theta)$
多变量的微分，当函数有多个变量的时候，即分别对每个变量进行求微分
1. $\frac{\partial}{\partial x}\left(x^{2} y^{2}\right)=2 x y^{2}$
2. $\frac{\partial}{\partial y}\left(-2 y^{5}+z{2}\right)=-10 y^{4} $
3. $\frac{\partial}{\partial \theta_{2}}\left(5 \theta_{1}+2 \theta_{2}-12 \theta_{3}\right)=2 $
4. $\frac{\partial}{\partial \theta_{2}}\left(0.55-\left(5 \theta_{1}+2 \theta_{2}-12 \theta_{3}\right)\right)=-2$

2.2.2 梯度

梯度实际上就是多变量微分的一般化。
下面这个例子：

$\begin{array}{l} J(\Theta)=0.55-\left(5 \theta_{1}+2 \theta_{2}-12 \theta_{3}\right) \\ \nabla J(\Theta)=\left\langle\frac{\partial J}{\partial \theta_{1}}, \frac{\partial J}{\partial \theta_{2}}, \frac{\partial J}{\partial \theta_{3}}\right\rangle=(-5,-2,12) \end{array}$

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

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

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

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

2.3 数学解释

首先给出数学公式：
$\Theta^1=\Theta^0+\alpha\nabla J(\Theta)$
此公式的意义是： $J$ 是关于 $\Theta$ 的一个函数， $\Theta$ 是一个向量，我们当前所处的位置为 $\Theta ^0$ 点，要从这个点走到 $J$ 的最小值点，也就是山底。首先我们先确定前进的方向，也就是梯度的反向，然后走一段距离的步长，也就是 $\alpha$ ，走完这个段步长，就到达了 $\Theta ^1$ 这个点！

2.3.1 $\alpha$ 学习率、步长

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

2.3.2 梯度的方向

梯度前加一个负号，就意味着朝着梯度相反的方向前进！我们在前文提到，梯度的方向实际就是函数在此点上升最快的方向！而我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号；那么如果时上坡，也就是梯度上升算法，当然就不需要添加负号了。

3. 实例

3.1 单变量函数的梯度下降

我们假设有一个单变量的函数
$J(\theta) = \theta ^ 2$
函数的微分，直接求导就可以得到
$J^{'}(\theta)=2\theta$
初始化，也就是起点，起点可以随意设置，这里设置为 $1$
$\theta ^0 = 1$
学习率也可以随意的设置，这里设置为 $0.4$
$\alpha =0.4$
根据梯度下降的计算公式
$\Theta^1=\Theta^0+\alpha\nabla J(\Theta)$
我们开始进行梯度下降的迭代计算过程：
$\begin{array}{l} \theta ^0=1\\ \theta^1=\theta^0-\alpha \cdot J^{'}(\theta^{0})=1-0.4\times 2=0.2\\ \theta^2=\theta^1-\alpha \cdot J^{'}(\theta^{1})=0.2-0.4\times 0.4=0.04\\ \theta^3=0.008\\ \theta^4=0.0016\\ \end{array}$
如图，经过四次运算，也就是走了四步，基本就抵达了函数的最低点，也就是山底。

3.2 多变量函数的梯度下降

我们假设有一个目标函数
$J(\Theta)=\theta^2_1+\theta^2_2$
现在要通过梯度下降法计算这个函数的最小值。我们通过观察就能发现最小值其实就是 $(0, 0)$ 点。但是接下来，我们会从梯度下降算法开始一步步计算到这个最小值！

我们假设初始的起点为：
$\Theta^0=(1, 3)$
初始的学习率为：
$\alpha=0.1$
函数的梯度为：
$\nabla J(\Theta)=<2\theta_1,2\theta_2>$
进行多次迭代：
$\begin{array}{l} \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.5124,1.536) \\ \Theta^{4}=(0.4096,1.228800000000001) \\ \vdots \\ \Theta^{10}=(0.1073741824000003,0.32212254720000005) \\ \vdots \\ \Theta^{50}=\left(1.141798154164342 e^{-05}, 3.42539442494306 e^{-05}\right) \\ \vdots \\ \Theta^{100}=\left(1.6296287810675902 e^{-10}, 4.8888886343202771 e^{-10}\right) \end{array}$
我们发现，已经基本靠近函数的最小值点

4. 代码实现

4.1 场景分析

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

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

首先，我们需要定义一个代价函数，在此我们选用均方误差代价函数（也称平方误差代价函数）
$J(\Theta)=\frac{1}{2m}\sum^{m}_{i=1}(h_{\theta}(x^{(i)})-y_{(i)})^2$
此公式中

$m$ 是数据集中数据点的个数，也就是样本数
$\frac{1}{2}$ 是一个常量，这是为了在求梯度的时候，二次方乘下来的 $2$ 就和这里的 $\frac{1}{2}$ 抵消了，自然就没有多余的常数系数，方便后续的计算，同时对结果不会有影响
$y$ 是数据集中每个点的真是 $y$ 坐标的值，也就是类标签
$h$ 是我们的预测函数（假设函数），根据每一个输入 $x$ ，根据 $\Theta$ 计算得到预测的 $y$ 值，即 $h_{\Theta}(x^{(i)})=\Theta_0+\Theta_1x^{(i)}$

我们可以根据代价函数看到，代价函数中的变量有两个 $\Theta_0、\Theta_1$ ，所以是一个多变量的梯度下降问题，求解出代价函数的梯度，也就是分别对两个变量进行微分
$\begin{array}{l} \nabla J(\Theta)=\left\langle\frac{\delta J}{\delta \Theta_{0}}, \frac{\delta J}{\delta \Theta_{1}}\right\rangle \\ \frac{\delta J}{\delta \Theta_{0}}=\frac{1}{m} \sum_{i=1}^{m}\left(h_{\Theta}\left(x^{(i)}\right)-y^{(i)}\right) \\ \frac{\delta J}{\delta \Theta_{1}}=\frac{1}{m} \sum_{i=1}^{m}\left(h_{\Theta}\left(x^{(i)}\right)-y^{(i)}\right) x^{(i)} \end{array}$
明确了代价函数和梯度，以及预测的函数形式。我们就可以开始编写代码了。但在这之前，需要说明一点，就是为了方便代码的编写，我们会将所有的公式都转换为矩阵的形式，python中计算矩阵是非常方便的，同时代码也会变得非常的简洁。

为了转换为矩阵的计算，我们观察到预测函数的形式
$h_{\Theta}(x^{(i)})=\Theta_0+\Theta_1x^{(i)}$
我们有两个变量，为了对这个公式进行矩阵化，我们可以给每一个点 $x$ 增加一维，这一维的值固定为 $1$ ，这一维将会乘到 $\Theta_0$ 上。这样就方便我们统一矩阵化的计算
$(x^{(i)},y^{(i)})\to (1,x^{(i)},y^{(i)})$
然后我们将代价函数和梯度转化为矩阵向量相乘的形式
$\begin{array}{l} J(\Theta)=\frac{1}{2 m}(X \Theta-\vec{y})^{T}(X \Theta-\vec{y}) \\ \nabla J(\Theta)=\frac{1}{m} X^{T}(X \Theta-\vec{y}) \end{array}$
为了防止我自己看不懂：
$\begin{aligned} &X \Theta-\vec{y}\\ =&\begin{pmatrix} 1 & x^1 \\ 1 & x^2 \\ \vdots & \vdots \\ 1 & x^m \end{pmatrix} \cdot \begin{pmatrix} \theta_0\\ \theta_1 \end{pmatrix} -\begin{pmatrix} y^1 \\ y^2\\ \vdots \\ y^m \end{pmatrix} \\ =&\begin{pmatrix} \theta_0 + \theta_1x^1-y^1 \\ \theta_0 + \theta_1x^2-y^2 \\ \vdots \\ \theta_0 + \theta_1x^m-y^m \\ \end{pmatrix} \\ \end{aligned}$

$\begin{aligned} &X^T(X\Theta-\vec{y})\\ =& \begin{pmatrix} 1 & 1&\cdots & 1 \\ x^1 &x^2 & \cdots & x^m \end{pmatrix} \begin{pmatrix} \theta_0 + \theta_1x^1-y^1 \\ \theta_0 + \theta_1x^2-y^2 \\ \vdots \\ \theta_0 + \theta_1x^m-y^m \\ \end{pmatrix} \\ =& \begin{pmatrix} m\theta_0 +\theta_1 \sum x^{(i)}-\sum y^{(i)}\\ (m\theta_0 +\theta_1 \sum x^{(i)}-\sum y^{(i)})x^{(i)} \end{pmatrix} \\ =&\begin{pmatrix} \sum_{i=1}^{m}\left(h_{\Theta}\left(x^{(i)}\right)-y^{(i)}\right)\\ \sum_{i=1}^{m}\left(h_{\Theta}\left(x^{(i)}\right)-y^{(i)}\right)x^{(i)} \end{pmatrix} \\ =&m\begin{pmatrix} \frac{\delta J}{\delta \Theta_{0}} \\ \frac{\delta J}{\delta \Theta_{1}} \end{pmatrix} \end{aligned}$

4.2 代码

from numpy import *

# 数据集大小 即20个数据点
m = 20
# x的坐标以及对应的矩阵
X0 = ones((m, 1))  # 生成一个m行1列的向量，也就是x0，全是1
X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量，也就是x1，从1到m
X = hstack((X0, X1))  # 按照列堆叠形成数组，其实就是样本数据
# 对应的y坐标
Y = array([
    3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
    11, 13, 13, 16, 17, 18, 17, 19, 21
]).reshape(m, 1)
# 学习率
alpha = 0.01


# 定义代价函数
def cost_function(theta, X, Y):
    diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘，就需要用到dot()
    return (1/(2*m)) * dot(diff.transpose(), diff)


# 定义代价函数对应的梯度函数
def gradient_function(theta, X, Y):
    diff = dot(X, theta) - Y
    return (1/m) * dot(X.transpose(), diff)


# 梯度下降迭代
def gradient_descent(X, Y, alpha):
    theta = array([1, 1]).reshape(2, 1)
    gradient = gradient_function(theta, X, Y)
    while not all(abs(gradient) <= 1e-5):
        theta = theta - alpha * gradient
        gradient = gradient_function(theta, X, Y)
    return theta


optimal = gradient_descent(X, Y, alpha)
print('optimal:', optimal)
print('cost function:', cost_function(optimal, X, Y)[0][0])


# 根据数据画出对应的图像
def plot(X, Y, theta):
    import matplotlib.pyplot as plt
    ax = plt.subplot(111)  # 这是我改的
    ax.scatter(X, Y, s=30, c="red", marker="s")
    plt.xlabel("X")
    plt.ylabel("Y")
    x = arange(0, 21, 0.2)  # x的范围
    y = theta[0] + theta[1]*x
    ax.plot(x, y)
    plt.show()


plot(X1, Y, optimal)

5. 小结

最后，我们回到文章开头所提出的场景假设:
这个下山的人实际上就代表了反向传播算法，下山的路径其实就代表着算法中一直在寻找的参数 $\Theta$ ，山上当前点的最陡峭的方向实际上就是代价函数在这一点的梯度方向，场景中观测最陡峭方向所用的工具就是微分。在下一次观测之前的时间就是有我们算法中的学习率 $\alpha$ 所定义的。
可以看到场景假设和梯度下降算法很好的完成了对应！