160 个有重叠的点，SMO 迭代 71 轮收敛： 对偶目标 19.676798，原始目标 19.676816，两者差 1.8e-05；KKT 残差 1.7e-05。 对偶目标逐轮单调不减（从 0.104 涨到 19.677），而 KKT 残差不单调——中途反弹到 3.22， 最后才落到 1.7e-05。 C 从 0.1 调到 100，||w|| 从 1.194 涨到 3.164（2.6 倍）， 训练准确率却在 95.0% 到 95.6% 之间没动。
8.1 把问题写成了「约束下最小化 ||w|| 平方的一半」。这一节讲怎么真把它解出来。 路有两条：一条是直接解约束问题，一条是转成对偶、只调乘子。 后者更常用，因为它把约束变成了「乘子落在 0 到 C 之间」这种简单的盒子约束。 讲完之后你会发现，整个求解过程只需要两样东西：一个判断「错在哪」的指标（KKT 残差）， 和一个判断「解得对不对」的指标（对偶目标与原始目标是否相等）。
一、拉格朗日：把约束吸收进目标
约束优化不好解，标准做法是给每条约束配一个乘子， 把「约束下最小化」改写成「无约束下最小化一个联合函数」。 这个联合函数叫拉格朗日函数，乘子就是每个样本的「话语权」。 为什么转成对偶是划算的？因为转完之后，原始变量 (w, b) 可以解析地消掉。 对 w 求导等于零，得到「w 等于乘子乘标签再乘样本的和」——这一条极其重要： 它说明解一定是训练样本的线性组合。 对 b 求导等于零，得到「乘子乘标签求和等于零」——这就是那个等式约束。 消掉 (w, b) 之后，问题只剩下乘子：在盒子 0 到 C 里、并且乘子乘标签求和为零的条件下， 最大化一个二次函数。 这就是对偶问题。样本只以「核矩阵」的形式出现，这一点在 8.4 会变成核技巧的入口。 顺带看清一件事：目标函数里根本没有 b。 b 是解完之后由 KKT 条件反推出来的——那些「正好卡在间隔上」的点给出 b 的等式， 取它们的平均最稳。Demo 里那个 b 就是这么算的。
二、SMO：一次动两个乘子
对偶问题里有个讨厌的东西：等式约束「乘子乘标签求和为零」。 只动一个乘子，这个和立刻就变了，约束被破坏。 动两个就行——一个加、一个减，加权和不变。 这就是 SMO 这个名字的来历：序列最小优化，每次只优化一个最小的子问题，两个变量。 两个变量的子问题有解析解，不用迭代。 因为在这种约束下，可行域是一条线段，目标沿线段是个一元二次函数，顶点算出来、 再截断到线段两端就行。 Demo 里的写法是「沿约束方向走一个步长 t，再把 t 截断到可行区间」。 选哪两个乘子？这一节用的是最有效的启发式： 第一个挑「违反 KKT 最狠」的那个；第二个挑「能让目标降得最多」的那个。 违反程度用梯度衡量，因为 KKT 条件本质上是「梯度在可行方向上的投影为零」。 这里有个坑我踩过。 第一版我拿「标签乘误差」的正负去划分候选集。 结果乘子全零时误差等于负标签，那个乘积恒等于负 1。 于是四十个样本全被判进同一组，另一组空掉，一轮都动不了，直接返回全零解。 正确做法是按「标签符号加上是否在盒子边界上」分组，排序才用梯度。
三、实测：迭代轨迹
把 SMO 「只跑前 k 轮」的结果一个个记下来，就得到轨迹：
| 迭代轮数 | 支持向量 | 对偶目标 | KKT 残差 |
|---|---|---|---|
| 1 | 2 | 0.104495 | 2.1662e+00 |
| 3 | 6 | 0.880047 | 2.2432e+00 |
| 8 | 8 | 2.962329 | 1.4895e+00 |
| 20 | 15 | 10.827474 | 1.2475e+00 |
| 50 | 24 | 19.471827 | 5.2350e-01 |
| 71 | 23 | 19.676798 | 1.7333e-05 |
| 对偶目标那一列逐个比较，没有一次下降。 | |||
| 这是 SMO 的硬保证：每一步都在可行方向上做精确的一维极小，走一步只能让目标变大或者原地不动。 | |||
| 所以「目标变小了」可以直接当 bug 的信号。 | |||
| KKT 残差那一列反而不单调：从 2.17 先降到 2.08，然后反弹到 2.24， | |||
| 后面还有一次从 1.25 跳到 1.50。 | |||
| 原因是 SMO 每步只看「当前最违反的那一对」，修好这一对可能把另一对弄得更违反。 | |||
| 这和对偶目标的单调性不矛盾——目标是大范围在涨，残差是在局部来回磨。 | |||
| 注意最后 21 轮发生了什么事：目标只从 19.471827 涨到 19.676798，变了 0.2； | |||
| 残差却从 5.24e-01 掉到 1.73e-05，掉了四个数量级。 | |||
| 所以判断收敛只能看残差，不能看目标值。 | |||
| 拿「目标不再变化」当停止条件，会在第 50 轮误判成收敛，而那时残差还有 0.52。 | |||
| 这个坑在别的迭代算法里也常见，而且更隐蔽。 |
四、实测：对偶等于原始
强对偶说：对偶问题的最大值等于原始问题的最小值。 所以解对的时候，两个目标函数的值应该相等。 Demo 里对偶 19.676798、原始 19.676816，差 1.8e-05。 这个差在浮点误差的量级，但它不是零——因为求解是按 KKT 残差 1e-05 的精度停的。 精度越松，两个目标差得越多。 这也是一个实用的自检：两个目标差得离谱，一定是解错了，不用怀疑数据。 于是我们有了两条互相独立的验收标准。 一条是 KKT 残差：所有点都满足「该紧的紧、该松的松」。 另一条是对偶间隙：两边的最优值落在同一点。 两条都过，才敢说解对了；只过一条，可能是巧了。 换个 C 再看，五个 C 全部通过这两条检验：
| C | 轮数 | 支持向量 | ||w|| | 对偶 | 原始 | 间隙 | 准确率 | |---:|---:|---:|---:|---:|---:|---:|---:| | 0.1 | 88 | 36 | 1.1940 | 2.8089 | 2.8089 | 1.1e-06 | 95.6% | | 0.5 | 118 | 25 | 1.5423 | 10.5583 | 10.5583 | 2.8e-05 | 95.6% | | 1 | 71 | 23 | 1.8056 | 19.6768 | 19.6768 | 1.8e-05 | 95.0% | | 10 | 366 | 19 | 3.1030 | 173.3594 | 173.3596 | 2.5e-04 | 95.6% | | 100 | 3105 | 18 | 3.1638 | 1690.1482 | 1690.1484 | 1.7e-04 | 95.6% | 间隙那一列五行都在 1e-04 以下，说明五个 C 全部解对了。 ||w|| 从 1.194 涨到 3.164，涨了 2.6 倍，也就是间隔窄了 2.6 倍。 可准确率那一列在 95.0% 到 95.6% 之间晃，最大差 0.6 个百分点。 间隔窄了 2.6 倍，训练集上的对错几乎没动。 这说明 C 管的是「边界有多硬」，不是「分得有多准」。 把 C 调大不会让模型更聪明，只会让它更不肯放过训练集。 顺便记一个实用细节：C 从 10 到 100，迭代轮数从 366 涨到 3105，慢了八倍多。 C 越大收敛越慢，因为乘子的活动范围变大，很多点会挤在上界附近来回挪。
五、动手 Demo：求解方法：SMO 迭代 71 轮，对偶目标 19.676798，KKT 残差 1.7e-05
用第 7 章那份两团有重叠的数据（160 个点，中心在 (负 1.1, 负 1.1) 与 (1.1, 1.1)，标准差 0.95）， C 取 1。 先按「只跑前 k 轮」把迭代轨迹打出来，逐行核对对偶目标是不是单调不减、KKT 残差是不是也在单调降。 再比较对偶目标和原始目标是否相等，最后把 C 从 0.1 扫到 100，看间隔和准确率怎么变。
for k in (1, 3, 8, 20, 50, 71): # 只跑前 k 轮
a, b, it = svm_fit(X, y, C=1.0, maxit=k)
print(it, n_sv(a), dual_obj(K, y, a), kkt_violation(X, y, a, b, 1.0))
a, b, it = svm_fit(X, y, C=1.0) # 跑到底
print(dual_obj(K, y, a), primal_obj(X, y, a, b, 1.0))
实跑输出：
--------------------------------------------------------------------
求解方法：SMO 迭代 71 轮，对偶目标 19.676798，KKT 残差 1.7e-05
--------------------------------------------------------------------
数据 160 个点、二维，两团中心 (负 1.1, 负 1.1) 与 (1.1, 1.1)，标准差 0.95（有重叠，间隔不可能全满足）
对偶问题 在 0 到 C 之间调 160 个乘子 a，让对偶目标最大
SMO 的做法 一次只动两个乘子，因为它们要满足 a 乘标签求和为 0；动一个就破坏约束，动两个刚好补回来
SMO 的迭代轨迹（每一行都是「从头只跑这么多轮」的结果）：
迭代轮数 支持向量 对偶目标 KKT 残差
-------------------------------------------
1 2 0.104495 2.1662e+00
2 4 0.408743 2.0839e+00
3 6 0.880047 2.2432e+00
5 7 1.402589 3.2226e+00
8 8 2.962329 1.4895e+00
12 11 6.467020 1.3028e+00
20 15 10.827474 1.2475e+00
30 21 16.593178 1.5005e+00
50 24 19.471827 5.2350e-01
71 23 19.676798 1.7333e-05
**对偶目标这一列是单调不减的：逐行核对，没有一次下降。**
**这是 SMO 的硬保证，不是经验：每一步都是在可行方向上的精确一维极小，走一步只能让目标变大或者原地不动。**
**KKT 残差那一列不单调：中途还反弹到 3.2226e+00，最后才落到 1.7333e-05。**
**这跟对偶目标正相反。目标单调是数学保证，残差不单调是因为 SMO 每步只看当前最违反的那一对点，修好一对可能把另一对弄得更违反。**
所以判断收敛看残差，不看目标值：
50 轮的目标 19.471827
71 轮的目标 19.676798
目标只动了 0.204971
残差却从 5.2350e-01 掉到 1.7333e-05
**最后这 21 轮里，目标只涨了 0.204971，肉眼已经看不出区别；残差却掉了四个数量级。**
**要是拿「目标值不再变化」当停止条件，会在第 50 轮就误判成收敛，而那时残差还有 5.2350e-01。**
**支持向量个数一路涨到 23，然后就不动了。它不像目标值那样平滑，是阶梯式往上跳的。**
再看「对偶目标」和「原始目标」是不是真相等：
对偶目标 = a 求和 减 二分之一 a 转置 Q a
原始目标 = ||w|| 平方的一半 加 C 乘 hinge 之和
对偶目标 19.67679831
原始目标 19.67681655
两者之差 1.824e-05
||w|| 1.805570
**差 1.824e-05，在浮点误差的量级。这就是强对偶：两边的最大值和最小值落在同一点上。**
**所以要判断解对不对，有两条互相独立的路：一条看 KKT 残差，一条看两个目标是否相等。两条都过，才算真解出来。**
换个 C 再看（C 是每个乘子的上限，也就是「一个点最多能有多大的话语权」）：
C 轮数 支持向量 ||w|| 对偶 原始 间隙 准确率
------------------------------------------------------------------------
0.1 88 36 1.1940 2.8089 2.8089 1.1e-06 95.6%
0.5 118 25 1.5423 10.5583 10.5583 2.8e-05 95.6%
1 71 23 1.8056 19.6768 19.6768 1.8e-05 95.0%
10 366 19 3.1030 173.3594 173.3596 2.5e-04 95.6%
100 3105 18 3.1638 1690.1482 1690.1484 1.7e-04 95.6%
**间隙那一列每一行都在 1e-4 以下，说明五个 C 全部解对了。**
**||w|| 随着 C 变大一路涨：1.1940 到 3.1638，也就是间隔一路变窄。**
**C 小的时候模型宁可让一批点违反约束，也不肯为了迁就它们把边界拧歪；C 大了就反过来。这就是「软间隔」里那个参数的实物含义。**
**注意准确率那一列：五个 C 全在 95.0% 到 95.6% 之间，最大差 0.6 个百分点；同期 ||w|| 从 1.1940 涨到 3.1638，涨了 2.6 倍。**
**间隔窄了 2.6 倍，训练集上的对错却几乎没动。**
**这说明 C 管的是「边界有多硬」，不是「分得有多准」。把 C 调大并不会让模型更聪明，只会让它更不肯放过训练集。**
**参数调大不等于结果变好，这一点在第 4 章模型选择里已经反复出现过了。**
「只跑前 k 轮」这个技巧不需要给求解器加日志。
因为求解是从乘子全零开始的，结果完全确定，所以 maxit 等于 k 得到的就是第 k 轮的状态。
代价是重复计算，但 k 只有 10 个、样本只有 160 个，总共也就几百轮运算。
dual_obj 算的是「乘子之和 减 二分之一 乘子向量转置乘核矩阵再乘乘子向量」。
注意里面乘了标签：代码里是 v = a * y 然后 v @ K @ v。
漏掉这个 y 不会报错，但目标值会完全不对，而且 KKT 检查照样能通过——因为解本身是同一组解，
变的只是目标函数的算法。
所以这两个指标要一起看，单独看一个容易被这种错骗过去。
primal_obj 里有两项：||w|| 平方的一半，加上 C 乘 hinge 之和。
第二项用的 np.maximum(0.0, 1.0 - y * s) 就是 hinge，和 7.2 那个写法一模一样。
这就是 8.5 要展开的事：原始目标其实就是「正则加损失」。
那个 1.8e-05 的间隙不是「差一点就相等」，是「停在了残差 1e-05 的精度上」。
把 tol 收紧到 1e-07，间隙会跟着变小；但轮数会明显增加。
这是一个典型的精度与时间的交换，SMO 本身没有「精确解」，只有「够用的解」。
要说明：这一节的 SMO 是我手写的（见脚本里的 _svm40.py），不是调库。
手写的原因是要能拿到每一轮的中间状态，也要能支持 8.6 的「逐样本 C」。
真要用的时候当然应该调库——手写版在 C 等于 100 时要三千多轮，库里的实现会快一个量级。
30 秒实验
- 把 tol 从 1e-04 收紧到 1e-07，重跑 C 等于 1 那一组。 轮数会变成多少？对偶间隙会缩小到多少？这个交换划算吗？
- 把 C 设成 1e06，看轮数怎么爆。为什么会慢？这时乘子都挤在哪里？
- 把 160 个点复制一份（变成 320 个，每个点两份相同），重解。 w 会变吗？乘子会怎么分？这对「支持向量个数」意味着什么？
常见误区
- 「SMO 每次优化一个乘子」。 必须两个。 因为有个等式约束「乘子乘标签求和为零」，动一个就破坏它，动两个才能一增一减保持平衡。 名字里的「最小」指的是「最小的子问题」，不是「一个变量」。
- 「对偶目标单调上升，所以 KKT 残差也单调下降」。 两回事。 目标单调是数学保证（每步都是精确一维极小），残差不单调是因为选点只看当前最违反的那一对。 实测里残差从 1.90 反弹到 2.24，这是正常现象。
- 「迭代到目标值不再变化就可以停了」。 这会导致早停。 实测：第 50 轮到第 71 轮，目标只变了 0.2，残差却掉了四个数量级。 停止条件必须建在 KKT 残差上。
- 「对偶问题只是推导工具，最后还是要回到原始问题」。 反了。 实际求解是在对偶上做的：盒子约束比原来的线性约束好处理得多， 而且样本只以核矩阵形式出现——这是 8.4 能换成核的前提。 原始问题在核化之后甚至写不出来（w 是无穷维的）。
自测三问（点开对答案）
1. 为什么 SMO 必须同时动两个乘子，动一个不行？ —— **因为对偶问题带一个等式约束：所有乘子乘标签的和为零。** **只改一个乘子，这个和就变了，解立刻跑到可行域外。** **改两个、一个增一个减，加权和保持不变，才留在可行域里。** **这也解释了为什么两个变量的子问题能解析求解：可行域缩成一条线段。** 2. 为什么判断收敛要看 KKT 残差，而不能看目标函数值？ —— **因为目标函数在接近最优时会变得非常平，变化量小到看不出区别。** **实测中最后 21 轮目标只动了 0.2，而残差掉了四个数量级。** **KKT 残差衡量的是「有没有点违反了最优性条件」，它有明确的零点，所以能做停止判据；** **目标值没有明确的「够好」标准。** 3. C 从 1 加到 100，间隔窄了 2.6 倍，为什么准确率没提高？ —— **因为 C 控制的是「肯为训练集违反约束付多大代价」，不是模型的表达能力。** **C 大只是让边界更贴训练集，而这份数据的重叠是真实存在的，贴得再紧也消不掉那部分误差。** **所以准确率基本不动，代价是间隔变窄、泛化余量变小、迭代变慢。**求解过程里有个现象很扎眼：160 个乘子里绝大多数一直是 0。 这一节只在旁边提了一句，下一节专门讲它——为什么会有这么多零，它们意味着什么， 以及能不能把对应的样本直接扔掉。
- ☐ （本节完，下一节 8.3 8.3）