04 — SVM & Kernel Methods / 支持向量机与核方法

支持向量机（Support Vector Machine, SVM）是经典机器学习的巅峰之一。它的核（kernel /ˈkɜːrnl/）心思想简洁而优美：找到一个能将两类数据分开且间隔最大的超平面。而核技巧（Kernel Trick）更让 SVM 能够在不显式计算高维映射的情况下处理非线性分类（classification /ˌklæsɪfɪˈkeɪʃən/）问题——这一思想深刻影响了后来的核方法（Kernel Methods）乃至高斯过程（Gaussian Processes）。

时间线:

• 1963: Vapnik & Chervonenkis 提出线性支持向量机基本思想
• 1992: Boser, Guyon & Vapnik 引入核技巧（Kernel Trick）

• 1995: Cortes & Vapnik 正式发表 SVM（支持向量机）

---

1. 最大间隔分类器（Maximum Margin Classifier）

1.1 问题设定

假设我们有一个二分类数据集 $\{({\mathbf{x}}_i,y_i){\}}_{i=1}^n$，其中 $y_i\in \{-1,+1\}$。我们想找到一个**超平面（Hyperplane）**将两类样本分开：

$$w^T\mathbf{x}+b=0$$

决策规则为：

$$\hat{y}=\{\begin{array}{ll}+1,& w^T\mathbf{x}+b>0\\ -1,& w^T\mathbf{x}+b<0\end{array}$$

1.2 什么是间隔？

直观上，可以分开两类的超平面有无数个。但哪一个最好？

    两类数据点及多个候选超平面：

    ○ ○ ○           ● ● ●
        \       /
    ○   \  (1) /     ●
      ○   \   /   ●
           \ /
            ×      ← 超平面 (2) 似乎更"居中"
           / \
      ○   /   \   ●
        /       \
    ○ ○ ○           ● ● ●

间隔（Margin） 定义为：到超平面最近的样本点（即支持向量，Support Vectors）到超平面的距离。

• 函数间隔（Functional Margin）：${\hat{\gamma }}_i=y_i(w^T{\mathbf{x}}_i+b)$，符号表示分类是否正确，绝对值表示"确信度"。
• 几何间隔（Geometric Margin）：${\gamma }_i=\frac{y_i(w^T{\mathbf{x}}_i+b)}{\parallel w\parallel }$，即函数间隔除以 $\parallel w\parallel$，表示样本到超平面的实际欧氏距离。

最大间隔分类器就是在所有能将数据正确分类的超平面中，选择几何间隔最大的那个。

1.3 为什么最大化间隔能带来更好的泛化？

这是 SVM 最深刻的理论洞见之一：

1. 结构风险最小化（Structural Risk Minimization）：大间隔意味着超平面两侧有更大的"缓冲带"，对小扰动更鲁棒。一个小的输入变化不太可能使样本越过决策边界。

2. VC 维（Vapnik-Chervonenkis Dimension）：间隔 $\gamma$ 与 VC 维之间存在关系：

   $$\text{VC-dim}\le \frac{R^2}{{\gamma }^2}+1$$

   其中 $R$ 是数据分布的半径。间隔越大，VC 维越小，模型的**容量（Capacity）**越低，泛化误差上界越小。

3. 直观理解：想象两块紧挨着的不同颜色的磁铁——如果你只要求它们被隔开，可以有一万种方式。但如果你要求"隔得越远越好"，这个分隔方案就唯一确定了，而且对新的磁铁位置最不敏感。

这是奥卡姆剃刀原则（Occam's Razor）在分类问题上的体现：在能正确分类所有样本的超平面中，间隔最大的那个是最简单的。

1.4 形式化定义

最大间隔分类器的目标函数：

$$\underset{w,b}{max}\frac{1}{\parallel w\parallel }\text{s.t.}{y}_i(w^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

等价地（更方便优化）：

$$\underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2\text{s.t.}{y}_i(w^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

这里的约束条件将函数间隔归一化（normalization /ˌnɔːrmələˈzeɪʃən/）为 1。因为缩放 $w$ 和 $b$ 不会改变超平面本身，我们可以固定 $\hat{\gamma }=1$ 来简化问题。

---

2. 对偶问题（Dual Problem） 📐

2.1 为什么要转对偶？

上述优化问题是一个凸二次规划（Convex Quadratic Programming），可以直接求解。但转成对偶形式有两个关键好处：

1. 对偶问题只涉及数据点的内积（Dot Product）——这为核技巧铺平了道路
2. 对偶形式自然引入了稀疏性——只有支持向量对应的拉格朗日乘子非零

2.2 简要推导（Primal → Lagrangian → Dual）

Step 1 — 构造拉格朗日函数（Lagrangian）：

为每个约束引入拉格朗日乘子 ${\alpha }_i\ge 0$：

$$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i[y_i(w^T{\mathbf{x}}_i+b)-1]$$

Step 2 — 对原始变量求极小：

令 $\frac{\partial \mathcal{L}}{\partial w}=0$ 和 $\frac{\partial \mathcal{L}}{\partial b}=0$：

$$w=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

Step 3 — 回代得到对偶问题：

将 $w$ 的表达式代回 $\mathcal{L}$，消去 $w$ 和 $b$，得到对偶问题（Dual Problem）：

$$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$$$$\text{s.t.}{\alpha }_i\ge 0,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

把"消去 $w$ 和 $b$"这步算给你看

很多教程到"代回即得"就停了，下面把代数补全。从拉格朗日函数出发，先把括号展开：

$$\mathcal{L}=\frac{1}{2}\parallel w{\parallel }^2-\sum _i{\alpha }_i{y}_i{w}^T{\mathbf{x}}_i-b\sum _i{\alpha }_i{y}_i+\sum _i{\alpha }_i$$

用第二步的两个条件做替换。 条件 $\sum _i{\alpha }_i{y}_i=0$ 直接让第三项 $-b\sum _i{\alpha }_i{y}_i$ 整项消失——$b$ 就是这样"消去"的。接着代入 $w=\sum _i{\alpha }_i{y}_i{\mathbf{x}}_i$，分别处理剩下两项：

第一项（范数）：

$$\frac{1}{2}\parallel w{\parallel }^2=\frac{1}{2}{w}^{T}w=\frac{1}{2}(\sum _i{\alpha }_i{y}_i{\mathbf{x}}_i{)}^T(\sum _j{\alpha }_j{y}_j{\mathbf{x}}_j)=\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$$

第二项（同样代入 $w$）：

$$\sum _i{\alpha }_i{y}_i{w}^T{\mathbf{x}}_i=\sum _i{\alpha }_i{y}_i(\sum _j{\alpha }_j{y}_j{\mathbf{x}}_j{)}^T{\mathbf{x}}_i=\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$$

关键：这两项形式完全相同。 第一项是 $+\frac{1}{2}(\cdot )$，第二项前面带负号是 $-(\cdot )$，相加得 $\frac{1}{2}-1=-\frac{1}{2}$ 倍：

$$\mathcal{L}=\underset{\text{第一项}}{\underbrace{\frac{1}{2}\sum _{i,j}(\cdot )}}-\underset{\text{第二项}}{\underbrace{\sum _{i,j}(\cdot )}}+\sum _i{\alpha }_i=\sum _i{\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$$

这正是上面的对偶目标。约束 $\sum _i{\alpha }_i{y}_i=0$ 是替换时用掉的条件，必须作为对偶问题的约束保留下来；${\alpha }_i\ge 0$ 来自原始不等式约束的拉格朗日乘子非负性。现在所有 $\mathbf{x}$ 都只以内积 ${\mathbf{x}}_i^T{\mathbf{x}}_j$ 出现——§3 的核技巧就是把这个内积换成核函数。

2.3 核心洞察

注意对偶问题中，数据点 ${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 只以内积 $⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩={\mathbf{x}}_i^T{\mathbf{x}}_j$ 的形式出现。这个观察至关重要—它直接引出了核技巧。

此外，KKT 条件（Karush-Kuhn-Tucker Conditions）告诉我们：

$${\alpha }_i[y_i(w^T{\mathbf{x}}_i+b)-1]=0,\mathrm{\forall }i$$

这意味着 ${\alpha }_i>0$ 仅当 $y_i(w^T{\mathbf{x}}_i+b)=1$，即样本 ${\mathbf{x}}_i$ 恰好位于间隔边界上。这些样本就是支持向量（Support Vectors）。其他所有样本的 ${\alpha }_i=0$，对模型没有任何影响。

这就是 SVM 的稀疏性（Sparsity）：最终的决策函数仅由少数支持向量决定。

2.4 软间隔（Soft Margin）

当数据不可分时，我们引入松弛变量（Slack Variable） ${\xi }_i\ge 0$ 和惩罚参数（parameter /pəˈræmɪtər/） $C$：

$$\underset{w,b,\xi }{min}\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^n{\xi }_i,\text{s.t.}{y}_i(w^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i$$

• $C$ 越大 → 对误分类的惩罚越重 → 决策边界越复杂（可能过拟合（overfitting /ˈoʊvərˈfɪtɪŋ/））
• $C$ 越小 → 允许更多误分类 → 决策边界更平滑（可能欠拟合（underfitting /ˈʌndərˈfɪtɪŋ/））

---

🔍 完整演算：拉格朗日对偶推导 — 4 样本手算

📐 公式

原始问题（Primal Problem）：

$$\underset{w,b}{min}\frac{1}{2}\parallel w{\parallel }^2\text{s.t.}{y}_i(w^T{\mathbf{x}}_i+b)\ge 1,\mathrm{\forall }i$$

拉格朗日函数（Lagrangian）：

$$\mathcal{L}(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2-\sum _{i=1}^n{\alpha }_i[y_i(w^T{\mathbf{x}}_i+b)-1]$$

对偶问题（Dual Problem）：

$$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$$$$\text{s.t.}{\alpha }_i\ge 0,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

---

📖 参数含义

符号	名称	含义
$w$	权重向量	超平面的法向量，决定决策边界方向
$b$	偏置	超平面到原点的偏移量
${\alpha }_i$	拉格朗日乘子	第 $i$ 个约束对应的对偶变量，${\alpha }_i\ge 0$
${\mathbf{x}}_i$	输入样本	第 $i$ 个数据点的特征向量
$y_i$	类别标签	$\{-1,+1\}$，正负类的标识
$⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$	内积	${\mathbf{x}}_i^T{\mathbf{x}}_j$，衡量两个样本的相似度

---

📝 公式来源

对偶推导分三步：

1. 构造 Lagrangian: 将约束 $y_i(w^T{\mathbf{x}}_i+b)-1\ge 0$ 以 ${\alpha }_i$ 为权重加入目标函数
2. 对 $w,b$ 求极小: 令偏导为零得到 $w$ 的表达式和 ${\alpha }_i$ 的约束条件
3. 回代消去 $w,b$: 代入 Lagrangian 后得到只含 ${\alpha }_i$ 的对偶目标

核心公式 $w=\sum {\alpha }_i{y}_i{\mathbf{x}}_i$ 代入后，内积 $⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩$ 自然出现——这是核技巧的数学基础。

---

✏️ 手算演示

给定 4 个样本：正类 $(+1)$ 两个，负类 $(-1)$ 两个。

样本	特征 ${\mathbf{x}}_i$	标签 $y_i$
$x_1$	$[1,2]$	$+1$
$x_2$	$[2,1]$	$+1$
$x_3$	$[5,5]$	$-1$
$x_4$	$[6,4]$	$-1$

Step 1: 计算核矩阵（内积矩阵）

$$K_{ij}=⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩={\mathbf{x}}_i^T{\mathbf{x}}_j$$$$K=\left[\begin{array}{cccc}5& 4& 15& 14\\ 4& 5& 15& 16\\ 15& 15& 50& 50\\ 14& 16& 50& 52\end{array}\right]$$

Step 2: 写出对偶目标

$$\underset{\alpha }{max}\sum _{i=1}^4{\alpha }_i-\frac{1}{2}\sum _{i=1}^4\sum _{j=1}^4{\alpha }_i{\alpha }_j{y}_i{y}_j{K}_{ij}$$

其中 $y=[+1,+1,-1,-1]$，即 $y_i{y}_j=+1$ 同类、$-1$ 异类。

展开二次项：

$$\begin{array}{rl}\text{Obj}(\alpha )=& {\alpha }_1+{\alpha }_2+{\alpha }_3+{\alpha }_4\\ & -\frac{1}{2}[5{\alpha }_1^2+5{\alpha }_2^2+50{\alpha }_3^2+52{\alpha }_4^2\\ & +8{\alpha }_1{\alpha }_2-30{\alpha }_1{\alpha }_3-28{\alpha }_1{\alpha }_4\\ & -30{\alpha }_2{\alpha }_3-32{\alpha }_2{\alpha }_4+100{\alpha }_3{\alpha }_4]\end{array}$$

Step 3: 约束条件

$${\alpha }_1+{\alpha }_2-{\alpha }_3-{\alpha }_4=0,{\alpha }_i\ge 0$$

Step 4: 求解（示意）

解此二次规划可得最优 ${\alpha }^{\ast }$。通常只有支持向量（间隔边界上的样本）的 ${\alpha }_i>0$，其余为 $0$。本例中 $x_1$, $x_2$, $x_3$ 可能为支持向量。

---

🌍 实际意义

• 对偶形式 是核技巧的入口——目标函数只依赖样本内积，替换为核函数即得非线性 SVM
• 稀疏性：${\alpha }_i>0$ 仅对支持向量成立，使得模型在推理时只计算少数样本的核函数
• 实际库：LIBSVM、scikit-learn 的 SVC 均使用对偶形式求解，内部通过 SMO 算法高效迭代

---

3. 核技巧（Kernel Trick）⭐

3.1 核心问题

现实世界的数据很少是线性可分的。传统的做法是：将数据映射到高维特征空间 $\varphi (\mathbf{x})$，希望在高维空间中数据变得线性可分。

  原始空间 (2D)              特征空间 (3D)
  
     ○    ●                    ○
   ○   ○   ●  ●              ○   ○
     ○   ●   ●           →      ○    ●  ●
       ○ ●  ●                    ○ ●   ●
         ●                          ●
        
  两类交织在一起           高维投影后线性可分

但直接计算 $\varphi (\mathbf{x})$ 可能有三个问题：

1. $\varphi$ 的维度可能极高（甚至无穷维）
2. 显式计算和存储高维向量开销巨大
3. 我们其实只关心高维空间中的内积，而不是坐标本身

3.2 核函数的定义

核技巧（Kernel Trick） 的核心洞察是：

我们不需要显式地计算 $\varphi (\mathbf{x})$，只需要定义一个核函数（Kernel Function） $K({\mathbf{x}}_i,{\mathbf{x}}_j)=⟨\varphi ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)⟩$，它直接给出了两个数据点在高维特征空间中的内积。

回想对偶问题的目标函数，只需将内积替换为核函数：

$$\underset{\alpha }{max}\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)$$

决策函数也相应地变为：

$$f(\mathbf{x})=\sum _{i=1}^n{\alpha }_i{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b$$

这是整个 SVM 中最重要的公式。注意我们从头到尾都没有计算 $\varphi (\mathbf{x})$，只计算了 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$。

3.3 常用核函数

核函数	公式	关键参数	特点
线性核（Linear）	$K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^T{\mathbf{x}}_j$	无	相当于无映射，用于线性可分数据
多项式核（Polynomial）	$K({\mathbf{x}}_i,{\mathbf{x}}_j)=({\mathbf{x}}_i^T{\mathbf{x}}_j+c{)}^d$	$d$（次数）, $c$（偏置）	有限维映射，$d$ 控制复杂度
RBF 核（高斯核）	$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma |{\mathbf{x}}_i-{\mathbf{x}}_j{|}^2)$	$\gamma$	映射到无穷维，最常用
Sigmoid（/ˈsɪɡmɔɪd/） 核	$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh (\kappa {\mathbf{x}}_i^T{\mathbf{x}}_j+\theta )$	$\kappa ,\theta$	类似两层神经网络的激活

3.4 RBF 核详解 📐

RBF（Radial Basis Function）核，也称为高斯核（Gaussian Kernel），是实践中使用最广泛的核函数：

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \parallel {\mathbf{x}}_i-{\mathbf{x}}_j{\parallel }^2)$$

参数 $\gamma$ 的影响：

• $\gamma$ 小 → 核函数随距离衰减慢 → 每个样本的影响范围大 → 决策边界平滑 → 欠拟合风险
• $\gamma$ 大 → 核函数随距离衰减快 → 每个样本只影响其附近区域 → 决策边界曲折 → 过拟合风险

不同 γ 下的决策边界（详见配套代码 svm_demo.py）：

γ = 0.1 (欠拟合)     γ = 1.0 (合适)        γ = 10 (过拟合)
  ╱╲                     ╱ ╲               ╱╱╱╲╲╲
 ╱  ╲    ○  ●          ╱   ╲              ╱╱ ╲╲  ╲
╱    ╲  ○  ●  ●      ╱   ○ ╲ ●          ╱ ○ ╲ ● ╲
╲    ╱  ○ ●  ●       ╲  ○○ ●╱           ╲ ○● ●╱
 ╲  ╱    ●  ○         ╲  ●  ╱            ╲● ○ ╱
  ╲╱                     ╲ ╱               ╲╱╲╱

边界过于平滑，       边界较好地分离          边界紧紧包住
误分类较多           两类数据                每个样本，过拟合

为什么 RBF 核映射到无穷维空间？

将指数展开：

$$\exp (-\gamma \parallel x-x^{\prime }{\parallel }^2)=\exp (-\gamma x^2)\cdot \exp (-\gamma x^{\prime 2})\cdot \sum _{k=0}^{\mathrm{\infty }}\frac{(2\gamma x{x}^{\prime }{)}^k}{k!}$$

这意味着 $\varphi (x)$ 实际上是一个无穷维向量：$\varphi (x)=\exp (-\gamma x^2)\cdot [1,\sqrt{2\gamma }x,\frac{2\gamma }{\sqrt{2!}}{x}^2,\dots ]$。

这就是核技巧的威力：我们在原始空间中用一行代码计算 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$，却等价于在无穷维空间中计算了两个向量的内积。

🔍 完整演算：RBF 核手算 — 两样本不同 $\gamma$ 对比

📐 公式

RBF 核（高斯核）定义：

$$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \parallel {\mathbf{x}}_i-{\mathbf{x}}_j{\parallel }^2)$$

其中 $\parallel {\mathbf{x}}_i-{\mathbf{x}}_j{\parallel }^2=\sum _{k=1}^d(x_{ik}-x_{jk}{)}^2$ 是欧氏距离的平方。

---

📖 参数含义

符号	名称	含义
${\mathbf{x}}_i,{\mathbf{x}}_j$	输入样本	两个数据点的特征向量
$|{\mathbf{x}}_i-{\mathbf{x}}_j{|}^2$	欧氏距离平方	两点在原始空间中的距离
$\gamma$	核宽度参数	控制核函数的衰减速度，$\gamma >0$
$\exp (\cdot )$	指数函数	将距离映射到 $(0,1]$ 区间

---

📝 公式来源

RBF 核来源于高斯函数的形状：

$$\exp (-\frac{\parallel {\mathbf{x}}_i-{\mathbf{x}}_j{\parallel }^2}{2{\sigma }^2})$$

其中 $\sigma$ 是高斯分布的标准差。令 $\gamma =\frac{1}{2{\sigma }^2}$ 即得常用形式 $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \parallel {\mathbf{x}}_i-{\mathbf{x}}_j{\parallel }^2)$。

核函数值域为 $(0,1]$：

• 当 ${\mathbf{x}}_i={\mathbf{x}}_j$ 时取最大值 $1$
• 距离越远，值越接近 $0$

---

✏️ 手算演示

给定两点：$x_1=[1,2]$, $x_2=[4,6]$

Step 1: 计算欧氏距离平方

$$\parallel x_1-x_2{\parallel }^2=(1-4{)}^2+(2-6{)}^2=(-3{)}^2+(-4{)}^2=9+16=25$$

Step 2: 分别计算两种 $\gamma$ 下的核值

情形一：$\gamma =0.1$（小 $\gamma$，平滑边界）

$$K(x_1,x_2)=\exp (-0.1\times 25)=\exp (-2.5)\approx 0.0821$$

情形二：$\gamma =1.0$（大 $\gamma$，曲折边界）

$$K(x_1,x_2)=\exp (-1.0\times 25)=\exp (-25)\approx 1.389\times {10}^{-11}$$

Step 3: 对比分析

$\gamma$	$-\gamma \cdot d^2$	$K(x_1,x_2)$	含义
$0.1$	$-2.5$	$0.0821$	距离 5 个单位时仍有 8% 的"相似度"
$1.0$	$-25$	$\approx 0$	距离 5 个单位时几乎完全不相似

---

🌍 实际意义

• $\gamma$ 控制每个支持向量的影响半径：$\gamma$ 越小，每个点的影响范围越大；$\gamma$ 越大，每个点只影响其极近邻
• 参数选择直接影响泛化：
  • $\gamma$ 太小（如 $0.01$）：每个点影响全局，边界过于平滑，欠拟合
  • $\gamma$ 适中（如 $0.1$）：边界合理，泛化良好
  • $\gamma$ 太大（如 $10$）：每个点只影响自身附近，边界围绕每个样本，过拟合
• 实际调参：常用网格搜索（Grid Search）配合交叉验证选择最优 $\gamma$，典型范围 $[{10}^{-3},{10}^3]$

3.5 Mercer 条件

什么样的函数可以作为核函数？Mercer 条件（Mercer's Condition） 给出了答案：对于任意有限个数据点 $\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_n\}$，核矩阵（Kernel Matrix, Gram Matrix）$K_{ij}=K({\mathbf{x}}_i,{\mathbf{x}}_j)$ 必须是**半正定（Positive Semi-definite）**的。

这保证了存在某个特征空间 $\varphi$ 使得 $K({\mathbf{x}}_i,{\mathbf{x}}_j)=⟨\varphi ({\mathbf{x}}_i),\varphi ({\mathbf{x}}_j)⟩$。

3.6 核技巧的应用范围

核技巧不限于 SVM。任何算法如果其计算只依赖于样本间的内积（即可以写成 ${\mathbf{x}}_i^T{\mathbf{x}}_j$ 的形式），就可以用核函数替换内积来实现"核化"（Kernelization）：

• 核感知机（Kernel Perceptron）
• 核 PCA（Kernel PCA）
• 核岭回归（regression /rɪˈɡreʃən/）（Kernel Ridge Regression）
• 核 K-means（Kernel K-means）

核技巧是"将线性算法推广到非线性"的通用框架。

---

3.7 代码精读：sklearn SVM API 内部结构

调用 SVC.fit() 之后，sklearn 把什么存到模型里？预测时到底算的是哪个公式？下面逐行拆开：

from sklearn.svm import SVC
from sklearn.datasets import make_moons
import numpy as np

X, y = make_moons(n_samples=200, noise=0.15, random_state=42)

# kernel='rbf'  → 高斯核 K(xi, xj) = exp(-γ||xi - xj||²)
# C=1.0         → 软间隔惩罚（越大越严格分类，边界越复杂）
# gamma='scale' → γ = 1 / (n_features * X.var())，自动缩放
svm = SVC(kernel='rbf', C=1.0, gamma='scale')
svm.fit(X, y)

fit() 内部运行的是 SMO 算法（Sequential Minimal Optimization，Platt 1998）——它把大二次规划问题分解成每次只求解两个 ${\alpha }_i$ 的子问题，循环迭代直到 KKT 条件满足。求解完成后，fit() 把结果存进以下几个关键属性：

print("支持向量数量:", svm.n_support_)      # 例如 [32, 28]，各类各多少个
print("支持向量坐标:", svm.support_vectors_.shape)  # (60, 2) — 这60个点在间隔边界上
print("支持向量下标:", svm.support_.shape)          # 在原始 X 中的索引，用于追溯
print("对偶系数 α*y:", svm.dual_coef_.shape)        # (1, 60) — 即 α_i * y_i
print("决策边界偏置:", svm.intercept_)              # [b]，一个标量

逐个解释这些属性对应的数学含义：

属性	数学符号	来源
support_vectors_	$\{{\mathbf{x}}_i\mid {\alpha }_i>0\}$	KKT 条件：只有间隔边界上的样本 ${\alpha }_i\ne 0$
dual_coef_	${\alpha }_i^{\ast }\cdot y_i$	对偶问题的解，已乘上标签；符号对应 §2.3 公式
intercept_	$b$	由支持向量的 KKT 互补条件 $y_i(w^T{x}_i+b)=1$ 推导
n_support_	各类的支持向量个数	C 越大 → 间隔越小 → 支持向量越少（更紧贴边界）

预测时的计算流程：

# predict() 内部等价于：
def _predict_manual(svm, X_test):
    # 1. 计算测试点与所有支持向量的核函数值
    #    K[i, j] = exp(-γ * ||X_test[i] - support_vectors[j]||²)
    from sklearn.metrics.pairwise import rbf_kernel
    gamma = svm._gamma   # 实际 γ 值
    K = rbf_kernel(X_test, svm.support_vectors_, gamma=gamma)
    # K.shape = (n_test, n_sv)

    # 2. 决策函数 f(x) = Σ_j (α_j * y_j) * K(x, x_j) + b
    #    dual_coef_[0] 就是 α_j * y_j
    decision = K @ svm.dual_coef_.T + svm.intercept_
    # decision.shape = (n_test, 1)

    # 3. 取符号得到类别预测
    return np.sign(decision).ravel().astype(int)

关键点：预测只用到支持向量，不是全部训练数据。这就是 SVM 的稀疏性——60 个支持向量 vs 200 个训练点，推理时只算 60 次核函数。

参数调优的直觉与代码：

from sklearn.model_selection import GridSearchCV

param_grid = {
    'C':     [0.1, 1, 10, 100],   # 软间隔惩罚：越大 → 边界越复杂
    'gamma': [0.01, 0.1, 1, 10],  # RBF 宽度：越大 → 影响范围越小
}

grid = GridSearchCV(SVC(kernel='rbf'), param_grid, cv=5, scoring='accuracy')
grid.fit(X, y)
print("最优参数:", grid.best_params_)   # e.g. {'C': 10, 'gamma': 0.1}
print("最优精度:", grid.best_score_)

调参的"感知器"：

• C 小 + gamma 小 → 决策边界很平滑（欠拟合）
• C 大 + gamma 大 → 决策边界紧贴每个点（过拟合）
• 最优区间 通常在两者中间，交叉验证找到的"峡谷"处

---

4. SVM vs 神经网络（Neural Networks）

4.1 哲学对比

维度	SVM	神经网络
核心思想	最大化间隔 + 核技巧	层次化特征学习
优化目标	凸优化（保证全局最优）	非凸优化（可能局部最优）
特征工程	依赖核函数的设计	自动学习特征表示
数据效率	小样本下表现优异	通常需要大量数据
可解释性	支持向量直观可解释	黑箱，难以解释
计算复杂度	$O(n^2\sim n^3)$，训练随样本量增长慢	可大规模并行，GPU 加速

4.2 什么时候用 SVM？

• 小样本（$n<{10}^4$）：SVM 通常优于或不输神经网络
• 特征维度高（$d\gg n$）：如文本分类，SVM 天然擅长
• 需要可解释性：支持向量提供了模型决策的依据
• 数据量巨大（$n>{10}^5$）：此时 SVM 的二次规划开销过高，神经网络的 minibatch 训练更具优势

4.3 有趣的联系

• SVM 使用 hinge loss + 最大间隔；神经网络通常使用 cross-entropy（/ˈentrəpi/） loss
• 现代深度学习中的"权重衰减（Weight Decay）" 本质上就是 SVM 的最大间隔思想的延续
• 最后一个隐藏层的输出可以看作神经网络学习的特征表示 $\varphi (\mathbf{x})$，而输出层则类似于线性 SVM

2012 年之前，SVM 是机器学习的主导范式。深度学习崛起后，SVM 在大规模任务上被取代，但它在小样本场景、核方法理论以及可解释性方面的价值仍然不可替代。

---

本章演算盒索引

位置	演算盒	跳转
§2	🔍 拉格朗日对偶推导 — 4 样本	跳转
§3.4	🔍 RBF 核手算 — 不同 γ 对比	跳转

---

5. 本章小结

概念	要点
最大间隔分类器	找到几何间隔最大的超平面，泛化误差有理论保证
支持向量	仅位于间隔边界上的样本点决定决策边界，其余样本不影响模型
对偶问题	将原始优化转对偶，目标只依赖数据点的内积
核技巧 ⭐	不计算 $\varphi (\mathbf{x})$，只计算 $K({\mathbf{x}}_i,{\mathbf{x}}_j)$，等价于高维空间内积
RBF 核	$K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma |{\mathbf{x}}_i-{\mathbf{x}}_j{|}^2)$，最常用的核函数
$\gamma$ 参数	小 → 欠拟合（边界平滑）；大 → 过拟合（边界曲折）
$C$ 参数	小 → 更大间隔但可能误分类；大 → 更严格分类但可能过拟合
SVM vs NN	小样本选 SVM，大样本选 NN；SVM 凸优化保证全局最优

---

6. 进一步阅读

• The Kernel Trick — 直观解释 (YouTube)
• Support Vector Machines — 3Blue1Brown 可视化讲解
• A Tutorial on Support Vector Machines for Pattern Recognition — Burges, 1998
• LIBSVM: A Library for Support Vector Machines — Chih-Chung Chang & Chih-Jen Lin
• Pattern Recognition and Machine Learning — Christopher Bishop, Chapter 7
• Scikit-learn SVM 文档 — RBF 参数详解

---

下一章：第5章 — 无监督学习

---

配套代码：svm_demo.py — SVM 核函数对比实验，RBF 参数 $\gamma$ 的影响可视化，支持向量标注

参考文献 (References)

1. Vapnik, V. & Chervonenkis, A. (1963). On the uniform convergence of relative frequencies. Doklady Akademii Nauk USSR. — VC 维理论。
2. Cortes, C. & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. — 正式提出 SVM。
3. Boser, B. E., Guyon, I. M. & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. COLT, 144–152. — 核技巧的引入。