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

简化版

SVM 从原始问题转成对偶问题主要有三个理由。一、能用核技巧：对偶形式里样本只以内积 xᵢ·xⱼ 出现，可以直接替换成核函数处理非线性——这是最重要的动机。二、复杂度换了个维度：原始问题的变量数是特征维度 d，对偶问题的变量数是样本数 m，当特征维度很高（甚至无穷维，如 RBF 核）时，转成按样本数求解更可行。三、天然暴露支持向量：对偶解里大部分拉格朗日乘子 α=0，只有支持向量 α>0，模型稀疏、结构清晰。对偶问题仍是凸二次规划，与原始问题最优值相等（强对偶成立）。

详细版

原始问题（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ⱼ)` 即可非线性
换维度	变量从 d 维变 m 维；d≫m 或 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)，w 的维度等于特征映射后的维度。如果用 RBF 核（无穷维），w 就是无穷维向量，原始问题根本没法直接写、没法解。只有对偶形式把一切化成内积，核技巧才用得上。所以「为了能用核」是转对偶的头号理由。

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

原始问题变量是 w，维度 = 特征数 d。
对偶问题变量是 α，维度 = 样本数 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 转对偶三大理由：① 能用核（最重要）——对偶目标和预测只以内积 xᵢ·xⱼ 出现，替换成核函数 K 即可处理非线性，而原始问题里 w 与 φ(x) 耦合、无穷维核根本没法写；② 换求解维度——变量从特征维 d（原始）变样本数 m（对偶），特征高维/无穷时按样本数解才可行（反过来样本远多于特征时解原始更快）；③ 天然出支持向量——KKT 使非支持向量 α=0、w=Σαᵢyᵢxᵢ 只由支持向量决定，模型稀疏。理论上 SVM 满足 Slater 条件、强对偶成立，对偶最优=原始最优，解满足 KKT。对偶常用 SMO 求解。

简化版

详细版