本文循序渐进描述梯度下降算法，从导数的几何意义开始聊起，如果熟悉微积分可以跳过，主要内容如下：

一. 导数的几何意义
二. 偏导数
三. 什么是梯度
四. 梯度下降算法
- $α$ 是什么含义?
- 为什么是 $-$ ?
- 梯度下降举例一
- 梯度下降举例二
- 值得关注的一些问题
五. 梯度下降应用于线性回归
- 5.1 批量梯度下降
- 5.2 批量梯度下降算法python实现

一. 导数的几何意义

导数用来衡量函数对取值的微小变化有多敏感，如下图所示，假设有一辆汽车在行驶， $s(t)$ 是关于时间 $t$ 的行驶距离函数， $dt$ 表示一小段时间， $ds$ 表示 $dt$ 时间段内行驶的距离，导数表示，在 $t$ 点，当 $dt$ 趋近于 $0$ 时， $ds$ 和 $dt$ 的比值

导数含义

那么当趋近于时(注意，趋紧，但不是)，导数的几何含义是什么呢？我们来看下面一张动图，解释了导数在几何意义上表示函数图上某点切线的斜率：

导数与斜率.gif

关于使用链式求导法计算导数的两个例子如下：
$\frac{d(x^2)}{dx} =2x$
$\frac{d(5-θ)^2}{dθ} =-2(5-θ)(负号源于-θ)$

备注：
$\frac{d(x^2)}{dx} =2x$ 推导过程如下：
$\begin{eqnarray} \frac{d(x^2)}{dx} &=& \lim_{dx\rightarrow0}\frac{(x+dx)^2-x^2}{dx}\\ &=& \lim_{dx\rightarrow0}\frac{x^2+2xdx+dx^2-x^2}{dx}\\ &=& \lim_{dx\rightarrow0}\frac{2xdx+dx^2}{dx}\\ &=& \lim_{dx\rightarrow0}(2x+dx)\\ &=& 2x\\ \end{eqnarray}$

二. 偏导数

一元函数是从实数到实数的映射 $f:\mathbb{R} \to \mathbb{R}$ ，如果函数有多个变量呢？也就是说函数是从向量到实数的映射，那么这个函数就是多元函数(multivariate function)，即 $f:\mathbb{R}^n \to \mathbb{R}$ ，其中 $n$ 是输入向量的维度。例如函数 $f(θ)=θ_1^2+θ_2^2$ 是从二维实数向量 $θ=[θ_1,θ_2]$ 到实数的映射 $f:\mathbb{R}^2 \to \mathbb{R}$ 。偏导数是函数关于其中一个变量的导数而保持其他变量恒定。举几个偏导数的例子：
$\frac{∂}{∂x}f(x,y)=\frac{∂}{∂x}(x^2y^2) = 2xy^2$
$\frac{∂}{∂θ_2}f(θ_1,θ_2,θ_3)=\frac{∂}{∂θ_2}(0.55−(5θ_1 + 2θ_2 − 12θ_3)) = -2$
$\frac{∂}{∂θ_3}f(θ_1,θ_2,θ_3)=\frac{∂}{∂θ_3}(0.55−(5θ_1 + 2θ_2 − 12θ_3)) = 12$

三. 什么是梯度

多元函数的梯度是一个向量，其中每个分量与函数关于该分量的偏导数成比例。例如我们有三维多元函数 $f(θ_1,θ_2,θ_3)$ ，则梯度表示为：
$\nabla f(θ) = \left[\frac{\partial f(θ_1,θ_2,θ_3)}{\partial θ_1} \; , \; \frac{\partial f(θ_1,θ_2,θ_3)}{\partial θ_2} \; , \;\frac{\partial f(θ_1,θ_2,θ_3)}{\partial θ_3}\right]$
例如： $f(θ) = 0.55−(5θ_1 + 2θ_2 − 12θ_3)$ ，则 $f(θ)$ 的梯度表示为：
$\nabla f(θ) = \left[\frac{∂f}{∂θ_1}, \frac{∂f}{∂θ_2}, \frac{∂f}{∂θ_3}\right] = \left[ -5, -2, 12\right]$
假设函数 $f(θ_1，θ_2，θ_3)$ 表示一个房间的在点 $[θ_1，θ_2，θ_3]$ 的温度，如果我们在 $θ_1$ 方向上迈出一小步，记录温度的变化，我们得到 $f$ 相对于 $θ_1$ 方向的导数， $\frac{\partial f(θ_1,θ_2,θ_3)}{\partial θ_1}$ ，让它的值为 $5$ ，之后我们在其他两个方向重复这个过程，我们将得到温度在 $θ_2$ 和 $θ_3$ 方向上的变化，让它们的值分别为 $15$ 和 $0$ 。此时
$\nabla f(θ) = \left[\frac{∂f}{∂θ_1}, \frac{∂f}{∂θ_2}, \frac{∂f}{∂θ_3}\right] = \left[ 5, 15, 0\right]$
由于在 $θ_2$ 方向上的温度变化是 $θ_1$ 方向上温度变化的 $3$ 倍，因此如果在 $[5,15,0]$ 方向上迈出一步，我们将得到函数 $f(θ_1，θ_2，θ_3)$ 的最大温度变化量。因此，梯度向量给出了多元函数的最大变化量和方向。

四. 梯度下降算法

梯度下降算法是通过逐步迭代达到函数最小值的算法(不是所有情况都能达到最小值，有一些注意事项后续说明)，例如下图中的红色圆点：

梯度下降图例.png

想象一下我们在徒步下山，我们不能从全局的视野找到最快的下山路径，我们怎样该怎么走呢？是不是会看看周围，选择一条当前最陡峭的下坡路？怎么找这个方向呢？这个方向是上升最快的反方向。第三节中我们介绍了梯度向量给出了多元函数的最大变化量和方向，这意味着，如果我们在点，想要移动到附近的最低点（也就是“局部最小值”），我们的下一步应该这样计算：

梯度下降迭代公式.png

$α$ 是什么含义?
在梯度下降算法中被称作为学习率或者步长，意味着我们可以通过α来控制每一步走的距离，不能太大也不能太小，太小的话，可能导致迟迟走不到最低点，太大的话，会导致错过最低点。
(感兴趣的小伙伴可以尝试在谷歌机器学习课程上的调节学习率看效果https://developers.google.com/machine-learning/crash-course/fitter/graph)

为什么是 $-$ ?
梯度前加一个负号，表示朝着梯度相反的方向前进，我们在前文提到，梯度的方向就是函数在此点上升最快的方向，而我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号。

梯度下降举例一
我们来看下只有一个变量时梯度下降的计算，由于梯度下降算法常应用于求解损失函数，而损失函数通常用 $J(θ)$ 来表示，假设 $J(θ)=θ^2$ ，则导数为 $J′(θ) = 2θ$ ，我们选择 $θ^0=1$ ， $α=0.4$ ，则:
$\begin{eqnarray} θ^0 &=& 1\\ θ^1 &=& θ^0 − α ∗ J′(θ^0)\\ &=& 1−0.4∗2\\ &=& 0.2\\ θ^2 &=& θ^1 − α ∗ J′(θ^1)\\ &=& 0.04\\ θ^3 &=& 0.008\\ θ^4 &=& 0.0016\\ ... \end{eqnarray}$

梯度下降过程图例.png

而当我们将学习率设置为 $α=0.75$ 时：
$\begin{eqnarray} θ^0 &=& 1\\ θ^1 &=& θ^0 − α ∗ J′(θ^0)\\ &=& 1−0.75∗2\\ &=& -0.5\\ θ^2 &=& θ^1 − α ∗ J′(θ^1)\\ &=& -1.25 \\ ... \end{eqnarray}$

设置较大学习率错过最低点.png

如图所示，到了最低点左侧的位置，并且的值继续向左偏移，错过了最低点：

梯度下降举例二
我们来看下有两个变量时梯度下降的计算过程，假设 $J(Θ) = θ_1^2 + θ_2^2$ . 容易看出在 $(0,0)$ 点， $J$ 达到最小值。我们来看下能否通过梯度下降得到这个结果。设置初始值 $Θ^0 = (1, 3)，α = 0.1$ ， $∇J(Θ)$ 为：
$∇J(Θ) = ⟨2θ1, 2θ2⟩$
在 $(1, 3)$ 点，梯度向量为 $\left[2, 6 \right]$ 。
$\begin{eqnarray} Θ^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.2288000000000001) \\ ...\\ Θ^{10} &=& (0.10737418240000003, 0.32212254720000005) \\ ...\\ Θ^{50} &=& (1.1417981541647683e^{−05}, 3.425394462494306e^{−05}) \\ ...\\ Θ^{100} &=& (1.6296287810675902e^{−10}, 4.888886343202771e^{−10}) \\ \end{eqnarray}$

image.png

可以看出我们的确在不断接近最小值，即。

最后，有一些非常重要的问题值得我们关注下～

函数必须是可微分的 (differentiable)（左侧示例）；
学习率 $α$ 不应太小（中间示例）或太大（右侧示例）。

梯度下降值得关注的问题.png

五. 梯度下降应用于线性回归

梯度下降算法是线性回归中用于找出误差或成本函数最小值的方法之一。请注意，错误或成本函数必须是可微分的才能使用梯度下降。这是将误差进行平方的原因之一，使用绝对值计算误差可能会导致“拐角”，如图【梯度下降值得关注的问题】左侧所示。

5.1 批量梯度下降

在监督学习中，我们需要决定如何表示函数/假设h，而线性回归函数则是首选：
$h_θ(x) = θ_0 + θ_1x_1 + θ_2x_2$
其中， $θ$ 是 $X$ 到 $Y$ 映射的参数（也称为权重），为了书写简便，通常去掉下标θ，写作 $h_θ(x)$ ，同时引入 $x_0=1$ （截距），即：
$h(x) = \sum_{i=0}^nθ_ix_i =θ^Tx$
等式右侧是将 $θ$ 和 $x$ 看作是向量， $n$ 是输入的参数个数（不算 $x_0$ ），那么问题来了，给定一个训练数据集，怎么确定参数 $θ$ ？比较合理的想法是让假设 $h(x)$ 尽量接近 $y$ ，至少接近已有的训练数据集。定义成本函数（cost function）来表示 $h(x)$ 和 $y$ 值相接近的程度：
$J(θ) = \frac {1} {2}\sum_{i=1}^m(h_θ(x^{(i)})-y^{(i)})^2$
这里的系数1/2是为了后面求解偏导数时可以与系数相互抵消。我们的目标是要求解 $θ$ 使成本函数 $J(θ)$ 尽可能的小。使用梯度下降算法进行求解：
$θ_j := θ_j - α\frac{∂}{∂θ_j}J(θ)$
(对所有 $j=0,...n$ 求解 $θ$ )
首先，我们先求解 $\frac{∂}{∂θ_j}J(θ)$ :
$\begin{eqnarray} \frac{∂}{∂θ_j}J(θ) &=& \frac{∂}{∂θ_j}\frac {1} {2}(h_θ(x)-y)^2\\ &=& 2 \cdot \frac {1} {2} \cdot (h_θ(x)-y) \cdot \frac{∂}{∂θ_j}(h_θ(x)-y)\\ &=& (h_θ(x)-y) \cdot \frac{∂}{∂θ_j}(\sum_{i=0}^{n}θ_ix_i-y)\\ &=& (h_θ(x)-y) x_j \end{eqnarray}$

对于只含有一组数据的训练样本，我们可以得到更新 $θ$ 的规则为：
$θ_j := θ_j + α(y^{(i)}- h_θ(x^{(i)}) x_j^{(i)}$
扩展到多组数据样本，更新公式为：
$Repeat$ $until$ $convergence$ $\{$
$θ_j := θ_j + α\sum_{i=1}^m((y^{(i)}- h_θ(x^{(i)}))x_j^{(i)}$

$\}$
这种方法称为批处理梯度下降算法，这种更新算法所需要的运算成本很高，尤其是数据量较大时。考虑下面的更新算法：

该算法又叫做随机梯度下降法，这种算法不停的更新θ，每次使用一个样本数据进行更新。当数据量较大时，一般使用后者算法进行更新。
$Loop$ $\{$
$from$ $i=1$ $to$ $m,$ $\{$
$θ_j := θ_j + α\sum_{i=1}^m((y^{(i)}- h_θ(x^{(i)}))x_j^{(i)}$
$\}$
$\}$

5.2 批量梯度下降算法python实现

假设有原始数据集：

1.1 1.5 2.5
1.3 1.9 3.2
1.5 2.3 3.9
1.7 2.7 4.6
1.9 3.1 5.3
2.1 3.5 6
2.3 3.9 6.7
2.5 4.3 7.4
2.7 4.7 8.1
2.9 5.1 8.8

使用批量梯度下降算法求解线性回归代码如下：

import numpy as np

"""
    作者：_与谁同坐_
    功能：使用批量梯度下降法求解线性回归
    版本: 1.0
    日期：2019/03/15
"""

def batch_gradient_descent(data_set):
    """
    梯度下降法求解线性回归参数θ
    :param data_set: 原始数据集
    :return: 参数θ
    """
    m, n = np.shape(data_set)
    # 选取训练数据X，并补充参数x_0=1
    train_data = np.ones((m, n))
    train_data[:, :-1] = data_set[:, :-1]
    x = train_data
    # 最后一列作为y
    y = data_set[:, -1]
    # 初始化系数θ
    theta = np.ones(n)
    # 学习率α
    alpha = 0.1
    # 迭代次数
    max_steps = 5000

    x_trans = x.transpose()
    for i in range(0, max_steps):
        hypothesis = np.dot(x, theta)
        # 计算损失
        loss = hypothesis - y
        # 计算梯度
        gradient = np.dot(x_trans, loss) / m
        # 迭代逐步求解θ
        theta = theta - alpha * gradient

    return theta


def predict(data_predict_set, theta):
    """
    使用求解的线性函数参数θ来预测结果
    :param x: 待预测的数据x
    :param theta: 参数θ
    :return: 预测出的结果
    """
    m, n = np.shape(data_predict_set)
    x_data = np.ones((m, n+1))
    x_data[:, :-1] = data_predict_set
    y_predict = np.dot(x_data, theta)
    return y_predict


def main():
    file_path = r"/Users/xxx/mldata/house.csv"
    data_train_set = np.genfromtxt(file_path, delimiter=' ')
    theta = batch_gradient_descent(data_train_set)
    data_predict_set = np.array([[3.1, 5.5], [3.3, 5.9], [3.5, 6.3], [3.7, 6.7], [3.9, 7.1]])
    print(predict(data_predict_set, theta))


if __name__ == '__main__':
    main()

固定学习率为0.05，更改迭代次数为5000时，结果为：

[ 9.5 10.2 10.9 11.6 12.3]

参考资料
https://storage.googleapis.com/supplemental_media/udacityu/315142919/Gradient%20Descent.pdf
https://najeebkhan.github.io/blog/VecCal.html
https://www.jianshu.com/p/9bf3017e2487
https://www.bilibili.com/video/av24325548/?p=1
http://cs229.stanford.edu/notes/cs229-notes1.pdf

https://www.cnblogs.com/pinard/p/5970503.html

梯度下降（Gradient Descent）数学原理分析与实例