第二课 线性回归和梯度下降

1. 摘要

本课内容从一个无人驾驶的案例引入回归的概念,借用上次Portland Oregon房价的例子,推导出梯度下降和最小二乘两个算法。

2. 基本概念及符号

在无人驾驶的案例中,汽车试图预测驾驶的方向,是一种连续的量。
因此可以总结下述概念(自己总结的并不严格)

回归问题:给定一组输入,算法输出一组连续变化的量,称为回归问题。

然后来看Portland Oregon房价案例,我们有以下数据

Living area (feet2) #bedrooms Price (1000$s)
2104 3 400
1600 3 330
2400 3 369
1416 2 232
3000 4 540

m: 训练样本数量(上述例子中就是5)
x: 输入变量(上述例子中就是(2104, 3)等)
y: 输出变量或叫目标(上述例子中就是400等)
(x, y): 训练样本(上述例子中就是((2103, 3), 400))
i: 训练样本的编号(上述例子中((2103, 3), 400)就是1号样本, 即i=1,记为(x^1, y^1), 这里i并不表示乘方只是一个序号,下文同样。

h: 表示一个假设,一般记为h(x),或者h_\theta(x)

\theta: 假设中的参数,如上述例子会有如下表示h_\theta(x) = \theta_0 + \theta_1x_1 + \theta_2x_2,其中x_1表示房屋面积,x_2表示卧室数量

再进一步,我们规定x_0=1,那么

h_\theta(x) = \sum_{i=0}^n\theta_ix_i = \theta^TX

这里n表示输入变量的特征数,比如上述例子中n就为2。

3. 梯度下降

为了使我们的模型在训练数据上尽量准确,我们定义如下误差项损失函数:

\frac12\sum_{i=0}^m(h_\theta(x^i) - y^i)^2

显然,这里是模型对训练集所有数据误差平方的一个求和,前面的\frac12是为了后面计算方便。如果一个模型在训练集上有更好的表现,那么上述算式的值一定更小。于是我们定义

J(\theta) = \frac12\sum_{i=0}^m(h_\theta(x^{(i)}) - y^{(i)})^2

我们要找到\min\limits_{\theta}J(\theta)时的\theta值,也就确定了模型参数。

有这样一种思路,我们首先给的一个\theta的初始值(一般为零向量),然后我们通过不断改变\theta的值,似的J(\theta)不断减小,直到一个我们满意的最小值。该思路可以表现为如下图像。

就像一个人站在山顶,他想尽快下山,那么他首先环视一周,找到最陡的下坡路,然后向这个方向迈出一步,然后再环视一周,找到最陡的下坡路,再向这个方向走一步。。。重复以上过程,可以想象这个人一定会下到山脚。当然有一个问题是,根据这个人在山顶初始位置的不同,他下到山脚的位置也不尽相同,但我们遇到的问题大多是只有一个全局最小值,所以不必担心这样的情况。于是,我们依照如下公式更新\theta

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

公式中“:=”表示赋值,把右边的值赋给左边。此外,\alpha是一个参数,通常是手动设定的,代表了“步长”。如果\alpha设定过小,那上述公式收敛的速率会很慢,相反如果设置过大,那么在接近极小值时有可能直接“迈过”去了。
视频中Andrew教授以单训练样本对上面的公式进行了计算,下面我直接以更一般的m个训练样本进行推导。

\begin{aligned} \frac{\partial}{\partial \theta_i}J(\theta) & = \frac{\partial}{\partial \theta_i}\frac12\sum_{j=0}^m(h_\theta(x^{(j)}) - y^{(j)})^2 \\ & = \frac12\sum_{j=0}^m\frac{\partial} {\partial \theta_i}(h_\theta(x^{(j)}) - y^{(j)})^2 \\ & = \frac12 * 2 * \sum_{j=0}^m(h_\theta(x^{(j)}) - y^{(j)})\frac{\partial}{\partial \theta_i} (h_\theta(x^{(j)}) - y^{(j)}) \end{aligned}

这里,

\begin{aligned} \frac{\partial}{\partial \theta_i}(h_\theta(x^{(j)}) - y^{(j)}) & = \frac{\partial}{\partial \theta_i}(\sum_{i=0}^n\theta_ix_i^{(j)} - y^{(j)}) \\ & = \frac{\partial}{\partial \theta_i}(\theta_0x_0^{(j)} + \theta_1x_i^{(j)} + ... + \theta_nx_n^{(j)} - y^{(j)}) \\ & = x_i^{(j)} \end{aligned}

因此,

\frac{\partial}{\partial \theta_i}J(\theta) = \sum_{j=0}^m(h_\theta(x^{(j)}) - y^{(j)})x_i^{(j)}

最终,我们得到了\theta的更新公式

\theta_i := \theta_i - \alpha\sum_{j=0}^m(h_\theta(x^{(j)}) - y^{(j)})x_i^{(j)}

通常,上述算法被称为批梯度下降算法(Batch Gradient Descent) ,因为每迭代一个\theta_i我们都会使用所有的训练集,因而当训练集非常庞大的时候,该算法收敛的速率通常让人崩溃。这种时候,我们通常选择另一种称为随机梯度下降算法(Stochastic Gradient Descent) 来进行计算。该算法更新参数的公式如下:
对于每个训练样本(x^{(j)}, y^{(j)})

\theta_i := \theta_i - \alpha(h_\theta(x^{(j)}) - y^{(j)})x_i^{(j)}\quad(for\,all\,i)

上述算法的思想在于,每次迭代只使用一个训练样本,然后用这个样本更新所有参数,如果还有更多样本则重复上述过程。
这种算法的效率通常比批梯度下降要快,但每次迭代的方向有可能是负梯度方向,最终有可能在极小值附近徘徊,但结果会很接近极小值。

4. 最小二乘法

前面介绍的两种算法属于迭代算法,需要大量运算,而最小二乘法则只需要把数据代入一个公式即可得到结果。为此,我们需要定义一些符号,并且后面的运算都是基于向量或矩阵的。

4.1 符号系统

  1. 向量及矩阵求导

    f: \reals^{m*n} \to \reals,并且A \in \reals^{m*n},定义

\nabla_A f(A) = \begin{pmatrix} \frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}} \\ \vdots & \ddots & \vdots \\ \frac{\partial f}{\partial A_{m1}} & \cdots & \frac{\partial f}{\partial A_{mn}} \end{pmatrix}
  1. 关于矩阵迹(trace)的一些定理

    定义:设A \in \mathbb{R^{n*n}},则称trA = \sum_{i = 0}^n A_{ii}为矩阵A的迹

\begin{gathered} trAB = trBA \quad(1) \\ trABC = trCAB = trBCA \quad(2) \\ f(A) = trAB, \nabla f(A) = B^T \quad(3) \\ trA = trA^T \quad(4) \\ tra = a, a \in \reals \quad(5) \\ \nabla_A trABA^TC = CAB + C^TAB^T \quad(6) \end{gathered}

4.2 最小二乘公式推导

首先回忆一下在梯度下降算法中,我们定义的模型偏差损失函数

J(\theta) = \frac12\sum_{i=0}^m(h_\theta(x^{(i)}) - y^{(i)})^2

现在我们要把上述公式的变量都替换为矩阵或向量。

我们所有的训练样本输入、输出及参数可以表示为如下矩阵

X = \begin{pmatrix} (x^{(1)})^T \\ \vdots \\ (x^{(m)})^T \\ \end{pmatrix} \quad Y = \begin{pmatrix} y^{(1)} \\ \vdots \\ y^{(m)} \\ \end{pmatrix} \quad \theta = \begin{pmatrix} \theta_1 \\ \vdots \\ \theta_n \\ \end{pmatrix}

那么,模型预测值与实际值的差可以表示为

\begin{aligned} X\theta - Y & = \begin{pmatrix} (x^{(1)})^T \\ \vdots \\ (x^{(m)})^T \end{pmatrix} \begin{pmatrix} \theta_1 \\ \vdots \\ \theta_n \end{pmatrix} - \begin{pmatrix} y^{(1)} \\ \vdots \\ y^{(m)} \end{pmatrix} \\ & = \begin{pmatrix} (x^{(1)})^T\theta \\ \vdots \\ (x^{(m)})^T\theta \end{pmatrix} - \begin{pmatrix} y^{(1)} \\ \vdots \\ y^{(m)} \end{pmatrix} \\ & = \begin{pmatrix} h_\theta(x^{(1)}) \\ \vdots \\ h_\theta(x^{(m)}) \end{pmatrix} - \begin{pmatrix} y^{(1)} \\ \vdots \\ y^{(m)} \end{pmatrix} \\ & = \begin{pmatrix} h_\theta(x^{(1)}) - y^{(1)} \\ \vdots \\ h_\theta(x^{(m)}) - y^{(m)} \end{pmatrix} \end{aligned}

由向量内积的定义,我们可以得到

\frac12(X\theta - Y)^T(X\theta - Y) = \frac12\sum_{i=0}^m(h_\theta(x^{(i)}) - y^{(i)})^2 = J(\theta)

如同梯度下降,我们希望求得J(\theta)取得极小值时\theta的值,此时一个办法就是对J(\theta)求导
因此,我们设

\nabla_\theta J(\theta) = \vec 0

其中,

\begin{aligned} \nabla_\theta J(\theta) & = \nabla_\theta \frac12(X\theta - Y)^T(X\theta - Y) \\ & = \frac12\nabla_\theta (\theta^TX^TX\theta - \theta^TX^TY - Y^TX\theta + Y^TY) \end{aligned}

由于上式括号中表达式是向量内积的得到的,因此其实际上只是一个实数,由定理(5),我们可以得到

\begin{aligned} & \frac12\nabla_\theta (\theta^TX^TX\theta - \theta^TX^Ty - y^TX\theta + y^Ty) \\ & = \frac12\nabla_\theta tr(\theta^TX^TX\theta - \theta^TX^Ty - y^TX\theta + y^Ty) \\ & = \frac12(\nabla_\theta tr\theta\theta^TX^TX - \nabla_\theta trY^TX\theta - \nabla_\theta trY^TX\theta)\quad\text{(use theory (2)(4)(5))} \\ & = \frac12(\nabla_\theta tr\theta\theta^TX^TX - 2\nabla_\theta trY^TX\theta) \\ & = \frac12\nabla_\theta tr\theta\theta^TX^TX - X^TY\quad\text{(use theory (3))} \end{aligned}

接下来,我们再看上式第一项,求导部分可以作如下变换

\nabla_\theta tr\theta\theta^TX^TX = \nabla_\theta tr\theta I\theta^TX^TX

然后我们记

A = \theta \quad B = I \quad C = X^TX

那么由定理(6),可以得出

\frac12\nabla_\theta tr\theta\theta^TX^TX = \frac12(X^TX\theta I + X^TX\theta I) = X^TX\theta

最终,我们求得

\nabla_\theta J(\theta) = X^TX\theta - X^TY = \vec 0
\begin{aligned} X^TX\theta & = X^TY \\ \theta & = (X^TX)^{-1}X^TY \end{aligned}