SVM 为什么要转化成对偶问题求解？

简化版

SVM 对偶形式把样本表示为两两内积，因此可直接用核函数替换内积，并通过非零对偶系数识别支持向量。这是核 SVM 使用对偶的核心价值。常说“原始变量按特征数 d、对偶变量按样本数 n”只是求解规模的粗略比较：软间隔原始约束形式还含 n 个松弛变量，现代线性求解器也可消去松弛写成无约束 hinge 目标；对偶还可能承担 O(n²) 核矩阵代价。所以对偶并非天然降维或更快，选择取决于核、n、d、稀疏性与求解器。

详细版

原始问题（Primal）：

min_{w,b}  ½‖w‖²  (+ C·Σξ)
s.t.       yᵢ(wᵀxᵢ+b) ≥ 1 (-ξᵢ)
变量：w（d 维）、b       ← 变量数 ≈ 特征维度 d

对偶问题（Dual）：

max_α  Σαᵢ - ½ΣΣ αᵢαⱼyᵢyⱼ(xᵢ·xⱼ)
s.t.   Σαᵢyᵢ = 0,  0 ≤ αᵢ ≤ C
变量：α（m 维）          ← 变量数 = 样本数 m

转对偶的三大好处：

好处	说明
能用核	样本只以内积 `xᵢ·xⱼ` 出现 → 换成 `K(xᵢ,xⱼ)` 即可非线性
换表示	对偶有 n 个 α；是否更易解取决于 n、d、核矩阵与求解器
出支持向量	KKT 使非支持向量 α=0，模型稀疏

前提： 强对偶成立（满足 Slater 条件），对偶最优 = 原始最优；解满足 KKT 条件。

完整版教学

一、原始问题长什么样

SVM（软间隔）的原始优化问题是：

min_{w,b,ξ}  ½‖w‖² + C·Σξᵢ
s.t.  yᵢ(wᵀxᵢ+b) ≥ 1 - ξᵢ,  ξᵢ ≥ 0

优化变量是 w（维度 = 特征数 d）和 b（还有松弛 ξ）。
这是个带不等式约束的凸二次规划，本身就能直接解。

既然原始问题能解，为什么还要费劲转成对偶？因为对偶形式带来三个原始形式给不了的关键好处。

二、拉格朗日对偶怎么来的（思路）

对每个约束 yᵢ(wᵀxᵢ+b) ≥ 1-ξᵢ 引入拉格朗日乘子 αᵢ≥0，构造拉格朗日函数 L，然后：

对原始变量 w、b、ξ 求偏导并令为 0，得到关系：

∂L/∂w = 0  ⟹  w = Σ αᵢyᵢxᵢ      ← w 是样本的线性组合！
∂L/∂b = 0  ⟹  Σ αᵢyᵢ = 0
∂L/∂ξ = 0  ⟹  0 ≤ αᵢ ≤ C

把这些关系代回 L，消去 w、b、ξ，就得到只含 α 的对偶问题：

max_α  Σαᵢ - ½ΣΣ αᵢαⱼyᵢyⱼ(xᵢ·xⱼ)
s.t.   Σαᵢyᵢ = 0,  0 ≤ αᵢ ≤ C

关键观察：代入后，样本 xᵢ 只以两两内积 xᵢ·xⱼ 的形式出现，w 也变成了 Σαᵢyᵢxᵢ。这两点正是后面所有好处的根源。

三、好处一（最重要）：能无缝用核技巧

这是转对偶最核心的动机。对偶目标里样本只以内积 xᵢ·xⱼ 出现，预测函数 f(x)=Σαᵢyᵢ(xᵢ·x)+b 也只用内积。

于是要处理非线性，只需把所有内积 xᵢ·xⱼ 替换成核函数 K(xᵢ,xⱼ)=φ(xᵢ)·φ(xⱼ)，就等价于在高维空间跑线性 SVM，却完全不用显式做高维映射（见核技巧专题）。

反观有限维坐标形式的原始问题，需要显式表示 w 与 φ(x)；RBF 对应的特征空间可为无穷维，无法用普通有限坐标直接展开。理论上仍可在再生核希尔伯特空间表述原始问题，但计算上通常借表示定理和核展开求解。所以“让计算只依赖核内积”是转对偶的头号理由。

四、好处二：把「按特征维度」求解变成「按样本数」求解

原始问题的模型参数 w 维度为 d；约束式软间隔还显式含 n 个 ξ_i，无约束线性实现则可把它们消去。
对偶问题变量是 α，维度 = 样本数 m。

这在特征维度远大于样本数时是巨大优势：

用核方法时特征维度可能几千、几万甚至无穷，按 d 求解不可行；按样本数 m 求解就现实得多。
文本等高维稀疏场景 d≫m，对偶更合适。

（反过来，如果样本数 m 远大于特征数 d，原始问题按 d 求解反而更快——所以像 LIBLINEAR 对大样本线性 SVM 会选择解原始问题。转对偶不是无脑更优，而是为了核和高维。）

五、好处三：天然产生稀疏的支持向量

对偶解满足 KKT 互补松弛条件，使得：

间隔外、分类正确的样本 αᵢ=0（非支持向量）。
只有间隔边界上/内/分错的样本 αᵢ>0（支持向量）。

由 w = Σαᵢyᵢxᵢ，只有 α>0 的支持向量真正决定模型。这带来：模型稀疏（只需存支持向量）、预测只需和支持向量算核、结构清晰、对远处离群点鲁棒（见支持向量专题）。这个「谁是支持向量」的信息，是对偶形式自然给出的。

六、理论保障：强对偶与 KKT

转对偶要「合法」，需要对偶最优值 = 原始最优值（强对偶成立）。SVM 是凸问题且满足 Slater 约束规范，所以强对偶成立——解对偶和解原始得到同一个最优。最优解还满足 KKT 条件（平稳性、原始/对偶可行、互补松弛），这既是求解的依据，也是推出「非支持向量 α=0」的来源。

七、常见追问

转对偶一定更快吗？ 不一定。样本多、特征少、线性核时解原始更快（变量少）；特征高维/无穷、要用核时对偶才是必须。
对偶问题怎么解？ 经典是 SMO 算法（每次选两个 α 优化、解析更新），高效处理二次规划。
b 怎么求？ 用 0<α<C 的支持向量满足 yᵢ(wᵀxᵢ+b)=1 反解并平均。
原始问题就不能用核吗？ 很难——原始里 w 与 φ(x) 显式耦合，无穷维时无法表示；对偶只依赖内积才让核可行。

八、用算例与工程边界复核

线性 SVM 原始变量主要随特征维度 d 增长，对偶变量有 n 个、每个样本一个。若 n=100 万、d=100，直接说“对偶更快”显然错误；对偶的关键价值是内积形式与核技巧，求解优势取决于 n、d、稀疏性和算法。

对象/方案	核心机制	选择或风险
原始问题	变量规模主要与 d 相关	大 n 小 d 常更合适
对偶问题	n 个 α 与 Gram 矩阵	核化、支持向量稀疏
强对偶	凸问题+可行条件	KKT 连接原始与对偶

把推导和选择压缩成执行路径：

form Lagrangian
 -> stationarity eliminates w,b
 -> dual in α with inner products
 -> KKT recover w/b and SVs

“转对偶是为了降维”不是普遍结论；样本数大于特征数时，对偶变量反而更多。

九、常见误区与追问

误区：SVM 对偶问题始终比原始问题更容易。 核 SVM 依赖对偶，但线性大样本常用原始或专用线性求解器。
误区：α 非零只是一种数值巧合。 互补松弛把 α 与活跃间隔约束连接起来，形成支持向量。
追问：对偶约束 Σα_i y_i=0 从哪来？ 对拉格朗日函数中的偏置 b 求驻点得到该等式。
追问：为什么 α 有上界 C？ 软间隔中对 ξ 求驻点并结合乘子非负，可推出 0≤α_i≤C。
追问：如何从 α 恢复 w？ 线性情形 w=Σα_i y_i x_i；核情形通常保留对偶展开而不显式构造 w。

十、加强记忆

SVM 对偶的核心是把训练和预测写成样本内积，从而可替换为核函数，并由非零 α 得到支持向量展开。它有 n 个对偶变量并可能需要二次规模的核信息，不是普遍“降维”：大 n 的线性问题常更适合原始或专用线性求解器。软间隔原始约束形式也含 n 个松弛变量，变量数比较必须说明表述方式。凸 SVM 在相应可行条件下满足强对偶与 KKT；线性情形可由 w=Σα_i y_i x_i 恢复权重，核情形通常保留支持向量展开。

简化版

详细版