用人话讲明白梯度下降Gradient Descent（以求解多元

作者: 化简可得 | 来源:发表于2020-05-01 22:55 被阅读0次

文章目录
1.梯度
2.多元线性回归参数求解
3.梯度下降
4.梯度下降法求解多元线性回归

梯度下降算法在机器学习中出现频率特别高，是非常常用的优化算法。

本文借多元线性回归，用人话解释清楚梯度下降的原理和步骤。

1.梯度

梯度是什么呢？

我们还是从最简单的情况说起，对于一元函数来讲，梯度就是函数的导数。

而对于多元函数而言，梯度是一个向量，也就是说，把求得的偏导数以向量的形式写出来，就是梯度。

例如，我们在用人话讲明白线性回归LinearRegression一文中，求未知参数 $\beta_{0}$ 和 $\beta_{1}$ 时，对损失函数求偏导，此时的梯度向量为 $(\frac{∂Q}{∂\beta_{0}}, \frac{∂Q}{∂\beta_{1}})^T$ ，其中：

$\frac{\partial Q}{\partial \beta_{0}}=2\sum_{1}^{n}{(y_{i}-\hat{\beta_{0}}-\hat{\beta_{1}}x_{i})}$

$\frac{\partial Q}{\partial \beta_{1}}=2\sum_{1}^{n}{(y_{i}-\hat{\beta_{0}}-\hat{\beta_{1}}x_{i})x_{i}}$

那篇文章中，因为一元线性回归中只有2个参数，因此令两个偏导数为0，能很容易求得 $\beta_{0}$ 和 $\beta_{1}$ 的解。

但是，这种求导的方法在多元回归的参数求解中就不太实用了，为什么呢？

2.多元线性回归参数求解

多元线性回归方程的一般形式为：

$y={\beta}_{0}+{\beta}_{1} {x}_{\mathbf{1} }+{\beta}_{2} {x}_{2 }+\cdots+{\beta}_{p}{x}_{p}$
可以简写为矩阵形式（一般加粗表示矩阵或向量）：
$\boldsymbol{Y}=\boldsymbol{X}\boldsymbol{\beta}$
其中， $\boldsymbol{Y}=\left[\begin{array}{c}y_{1} \\ y_{2} \\ \vdots \\ y_{n}\end{array}\right], \boldsymbol{X}=\left[\begin{array}{cccc}1 & x_{11} & \cdots & x_{1 p} \\ 1 & x_{21} & \cdots & x_{2 p} \\ \vdots & \vdots & & \vdots \\ 1 & x_{n 1} & \cdots & x_{n p}\end{array}\right], \boldsymbol{\beta}=\left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]$

之前我们介绍过一元线性回归的损失函数可以用残差平方和：
$Q=\sum_{i=1}^{n}\left(y_{i}-\hat{y}_{i}\right)^{2}$

代入多元线性回归方程就是：
$Q=\sum_{i=1}^{n}\left(y_{i}-\hat\beta_{0}-\hat\beta_{1} x_{i 1}-\ldots-\hat\beta_{p} x_{i p}\right)^{2}$
用矩阵形式表示：
$\begin{aligned} Q &=(\boldsymbol{X}\boldsymbol{\beta}-\boldsymbol{Y})^T(\boldsymbol{X}\boldsymbol{\beta}-\boldsymbol{Y}) \\ & =(\boldsymbol \beta^{T} \boldsymbol{X}^{T}-\boldsymbol{Y}^{T})(\boldsymbol{X} \boldsymbol\beta-\boldsymbol{Y}) \\ & =\boldsymbol\beta^{T} \boldsymbol{X}^{T} \boldsymbol{X} \boldsymbol\beta-\boldsymbol\beta^{T} \boldsymbol{X}^{T} \boldsymbol{Y}-\boldsymbol{Y}^{T} \boldsymbol{X} \boldsymbol\beta+\boldsymbol{Y}^{T} \boldsymbol{Y}\end{aligned}$

上面的展开过程涉及矩阵转置，这里简单提一下矩阵转置相关运算，以免之前学过但是现在忘了：
$(A+B)^{T}=A^{T}+B^{T}$

$(A B)^{T}=B^{T} A^{T}$

好了，按照一元线性回归求解析解的思路，现在我们要对Q求导并令导数为0（原谅我懒，后面写公式就不对向量或矩阵加粗了，大家能理解就行）：
$\begin{aligned} \frac{\partial Q}{\partial \beta}=2 X^{T} X \beta-X^{T} Y-X^{T} Y &=0 \\ 2X^{T} X \beta-2X^{T} Y &=0 \\ X^{T} X \beta&=X^{T} Y \\ \beta &=\left(X^{T} X\right)^{-1} X^{T} Y \end{aligned}$

上面的推导过程涉及矩阵求导，这里以 ${Y}^{T} {X} \beta$ 求导为例展开讲下，为什么 $\frac{\partial {Y}^{T} {X} \beta}{\partial \beta}={X}^{T} {Y}$ ，其他几项留给大家举一反三。

首先：
$\begin{aligned} \frac{\partial {Y}^{T} {X} \beta}{\partial \beta} = \frac{\partial \left((y_{1}, y_{2}, \dots,y_{n}) \left[\begin{array}{cccc}1 & x_{11} & \cdots & x_{1 p} \\ 1 & x_{21} & \cdots & x_{2 p} \\ \vdots & \vdots & & \vdots \\ 1 & x_{n 1} & \cdots & x_{n p}\end{array}\right] \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]\right)} {\partial \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]} \end{aligned}$

为了直观点，我们将 ${Y}^{T} {X}$ 记为A，因为Y是n维列向量，X是n×(p+1)的矩阵，因此 ${Y}^{T} {X}$ 是(p+1)维行向量：
$(y_{1}, y_{2}, \dots,y_{n}) \left[\begin{array}{cccc}1 & x_{11} & \cdots & x_{1 p} \\ 1 & x_{21} & \cdots & x_{2 p} \\ \vdots & \vdots & & \vdots \\ 1 & x_{n 1} & \cdots & x_{n p}\end{array}\right] = (\alpha_{0}, \alpha_{1}, \dots,\alpha_{p})$
那么上面求导可以简写为：
$\begin{aligned} \frac{\partial {Y}^{T} {X} \beta}{\partial \beta} = \frac{\partial \left((\alpha_{0}, \alpha_{1}, \dots,\alpha_{p}) \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]\right)} {\partial \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]}= \frac{\partial (\alpha_{0}\beta_{0}+\dots+\alpha_{p}\beta_{p})} {\partial \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]} \end{aligned}$

这种形式的矩阵求导属于分母布局，即分子为行向量或者分母为列向量（这里属于后者）。

搞不清楚的可以看看这篇：矩阵求导实例，这里我直接写出标量/列向量求导的公式，如下（y表示标量，X表示列向量）：
$\frac{\partial y}{\partial {X}}= \left[\begin{array}{c} \frac{\partial y}{\partial x_{1}} \\ \frac{\partial y}{\partial x_{2}} \\ \vdots \\ \frac{\partial y}{\partial x_{n}} \end{array}\right]$

根据上式，显然有：
$\frac{\partial (\alpha_{0}\beta_{0}+\dots+\alpha_{p}\beta_{p})} {\partial \left[\begin{array}{c}\beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{p}\end{array}\right]} = {\left[\begin{array}{c} \frac{\partial \alpha_{0}\beta_{0}}{\partial \beta_{0}} \\ \frac{\partial \alpha_{1}\beta_{1}}{\partial \beta_{1}} \\ \vdots \\ \frac{\partial \alpha_{p}\beta_{p}}{\partial \beta_{p}} \end{array}\right]}= \left[\begin{array}{c}\alpha_{0} \\ \alpha_{1} \\ \vdots \\ \alpha_{p}\end{array}\right]$

前面我们将 ${Y}^{T} {X}$ 记为A， $A=(\alpha_{0}, \alpha_{1}, \dots,\alpha_{p})$ ，那么上面算出来的结果就是 ${A}^{T}$ ，即 ${X}^{T} {Y}$ 。

说了这么多有的没的，最终我想说是的 $\beta=\left(X^{T} X\right)^{-1} X^{T} Y$ ，里面涉及到矩阵求逆，但实际问题中可能X没有逆矩阵，这时计算的结果就不够精确。

第二个问题就是，如果维度多、样本多，即便有逆矩阵，计算机求解的速度也会很慢。

所以，基于上面这两点，一般情况下我们不会用解析解求解法求多元线性回归参数，而是采用梯度下降法，它的计算代价相对更低。

3.梯度下降

好了，重点来了，本文真正要讲的东西终于登场了。

梯度下降，就是通过一步步迭代，让所有偏导函数都下降到最低。如果觉得不好理解，我们就还是以最简单的一元函数为例开始讲。

下图是我用Excel简单画的二次函数图像（看起来有点歪，原谅我懒……懒得调整了……），函数为 $y=x^2$ ，它的导数为y=2x。

在这里插入图片描述
如果我们初始化的点在x=1处，它的导函数值，也就是梯度值是2，为正，那就让它往左移一点，继续计算它的梯度值，若为正，就继续往左移。

如果我们初始化的点在x=-1处，该处的梯度值是-2，为负，那就让它往右移。

多元函数的逻辑也一样，先初始化一个点，也就是随便选择一个位置，计算它的梯度，然后往梯度相反的方向，每次移动一点点，直到达到停止条件。

这个停止条件，可以是足够大的迭代步数，也可以是一个比较小的阈值，当两次迭代之间的差值小于该阈值时，认为梯度已经下降到最低点附近了。

在这里插入图片描述

二元函数的梯度下降示例如上图（图片来自梯度下降），对于这种非凸函数，可能会出现这种情况：初始化的点不同，最后的结果也不同，也就是陷入局部最小值。

在这里插入图片描述
这种问题比较有效的解决方法，就是多取几个初始点。不过对于我们接下来讲的多元线性回归，以及后面要讲的逻辑回归，都不存在这个问题，因为他们的损失函数都是凸函数，有全局最小值。

用数学公式来描述梯度下降的步骤，就是：
$\Theta_{k+1}=\Theta_{k}-\alpha \cdot g$

解释下公式含义：

$\Theta_{k}$ 为k时刻的点坐标， $\Theta_{k+1}$ 为下一刻要移动到的点的坐标，例如 $\Theta_{0}$ 就代表初始化的点坐标， $\Theta_{1}$ 就代表第一步到移动到的位置；
g代表梯度，前面有个负号，就代表梯度下降，即朝着梯度相反的反向移动；
$\alpha$ 被称为步长，用它乘以梯度值来控制每次移动的距离，这个值的设定也是一门学问，设定的过小，迭代的次数就会过多，设定的过大，容易一步跨太远，直接跳过了最小值。
在这里插入图片描述

4.梯度下降法求解多元线性回归

回到前面的多元线性回归，我们用梯度下降算法求损失函数的最小值。

首先，求梯度，也就是前面我们已经给出的求偏导的公式：
$\frac{\partial Q}{\partial \beta}=2 X^{T} X \beta-2X^{T} Y=2 X^{T} (X \beta-Y)$

将梯度代入随机梯度下降公式：
$\Theta_{k+1}=\Theta_{k}-\alpha \cdot 2 X^{T} (X \beta-Y)$

这个式子中，X矩阵和Y向量都是已知的，步长是人为设定的一个值，只有参数 $\beta$ 是未知的，而每一步的 $\Theta$ 是由 $\beta$ 决定的，也就是每一步的点坐标。

算法过程：

初始化 $\beta$ 向量的值，即 $\Theta_{0}$ ，将其代入 $\frac{\partial Q}{\partial \beta}$ 得到当前位置的梯度；
用步长 $\alpha$ 乘以当前梯度，得到从当前位置下降的距离；
更新 $\Theta_1$ ，其更新表达式为 $\Theta_1=\Theta_0-\alpha \cdot 2 X^{T} (X \Theta_0-Y)$ ；
重复以上步骤，直到更新到某个 $\Theta_k$ ，达到停止条件，这个 $\Theta_k$ 就是我们求解的参数向量。