Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 2: Supervised Learning Setup. LMS（线性回归与最小均方）

目录 · ← l1 · l3 →

Lecture 2: Supervised Learning Setup. LMS（线性回归与最小均方）

概述

本讲正式建立监督学习的数学框架：定义假设函数、代价函数与两种求解算法——梯度下降（批量/随机） 与 正规方程。核心思想：把“学习”转化为“最小化一个可微的代价函数”，这是整个课程最基础也最通用的一步。

核心概念与数学直觉

  • 监督学习问题设定：训练集 $\{(x^{(i)}, y^{(i)});\ i=1,\dots,m\}$，$x^{(i)} \in \mathbb{R}^{n}$（$n$ 个特征），$y^{(i)} \in \mathbb{R}$。目标：学习假设 $h$ 使 $h(x) \approx y$。

  • 假设函数 (Hypothesis) $h_\theta(x)$：输入特征的线性组合。
    • 直观解释：在二维平面中，$h_\theta(x) = \theta_0 + \theta_1 x$ 就是一条直线——我们要找一条“最贴近所有数据点”的直线。
    • 数学形式：$h_\theta(x) = \sum_{j=0}^{n} \theta_j x_j = \theta^T x$（约定 $x_0 = 1$，把截距吸收进参数向量）。
      • $\theta \in \mathbb{R}^{n+1}$：参数/权重，决定直线的斜率与截距，是我们要学习的对象。
      • $x_j$：第 $j$ 个特征；$x_0=1$ 是偏置项（bias term）。
      • $\theta^T x$：向量点积，把“每条特征对预测的贡献 $\theta_j x_j$”累加起来。
    • 直觉：每个参数 $\theta_j$ 可理解为“特征 $x_j$ 每增加一个单位，预测值变化多少”——这就是可解释性的来源（在特征独立、量纲相当时）。
  • 代价函数 (Cost Function) $J(\theta)$：衡量预测与真值的差距，即均方误差 (MSE)： $J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)})^2$
    • $m$：训练样本数。
    • $h_\theta(x^{(i)})$：第 $i$ 个样本的预测值。
    • $y^{(i)}$：第 $i$ 个样本的真实值。
    • $(h_\theta(x^{(i)}) - y^{(i)})^2$：平方误差——平方保证非负，且惩罚大误差远重于小误差（非线性放大）。
    • $\frac{1}{2m}$：$1/m$ 是取平均（与样本量无关）；$1/2$ 纯粹为了方便——求导时平方的 2 与 $1/2$ 抵消，使梯度表达式更简洁。
    • 直觉：代价函数像“卷尺”——测量拟合曲线与数据点的总偏差；目标是把总偏差压到最小。

  • 为什么 MSE 是合理的？（概率解释，L2 后半部分）：假设 $y^{(i)} = \theta^T x^{(i)} + \epsilon^{(i)}$，其中噪声 $\epsilon^{(i)} \sim \mathcal{N}(0, \sigma^2)$ 独立同分布。则由最大似然估计 (MLE)： $\ell(\theta) = \log \prod_{i=1}^{m} p(y^{(i)} \| x^{(i)}; \theta) = m \log \frac{1}{\sqrt{2\pi}\sigma} - \frac{1}{2\sigma^2} \sum_{i=1}^{m} (y^{(i)} - \theta^T x^{(i)})^2$ 最大化对数似然 $\ell(\theta)$ 等价于最小化 $J(\theta)$！这揭示了 MSE 的“出身”：它来自“高斯噪声 + 最大似然”的概率假设，而非随意选择。这是整个课程的方法论模板：先做概率假设，再推导损失函数。

  • 正规方程 (Normal Equation)：代价函数 $J$ 对 $\theta$ 求导置零，得到闭式解： $\nabla_\theta J(\theta) = \frac{1}{m} X^T (X\theta - y) = 0 \quad \Longrightarrow \quad \theta = (X^T X)^{-1} X^T y$
    • $X \in \mathbb{R}^{m \times (n+1)}$：设计矩阵，第 $i$ 行为样本 $x^{(i)}$（含 $x_0=1$）。
    • $y \in \mathbb{R}^{m}$：标签向量。
    • $X^T X$：若可逆（特征线性无关），一步求出全局最优；复杂度 $O(n^3)$（求逆）。

算法伪代码与逻辑解说：批量梯度下降 (Batch Gradient Descent)

伪代码

输入:
    - 训练数据 (X, y)，X 为 m×(n+1) 设计矩阵
    - 学习率 alpha (η)
    - 收敛阈值 epsilon，最大迭代次数 max_iters

输出:
    - 最优参数 theta

1. 初始化 theta = 0（或小随机值），iter = 0
2. 循环直到收敛:
    2.1 计算梯度: grad = (1/m) * X^T * (X*theta - y)   // 全量样本
    2.2 更新: theta = theta - alpha * grad
    2.3 iter = iter + 1
    2.4 若 ||grad|| < epsilon 或 iter >= max_iters: 终止
3. 返回 theta

【算法逻辑解说】

  1. 梯度是什么：$\nabla_\theta J$ 是一个向量，指向 $J$ 在当前 $\theta$ 处上升最快的方向。减去它（乘学习率 $\alpha$）就是沿下降最快的方向迈一步——这就是“下山”的比喻：闭着眼感受最陡的坡，每次沿最陡方向挪一步。
  2. 更新规则的标量形式（理解用）：对每个参数 $\theta_j$： $\theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)}$ 注意 $(h_\theta(x^{(i)}) - y^{(i)})$ 是预测误差，$x_j^{(i)}$ 是误差的“权重”——误差大且特征值大的样本对参数更新的贡献大。
  3. 向量化（Vectorization）：X*theta - y 一次算完所有样本的误差向量；X^T * 误差 完成所有参数梯度的同时计算。NumPy 的 BLAS 底层并行远超 Python 显式 for 循环——这是处理大数据集的必要条件。
  4. 学习率 $\alpha$：步长。太大→震荡甚至发散（$J$ 越来越大）；太小→收敛极慢。课程建议按数量级网格搜索（0.001, 0.01, 0.1, …）。
  5. 收敛条件：梯度范数接近 0（到达谷底）或达到迭代上限。实践中常监控 $J(\theta)$ 随迭代的变化曲线。

算法伪代码与逻辑解说：随机梯度下降 (Stochastic Gradient Descent, SGD)

伪代码

输入: (X, y), alpha, max_iters
输出: theta

1. 初始化 theta = 0
2. 循环 iter = 1..max_iters:
    2.1 随机打乱样本顺序（或随机采样）
    2.2 对每个样本 i（顺序遍历）:
        theta = theta - alpha * (h_theta(x^(i)) - y^(i)) * x^(i)
        // 注意: 每个样本立即更新一次参数，且学习率常随迭代衰减
3. 返回 theta

【算法逻辑解说】

  1. 与批量的区别：批量 GD 每步用全部 $m$ 个样本的梯度；SGD 每步只用一个样本的梯度。SGD 的更新方向是真实梯度的有噪声估计。
  2. 为什么 SGD 在大数据上更优：批量 GD 每步代价 $O(mn)$；SGD 每步代价 $O(n)$，且立即开始改进。当 $m$ 达百万级，SGD 往往能先于批量 GD 到达可接受解。
  3. 噪声是特征而非缺陷：随机性帮助跳出浅的局部极小（对凸问题无影响，对非凸有益）；代价是收敛路径曲折。常用技巧：学习率按 $1/\text{iter}$ 衰减，保证最终收敛。
  4. Mini-batch SGD（介于两者之间）：每步用 $b$ 个样本（如 32/64）——现代深度学习的事实标准，兼顾稳定与效率。

关键要点

  1. 学习 = 最小化代价函数；MSE 代价源自“高斯噪声 + MLE”的概率假设。
  2. 梯度下降（迭代）与正规方程（闭式）是求解线性回归的两种途径，各有适用场景（$n$ 大小、是否需要在线学习）。
  3. 特征缩放（归一化到相近范围）能显著加速梯度下降收敛——等高线“圆”时梯度下降走直线。
  4. 向量化是工程性能的关键；SGD 适合海量数据。

常见误区与注意事项

  • 忘记特征缩放：特征量纲差异大（面积 0–2000 vs 卧室数 1–5）时，代价等高线是细长椭圆，梯度下降呈锯齿状缓慢收敛。用均值归一化 $x \leftarrow \frac{x - \mu}{\sigma}$。
  • 学习率选择不当：过小收敛慢、过大发散。若 $J$ 在迭代中不降反升，几乎可以断定是 $\alpha$ 过大（或代码有 bug）。
  • 把 MSE 用于分类问题：分类的 $y$ 是离散类别，MSE 会惩罚“正确但数值不同”的预测；分类应用交叉熵（L3）。
  • 正规方程遇不可逆 $X^T X$：特征线性相关或 $m < n$ 时不可逆；可用伪逆或正则化（L5 的岭回归即解决此问题）。
  • 误用梯度下降于非凸问题：线性回归的 $J$ 是凸函数（唯一全局最优）；但对神经网络等非凸问题，梯度下降只能保证局部最优。

思考题

  1. 问题：设 $m=1$（单样本 $(x, y)$），推导 SGD 在 $h_\theta(x)=\theta_0+\theta_1 x$ 下的两个更新方程，并解释几何意义。
    • 答案：$\theta_0 := \theta_0 - \alpha (h_\theta(x) - y)$，$\theta_1 := \theta_1 - \alpha (h_\theta(x) - y) x$。几何意义：误差 $(h_\theta(x)-y)$ 乘以该参数对应的输入分量，即“沿误差下降方向按输入大小成比例地调整权重”。
  2. 问题：正规方程 $\theta = (X^TX)^{-1}X^Ty$ 何时比梯度下降更差？
    • 答案：当特征数 $n$ 很大（如 $>10^4$）时，$X^TX$ 求逆复杂度 $O(n^3)$ 不可接受；且若需在线（数据不断到达）更新模型，迭代法天然适配，正规方程需要整体重算。
  3. 问题：为什么概率解释中假设 $\epsilon \sim \mathcal{N}(0, \sigma^2)$ 会导出平方损失而非绝对损失？
    • 答案：因为高斯分布的密度 $p(y\vert x;\theta) \propto \exp(-\frac{(y-\theta^T x)^2}{2\sigma^2})$ 取负对数后出现平方项。若假设拉普拉斯噪声则得到绝对损失 $\vert y - \theta^T x\vert $——损失函数的选择对应噪声分布的假设，这是“损失函数从哪来”的深层答案。