第 4 讲
线性回归
Linear Regression
$$h_\theta(x)=\theta^\top x,\qquad
J(\theta)=\frac12\sum_{i=1}^{n}\big(h_\theta(x_i)-y_i\big)^2$$
| 主线 | 核心问题 |
|---|
| 梯度下降 | 从预测误差推导参数更新 |
| Normal equations | 直接求解同一个最小二乘问题 |
| 概率解释 | 从高斯噪声与最大似然得到平方损失 |
| 局部加权回归 · 选讲 | 在查询点附近重新拟合线性模型 |
Andrew Ng / Tengyu Ma · CS229 Lecture Notes，Chapter 1，pp. 8–19
训练数据与线性模型
输入 $x$ 与连续标签 $y$
| 面积 / ft² | 卧室数 | 价格 / 千美元 |
|---|
| 2104 | 3 | 400 |
| 1600 | 3 | 330 |
| 2400 | 3 | 369 |
| 1416 | 2 | 232 |
| 3000 | 4 | 540 |
| … | … | … |
输入：面积、卧室数等特征。
输出：房屋价格。
$$h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2$$
对 $d$ 个特征，引入恒为 $1$ 的坐标 $x_0$：
$$x=\begin{bmatrix}1&x_1&\cdots&x_d\end{bmatrix}^{\!\top},
\quad\theta=\begin{bmatrix}\theta_0&\theta_1&\cdots&\theta_d\end{bmatrix}^{\!\top}$$
$$h_\theta(x)=\sum_{j=0}^{d}\theta_jx_j=\theta^\top x$$
$S=\{(x_i,y_i)\}_{i=1}^{n}$；$n$ 为样本数，$d+1$ 为含截距的参数数。
选定线性函数族后，学习的任务是从数据确定参数 $\theta$。
CS229，pp. 8–9。后续推导适用于一般输入；“线性”指对未知参数线性。
最小二乘目标与残差
残差：$r_i=y_i-h_\theta(x_i)$。
$$J(\theta)=\frac12\sum_{i=1}^{n}r_i^2
=\frac12\sum_{i=1}^{n}(\theta^\top x_i-y_i)^2$$
$$\theta^*\in\arg\min_\theta J(\theta)$$
平方消除正负抵消，对大残差给予更高权重；系数 $1/2$ 方便求导。
均方误差（Mean Squared Error, MSE）：
$$\mathrm{MSE}=\frac1n\sum_i r_i^2=\frac{2J}{n}$$
最小二乘（least squares）指定优化目标；目标的求解方法可以不同。
图中仅取面积；$u=(\text{面积}-2000)/1000$，$v=\text{价格}/100$，拟合 $v=\theta_0+\theta_1u$。CS229，p. 9。
从平方损失推导梯度
先看一个样本：$\ell_i(\theta)=\frac12(h_\theta(x_i)-y_i)^2$。第 $j$ 个参数通过加权和影响预测。
$$\begin{aligned}
\frac{\partial\ell_i}{\partial\theta_j}
&=\frac12\cdot2(h_\theta(x_i)-y_i)\,
\frac{\partial(h_\theta(x_i)-y_i)}{\partial\theta_j}\\[.5em]
&=(h_\theta(x_i)-y_i)\,
\frac{\partial}{\partial\theta_j}\left(\sum_{k=0}^{d}\theta_kx_{ik}-y_i\right)\\[.5em]
&=(h_\theta(x_i)-y_i)x_{ij}.
\end{aligned}$$
$$\frac{\partial J}{\partial\theta_j}
=\sum_{i=1}^{n}(h_\theta(x_i)-y_i)x_{ij},\qquad
\nabla_\theta J=\sum_{i=1}^{n}(h_\theta(x_i)-y_i)x_i$$
截距：$x_{i0}=1$，所以 $\displaystyle\frac{\partial J}{\partial\theta_0}=\sum_i(h_\theta(x_i)-y_i)$。
每项梯度 = 预测误差 × 对应特征；一次更新使用同一组旧参数。
CS229，§1.1，pp. 9–10。$x_{ij}$ 是第 $i$ 个样本的第 $j$ 个坐标。
梯度下降：在参数空间中寻找最小值
给定训练数据后，$x_i,y_i$ 均为常数，$J$ 就是参数 $\theta$ 的函数。
$\boxed{\theta^{(t+1)}=\theta^{(t)}-\alpha\nabla J(\theta^{(t)})}$：从初值出发，沿负梯度反复更新以降低 $J$。
固定房屋数据（缩放后）：$(u_i,v_i)=(0.104,4),\ (-0.4,3.3),\ (0.4,3.69),\ (-0.584,2.32),\ (1,5.4)$。
一个参数：固定截距 $\theta_0=3.5$，只调整斜率
两个参数：同时调整截距 $\theta_0$ 与斜率 $\theta_1$
梯度下降（gradient descent）。$\alpha=0.1$；数字为迭代步数，品红线为更新路径，× 为最小值位置；曲面可旋转。
负梯度方向与一次完整的参数更新
为什么沿负梯度走
一维：导数为正，向左减小参数；导数为负，向右增大参数。
$$J(\theta+\Delta)\approx J(\theta)+\nabla J(\theta)^\top\Delta$$
$$\Delta=-\alpha\nabla J(\theta)\quad\Longrightarrow$$
$$J(\theta+\Delta)\approx J(\theta)-\alpha\|\nabla J(\theta)\|_2^2$$
非零梯度、足够小的步长下，$J$ 会下降。步长控制每次移动多远。
计算梯度 → 更新参数 → 重新计算梯度，直到达到停止条件。
房屋数据：从 $\theta^{(0)}=(0,0)^\top$ 出发
$$\nabla J(0)=\begin{bmatrix}-\sum_i v_i\\-\sum_i u_iv_i\end{bmatrix}
=\begin{bmatrix}-18.71\\-4.61712\end{bmatrix}$$
$$\theta^{(1)}=\begin{bmatrix}0\\0\end{bmatrix}
-0.1\begin{bmatrix}-18.71\\-4.61712\end{bmatrix}
=\begin{bmatrix}1.871\\0.461712\end{bmatrix}$$
| 迭代 $t$ | $\theta_0$ | $\theta_1$ | $J$ |
|---|
| 0 | 0 | 0 | 37.5243 |
| 1 | 1.8710 | 0.4617 | 9.7651 |
| 2 | 2.7825 | 0.7489 | 2.9141 |
| $\cdots$ | $\cdots$ | $\cdots$ | $\cdots$ |
停止条件可取 $\|\nabla J\|$ 足够小、损失变化足够小，或达到迭代上限。线性回归的凸目标使适当步长下的迭代趋向全局最小值。
批量梯度下降与随机梯度下降
批量梯度下降 batch gradient descent
每一步累计全部 $n$ 个样本的梯度。
$$\theta_j^{(t+1)}=\theta_j^{(t)}
-\alpha\sum_{i=1}^{n}\big(h_{\theta^{(t)}}(x_i)-y_i\big)x_{ij}$$
- 初始化参数。
- 用全部样本计算梯度。
- 同时更新所有坐标，重复迭代。
随机梯度下降 Stochastic Gradient Descent, SGD
每一步用一个样本近似更新方向。
$$\theta_j^{(t+1)}=\theta_j^{(t)}
-\eta_t\big(h_{\theta^{(t)}}(x_i)-y_i\big)x_{ij}$$
- 抽取样本或打乱后遍历。
- 计算当前样本的梯度。
- 立即更新，再处理其他样本。
小批量（mini-batch）：
$\displaystyle\theta^{(t+1)}=\theta^{(t)}
-\frac{\eta_t}{|\mathcal B_t|}\sum_{i\in\mathcal B_t}
(h_{\theta^{(t)}}(x_i)-y_i)x_i$
批量更新方向确定；单样本与小批量更新成本较低，但轨迹有波动。固定步长的 SGD 可能在最优解附近持续波动。
CS229，§1.1，pp. 10–13。小批量按平均梯度写法；总和与平均的比例可吸收到学习率中。
学习率与损失等高线
$\displaystyle J(\theta_0,\theta_1)=\frac12\sum_i(\theta_0+\theta_1u_i-v_i)^2$
学习率过小：进展缓慢；过大：可能振荡或发散。
沿用五条房屋记录及前页缩放；坐标轴是参数，右图为 $\log_{10}J$。步长过大时轨迹会越出显示范围。
从样本求和到矩阵形式
把所有样本的预测放进一个列向量：每行对应一个样本，首列恒为 $1$。
$$X=\underbrace{\begin{bmatrix}
1&x_{11}&\cdots&x_{1d}\\
1&x_{21}&\cdots&x_{2d}\\
\vdots&\vdots&&\vdots\\
1&x_{n1}&\cdots&x_{nd}
\end{bmatrix}}_{n\times(d+1)},\quad
\theta=\underbrace{\begin{bmatrix}\theta_0\\\theta_1\\\vdots\\\theta_d\end{bmatrix}}_{(d+1)\times1},
\quad\mathbf y=\underbrace{\begin{bmatrix}y_1\\y_2\\\vdots\\y_n\end{bmatrix}}_{n\times1}$$
$$\hat{\mathbf y}=X\theta,\qquad
X\theta-\mathbf y=
\begin{bmatrix}h_\theta(x_1)-y_1\\\vdots\\h_\theta(x_n)-y_n\end{bmatrix}$$
$$J(\theta)=\frac12\sum_{i=1}^{n}(h_\theta(x_i)-y_i)^2
=\frac12(X\theta-\mathbf y)^\top(X\theta-\mathbf y)
=\frac12\|X\theta-\mathbf y\|_2^2$$
设计矩阵（design matrix）。$\mathbf y$ 表示全部标签，$y_i$ 表示单个标签。CS229，§1.2，pp. 13–14。
展开目标函数并对参数求导
$$\begin{aligned}
J(\theta)
&=\tfrac12(X\theta-\mathbf y)^\top(X\theta-\mathbf y)\\[.55em]
&=\tfrac12\big(\theta^\top X^\top X\theta
-\theta^\top X^\top\mathbf y-\mathbf y^\top X\theta
+\mathbf y^\top\mathbf y\big)\\[.55em]
&=\tfrac12\theta^\top X^\top X\theta
-\theta^\top X^\top\mathbf y
+\tfrac12\mathbf y^\top\mathbf y.
\end{aligned}$$
$$\begin{aligned}
\nabla_\theta J
&=\tfrac12\cdot2X^\top X\theta-X^\top\mathbf y+0\\[.4em]
&=X^\top(X\theta-\mathbf y).
\end{aligned}$$
矩阵求导规则
$$a^\top b=b^\top a$$
$$\nabla_\theta(a^\top\theta)=a$$
$$\nabla_\theta(\theta^\top A\theta)=(A+A^\top)\theta$$
$A=X^\top X$ 对称，所以最后一式为 $2A\theta$；与参数无关的项导数为零。
矩阵求导与逐样本求导得到相同梯度：$\nabla J=\sum_i(h_\theta(x_i)-y_i)x_i$。
CS229，§1.2.1–1.2.2，pp. 13–15。
从零梯度到最优参数：normal equations
将梯度设为零，得到关于 $\theta$ 的线性方程组，称为 normal equations。
求解这个方程组，即得到最小二乘的最优参数。
$$\nabla J(\theta^*)=0
\ \Longrightarrow\ X^\top(X\theta^*-\mathbf y)=0
\ \Longrightarrow\ \underbrace{X^\top X\theta^*=X^\top\mathbf y}_{\text{normal equations}}$$
$$\boxed{\theta^*=(X^\top X)^{-1}X^\top\mathbf y}
\qquad\text{当 }\operatorname{rank}(X)=d+1$$
为什么驻点就是最优解
$$\nabla^2J=X^\top X,\qquad
z^\top X^\top Xz=\|Xz\|_2^2\ge0$$
$J$ 为凸二次函数；$X$ 满列秩时，Hessian 正定，最优参数唯一。
什么时候不能直接取逆
样本数 $n<d+1$，或特征列线性相关时，$X^\top X$ 不可逆。
最小二乘问题仍有解；可用伪逆 $\theta^*=X^+\mathbf y$ 取得最小范数解。
闭式解（closed-form solution）；伪逆（pseudoinverse）。数值实现可通过矩阵分解求解线性方程，避免显式求逆。
完整算例：由数据计算最小二乘解
给定三个样本 $(1,2),(2,3),(3,5)$，拟合 $h_\theta(x)=\theta_0+\theta_1x$。
$$X=\begin{bmatrix}1&1\\1&2\\1&3\end{bmatrix},\quad
\mathbf y=\begin{bmatrix}2\\3\\5\end{bmatrix},
\quad X^\top X=\begin{bmatrix}3&6\\6&14\end{bmatrix},
\quad X^\top\mathbf y=\begin{bmatrix}10\\23\end{bmatrix}$$
$$\theta^*=\frac1{3\cdot14-6\cdot6}
\begin{bmatrix}14&-6\\-6&3\end{bmatrix}
\begin{bmatrix}10\\23\end{bmatrix}
=\begin{bmatrix}1/3\\3/2\end{bmatrix},
\qquad h_{\theta^*}(x)=\frac13+\frac32x$$
$$\hat{\mathbf y}=\begin{bmatrix}11/6\\10/3\\29/6\end{bmatrix},
\quad r=\mathbf y-\hat{\mathbf y}
=\begin{bmatrix}1/6\\-1/3\\1/6\end{bmatrix}$$
$$X^\top r=\begin{bmatrix}0\\0\end{bmatrix},
\qquad J(\theta^*)=\frac12\left(\frac1{36}+\frac19+\frac1{36}\right)=\frac1{12}$$
最优解仍可有非零残差；最小二乘不要求回归线穿过每个样本。
最小二乘解的几何含义
已求出的最优参数满足 $X^\top(\mathbf y-X\theta^*)=0$：残差与 $X$ 的每一列正交。
$$\hat{\mathbf y}=X\theta^*\in\operatorname{col}(X)$$
$$X^\top(\mathbf y-\hat{\mathbf y})=0
\quad\Longleftrightarrow\quad r\perp\operatorname{col}(X)$$
$$P_X=X(X^\top X)^{-1}X^\top,\qquad
\hat{\mathbf y}=P_X\mathbf y$$
$$P_X^\top=P_X,\qquad P_X^2=P_X$$
最小二乘寻找列空间中离 $\mathbf y$ 最近的向量；加入截距时还满足 $\sum_i r_i=0$。
向量位于 $n$ 维样本空间，每个分量对应一条样本；$\operatorname{col}(X)$ 为 $X$ 的列空间。此处投影矩阵的写法要求 $X$ 满列秩。
闭式解与梯度下降：两种求解方式
$$\theta^*=(X^\top X)^{-1}X^\top\mathbf y$$
通过线性代数直接求解。
$$\theta^{(t+1)}=\theta^{(t)}-\alpha X^\top(X\theta^{(t)}-\mathbf y)$$
用多次较便宜的更新逐步接近最优解。
两者最小化同一个 $J(\theta)$。选哪一种，取决于问题规模、矩阵结构和精度要求。
| 比较 | 直接法 | 梯度方法 |
|---|
| 主要计算 | 形成 $X^\top X$ 并解线性方程 | 反复计算预测误差与梯度 |
| 稠密情形的成本 | $O(np^2+p^3)$，$p=d+1$ | 批量每步 $O(np)$；$T$ 步为 $O(Tnp)$ |
| 存储与数据访问 | 保存 $X^\top X$ 需 $O(p^2)$ 额外空间 | 无需形成 $p\times p$ 矩阵；可按小批量访问 |
| 常见选择 | 特征数适中：通常简单有效 | 高维、稀疏或大规模迭代计算更灵活 |
闭式可写出，不等于计算成本低。 特征数 $p=10^4$ 时，$X^\top X$ 已有 $10^8$ 个元素。
成本比较针对常规稠密实现；$n$ 大而 $p$ 小时，直接法也可能很合适。迭代次数取决于条件数、步长和精度要求。
高斯噪声与条件分布
把观测写成线性预测与误差之和，并为误差加入概率假设：
$$y_i=\theta^\top x_i+\varepsilon_i,\qquad
\varepsilon_i\overset{\mathrm{i.i.d.}}{\sim}\mathcal N(0,\sigma^2),
\quad\varepsilon_i\text{ 与输入独立}$$
$$p(\varepsilon_i)=\frac1{\sqrt{2\pi\sigma^2}}
\exp\!\left(-\frac{\varepsilon_i^2}{2\sigma^2}\right)$$
$$y_i\mid x_i;\theta\sim\mathcal N(\theta^\top x_i,\sigma^2)$$
均值由输入和参数决定；$\sigma^2$ 描述围绕均值的波动，所有样本共享同一方差。
$$p(y_i\mid x_i;\theta)=\frac1{\sqrt{2\pi\sigma^2}}
\exp\!\left[-\frac{(y_i-\theta^\top x_i)^2}{2\sigma^2}\right]$$
独立同分布：independent and identically distributed，i.i.d.。CS229，§1.3，pp. 15–16。
似然函数与最大似然估计
固定已经观测到的 $X,\mathbf y$，把联合密度看成参数 $\theta$ 的函数：
$$\begin{aligned}
L(\theta;X,\mathbf y)
&=p(\mathbf y\mid X;\theta)\\[.4em]
&=\prod_{i=1}^{n}p(y_i\mid x_i;\theta)\\[.4em]
&=\prod_{i=1}^{n}\frac1{\sqrt{2\pi\sigma^2}}
\exp\!\left[-\frac{(y_i-\theta^\top x_i)^2}{2\sigma^2}\right].
\end{aligned}$$
$$\theta_{\mathrm{ML}}\in\arg\max_\theta L(\theta;X,\mathbf y)$$
分布：固定参数，描述可能观测到哪些 $y$。
似然：固定观测数据，比较哪些参数更支持这些数据。
最大似然估计（Maximum Likelihood Estimation, MLE）：选择使已观测数据的联合密度最大的参数。
乘积来自条件独立假设。CS229，§1.3，p. 16。
对数似然与最小二乘的等价性
对数严格递增，因此最大化 $L(\theta)$ 与最大化 $\log L(\theta)$ 得到相同参数。
$$\begin{aligned}
\log L(\theta)
&=\sum_{i=1}^{n}\log\left\{\frac1{\sqrt{2\pi\sigma^2}}
\exp\!\left[-\frac{(y_i-\theta^\top x_i)^2}{2\sigma^2}\right]\right\}\\[.3em]
&=\sum_{i=1}^{n}\left[-\frac12\log(2\pi\sigma^2)
-\frac{(y_i-\theta^\top x_i)^2}{2\sigma^2}\right]\\[.3em]
&=-\frac n2\log(2\pi\sigma^2)
-\frac1{2\sigma^2}\sum_{i=1}^{n}(y_i-\theta^\top x_i)^2\\[.3em]
&=\underbrace{-\frac n2\log(2\pi\sigma^2)}_{\text{对 }\theta\text{ 为常数}}
-\frac1{\sigma^2}J(\theta).
\end{aligned}$$
$$\boxed{\arg\max_\theta\log L(\theta)=\arg\min_\theta J(\theta)}$$
独立同方差高斯误差下，最小二乘解就是最大似然估计；最小二乘本身的定义不要求高斯假设。
CS229，§1.3，p. 17。绝对误差也可由其他噪声假设解释；损失函数体现了建模选择。
全局拟合与局部拟合 选讲
全局模型：一次拟合
$$\theta^*=\arg\min_\theta\sum_i(y_i-\theta^\top x_i)^2$$
$$\hat y(q)=\theta^{*\top}q$$
所有查询点共享一组参数。可加入 $x^2,x^3,\ldots$ 特征，使原始输入上的拟合成为曲线。
局部模型：随查询点重新拟合
$$\theta(q)=\arg\min_\theta\sum_i\omega_i(q)(y_i-\theta^\top x_i)^2$$
$$\hat y(q)=\theta(q)^\top q$$
查询点附近的样本权重更大。每个局部模型线性，整体预测函数可以非线性。
$$\omega_i(q)=\exp\!\left(-\frac{\|x_i-q\|_2^2}{2\tau^2}\right),
\qquad \tau>0$$
带宽（bandwidth）$\tau$ 控制邻域大小；距离在尺度可比的输入特征上计算。
局部加权线性回归（Locally Weighted Linear Regression, LWR）。CS229，§1.4，pp. 17–19；$q_0=1$。
局部加权最小二乘的求解 选讲
对一个固定查询点 $q$，先确定权重，再对 $\theta$ 优化：
$$W_q=\operatorname{diag}\big(\omega_1(q),\ldots,\omega_n(q)\big)$$
$$J_q(\theta)=\frac12\sum_i\omega_i(q)(x_i^\top\theta-y_i)^2
=\frac12(X\theta-\mathbf y)^\top W_q(X\theta-\mathbf y)$$
$$\begin{aligned}
\nabla_\theta J_q
&=X^\top W_q(X\theta-\mathbf y)=0\\[.4em]
X^\top W_qX\,\theta(q)&=X^\top W_q\mathbf y\\[.4em]
\theta(q)&=(X^\top W_qX)^{-1}X^\top W_q\mathbf y.
\end{aligned}$$
| 带宽较小 | 带宽较大 |
|---|
| 主要依赖附近样本，局部变化更灵活 | 更多远处样本参与，拟合更平滑 |
| 有效样本少，估计可能不稳定 | $\tau\to\infty$ 时 $\omega_i\to1$，趋向全局最小二乘 |
闭式写法要求 $X^\top W_qX$ 可逆；过小带宽也可能造成数值病态。加权 normal equations由前面的推导直接推广。
带宽与局部预测 选讲
$\displaystyle\hat y(q)=\theta_0(q)+\theta_1(q)q,\qquad
\omega_i(q)=\exp\!\left[-\frac{(x_i-q)^2}{2\tau^2}\right]$
合成数据：$y=0.4x+\sin(1.8x)+\varepsilon$，$\varepsilon\sim\mathcal N(0,0.12^2)$；每次改变 $q$ 或 $\tau$ 都重新求解。
线性回归：模型、求解与概率解释
| 层次 | 核心表达 | 含义 |
|---|
| 模型 | $h_\theta(x)=\theta^\top x$ | 对参数线性的函数族 |
| 目标 | $J=\frac12\|X\theta-\mathbf y\|_2^2$ | 最小化训练平方误差 |
| 迭代求解 | $\theta\leftarrow\theta-\alpha\nabla J$ | 重复计算梯度并更新 |
| 直接求解 | $X^\top X\theta=X^\top\mathbf y$ | 解线性方程组；满列秩时参数唯一 |
| 概率解释 | $y\mid x;\theta\sim\mathcal N(\theta^\top x,\sigma^2)$ | 高斯假设下，MLE 等价于最小二乘 |
| 局部推广 | $X^\top W_qX\theta(q)=X^\top W_q\mathbf y$ | 查询点决定样本权重 |
模型、损失函数和求解算法分别回答：用什么预测、怎样评价、如何找到参数。
分类任务改变输出及其概率模型；线性得分、链式求导与最大似然仍可继续使用。
参考阅读：CS229 · Chapter 1：Linear regression（pp. 8–19）
第 4 讲结束
← → 翻页 · o 总览 · s 演讲者视图 ·
f 全屏 · 网址后加 ?print-pdf 可导出 PDF
机器学习 · 研究生 第 4 讲 线性回归
https://kaizhao.net/teaching/shu-ml-grad