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 7: Kernels. Support Vector Machines (SVM)

目录 · ← l6 · l8 →

Lecture 7: Kernels. Support Vector Machines (SVM)

概述

本讲介绍两件互相成就的事：核方法 (Kernel Methods)——一种在不显式构造高维特征的情况下让线性模型“隐式”在高维空间工作的技巧；以及支持向量机 (SVM)——基于最大间隔思想的强大分类器。SVM 的对偶形式与核技巧结合，诞生了“核 SVM”，能高效处理非线性分类。本讲是课程中数学最密集的部分之一。

核心概念与数学直觉

  • 特征映射与核技巧：线性模型无法处理非线性可分数据。思路：把输入 $x$ 映射到高维特征空间 $\phi(x)$，在其中做线性分类。
    • 问题：$\phi(x)$ 维度可能爆炸（如二次多项式映射有 $O(n^2)$ 维）。
    • 核技巧 (Kernel Trick)：许多算法（如 SVM 对偶、岭回归）中 $\phi(x)$ 只以内积 $\langle \phi(x), \phi(z) \rangle$ 的形式出现。若存在函数 $K(x, z) = \langle \phi(x), \phi(z) \rangle$ 可直接高效计算，就无需显式构造 $\phi$！
    • 例子：$K(x,z) = (x^T z)^2$ 对应二次多项式特征映射——计算是 $O(n)$，而显式 $\phi$ 是 $O(n^2)$ 维。核技巧 = 免费的高维空间。
    • 常用核：
      • 线性核：$K(x,z) = x^T z$。
      • 多项式核：$K(x,z) = (x^T z + c)^d$。
      • 高斯核 (RBF)：$K(x,z) = \exp\left(-\frac{\vert x - z\vert ^2}{2\sigma^2}\right)$——对应无限维特征空间，衡量两个点的相似度（距离近相似度高）。
    • 合法核的判据（Mercer 定理）：$K$ 是合法核 ⟺ 对任意有限点集，核矩阵 $K_{ij} = K(x^{(i)}, x^{(j)})$ 是半正定的。直觉：核矩阵是“两两相似度”表，必须像内积矩阵一样良定义。
    • 核的运算：核的和、积、常数倍仍是核——可组合出复杂核。
  • SVM：最大间隔分类器：
    • 问题定义：线性二分类。存在无数条分界线都能正确分开数据——SVM 选间隔最大的那条。
    • 直观解释：把分界线想象成“公路”，两侧留出最宽的“缓冲区”（间隔）。间隔越大，对新数据越鲁棒（离边界越远越安全）。SVM 选择使间隔最大的分界线，只由离边界最近的点决定——这些点叫支持向量 (support vectors)。
    • 函数间隔 vs 几何间隔：
      • 函数间隔：$\hat{\gamma}^{(i)} = y^{(i)}(w^T x^{(i)} + b)$（对正确分类样本为正；对 $(w,b)$ 整体缩放会变大——不规范）。
      • 几何间隔：$\gamma^{(i)} = y^{(i)}\left(\frac{w^T}{\vert w\vert } x^{(i)} + \frac{b}{\vert w\vert }\right)$——归一化后的函数间隔，缩放不变，几何意义是点到超平面的距离。
    • 优化问题（原始形式）：最大化最小几何间隔： $\max_{\gamma, w, b} \gamma \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \ge \gamma, \ \|w\| = 1$ 规范化后等价于： $\min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \ge 1, \ \forall i$
      • $\frac{1}{2}\vert w\vert ^2$：最小化 $\vert w\vert $ = 最大化间隔（间隔 $= 2/\vert w\vert $）。
      • 直觉：约束“每个点至少在边界外侧”，目标“边界越宽越好”。
    • 软间隔 (Soft Margin)：数据线性不可分或有噪声时引入松弛变量 $\xi_i$ 与惩罚 $C$： $\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{m} \xi_i \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \ge 1 - \xi_i, \ \xi_i \ge 0$
      • $C$：对“越界点”的容忍度。$C$ 大 ⇒ 严格分类（可能过拟合）；$C$ 小 ⇒ 容忍误分（更平滑）。$\xi_i$ 衡量第 $i$ 个点越界的程度。
    • 对偶形式与核化：构造拉格朗日，对偶问题只依赖内积 $x^{(i)T} x^{(j)}$（替换为 $K(x^{(i)}, x^{(j)})$ 即得核 SVM）。KKT 条件给出：$w = \sum_i \alpha_i y^{(i)} \phi(x^{(i)})$——决策只由 $\alpha_i > 0$ 的支持向量决定： $h(x) = \text{sign}\left( \sum_{i \in SV} \alpha_i y^{(i)} K(x^{(i)}, x) + b \right)$
      • 直觉：新点分类 = 与所有支持向量的“相似度”加权投票。
    • SMO 算法：坐标上升思想的特例，每次只优化两个 $\alpha$（闭式解），循环直到收敛——是实践中训练 SVM 的标准算法。

算法伪代码与逻辑解说：SMO（简化版）

伪代码

输入:
    - 训练数据 (X, y)，y ∈ {-1, +1}
    - 核函数 K(·,·)，惩罚参数 C

输出:
    - 拉格朗日乘子 alpha，偏置 b

1. 初始化 alpha = 0, b = 0
2. 循环直到 alpha 收敛（KKT 条件近似满足）:
    2.1 选取一对"违反 KKT 最严重"的乘子 alpha_i, alpha_j（启发式选择）
    2.2 计算误差: E_i = f(x^(i)) - y^(i)，其中 f(x) = Σ_k alpha_k y_k K(x_k, x) + b
    2.3 解析更新 alpha_j（带上下界 L, H 的裁剪）:
         alpha_j_new = alpha_j + y_j (E_i - E_j) / (K_ii + K_jj - 2K_ij)
         alpha_j_new = clip(alpha_j_new, L, H)     // L, H 由 C 与 alpha_i+alpha_j 决定
    2.4 更新 alpha_i = alpha_i + y_i y_j (alpha_j_old - alpha_j_new)
    2.5 更新 b（由支持向量条件）
3. 返回 alpha, b

【算法逻辑解说】

  1. 为什么对偶：原始问题是约束优化（难）；对偶问题约束简单（$0 \le \alpha_i \le C$），且目标函数只含核内积——核技巧在此落地。
  2. Step 2.1 选对 (pair)：SMO 每次只动两个 $\alpha$（一个也动不了：$\sum \alpha_i y_i = 0$ 约束）。启发式优先选“误差最大”的点对，加速收敛。
  3. Step 2.3 解析更新：固定其他 $\alpha$ 后，$\alpha_j$ 的优化有闭式解——分子是误差差，分母是核矩阵二阶差（曲率）；裁剪到 $[L, H]$ 保证约束 $0 \le \alpha \le C$ 与 $\sum \alpha_i y_i = 0$ 同时满足。
  4. 收敛判定：所有点满足 KKT 条件（对 $\alpha_i = 0$：点在边界内；$0 < \alpha_i < C$：点在边界上；$\alpha_i = C$：点越界）。KKT 是“最优性”的精确刻画。
  5. 预测：只需支持向量（$\alpha_i > 0$ 的点），其余点不参与——稀疏性让 SVM 预测高效。

关键要点

  1. 核技巧：只需内积可计算 ⇒ 隐式高维（甚至无限维）特征空间，计算代价不变。
  2. SVM = 最大间隔分类器；间隔大 ⇒ 泛化好（理论上有界，L13 学习理论部分会提）。
  3. 软间隔参数 $C$ 是偏差-方差旋钮：$C$ 大→低偏差高方差。
  4. 对偶 + KKT：解由支持向量稀疏表示；SMO 是标准训练算法。
  5. 高斯核参数 $\sigma$ 同样控制复杂度：$\sigma$ 小→决策边界更复杂（高方差）。

常见误区与注意事项

  • 不缩放特征直接上核 SVM：高斯核依赖欧氏距离，量纲大的特征主导相似度——必须先标准化。
  • $\sigma$ 与 $C$ 一起盲调：高斯核 SVM 有两个超参数，应网格搜索（对数刻度）。$\sigma$ 过小→每个点都是孤岛（过拟合）；过大→核退化为线性（欠拟合）。
  • 误以为 SVM 输出是概率：标准 SVM 输出的是到边界的距离（margin），不是概率；需要校准（Platt scaling）才能当概率用。
  • 大数据集用 SVM：核矩阵 $O(m^2)$ 内存、SMO $O(m^2)$~$O(m^3)$ 时间；$m > 10^5$ 时优先考虑线性模型/神经网络。
  • 混淆函数间隔与几何间隔的缩放不变性：函数间隔随 $\vert w\vert $ 缩放变化，几何间隔不变——优化必须用几何间隔（或固定 $\vert w\vert =1$ 的规范化形式）。

思考题

  1. 问题：为什么最大化间隔等价于最小化 $\frac{1}{2}\vert w\vert ^2$？
    • 答案：几何间隔 $\gamma = 1/\vert w\vert $（在约束 $y^{(i)}(w^Tx^{(i)}+b) \ge 1$ 规范化后，边界到超平面距离为 $1/\vert w\vert $，总间隔 $2/\vert w\vert $）。最大化 $2/\vert w\vert $ ⟺ 最小化 $\vert w\vert $ ⟺ 最小化 $\frac{1}{2}\vert w\vert ^2$（平方仅便于求导）。
  2. 问题：高斯核 $K(x,z) = \exp(-\vert x-z\vert ^2/2\sigma^2)$ 对应无限维特征映射——直觉上它“记住了什么”？
    • 答案：它衡量点与点的相似度（距离越近越相似）。在训练点上构造的“相似度山峰”（每个支持向量一个峰），叠加后形成任意复杂的决策曲面。$\sigma$ 控制峰宽：$\sigma$ 小→峰窄→只影响极近的点→边界锯齿化（高方差）。
  3. 问题：线性不可分数据上，为何软间隔 SVM 仍可能优于强制硬间隔？
    • 答案：硬间隔要求所有点严格分开——对噪声点会“委曲求全”形成病态边界（高方差、泛化差）。软间隔允许少数点越界（付出 $C\xi_i$ 代价），换来更平滑、间隔更大的边界——用少量训练误差换更小的泛化误差（偏差-方差权衡）。