梯度下降(Gradient Descent) [cs229学习笔记]

本文对应的是吴恩达老师的CS229机器学习的第二课。这节课先介绍了线性回归；然后讲述了两个简单的优化方法，批梯度下降和随机梯度下降；最后推导了矩阵形式的线性回归。

为防止符号混淆，本文中 $i$i 表示样本序号，$j$j 表示特征序号，$n$n 表示样本数量，$m$m 表示特征数量

---

损失函数(loss function)

简单起见，这节课研究的函数为线性回归。所谓回归，指的就是对某一连续变量的预测；线性指的是所采用的函数为线性函数。对于某一输入 $\bold{x}$x，预测函数为：

$\begin{aligned} h(\bold{x}) = h_\theta(\bold{x})&=\theta_0+\theta_1x_1+\theta_2x_2+\cdots\\ &=\sum_{j=0}^m\theta_jx_j\\ &=\theta^T\bold{x} \end{aligned}$h(x)=hθ​(x)​=θ0​+θ1​x1​+θ2​x2​+⋯=j=0∑m​θj​xj​=θTx​

那么，对于我们的分类任务，我们的目标是预测值与实际值尽可能相同，即预测值与实际值之间的误差尽可能小。

我们将预测值与实际值之间的误差称为损失函数 $J(\theta)$J(θ)，则一个简单的平方项误差损失函数可以写成：

$J(\theta) = \frac{1}{2}\sum_{i=1}^n \left(h_\theta(\bold{x}^{(i)})-y^{(i)}\right)^2$J(θ)=21​i=1∑n​(hθ​(x(i))−y(i))2

我们的目标就是最小化损失函数，即

$\min_\theta J(\theta)$θmin​J(θ)

---

批梯度下降(Batch Gradient Descent)

如图所示为误差图，我们希望损失函数最终能达到最小值，即沿着梯度下降的方向（箭头方向）走。同时，注意到起点位置的不同可能会导致最终走向不同的最低点，即得到不同的局部最优解(local minima)。

那么如何保证沿着梯度方向走呢？我们可以通过求偏导的方法，因为导数方向是切线方向，始终指向梯度变化最快的方向，即最陡的方向。因此，对于每一个特征 $j$j，我们都可以用求偏导的方式来更新它。于是，梯度下降法就呼之欲出了：

1. 首先，我们初始化 $\theta$θ，我们可以随机初始化，或者直接初始化为 $0$0，即 $\theta \coloneqq \overrightarrow{0}$θ:=0，其中 $\coloneqq$:= 符号表示计算机中的赋值操作。
2. 对每一个特征 $j\in m$j∈m，$\theta_j \coloneqq \theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)$θj​:=θj​−α∂θj​∂​J(θ)，其中 $\alpha$α 为步长（图中每一个箭头的长度），即学习率。
   我们先取出 $n$n 个样本中的一个计算其偏导数。根据前文对损失函数的定义，我们可以得到：
   $\begin{aligned} \frac{\partial}{\partial\theta_j}J(\theta)&=\frac{\partial}{\partial\theta_j} \left(h_\theta(\bold{\bold{x}})-y\right)^2\\ &=2 \cdot \frac{1}{2} \left(h_\theta(\bold{x})-y\right) \frac{\partial}{\partial\theta_j} \left(h_\theta(\bold{x})-y\right)\\ &= \left(h_\theta(\bold{x})-y\right) \frac{\partial}{\partial\theta_j} \left(\theta_0+\theta_1x_1+\theta_2x_2+\cdots-y\right)\\ &=\left(h_\theta(\bold{x})-y\right) \cdot x_j \end{aligned}$∂θj​∂​J(θ)​=∂θj​∂​(hθ​(x)−y)2=2⋅21​(hθ​(x)−y)∂θj​∂​(hθ​(x)−y)=(hθ​(x)−y)∂θj​∂​(θ0​+θ1​x1​+θ2​x2​+⋯−y)=(hθ​(x)−y)⋅xj​​
3. 利用所得偏导数更新每一个特征 $j\in m$j∈m 对应的权重：$\theta_j \coloneqq \theta_j-\alpha\left(h_\theta(\bold{x})-y\right) \cdot x_j$θj​:=θj​−α(hθ​(x)−y)⋅xj​

上述是每一个样本对应的梯度更新，对于整个损失函数，我们只需将其求和再更新即可。于是，梯度下降法就可以写为：

对每一个特征 $j\in m$j∈m，重复以下操作直至收敛：
$\theta_j \coloneqq \theta_j-\alpha\sum_{i=1}^n\left(h_\theta(\bold{x}^{(i)})-y^{(i)}\right) \cdot x_j^{(i)}$θj​:=θj​−αi=1∑n​(hθ​(x(i))−y(i))⋅xj(i)​

那么什么时候算收敛呢？一般来说，若两次（或者多次求平均）更新之间损失函数变化很小，则判定为收敛。

---

随机梯度下降(Stochastic Gradient Descent)

批梯度下降的训练速度非常慢，因为每次都需要用所有的数据进行计算，当数据集非常大的时候，这种计算的效率会非常低。那么有没有方法使计算速度更快呢？随机梯度下降就是这个方法。不同于批梯度下降，随机梯度下降每次只取一个样本进行梯度更新。随机梯度下降法可以写为：

对每一个特征 $j\in m$j∈m，重复以下操作直至收敛：
$\theta_j \coloneqq \theta_j-\alpha\left(h_\theta(\bold{x}^{(i)})-y^{(i)}\right) \cdot x_j^{(i)}$θj​:=θj​−α(hθ​(x(i))−y(i))⋅xj(i)​

可以看到随机梯度下降相比于批梯度下降，就是少了一个求和，即随机梯度下降每次只用一个样本进行更新，而不是用全部样本。

但是每次随机取一个样本点进行计算，为什么就能收敛呢？一个较为直观的解释是：在批梯度下降方法中，下降方向是梯度最陡的方向；而随机梯度下降方法中，虽然每一次下降方向可能与梯度最陡的方向不同，但是多次重复的下降方向的数学期望是与梯度最陡的方向相同的，因此随机梯度下降大致上也是可以收敛的。

随机梯度下降的优点是随机梯度下降比批梯度下降快得多，而缺点也存在，就是随机梯度下降难以收敛到最低点，往往会在最低点附近徘徊，如上图所示。

---

矩阵形式

现在，我们将推导线性回归的矩阵形式，并推导矩阵形式下的梯度更新公式。首先，我们先介绍几个定义。我们定义函数 $J$J 的梯度为：

$\nabla_\theta J = \begin{bmatrix} \frac{\partial J}{\partial \theta_0} \\ \vdots \\ \frac{\partial J}{\partial \theta_m} \end{bmatrix}\in \Reals^{m+1}$∇θ​J=⎣⎢⎡​∂θ0​∂J​⋮∂θm​∂J​​⎦⎥⎤​∈Rm+1

那么前文的批梯度下降法可以简写为：

$\theta \coloneqq \theta -\alpha \nabla_\theta J$θ:=θ−α∇θ​J

更一般地，当我们把输入数据 $x$x 写成矩阵形式：

$X=\begin{bmatrix} -&\bold{x}^{(1)T}&-\\ &\vdots& \\ -&\bold{x}^{(n)T}&- \end{bmatrix}$X=⎣⎢⎡​−−​x(1)T⋮x(n)T​−−​⎦⎥⎤​

并把所有 $y$y 也写成向量的形式 $\bold{y}$y，则有：

$X\theta - \bold{y}=\begin{bmatrix} \bold{x}^{(1)T}\theta\\ \vdots\\ \bold{x}^{(n)T}\theta \end{bmatrix}-\begin{bmatrix} y^{(1)}\\ \vdots\\ y^{(n)} \end{bmatrix}=\begin{bmatrix} h_\theta(\bold{x}^{(1)})-y^{(1)}\\ \vdots\\ h_\theta(\bold{x}^{(n)})-y^{(n)} \end{bmatrix}$Xθ−y=⎣⎢⎡​x(1)Tθ⋮x(n)Tθ​⎦⎥⎤​−⎣⎢⎡​y(1)⋮y(n)​⎦⎥⎤​=⎣⎢⎡​hθ​(x(1))−y(1)⋮hθ​(x(n))−y(n)​⎦⎥⎤​

则对应的损失函数可以写为

$\begin{aligned} J(\theta) &= \frac{1}{2}\sum_{i=1}^n \left(h_\theta(\bold{x}^{(i)})-y^{(i)}\right)^2\\ &=\frac{1}{2}(X\theta-\bold{y})^T(X\theta-\bold{y}) \end{aligned}$J(θ)​=21​i=1∑n​(hθ​(x(i))−y(i))2=21​(Xθ−y)T(Xθ−y)​

接下来，我们来推导线性回归的矩阵形式。不同于课上的推导方式（转换为迹trace然后计算），我们直接用矩阵求导来推导。下面给出l两个个本文将用到的矩阵求导公式（相关证明请自行搜索）。

$\begin{aligned} \frac{\partial A^T\bold{x}}{\partial \bold{x}}&=A\\ \frac{\partial \bold{x}^TA\bold{x}}{\partial \bold{x}}&=\left(A+A^T\right)\bold{x} \end{aligned}$∂x∂ATx​∂x∂xTAx​​=A=(A+AT)x​

对于损失函数 $J(\theta)$J(θ)，我们希望直接通过计算得到其梯度为 $0$0 的对应参数，即我们希望$\nabla_\theta J=0$∇θ​J=0。于是，将损失函数的矩阵形式代入计算，可得其梯度为

$\begin{aligned} 0= \nabla_\theta J &= \nabla_\theta \frac{1}{2}(X\theta-\bold{y})^T(X\theta-\bold{y})\\ &= \frac{1}{2} \nabla_\theta \left(\theta^TX^TX\theta-\bold{y}^TX\theta-\theta^TX^T \bold{y}+\bold{y}^T\bold{y}\right) \end{aligned}$0=∇θ​J​=∇θ​21​(Xθ−y)T(Xθ−y)=21​∇θ​(θTXTXθ−yTXθ−θTXTy+yTy)​

这里注意到 $\theta^TX^T \bold{y}$θTXTy 是一个标量，而标量的转置任然是其本身，即 $\theta^TX^T \bold{y}=\left(\theta^TX^T \bold{y}\right)^T=\bold{y}^TX\theta$θTXTy=(θTXTy)T=yTXθ。以及 $\bold{y}$y 与 $\theta$θ 无关，即 $\nabla_\theta\left(\bold{y}^T\bold{y}\right)=0$∇θ​(yTy)=0。再结合前面提到的几个矩阵求导公式，我们可以得到：

$\begin{aligned} 0 &= \frac{1}{2} \nabla_\theta \left(\theta^TX^TX\theta-\bold{y}^TX\theta-\theta^TX^T \bold{y}+\bold{y}^T\bold{y}\right)\\ &= \frac{1}{2} \nabla_\theta \left(\theta^TX^TX\theta\right)-\frac{1}{2} \nabla_\theta\left(2\bold{y}^TX\theta\right)\\ &= \frac{1}{2}\left(X^TX+\left(X^TX\right)^T\right)\theta-\frac{1}{2}\left(2(\bold{y}^TX)^T\right)\\ &=X^TX\theta-X^T\bold{y} \end{aligned}$0​=21​∇θ​(θTXTXθ−yTXθ−θTXTy+yTy)=21​∇θ​(θTXTXθ)−21​∇θ​(2yTXθ)=21​(XTX+(XTX)T)θ−21​(2(yTX)T)=XTXθ−XTy​

于是，我们可以写出矩阵形式下的梯度更新公式

$\theta=\left(X^TX\right)^{-1}X^T\bold{y}$θ=(XTX)−1XTy