知识卡片
SMO每次只调两个乘子
SVM 的对偶问题是一个关于 M 个乘子 α 的二次规划,约束有两类:等式约束 Σα_i y_i=0,盒约束 0≤α_i≤C(硬间隔时上界为 ∞)。样本上万时,用通用 QP 求解器直接解,时间和内存都不可接受。SMO(Sequential Minimal Optimization)的思路是把它拆成一连串”最小规模”的子问题。
为什么一次必须动两个。 假设固定其余变量,只把 α_1 增加 δ,那么 Σα_i y_i=0 会被破坏成 δy_1≠0。等式约束就像一个跷跷板:想抬一个,必须压另一个。所以每次至少同时更新一对 (α_i, α_j),并保持 y_iα_i+y_jα_j = 常数——几何上,可行点被限制在盒子里的一条 45° 线段上。
每一轮做什么:
- 选出一对乘子。外层用启发式挑”违反 KKT 最严重”的样本(例如 0<α_i 却不落在边界上的点),内层再挑一个能让目标下降最多的搭档,避免瞎走。
- 固定其余乘子,把目标函数写成只含 α_j 的一元二次式,直接求极值(有解析解,不用迭代)。
- 把解裁剪到 [0,C]×[0,C] 的可行段内,回代得到 α_i。
- 更新 b,使这一对样本恰好满足 KKT。
- 重复,直到所有乘子在容差内都满足 KKT。
它省在哪里: 单步只处理两个变量,代价是 O(M) 级别(主要是算这一对涉及的内积),而不是通用 QP 的 O(M³);而且不需要一次性构造整个 M×M 核矩阵,可以按需计算或缓存,这是 SMO 能与核函数配合、撑住较大样本量的关键。收敛性和稀疏性也保持:最终大部分 α 仍是 0,只有支持向量非零。
说明:以上是理解原文”对偶问题一般用 SMO 求解”所需的背景。原书只点出这一步采用 SMO,未展开细节,也没有给出选点规则与收敛证明;具体实现可参考 libsvm。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 支持向量机 8.2.2 推导 · 查看原书依据
求解上面的优化问题时,原则上可以使用各种合适的优化方法,但一般采用的是SMO算法
参考来源
- 位置:《机器学习基础:从入门到求职》第8章《第8章 支持向量机》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00011.html)
- 结论依据:原文在求解对偶问题时明确"一般采用的是 SMO 算法"并声明不展开;本卡据此补充 SMO 为何成对更新与如何迭代的通用解释,不涉及原书未给的具体公式。
- 原始内容:求解上面的优化问题时,原则上可以使用各种合适的优化方法,但一般采用的是SMO算法,感兴趣的读者可以自己查阅相关资料,这里不展开讨论。