支持向量机 SVM

支持向量机是判别式分类方法里最优雅的一个。它不去建模数据怎么分布（那是生成式方法干的事），而是直接问一个几何问题：在所有能分开两类的直线里，哪一条最「稳」？ 整条推导链——最大间隔 → 凸优化 → 对偶 → KKT——是理解现代机器学习里”带约束优化”的绝佳样板。

一、为什么要「最大间隔」

线性可分时，能把两类分开的超平面有无穷多个。它们在训练集上的错误率都是 0，但泛化能力天差地别：一条紧贴着某类样本的边界，稍微来点噪声就会判错；而一条两边都留足空白的边界，对扰动的容忍度高得多。

SVM 的选择是：让边界离最近的样本尽可能远。这个”最近距离”叫间隔（margin），最大化它，就是在”两堵墙之间走正中央”。直觉上，间隔越宽，模型越稳健、泛化越好——这个直觉后来也被统计学习理论严格支持。

二、±1 标签：一个不起眼但关键的设计

设线性模型 $y(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x} + b$，决策取符号。标签不用 $\{0, 1\}$ 而用 $t_n \in \{+1, -1\}$，这个选择带来两个连锁的便利。

其一，分类是否正确能写成一个式子：

$t_n\, y(\mathbf{x}_n) > 0 \iff \text{分类正确}$

因为正类（$t=+1$）应落在 $y>0$ 一侧、负类（$t=-1$）落在 $y<0$ 一侧，对的时候乘积恒正。

其二，点到超平面的距离能去掉绝对值。几何距离本是 $|y(\mathbf{x}_n)| / \|\mathbf{w}\|$，但对分对的点 $t_n y(\mathbf{x}_n)$ 恰好就等于那个绝对值，于是：

$\text{距离} = \frac{t_n\, y(\mathbf{x}_n)}{\|\mathbf{w}\|}$

绝对值是优化的天敌（不可导），这一步把它干净地消掉了。最大间隔的原始目标因此写成：

$\max_{\mathbf{w}, b}\ \frac{1}{\|\mathbf{w}\|} \min_n \left[ t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \right]$

形式上 max 套 min，还不好解，需要再化一刀。

三、规范化：把丑目标变成凸二次规划

关键观察：$(\mathbf{w}, b)$ 同时乘一个正常数，描述的是同一个超平面，但会改变 $y$ 的数值大小。既然这个尺度是自由的，干脆钉死它——规定离超平面最近的点满足 $t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) = 1$。

这样一来，所有点满足 $t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \ge 1$，而最近点的距离就是 $1/\|\mathbf{w}\|$。最大化 $1/\|\mathbf{w}\|$ 等价于最小化 $\frac{1}{2}\|\mathbf{w}\|^2$，于是得到 SVM 的基本型：

$\min_{\mathbf{w}, b}\ \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \ge 1,\ \forall n$

这是一个凸二次规划：目标是凸的，约束是线性的。凸性保证了局部最优即全局最优——没有”卡在坏解里”的风险。

四、对偶问题：换一个视角解同一题

带约束的优化，标准武器是拉格朗日乘子法。给每条约束配一个乘子 $a_n \ge 0$，构造拉格朗日函数：

$L(\mathbf{w}, b, \mathbf{a}) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{n} a_n \left[ t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) - 1 \right]$

对偶问题是什么？可以用博弈来体会：你调 $\mathbf{w}, b$ 想让 $L$ 小，对手调 $\mathbf{a}$ 想让它大。原问题是”你先动”（$\min\max$），对偶是”对手先动”（$\max\min$）。在凸问题里两者的最优值相等（强对偶），所以可以挑更好解的那个来解。

对 $\mathbf{w}, b$ 求偏导置零，得到两个关键关系：

$\mathbf{w} = \sum_{n} a_n t_n \mathbf{x}_n, \qquad \sum_{n} a_n t_n = 0$

第一式意味深长：最优的权向量是训练样本的线性组合。把它代回消元，得到只含乘子的对偶问题：

$\max_{\mathbf{a}}\ \sum_{n} a_n - \frac{1}{2}\sum_{n}\sum_{m} a_n a_m t_n t_m\, \mathbf{x}_n^{\mathsf{T}}\mathbf{x}_m, \quad \text{s.t.}\ a_n \ge 0,\ \sum_n a_n t_n = 0$

对偶形式带来两个深远的好处：样本只通过内积 $\mathbf{x}_n^{\mathsf{T}}\mathbf{x}_m$ 出现——把内积换成核函数，就能不显式升维地处理非线性（核技巧的入口）；而且解出来的 $\mathbf{a}$ 是稀疏的，这直接引出了”支持向量”。

五、KKT 条件：为什么大多数样本「没用」

最优解满足 KKT 条件，其中最核心的是互补松弛：

$a_n \left( t_n\, y(\mathbf{x}_n) - 1 \right) = 0$

这个乘积为零，意味着对每个样本，二者必居其一：

• $a_n = 0$：它对 $\mathbf{w} = \sum_n a_n t_n \mathbf{x}_n$ 毫无贡献。这些是分得很开、落在间隔之外的”安全样本”。
• $t_n y(\mathbf{x}_n) = 1$：它恰好压在间隔边界上，此时 $a_n$ 可以非零。这些点叫支持向量。

结论很惊人：超平面完全由那一小撮支持向量决定，删掉其余所有样本，结果分毫不变。这就是”支持向量机”名字的由来，也是它在高维小样本下依然稳健的原因——模型复杂度由支持向量的数量决定，而非样本总数。

六、软间隔：与噪声和不可分共处

硬间隔有两个软肋：数据线性不可分时根本无解；有一个离群点就能把边界拽歪。解法是给约束”松绑”，引入松弛变量 $\xi_n \ge 0$：

$t_n\, y(\mathbf{x}_n) \ge 1 - \xi_n$

$\xi_n$ 度量第 $n$ 个样本”违规”的程度：0 是乖乖待在间隔外，介于 0 和 1 之间是进了间隔但还在正确一侧，大于 1 就是被分错了。目标函数相应地为违规付费：

$\min_{\mathbf{w}, b, \xi}\ \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{n} \xi_n$

$C$ 是一个权衡旋钮：调大它，重罚违规、逼近硬间隔，训练误差小但容易过拟合；调小它，容忍违规、间隔更宽，泛化更好。这正是机器学习里反复出现的偏差—方差 / 准确—泛化的权衡，在 SVM 里被浓缩成一个超参数。

软间隔的对偶几乎和硬间隔一样，只是乘子多了一个上界 $0 \le a_n \le C$。由此支持向量细分成两种：$0 < a_n < C$ 的点恰在边界上，$a_n = C$ 的点则越了界（进入间隔甚至被错分）。

小结

• SVM 的灵魂是最大间隔：在能分开的边界里挑最稳的那条。
• ±1 标签让”判对”和”距离”都变得可优化；规范化把问题化为凸二次规划。
• 对偶让样本只以内积出现（通向核方法），并暴露出解的稀疏性。
• KKT 互补松弛揭示：只有压在边界上的支持向量真正定义了模型。
• 软间隔用松弛变量 + 惩罚 $C$ 换来对噪声和不可分的鲁棒性，$C$ 是准确与泛化的旋钮。