ML1-1 线性回归与其解法

1. 监督学习

• 定义：给定一个训练集，我们的目标是学习一个函数 $h : \mathcal{X} \mapsto \mathcal Y$，使得 $h(x)$ 能够很好地预测 $y$ 的对应值。
• 特点：训练数据是成对的（同时给出了输入和输出）
• 两类典型问题
  • 回归（regression）问题：输出为连续值
  • 分类（classification）问题：输出为离散值

常见术语

如下：

• 输入：一般用 $x$ 表示，常见形式是 $D$ 维向量
• 输出：又称标签，在回归问题中一般是实数，在分类问题中一般是离散值
• 训练集：$n$ 个训练样本的集合，一个 $(x^{(i)}, y^{(i)})$ 对被称为一个训练样本
• 假设函数：即函数 $h(x)$ ，是我们通过某种算法从数据中学到的模型

2. 线性回归模型

下面是CS229给出的一个情景：

情景

假设我们有一个数据集，给出了俄勒冈州波特兰市47栋房屋的居住面积和价格，我们还知道每栋房屋的卧室数量。这里，$x$ 是 $\mathbb{R}^2$ 中的二维向量。例如，$x_1^{(i)}$是训练集中第 $i$ 栋房屋的居住面积，$x_2^{(i)}$ 是其卧室数量（暂时选定了这两个特征）。

要执行监督学习，我们必须考虑函数 $h(x)$ 在计算机中的表示。作为初始选择，我们决定将 $y$ 近似为 $x$ 的线性函数：

$$h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2$$
其中，

• $\theta_i$ 是参数（权重），用于参数化从 $\mathcal{X}$ 到 $\mathcal Y$ 的线性函数空间
• 为简化符号，我们还引入约定令 $x_0 = 1$（截距项）
• 线性回归的目标就是找到一组最优的 $\theta$

所以上式可以归结为：

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

其中右侧我们将 $\theta$ 和 $x$ 都视为向量，$d$ 是输入变量的数量（不计入 $x_0$）。

线性假设模型

在线性回归中，假设函数 $h(x)$ 是输入特征 $x$ 的线性组合
$$h_θ(x) = θ_0 + θ_1x_1 + θ_2x_2 + ... + θ_dx_d$$
引入 $x_0 = 1$，从而将假设函数写成向量点积的形式
$$h_\theta(x) = \theta^T x$$
其中，
$$θ = [θ_0, θ_1, \dots, θ_d]ᵀ，x = [1, x_1, \dots, x_d]ᵀ$$

我们如何学习参数 $\theta$ 呢，一个合理的方法是使 $h(x)$ 接近 $y$。我们定义代价函数如下：

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

这是我们熟悉的最小二乘代价函数（Least Squares），公式前方的 $\frac{1}{2}$ 是为了求导后的形式简洁。我们的目标是找到能使 $J(θ)$ 最小化的参数 $\hat{\theta}$，即：

$$\hat{\theta} = arg min_θ J(θ)$$

3. 线性回归的解法

对于线性回归，我们存在两种解法：

• LMS算法：使用梯度下降，迭代求解
• 正规方程法：直接求出精确解析解

本节我们先解释LMS算法。

3.1 LMS算法

我们希望找到 $\hat{\theta}$ 以最小化 $J(θ)$ 。为此，我们将采取一种搜索算法，从 $\theta$ 的某个"初始猜测"开始，反复改变 $\theta$ 使 $J(\theta)$ 更小，直到希望收敛到使 $J(\theta)$ 最小的 $\theta$ 值。

具体来说，我们采用的是梯度下降算法，步骤如下：

1. 确定一个初始的 $\theta$
2. 反复执行更新下式直到收敛（此更新对所有 $j = 0, \ldots,d$ 同时执行）：
   $$\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j} J(\theta)$$
   $\alpha$ 称为学习率。这是一个非常自然的算法，它反复沿着 $J$ 最陡下降的方向迈出一步。

为了实现上述算法，我们需要计算偏导数项 $\frac{\partial}{\partial \theta_j} J(\theta)$ 。这里首先考虑只有一个训练 $(x, y)$ 样本的情况（这样可以忽略 $J$ 定义中的求和）：

$$\begin{aligned}\frac{\partial}{\partial \theta_j} J(\theta) &= \frac{\partial}{\partial \theta_j} \frac{1}{2} (h_\theta(x) - y)^2 \\&= 2 \cdot \frac{1}{2} (h_\theta(x) - y) \cdot \frac{\partial}{\partial \theta_j} (h_\theta(x) - y) \\&= (h_\theta(x) - y) \cdot \frac{\partial}{\partial \theta_j} \sum_{i=0}^{d} \theta_i x_i - y \\&= (h_\theta(x) - y) x_j\end{aligned}$$

于是，对于单个训练样本，我们有：

LMS 更新规则（单样本）

$\theta_j := \theta_j + \alpha \left( y^{(i)} - h_\theta(x^{(i)}) \right) x_j^{(i)}$

这个规则被称为 LMS 更新规则（LMS 代表"最小均方"），也称为 Widrow-Hoff 学习规则。

该规则的几个性质：

• 更新的幅度与误差项 $(y^{(i)} - h_\theta(x^{(i)}))$ 成比例（误差大，调整幅度就大）
• 更新的幅度也与特征值有关（特征值大，调整权重也大）

我们推导的 LMS 规则仅适用于单个训练样本的情况。有几种方法可以将其修改为适用于包含多个样本的训练集。

3.1.1 批量梯度下降

重复直到收敛

$$θ_j := θ_j + α Σ_{i=1}^{n} (y^{(i)} - h_θ(x^{(i)})) x_j^{(i)} \text{ (for every j)}$$

通过将各坐标的更新分组为向量 $\theta$ 的更新，上述更新可以写为更简洁的形式：

BGD公式

$\theta := \theta + \alpha \sum_{i=1}^{n} \left( y^{(i)} - h_\theta(x^{(i)}) \right) x^{(i)}$

可以验证，上述更新规则中的求和项正是该情形下的前述偏导数项。

这种方法在每一步都查看整个训练集中的每个样本，称为批量梯度下降（BGD）。

3.1.2 随机梯度下降

从 1 到 $n$ 循环执行

$$θ_j := θ_j + α (y^{(i)} - h_θ(x^{(i)})) x_j^{(i)}\text{ (for every j)}$$

通过将各坐标的更新分组为向量 $\theta$ 的更新，上述更新可以写为更简洁的形式：

SGD公式

$\theta := \theta + \alpha \left( y^{(i)} - h_\theta(x^{(i)}) \right) x^{(i)}$

在该算法中，我们反复遍历训练集，每遇到一个训练样本，就仅根据该单个样本的误差梯度更新参数。这个算法称为随机梯度下降（SGD）（也称为增量梯度下降（IGD））。

提示

当训练集很大时，随机梯度下降通常比批量梯度下降更受青睐：

• 批量梯度下降在迈出一步之前必须扫描整个训练集——当 $n$ 很大时这是一个代价高昂的操作；而随机梯度下降可以立即开始取得进展，并且每看一个样本就继续取得进展。
• 通常，随机梯度下降比批量梯度下降更快的使 $\theta$ 接近最小值。（但注意它可能永远不会"收敛"到最小值，参数 $\theta$ 会在 $J(\theta)$ 的最小值附近持续震荡；但在实践中，最小值附近的大部分值都是真实最小值的相当好的近似。）
  • 通过随着算法运行缓慢地将学习率 $\alpha$ 减小到零，也可以确保参数收敛到全局最小值。

3.1.3 线性回归与凸优化

线性回归是一种典型的凸优化问题。

其特征：

• 目标函数 $J(θ)$ 是凸函数
• 定义域 $ℝ^n$ 是凸集

这意味着任何局部最优解都是全局最优解。

线性回归提出的优化问题只有一个全局最优值，没有其他局部最优值。因此梯度下降总是收敛到全局最小值（假设学习率不是太大）：

图中显示的椭圆是二次函数的等高线。同时还显示了梯度下降的轨迹，初始化为 (48,30)。图中标记的 x（由直线连接）表示梯度下降所经历的 $\theta$ 的连续值。

3.2 正规方程

之前我们使用梯度下降这种迭代的方法，以求解关于 $J$ 最优化的问题。
而对于线性回归而言，我们是可以直接求出精确的解析解的。
我们将通过对 $\theta_j$ 求导并令其为零来显式地最小化 $J$，即正规方程（The normal equations）。

3.2.1 预备：矩阵导数

对于一个函数 $f : \mathbb{R}^{n \times d} \mapsto \mathbb{R}$ ，将 $n \times d$ 矩阵映射到实数，我们定义 $f$ 对 $A$ 的导数为：

$$\nabla_A f(A) = \begin{bmatrix}\frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1d}} \\\vdots & \ddots & \vdots \\\frac{\partial f}{\partial A_{n1}} & \cdots & \frac{\partial f}{\partial A_{nd}}\end{bmatrix}$$

$e.g.$ 假设有 $2 \times 2$ 矩阵 $A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}$，函数 $f : \mathbb{R}^{2 \times 2} \mapsto \mathbb{R}$ 由下式给出：

$$f(A) = \frac{3}{2} A_{11} + 5 A_{12}^2 + A_{21} A_{22}$$
这里 $A_{ij}$ 表示矩阵 $A$ 的 $(i,j)$ 元素，那么我们有：

$$\nabla_A f(A) = \begin{bmatrix}\frac{3}{2} & 10 A_{12} \\A_{22} & A_{21}\end{bmatrix}$$

3.2.2 解最小二乘法

给定一个训练集，定义设计矩阵 $X$ 为 $n \times d$ 矩阵（ $n$ 样本 $d$ 特征，实际上为 $n \times (d+1)$，如果包含截距项的话），其行中包含训练样本的输入值：

$$X = \begin{bmatrix}— (x^{(1)})^T — \\— (x^{(2)})^T — \\\vdots \\— (x^{(n)})^T —\end{bmatrix}$$
另外，令 $\vec{y}$ 为包含训练集中所有目标值的 $n$ 维向量：

$$\vec{y} = \begin{bmatrix}y^{(1)} \\y^{(2)} \\\vdots \\y^{(n)}\end{bmatrix}$$

1. 由于 $h_\theta(x^{(i)}) = (x^{(i)})^T \theta$，我们可以得到

$$X\theta - \vec{y} = \begin{bmatrix}(x^{(1)})^T \theta \\\vdots \\(x^{(n)})^T \theta\end{bmatrix} - \begin{bmatrix}y^{(1)} \\\vdots \\y^{(n)}\end{bmatrix} = \begin{bmatrix}h_\theta(x^{(1)}) - y^{(1)} \\\vdots \\h_\theta(x^{(n)}) - y^{(n)}\end{bmatrix}$$

2. 利用对于某向量 $\vec{z}$ ，有 $z^T z = \sum_i z_i^2$ ，我们可以得到

$$\frac{1}{2} (X\theta - \vec{y})^T (X\theta - \vec{y}) = \frac{1}{2} \sum_{i=1}^{n} (h_\theta(x^{(i)}) - y^{(i)})^2 = J(\theta)$$

3. 求 $J(\theta)$ 的导数

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

第一步：展开乘积
第二步：$θ^TX^Ty$ 和 $y^TXθ$ 都是标量，且互为转置，予以合并。同时忽略常数项。
第三步：逐项求梯度，用到两个公式：

• 对于对称矩阵 $A$，有 $\nabla_x x^T A x = 2Ax$
• 对于与 $x$ 无关的向量 $b$，有 $\nabla_x b^T x = b$

4. 令其导数为 $0$ ，得到正规方程

$$X^T X \theta = X^T \vec{y}$$
因此最小化 $J(\theta)$ 的 $\theta$ 由以下封闭值给出

正规方程的解

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

上步假设 $X^T X$ 是可逆矩阵。这可以在计算逆矩阵之前进行检查。如果线性无关的样本数量少于特征数量，或者特征不是线性无关的，则 $X^T X$ 将不可逆。即使在这种情况下，也可以使用额外的技术来解决。

4. 附录

公式 $\nabla_x b^T x = b$

类比：
标量导数：d/dx (b·x) = b  
向量梯度：∇ₓ (bᵀx) = b

• 左侧即点积形式，展开后做矩阵导数即可

公式 $\nabla_x x^T A x = 2Ax$ （二次型）

类比：
标量导数：d/dx (a·x²) = 2a·x  
向量梯度：∇ₓ (xᵀAx) = 2Ax（A 对称时）