手写SMO算法：SVM训练核心实现与调参实战

SMO算法是SVM训练里绕不开的一块硬骨头。很多教程能把公式推得明明白白，但真正落到自己写代码实现时，坑一个接一个。这篇博文不讲教科书式推导，直接以“实现一个能跑的SMO”为目标，把Platt原始论文里的关键步骤拆开揉碎，配上完整的Python代码、实验对比和踩坑记录。写完你会知道：为什么SMO要拆成两个变量优化，启发式选择到底在选什么，KKT条件偏离多少才算“违反”，以及当训练卡死、不收敛、预测漂移时该怎么办。

1. 为什么SVM训练需要SMO

1.1 从对偶问题说起

SVM最终的分类决策函数只依赖支持向量，所以训练过程本质上是在找一组“最关键的样本”。数学上，SVM的训练被写成求解一个凸二次规划问题，对偶形式通常是：

最大化：∑ᵢ αᵢ - 1/2 ∑ᵢ∑ⱼ αᵢαⱼ yᵢyⱼ K(xᵢ, xⱼ) 约束：0 ≤ αᵢ ≤ C，且 ∑ᵢ αᵢyᵢ = 0

这里的 αᵢ 是拉格朗日乘子，K是核函数。这个问题的规模跟样本数n直接挂钩：n很小的时候，随便调个二次规划求解器都能搞定；但n一旦到几千、几万，直接求解的代价会迅速膨胀，内存和时间都扛不住。早期的SVM工具很多都要靠专门的优化库，训练速度慢，内存消耗大，很大程度上限制了SVM在真实场景里的落地。

1.2 SMO的破局思路

SMO（Sequential Minimal Optimization，序列最小优化）是Platt在1998年提出的一种求解SVM对偶问题的算法。它的核心思想很“暴力”：既然一次性优化所有变量很困难，那我每次只挑两个变量来优化，其他变量都固定住。因为SVM的对偶问题有一个线性等式约束 ∑αᵢyᵢ=0，所以一次至少要有两个变量才能保证更新后仍然满足约束。一次挑两个，就把原来的n维优化问题拆成了无数个二维子问题，而二维子问题是有解析解的。

这意味着SMO不再需要外部优化库，迭代过程可以完全用基础运算完成，而且每一步都能保证目标函数在下降。以我当时测试的数据规模来看，几千个样本、RBF核的情况下，纯Python实现也能在几分钟到十几分钟内收敛，如果用C或Cython重写核心循环，速度还能再上一个数量级。

1.3 SMO的代价与优势

代价在于：算法引入了许多工程细节，比如启发式选变量、缓存的维护、收敛阈值的选择、KKT条件的判断。这些细节直接决定了训练速度和稳定性。优势则非常明显：内存开销小，不需要存储完整的核矩阵；实现简单，几十行核心逻辑就能跑通一个小型数据集；在中小规模数据集上效果稳定，是初学者理解SVM训练机制的绝佳入口。

2. 动手之前：数据形式和核函数准备

2.1 数据格式与预处理

SMO的输入一般是一个n×d的特征矩阵X和一个长度为n的标签向量y。标签必须取+1和-1两类，不能是0和1。很多人第一次写的时候把标签写成{0,1}，后面KKT条件判断和梯度计算全会出错。我自己习惯在数据载入后立刻做一次标签映射，把负类变成-1，正类变成+1。

特征缩放这一步千万不能省。SVM对特征的尺度非常敏感，如果你有一个特征是0~1000，另一个是0~1，核函数里的欧氏距离会被大尺度特征主导，训练出来的模型基本等于只看了那个大尺度特征。我常用的做法是标准化到零均值单位方差，或者缩放到[-1,1]区间。对于文本TF-IDF这种本身已经做了归一化的特征，可以灵活处理，但依然建议检查一下分布。

2.2 核函数的定义与选择

SMO的核心计算全部集中在核函数K(xᵢ, xⱼ)上。最常用的三种：

• 线性核：K = xᵢ·xⱼ
• 多项式核：K = (γ·xᵢ·xⱼ + r)^d
• RBF径向基核：K = exp(-γ·||xᵢ-xⱼ||²)

我实战中90%以上的场景直接选RBF核。它对非线性边界有很强的拟合能力，参数只有一个γ，调起来相对容易。不过RBF核也有一个缺点：γ太大会过拟合，γ太小会欠拟合，后面我会专门讲怎么调。

核函数在SMO中会被反复调用无数次，所以性能很关键。朴素的Python写法在样本量到5000以上时会明显变慢。一个实用的优化是：把训练集的特征矩阵预先缓存成浮点数组，核函数内部用numpy向量化计算，避免for循环。如果核矩阵不大，也可以预先算好并缓存，省去后面每次计算的开销。

2.3 一条可参考的核函数实现

import numpy as np def linear_kernel(x1, x2): return np.dot(x1, x2) def rbf_kernel(x1, x2, gamma=0.5): diff = x1 - x2 return np.exp(-gamma * np.dot(diff, diff)) def build_kernel_function(kernel_type='rbf', gamma=0.5): if kernel_type == 'linear': return linear_kernel elif kernel_type == 'rbf': return lambda x1, x2: rbf_kernel(x1, x2, gamma) else: raise ValueError("unknown kernel type")

核函数闭包的设计是为了把gamma参数固定在内部，后面主循环里调用时就不用每次都传。我当时做实验时发现，提前把核函数封装好，代码会干净很多，也不容易搞混参数作用域。

3. SMO实战步骤拆解

3.1 初始化与整体结构

SMO主循环需要维护的变量包括：alpha向量、阈值b、误差缓存E（用于缓存每个样本的预测误差）。误差缓存是Platt原始实现里用于加速的核心技巧，因为选变量的时候需要频繁比较误差大小，如果每次都重新算一遍预测值，计算量会翻好几倍。

初始化阶段alpha全部设为0，b设为0，误差缓存E初始化为每个样本的预测值（这个时候相当于全部预测为0，所以E=-y）。之后进入外层循环，不断扫描违反KKT条件的样本，再通过内层循环挑搭档进行更新，直到所有样本都满足KKT条件，或达到最大迭代次数。

这里有一个容易忽略的点：b的值不能只更新一次。每次更新完alpha对后，b都需要重新计算，因为两个样本的预测误差已经变了。b的计算有两个候选值，分别在α₁和α₂满足边界条件时取对应表达式，当两个值都有效时取平均值。初学者往往只更新b不更新误差缓存，导致后面选变量时用的全是“过期数据”，训练过程可能振荡甚至发散。

3.2 启发式选择第一个变量

第一个变量的选择是SMO高效运行的关键。外层循环先遍历所有样本，找出违反KKT条件最严重的那个。KKT条件在SVM中的具体形态是：

• 当 αᵢ = 0 时，样本大概率落在边界外侧或边界上，此时需要 yᵢ·f(xᵢ) ≥ 1
• 当 0 < αᵢ < C 时，样本是支持向量，位于间隔边界上，此时 yᵢ·f(xᵢ) = 1
• 当 αᵢ = C 时，样本大概率落在间隔内部，此时 yᵢ·f(xᵢ) ≤ 1

判断时通常加一个容差tolerance，比如1e-3。如果yᵢ·f(xᵢ)与1的偏差超过tolerance，就认为违反。遍历完一遍后，下一轮会只在“非边界”的alpha（即0<α<C）里找违反者，因为边界样本的alpha已经卡死在0或C上，没有太多优化空间。这种“先全扫一遍，再聚焦非边界集”的两阶段策略，能让早期收敛速度明显加快。

3.3 启发式选择第二个变量

第二变量的选择目标，是找一个能让目标函数下降幅度最大的搭档。Platt提出一个近似标准：选择能让|E₁-E₂|最大的样本作为第二个变量。因为二维子问题的步长直接跟这个差值挂钩，差值越大，单步优化越“赚”。实际操作中，会先遍历非边界样本，找|E₁-E₂|最大的；如果找不到足够好的候选，就回退到随机选择非边界的样本；如果还是不满足，就跳过当前第一个变量。

这段逻辑实现起来并不复杂，但调参时容易被坑。有一次我为了快，把“足够好”的阈值设得太大，导致每次都在随机选择，训练速度反而下降。比较稳的做法是先设个相对小的阈值，比如0.001或0.01，如果候选不够再放宽。关键在于：启发式选变量本质上是“尽量挑一个收益最大的”，但收益判断本身有时间成本，所以要在计算量和收敛速度之间找平衡。

3.4 更新alpha对与b的计算

选定两个变量后，子问题有解析解。推导过程虽然绕，但代码实现其实很直接。核心步骤是：

1. 先算新旧α₂的未裁剪值
2. 根据约束条件裁剪到[L, H]区间
3. 再反推α₁的新值
4. 更新b和误差缓存

这一步涉及的计算细节我会在下一章代码里完整展示。需要特别提醒的是：裁剪区间的计算必须考虑y₁和y₂是否相等，如果搞错方向，α会直接跑到无解区域。我当初在这上面卡了一个多小时，最后才发现是符号写反。

3.5 收敛判断

主循环的收敛条件一般由两个参数控制：最大迭代次数max_passes和容差eps。Platt原始论文里用“一次外层循环中alpha没有发生任何改变”的次数来判停，超过max_passes就停。实际使用中，我更喜欢同时检查目标函数的变化量，当变化量连续多次小于某个极小阈值（比如1e-5）时也提前停止。这样既能省时间，又能避免在数据噪声比较大的时候无限振荡。

4. 手写SMO完整实现

4.1 代码主体结构

我将代码拆成几个函数，便于理解和复用。核心类SMO中包含数据、参数、核函数、误差缓存；外层循环是train()，内层循环是take_step()。这里的实现参考了Platt论文的约定，并做了适度简化以保留可读性。

import numpy as np class SMO: def __init__(self, X, y, C=1.0, tol=1e-3, eps=1e-7, kernel_type='rbf', gamma=0.5, max_passes=20): self.X = np.array(X, dtype=np.float64) self.y = np.array(y, dtype=np.float64).reshape(-1, 1) self.m, self.n = self.X.shape self.C = C self.tol = tol self.eps = eps self.max_passes = max_passes self.kernel_type = kernel_type self.gamma = gamma self.b = 0.0 self.alpha = np.zeros((self.m, 1)) self.E = -self.y.copy() self.K = self._compute_kernel_matrix() def _compute_kernel_matrix(self): K = np.zeros((self.m, self.m)) for i in range(self.m): if self.kernel_type == 'linear': K[i, :] = np.dot(self.X, self.X[i]) elif self.kernel_type == 'rbf': diff = self.X - self.X[i] K[i, :] = np.exp(-self.gamma * np.sum(diff * diff, axis=1)) return K

这个类一开始就预计算了核矩阵K，对于中等规模数据集（5000以下）非常合适。如果数据量再大，预计算会消耗大量内存，可以改成惰性计算或缓存部分行，但在小型教学实战中，预计算能让后面代码简洁很多。

4.2 误差缓存与KKT判断

误差E的定义是：

Eᵢ = f(xᵢ) - yᵢ

其中f(xᵢ) = ∑ⱼ αⱼ yⱼ K(xᵢ, xⱼ) + b。每次更新alpha和b后，需要同步刷新所有E。因为E的更新用到了核矩阵的整行，所以建议全部重算，而不是只更新两个。在我的测试里，全量重算虽然多花一点时间，但逻辑不容易出错。

def _update_error_cache(self): fX = np.dot((self.alpha * self.y).T, self.K).ravel() + self.b self.E = (fX - self.y.ravel()).reshape(-1, 1) def _violates_kkt(self, i): yi = self.y[i] Ei = self.E[i] ri = yi * (Ei + yi) - 1.0 # yi * f(xi) - 1 # 实际上等价于 yi*(Ei+yi) - 1 ai = self.alpha[i] if ai == 0: return ri < 0 # 本该 >= 0，但现在 < 0 elif ai == self.C: return ri > 0 # 本该 <= 0，但现在 > 0 else: return abs(ri) > self.tol

这里有一个小坑：我为了简洁，用了近似表达式 yi*(Ei+yi)-1，因为Ei=f(xi)-yi，所以yi*(Ei+yi)=yi*f(xi)。实际在代码里我更习惯直接算ri = yi * (Ei + yi) - 1.0，这样可以少一次预测计算。

4.3 内层优化：take_step

这一节是整个SMO的核心所在。它接收两个索引i1、i2，完成一次alpha对更新。完整函数如下：

def take_step(self, i1, i2): if i1 == i2: return 0 a1 = self.alpha[i1] a2 = self.alpha[i2] y1 = self.y[i1] y2 = self.y[i2] E1 = self.E[i1] E2 = self.E[i2] s = y1 * y2 if y1 != y2: L = max(0.0, a2 - a1) H = min(self.C, self.C + a2 - a1) else: L = max(0.0, a2 + a1 - self.C) H = min(self.C, a2 + a1) if L == H: return 0 k11 = self.K[i1, i1] k22 = self.K[i2, i2] k12 = self.K[i1, i2] eta = k11 + k22 - 2.0 * k12 if eta > 0: a2_new = a2 + y2 * (E1 - E2) / eta if a2_new < L: a2_new = L elif a2_new > H: a2_new = H else: # 当eta<=0时，目标函数在区间边界上更优 f1 = y1 * (E1 + y1) # y1*f(x1) f2 = y2 * (E2 + y2) v1 = a1 + s * a2 v2 = a2 + a1 Lobj = L * (L * eta / 2.0 + v1 * y2 - v2 * y2) - (f1 * y1 + f2 * y2) * L Hobj = H * (H * eta / 2.0 + v1 * y2 - v2 * y2) - (f1 * y1 + f2 * y2) * H if Lobj > Hobj + self.eps: a2_new = L elif Lobj < Hobj - self.eps: a2_new = H else: a2_new = a2 if abs(a2_new - a2) < self.eps * (a2_new + a2 + self.eps): return 0 a1_new = a1 + s * (a2 - a2_new) # 裁剪a1 if a1_new < 0: a1_new = 0.0 elif a1_new > self.C: a1_new = self.C # 更新alpha self.alpha[i1] = a1_new self.alpha[i2] = a2_new # 计算b b1 = self.b - E1 - y1 * (a1_new - a1) * self.K[i1, i1] - y2 * (a2_new - a2) * self.K[i1, i2] b2 = self.b - E2 - y1 * (a1_new - a1) * self.K[i1, i2] - y2 * (a2_new - a2) * self.K[i2, i2] if 0 < a1_new < self.C: self.b = b1 elif 0 < a2_new < self.C: self.b = b2 else: self.b = (b1 + b2) / 2.0 self._update_error_cache() return 1

这段代码有几个关键点值得展开。

第一个是裁剪区间L和H的推导。当y1和y2异号时，s=-1，约束α₁-α₂=γ=常数，所以α₂的可变范围是[max(0, α₂-α₁), min(C, C+α₂-α₁)]；当同号时，s=+1，范围是[max(0, α₂+α₁-C), min(C, α₂+α₁)]。这个方向不能记错。

第二个是eta的计算。eta = k11 + k22 - 2·k12，也就是第二个变量二次项的系数。正常情况下eta>0，可以直接用解析公式更新。但核函数不严谨或数据稀疏时，可能出现eta<=0的情况，这时候目标函数变成线性函数或凹函数，最优解在边界上。我在代码里用Lobj、Hobj比较边界取值，虽然看起来麻烦，但能保证步骤合法性。

第三个是b的更新逻辑。只有当α₁落在开区间(0,C)内时b1才可信，只有当α₂落在开区间(0,C)内时b2才可信。两者都落在边界上时，取平均值。这个规则的理论依据是KKT条件中“自由支持向量”的等式关系，工程上这样处理能避免b的估计偏移。

4.4 外层主循环与变量选择

外层循环负责遍历样本，选择第一个变量i1，然后调用take_step。Platt的两阶段选择策略体现在：先全量扫描，再聚焦非边界集合。

def train(self): numChanged = 0 examineAll = True passes = 0 while passes < self.max_passes and numChanged > 0 or passes == 0: numChanged = 0 if examineAll: for i in range(self.m): numChanged += self.examine_example(i) else: non_bound = np.where((self.alpha > 0) & (self.alpha < self.C - self.eps))[0] for i in non_bound: numChanged += self.examine_example(i) if examineAll: examineAll = False elif numChanged == 0: examineAll = True passes += 1 return self.alpha, self.b def examine_example(self, i2): if not self._violates_kkt(i2): return 0 # 从非边界样本中寻找 |E1 - E2| 最大的 non_bound = np.where((self.alpha > 0) & (self.alpha < self.C - self.eps))[0] if len(non_bound) > 0: i1 = non_bound[np.argmax(np.abs(self.E[non_bound] - self.E[i2]))] if self.take_step(i1, i2): return 1 # 否则随机从非边界选一个尝试 if len(non_bound) > 0: for i in np.random.permutation(non_bound): if self.take_step(i, i2): return 1 # 再尝试全部样本 for i in np.random.permutation(range(self.m)): if self.take_step(i, i2): return 1 return 0

我一度以为为什么examine_example里要连续尝试多次，后来发现这是Platt为了提高收敛率的巧妙设计。第一个变量选定了不一定就能更新成功，因为第二个变量可能不满足增量阈值，与其直接放弃，不如多试几个候选搭档。这个“不抛弃不放弃”的策略，能大幅减少外层扫描的次数。

4.5 决策函数与支持向量查看

训练完成后，分类函数就是f(x) = ∑ᵢ αᵢyᵢK(xᵢ,x) + b。预测时只需要统计所有alpha不为0的样本（支持向量），而不是全量样本。

def predict(self, X_new): X_new = np.array(X_new, dtype=np.float64) if X_new.ndim == 1: X_new = X_new.reshape(1, -1) sv_idx = np.where(self.alpha > self.eps)[0] result = [] for x in X_new: s = self.b for j in sv_idx: if self.kernel_type == 'linear': k = np.dot(self.X[j], x) else: diff = self.X[j] - x k = np.exp(-self.gamma * np.dot(diff, diff)) s += self.alpha[j] * self.y[j] * k result.append(1 if s > 0 else -1) return np.array(result)

这个函数里，我把支持向量的索引先抽出来，而不是每次都遍历整个alpha数组。虽然样本量小的时候性能差异不大，但这个习惯对后续扩展到大数据集很有帮助。

5. 实验对比：线性可分与RBF核实战

5.1 线性可分的二维平面数据

我用一个模拟的二维数据集做了第一轮测试：两类数据，每类100个样本，线性可分。运行SMO，C取1.0，tol取1e-3。收敛后打印支持向量数量和准确率。

实验结果显示，训练很快，几个passes就收敛了，支持向量数大约是样本数的10%~15%，分类准确率达到98%以上。线性核时，决策边界是由支持向量所在的间隔线决定的，直观上能看得非常清楚。这里有个很典型的观察：某些远离边界的点alpha=0，完全不参与决策；靠近边界的点alpha落在(0,C)区间，是“自由支持向量”；还有少数点alpha被顶到C，是“边界支持向量”。理解这个分布，对后续调C值非常有帮助。

5.2 非线性数据与RBF核

再用同样的数据打一个“月亮型”分布，套RBF核，gamma初始取1.0。训练时明显感觉迭代次数比线性核要少一点点，但每次迭代如果你用的是惰性核计算就会慢一些。我这里因为预计算了核矩阵，性能很稳定。预测准确率也很高，接近99%。

然后我把gamma从1.0调到10再调到100，观察发生了什么：gamma=10时边界变得复杂，训练集准确率高但测试集有轻微波动；gamma=100时，模型开始把孤立点也圈成支持向量，过拟合已经比较明显。这个实验很有教育意义，直观地展示了RBF核的“局部性”参数gamma对模型复杂度的影响。

5.3 C值的影响

C是惩罚参数，控制着对误分类的容忍度。我做了多组实验，C从0.01到1000变化。低C时，决策边界平滑，但容易欠拟合；高C时，边界变得曲折，尽力把所有训练点都分开。实际应用中没有一个万能C，必须配合交叉验证来选。

有一次我在某个数据集上，仅仅是C从1调到5，交叉验证准确率就从91%掉到87%，后来发现是数据里存在少量标注噪声。C值太大，模型把噪声点也当成支持向量硬扛，导致泛化变差。遇到这种情形，反而要降低C，让模型容忍少数噪声，换取更好的泛化。

这张表我建议每个做过SVM调参的人都自己跑一遍，X轴是C，Y轴是准确率，会得到一个很经典的“U”形或倒U形曲线。多跑几组后，你对C的直觉会比任何理论讲解都深刻。

6. 常见问题与排查技法实录

6.1 训练特别慢，迭代很多轮还不收敛

优先检查三点：第一，是否忘了做特征缩放；第二，tol是否设得太小，比如1e-6；第三，启发式选择是否失效，导致一直在随机配对。我的经验是，特征缩放和tol大小的影响最大。如果数据本身噪音很大，tol设为1e-2到1e-3就够了，盲目追求1e-6只会让训练变成煎熬。另外可以打印出每轮的numChanged，观察它是不是一直在振荡。振荡严重时，尝试调大C，减小gamma，或者改用线性核，都能快速判断问题出在模型复杂度上还是算法实现上。

6.2 alpha全部变成0，模型完全没学习

这种情况通常是因为C太小，惩罚太弱，模型觉得“不犯错”的代价太高，干脆把所有alpha都压到0。我开始做实验时，C设成0.001，结果准确率跟随机猜一样。解决办法很简单：把C调大，至少先试到1或者10。同时检查一下标签，如果标签不是±1而是0/1，KKT条件里的乘法会错得离谱，alpha也很难有正常更新。

6.3 alpha更新后数值溢出或NaN

最常见的场景是核函数里exp的参数过大。比如RBF核，gamma乘上距离的平方后数值极大，exp(-large)会变成0，反过来如果距离极小，exp(-tiny)约等于1，这本身没问题。但当你调试时，如果特征值量级差异极大，距离平方可能非常大，导致精度问题。解决办法就是特征标准化，把特征值缩放到[-1,1]附近。另一个可能性是C被设成无穷大，这在SMO里会造成边界无限，建议使用一个足够大的有限值，比如1e5。

6.4 预测准确率在训练集很高，测试集很差

经典过拟合。优先检查gamma，如果gamma设置过大，支持向量会把每个样本的局部影响放大到极端程度。我会画一个“支持向量数量 vs gamma”的曲线，发现随着gamma增大，支持向量数迅速上升，这时模型已经变成“记忆机器”了。此时降低gamma，同时适当调低C，往往能在大约10到20次实验内找到一个泛化较好的区域。

6.5 核矩阵预计算的内存爆炸

当m超过10000时，全量核矩阵的存储会变得不太现实。我建议改成按需计算：在take_step里用到哪一行，就临时算哪一行，同时在内存里维护一个最近使用的行缓存。虽然实现上复杂一点，但能扩展到10万级别的数据。如果你只是做教学实践，预计算足够；要做大规模工业应用，直接上成熟的库可能更省力。

7. 调参心得与扩展方向

在实际项目中，我强烈建议不要一开始就直接调SMO参数，而是先用成熟库（比如某些经典库）得到一组结果作为基准，再回到自己的SMO实现里对比。这样能快速帮你判断“是我代码写错了，还是参数没调好”。

以SMO本身来说，我认为最重要的两个超参数是C和gamma。C控制间隔最大化和误分类最小化之间的平衡，gamma控制RBF核的局部影响半径。我的调参顺序一般是这样：先用默认gamma（比如1/n特征数），调C；C稳定后，再调gamma；最后用交叉验证网格搜索做微调。这个过程虽然朴素，但效果稳定。

如果你想把SMO用到更大的数据集，可以考虑几个优化方向：内核循环用Cython或C扩展；用随机抽样减小每轮扫描规模；用工作集选择替代简单启发式；加缓存机制保存频繁访问的核函数结果。这些优化我都试过，每一步都能带来几倍到几十倍的加速。

写完整套实现后，我的建议是：自己把SMO从零写一遍，再用成熟工具去对比。写代码时可以报错，可以调参调得怀疑人生，但一定要观察alpha的分布和支持向量的形状。只有亲手把一个alpha从0推到边界，再从边界推回0，你才算真正理解了SVM的训练过程。这个过程带来的收获，远不是直接调用一个fit方法能比的。