重学 ML 03：浅层学习的几何巅峰 —— 支持向量机与核技巧

本篇导读：在第一篇与第二篇中，我们以概率建模（MLE / MAP）为主线，让所有样本共同参与拉扯出一条平均平衡边界。本篇我们彻底切换视角，进入浅层学习的几何巅峰——支持向量机（SVM）：从“抗微扰最宽安全区”出发，推导拉格朗日对偶与 KKT 条件的样本稀疏性，拆解高斯核通往无穷维空间的核技巧，并在文末打通它与现代 Transformer 注意力机制的数学同构。

---

1. 历史的转折：当概率拟合遇到“几何抗扰动”

在前两站中，我们的核心武器是逻辑回归（对数几率回归）与极大似然/最大后验估计（MLE / MAP）。那是一套典型的概率建模思维：

• 每个样本点无论离分界线多远，都会通过 Sigmoid 函数计算出概率 $p_i$，并在交叉熵损失中贡献一份梯度力 $(p_i-y_i)x_i$；

• 最终学出的分界线，是全场所有正负样本共同拔河、妥协出的平均平衡线。

然而，在 20 世纪 90 年代初，统计学习理论奠基人弗拉基米尔·瓦普尼克（Vladimir Vapnik）与同事提出了另一个直击本质的几何问题：

如果两类数据在空间中是线性可分的，那么能把它们完美切开的直线（超平面）有无穷多条。在这无穷多条“训练误差都为 0”的分界线中，哪一条才是在面对未知测试数据时最稳健、最不容易出错的？

图：分类边界的几何抗扰动对比——左图传统线性分类/逻辑回归受全样本平均拉扯，分界线贴近样本簇边缘，微小噪声抖动即可导致越界误判；右图支持向量机（SVM）在两类边界之间撑开最宽的“无人安全走廊” $\text{Margin}=2/\Vert w{\Vert }_2$，由压在 $\pm 1$ 边界上的支持向量锁定最优决策面

1.1 走钢丝 vs 走大桥：间隔（Margin）的物理直觉

想象你在一条峡谷上方通行：

• 如果分界线紧贴着某一侧的训练样本擦肩而过，虽然当前训练集全部判对，但未来测试样本只要在测量噪声或环境波动下出现哪怕一丁点抖动（$\Delta x$），就会直接越界被判错；

• 最稳健的策略，是找到正负两类样本点集之间最宽的那条“真空走廊（隔离带）”，然后把分类超平面不偏不倚地架设在这条走廊的正中央。

这条走廊的宽度，就叫做间隔（Margin）。撑起这条走廊边缘、离分界线最近的那几个关键样本点，就是后来名震天下的支持向量（Support Vectors）。

认知飞跃： 从逻辑回归到硬间隔 SVM，机器学习完成了一次深刻的视角切换——从“最大化全样本的后验概率似然”，转向了“最大化分类边界的抗扰动几何安全距离（最大间隔原理）”。

---

2. 几何定标：为什么最大化间隔等价于 $\min \frac{1}{2}\Vert w{\Vert }_2^2$？

要把“撑开最宽走廊”的几何直觉变成计算机能解的数学方程，我们需要严格定义“点到超平面的距离”，并消解掉方程里的尺度冗余。

2.1 点到超平面的几何距离

设特征空间中的分类超平面方程为：

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

其中 $w\in {\mathbb{R}}^d$ 是决定超平面朝向的法向量（垂直于超平面，指向正类一侧），$b\in \mathbb{R}$ 是决定超平面平移位置的截距。

同时，为了书写极其优美，SVM 将二分类标签约定为 $y_i\in \{-1,+1\}$（而非逻辑回归里的 $\{0,1\}$）。

对于空间中任意一个样本点 $x_i$，它到超平面 $w^{T}x+b=0$ 的垂直欧氏距离是多少？

通过基础解析几何（将向量投影到单位法向量 $\frac{w}{\Vert w{\Vert }_2}$ 上，完整推导见 附录 A），该垂直距离为：

${\gamma }_i=\frac{|w^T{x}_i+b|}{\Vert w{\Vert }_2}$

由于我们规定正例 $y_i=+1$ 应该落在 $w^T{x}_i+b>0$ 一侧，负例 $y_i=-1$ 应该落在 $w^T{x}_i+b<0$ 一侧，因此只要样本被正确分类，$y_i$ 与 $(w^T{x}_i+b)$ 就必然同号！于是绝对值符号可以直接写成两者的乘积：

${\gamma }_i=\frac{y_i(w^T{x}_i+b)}{\Vert w{\Vert }_2}(\text{几何间隔 Geometric Margin})$

其中分子 ${\hat{\gamma }}_i\triangleq y_i(w^T{x}_i+b)$ 被称为函数间隔（Functional Margin）。

2.2 尺度冗余的消解：用“定标尺”锁死分子

我们的目标是：让所有样本中离超平面最近的那个几何距离 $\gamma ={\min }_i{\gamma }_i$ 达到最大：

${\max }_{w,b}\gamma ={\max }_{w,b}{\min }_{i=1,\dots ,n}\frac{y_i(w^T{x}_i+b)}{\Vert w{\Vert }_2}$

初看这个式子，分子和分母同时含有未知参数 $w$，是个非凸的分式优化问题。但仔细观察超平面方程 $w^{T}x+b=0$，你会发现一个极其重要的几何事实：

超平面的参数具有“齐次缩放不变性”：如果你把 $(w,b)$ 同时乘以任意正数 $c>0$（比如翻 10 倍变成 $10w$ 和 $10b$），方程 $10w^{T}x+10b=0$ 表示的是空间中完完全全同一个超平面！法向量方向没变，位置也没变，点到平面的真实几何距离 ${\gamma }_i$（分子分母的 $10$ 刚好约掉）也丝毫未变，唯独分子的函数间隔 $y_i(w^T{x}_i+b)$ 被人为放大了 $10$ 倍。

既然 $(w,b)$ 的整体缩放倍数是个可以任意调节的自由度（如同你可以选“米”或“厘米”做标尺），我们干脆强行定下规矩（Canonical Hyperplane 规范化定标）：

在同一超平面的所有等价参数缩放版本中，我们只选那个让离分界线最近的样本点的函数间隔恰好等于 $1$ 的 $(w,b)$！即规定： ${\min }_{i=1,\dots ,n}{y}_i(w^T{x}_i+b)=1$

这一步“定标”堪称神来之笔！一旦规定了最近点的分子等于 $1$：

1. 所有样本的约束条件立刻简化为简洁的线性不等式：

   $y_i(w^T{x}_i+b)\ge 1,\forall i=1,\dots ,n$

2. 走廊的总宽度（裕度 Margin）瞬间只剩下了分母：

   • 压在上边界（$w^T{x}_{+}+b=+1$）的正类支持向量到中心平面的距离是 $\frac{1}{\Vert w{\Vert }_2}$；

   • 压在下边界（$w^T{x}_{-}+b=-1$）的负类支持向量到中心平面的距离也是 $\frac{1}{\Vert w{\Vert }_2}$；

   • 两条平行边界之间的总隔离带宽度就是：

     $\text{Margin}=\frac{2}{\Vert w{\Vert }_2}$

图：支持向量机的规范化几何定标与最大间隔走廊——通过锁死最近样本（支持向量）的函数间隔 $y_i(w^T{x}_i+b)=1$，将最大化走廊总宽度 $\text{Margin}=2/\Vert w{\Vert }_2$ 转化为在每个支持向量周围吹起半径为 $r=1/\Vert w{\Vert }_2$ 的抗微扰安全球

2.3 鲁棒优化视角（Robust Optimization）：为每个样本吹大“抗微扰安全球”

很多人初学最大间隔时，会以为“撑开最宽走廊”只是一个纯粹的直观几何比喻。然而在现代鲁棒优化（Robust Optimization）理论中，最大化几何间隔与“最坏情况下的输入微扰鲁棒性（Worst-case Input Perturbation Robustness）”在代数上是完全等价的！

假设我们观测到的训练样本 $x_i$ 存在现实测量噪声或物理环境波动，或者未来的未知测试样本会在 $x_i$ 附近发生半径为 $r$ 的欧氏空间微扰 $\delta$（即真实输入可能落在闭球 $B_2(x_i,r)=\{x_i+\delta \mid \Vert \delta {\Vert }_2\le r\}$ 内）。

如果我们提出一个最严苛的抗扰动鲁棒分类要求：

“无论扰动 $\delta$ 朝哪个最坏的方向偏移，只要其欧氏范数 $\Vert \delta {\Vert }_2\le r$，该样本在扰动后的新位置 $x_i+\delta$ 都必须依然被正确分类，绝不越界！”

用数学语言写出这个最坏情况（Worst-case）鲁棒约束：

${\min }_{\Vert \delta {\Vert }_2\le r}{y}_i(w^T(x_i+\delta )+b)\ge 0,\forall i=1,\dots ,n$

我们来严密求解内层的极小化对抗问题：

展开左侧括号：

$y_i(w^T{x}_i+b)+{\min }_{\Vert \delta {\Vert }_2\le r}\left(y_i{w}^T\delta \right)\ge 0$

为了让 $y_i{w}^T\delta$ 达到极小值，扰动向量 $\delta$ 必然选择与法向力 $y_{i}w$ 严格反向的最坏攻击方向，且使出极限范数 $\Vert \delta {\Vert }_2=r$。由柯西-施瓦茨不等式（Cauchy-Schwarz Inequality），该内积的极小值精确为：

${\min }_{\Vert \delta {\Vert }_2\le r}(y_i{w}^T\delta )=-r\Vert y_{i}w{\Vert }_2=-r\Vert w{\Vert }_2$

代回原鲁棒不等式，立即得到：

$y_i(w^T{x}_i+b)-r\Vert w{\Vert }_2\ge 0⟺\frac{y_i(w^T{x}_i+b)}{\Vert w{\Vert }_2}\ge r$

这一推导揭示了震人心魄的几何本质：

• 左侧 $\frac{y_i(w^T{x}_i+b)}{\Vert w{\Vert }_2}$ 恰恰就是样本到分类平面的几何间隔 ${\gamma }_i$；

• 右侧 $r$ 则是系统能够100% 抵御未知微扰的安全球半径（Robustness Radius）！

因此，“最大化两类样本间的几何间隔”，在物理上完完全全等价于“在每个训练样本点周围吹起一个最大的等半径欧氏抗扰安全球 $B_2(x_i,r)$，并要求所有安全球互不越界、彼此相切”！

在规范化定标 ${\min }_i{y}_i(w^T{x}_i+b)=1$ 下，这个极限抗扰半径被精确锁死为：

$r=\frac{1}{\Vert w{\Vert }_2}$

要让抗扰半径 $r$ 尽可能大，就必须让分母 $\Vert w{\Vert }_2$ 尽可能小——这也正是上图左侧清晰呈现的几何画面：支持向量周围的抗扰球恰好与中心超平面相切！

2.4 硬间隔 SVM 的主问题（Primal Problem）

想要让走廊宽度 $\frac{2}{\Vert w{\Vert }_2}$（即抗扰安全球半径 $r=\frac{1}{\Vert w{\Vert }_2}$）最大，等价于让分母 $\Vert w{\Vert }_2$ 最小；为了求导后消去系数 $2$ 且变成光滑的二次函数，我们等价地最小化 $\frac{1}{2}\Vert w{\Vert }_2^2$。

于是，硬间隔支持向量机的基本型（主问题）正式诞生：

$\begin{array}{rl}\underset{w,b}{\min }& \frac{1}{2}\Vert w{\Vert }_2^2\\ \text{s.t.}& y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,n\end{array}$

与第二站 L2 正则化的跨时空回响： 在第二站中，我们从高斯先验导出 $\min (\text{Loss}+\lambda \Vert w{\Vert }_2^2)$，那时我们说“把 $\Vert w{\Vert }_2^2$ 压小是为了防止权重膨胀、压制方差”。 而在第三站，SVM 给了 $\Vert w{\Vert }_2^2$ 一个如刀削般锐利的几何解释：当分类边界处的函数输出被定标为 $\pm 1$ 时，$\Vert w{\Vert }_2$ 越小，意味着从 $-1$ 爬升到 $+1$ 的斜坡越平缓，两类边界在物理空间中被撑开的安全隔离带 $\frac{2}{\Vert w{\Vert }_2}$ 就越宽！统计上的“参数范数收缩”与几何上的“最大安全间隔”，在这里实现了深刻的底层统一。

---

3. 拉格朗日对偶与 KKT 条件：为什么绝大多数样本“毫无话语权”？

观察上面的主问题：目标函数 $\frac{1}{2}\Vert w{\Vert }_2^2$ 是严格凸的二次函数（关于 $w$），约束条件 $1-y_i(w^T{x}_i+b)\le 0$ 是线性的。这是一个标准的凸二次规划（Convex Quadratic Programming, QP）问题，直接丢给现成的数值求解器就能算出唯一的全局最优解 $(w^{\ast },b^{\ast })$。

既然主问题直接就能解，为什么所有的机器学习教材（包括《西瓜书》）都要大费周章地引入拉格朗日乘子 ${\alpha }_i$，把它转化成“对偶问题（Dual Problem）”？

这里藏着 SVM 走向巅峰的两个核心秘密：

1. 揭示解的稀疏结构（物理力学直觉）：证明最优超平面仅仅由极少数压线的“支持向量”决定，其余海量内部样本权重严格为 $0$；

2. 为“核技巧（Kernel Trick）”铺平道路（维度解耦）：主问题的变量维度是特征维度 $d$（若升维到无穷维就无法直接计算 $w$）；而对偶问题中所有的特征向量全部收缩为样本间的成对内积 $x_i^T{x}_j$，从而让我们能够在无穷维空间中“隐式切分”！

3.1 拉格朗日函数与“零和博弈”鞍点直觉

为了把 $n$ 个不等式约束 $1-y_i(w^T{x}_i+b)\le 0$ 融合进目标函数，我们为每个样本引入一个非负的拉格朗日乘子（Lagrange Multiplier） ${\alpha }_i\ge 0$，构造广义拉格朗日函数：

$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }_2^2+{\sum }_{i=1}^n{\alpha }_i(1-y_i(w^T{x}_i+b))$

为什么主问题等价于 ${\min }_{w,b}{\max }_{\alpha \ge 0}L(w,b,\alpha )$？你可以把它想象成一场“立法者与找茬裁判的博弈”：

• 先固定 $(w,b)$，让裁判 $\alpha \ge 0$ 极大化 $L$：

  • 如果你选的 $(w,b)$ 违背了任意一个样本的约束（即存在某个 $i$ 使得 $1-y_i(w^T{x}_i+b)>0$），裁判只需把对应的 ${\alpha }_i$ 拧到 $+\infty$，总目标就会瞬间爆炸为 $+\infty$！

  • 反之，如果你选的 $(w,b)$ 乖乖遵守了所有约束（即 $1-y_i(w^T{x}_i+b)\le 0$ 恒成立），由于 ${\alpha }_i\ge 0$，第二项 $\sum {\alpha }_i(\dots )\le 0$；裁判为了尽量让 $L$ 大一点，只能无奈地把所有严格小于 0 的项对应的 ${\alpha }_i$ 全部设为 $0$，此时 ${\max }_{\alpha \ge 0}L(w,b,\alpha )$ 刚好还原为 $\frac{1}{2}\Vert w{\Vert }_2^2$。

因此，外层再对 $(w,b)$ 求极小，就完全等价于原约束问题！由于该主问题是凸二次规划且在严格线性可分时满足 Slater 条件（强对偶性成立，详细数学条件见 附录 B），我们可以合法地交换 $\min$ 和 $\max$ 的顺序，先固定 $\alpha$ 对无约束的 $(w,b)$ 求极小，再对 $\alpha$ 求极大：

${\min }_{w,b}{\max }_{\alpha \ge 0}L(w,b,\alpha )={\max }_{\alpha \ge 0}{\min }_{w,b}L(w,b,\alpha )$

3.2 极值消元：从特征参数 $(w,b)$ 到样本内积 $x_i^T{x}_j$

在内层固定 $\alpha$，对 $(w,b)$ 求偏导并令其等于 $0$：

1. 对法向量 $w$ 求偏导：

   ${\nabla }_{w}L=w-{\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i=0⟹\mathbf{w}={\sum }_{\mathbf{i}=1}^{\mathbf{n}}{\alpha }_{\mathbf{i}}{\mathbf{y}}_{\mathbf{i}}{\mathbf{x}}_{\mathbf{i}}$

2. 对截距 $b$ 求偏导：

   $\frac{\partial L}{\partial b}=-{\sum }_{i=1}^n{\alpha }_i{y}_i=0⟹{\sum }_{\mathbf{i}=1}^{\mathbf{n}}{\alpha }_{\mathbf{i}}{\mathbf{y}}_{\mathbf{i}}=0$

将上面两个关系式代回拉格朗日函数 $L(w,b,\alpha )$ 中消去 $w$ 和 $b$（完整代数消元步骤见 附录 B），便得到了只含 $\alpha$ 的对偶问题（Dual Problem）：

$\begin{array}{rl}\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(x_i^T{x}_j)\\ \text{s.t.}& \sum _{i=1}^n{\alpha }_i{y}_i=0,\\ & {\alpha }_i\ge 0,i=1,2,\dots ,n\end{array}$

3.3 力学图景与 KKT 互补松弛：为什么只有“压线点”决定天下？

请仔细审视刚刚求导得出的三个核心关系，它们与最优解必须满足的 KKT 条件（Karush-Kuhn-Tucker Conditions） 共同构成了极其美妙的刚体静力学平衡图景：

1. 最优法向量是样本的线性组合（表示定理的雏形）：

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

   这说明：分类超平面的法向量 $w^{\ast }$，完全是由训练样本 $x_i$ 按照权重 ${\alpha }_i^{\ast }{y}_i$ 叠加而成的！

2. KKT 互补松弛条件（Complementary Slackness）—— 稀疏性的根源：

   在最优解处，每个样本的乘子 ${\alpha }_i^{\ast }$ 与其约束余量必须满足乘积为零：

   ${\alpha }_i^{\ast }(1-y_i(w^{\ast T}{x}_i+b^{\ast }))=0,\forall i=1,\dots ,n$

   两个非负数的乘积为 $0$，意味着它们至少有一个必须为 $0$！这直接将全体训练样本切分成了命运截然不同的两类：

   • 绝大多数内部样本（远离走廊边缘）：它们老老实实待在安全区深处，满足严格不等式 $y_i(w^{\ast T}{x}_i+b^{\ast })>1$（即括号项 $1-y_i(\dots )\ne 0$）。为了满足乘积为 $0$，它们的拉格朗日乘子必须严格等于零：${\alpha }_i^{\ast }=0$！

     这意味着：这些内部样本在公式 $w^{\ast }=\sum {\alpha }_i^{\ast }{y}_i{x}_i$ 中的系数是 $0$！哪怕你把走廊外面的那 99% 的样本点随手删掉、或者在安全区内任意挪动位置，最优分类超平面纹丝不动！

   • 极少数压线样本（支持向量 Support Vectors）：唯有当 ${\alpha }_i^{\ast }>0$ 时，该样本才对 $w^{\ast }$ 有贡献；而一旦 ${\alpha }_i^{\ast }>0$，括号项就必须等于 $0$，即：

     $y_i(w^{\ast T}{x}_i+b^{\ast })=1$

     这些点分毫不差地刚好压在走廊的两条平行边界线 $w^{\ast T}x+b^{\ast }=\pm 1$ 上！它们就像在峡谷两侧顶住隔离板的那几根柱子，独自“支撑”起了整个分类超平面——这就是“支持向量（Support Vectors）”这一名字的精确由来。（注：几何上刚好压在边界 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$ 上的点，在退化情形下也可能出现 ${\alpha }_i^{\ast }=0$；在严格意义上，我们将 ${\alpha }_i^{\ast }>0$ 的样本定义为支持向量。）

3. 静力学合力与力矩平衡：

   如果把隔离带看作一块刚性挡板，每个支持向量 $x_i$ 都在垂直于边界的方向上对挡板施加一个推力，力的大小就是 ${\alpha }_i^{\ast }$，正例（$y_i=+1$）往一个方向推，负例（$y_i=-1$）往反方向推：

   • 对偶约束 ${\sum }_{i=1}^n{\alpha }_i^{\ast }{y}_i=0⟺{\sum }_{y_i=+1}{\alpha }_i^{\ast }={\sum }_{y_i=-1}{\alpha }_i^{\ast }$，正是正负两侧总推力大小相等、方向相反的“静力学受力平衡条件”（否则挡板就会发生平移）！

   • 而 $w^{\ast }=\sum {\alpha }_i^{\ast }{y}_i{x}_i$ 则是两侧推力共同锁定的法向朝向。

图：KKT 互补松弛条件下的力学图景对比——左图逻辑回归中所有样本均具非零梯度权重 $(p_i-y_i)\ne 0$，全员参与拉扯分界线；右图支持向量机中安全区内部样本乘子严格归零（${\alpha }_i^{\ast }=0$，删去亦不影响分界线），唯独压在 $\pm 1$ 边界上的支持向量（${\alpha }_i^{\ast }>0$）如刚性支柱般锁定超平面

4. 偏置 $b^{\ast }$ 的反解与测试期新样本预测：

   • 为什么对偶问题求完还要单独反解 $b^{\ast }$（且为什么要取平均）？

     回看第 3.2 节：当我们对拉格朗日函数求偏导 $\frac{\partial L}{\partial b}=0$ 时，$b$ 乘上了 ${\sum }_{i=1}^n{\alpha }_i{y}_i=0$，从而在对偶目标函数里直接消掉了。这意味着求解对偶问题只能直接拿到乘子 ${\alpha }^{\ast }$ 和法向量 $w^{\ast }={\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i{x}_i$，而截距 $b^{\ast }$ 必须事后借由支持向量反推出来。

     怎么反推？根据互补松弛条件，任意一个支持向量 $x_s$（$s\in S=\{i\mid {\alpha }_i^{\ast }>0\}$）都精确压在间隔边界上，满足 $y_s(w^{\ast T}{x}_s+b^{\ast })=1$。两边同乘 $y_s$（利用 $y_s^2=1$），理论上随便挑任意一个支持向量 $x_s$，就能直接算出：

     $b^{\ast }=y_s-w^{\ast T}{x}_s=y_s-{\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i⟨x_i,x_s⟩$

     但在计算机数值求解二次规划（如 SMO 算法）时，由于浮点数精度与收敛停止阈值的存在，求出的 ${\alpha }_i^{\ast }$ 会有微小的数值误差，导致代入不同支持向量 $x_s$ 算出来的 $b^{\ast }$ 在小数点后略有波动。因此，在工程实践中（如《西瓜书》式 6.18），通常会把所有支持向量各自算出的 $b^{\ast }$ 取算术平均，以此抵消数值求解的随机扰动，得到最稳健的截距估计：

     $b^{\ast }=\frac{1}{|S|}{\sum }_{s\in S}\left(y_s-{\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i⟨x_i,x_s⟩\right)$

   • 当训练完成、面对从未见过的测试新样本 $x_{\text{new}}$ 时，这公式意味着什么？

     将 $w^{\ast }={\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i{x}_i$ 代入线性判别式 $f(x_{\text{new}})=\mathrm{sign}(w^{\ast T}{x}_{\text{new}}+b^{\ast })$，由于非支持向量的 ${\alpha }_i^{\ast }=0$，求和项自动坍缩为仅对支持向量集合 $S$ 求和：

     $f(x_{\text{new}})=\mathrm{sign}\left({\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i⟨x_i,x_{\text{new}}⟩+b^{\ast }\right)$

     这个看似简单的代换蕴含着两大极其深远的红利：

     1. 极致的推理与存储精简（稀疏性红利）：训练结束后，那 99% 处于安全区内部的训练样本（${\alpha }_i^{\ast }=0$）可以直接从内存里永久丢弃！哪怕训练集有 10 万个样本，只要最后只有 50 个支持向量，预测一个新样本 $x_{\text{new}}$ 时就只需要跟这 50 个支持向量算内积。

     2. 只依赖“样本对内积”（通往第 4 节核技巧的唯一钥匙）：注意看，预测新样本 $x_{\text{new}}$ 时，我们甚至不需要显式把向量 $w^{\ast }$ 算出来存着，而是只需要计算新样本 $x_{\text{new}}$ 与各个支持向量 $x_i$ 之间的内积 $⟨x_i,x_{\text{new}}⟩$！正是因为训练和预测都只需要“两个样本的内积”，下一节我们才能把内积直接替换成核函数 $K(x_i,x_{\text{new}})$，在完全算不出 $w^{\ast }$ 的无穷维空间里照样轻松分类！

---

4. 核技巧（Kernel Trick）：不进高维空间，却享高维切分

在第一站的末尾（第 6.2 节），我们见识了线性分类器的阿喀琉斯之踵——XOR 异或难题与非线性分布（比如一圈正例包着一团负例的同心圆分布）。在原始二维平面上，没有任何一条直线能把内圈和外圈切开。

当时的统计学家提出了破局之道：特征映射升维（Feature Mapping）。

既然在低维空间 ${\mathbb{R}}^d$ 切不开，我们就找一个非线性映射函数 $\varphi :{\mathbb{R}}^d\to \mathcal{H}$，把样本点拍进一个更高维（甚至无穷维）的特征空间 $\mathcal{H}$ 中，然后在高维空间里用超平面 $w^T\varphi (x)+b=0$ 把它们一刀切开！

4.1 为什么要构造“多项式交叉特征”？显式升维又为何会引发“维数灾难”？

（1）直觉追问：为什么要构造 $p$ 阶多项式交叉特征 $\varphi (x)$？

回到二维平面 ${\mathbb{R}}^2$ 上的两个经典非线性难题，答案立刻水落石出：

• 几何弯曲直觉（把二维曲线拉直成三维平面）：

  假设正例在半径为 $1$ 的圆内（$x_1^2+x_2^2<1$），负例在圆外（$x_1^2+x_2^2>1$）；或者分界线是一个斜着的椭圆 $w_1{x}_1^2+w_2{x}_1{x}_2+w_3{x}_2^2+b=0$。

  在原始二维坐标 $(x_1,x_2)$ 下，它是弯曲的二次曲线，任何直线都切不开；但如果我们把二次自乘项与交叉相乘项定义为三维空间的新坐标轴：

  $\varphi (x)=(\underset{z_1}{\underbrace{x_1^2}},\underset{z_2}{\underbrace{x_1{x}_2}},\underset{z_3}{\underbrace{x_2^2}}{)}^T\in {\mathbb{R}}^3$

  那么原来的二维椭圆方程，在新空间 $(z_1,z_2,z_3)$ 里瞬间变成了一个平平无奇的线性超平面 $w_1{z}_1+w_2{z}_2+w_3{z}_3+b=0$！同理，如果你要拟合任意复杂度的光滑曲面，根据泰勒展开（Weierstrass 逼近定理），只需引入更高阶（$p$ 阶）的多项式项，就能在更高维空间里用“一刀平切”等价实现低维空间里任意蜿蜒曲折的非线性分界线。

• 特征交互直觉（突破线性模型的“独立可加性”盲区）：

  普通线性分类器 $w_1{x}_1+w_2{x}_2+b$ 默认特征之间是孤立可加的（特征 1 的贡献与特征 2 的取值无关）。但在真实世界里，分类往往取决于特征之间的协同与逻辑与（AND）交互：

  • 比如 XOR 异或问题：正例在一、三象限（$x_1,x_2$ 同号），负例在二、四象限（$x_1,x_2$ 异号）。单看 $x_1$ 或单看 $x_2$ 毫无区分度，但只要构造出一个二阶交叉特征 $z=x_1{x}_2$，正例全部满足 $z>0$，负例全部满足 $z<0$，瞬间线性可分！

  • 比如图像识别：单个像素 $x_i$ 是黑是白毫无意义，唯有当“左眼位置的像素 $x_i$”、“右眼位置的像素 $x_j$”与“鼻梁位置的像素 $x_k$”同时出现（即高阶乘积项 $x_i{x}_j{x}_k\dots$ 非零）时，才能触发“这是一张人脸”的判别特征。

（2）维数怎么算出来的？—— 显式升维的噩梦（Curse of Dimensionality）

既然 $p$ 阶多项式交叉特征这么好用，为什么我们不能直接把它们全部算出来存成新向量 $\varphi (x)$？

让我们算一笔简单的组合数学账（隔板法 / 可重复组合）：

假设原始输入 $x=(x_1,x_2,\dots ,x_d{)}^T$ 有 $d$ 个特征。我们要构造所有总次数不超过 $p$ 阶的多项式单项式（包含常数项 $1$、一阶项 $x_i$、二阶项 $x_i^2,x_i{x}_j$……直到 $p$ 阶项）。

💡 维数公式的直观推导（选球放盒模型）： 凑出一个次数 $\le p$ 的单项式，等价于手里有 $p$ 个相同的次数名额（球），要分给 $d$ 个特征变量 $(x_1,\dots ,x_d)$ 外加 $1$ 个代表“常数 1”的虚拟桶（一共 $d+1$ 个桶，分到常数桶里的名额代表用 $1$ 占位，从而得到低于 $p$ 阶的项）。 根据高中组合数学的隔板法，$p$ 个球放进 $d+1$ 个桶（允许空桶）的方案数，等于在 $p$ 个球和 $d$ 块隔板构成的 $d+p$ 个位置里选出 $p$ 个位置放球： $\text{映射后总维数 }D=\left(\genfrac{}{}{0ex}{}{d+p}{p}\right)=\frac{(d+p)!}{p!d!}\approx \frac{d^p}{p!}(\text{当 }d\gg p)$

先用 $d=2$ 个特征（$x_1,x_2$）、$p=2$ 阶验证一下公式：

$D=\left(\genfrac{}{}{0ex}{}{2+2}{2}\right)=\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6\text{ 维}⟹\varphi (x)=(\underset{\text{0阶}}{\underbrace{1}},\underset{\text{1阶}}{\underbrace{x_1,x_2}},\underset{\text{2阶}}{\underbrace{x_1^2,x_1{x}_2,x_2^2}}{)}^T$

当特征数很小（$d=2$）时，$6$ 维看起来无比温和。但只要放到真实工业场景里动手算一下，就会立刻撞上一堵算力高墙：

假设原始输入 $x$ 有 $d=1000$ 个特征（比如一张仅 $32\times 32$ 像素的小灰度图）：

• 当 $p=2$（仅含二次交叉项 $x_i{x}_j$）时，映射后的维度是 $\left(\genfrac{}{}{0ex}{}{1000+2}{2}\right)=\frac{1002\times 1001}{2}\approx 50\text{ 万维}$；

• 当 $p=5$（五阶特征交互 $x_{i_1}{x}_{i_2}{x}_{i_3}{x}_{i_4}{x}_{i_5}$）时，映射后的维度高达：

  $D=\left(\genfrac{}{}{0ex}{}{1000+5}{5}\right)\approx \frac{1000^5}{5!}\approx 8.5\times 10^{12}(8.5\text{ 万亿维})!$

如果按照笨办法，先把每个样本 $x_i$ 显式展开成 $8.5$ 万亿维的向量 $\varphi (x_i)$ 存进内存，再去算高维空间里的内积 $\varphi (x_i{)}^T\varphi (x_j)$，地球上所有的超级计算机都会瞬间内存溢出、算力瘫痪。

4.2 核技巧的降维打击：先算内积，再做幂运算！

就在这看似绝境的地方，前文推导出的 SVM 对偶问题 展现出了惊人的威力！

请回头看一眼对偶问题和预测函数：在升维后的空间里，我们从头到尾根本不需要单独知道高维向量 $\varphi (x_i)$ 长什么样，也不需要显式存储高维法向量 $w$！

无论是在训练目标：

${\max }_{\alpha }{\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\underset{\text{唯一出现 }\varphi \text{ 的地方}}{\underbrace{⟨\varphi (x_i),\varphi (x_j)⟩}}$

还是在预测决策：

$f(x)=\mathrm{sign}\left({\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i\underset{\text{唯一出现 }\varphi \text{ 的地方}}{\underbrace{⟨\varphi (x_i),\varphi (x)⟩}}+b^{\ast }\right)$

高维映射 $\varphi (\cdot )$ 永远、且仅仅以“两个样本的高维内积 $⟨\varphi (x),\varphi (z)⟩$”的形式成对出现！

那么，有没有可能完全跳过构造高维向量 $\varphi (x)$ 的过程，直接在原始低维空间 ${\mathbb{R}}^d$ 里用一个极简的二元函数 $K(x,z)$，一步算出它们在高维空间里的内积？

让我们看一个让人拍案叫绝的代数魔术：

设原始输入是二维向量 $x=(x_1,x_2{)}^T$ 和 $z=(z_1,z_2{)}^T$。我们在低维空间直接计算它们内积的平方：

$K(x,z)=(x^{T}z{)}^2=(x_1{z}_1+x_2{z}_2{)}^2=x_1^2{z}_1^2+2x_1{x}_2{z}_1{z}_2+x_2^2{z}_2^2$

仔细看最右边这三项！它可以严丝合缝地拆成两个三维向量的标准内积：

$K(x,z)=\underset{\varphi (x{)}^T}{\underbrace{{\left[\begin{array}{c}{x}_1^2\\ \sqrt{2}{x}_1{x}_2\\ x_2^2\end{array}\right]}^T}}\underset{\varphi (z)}{\underbrace{\left[\begin{array}{c}{z}_1^2\\ \sqrt{2}{z}_1{z}_2\\ z_2^2\end{array}\right]}}=⟨\varphi (x),\varphi (z)⟩$

推广到刚才那个 $d=1000$ 维、$p=5$ 阶多项式的噩梦场景：

• 笨办法（显式映射）：先构造两个 8.5 万亿维的向量 $\varphi (x)$ 和 $\varphi (z)$，再做 8.5 万亿次乘法求和，复杂度是 $O(d^p)\approx 10^{13}$；

• 核技巧（隐式内积）：直接在 1000 维空间算一次普通内积 $x^{T}z$（仅需 1000 次乘法），然后加 $c$ 再求一次 $5$ 次方：

  $K(x,z)=(x^{T}z+c{)}^5=⟨\varphi (x),\varphi (z)⟩$

  计算复杂度仅仅是 $O(d)=1000$ 次运算！

核技巧（Kernel Trick）的本质定义： 如果存在一个定义在原始低维输入空间上的函数 $K(x,z)$，它的计算结果恰好等于某个高维（甚至无穷维）特征空间 $\mathcal{H}$ 中两个映射向量的内积： $K(x,z)=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ 我们就称 $K(x,z)$ 为核函数（Kernel Function）。核技巧就像一条穿越维度的“虫洞”：你在低维空间付出了极其廉价的 $O(d)$ 算力，却在数学上等价于在万亿维乃至无穷维空间里完成了线性超平面切分！

图：特征映射升维与核技巧（Kernel Trick）的几何直觉——在原始二维空间 ${\mathbb{R}}^2$ 中线性不可分的同心圆边界（左），经二次多项式映射 $\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2{)}^T$ 托举至三维抛物面空间 $\mathcal{H}$ 后，内圈正例沉在碗底、外圈负例升上碗壁，即可被一张平直的线性超平面 $⟨w,\varphi (x)⟩+b=0$ 一刀切开（右）；而核函数 $K(x,z)=⟨\varphi (x),\varphi (z)⟩$ 则直接绕开了高昂的显式升维，以 $O(d)$ 的计算代价一步算出高维空间内积

4.3 高斯核（RBF 核）：为什么一行公式能映射进“无穷维空间”？

在所有核函数中，工业界实战统治力最强、最传奇的当属高斯径向基函数核（Gaussian Radial Basis Function Kernel，简称 RBF 核）：

$K(x,z)=\exp \left(-\gamma \Vert x-z{\Vert }_2^2\right)(\gamma =\frac{1}{2{\sigma }^2}>0)$

初看这个公式，它明明只是在原始低维空间里算“两个点 $x$ 和 $z$ 欧氏距离平方的负指数”，怎么就等价于把样本映射到了无穷维（Infinite-dimensional）特征空间做内积呢？

要把这件事彻底看懂，我们只需要记住核技巧的唯一目标：把一个同时含有 $x$ 和 $z$ 的二元函数 $K(x,z)$，拆解成“纯含 $x$ 的项 ${\varphi }_k(x)$”与“纯含 $z$ 的项 ${\varphi }_k(z)$”相乘再相加的形式（因为两个向量的内积定义就是对应坐标相乘再求和：$⟨\varphi (x),\varphi (z)⟩={\sum }_k{\varphi }_k(x){\varphi }_k(z)$）。

我们以一维输入 $x,z\in \mathbb{R}$（为书写清爽，不妨设 $2\gamma =1$）为例，分三步拆解这个魔术：

1. 第一步：把 $(x-z{)}^2$ 拆开，分离“各自独立项”与“交叉纠缠项”

   利用初中完全平方公式 $(x-z{)}^2=x^2+z^2-2xz$，指数上的减法变成同底数幂的乘法：

   $K(x,z)=e^{-\frac{1}{2}(x-z{)}^2}=\underset{\text{只与 }x\text{ 有关}}{\underbrace{e^{-\frac{1}{2}{x}^2}}}\cdot \underset{\text{只与 }z\text{ 有关}}{\underbrace{e^{-\frac{1}{2}{z}^2}}}\cdot \underset{\text{唯一把 }x,z\text{ 绑在一起的项}}{\underbrace{e^{xz}}}$

   看！前两项 $e^{-\frac{1}{2}{x}^2}$ 和 $e^{-\frac{1}{2}{z}^2}$ 已经自动分家了（一个只归 $x$ 管，一个只归 $z$ 管）。现在唯一的绊脚石是第三项 $e^{xz}$——在这里 $x$ 和 $z$ 乘在一起塞进了指数里，怎么把它们拆成“左边的 $x$ 函数 $\times$ 右边的 $z$ 函数”？

2. 第二步：用泰勒级数把 $e^{xz}$ 展开成“0 阶到无穷阶多项式的总和”

   微积分里最基础的指数泰勒展开公式告诉我们：对任意实数 $u$，都有

   $e^u=1+u+\frac{u^2}{2!}+\frac{u^3}{3!}+\cdots +\frac{u^k}{k!}+\cdots ={\sum }_{k=0}^{\infty }\frac{u^k}{k!}$

   现在把 $u=xz$ 代进去！因为 $(xz{)}^k=x^k\cdot z^k$，原本纠缠在指数里的 $x$ 和 $z$ 瞬间在每一项里 cleanly 拆成了左右对称的两半：

   $e^{xz}=1\cdot 1+x\cdot z+\left(\frac{x^2}{\sqrt{2!}}\right)\left(\frac{z^2}{\sqrt{2!}}\right)+\left(\frac{x^3}{\sqrt{3!}}\right)\left(\frac{z^3}{\sqrt{3!}}\right)+\cdots ={\sum }_{k=0}^{\infty }\left(\frac{x^k}{\sqrt{k!}}\right)\left(\frac{z^k}{\sqrt{k!}}\right)$

3. 第三步：把外面的高斯衰减包络乘进去，直接读出无穷维坐标 $\varphi (x)$！

   把第一步分好家的 $e^{-\frac{1}{2}{x}^2}$ 和 $e^{-\frac{1}{2}{z}^2}$ 分别塞进每一项的左右两边，我们就得到了最终的内积分解：

   $K(x,z)={\sum }_{k=0}^{\infty }\underset{\text{第 }k\text{ 维坐标 }{\varphi }_k(x)}{\underbrace{\left(e^{-\frac{1}{2}{x}^2}\frac{x^k}{\sqrt{k!}}\right)}}\cdot \underset{\text{第 }k\text{ 维坐标 }{\varphi }_k(z)}{\underbrace{\left(e^{-\frac{1}{2}{z}^2}\frac{z^k}{\sqrt{k!}}\right)}}=⟨\varphi (x),\varphi (z){⟩}_{{\ell }^2}$

   直觉震撼时刻——那个无穷维向量 $\varphi (x)$ 到底长什么样？

   对于任意一个一维数字 $x$，高斯核实际上隐式地把它映射成了这样一个无穷长（$\infty$ 维）的特征向量：

   $\varphi (x)=\left[\begin{array}{c}{\varphi }_0(x)\\ {\varphi }_1(x)\\ {\varphi }_2(x)\\ {\varphi }_3(x)\\ ⋮\\ {\varphi }_k(x)\\ ⋮\end{array}\right]=e^{-\frac{1}{2}{x}^2}\left[\begin{array}{cc}1& \leftarrow \text{第 0 维：常数基准（局部高斯钟形包络）}\\ x& \leftarrow \text{第 1 维：一阶线性特征（奇函数 S 形波）}\\ \frac{x^2}{\sqrt{2!}}& \leftarrow \text{第 2 维：二阶二次曲率特征（偶函数双峰波）}\\ \frac{x^3}{\sqrt{3!}}& \leftarrow \text{第 3 维：三阶多项式特征}\\ ⋮& ⋮\\ \frac{x^k}{\sqrt{k!}}& \leftarrow \text{第 }k\text{ 维：}k\text{ 阶高次多项式特征（受 }\frac{1}{\sqrt{k!}}\text{ 快速衰减）}\\ ⋮& \end{array}\right]$

   • 在 4.1 节中，多项式核 $(x^{T}z+c{)}^p$ 只能把特征展开到固定的 $p$ 阶；

   • 而高斯核因为借用了指数函数 $e^{xz}$ 的泰勒级数，相当于一口气把 $0$ 阶、$1$ 阶、$2$ 阶……直到无穷阶（$k\to \infty$）的所有多项式特征全部打包放进了向量 $\varphi (x)$ 里！

   • 你可能会问：无穷多项加起来不会爆炸（发散）吗？ 不会！因为每一维坐标都除以了阶乘根号 $\sqrt{k!}$（阶乘的增长速度远超幂函数），并且外面还套了一层高斯衰减壳 $e^{-\frac{1}{2}{x}^2}$。所以随着维度 $k$ 往无穷大走，高阶坐标 ${\varphi }_k(x)$ 会迅速衰减趋近于 $0$，保证无穷维向量的总长度恒为 $1$（即 $\Vert \varphi (x){\Vert }_{{\ell }^2}^2=K(x,x)=e^0=1$，所有样本都被映射到了无穷维单位超球面上！多维输入 $x,z\in {\mathbb{R}}^d$ 的严格展开与 Mercer 定理详见 附录 C）。

高斯核的局部几何直觉：“以支持向量为灯塔的局部相似性叠加”

把高斯核代回 SVM 的预测函数：

$f(x)=\mathrm{sign}\left({\sum }_{i\in S}{\alpha }_i^{\ast }{y}_i\exp \left(-\gamma \Vert x-x_i{\Vert }_2^2\right)+b^{\ast }\right)$

这个公式在原始空间里有着极其直观的物理画面：

• 每个支持向量 $x_i$ 就像在自己的坐标位置立起了一座“高斯钟形山峰（或灯塔）”（正例支持向量是向上隆起的山峰 $+1$，负例支持向量是向下凹陷的盆地 $-1$）；

• 当新样本 $x$ 走过来时，$\exp (-\gamma \Vert x-x_i{\Vert }_2^2)\in (0,1]$ 测量的就是 $x$ 与各个支持向量之间的局部欧氏相似度；

• 带宽参数 $\gamma$ 的几何调控：

  • $\gamma$ 极小（$\sigma$ 极大，山峰极其平缓宽阔）：每个支持向量的辐射范围覆盖全场，叠加出来的等高线非常平滑、接近线性边界（容易欠拟合，高偏差、低方差）；

  • $\gamma$ 极大（$\sigma$ 极小，山峰变成一根根极细的针刺）：只有当 $x$ 几乎贴到某个支持向量脸上时相似度才非零，稍远一点就衰减为 $0$。此时决策边界会在每个正例样本周围画出一个个孤立的“小孤岛”，虽然能把训练集 100% 死记硬背下来，但泛化能力彻底崩溃（严重过拟合，低偏差、高方差）！

图：高斯核（RBF Kernel）的一体两面——左图（代数视角）：通过泰勒级数将交叉项 $e^{xz}$ 展开，把高斯核拆解为从 0 阶钟形波 ${\varphi }_0(x)$、1 阶奇函数波 ${\varphi }_1(x)$、2 阶双峰波 ${\varphi }_2(x)$ 直至无穷阶（$k\to \infty$）特征波包分量在 ${\ell }^2$ 希尔伯特空间中的无穷维内积；右图（几何视角）：在原始空间中，每个正例支持向量立起一座 $+1$ 高斯山峰（陶土红），每个负例支持向量挖出一座 $-1$ 高斯盆地（钢蓝），山峰与盆地相消的零等高线 $f(x)=0$ 即雕刻出平滑的非线性分类边界

---

5. 向现实妥协：两种鲁棒性的辩证博弈与 Hinge 损失大一统

在第 2.3 节中，我们见证了硬间隔 SVM 极其纯粹的物理美感：它通过最大化间隔，在每个样本周围吹起了一个半径为 $r=\frac{1}{\Vert w{\Vert }_2}$ 的抗微扰安全球。

然而，细心的读者在此处会发现一个极其尖锐的“鲁棒性悖论”：

在机器学习中，“鲁棒性（Robustness）”其实存在着两个截然不同、甚至相互冲突的维度：

1. 测试期输入微扰鲁棒性（Test-time Input Perturbation Robustness）：模型学成后，测试样本受到微小欧氏噪声抖动 $\delta$（$\Vert \delta {\Vert }_2\le r$）时，预测判定是否依旧坚挺？
2. 训练期异常值/脏数据鲁棒性（Training-time Outlier Robustness）：在训练阶段，若数据集中混入了标注错误、测量损坏的离群噪点（Outliers），学出的分界线会不会被严重带偏甚至崩溃？

5.1 硬间隔的“安全气囊悖论”与可行解的灾难性缩水

硬间隔 SVM 的全部理论，建立在一个极端理想化的前提之上：假设训练集里的所有数据都是 100% 绝对纯净、标签绝对正确的模范样本。在此前提下，它将所有精力倾注在最大化测试期输入微扰鲁棒性上。

然而，硬间隔 SVM 对每个样本实行的是“绝对平均主义且拥有一票否决权”的铁腕规则：

• 它根本无法分辨哪个点是普遍规律的代表，哪个点是不小心手滑标错的孤立噪点；

• 它死板地要求：全场所有样本，无论良莠，都必须套上同等厚度的抗扰安全气囊 $r=\frac{1}{\Vert w{\Vert }_2}$，且绝不允许任何一个样本的气囊发生碰撞或越界！

一旦真实的训练集混入哪怕一颗脏数据（Outlier），这种对“测试期抗扰动”的极致死守，立刻会在“训练期抗脏数据”上引发灾难性的崩塌：

1. 边缘噪点引发可用解严重缩水，全体正常样本陪葬：若混入的噪点靠近对方阵营，为了给这颗叛徒噪点也吹起同样大小的安全气囊，分类超平面被迫发生剧烈偏转与倾斜；为了不让噪点越界，正负两类之间的走廊被挤压成一条极其狭窄的细缝（$r\to 0$）。为了迁就唯一一颗脏数据，全体正常样本的测试期抗微扰安全气囊被迫大幅缩水！

2. 阵营深处噪点导致几何相撞，可行解空间彻底清零：若噪点直接混入了对方阵营的腹地（例如一个由于录入错误被打上负标的点，物理坐标深深嵌在一堆正例正中央），该噪点的安全气囊与周围正例的气囊必然发生几何干涉与重叠。此时，硬间隔不等式组 $y_i(w^T{x}_i+b)\ge 1$ 瞬间产生代数矛盾，可行域直接变为空集（Infeasible）——模型连一条合法的分界线都选不出来！

图：两种鲁棒性的冲突与软间隔救赎——左图硬间隔为死保单个离群噪点（Outlier）被迫将决策走廊挤压成细缝；右图软间隔通过松弛变量 $\xi >0$（泄气阀）与推力上限 $\alpha \le C$ 容忍单个噪点越界，从而为绝大多数正常样本保住宽阔稳健的分类走廊

这构成了统计学习史上一段发人深省的哲学反讽：硬间隔 SVM 为了在测试期追求极致的“抗微扰”，却在训练期对“脏数据”表现出了几乎弱不禁风的零容忍度！

5.2 软间隔 SVM：给安全气囊装上“泄气阀”（松弛变量 ${\xi }_i$）

为了打破这一僵局，Vapnik 与 Cortes 于 1995 年提出了软间隔（Soft-margin）SVM。

软间隔的核心智慧极其通透：既然要求所有点都拥有毫无妥协的标准气囊太苛刻，我们为每一个样本 $i$ 安装一个“气囊泄气阀 / 减压阀”——非负松弛变量（Slack Variable）${\xi }_i\ge 0$，将硬性约束放宽为：

$y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$

• 若 ${\xi }_i=0$：该样本是守法公民，拥有完整的抗扰安全气囊（处于隔离带边界上或深处）；

• 若 $0<{\xi }_i<1$：气囊部分放气，样本侵入了隔离带走廊内部，但尚未跨过中心决策线 $w^{T}x+b=0$（分类依然正确，只是安全余量不足 $1$）；

• 若 ${\xi }_i=1$：气囊完全瘪掉，样本恰好被推到了中心决策超平面 $w^{T}x+b=0$ 上；

• 若 ${\xi }_i>1$：样本彻底越界穿入敌方阵营，被模型分类错误！

当然，放气不是免费的！总体准则依然是“大家的标准气囊 $r=\frac{1}{\Vert w{\Vert }_2}$ 吹得越大越好，但允许个别刺头脏数据交罚款放气”。每多放一单位的气（${\xi }_i$），就在总目标中交一份罚款 $C\cdot {\xi }_i$。于是得到软间隔 SVM 的主问题：

$\begin{array}{rl}\underset{w,b,\xi }{\min }& \frac{1}{2}\Vert w{\Vert }_2^2+C\sum _{i=1}^n{\xi }_i\\ \text{s.t.}& y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,i=1,\dots ,n\end{array}$

这里的惩罚系数 $C>0$ 充当了两种鲁棒性之间的宏观调谐器：

• $C\to +\infty$（零容忍严打）：放气罚款无穷大，任何 ${\xi }_i>0$ 均被严禁，模型退化回硬间隔 SVM（极致偏向测试期抗微扰，牺牲训练期抗异常值）；

• $C$ 适中或较小（包容路线）：允许少数无法调和的离群点支付代价放气越界（${\xi }_i>0$），从而换取绝大多数正常样本享有宽阔从容的全局安全走廊（兼顾输入抗扰度与脏数据鲁棒性）。

5.3 对偶盒式约束：限制单点推力的“涨停板” $0\le {\alpha }_i\le C$

软间隔问题写成拉格朗日对偶形式后（完整推导见 附录 B.3），其形式与硬间隔高度统一，唯一的质变是乘子 ${\alpha }_i$ 头顶上出现了一道天花板 $C$：

$\begin{array}{rl}\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(x_i,x_j)\\ \text{s.t.}& \sum _{i=1}^n{\alpha }_i{y}_i=0,\\ & 0\le {\alpha }_{\mathbf{i}}\le \mathbf{C},i=1,2,\dots ,n\end{array}$

请从物理力学角度品味这道盒式约束（Box Constraint）的深刻神韵！

在第 3.3 节中我们阐明：${\alpha }_i$ 代表样本对分界线施加的“法向拉扯力”。

• 在硬间隔（$C=\infty$）中，如果混入一个极端离群点，为了强制满足 $y_{i}f(x_i)\ge 1$，它的推力 ${\alpha }_i$ 可以无上限地飙升至无穷大，凭一己之力把整块隔离板掀翻扭曲；

• 而在软间隔中，任何单个样本对全局超平面的最大话语权（推力）被死死封顶在 $C$ 以内（${\alpha }_i\le C$）！哪怕来了一个坐标极其荒谬、深入敌军腹地的错标噪点，它使出的最大力气也只能是 $C$；当这股拉扯力无法撼动全局时，模型宁可让它放气越界（${\xi }_i>1$），也绝不容许它一人绑架全局决策边界！

由 KKT 互补松弛条件，全体样本在这里被清晰地三分天下：

1. 内部样本（${\alpha }_i^{\ast }=0$）：隔离带外侧的安全区内部样本（$y_{i}f(x_i)>1,{\xi }_i^{\ast }=0$），气囊完好，对边界无推力；

2. 自由支持向量（Free Support Vectors）（$0<{\alpha }_i^{\ast }<C$），严格压在隔离带边界线上（$y_{i}f(x_i)=1,{\xi }_i^{\ast }=0$），气囊饱满且刚好相切，工程上正是由这类样本精确反解截距 $b^{\ast }$（⚠️ 注意：绝不能混入 ${\alpha }_i^{\ast }=C$ 的有界支持向量计算平均值！软间隔截距公式为 $b^{\ast }=\frac{1}{|S_{\text{free}}|}{\sum }_{s\in S_{\text{free}}}(y_s-{\sum }_{i\in S}{\alpha }_i^{\ast }{y}_{i}K(x_i,x_s))$，其中 $S_{\text{free}}=\{s\mid 0<{\alpha }_s^{\ast }<C\}$）；

3. 有界支持向量（Bounded Support Vectors）（${\alpha }_i^{\ast }=C$），推力已达涨停板 $C$，泄气阀被触发，侵入了隔离带内部（$0<{\xi }_i^{\ast }\le 1$）甚至已被分错（${\xi }_i^{\ast }>1$）。

5.4 撕下几何外衣：Hinge Loss（合页损失）与统计正则化的大一统

现在，让我们把软间隔主问题里的不等式约束 ${\xi }_i\ge 1-y_i(w^T{x}_i+b)$ 和 ${\xi }_i\ge 0$ 直接合并。为了使目标最小，${\xi }_i$ 必然取这两者的较大值：

${\xi }_i^{\ast }=\max (0,1-y_i(w^T{x}_i+b))$

把它直接代回软间隔主问题的目标函数中，约束瞬间全部消失，变成了一个大家无比眼熟的无约束优化问题：

${\min }_{w,b}[\underset{\text{经验风险：合页损失 (Hinge Loss)}}{\underbrace{C\sum _{i=1}^n\max (0,1-y_i(w^T{x}_i+b))}}+\underset{\text{正则化项：L2 惩罚}}{\underbrace{\frac{1}{2}\Vert w{\Vert }_2^2}}]$

（两边同除以 $C$，令 $\lambda =\frac{1}{2C}$，就完全写成了第二站的标准形式：$\sum {\ell }_{\text{hinge}}+\lambda \Vert w{\Vert }_2^2$！）

全书前三站的终极贯通（几何派 vs 统计派的殊途同归）： 原来，Vapnik 从纯粹几何“最大间隔 + 松弛变量”推导出来的软间隔 SVM，脱下几何外衣后，在代数上完完全全就是“Hinge 损失函数 + L2 正则化”！

• 惩罚系数 $C$ 就是 L2 正则化强度 $\lambda$ 的倒数（$\lambda \propto 1/C$）：$C$ 越小 $⟺\lambda$ 越大 $⟺$ 正则化越强 $⟺\Vert w{\Vert }_2$ 越小 $⟺$ 隔离带 $\frac{2}{\Vert w{\Vert }_2}$ 越宽！
• 为什么 SVM 有稀疏性（支持向量），而逻辑回归没有？全看损失函数的形状！

图：分类替代损失函数对比——Hinge 损失在 $z=y\cdot f(x)\ge 1$ 处存在完全平坦的“零梯度死区”（绿色区域 $\text{Loss}=0$），使安全区内部样本乘子严格归零（${\alpha }_i^{\ast }=0$），造就了支持向量的稀疏性；而 Logistic 损失处处光滑递减、导数永不为零，因此全体样本均参与决策面拉扯

请对比这两条曲线在 $z=y_i(w^T{x}_i+b)\ge 1$（即样本已被正确分类且跑出隔离带以外）时的行为：

• 合页损失（Hinge Loss）${\ell }_{\text{hinge}}(z)=\max (0,1-z)$：

  像一扇合页门，在 $z<1$ 时以斜率 $-1$ 线性惩罚；但一旦 $z>1$，损失直接归零，且导数恒等于 $0$！

  这意味着：只要一个样本已经安全退到了隔离带边界 $1$ 以外，SVM 就会对它说：“你已经及格满分了，我不再关心你还能跑多远，你的梯度归零！” 正是这段水平归零的死区（Flat Zero Region），造就了 ${\alpha }_i^{\ast }=0$ 的支持向量稀疏性！

• 逻辑回归损失（Logistic Loss）${\ell }_{\text{log}}(z)=\ln (1+e^{-z})$（标签取 $\pm 1$ 时的交叉熵，与 Hinge 损失同尺度对比常除以 $\ln 2$）：

  这是一条处处光滑严格递减的曲线，虽然当 $z\to +\infty$ 时渐近趋于 $0$，但它永远不会严格等于 $0$，导数 $-\frac{1}{1+e^z}$ 也永远不会等于 $0$！

  这意味着：哪怕一个样本已经离分界线十万八千里远（$z=10$），逻辑回归依然嫌它的预测概率 $0.99995$ 还不够接近 $1$，依然会给它分配一个微弱的非零梯度。因此逻辑回归在对偶样本空间的解是稠密的（所有样本的 ${\alpha }_i^{\ast }\ne 0$，全员都参与组合）。

深度追问：解的“稀疏（Sparse）”与“稠密（Dense）”究竟各有什么优劣势？

既然 SVM 的样本稀疏解（仅少数 ${\alpha }_i^{\ast }>0$）看起来如此干练，为什么工业界没有彻底淘汰稠密解（如逻辑回归与神经网络交叉熵），反而让稠密解在很多场景下占据了统治地位？

把这两者放在天平上对比，我们会看到一场极为经典的工程与统计学权衡：

💡 认知折叠：把第二站与第三站的“稀疏性”串成一张网 学到这里，你会发现机器学习里的“稀疏 vs 稠密”恰好构成了一对完美的对偶镜像：

• 第二站（L1 Lasso vs L2 Ridge）是在“特征维度 $j\in \{1,\dots ,d\}$”上讨论稀疏：L1 正则通过尖角把无关特征的权重 $w_j^{\ast }$ 砍成 $0$（特征选择）；
• 第三站（Hinge SVM vs Logistic LR）是在“样本维度 $i\in \{1,\dots ,n\}$”上讨论稀疏：Hinge 损失通过 $z\ge 1$ 的平坦折角把无关样本的对偶权重 ${\alpha }_i^{\ast }$ 砍成 $0$（样本选择 / 支持向量）！ 一切稀疏性的数学源头，都来自于优化目标中的“非光滑尖角 / 折角（Non-smooth Kink）”——光滑的曲线（L2 球面、Logistic 损失）永远只会温和地衰减趋近于 $0$，唯有带折角的分段函数（L1 菱形顶点、Hinge 合页拐点）才能产生一步到位的“严格等于 $0$”！

---

6. 15 行 Python 极简验证：亲眼见证支持向量与核技巧

我们用几行代码对比线性核与高斯 RBF 核在非线性同心圆数据上的表现，并验证“删掉所有非支持向量，模型分界线完全不变”这一核心性质：

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

# 1. 生成二维非线性可分数据：内圈正例，外圈负例（同心圆）
X, y = make_circles(n_samples=100, factor=0.4, noise=0.08, random_state=42)

# 2. 训练高斯核 (RBF) SVM（显式指定 tol=1e-9 以消除工程数值停止容差对理论等价性的干扰）
clf_full = SVC(kernel='rbf', C=10.0, gamma=1.0, tol=1e-9).fit(X, y)
sv_indices = clf_full.support_  # 获取支持向量的下标

# 3. 见证奇迹：删掉 80%+ 的内部样本，【只用支持向量】重新训练一个 SVM！
clf_sv_only = SVC(kernel='rbf', C=10.0, gamma=1.0, tol=1e-9).fit(X[sv_indices], y[sv_indices])

# 4. 对比两个模型的参数与预测差异
max_diff = np.max(np.abs(clf_full.decision_function(X) - clf_sv_only.decision_function(X)))
print(f"总样本数: {len(X)}, 支持向量个数: {len(sv_indices)} (仅占 {len(sv_indices)}%)")
print(f"全样本训练 vs 仅用支持向量训练，决策函数最大数值偏差: {max_diff:.2e}")

# 输出：总样本数: 100, 支持向量个数: 14 (仅占 14%)

#       全样本训练 vs 仅用支持向量训练，决策函数最大数值偏差: 4.24e-09 (在数值收敛精度内完全等价！)

看！在 100 个样本中，只有 14 个压在边界上的支持向量起作用。直接把其余 86 个样本从训练集里彻底抹除，重新训练出的高维非线性曲面与原来在数值精度内完全一致（注：scikit-learn 默认 tol=1e-3 时两轮 SMO 优化路径略有不同会有约 $10^{-3}$ 的工程停止浮点差，将精度设为 tol=1e-9 即可见证极限恒等）！这就是 KKT 互补松弛条件赋予 SVM 的数学纯粹性。

---

7. 历史的回望：为什么 SVM 曾统治江湖，又为何让位于深度学习？

在 1995 年到 2012 年（ImageNet 深度学习爆发前）的十余年间，SVM 几乎凭借一己之力将当时的多层神经网络（MLP）打入冷宫，成为学术界与工业界无可争议的头号霸主：

1. 严格的凸优化保证：当年的深层神经网络饱受梯度消失、鞍点停滞、超参数玄学调参之苦；而无论核函数映射到的空间有多高维，SVM 的对偶问题始终是一个凸二次规划问题，保证全局最优，绝无局部极小值陷阱。

2. 小样本下的强泛化能力：得益于最大间隔原理与支持向量的稀疏表示，在样本量仅有几百到几千的年代，SVM 展现出远超同期神经网络的抗过拟合能力。

然而，为什么当时代迈入百万级、亿级大数据的今天，核 SVM 却在图像、语音、自然语言领域全面让位于深度神经网络？

这里有两堵核方法在数学结构上无法绕开的铜墙铁壁：

7.1 算力与内存的“样本量平方死穴”：$O(n^2)\sim O(n^3)$

回顾对偶问题：为了消掉特征维度 $d$，我们把问题转化成了关于 $n$ 个样本乘子 ${\alpha }_i$ 的优化，代价是必须计算和访问一张 $n\times n$ 的核矩阵（Gram Matrix） $K_{ij}=K(x_i,x_j)$：

• 当样本量 $n=1,000$ 时，核矩阵只有 $10^6$ 个浮点数（约 $8\text{ MB}$），使用 SMO 算法（Sequential Minimal Optimization，序列最小优化） 眨眼即出；

• 当样本量 $n=1,000,000$（一百万，现代深度学习的起步规模）时，核矩阵有 $10^{12}$（一万亿）个元素，仅存储这张矩阵就需要 $8,000\text{ GB}$（8 TB）内存！即便使用 SMO 动态缓存局部行，训练时间复杂度依然按 $O(n^2)$ 甚至更高阶暴涨，预测时支持向量的数量 $|S|$ 通常也会随总样本量 $n$ 线性增长，导致每次推理都要同成千上万个支持向量算核函数。

• 相比之下，深度神经网络采用固定规模的参数矩阵 $\theta$，配合 Mini-batch SGD，每步只看几十个样本，训练复杂度关于样本量 $n$ 是线性的 $O(n)$，推理耗时更是与训练样本量 $n$ 完全无关的常数 $O(1)$！样本越多，神经网络越强，而核 SVM 却被样本量活活撑爆。

7.2 工程实战决策矩阵：面对不同的样本量 $n$ 与特征维数 $d$，怎么选主问题/对偶、线性核/高斯核？

把主问题（优化 $d$ 维参数 $w\in {\mathbb{R}}^d$）与对偶问题（优化 $n$ 维样本乘子 $\alpha \in {\mathbb{R}}^n$）放在一起，我们就能总结出工业界经典的“看 $n$ 与 $d$ 下菜碟”铁律（如 LIBLINEAR 与 LIBSVM 的分工哲学）：

7.3 从“固定死核”到“深度学习表征”与“Transformer 注意力（Attention）”的借尸还魂

除了 $O(n^2)$ 的算力瓶颈，核 SVM 让位于深度学习还有一个更深刻的认知哲学分野——但令人惊叹的是，核方法的数学灵魂并没有死，而是在 Transformer 的自注意力机制（Self-Attention） 中完成了华丽的涅槃重生！

1. 为什么传统核 SVM 输给了深度神经网络？——“固定死核” vs “可学习特征映射”

   • 在核 SVM 中，核函数 $K(x,z)=\exp (-\gamma \Vert x-z{\Vert }_2^2)$ 是人类事先写死、与任务无关的固定相似度公式。它只能在原始像素或浅层特征上僵硬地计算欧氏距离——如果一张猫的照片往右平移了 3 个像素，像素欧氏距离 $\Vert x-z{\Vert }_2^2$ 就会剧变，高斯核立刻傻眼。

   • 而深度神经网络把预测写成了 $f(x)=w^T{\varphi }_{\theta }(\mathbf{x})+b$：这里的特征映射 ${\varphi }_{\theta }(x)$ 不再是死公式，而是由多层可训练参数 $\theta$ 驱动的特征提取器！它通过反向传播自动把原始像素扭曲、折叠、提炼成高层语义空间，使得数据在最后一层天然变成线性可分。

2. 震撼彩蛋：Transformer 的 Self-Attention，本质上就是一个“可学习的动态核机器（Learnable Kernel Machine）”！

   请把核 SVM（或核回归）对新样本 $x$ 的预测公式，与大语言模型基石 Transformer 的自注意力（Self-Attention）公式并排放在一起对比：

   • 核方法（Kernel Method）：

     $f(x)={\sum }_{i\in S}\underset{\text{固定核相似度 }\exp (-\gamma \Vert x-x_i{\Vert }^2)}{\underbrace{K(x,x_i)}}\cdot \underset{\text{样本固定权重}}{\underbrace{({\alpha }_i^{\ast }{y}_i)}}$

   • Transformer 自注意力（Self-Attention）：

     $\mathrm{Attention}(q,K,V)={\sum }_{i=1}^n\underset{\text{可学习的非对称指数核 }{K}_{\theta }(x,x_i)}{\underbrace{\frac{\exp (⟨W_{Q}x,W_K{x}_i⟩/\sqrt{d_k})}{{\sum }_{j=1}^n\exp (⟨W_{Q}x,W_K{x}_j⟩/\sqrt{d_k})}}}\cdot \underset{\text{动态价值向量 }{v}_i}{\underbrace{(W_V{x}_i)}}$

   看出来了吗？！这两者在数学骨架上简直是一个模子刻出来的：

   • 继承（同样是“核相似度加权求和”）：

     Transformer 在处理当前词 $x$（Query）时，依然没有把上下文压缩成一个死参数，而是像核方法拿新样本跟支持向量比对一样，拿当前词 $x$ 去跟上下文里的每一个历史词 $x_i$（Key）计算指数内积相似度 $\exp (⟨q,k_i⟩/\sqrt{d_k})$（这在数学上正是一个归一化后的指数核 / 高斯核变体！），然后把历史词的信息 $v_i$ 按核相似度加权汇聚起来！

   • 三大超越（Transformer 是如何进化核方法的？）：

     1. 从“死核”进化为“可学习投影核”：不再直接在原始空间算 $⟨x,x_i⟩$，而是先用可学习的矩阵 $W_Q,W_K$ 把输入投影到语义子空间再算内积 $⟨W_{Q}x,W_K{x}_i⟩$——什么是相似，由数据自己说了算！

     2. 从“对称核”进化为“非对称因果核”：传统核必须满足对称性 $K(x,z)=K(z,x)$（Mercer 定理）；而由于 $W_Q\ne W_K$，Attention 打破了对称性束缚（“我关注你”不等于“你关注我”），从而能够表达有向语法依赖与因果推理！

     3. 连 $O(n^2)$ 的软肋都一脉相承：为什么今天长文本大模型（Long-Context LLM）最头疼的是上下文长度 $n$ 变长时的显存与算力 $O(n^2)$ 爆炸？因为 Self-Attention 的那张 $n\times n$ 注意力矩阵 $A_{ij}=\exp (q_i^T{k}_j/\sqrt{d_k})$，在数学上完完全全就是核方法里那张 $n\times n$ 的 Gram 核矩阵！而近年来大火的 Linear Attention（线性注意力），用的恰恰就是当年核方法为了绕开 $n\times n$ 核矩阵而发明的“显式特征映射重构 $⟨\varphi (q_i),\varphi (k_j)⟩$”技巧！

历史的轮回就是如此迷人：二十年前在 SVM 里锤炼出的“内积核度量、对偶样本表示、Gram 矩阵瓶颈与低秩近似”，在二十年后的今天，依然是理解大模型架构演进最硬核的数学钥匙。

---

8. 本章核心总结与认知闭环

从本章迈向下一站：在第三站，支持向量机用严丝合缝的解析几何与凸对偶理论，将连续特征空间中的超平面切分推向了浅层学习的巅峰。然而在真实的商业与工业世界里（如银行信贷审批、医疗指标诊断、电商用户行为宽表），数据往往不是连续光滑的几何流形，而是充斥着离散类别、缺失值、量纲悬殊且具有强烈“轴平行阶梯规则”的异构表格数据（Tabular Data）——下一站我们将走进“表格数据的王者”：基于信息熵分治的决策树与集成学习（Random Forest / GBDT / XGBoost）。

---

📖 深度附录（数学与理论底座）

本附录提供正文主干所依赖的严密数学证明、历史溯源与理论边界推导，供需要严格求证的读者查阅。

附录 A：点到超平面的欧氏距离与最大间隔主问题的严格几何推导

设超平面 $H=\{x\in {\mathbb{R}}^d\mid w^{T}x+b=0\}$，其中 $w\ne 0$。

1. 为什么 $w$ 必然垂直于超平面 $H$？

   任取超平面 $H$ 上的两个点 $x^{\prime },x^{\prime \prime }\in H$，则它们满足：

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

   两式相减得：

   $w^T(x^{\prime }-x^{\prime \prime })=0$

   由于 $(x^{\prime }-x^{\prime \prime })$ 是平行于超平面 $H$ 的任意方向向量，内积为 $0$ 严格证明了权重向量 $w$ 是超平面 $H$ 的法向量（Normal Vector），对应的单位法向量为 $u=\frac{w}{\Vert w{\Vert }_2}$。

2. 空间任意点 $x_0$ 到超平面 $H$ 的正交投影距离：

   设点 $x_0\in {\mathbb{R}}^d$ 在超平面 $H$ 上的正交投影点（垂足）为 $x_{\perp }\in H$。

   因为连线向量 $(x_0-x_{\perp })$ 与超平面垂直，它必定平行于单位法向量 $u$。记有向投影距离为 $r\in \mathbb{R}$（当 $x_0$ 在 $w$ 指向一侧时 $r>0$，反之 $r<0$），则：

   $x_0-x_{\perp }=r\cdot \frac{w}{\Vert w{\Vert }_2}⟹x_{\perp }=x_0-r\frac{w}{\Vert w{\Vert }_2}$

   因为垂足 $x_{\perp }$ 位于超平面 $H$ 上，必满足 $w^T{x}_{\perp }+b=0$。将上式代入超平面方程：

   $w^T\left(x_0-r\frac{w}{\Vert w{\Vert }_2}\right)+b=0⟹w^T{x}_0-r\frac{w^{T}w}{\Vert w{\Vert }_2}+b=0$

   注意到 $w^{T}w=\Vert w{\Vert }_2^2$，化简立即解出有向距离 $r$ 与绝对欧氏距离 ${\gamma }_0=|r|$：

   $r=\frac{w^T{x}_0+b}{\Vert w{\Vert }_2},{\gamma }_0=|r|=\frac{|w^T{x}_0+b|}{\Vert w{\Vert }_2}$

3. 两条平行支持超平面之间的隔离带宽度：

   在规范化定标 ${\min }_i{y}_i(w^T{x}_i+b)=1$ 下，正负两类的边界超平面分别为：

   $H_{+}:w^{T}x+b=+1,H_{-}:w^{T}x+b=-1$

   由上述距离公式，原点到两平面的有向距离之差（即两平行超平面间的垂直距离）为：

   $\text{Margin}(H_{+},H_{-})=\frac{(+1-b)-(-1-b)}{\Vert w{\Vert }_2}=\frac{2}{\Vert w{\Vert }_2}$

↩ 返回正文：几何定标与最大间隔主问题

---

附录 B：拉格朗日对偶消元、Slater 强对偶定理与 KKT 条件完整推导

1. 强对偶性（Strong Duality）何时成立？

对于一般优化问题 ${\min }_{x}f(x)\text{ s.t. }{g}_i(x)\le 0,h_j(x)=0$，对偶问题最优值 $d^{\ast }={\max }_{\alpha \ge 0,\beta }{\min }_{x}L(x,\alpha ,\beta )$ 与主问题最优值 $p^{\ast }={\min }_x{\max }_{\alpha \ge 0,\beta }L(x,\alpha ,\beta )$ 之间永远满足弱对偶不等式（Weak Duality）：

$d^{\ast }\le p^{\ast }$

（直觉：“矮子里拔将军”永远不超过“将军里挑矮子”）。

而要使等号 $d^{\ast }=p^{\ast }$（强对偶性） 成立，从而允许我们无损地交换 $\min$ 和 $\max$，SVM 满足凸优化中的 Slater 条件：

• 主问题目标函数 $f(w,b)=\frac{1}{2}\Vert w{\Vert }_2^2$ 是凸函数；

• 约束函数 $g_i(w,b)=1-y_i(w^T{x}_i+b)$ 是仿射函数（线性函数）；

• 在凸优化理论中（Boyd & Vandenberghe, Convex Optimization §5.2.3），当所有不等式约束均为仿射函数时，只要主问题存在至少一个可行解（对硬间隔而言即数据线性可分；对软间隔而言，取 $w=0,b=0,{\xi }_i=1$ 恒有严格可行解），强对偶性 $d^{\ast }=p^{\ast }$ 与 KKT 充要条件便严格成立！

2. 硬间隔对偶函数的完整代数消元

拉格朗日函数为：

$L(w,b,\alpha )=\frac{1}{2}{w}^{T}w+{\sum }_{i=1}^n{\alpha }_i-{\sum }_{i=1}^n{\alpha }_i{y}_i{w}^T{x}_i-b{\sum }_{i=1}^n{\alpha }_i{y}_i$

固定 $\alpha \ge 0$，将内层极小化一阶条件 $w={\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i$ 与 ${\sum }_{i=1}^n{\alpha }_i{y}_i=0$ 代入上式：

• 第一项变为：

  $\frac{1}{2}{w}^{T}w=\frac{1}{2}{\left({\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i\right)}^T\left({\sum }_{j=1}^n{\alpha }_j{y}_j{x}_j\right)=\frac{1}{2}{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)$

• 第三项变为：

  $-{\sum }_{i=1}^n{\alpha }_i{y}_i{\left({\sum }_{j=1}^n{\alpha }_j{y}_j{x}_j\right)}^T{x}_i=-{\sum }_{i=1}^n{\sum }_{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i^T{x}_j)$

• 第四项因 ${\sum }_{i=1}^n{\alpha }_i{y}_i=0$ 直接归零！（注意：若 $\sum {\alpha }_i{y}_i\ne 0$，由于 $b\in (-\infty ,+\infty )$ 无约束，${\inf }_{b}L=-\infty$，对极大化无意义，故 $\sum {\alpha }_i{y}_i=0$ 作为硬性约束保留在对偶问题中。）

将第一项（$+\frac{1}{2}$ 倍双重求和）与第三项（$-1$ 倍双重求和）合并，即得对偶目标函数：

${\theta }_D(\alpha )={\inf }_{w,b}L(w,b,\alpha )={\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(x_i^T{x}_j)$

3. 软间隔 SVM 的对偶推导与 KKT 三分天下

软间隔主问题有两类不等式约束：$1-{\xi }_i-y_i(w^T{x}_i+b)\le 0$（对应乘子 ${\alpha }_i\ge 0$）与 $-{\xi }_i\le 0$（对应乘子 ${\mu }_i\ge 0$）。其拉格朗日函数为：

$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}\Vert w{\Vert }_2^2+C{\sum }_{i=1}^n{\xi }_i+{\sum }_{i=1}^n{\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i+b))-{\sum }_{i=1}^n{\mu }_i{\xi }_i$

对主变量 $(w,b,{\xi }_i)$ 分别求偏导并令其等于 $0$：

1. ${\nabla }_{w}L=0⟹w={\sum }_{i=1}^n{\alpha }_i{y}_i{x}_i$

2. $\frac{\partial L}{\partial b}=0⟹{\sum }_{i=1}^n{\alpha }_i{y}_i=0$

3. $\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0⟹{\mu }_i=C-{\alpha }_i$

重点看第 3 式！因为所有含 ${\xi }_i$ 的项在 $L$ 中合并为 ${\sum }_{i=1}^n(C-{\alpha }_i-{\mu }_i){\xi }_i$，一旦代入 $C-{\alpha }_i-{\mu }_i=0$，${\xi }_i$ 就在目标函数中彻底抵消消失了！

同时，由于对偶可行性要求 ${\alpha }_i\ge 0$ 且 ${\mu }_i=C-{\alpha }_i\ge 0$，两者合并便直接导出了著名的盒式约束（Box Constraint）：

$0\le {\alpha }_i\le C$

结合 KKT 互补松弛条件：

$\{\begin{array}{l}{\alpha }_i^{\ast }(1-{\xi }_i^{\ast }-y_{i}f(x_i))=0\\ {\mu }_i^{\ast }{\xi }_i^{\ast }=(C-{\alpha }_i^{\ast }){\xi }_i^{\ast }=0\end{array}$

由此可严密推导出三类样本的几何位置：

• 若 ${\alpha }_i^{\ast }=0⟹{\mu }_i^{\ast }=C>0⟹{\xi }_i^{\ast }=0⟹y_{i}f(x_i)\ge 1$（间隔外部安全点）；

• 若 $0<{\alpha }_i^{\ast }<C⟹{\mu }_i^{\ast }=C-{\alpha }_i^{\ast }>0⟹{\xi }_i^{\ast }=0$，且由第一式知 $1-0-y_{i}f(x_i)=0⟹y_{i}f(x_i)=1$（恰好压在间隔边界上的自由支持向量）；

• 若 ${\alpha }_i^{\ast }=C⟹{\mu }_i^{\ast }=0⟹{\xi }_i^{\ast }\ge 0$，且 $y_{i}f(x_i)=1-{\xi }_i^{\ast }\le 1$（侵入间隔内部甚至被分错的有界支持向量）。

↩ 返回正文：拉格朗日对偶与 KKT 条件

---

附录 C：Mercer 定理、半正定核矩阵与高斯核无穷维映射证明

1. 什么样的二元函数 $K(x,z)$ 才有资格充当合法的核函数？

既然核技巧跳过了显式定义 $\varphi (x)$、直接写出 $K(x,z)$，那我们随便拍脑袋写一个对称函数（比如 $K(x,z)=\sin (x^{T}z)$ 或 $\Vert x-z{\Vert }_2$），都能对应某个高维空间里的真实内积 $⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ 吗？

答案是不能！ 内积运算有着极其严格的几何约束（如满足柯西-施瓦茨不等式、自身内积非负 $⟨v,v⟩\ge 0$）。Mercer 定理（以及 Moore-Aronszajn 再生核希尔伯特空间 RKHS 定理） 给出了充要条件：

正定核（Positive Semidefinite Kernel）判定定理： 对称函数 $K:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 能够表示为某个希尔伯特空间 $\mathcal{H}$ 中的内积 $K(x,z)=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ 的充分必要条件是： 对于输入空间中的任意有限个样本点 $\{x_1,x_2,\dots ,x_n\}$，由它们两两计算构成的 $n\times n$ Gram 核矩阵 $G_{ij}=K(x_i,x_j)$ 都是对称半正定矩阵（Symmetric Positive Semidefinite, $G⪰0$）！

• 必要性一秒看懂：如果 $K(x_i,x_j)=⟨\varphi (x_i),\varphi (x_j)⟩$ 真是内积，那么对于任意实向量 $c=(c_1,\dots ,c_n{)}^T\in {\mathbb{R}}^n$：

  $c^{T}Gc={\sum }_{i=1}^n{\sum }_{j=1}^n{c}_i{c}_j⟨\varphi (x_i),\varphi (x_j){⟩}_{\mathcal{H}}={\Vert {\sum }_{i=1}^n{c}_i\varphi (x_i)\Vert }_{\mathcal{H}}^2\ge 0$

  高维向量自身的范数平方永远非负！而且只有当 Gram 矩阵半正定（$G⪰0$）时，SVM 对偶目标函数中的二次项 $-\frac{1}{2}{\alpha }^T(G\odot y{y}^T)\alpha$ 才是凹的，对偶问题才不会失去凸优化的全局最优保证！

• 理论脉络溯源：在数学发展史上，Mercer 定理原本基于紧致度量空间与连续对称核，依赖积分算子导出 $L^2$ 正交特征函数展开；而将“任意抽象集合上的任意有限样本点集其 Gram 矩阵半正定”作为充要条件直接对应到唯一实再生核希尔伯特空间（RKHS）内积的严格代数保证，是泛函分析中的 Moore-Aronszajn 定理（1950）。机器学习教材常借用广义正定核 / Mercer 核之名统称此充要条件。

2. 多维高斯核（RBF）的无穷维显式映射构造

对任意多维向量 $x,z\in {\mathbb{R}}^d$，高斯核定义为 $K(x,z)=\exp (-\gamma \Vert x-z{\Vert }_2^2)$。利用 $\Vert x-z{\Vert }_2^2=\Vert x{\Vert }_2^2+\Vert z{\Vert }_2^2-2x^{T}z$：

$K(x,z)=e^{-\gamma \Vert x{\Vert }_2^2}{e}^{-\gamma \Vert z{\Vert }_2^2}\exp (2\gamma x^{T}z)=e^{-\gamma \Vert x{\Vert }_2^2}{e}^{-\gamma \Vert z{\Vert }_2^2}{\sum }_{k=0}^{\infty }\frac{(2\gamma {)}^k}{k!}(x^{T}z{)}^k$

其中每一阶幂次 $(x^{T}z{)}^k={\left({\sum }_{j=1}^d{x}_j{z}_j\right)}^k$ 由多项式定理展开为所有满足 $k_1+k_2+\cdots +k_d=k$ 的多重指标 $(k_1,\dots ,k_d)$ 之和：

$(x^{T}z{)}^k={\sum }_{k_1+\cdots +k_d=k}\frac{k!}{k_1!\cdots k_d!}\left(x_1^{k_1}\cdots x_d^{k_d}\right)\left(z_1^{k_1}\cdots z_d^{k_d}\right)$

代入上式后，每一个多重指标 $(k_1,\dots ,k_d)\in {\mathbb{N}}_0^d$ 都对应无穷维空间 ${\ell }^2$ 中的一个坐标分量：

${\varphi }_{(k_1,\dots ,k_d)}(x)=e^{-\gamma \Vert x{\Vert }_2^2}\sqrt{\frac{(2\gamma {)}^{k_1+\cdots +k_d}}{k_1!\cdots k_d!}}{x}_1^{k_1}{x}_2^{k_2}\cdots x_d^{k_d}$

这严格证明了高斯 RBF 核是合法的正定核，且将有限维输入映射到了可数无穷维希尔伯特空间 ${\ell }^2$ 中。进一步可以证明：只要输入的 $n$ 个样本点两两互异（$x_i\ne x_j$）且 $\gamma >0$，高斯核生成的 Gram 矩阵是严格正定（Strictly Positive Definite, $G\succ 0$）且满秩的！

↩ 返回正文：核技巧与高斯核无穷维映射