支持向量机SVM
定义
支持向量机(Support Vector Machine, SVM)指以最大化几何间隔为准则求解线性判别函数 的一类分类方法;样本线性不可分时引入松弛变量 得到软间隔形式,并用核函数 替换内积,使判别函数在映射后的特征空间中线性、在原输入空间中非线性。
- :训练集, 为样本数。
- :第 个样本的特征向量, 为特征维数。
- :类别标记,二分类采用该编码。
- :分离超平面的法向量,决定超平面方向。
- :偏置,决定超平面相对原点的位置。
- :样本 的函数间隔(functional margin)。
- :样本 的几何间隔(geometric margin),等于样本到超平面的欧氏距离,分类正确时取正值。
- :松弛变量,度量样本违反间隔约束的程度。
- :正则化常数,控制间隔宽度与间隔违反总量之间的权衡。
- :间隔约束对应的拉格朗日乘子,软间隔下同时受上界 约束。
- :核函数,, 为特征映射, 为内积空间。
- 支持向量(support vector):满足 的训练样本,其间隔约束在最优解处起作用。
为什么重要
- 解决的问题:逻辑回归只要求把样本分对,分离超平面在可分数据上有无穷多个;SVM 在全部可行超平面中选出到最近样本距离最大的一个,使解唯一且对样本扰动不敏感。
- 没有它会怎样:缺少一个把「间隔最大化」写成凸二次规划、再用对偶与 KKT 求解的完整范例;也缺少核方法的入口,非线性判别将只能依靠显式构造高维特征。
- 对偶形式的意义:原始问题在 中求解,对偶问题在 中求解,且目标函数只通过样本两两内积依赖数据。当 时对偶更经济,同时为核替换提供了结构上的可能。
- 在全书中的位置:前置为 逻辑回归 的线性判别与 优化算法-梯度下降与Adam 的凸优化、拉格朗日乘子;本篇的对偶与 KKT 是理解 树模型与集成学习 中正则化目标、以及后续对偶方法的基础; 与 的选取直接进入 模型评估与交叉验证 的流程。
- 对应能力目标:懂原理要求能完成从原始问题到对偶问题的推导并解释 KKT 的每一组条件;能复现要求能写出核化决策函数与两变量解析更新;会评估要求能判断 、、核类型对支持向量数量与泛化误差的影响。
原理与推导
flowchart TD
A["原始问题:最小化 0.5·||w||²,约束 y_i(w·x_i+b)>=1"] --> B["拉格朗日函数 L(w,b,alpha)"]
B --> C["对偶问题:关于 alpha 的二次规划"]
C --> D["KKT 条件:互补松弛 alpha_i·(y_i f_i-1)=0"]
D --> E["支持向量与偏置 b"]
C --> F["核替换:内积 x_i·x_j 换为 K(x_i,x_j)"]
F --> G["核化决策函数 f(x)=sum alpha_i y_i K(x_i,x)+b"]
C --> H["SMO:固定其余变量,解析求解两个 alpha"]
1. 最大间隔分类的几何设定
分离超平面定义为点集 ,法向量 与其正交。点 到该超平面的带符号距离为
符号由 决定,绝对值除以 后与 的尺度无关。判别规则取 。
设两类样本分别位于超平面两侧。记最近的正类样本到超平面的距离为 ,最近的负类样本距离为 ,则间隔(margin)定义为 。对固定方向 ,平移 可使两侧最近距离相等,即最优解处 ,间隔宽度为 。若把两侧的约束统一写成 ,则由点到平面距离公式,,间隔宽度为
因此最大化间隔等价于最小化 ,这是后续优化问题的几何来源。
2. 函数间隔与几何间隔
函数间隔 只要求约束值不小于某个正数,本身带有尺度不确定性:把 同时乘以 ,超平面不变,但 变为 。数据集上的函数间隔取 ,几何间隔取 。
尺度不确定性带来两种归一化方式:
- 固定 ,此时函数间隔等于几何间隔,优化变量落在单位球面上,约束为非线性。
- 固定 ,即要求 ,约束为线性,代价是 可以自由缩放。
第 2 种方式把问题化为凸二次规划,是标准做法。其合法性在于:对任意可行解 ,设其函数间隔为 ,令 、,则新解的函数间隔为 ,几何间隔保持不变,而 。因此「在 的约束下最小化 」与「在所有可行超平面中最大化 」等价。
3. 硬间隔优化问题
在数据线性可分的假设下,原始问题为
目标函数是 的严格凸二次函数,约束是仿射函数,可行域为凸集,因此局部最优即全局最优,且最优 唯一( 的唯一性需另行判断)。 是为了求导后消去系数 。 由 KKT 条件确定:若存在满足 的自由支持向量,则 唯一;若不存在, 只能确定在一个由两类边界样本共同界定的区间内。
4. 拉格朗日函数与对偶问题
对每个不等式约束引入乘子 ,拉格朗日函数为
原始问题等价于 :当约束被违反时,括号内为负,乘子取无穷大使 ;约束满足时, 在 处取到, 退化为原目标。交换 与 得到对偶问题 ,由弱对偶,对偶值不超过原始值。
先对内层求极小。令偏导为零:
将两式代回 。第一项:
第二项:
第三项 。合并得
于是对偶问题为
对偶目标关于 是凹二次函数,约束为线性,可行域非空,因此对偶可解。线性可分时存在严格可行点,Slater 条件成立,强对偶成立,原始最优值等于对偶最优值。数据不可分时原始问题无可行解,此时必须引入松弛变量。
5. KKT 条件与支持向量
凸问题且强对偶成立时,原始最优解与对偶最优解满足 KKT 条件:
- 平稳性:,,即 且 。
- 原始可行性:。
- 对偶可行性:。
- 互补松弛:。
由第 4 条,若 ,则 ,样本恰好落在间隔边界上;若 ,则 。因此只有位于间隔边界上的样本对 有非零贡献,这些样本就是支持向量。决策函数可写成
预测代价只与支持向量数量成正比,与 无必然关系。
偏置由自由支持向量给出:若存在 使 ,则
数值实现中通常对所有满足 的样本求平均以降低误差。若不存在自由支持向量, 只能确定在一个区间内,该区间由 与 两侧的约束共同界定。
6. 软间隔、松弛变量与 C 的作用
数据不可分时,约束 无解。引入松弛变量 允许违反:
是间隔宽度与违反总量之间的交换率。 时任何 都不可接受,退化为硬间隔; 减小时允许更多样本进入间隔内部甚至被错分,间隔变宽。对应的对偶问题只多出上界约束:
三类 的几何含义:
| 取值 | 位置 | 对 的贡献 |
|---|---|---|
| 间隔外且分类正确 | 无 | |
| 恰在间隔边界上 | 有,且 由这些样本确定 | |
| 间隔内或被错分 | 有,其违反量为 |
从偏差-方差角度看, 小对应强正则化、宽间隔、偏差大方差小; 大对应弱正则化、窄间隔、偏差小方差大。 需要通过交叉验证选择,不能由训练误差单调判断。
7. 合页损失视角
软间隔问题可消去 。对固定的 ,每个 的可行下界是 ,目标中 的系数 为正,故最优取该下界:
代回目标得无约束形式
右侧求和项即合页损失(hinge loss)。它在 时为零,在 时线性增长,在 处不可导。其 subgradient 为
因此目标的次梯度下降更新为 。合页损失在间隔外梯度为零,这解释了支持向量的稀疏性:只有违反间隔的样本持续影响参数。
与 逻辑回归 的对数损失对比:对数损失在 时仍给出非零梯度,模型会继续把已正确分类但置信度低的样本推远;合页损失在 后停止惩罚,因而解更稀疏。二者都是 - 损失的凸上界,训练目标不同导致解的性质不同。
8. 核技巧与 Mercer 条件
对偶目标与决策函数只通过内积 依赖数据。若把每个样本映射为 ,只需把内积替换为 ,无需显式计算 。这一替换称为核技巧(kernel trick)。
一个对称函数 能写成某个内积空间中的内积,当且仅当它对任意有限样本集的 Gram 矩阵半正定:
连续形式即 Mercer 条件:对平方可积函数 ,
满足该条件的核对应对称半正定核矩阵,此时存在特征映射与再生核希尔伯特空间。实践中可行性检查即为:对训练集计算核矩阵,检查最小特征值是否显著为负。
常用核:
| 核 | 表达式 | 超参数 | 性质 |
|---|---|---|---|
| 线性核 | 无 | 等价于原始空间线性 SVM, 大时首选 | |
| 多项式核 | 显式建模特征交叉, 大时数值不稳定 | ||
| RBF 核 | 对应无穷维特征空间,局部性由 控制 | ||
| Sigmoid 核 | 仅部分参数下半正定,不保证满足 Mercer 条件 |
RBF 核的无穷维展开说明其表达能力:由 与指数函数的幂级数,
即特征映射包含所有阶数的多项式项。 越大,核随距离衰减越快,单个支持向量的影响范围越小,模型越容易过拟合; 越小,核接近常数,模型趋向欠拟合。
9. 核化后的决策函数
把内积替换为核后,对偶问题与决策函数为
在特征空间中 ,因此核化后的间隔宽度仍是 ,只是该范数无法在原始空间中直接观测。预测时需计算 与全部支持向量的核值,代价为 。
由于核矩阵只依赖样本间的相似度,SVM 的预测可视为「以支持向量为参照、按核相似度加权投票」,其权重由 给出。这一结构与 Embedding与向量检索 中以内积衡量相似度的做法同源,区别在于 SVM 的权重由间隔约束解出,检索的权重由模型训练得到。
10. SMO 算法
对偶问题是 个变量的二次规划,通用求解器需要 量级。序列最小最优化(Sequential Minimal Optimization, SMO)利用等式约束 :若只保留两个变量,其余固定,则等式约束把两个变量压成一维,子问题有解析解。
设选中 ,其余 固定。由约束得
代入对偶目标,得到关于 的一元二次函数,二次项系数为 ,其中
由 知目标关于 凹,无约束极大值点为
再把 裁剪到可行区间 ,并由等式约束回代 。
区间端点由 与等式约束共同决定:
| 情形 | ||
|---|---|---|
推导 一行:此时 ,条件 给出 与 ,与 取交集即得上表。
工作集选择常用最大违反对:以 为违反度量,在
中取 、,当 小于容差时停止。每次更新只修改两个乘子,其余乘子保持不变,因而每步代价为 量级,整体在中等规模数据上明显快于通用二次规划求解器。
11. 复杂度
| 环节 | 代价 | 说明 |
|---|---|---|
| 核矩阵构造 | 时间、 内存 | 线性核可省去显式矩阵,按需计算 |
| 通用二次规划求解 | 最坏 | 稠密矩阵分解 |
| SMO | 每步 ,总步数与问题难度相关 | 实践中常为 量级 |
| 线性核专用求解器 | 每轮 | 坐标下降或对偶坐标下降 |
| 预测 | 只与支持向量数量有关 |
达到 以上时, 的核矩阵内存成为主要瓶颈;此时可选线性核并改用线性求解器,或使用随机特征近似 RBF 核,把核化问题转回 的线性问题。
关键直觉
机制性直觉
对偶形式说明:SVM 的判别函数只通过核函数与支持向量的内积依赖训练数据, 是每个间隔约束的对偶变量,只有约束在最优解处取等号的样本才有 ,软间隔下还包括被截断在 的违反样本。最大化间隔等价于在「所有样本距超平面至少 」的约束下最小化 ,因此预测代价由支持向量数量 决定,而非由样本总数 决定。这与定义中「支持向量是 的样本」一条严格对应: 的稀疏性直接给出预测时的计算量。
例子与代码
手算:4 个样本的硬间隔解
取 、 为正类,、 为负类,。
第 1 步:确定起作用约束。跨类最近的点对是 与 ,距离 。若最大间隔超平面的最近点正是这一对,则法向量平行于 ,可设 。
第 2 步:令两个约束取等号。
两式相减得 ,即 ,代回得 。于是 ,,分界直线为 。
第 3 步:验证其余约束。,,均满足。
第 4 步:由 KKT 求乘子。由 得
两个分量给出同一方程 ;由 得 。联立得 ,。
第 5 步:验证最优性。对偶目标
而原始目标 ,两者相等,强对偶成立,故该解最优。
第 6 步:几何量。,几何间隔 ,间隔宽度 。各样本的函数间隔为 ,只有 落在边界上。
尺度检查。若取 ,超平面不变,函数间隔变为 ,几何间隔不变。这说明约束 是归一化约定,不是几何不变量。
代码一:不同核的对比与 C 的作用
以下代码在二维双月数据上训练三种核的 SVM,输出支持向量数量与准确率。标准化是必要的:RBF 核按欧氏距离衰减,特征尺度不同会让距离由方差大的特征主导。
# 依赖:Python 3.12、NumPy 2.3.5、scikit-learn 1.9.1
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
X, y = make_moons(n_samples=200, noise=0.25, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
scaler = StandardScaler().fit(X_tr)
X_tr, X_te = scaler.transform(X_tr), scaler.transform(X_te)
grid = {
"linear": dict(kernel="linear"),
"poly3": dict(kernel="poly", degree=3, coef0=1.0, gamma="scale"),
"rbf": dict(kernel="rbf", gamma="scale"),
}
for name, kw in grid.items():
clf = SVC(C=1.0, **kw).fit(X_tr, y_tr)
print(f"{name:6s} 支持向量 {clf.n_support_.sum():3d}(每类 {clf.n_support_})"
f" 训练 {clf.score(X_tr, y_tr):.4f} 测试 {clf.score(X_te, y_te):.4f}")
for C in [0.01, 0.1, 1.0, 100.0]:
clf = SVC(C=C, kernel="rbf", gamma="scale").fit(X_tr, y_tr)
at_bound = int(np.sum(np.abs(clf.dual_coef_) >= C - 1e-9))
print(f"C={C:<6} 支持向量 {clf.n_support_.sum():3d} 位于上界 {at_bound:3d}"
f" 测试 {clf.score(X_te, y_te):.4f}")
预期输出:
linear 支持向量 54(每类 [27 27]) 训练 0.8143 测试 0.8667
poly3 支持向量 46(每类 [23 23]) 训练 0.9286 测试 0.9333
rbf 支持向量 54(每类 [26 28]) 训练 0.9357 测试 0.9333
C=0.01 支持向量 140 位于上界 140 测试 0.8833
C=0.1 支持向量 96 位于上界 92 测试 0.8833
C=1.0 支持向量 54 位于上界 44 测试 0.9333
C=100.0 支持向量 26 位于上界 14 测试 0.9000
解读:
- 线性核在二维双月数据上训练准确率 0.8143,明显低于 RBF 核的 0.9357。数据本身非线性可分,线性核的假设空间不足,增加 也不能改变这一点。
- 支持向量占比高(54/140)说明间隔边界附近样本密集,这也是非线性数据上 SVM 预测代价偏高的原因。
- 时 140 个训练样本全部成为支持向量且全部位于上界 ,每轮更新都被箱约束截断,模型容量被 强限制,测试准确率 0.8833; 时支持向量降至 26,模型更贴合训练集,测试准确率反而下降到 0.9000。这组数据上 的测试表现最好,说明 必须由验证集选择。
dual_coef_返回的是 组成的带符号数组,两类的符号相反,因此用绝对值与 比较。
代码二:手写 SMO
以下实现只依赖 NumPy,用最大违反对选择工作集,用核矩阵统一处理线性与 RBF 两种情形。收敛判据取对偶目标的增量,避免退化情形下 KKT 间隙判据的振荡。
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
def rbf_kernel(A, B, gamma):
d2 = (A ** 2).sum(1)[:, None] + (B ** 2).sum(1)[None, :] - 2.0 * A @ B.T
return np.exp(-gamma * np.maximum(d2, 0.0))
def smo(K, y, C=1.0, tol=1e-9, max_iter=5000):
n = len(y)
a = np.zeros(n)
Q = np.outer(y, y) * K
W_old = -np.inf
for it in range(max_iter):
W = a.sum() - 0.5 * a @ Q @ a # 对偶目标,用于判断是否继续
if W - W_old < tol:
break
W_old = W
grad = Q @ a - 1.0 # 对偶目标的梯度
up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))
low = ((y > 0) & (a > 0)) | ((y < 0) & (a < C))
gu = np.where(up, -y * grad, -np.inf)
gl = np.where(low, -y * grad, np.inf)
i = int(np.argmax(gu)) # 最大违反对中的 i
for j in np.argsort(gl): # 依次尝试违反最大的 j
if j == i:
continue
ai, aj = a[i], a[j]
if y[i] != y[j]:
L, H = max(0.0, aj - ai), min(C, C + aj - ai)
else:
L, H = max(0.0, ai + aj - C), min(C, ai + aj)
if L >= H:
continue
eta = K[i, i] + K[j, j] - 2.0 * K[i, j]
if eta <= 1e-12:
continue
aj_new = np.clip(aj - (grad[j] - y[i] * y[j] * grad[i]) / eta, L, H)
a[i], a[j] = ai - y[i] * y[j] * (aj_new - aj), aj_new
break
return a, it
def fit_b(K, y, a, C):
sv = (a > 1e-9) & (a < C - 1e-9) # 自由支持向量确定 b
f0 = K @ (a * y)
return float(np.mean(y[sv] - f0[sv])) if sv.any() else 0.0
Xs = np.array([[3., 3.], [4., 3.], [1., 1.], [1., 0.]])
ys = np.array([1., 1., -1., -1.])
K4 = Xs @ Xs.T
a, it = smo(K4, ys, C=1e6, tol=1e-12)
b = fit_b(K4, ys, a, 1e6)
print("手算例:alpha =", np.round(a, 4), " b =", round(b, 4))
print("w =", np.round((a * ys) @ Xs, 4), " 间隔 =", np.round(ys * (K4 @ (a * ys) + b), 4))
print("迭代次数 =", it, " ||w|| =", round(float(np.linalg.norm((a * ys) @ Xs)), 4))
X, y = make_moons(n_samples=200, noise=0.25, random_state=0)
y = np.where(y == 0, -1.0, 1.0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
sc = StandardScaler().fit(X_tr)
X_tr, X_te = sc.transform(X_tr), sc.transform(X_te)
gamma = 1.0 / X_tr.shape[1]
K_tr, K_te = rbf_kernel(X_tr, X_tr, gamma), rbf_kernel(X_te, X_tr, gamma)
a, it = smo(K_tr, y_tr, C=1.0)
b = fit_b(K_tr, y_tr, a, 1.0)
print("双月:迭代", it, " 支持向量", int((a > 1e-9).sum()), " 上界", int((a > 1 - 1e-9).sum()))
print("训练准确率", round(float(np.mean(np.sign(K_tr @ (a * y_tr) + b) == y_tr)), 4),
" 测试准确率", round(float(np.mean(np.sign(K_te @ (a * y_tr) + b) == y_te)), 4))
print("对偶目标", round(float(a.sum() - 0.5 * (a * y_tr) @ K_tr @ (a * y_tr)), 4))
预期输出:
手算例:alpha = [0.25 0. 0.25 0. ] b = -2.0
w = [0.5 0.5] 间隔 = [1. 1.5 1. 1.5]
迭代次数 = 7 ||w|| = 0.7071
双月:迭代 38 支持向量 52 上界 46
训练准确率 0.9357 测试准确率 0.9333
对偶目标 39.5929
说明:
- 手算例得到 、、,与手算完全一致,说明解析更新与裁剪逻辑正确。 用于近似硬间隔;若取 , 会被压到上界, 的模长随之改变。
- 双月数据上 38 次迭代收敛,训练准确率 0.9357、测试 0.9333,与 scikit-learn 的 LIBSVM 结果一致(其支持向量数为 54,差异来自对偶解在边界样本上的不唯一性与数值容差)。
- 若删去
np.clip, 可能越出 ,等式约束仍成立但违反箱约束,迭代会发散或得到负的乘子。 - 若删去
fit_b中「自由支持向量」的筛选而直接用全部样本平均, 的估计会被位于间隔内或被错分的样本影响而产生偏移,因为只有 的样本满足 。
易错点
常见错误
- 把函数间隔当作几何间隔。约束 只是归一化约定,间隔宽度是 ;报告中若写「间隔为 1」,必须说明是函数间隔。
- 认为 等价于样本「在间隔边界上」。 才对应边界; 对应间隔内部或错分样本,其函数间隔小于 1。
- 用 的唯一性做结论。当支持向量线性相关或恰在边界上时,对偶最优解可能不唯一,而原始最优 仍唯一;例如四个位于正方形顶点的样本, 与其他组合给出同一个 。
- 混淆 与 的作用。 控制间隔违反的惩罚, 控制 RBF 核的局部性;固定 调 会同时改变模型复杂度与支持向量数量,二维网格搜索必须联合进行。
- 在未标准化的特征上直接使用 RBF 核。尺度大的特征主导欧氏距离,核矩阵接近单位阵,模型退化为最近邻分类。
- 把
SVC(probability=False)的decision_function输出当作概率。原始 SVM 输出的是到超平面的带符号距离,概率需要额外的校准(如 Platt 缩放)并会改变训练过程。
关联笔记
- 前置:逻辑回归 —— 同为线性判别模型,对照对数损失与合页损失的差异可解释稀疏性与概率输出的取舍。
- 前置:优化算法-梯度下降与Adam —— 拉格朗日乘子、对偶与 KKT 是凸优化的直接应用,本篇第 4、5 节依赖该篇的约束优化结论。
- 后续:模型评估与交叉验证 —— 、 与核类型的联合选择需要在验证集上完成,本篇只给出目标函数与求解方法。
- 对照:树模型与集成学习 —— 轴对齐划分不需要特征缩放、可处理非线性,但其决策边界不连续;SVM 的边界由少数支持向量连续决定,对特征尺度敏感。
- 应用:Embedding与向量检索 —— 核矩阵与嵌入相似度矩阵同为样本两两内积,SVM 的核化决策函数与基于内积的检索评分结构相同。
达标检测
- [ ] 写出函数间隔与几何间隔的定义,并说明为什么可以令 而不失一般性。
- [ ] 从硬间隔原始问题出发,写出拉格朗日函数,完成对 、 的求导、回代与对偶问题的全部步骤。
- [ ] 写出 KKT 的四组条件,并由互补松弛条件推出「只有支持向量影响决策函数」。
- [ ] 由软间隔原始问题消去 得到合页损失形式,并说明 增大时偏差与方差如何变化。
- [ ] 手算本篇 4 点例子:给出 、、、间隔宽度,并验证对偶目标等于原始目标。
- [ ] 运行代码二,把
gamma改为 与 ,记录支持向量数量与测试准确率的变化并解释原因。 - [ ] 构造一个对称函数并检查其 Gram 矩阵的最小特征值,判断它能否作为核使用。
参考来源
- Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, 2009, 第 12 章 —— 对应本篇最大间隔几何设定、对偶推导、核技巧与正则化视角。
- Stanford CS229 课程讲义(Andrew Ng),支持向量机与拉格朗日对偶部分 —— 对应本篇原始问题到对偶问题的推导、KKT 条件与 SMO 的两变量解析更新。
- d2l.ai《动手学深度学习》,第 12.2 节 凸性(含约束优化与 KKT 条件的讨论)—— 对应本篇对偶问题与 KKT 条件的凸优化背景。
- Goodfellow, Bengio, Courville, Deep Learning, 2016, 第 5 章 机器学习基础 —— 对应本篇合页损失作为线性分类器训练目标的定位,以及与逻辑回归损失的对照。