AndrewNg MachineLearning 学习笔记 02

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

1. 摘要

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

2. 基本概念及符号

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

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

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

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

再进一步，我们规定\(x_0=1\)，那么
\begin{align}
h_\theta(x) = \sum_{i=0}^n\theta_ix_i = \theta^TX
\end{align}
这里 n 表示输入变量的特征数，比如上述例子中 n 就为 2。

3. 梯度下降

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

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

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

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

\begin{align}
\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{align}
这里，
\begin{align}
\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{align}
因此，

最终，我们得到了\(\theta\)的更新公式

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

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

4. 最小二乘法

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

4.1 符号系统

1. 向量及矩阵求导

   设\(f : \mathbb{R}^{mn} \to \mathbb{R}\)，并且\(A \in \mathbb{R}^{mn}\)，定义

2. 关于矩阵迹(trace)的一些定理

   定义：设\(A \in \mathbb{R^{n*n}}\)，则称\(trA = \sum_{i = 0}^n A_{ii}\)为矩阵\(A\)的迹
   \begin{eqnarray}
   & 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 \mathbb{R}\quad(5)\\
   & \nabla_A trABA^TC = CAB + C^TAB^T\quad(6)
   \end{eqnarray}

4.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}

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

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

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

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

\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