线性模型与核方法
从线性回归出发，逐步构建完整的线性模型体系：基函数→回归→分类→SVM→核方法→结构化输出。理解"线性"真正限制的是参数组织方式而非表达能力，掌握最大间隔原理和核技巧的数学动机。
从课程脉络看：L01 定义了监督学习问题，L02 给出它的第一个具体答案族——判别式线性模型。L03 会从生成式角度重写同一个分类问题。
前置知识回顾
- 线性代数：矩阵乘法、逆矩阵、特征分解。作用：最小二乘解 $w_{ML}=(\Phi^T\Phi)^{-1}\Phi^T t$ 需要矩阵运算。去哪里补：线性代数课程。
- 概率论：高斯分布、条件概率、贝叶斯定理。作用：逻辑回归和生成式分类都需要概率解释。去哪里补：L01 MLE/MAP。
- 凸优化：拉格朗日乘子法、KKT 条件。作用：SVM 的原始问题和对偶问题都以约束优化为核心。去哪里补：凸优化基础。
很多人第一次学线性模型时觉得它太简单。但这恰好错过了重点：所谓线性，首先是对参数的线性，而不是对输入空间的僵化限制。模型 $y(x,\mathbf{w}) = w_0 + w_1 x + w_2 x^2 + \cdots + w_M x^M$ 虽然能拟合多项式曲线，但参数 $w_i$ 仍然以线性形式出现。关键在于选择合适的基函数 $\phi(x)$ 来变换输入空间。
线性模型的统一形式
引入基函数 $\phi(x)$ 后，线性模型统一写成：
其中 $\phi_0(x) = 1$（偏置项）。
| 基函数类型 | 形式 | 特点 |
|---|---|---|
| 恒等基函数 | $\phi(x) = x$ | 不做变换，最简单 |
| 多项式基函数 | $\phi_j(x) = x^j$ | 全局影响，高次不稳定 |
| 高斯（径向）基函数 | $\phi_j(x) = \exp\!\left(-\frac{(x-\mu_j)^2}{2s^2}\right)$ | 局部影响，适合插值 |
| 反曲（Sigmoid）基函数 | $\phi_j(x) = \sigma\!\left(\frac{x-\mu_j}{s}\right)$ | 与神经网络激活函数同族 |
线性回归的参数估计不是拍脑袋设计，而是可以从概率假设推导出来：
推导链：高斯噪声 → MLE → 平方和误差
- 假设：目标值 $t = y(x,\mathbf{w}) + \epsilon$，其中 $\epsilon \sim \mathcal{N}(0, \beta^{-1})$。
- 似然函数：$p(\mathbf{t}|X,\mathbf{w},\beta) = \prod_{i=1}^N \mathcal{N}(t_i | \mathbf{w}^T\phi(x_i), \beta^{-1})$。
- 对数似然：$\ln p = \frac{N}{2}\ln\beta - \frac{N}{2}\ln(2\pi) - \beta \cdot E_D(\mathbf{w})$。
- 平方和误差函数：$E_D(\mathbf{w}) = \frac{1}{2}\sum_{i=1}^N \{t_i - \mathbf{w}^T\phi(x_i)\}^2$。
- 最大化对数似然等价于最小化 $E_D(\mathbf{w})$。
- 解析解：$\mathbf{w}_{ML} = (\Phi^T\Phi)^{-1}\Phi^T\mathbf{t}$，其中 $\Phi$ 是设计矩阵（每行为 $\phi(x_i)^T$）。
这条推导链的结论是：最小二乘法不是拍脑袋设计，而是高斯噪声假设 + MLE 的自然结果。
线性回归输出连续值，分类需要离散标签。逻辑回归用 sigmoid 函数 $\sigma(a) = \frac{1}{1+\exp(-a)}$ 把线性输出压缩到 $[0,1]$ 区间，解释为后验概率：
对二分类问题，负对数似然（交叉熵误差函数）为：
这个误差函数关于 $\mathbf{w}$ 不再有解析解，需要用迭代优化（梯度下降或 Newton-Raphson/IRLS）。
SVM 切换到另一种视角：不再追求概率解释，而是追求分类边界的最大间隔（Maximum Margin）。
SVM 原始优化问题
通过拉格朗日乘子法转化为对偶问题后，目标函数中只出现内积 $\phi(\mathbf{x}_n)^T\phi(\mathbf{x}_m)$：
SVM 对偶问题
其中核函数 $k(\mathbf{x}_n,\mathbf{x}_m) = \phi(\mathbf{x}_n)^T\phi(\mathbf{x}_m)$。
大多数 $a_n = 0$，只有少数 $a_n > 0$ 的样本成为支撑向量——它们恰好落在间隔边界上，决定了分类器的最终形态。
软间隔 SVM 引入松弛变量 $\xi_n \geq 0$ 和惩罚因子 $C$：
标准 SVM 输出单个类别标签。结构化 SVM 把输出扩展为结构 $\mathbf{y} \in \mathcal{Y}$（序列、树、图），判别函数变为：
这是 L03 条件随机场（CRF）的重要前驱。
| 模型 | 建模对象 | 损失函数 | 关键特点 |
|---|---|---|---|
| 线性回归 | 连续输出 | 平方和误差（来自 MLE） | 有解析解 |
| 逻辑回归 | 后验概率 $p(C_1|\phi)$ | 交叉熵 | 输出可解释为概率 |
| SVM | 分类边界 | Hinge loss | 最大间隔，稀疏（支撑向量） |
| 核方法 | 隐式高维特征 | 同上 | 非线性边界但保留线性优化结构 |
| 结构化 SVM | 结构化输出 | 结构化 Hinge loss | 输出为序列/树/图 |
例题：核函数的性质验证
题目：已知 $k_1(\mathbf{x},\mathbf{y})$ 和 $k_2(\mathbf{x},\mathbf{y})$ 是有效核函数（即对应的 Gram 矩阵半正定）。证明 $k(\mathbf{x},\mathbf{y}) = k_1(\mathbf{x},\mathbf{y}) + k_2(\mathbf{x},\mathbf{y})$ 和 $k(\mathbf{x},\mathbf{y}) = c \cdot k_1(\mathbf{x},\mathbf{y})$（$c > 0$）也是有效核函数。
- 加法：Gram 矩阵 $K = K_1 + K_2$。两个半正定矩阵之和仍半正定（对任意向量 $\mathbf{v}$，$\mathbf{v}^T K\mathbf{v} = \mathbf{v}^T K_1\mathbf{v} + \mathbf{v}^T K_2\mathbf{v} \geq 0$）。
- 正数乘：$K = c \cdot K_1$。$\mathbf{v}^T K\mathbf{v} = c \cdot \mathbf{v}^T K_1\mathbf{v} \geq 0$（因为 $c > 0$）。
答案：核函数在加法和正数乘法下封闭。这意味着可以从简单核函数组合出复杂核函数。
例题：为什么大多数 $a_n = 0$
题目：在对偶问题中，为什么只有少数样本会成为支撑向量（$a_n > 0$）？
- 约束条件：$t_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b) \geq 1$。大多数样本满足严格大于 1，远离间隔边界。
- KKT 条件：$a_n \cdot [t_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b) - 1] = 0$。当约束严格满足（$>1$）时，$a_n$ 必须为 0。
- 支撑向量：只有恰好落在间隔边界上的样本（$t_n(\mathbf{w}^T\phi(\mathbf{x}_n)+b) = 1$），才有 $a_n > 0$。
答案：SVM 的稀疏性来自 KKT 互补松弛条件——绝大多数样本对分类器没有贡献，决策边界完全由边界上的少数关键样本决定。
后续用途 / 连接
- L03 贝叶斯分类：生成式模型建模 $p(x|y)p(y)$，当类条件密度为共协方差高斯时退化为线性判别——与 L02 的逻辑回归殊途同归。
- L04 集成学习：SVM 的间隔理论与 Boosting 的 margin 分析有深层联系。
- L07 神经网络：多层感知机可以看作"基函数 $\phi(x)$ 也从数据中学习"的极致推广。
- L08 Transformer：注意力矩阵的 softmax 操作与逻辑回归的 sigmoid 有相似的概率解释。
复习速查
- 基函数：$\phi(x)$ 把线性模型推广到非线性输入空间。
- 线性回归：高斯噪声 + MLE → 平方和误差 → $\mathbf{w}_{ML}=(\Phi^T\Phi)^{-1}\Phi^T\mathbf{t}$。
- 逻辑回归：sigmoid + 交叉熵，输出可解释为概率。
- SVM：最大间隔 → 对偶问题 → 支撑向量稀疏性。
- 核技巧：用 $k(\mathbf{x},\mathbf{x}')$ 隐式计算高维内积，保持线性优化结构。
- 结构化 SVM：输出从标签扩展为结构，是 CRF 的判别式前驱。
参考来源
- 课程课件：25C02 第 3–7 页（线性/非线性定义、基函数）
- 课程课件：25C02 第 10–11 页（线性回归推导）
- 课程课件：25C02 第 20–22 页（逻辑回归）
- 课程课件：25C02 第 37–43 页（SVM、对偶、核方法、软间隔）
- 课程课件：25C02 第 49–50 页（结构化 SVM）
- Oxford ML Lecture 9（https://www.cs.ox.ac.uk/people/varun.kanade/teaching/ML-MT2016/lectures/lecture09.pdf）
- Burges, A Tutorial on Support Vector Machines for Pattern Recognition (1998)