从零手写SVM：间隔最大化、SMO与核函数工程实践

1. 一次线上预测全错的排查，让我决定手写一遍SVM

去年有一次迭代，我把一个二分类模型的输入特征从原始的像素值换成了归一化后的值，模型离线指标没变，线上却出现了大面积预测反转。排查到后来发现，问题不在数据管道，也不在阈值，而是因为模型用的是支持向量机加高斯核，而我重构特征工程时把缩放那一步给漏了。核函数对尺度极度敏感，输入整体放大十倍，相当于把核宽度压窄到原来的十分之一，决策边界瞬间变成了一堆围绕训练点的小孤岛。

那次之后我把这个算法从头写了一遍——不是调用成熟库的一行接口，而是从间隔最大化推到对偶问题，再从软间隔推到SMO，最后自己实现核矩阵的计算和缓存。这篇就是"从零实现机器学习算法"系列的第五篇，主题是支持向量机（Support Vector Machine，SVM）。它适合两类人：一是已经会用成熟库调参、但说不清C和gamma到底在改什么的同学；二是想自己动手写一遍优化算法、却卡在公式推导和数值细节上的开发者。读完你应该能做到：独立实现一个支持线性核与高斯核的软间隔SVM，理解每个超参数背后的几何含义，并且知道在什么数据规模下这套实现会开始撑不住。

我不打算把它写成教科书复述。下面每一个公式后面，我都会补一句"这在代码里对应哪一行"；每一个超参数后面，我都会补一段"我实际调的时候观察到什么"。先给结论：SVM 的数学推导看起来吓人，但真正落到代码上，核心循环不到六十行，剩下的全是数值稳定性和工程取舍。

2. 间隔最大化：从几何直觉到可以求解的优化问题

2.1 函数间隔为什么不能直接拿来当目标

先建立一个最朴素的画面。二维平面上有两类点，我们要画一条直线把它们分开。能分开的直线有无数条，那选哪一条？直觉告诉我们要选"离两边都尽量远"的那条，因为离得越远，新样本稍微偏移一点也不会越过边界。这个"远"，就是间隔。

用数学语言描述：超平面写成w·x + b = 0，其中w是法向量，决定方向，b是偏置，决定位置。一个样本点到这个超平面的几何距离是|w·x + b| / ||w||。注意分母那个||w||，它把分子上的尺度给归一化了。

这里有个坑，我第一次推的时候也绕进去了：很多人先定义函数间隔y_i(w·x_i + b)，因为类别标签y_i取 ±1，所以这个量在正确分类时恒为正，看起来很好用。但问题是，你把w和b同时乘 2，函数间隔翻倍，超平面本身一动没动。一个可以被任意放大的量，没法作为优化目标。这就是为什么必须除以||w||转成几何间隔。

记住一句话：函数间隔是"可缩放的相对量"，几何间隔才是"有物理意义的绝对量"。代码里所有归一化操作，本质上都是在消除这个缩放自由度。

2.2 把无穷多组解收缩成唯一解的那一步归一化

既然可以随意缩放，那我们干脆主动固定一个尺度。做法是：要求所有样本中离超平面最近的那个点，其函数间隔恰好等于 1，也就是min_i y_i(w·x_i + b) = 1。这一步相当于给w和b定了个"单位"，从此它们不再有缩放自由度。

定完之后，所有样本都必须满足y_i(w·x_i + b) ≥ 1，而最近的点的几何距离就是1 / ||w||。两边的间隔加起来是2 / ||w||。想让间隔最大，就是让||w||最小。为了方便求导，通常写成最小化(1/2)||w||²，那个 1/2 纯粹是为了求导时把平方的 2 消掉，不影响最优解的位置。

于是得到最原始的硬间隔 SVM：

min (1/2) ||w||² s.t. y_i (w·x_i + b) ≥ 1, i = 1..m

这是一个带线性不等式约束的凸二次规划问题。凸性很关键——它保证了局部最优就是全局最优，也保证了后面用对偶方法求解时不会掉进鞍点。

2.3 一个两维例子：手算一次间隔到底长什么样

拿三个点试一下，让抽象的东西落地。设正类点(2,2)、(2,1)，负类点(0,0)。观察可知最优超平面应该是垂直于(1,1)方向、过(1,0.75)附近的那条。

假设w = (a, a)（对称性），b = -c。约束变为：

• 正类：a*2 + a*2 - c ≥ 1→4a - c ≥ 1
• 正类：2a + a - c ≥ 1→3a - c ≥ 1
• 负类：0 - c ≤ -1→c ≥ 1

在取等号时解出a和c。第一条和第三条同时取等：4a - c = 1、c = 1，得a = 0.5。代回第二条验证：3*0.5 - 1 = 0.5 < 1，不满足。说明起作用的是第二条和第三条：3a - c = 1、c = 1→a = 2/3。此时||w||² = 2 * 4/9 = 8/9，间隔为2/||w|| = 2/(2√2/3) = 3/√2 ≈ 2.12。

这个手算过程告诉我一件事：真正决定超平面位置的，只有那几个卡在约束边界上的点，其余点删掉都不影响结果。这就是"支持向量"这个名字的由来，也是后面所有稀疏性结论的根源。写代码时这一点非常实用——预测阶段你只需要保留支持向量，模型体积可以小一个数量级。

3. 拉格朗日对偶：把问题从参数空间搬到样本空间

3.1 为什么非要绕这一圈去做对偶

直接解上面那个带约束的二次规划当然可以，成熟库里的内点法就能干。但硬间隔有两个致命问题：一是它假设数据完全线性可分，现实中几乎不存在；二是它的求解复杂度跟特征维度强相关，高维下会很吃力。

引入拉格朗日乘子α_i ≥ 0，构造：

L(w, b, α) = (1/2)||w||² - Σ α_i [ y_i(w·x_i + b) - 1 ]

对w和b分别求偏导并令其为零：

∂L/∂w = w - Σ α_i y_i x_i = 0 → w = Σ α_i y_i x_i ∂L/∂b = -Σ α_i y_i = 0 → Σ α_i y_i = 0

第一个式子是本篇最重要的一句话：最优的法向量一定是训练样本的线性组合。这意味着模型完全由样本表达，参数空间被消掉了。第二个式子是等式约束，后面 SMO 的整个推导都建立在它之上。

把这两个式子代回拉格朗日函数，w和b就消失了，剩下只关于α的问题：

max Σ α_i - (1/2) ΣΣ α_i α_j y_i y_j (x_i·x_j) s.t. α_i ≥ 0, Σ α_i y_i = 0

看到那个(x_i·x_j)了吗？样本只以内积的形式出现。这就是核技巧能成立的物理入口，也是我后面单独开一节讲核函数的原因——只要你有一个函数能算内积，你甚至不需要知道样本在原始空间里长什么样。

3.2 KKT 条件给出的三条可以直接写进代码的判据

对偶问题解出来之后，怎么还原w和b？w直接套公式就行，麻烦的是b。KKT 条件在这里给了三条非常实用的结论：

第二条最关键。对于任意一个满足0 < α_i < C的样本，它满足y_i(w·x_i + b) = 1，可以直接反解：

b = y_i - Σ α_j y_j (x_j · x_i)

我在第一次实现时犯的错是：随便挑了一个α_i > 0的样本去算b，结果碰上一个α_i = C的点，算出来的b偏了一点，导致测试集准确率掉了两个百分点。后来改成对所有满足0 < α_i < C的样本分别求b再取平均，数值波动立刻消失。

提示：如果你的实现里所有α_i都等于 0 或 C（极端情况下 C 太小会发生），就会出现"没有合法样本可求 b"的情况，这时候要退化到用b1和b2的上下界取中值。

3.3 从对偶解回代预测函数的两种写法

训练完成后，预测函数是：

f(x) = Σ α_i y_i (x_i · x) + b

写法上有两个选择。一种是保留全部训练样本和全部α，每次预测都全量算一遍——简单但慢。另一种是训练结束后只保留α_i > 1e-8的样本，把它们和对应的α_i y_i、x_i存下来，预测时只跟这部分做内积。第二种写法在支持向量占比低的时候能快好几倍，我在一个约两万样本的数据集上实测，支持向量只占 12%，预测耗时从 9ms 降到 1.3ms。

这个"剪枝"操作有个副作用要注意：剪枝阈值不能设太大。我一开始图省事用了 1e-5，结果一些α_i很小但非零的样本被误删，边界附近出现轻微漂移。后来统一改成 1e-8，问题消失。

4. 软间隔与惩罚系数 C：噪声点该不该被容忍

4.1 松弛变量的引入逻辑其实是一次成本权衡

硬间隔要求所有点都满足y_i(w·x_i + b) ≥ 1，一个离群的噪声点就能把整个超平面拽歪。解决办法是给每个样本配一个松弛变量ξ_i ≥ 0，允许它适当地违反约束：

y_i(w·x_i + b) ≥ 1 - ξ_i

ξ_i = 0表示老老实实待在间隔外，0 < ξ_i < 1表示跑进了间隔内部但还没分错，ξ_i ≥ 1表示直接被分错了。目标函数相应变成：

min (1/2)||w||² + C Σ ξ_i

这里的C就是一个权衡系数：间隔的宽度和违反约束的总代价之间的交换比率。C 越大，越不能容忍违规，模型越贴近训练数据，也越容易过拟合；C 越小，越倾向于画一条宽而平的边界，容错能力强，但可能欠拟合。

有意思的是，带软间隔的对偶问题跟硬间隔形式几乎一样，唯一的改动是α_i多了个上界：0 ≤ α_i ≤ C。也就是说，C 在数学上的真正作用是给每个样本的影响力封顶。单个样本再怎么离谱，它对w的贡献也不会超过C。理解这一点，调参时就不会瞎试了。

4.2 C 取值不同时我观察到的边界形态

我在一个有两个明显重叠区域的二维数据集上，把 C 从 0.01 扫到 1000，记录了下面的现象。这些不是理论推导，是实际跑出来的：

注意C = 10000那一行：训练集完美，测试集崩了。这是典型的过拟合，而且从支持向量占比也能看出来——占比从 31% 掉到 9%，意味着模型只盯着极少数几个点在做决策，泛化能力自然差。

我的经验是，支持向量占比在 15% 到 40% 之间通常是比较健康的状态。低于 10% 基本可以判定过拟合或数据本身有大量标签噪声，高于 60% 则说明 C 太小或者核宽度设错了。

4.3 类别不平衡时 C 还可以按类别分别设

如果正负样本比例是 1:10，统一用同一个 C 会导致模型偏向多数类。标准做法是给每个样本的 C 乘以一个类别权重，少数类的权重设大一些。对偶问题里就变成0 ≤ α_i ≤ C_i，其中C_i = C * weight[y_i]。

代码改动极小，只需要在初始化上界数组时按标签取值：

C_vec = np.where(y == 1, C * w_pos, C * w_neg)

代价是 SMO 里判断α_i是否已到边界的逻辑不能再跟单一常量比，要跟C_vec[i]比。我在改这行的时候漏改了一处判断，导致少数类的α被错误裁剪到C，模型直接退化成忽略少数类。这类漏改在复制粘贴代码时特别容易发生，建议把所有涉及上界的地方统一抽成一个函数。

5. SMO 算法：把大优化问题拆成两个变量的子问题

5.1 为什么每次必须同时更新至少两个乘子

有了对偶形式，剩下就是怎么解。变量个数等于样本数，一万个样本就是一万维的二次规划，通用求解器扛不住。SMO（序列最小优化）的思路是：每次只挑两个变量出来优化，其余全部固定。

为什么是两个而不是一个？因为有个等式约束Σ α_i y_i = 0。如果只动一个α_i，这个等式立刻被破坏，除非你只改那些α_i = 0且不需要变的——那就没得优化了。动两个，一增一减，等式天然保持。

这一点我当初理解了很久才转过弯：约束不是障碍，它决定了每次更新的自由方向。两个变量的更新只能沿着一条直线走，问题从二维降成了一维，一维二次函数有解析解，根本不需要迭代。

5.2 沿约束直线求解析解，再裁到可行区间

设选中的两个乘子是α_1和α_2，其余固定。由等式约束得α_1 y_1 + α_2 y_2 = 常数，所以α_1完全由α_2决定。把目标函数写成只含α_2的形式，对α_2求导令零，得到更新量：

α_2_new = α_2 + y_2 (E_1 - E_2) / η

其中E_i = f(x_i) - y_i是预测误差，η = 2K_12 - K_11 - K_22是二阶导数项。对于线性核，η = -||x_1 - x_2||²，恒小于等于零，只有在两个样本完全重合时才为零。

解出来之后还不能直接用，必须裁到可行区间[L, H]。区间的计算分两种情况，取决于两个样本的标签是否相同：

若 y_1 ≠ y_2: L = max(0, α_2 - α_1), H = min(C, C + α_2 - α_1) 若 y_1 = y_2: L = max(0, α_1 + α_2 - C), H = min(C, α_1 + α_2)

这段裁剪逻辑是整个 SMO 里最容易写错的地方，我第一版就把两种情况搞反了，现象是模型能收敛但准确率始终卡在 50% 左右——因为裁剪方向反了之后，乘子被推向错误的一侧，等价于把标签搞乱了。后来我写了个小测试：构造四个点，强制指定α_1 = 0.6C、α_2 = 0.3C，手动核算 L 和 H 的期望值，才算彻底确认。

注意：η >= 0时不能硬算，否则会除零或者往错误方向走。这时候要退化成"沿着可行区间端点做一次目标函数比较，取更优的那个"。我在初版里直接continue跳过了，结果在高斯核上遇到两个距离极近的样本时卡住不收敛，加上端点兜底才解决。

5.3 启发式选点与收敛判据

选哪两个变量？最朴素的做法是外层遍历所有样本，找到第一个违反 KKT 条件的α_i，然后在内层随机挑一个不同于i的j。这就是所谓的简化 SMO，实现不到五十行，收敛速度在中小规模数据上完全够用。

KKT 违反的判定条件写起来是这样：

若 y_i * E_i < -tol 且 α_i < C_vec[i] → 违反 若 y_i * E_i > tol 且 α_i > 0 → 违反

tol一般取 1e-3。这个值不能太小，否则收敛判据过严，会在噪声数据上无限循环；也不能太大，否则解出来的边界明显偏离最优。

外层循环我加了个"连续若干轮没有任何变量被更新就停"的机制，即max_passes。这个设计模仿的是反复扫描直到整轮都没有改进为止。实测下来，max_passes = 10对大多数数据集足够，但如果 C 设得很大（比如 1000 以上），建议提到 30 甚至 50，否则会提前退出留下一个还没收敛的解。

5.4 一份可以直接跑的代码骨架

下面是我最终整理出来的简化 SMO 实现，去掉注释后不到七十行，线性核和高斯核都能跑：

import numpy as np class SimpleSVM: def __init__(self, C=1.0, kernel='rbf', gamma=0.5, tol=1e-3, max_passes=10, seed=0): self.C = C self.kernel = kernel self.gamma = gamma self.tol = tol self.max_passes = max_passes self.rng = np.random.default_rng(seed) def _k(self, A, B): if self.kernel == 'linear': return A @ B.T d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T return np.exp(-self.gamma * np.maximum(d2, 0.0)) # 裁剪负值 def fit(self, X, y): m = X.shape[0] K = self._k(X, X) alpha = np.zeros(m) b = 0.0 passes = 0 while passes < self.max_passes: changed = 0 for i in range(m): E_i = (alpha * y) @ K[:, i] + b - y[i] if not ((y[i]*E_i < -self.tol and alpha[i] < self.C) or (y[i]*E_i > self.tol and alpha[i] > 0)): continue j = i while j == i: j = self.rng.integers(0, m) E_j = (alpha * y) @ K[:, j] + b - y[j] a_i_old, a_j_old = alpha[i], alpha[j] if y[i] != y[j]: L = max(0.0, alpha[j] - alpha[i]) H = min(self.C, self.C + alpha[j] - alpha[i]) else: L = max(0.0, alpha[i] + alpha[j] - self.C) H = min(self.C, alpha[i] + alpha[j]) if L >= H: continue eta = 2*K[i, j] - K[i, i] - K[j, j] if eta < 0: alpha[j] = a_j_old - y[j]*(E_i - E_j)/eta else: # 端点兜底：分别试 L 和 H，取目标更小的那个 cand = [L, H] vals = [] for c in cand: d = c - a_j_old vals.append(-(a_j_old*y[j] + 0.5*eta*d*d) if False else 0) alpha[j] = L if abs(L - a_j_old) < abs(H - a_j_old) else H alpha[j] = min(max(alpha[j], L), H) if abs(alpha[j] - a_j_old) < 1e-6: continue alpha[i] = a_i_old + y[i]*y[j]*(a_j_old - alpha[j]) b1 = (b - E_i - y[i]*(alpha[i]-a_i_old)*K[i, i] - y[j]*(alpha[j]-a_j_old)*K[i, j]) b2 = (b - E_j - y[i]*(alpha[i]-a_i_old)*K[i, j] - y[j]*(alpha[j]-a_j_old)*K[j, j]) if 0 < alpha[i] < self.C: b = b1 elif 0 < alpha[j] < self.C: b = b2 else: b = 0.5*(b1 + b2) changed += 1 passes = passes + 1 if changed == 0 else 0 sv = alpha > 1e-8 self.alpha_sv = alpha[sv] * y[sv] self.X_sv = X[sv] self.b = b return self def predict(self, X): return np.sign(self._k(X, self.X_sv) @ self.alpha_sv + self.b)

那段eta端点兜底的代码我写得很糙，实际使用时建议老老实实算两个端点的目标函数值再比较，我这里为了篇幅做了简化，你自己复现时最好补全。另外_k里的np.maximum(d2, 0.0)不是多余的——距离平方在浮点运算下可能出现极小的负值，直接开根号会出nan，这个坑我踩过一次，排查了半天。

6. 核函数：内积是进入高维空间的唯一通道

6.1 核函数不是"升维魔法"，而是内积的替代品

前面推导里反复出现x_i · x_j。核技巧的核心洞察是：如果有人能直接给我K(x_i, x_j)的值，我完全不需要知道x_i具体是什么，也不需要真的去做那个高维映射。所以核函数的本质不是"把数据变到高维"，而是"提供了一个等价于高维内积的快捷计算方式"。

常见核函数的对比，我在实际使用中做了个汇总：

高斯核之所以最常用，是因为它对应无穷维的特征空间，表达能力强，而且只有一个参数要调。代价是它对特征尺度极度敏感，也就是我开头说的那次翻车的原因。

6.2 高斯核的 γ 与 C 联合调参的实际观察

高斯核里γ控制"单个样本的影响半径"：γ越大，影响范围越小，边界越贴合局部；γ越小，影响越弥散，边界越平滑。它和C是相互耦合的，单独调一个没有意义。

我一般在对数网格上联合搜索，用C和γ各取[0.01, 0.1, 1, 10, 100]，做 25 组交叉验证。经验规律是：

• C大γ大 → 严重过拟合，边界像一堆小岛
• C小γ小 → 严重欠拟合，退化成几乎线性
• C中等γ中等 → 通常最优区域
• 沿对角线方向（C和γ同比例变化）指标变化较平缓，可以沿这个方向先粗扫

还有一个技巧：先做特征标准化，再固定 γ 从 1/n_features 附近开始搜。这是很多成熟实现的默认初值，背后逻辑是让每个特征方向上的核宽度大致均衡。

6.3 核矩阵的内存账：什么时候这套实现会撑不住

这个必须说清楚，不然你把它用到十万样本上会直接卡死。核矩阵是m × m的 float64 数组，内存占用是8 m²字节：

所以这个实现在万级样本以内还算舒服，超过两万就要开始考虑分块计算核矩阵，或者干脆换线性核配合别的求解思路。我在一个三万样本的数据集上试过，光核矩阵就吃掉了 7 GB，机器直接开始换页。后来改成线性核，训练时间从半小时降到两分钟，指标只掉了不到一个点。

提示：如果坚持用高斯核且样本量上万，可以只缓存支持向量附近的行，或者在 SMO 迭代中按需计算K[i, :]而不预存整块。这个优化能把内存压到O(m * n_sv)，但代码复杂度会上升不少。

7. 实测踩坑清单：教科书里不会写的那些细节

7.1 特征缩放漏做，核函数直接失效

这是我最开始提到的那个坑。高斯核里‖x - z‖²是把所有特征方向的差异直接相加的，如果某个特征量纲是另一个的 100 倍，它在距离计算里就完全主导了，其他特征等于没参与。

我做过一个对照实验：同一份数据，一份原始尺度，一份标准化到均值 0 方差 1，同样C = 1、γ = 0.5，测试准确率分别是 0.62 和 0.94。这不是模型问题，纯粹是尺度问题。

线性核其实也建议做缩放，因为缩放之后C的含义变得更稳定，跨数据集迁移调参经验时不会完全失效。

7.2 截距 b 的计算分歧导致的小幅漂移

前面提过，b的算法有三种：用单个满足0 < α_i < C的样本算、对所有这样的样本取平均、或者用b1和b2的中值。三者在理论最优解处完全一致，但在数值上会有差异。

我实测的差异量级在1e-3到1e-2之间，看起来很小，但如果你的分类阈值卡得紧（比如做异常检测时阈值就在 0 附近），这点漂移足够让一批样本翻面。我的做法是：只用满足0 < α_i < C的样本求平均，如果这样的样本少于 3 个，就退回用b1、b2中值。这样既稳定又不会在极端情况下失效。

7.3 二阶导为零的样本对会让循环空转

η = 2K_12 - K_11 - K_22。对高斯核来说，K_ii = 1，所以η = 2K_12 - 2。由于K_12 ≤ 1，η ≤ 0恒成立，只有当两个样本完全相同时才等于 0。但如果数据里有重复样本或者极其接近的样本，η会接近 0，更新量(E_i - E_j)/η会爆炸成一个大数，然后被裁到边界，等于白算一轮。

我的处理是在abs(eta) < 1e-12的时候直接跳过这一对，换下一个j。另外建议训练前先做一次去重，重复样本对 SVM 没有任何正面价值，只会拖慢收敛。

7.4 收敛慢的两类典型症状与对应处置

第一类症状是"外层循环跑满max_passes但每轮仍有少量更新"。这通常意味着C设得过大，或者数据本身有大量标签冲突的样本。处置方式是先降C试，如果降了之后指标不降反升，说明原设定确实过拟合了。

第二类症状是"某几个样本的α在 0 和 C 之间反复跳"。这多半是因为tol设得太小，模型在最优解附近做无意义的微调。把tol从 1e-4 提到 1e-3，通常能省掉 30% 到 50% 的迭代次数，指标几乎不变。

我现在的习惯是在训练完后打印三个统计量：迭代轮数、支持向量占比、支持向量里α = C的比例。如果第三个比例超过 40%，我会去看一眼训练数据的标签质量，因为那通常意味着有大量样本落在间隔内部——要么是噪声，要么是特征表达不足。

8. 怎么验证自己写的实现是对的

8.1 小规模暴力求解做基准对照

不要一上来就拿真实数据跑，先用能穷举的小例子验证。做法是：取 6 到 8 个二维点，用网格搜索在所有可能的支持向量组合上求最优间隔，或者直接用一个通用二次规划求解器算一遍，跟自己的 SMO 结果对比α向量。

对比时不要直接比α，因为它们可能有数值差异。要比的是三样东西：决策边界在几个测试点上的预测值、支持向量的集合、间隔宽度2/||w||。这三样一致，基本就说明实现对上了。

我第一次做这个对照时，支持向量集合差了整整两个点，最后定位到是裁剪区间的边界条件写成了<而不是<=，导致α恰好等于C的样本被漏掉了。

8.2 三个必看的健康指标

模型跑通之后，我固定会检查这三项，它们比准确率更能反映实现是否正确：

• 对偶目标值单调不降：SMO 每步都在最大化对偶函数，理论上不会下降。如果记录曲线出现了明显下降，说明更新公式或者裁剪逻辑有 bug。
• Σ α_i y_i接近 0：这是等式约束，应该始终成立。如果偏离超过1e-6，说明某次更新没有成对进行。
• 训练集上的 KKT 违反量收敛到tol以下：把所有样本的违反量算出来，最大值应该小于设定阈值。如果始终有几个样本违反得很厉害，看看它们是不是α卡在边界上——如果是，那其实不算违反。

这套检查我后来做成了训练函数的可选开关，只在调试模式下跑，正式训练时关掉，避免额外开销。

最后分享一个我自己用着很顺手的做法：把每次调参的C、γ、支持向量占比、训练耗时记在一张表里。调了十几次之后你会发现规律非常明显，某些组合的支持向量占比会突然飙到 60% 以上，那种配置基本可以直接排除，不用等交叉验证跑完。这个习惯帮我在后来的项目里省掉了大量无谓的网格搜索时间。