CS229 Lesson 2 监督学习应用.梯度下降

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了处理线性回归的梯度下降方法以及正规方程。

Part I 线性回归

​ 为了让我们的房屋示例更有趣，让我们考虑一个稍微丰富的数据集，其中我们还知道每个房子的卧室数量：

​ 这里，$x$是$\mathbb R^2$中的二维向量。 例如，$x^{(i)}_1$是训练集中第$i$个房屋的生活区域，$x^{(i)}_2$是其卧室数。 作为初始选择，假设我们决定将$y$近似为$x$的线性函数：

$$h_{\theta}(x)=\theta_0 +\theta_1 x_1+\theta_2x_2$$

这里，$\theta_i$是参数（也称为权重），它们参数化从$\mathcal X$到$\mathcal Y$的线性映射的空间。当没有混淆的风险时，我们不写$h_{\theta}(x)$的下标，并将其简写为$h(x)$。 为了简化我们的符号，我们还引入了让$x_0 = 1$（这是截距项）的约定，所以

$$h(x)=\sum_{i=0}^n \theta_i x_i=\theta^T x$$

在上式中，我们将$θ$和$x$都视为向量，这里$n$是输入变量的数量（不计算$x_0$）。

​ 现在，给定训练集，我们如何选择或学习参数$θ$？ 一种合理的方法似乎是使$h(x)$接近$y$，至少对于我们的训练样本。 为了形式化，我们将定义一个函数，对于$θ$的每个值，测量$h(x^{(i)})$与相应的$y^{(i)}$的接近程度。 我们定义成本函数：

$$J(\theta) =\frac 1 2 \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})^2$$

​ 如果你以前看过线性回归，你可能会认为这是熟悉的最小二乘成本函数，它产生了普通的最小二乘回归模型。

1. LMS算法

为了使$J(\theta)$最小化，让我们考虑梯度下降算法，它以一些初始$\theta $开始，并重复执行更新：

$$\theta_j := \theta_j -\alpha \frac{\partial}{\partial \theta_j} J(\theta)$$

（对于$j = 0,…,n$的所有值同时执行该更新。）这里，$\alpha$被称为学习率。

​ 为了实现这个算法，我们必须弄清楚右边的偏导数项是什么，计算可得：

$$\begin{aligned} \frac{\partial}{\partial \theta_j} J(\theta) &=\frac{\partial}{\partial \theta_j} \frac 1 2 \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})^2\\ &= \frac 1 2 \sum_{i=1}^m\frac{\partial}{\partial \theta_j} (h_{\theta}(x^{(i)})-y^{(i)})^2\\ &=\frac 1 2 \sum_{i=1}^m2(h_{\theta}(x^{(i)})-y^{(i)}).\frac{\partial}{\partial \theta_j} (h_{\theta}(x^{(i)}_j )-y^{(i)})\\ &= \sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)}).\frac{\partial}{\partial \theta_j} \Big( \sum_{l=0}^n \theta_l x^{(i)}_l -y^{(i)} \Big) \\ &=\sum_{i=1}^m\big(h_{\theta}(x^{(i)})-y^{(i)}\big). x_j^{(i)} \end{aligned}$$

所以更新规则为

$$\theta_j := \theta_j +\alpha \sum_{i=1}^m\big(y^{(i)}-h_{\theta}(x^{(i)})\big). x_j^{(i)}$$

该规则称为LMS更新规则（LMS代表“最小均方误差”(least mean squares)，也称为Widrow-Hoff学习规则，具体的算法如下：

• 重复直到收敛{

  • 对每个$j$
  $$\theta_j := \theta_j +\alpha \sum_{i=1}^m\big(y^{(i)}-h_{\theta}(x^{(i)})\big). x_j^{(i)}$$

  }

此方法每个步查看整个训练集中的每个样本，因此被称为批量梯度下降，与之对应的是如下算法

• 循环{

  • 对于$i=1…m${
    • 对每个$j$
  $$\theta_j := \theta_j +\alpha \big(y^{(i)}-h_{\theta}(x^{(i)})\big). x_j^{(i)}$$

  ​ }

  }

在该算法中，我们反复遍历训练集，并且每次遇到训练样本时，我们仅根据该单个训练样本的误差梯度更新参数。该算法称为随机梯度下降（也称为增量梯度下降）。批量梯度下降必须扫描整个训练集，然后才采取一个更新步骤。如果$m$很大，那么这将带来很大计算量。通常，随机梯度下降比批量梯度下降更快地“接近”到最小值。（但请注意，它可能永远不会“收敛”到最小值，参数$θ$将保持在$J(θ)$的最小值附近振荡；但实际中，接近最小值的大多数值将与真实最小值相当接近。由于这些原因，特别是当训练集很大时，随机梯度下降通常优于批量梯度下降。

2. 正规方程

梯度下降给出了一种最小化$J$的方法。让我们讨论第二种方法，这次是明确地执行最小化而不是求助于迭代算法。 在这种方法中，我们将通过明确地将求导并将导数设置为零来最小化$J$。 首先对一些符号给出定义：给定训练集，将设计矩阵 $X$定义为$m\times n$的矩阵（实际上是$m\times (n+1)$，如果我们包括截距项），该矩阵的每行是一个训练样本：

$$X = \left[ \begin{matrix} — (x^{(1)})^T— \\ — (x^{(2)})^T— \\ \vdots\\ — (x^{(m)})^T— \end{matrix} \right]$$

另外，令$\vec y$为包含训练集中所有目标值的$m$维向量：

$$\vec y = \left[ \begin{matrix} y^{(1)} \\ y^{(2)} \\ \vdots\\ y^{(m)} \end{matrix} \right]$$

由于$h_{\theta}(x^{(i)})=(x^{(i)})^T \theta$，我们可以很容易地验证

$$\begin{aligned} X \theta -\vec y &= \left[ \begin{matrix} (x^{(1)})^T\theta \\ \vdots\\ (x^{(m)})^T\theta \end{matrix} \right] -\left[ \begin{matrix} y^{(1)} \\ \vdots\\ y^{(m)} \end{matrix} \right] \\ &= \left[ \begin{matrix} (x^{(1)})^T\theta-y^{(1)} \\ \vdots\\ (x^{(m)})^T\theta -y^{(m)} \end{matrix} \right] \end{aligned}$$

因此，利用对于任意向量$z$，$z^T z =\sum_{i}z_i^2$的事实，我们有：

$$\begin{aligned} \frac 1 2(X \theta -\vec y )^T(X \theta -\vec y ) &= \frac 1 2 \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})^2\\ &= J(\theta) \end{aligned}$$

关于$\theta$求梯度可得

$$\begin{aligned} \nabla_{\theta}J(\theta) &=\nabla_{\theta}\frac 1 2(X \theta -\vec y )^T(X \theta -\vec y )\\ &=\frac 1 2\nabla_{\theta} \big( \theta^T X^T X\theta - \theta^T X^T \vec y -\vec y^TX \theta + \vec y ^T\vec y \big)\\ &=\frac 1 2 \nabla_{\theta} \big(\theta^T X^T X\theta - 2\theta^T X^T \vec y)\\ &= \frac 1 2 \big( 2X^T X\theta - 2X^T \vec y \big) \\ &= X^T X\theta -X^T \vec y \end{aligned}$$

其中第三个等号利用了实数的转置等于本身的特点，所以有

$$\theta^T X^T \vec y =\vec y^TX \theta$$

第四个等号利用了

$$\begin{aligned} \nabla_{\theta} (\theta^T A \theta) &= (A+A^T)\theta \\ \nabla_{\theta}(\theta^T x) &= x \end{aligned}$$

令梯度为$0$可得正规方程：

$$X^T X\theta =X^T \vec y$$

因此，通过等式以解析形式给出使$J(\theta)$最小化的$\theta$的值

$$\theta =(X^T X)^{-1}X^T \vec y$$