知识框架
支持向量机的核心是最大间隔分类。重点包括函数间隔、几何间隔、硬间隔 SVM 原问题、拉格朗日对偶、KKT 条件、软间隔、惩罚系数 $C$、核技巧和常用核函数。
间隔与支持向量
二分类数据 $y_i\in\{-1,+1\}$，超平面为
\[
\mathbf{w}^\top\mathbf{x}+b=0.
\]
函数间隔：
\[
\hat\gamma_i=y_i(\mathbf{w}^\top\mathbf{x}_i+b).
\]
几何间隔：
\[
\gamma_i=\frac{y_i(\mathbf{w}^\top\mathbf{x}_i+b)}{\|\mathbf{w}\|}.
\]
支持向量是离分离超平面最近、决定间隔的样本点。规范化约束 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1$ 后，间隔宽度为
\[
\frac{2}{\|\mathbf{w}\|}.
\]
硬间隔 SVM
线性可分时，最大化间隔等价于
\[
\min_{\mathbf{w},b}\frac{1}{2}\|\mathbf{w}\|^2
\quad
\text{s.t.}\quad
y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1,\ i=1,\ldots,m.
\]
拉格朗日函数：
\[
L(\mathbf{w},b,\mathbf{\alpha})=
\frac{1}{2}\|\mathbf{w}\|^2
-\sum_{i=1}^{m}\alpha_i\left[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\right].
\]
对偶问题：
\[
\max_{\mathbf{\alpha}}\sum_{i=1}^{m}\alpha_i
-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}
\alpha_i\alpha_j y_i y_j \mathbf{x}_i^\top\mathbf{x}_j,
\]
\[
\text{s.t.}\quad \alpha_i\ge 0,\qquad \sum_{i=1}^{m}\alpha_i y_i=0.
\]
解得
\[
\mathbf{w}^{*}=\sum_{i=1}^{m}\alpha_i^{*}y_i\mathbf{x}_i.
\]
只有 $\alpha_i>0$ 的样本影响 $\mathbf{w}^{*}$，它们就是支持向量。
KKT 条件
硬间隔中互补松弛条件：
\[
\alpha_i\left[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\right]=0.
\]
若 $\alpha_i>0$，则样本恰在支持面上；若样本远离间隔边界，则 $\alpha_i=0$。
软间隔 SVM
线性不可分时引入松弛变量：
\[
\min_{\mathbf{w},b,\mathbf{\xi}}\frac{1}{2}\|\mathbf{w}\|^2+C\sum_{i=1}^{m}\xi_i
\]
\[
\text{s.t.}\quad y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1-\xi_i,\qquad \xi_i\ge 0.
\]
其对偶约束变为
\[
0\le \alpha_i\le C,\qquad \sum_i \alpha_i y_i=0.
\]
- $C$ 大：对误分类惩罚重，间隔较小，训练误差低，可能过拟合。
- $C$ 小：允许更多间隔违例，间隔较大，可能欠拟合。
若使用平方松弛惩罚 $\frac{C}{2}\sum_i\xi_i^2$，对偶目标常出现额外的 $-\frac{1}{2C}\sum_i\alpha_i^2$ 项。
核方法
若存在映射 $\phi(\mathbf{x})$，核函数定义为
\[
K(\mathbf{x},\mathbf{z})=\phi(\mathbf{x})^\top\phi(\mathbf{z}).
\]
把对偶问题中的内积替换为核函数即可得到非线性 SVM：
\[
f(\mathbf{x})=\operatorname{sign}\left(
\sum_{i=1}^{m}\alpha_i y_i K(\mathbf{x}_i,\mathbf{x})+b\right).
\]
核函数必须至少满足对称性和正半定性，即任意有限样本上的核矩阵为半正定矩阵。
常用核函数
\[
K(\mathbf{x},\mathbf{z})=\mathbf{x}^\top\mathbf{z}
\]
\[
K(\mathbf{x},\mathbf{z})=(\mathbf{x}^\top\mathbf{z}+c)^d
\]
\[
K(\mathbf{x},\mathbf{z})=\exp(-\gamma\|\mathbf{x}-\mathbf{z}\|^2).
\]
高斯核对应无限维特征映射，$\gamma$ 越大，单个样本影响范围越小，决策边界越容易复杂。
常见问法
- 写出硬间隔 SVM 原始问题，并解释最大间隔含义。
- 给简单二维样本，找支持向量、分离超平面和间隔宽度。
- 推导硬间隔或软间隔 SVM 的拉格朗日对偶。
- 解释 KKT 条件中支持向量对应的非零 $\alpha_i$。
- 比较硬间隔和软间隔几何差别。
- 说明 $C$ 过大或过小时对间隔、误分类和泛化的影响。
- 判断一个函数是否可作为核函数，或说明高斯核的非线性映射作用。