梯度下降（Gradient descent）

梯度下降算法的定位

梯度下降算法是一种求解局部最小值的算法，在线性模型和非线性模型中都可以用。

在用某个模型对数据进行拟合时，会用损失函数（或者叫错误函数等等）去评估拟合的准确性，这个时候往往要找到损失函数的最小值，即求出达到最佳拟合效果时各参数的值。求函数的最小值时往往用到梯度下降法。

从二维空间的线性回归说起

假设平面上有n个点: (x1, y1), (x2, y2), …, (xn, yn).
现在要找出一条直线去拟合这些点（即找出x和y的线性关系）。

首先要构造一个损失函数去评估拟合的好坏，最小二乘法是最常见的方法（其实就是用误差的平方和去构造损失函数）。
设拟合函数为 $\hat{y}=mx+b (\hat{y}为x对应的y的估计值)$ ，则损失函数为：
$E=\sum_{i=1}^{n}(mx_i+b-y_i)^2$

下面有两种方法去求参数m和b:
1，传统的统计学方法：求m和b的值使得E最小。

要求函数的最小值，首先想到的就是求导数，令导数等于零（这个例子是奏效的，应该能够证明这个函数是凸函数，用其它先验知识也能知道它的形状）。

于是分别求m和b的偏导数，令其等于零：
$\frac{\partial E}{\partial m}=2\sum_{i=1}^{n}(mx_i+b-y_i)x_i=0$
$\frac{\partial E}{\partial b}=2\sum_{i=1}^{n}(mx_i+b-y_i)=0$

解得：
$m=\frac{\overline{xy}-\bar{x}\bar{y}}{\overline{x^2}-\bar{x}^2}$

$b=\frac{\overline{x^2}\overline{y}-\overline{xy}\bar{x}}{\overline{x^2}-\bar{x}^2}$

2，用梯度下降的方法去求m和b
随便设定一个初始的m和b值，同时learning rate ( $\alpha$ )也需要提前设置。

不妨设 $m_0=b_0=0, \alpha = 0.0001$
经过一次迭代， $m_0和b_0$ 分别变成 $m_1和b_1$ ：
$m_1=m_0-\alpha\frac{\partial E}{\partial m_0}$
$b_1=b_0-\alpha\frac{\partial E}{\partial b_0}$
在 $m_0和b_0$ 都已知的情况下， $\frac{\partial E}{\partial m_0}和\frac{\partial E}{\partial b_0}$ 很容易求出来。
。。。
经过N（比如10000，一般要人为设置次数）次这样的迭代，就会得到 $m_N和b_N$ 的值，不出意外，这里的 $m_N和b_N$ 跟传统的解法得到的值基本一样。

拓展到多维空间的线性回归

假设在n+1维空间，有m个点：(x11, x12, …, x1n, y1), (x21, x22, …, x2n, y2), …, (xm1, xm2, …, xmn, ym)

用最小二乘法去构造损失函数：
$E=\sum_{i=1}^{m}(w_1x_{i1}+w_2x_{i2}+ ... +w_nx_{in} +b-y_i)^2$
(向量写法为 $E=\sum_{i=1}^{m}(w^Tx_i+b-y_i)^2$ )

对每一个系数分别求导数为：
$\frac{\partial E}{\partial w_1}=2\sum_{i=1}^{m}(w^Tx_i+b-y_i)x_{i1}$
$\frac{\partial E}{\partial w_2}=2\sum_{i=1}^{m}(w^Tx_i+b-y_i)x_{i2}$
…
$\frac{\partial E}{\partial w_n}=2\sum_{i=1}^{m}(w^Tx_i+b-y_i)x_{in}$
$\frac{\partial E}{\partial b}=2\sum_{i=1}^{m}(w^Tx_i+b-y_i)$
写成梯度的形式为：
$\nabla E=(\frac{\partial E}{\partial w_1}, \frac{\partial E}{\partial w_2}, ..., \frac{\partial E}{\partial w_n}, \frac{\partial E}{\partial b})^T$
梯度实际上就是对多变量函数的每一个变量求偏导数，再按一定的顺序组成向量或者矩阵。