SVM 最大间隔与对偶

SVM 寻找几何间隔最大的分类超平面。线性可分时约束 $y_i(w^Tx_i + b) \ge 1$ (函数间隔归一), 几何间隔为 $\frac{2}{\Vert w\Vert}$, 最大化它等价于最小化 $\frac{1}{2}\Vert w\Vert^2$。引入拉格朗日乘子 $\alpha_i \ge 0$ 得 $L(w, b, \alpha) = \frac{1}{2}\Vert w\Vert^2 - \sum_{i=1}^{n} \alpha_i [y_i(w^Tx_i + b) - 1]$, 对 $w, b$ 求导得 $w = \sum_i \alpha_i y_i x_i$ 与 $\sum_i \alpha_i y_i = 0$, 代回得对偶问题 $\max_{\alpha} \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^Tx_j$ s.t. $\alpha_i \ge 0,\ \sum_i \alpha_i y_i = 0$。KKT 互补松弛条件 $\alpha_i[y_i(w^Tx_i + b) - 1] = 0$: 只有落在间隔边界上 (即满足 $y_i(w^Tx_i+b) = 1$) 的样本 $\alpha_i > 0$, 其余样本 $\alpha_i = 0$——这些非零乘子对应的样本就是支持向量, 决策面 $f(x) = \sum_{i \in SV} \alpha_i y_i x_i^Tx + b$ 只由它们决定。

经典白板题“推导 SVM 对偶”与“为什么只有支持向量起作用”; 是理解核技巧 (对偶中的内积 $x_i^Tx_j$ 被核函数替换) 的前置。

原问题是带不等式约束的凸二次规划 (KKT 条件充分必要); 拉格朗日对偶把它转化为只依赖样本内积 $x_i^Tx_j$ 的问题——内积可被核替换从而实现隐式高维映射 (核技巧), 且互补松弛把模型压缩为 $n_{SV}$ 个支持向量的加权和: 训练存储 $O(n_{SV} \cdot d)$, 推理每个新样本只需与支持向量做内积, 复杂度与全部训练样本解耦。

白板推导 SVM 对偶: 写出 $L = \frac{1}{2}\Vert w\Vert^2 - \sum_i \alpha_i[y_i(w^Tx_i + b) - 1]$, 求 $w, b$ 偏导代回, 写出完整对偶目标与约束。

KKT 互补松弛 $\alpha_i[y_i(w^Tx_i+b) - 1] = 0$ 的几何含义: 为什么非支持向量的 $\alpha_i = 0$, 支持向量如何被识别?

几何间隔与函数间隔的区别: 推导间隔为什么是 $\frac{2}{\Vert w\Vert}$, 为什么要把函数间隔归一化?

推导决策面为什么是 $f(x) = \sum_{i \in SV} \alpha_i y_i x_i^Tx + b$: $w$ 为什么是支持向量的线性组合, 训练/推理复杂度各是多少?

为什么对偶问题能被核技巧利用? 对偶目标中哪些项只含内积, 原问题哪个地方没有内积?