1. 基本概念
1.1 为什么要求对偶问题
SVM的基本型是一个凸二次规划问题，可以直接求解，但通过转化为对偶问题可以：
- 更高效地求解
- 自然地引入核函数
- 更好地理解支持向量的性质
1.2 拉格朗日乘子法
对SVM基本型的每条约束添加拉格朗日乘子αi≥0\alpha_i \ge 0αi≥0，得到拉格朗日函数：
L(w,b,α)=12∣∣w∣∣2+∑i=1mαi(1−yi(wTxi+b))L(w, b, \alpha) = \frac{1}{2}||w||^2 + \sum_{i=1}^{m} \alpha_i (1 - y_i(w^T x_i + b))L(w,b,α)=21∣∣w∣∣2+i=1∑mαi(1−yi(wTxi+b))
令 L(w,b,α)L(w, b, \alpha)L(w,b,α) 对 www 和 bbb的偏导为零可得：
w=∑i=1mαiyixiw = \sum_{i=1}^{m} \alpha_i y_i x_iw=i=1∑mαiyixi
0=∑i=1mαiyi0 = \sum_{i=1}^{m} \alpha_i y_i0=i=1∑mαiyi
2. 对偶困难
2.1 对偶挑战的形式
将上述结果代入拉格朗日函数，消去www 和 bbb，得到对偶挑战：
maxα∑i=1mαi−12∑i=1m∑j=1mαiαjyiyjxiTxj\max_{\alpha} \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j x_i^T x_jαmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxj
s.t.∑i=1mαiyi=0,\text{s.t.} \quad \sum_{i=1}^{m} \alpha_i y_i = 0,s.t.i=1∑mαiyi=0,
αi≥0,i=1,2,…,m.\alpha_i \ge 0, \quad i = 1, 2, \ldots, m.αi≥0,i=1,2,…,m.
对偶问题的特点：
- 变量从 d+1d+1d+1 维（www 和 bbb）变为 mmm 维（α\alphaα）
- 目标函数只涉及样本之间的内积xiTxjx_i^T x_jxiTxj，便于引入核函数
2.2 模型的表示
解出 α\alphaα后，模型可表示为：
f(x)=wTx+b=∑i=1mαiyixiTx+bf(x) = w^T x + b = \sum_{i=1}^{m} \alpha_i y_i x_i^T x + bf(x)=wTx+b=i=1∑mαiyixiTx+b
模型的特点：
- www由承受向量决定（αi>0\alpha_i > 0αi>0 的样本）
- 模型只依赖于帮助向量，具有稀疏性
- 预测时只需计算新样本与支持向量的内积
2.3 KKT条件
对偶问题的求解需满足KKT条件：
{αi≥0;yif(xi)−1≥0;αi(yif(xi)−1)=0.\begin{cases} \alpha_i \ge 0; \\ y_i f(x_i) - 1 \ge 0; \\ \alpha_i (y_i f(x_i) - 1) = 0. \end{cases}⎩⎨⎧αi≥0;yif(xi)−1≥0;αi(yif(xi)−1)=0.
重要结论：
- 若 αi=0\alpha_i = 0αi=0：该样本不会对模型产生影响
- 若 αi>0\alpha_i > 0αi>0：必有 yif(xi)=1y_i f(x_i) = 1yif(xi)=1，该样本是支持向量，位于最大间隔边界上
训练完成后，大部分训练样本都不需保留，最终模型仅与帮助向量有关。
3. SMO算法
3.1 为什么需SMO算法
对偶问题是一个二次规划困难，规模正比于训练样本数，直接求解开销很大。SMO（Sequential Minimal Optimization）算法通过利用问题本身的特性，提供了高效的求解技巧。
3.2 SMO算法的基本思路
SMO的基本思路是每次选择两个变量αi\alpha_iαi 和 αj\alpha_jαj，固定其他参数进行优化。
算法步骤：
- 选取一对需更新的变量αi\alpha_iαi 和 αj\alpha_jαj（优先选择违背KKT条件程度最大的变量）
- 固定其他参数，求解对偶问题获得更新后的αi\alpha_iαi 和 αj\alpha_jαj
为什么高效：
- 固定其他参数后，仅优化两个参数的过程具有闭式解
- 不必调用数值优化算法即可高效计算
3.3 偏移项b的确定
对任意协助向量(xs,ys)(x_s, y_s)(xs,ys) 都有 ysf(xs)=1y_s f(x_s) = 1ysf(xs)=1，因此：
ys(∑i∈SαiyixiTxs+b)=1y_s \left( \sum_{i \in S} \alpha_i y_i x_i^T x_s + b \right) = 1ys(i∈S∑αiyixiTxs+b)=1
其中 SSS为所有支持向量的下标集。
实际任务中常采用更鲁棒的做法：使用所有支撑向量求解的平均值：
b=1∣S∣∑s∈S(ys−∑i∈SαiyixiTxs)b = \frac{1}{|S|} \sum_{s \in S} \left( y_s - \sum_{i \in S} \alpha_i y_i x_i^T x_s \right)b=∣S∣1s∈S∑(ys−i∈S∑αiyixiTxs)
4. 总结
对偶问题的优势：
- 计算效率：对偶问题的求解通常比原疑问更高效
- 核函数引入：对偶形式中只涉及样本之间的内积，便于引入核函数
- 稀疏性：模型只依赖于支持向量，具有很好的稀疏性
SMO算法的特点：
- 高效性：每次只优化两个变量，具有闭式解
- 实用性：适合大规模数据集
- 收敛性：能够保证收敛到全局最优解
支持向量的重要性：
- 拥护向量决定了划分超平面的位置
- 模型具有稀疏性，只需存储承受向量
- 预测时只需计算与支持向量的内积