Day 11｜SVM 与核方法:几何直觉驱动的最大间隔分类器（AI 学习笔记 · 经典机器学习周 · 第 11 篇）

SVM(支持向量机)的核心想法只有一句话——在两类样本之间找一条「最宽的马路」,马路的边界叫超平面,定义马路宽度的样本叫支持向量;当数据线性不可分时,核函数让 SVM 在隐式高维空间里继续找这条路,而无需真的把数据映射过去。

1. 几何直觉:最胖的那条分割线

1.1 二分类超平面

二维平面里的「分割线」推广到 d 维空间就是超平面:

w^T x + b = 0

• w = 法向量(决定超平面方向)
• b = 偏置(决定超平面位置)

1.2 函数间隔与几何间隔

对样本 (x_i, y_i),y_i ∈ {+1, -1}:

函数间隔(可同时缩放 w, b):

\hat{\gamma}_i = y_i (w^T x_i + b)

几何间隔(真实距离,缩放不变):

\gamma_i = y_i \cdot \frac{w^T x_i + b}{\|w\|}

优化目标:让所有样本中几何间隔最小的那个尽量大,等价于:

\max_{w,b} \quad \min_i \gamma_i

固定 min_i γ_i = 1(归一化),问题化为:

\min_{w,b} \quad \frac{1}{2} \|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \ge 1, \ \forall i

直观:最小化 ‖w‖ 等于最大化间隔,几何间隔 = 2 / ‖w‖。

1.3 支持向量的几何意义

约束 y_i(w^T x_i + b) ≥ 1 在最优点对部分样本「卡死」(Lagrange 乘子 α_i > 0),这些样本就是支持向量:它们正好在间隔边界上,定义马路的两个边线;其它样本 α_i = 0,对超平面没影响。

2. 软间隔:允许犯点小错

2.1 现实世界没有完美分割

数据有噪声、有重叠时,严格约束 y_i(w^T x_i + b) ≥ 1 无解。引入松弛变量 ξ_i ≥ 0,把硬约束放松成:

y_i(w^T x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0

目标函数加惩罚:

\min_{w,b,\xi} \quad \frac{1}{2}\|w\|^2 + C \sum_i \xi_i

2.2 惩罚参数 C 的含义

C 越大 → 越不容忍 ξ(硬间隔倾向,可能过拟合) C 越小 → 越宽容(可能欠拟合,泛化强)

等价于 L2 正则化的强度:对偶形式里 C 出现在 0 ≤ α_i ≤ C 的上界,直接限制支持向量的影响力。

2.3 合页损失(Hinge Loss)的另一种视角

SVM 的软间隔目标等价于经验风险 + L2 正则:

\sum_i \max(0, 1 - y_i(w^T x_i + b)) + \lambda \|w\|^2

max(0, 1 - y·f(x)) 就是合页损失——只要分对了且置信度高,损失为 0;否则线性增长。与之对照,Logistic Regression 用 LogLoss,在 y·f = 0 附近还给出小梯度;SVM 在 y·f ≥ 1 时直接 0 梯度,得到稀疏解(只有支持向量贡献)。

3. 对偶问题与 KKT 条件

3.1 拉格朗日对偶

原始问题:

\min_{w,b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \ge 1

拉格朗日函数:

\mathcal{L}(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i [y_i(w^T x_i + b) - 1]

对 w, b 求偏导令为 0:

w = \sum_i \alpha_i y_i x_i, \quad \sum_i \alpha_i y_i = 0

代回得对偶问题:

\max_\alpha \quad \sum_i \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle

\text{s.t.} \quad \alpha_i \ge 0, \quad \sum_i \alpha_i y_i = 0

3.2 KKT 条件(对偶可行的充要条件)

对偶变量 α_i 和原始约束 ξ_i 满足:

\alpha_i \ge 0, \quad y_i f(x_i) - 1 + \xi_i \ge 0, \quad \xi_i \ge 0

\alpha_i [y_i f(x_i) - 1 + \xi_i] = 0, \quad \mu_i \xi_i = 0

互补松弛性直接给出支持向量的判定:α_i > 0 的样本就是支持向量。

3.3 SMO 算法骨架

对偶问题是一个 QP,但 α 维度 = 训练样本数。Platt 1998 提出的 SMO 把它拆成「每次选两个变量」的子问题:

repeat:
    选两个变量 α_i, α_j (启发式:违反 KKT 最严重的两个)
    固定其它 α_k (k≠i,j)
    在约束 Σ α_k y_k = 0 下极小子问题(解析解)
until 收敛或达最大迭代

SMO 的关键洞察:两变量子问题有解析闭式解,因为约束把一个变量完全由另一个决定。LIBSVM / sklearn.svm.SVC 都基于 SMO。

4. 核技巧:低维不可分 → 高维可分

4.1 一个直觉例子

二维平面里 XOR 数据线性不可分——对角点同类、邻角点异类。但映射到三维:

\phi: (x_1, x_2) \mapsto (x_1, x_2, x_1^2 + x_2^2)

在第三维「半径平方」上,XOR 的两类就线性可分了。

问题是:显式映射到高维的计算代价随维度指数爆炸(组合爆炸)。

4.2 核函数定义

核函数是对偶形式中 ⟨x_i, x_j⟩ 的直接替代:

K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle

只要 K 能写成高维内积,就可以不显式算 φ,只在低维算 K 本身。

4.3 RBF 核 + γ 参数的几何含义

K_{\text{RBF}}(x, z) = \exp(-\gamma \|x - z\|^2)

• γ 小 → K 衰减慢 → 「远近样本都被认为相似」 → 决策边界平滑 → 欠拟合
• γ 大 → K 衰减快 → 「只有很近的样本才被认为相似」 → 决策边界崎岖 → 过拟合

直觉:γ = 1 / (2σ²),σ 是 RBF 的「有效半径」。

4.4 核函数有效条件(Mercer 定理)

一个对称函数 K 是合法核函数(对应某高维内积空间)当且仅当它在任意有限样本上的 Gram 矩阵 K_{ij} = K(x_i, x_j) 是半正定。违反 Mercer 的核(比如 sigmoid 核在某些参数下)会让 SVM 求解器不收敛。

5. PyTorch / sklearn 实战

5.1 sklearn SVM 三件套 + 网格搜索

import numpy as np
from sklearn.datasets import load_iris, make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC, LinearSVC
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.metrics import accuracy_score
import matplotlib.pyplot as plt

# 1. 线性核:鸢尾花二分类
iris = load_iris()
X = iris.data[:100, :2]  # 只取前两类、前两维便于画图
y = iris.target[:100]
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3,
                                          stratify=y, random_state=42)
lin = LinearSVC(C=1.0, dual="auto")
lin.fit(X_tr, y_tr); print("Linear acc:", accuracy_score(y_te, lin.predict(X_te)))

# 2. RBF 核:月牙非线性
Xm, ym = make_moons(n_samples=400, noise=0.25, random_state=42)
Xs, ys = StandardScaler().fit_transform(Xm), ym
X_tr, X_te, y_tr, y_te = train_test_split(Xs, ys, test_size=0.3,
                                          stratify=ys, random_state=42)
grid = GridSearchCV(
    SVC(kernel="rbf"),
    param_grid={"C": [0.1, 1, 10, 100], "gamma": [0.01, 0.1, 1, 10]},
    cv=5, scoring="accuracy", n_jobs=-1,
)
grid.fit(X_tr, y_tr)
print("Best:", grid.best_params_, "CV acc:", grid.best_score_)
print("Test acc:", grid.score(X_te, y_te))

5.2 手写 SVM 对偶 SMO(教学版本)

import numpy as np

def rbf_kernel(X, gamma):
    sq = (X ** 2).sum(axis=1)
    K = np.exp(-gamma * (sq[:, None] + sq[None, :] - 2 * X @ X.T))
    return K

def smo_simplified(X, y, C=1.0, gamma=0.5, max_iter=200, tol=1e-3):
    n, d = X.shape
    K = rbf_kernel(X, gamma)
    alpha = np.zeros(n)
    b = 0.0
    for _ in range(max_iter):
        n_changed = 0
        for i in range(n):
            Ei = (alpha * y) @ K[:, i] + b - y[i]
            if (y[i] * Ei < -tol and alpha[i] < C) or (y[i] * Ei > tol and alpha[i] > 0):
                j = np.random.randint(0, n)
                Ej = (alpha * y) @ K[:, j] + b - y[j]
                ai, aj = alpha[i].copy(), alpha[j].copy()
                if y[i] != y[j]:
                    L, H = max(0, aj - ai), min(C, C + aj - ai)
                else:
                    L, H = max(0, ai + aj - C), min(C, ai + aj)
                if L >= H: continue
                eta = K[i, i] + K[j, j] - 2 * K[i, j]
                if eta <= 0: continue
                alpha[j] += y[j] * (Ei - Ej) / eta
                alpha[j] = np.clip(alpha[j], L, H)
                if abs(alpha[j] - aj) < 1e-5: continue
                alpha[i] += y[i] * y[j] * (aj - alpha[j])
                b1 = b - Ei - y[i] * (alpha[i] - ai) * K[i, i] - y[j] * (alpha[j] - aj) * K[i, j]
                b2 = b - Ej - y[i] * (alpha[i] - ai) * K[i, j] - y[j] * (alpha[j] - aj) * K[j, j]
                b = (b1 + b2) / 2 if 0 < alpha[i] < C else (b2 if 0 < alpha[j] < C else b1)
                n_changed += 1
        if n_changed == 0: break
    sv = alpha > 1e-5
    return alpha, b, sv

Xm, ym = make_moons(n_samples=200, noise=0.2, random_state=0)
Xs = StandardScaler().fit_transform(Xm)
alpha, b, sv = smo_simplified(Xs, 2 * ym - 1, C=1.0, gamma=1.0)
print(f"支持向量数: {sv.sum()} / {len(Xm)}")

教学版只动了第一个启发式(随机选 j),实际 LIBSVM 用 WSS1 + WSS2 双启发式,迭代更少。

5.3 Platt Scaling 把 SVM 输出转概率

from sklearn.svm import SVC
from sklearn.linear_model import LogisticRegression
import numpy as np

# SVC decision_function 给有符号距离,直接当概率用错
# 用 Platt Scaling:用 sigmoid 拟合 P(y=1|f(x))
clf = SVC(kernel='rbf', probability=False)  # 默认关
clf.fit(X_tr, y_tr)
f = clf.decision_function(X_te)  # 距离

# 方法 1: sklearn 内置(probability=True 时自动跑 5 折 CV)
clf2 = SVC(kernel='rbf', probability=True)
clf2.fit(X_tr, y_tr)
proba = clf2.predict_proba(X_te)[:, 1]
print(proba[:5])  # 真正概率

# 方法 2: 自己用 Logistic 拟合
lr = LogisticRegression().fit(f.reshape(-1, 1), y_te)  # 仅教学,实际应在 CV 内
p = lr.predict_proba(f.reshape(-1, 1))[:, 1]

probability=True 会让训练时间 +20% 左右(因为内嵌 5 折 CV 拟合 Platt 参数),推理略慢但能拿到可靠的概率输出,需要 predict_proba 时才开。

6. SVM vs 其他分类器

核心经验:SVM 在「特征维数高、样本中等、非线性可分、需要稀疏解」四条件同时成立时最有优势;一旦样本 > 10⁵,优先考虑 LinearSVC、GBDT 或神经网络。

6.1 五个真实数据集上的精度经验

规律:SVM 在高维稀疏(文本)和小到中等样本的表格上仍是强者;但数据规模一旦到百万级,GBDT 系开始反超;图像和文本已不是 SVM 的主战场(被神经网络替代)。

6.2 训练复杂度对比

这就是为什么 LinearSVC 比 SVC(RBF) 大规模数据快几个数量级——RBF 核 Gram 矩阵 O(n²) 内存,百万样本就 10¹² 字节,直接 OOM。

7. 常见坑

7.1 忘了 StandardScaler

症状:SVM 训练极慢、决策边界严重偏向大方差特征 原因:SVM 距离计算对方差敏感 修法:所有 SVM 调用前必走 StandardScaler().fit_transform(X)

7.2 把 LinearSVC 和 SVC(kernel=’linear’) 混用

症状:数据规模上 10⁵ 后训练极慢 修法:LinearSVC 基于 liblinear,大规模用 SGD;SVC(kernel=’linear’) 走 SMO,大规模不推荐

7.3 RBF γ 调到 0

症状:模型退化成「多数类预测器」,所有样本同一类 原因:γ=0 时 K 退化为常数矩阵,等价于没核 修法:gamma='scale'(sklearn 默认)= 1 / (d · Var(X)) 起步

7.4 γ 调到极大

症状:训练 acc 100%,测试 acc 50% 原因:每个样本自己成一个「聚类」,决策边界绕开所有样本 修法:把 γ 调小一两个数量级,或加大 C 收紧正则

7.5 predict() 返回的不是 label 而是距离

症状:看到 0.87, -0.34 这种数字以为是 label 修法:decision_function 给有符号距离,predict_proba 给概率(需 probability=True 启用 Platt scaling),predict 给 label

7.6 不平衡数据忘了 class_weight

症状:召回率低、模型全预测多数类 修法:SVC(class_weight='balanced') 或手动 dict({0:1, 1:n_neg/n_pos})

7.7 把 SVC 当回归用

症状:回归任务上训得很慢、效果差 修法:回归用 SVR 或 LinearSVR;SVR 引入 ε-insensitive 容忍带

7.8 没用交叉验证选 (C, γ)

症状:手调两个参数到 test 上 95%,K 折 CV 只有 78% 修法:永远 GridSearchCV 或 RandomizedSearchCV;推荐粗搜 → 细搜两步走

7.9 多分类用 OvR 还是 OvO

症状:SVC 默认 OvO,3 类问题训练 3 个二分类器;数据不平衡时模型偏向多数类 修法:decision_function_shape='ovr' 改为 OvR(快);不平衡时设 class_weight='balanced' 通用补救

7.10 把 SVC 部署到生产忘了存支持向量

症状:重新训练后预测分布漂移 修法:用 pickle.dump(clf, f) 存整个 fitted 模型(含支持向量),不要只存权重;推理直接 clf.predict(X_new)

8. 自检三问

A. 什么是支持向量?为什么 SVM 的决策边界只由它们决定?能否写出对应的 KKT 互补松弛条件?

要点:支持向量是训练集中 α_i > 0 的样本,位于间隔边界 y_i(w^T x_i + b) = 1 上;其它样本 α_i = 0,在对偶形式里不出现在 w = Σ α_i y_i x_i 中,所以决策边界只由支持向量决定。KKT 互补松弛:α_i · [y_i(w^T x_i + b) - 1] = 0,α_i > 0 ⇒ 约束「卡死」。详见 §1.3 + §3.2。

B. RBF 核的 γ 变大,模型会发生什么?从「有效半径」和「VC 维」两个角度答。

要点:γ = 1/(2σ²),γ 大 ⇒ σ 小 ⇒ 每个样本的「影响半径」缩短,决策边界被迫为每个训练样本画小圈,VC 维近似 = 支持向量数,模型复杂度爆炸,过拟合。γ 小则相反,边界过度平滑,欠拟合。最佳 γ 通过 CV 选。详见 §4.3。

C. 核技巧为什么不需要显式映射到高维?写出多项式核 K(x, z) = (γ x^T z + r)^d 的展开式说明哪些维度其实从未真正被计算。

要点:对偶形式里只用 ⟨x_i, x_j⟩,替换为 K(x_i, x_j) 即可,只要 K 是合法核(Mercer)。以多项式核 d=2 为例,展开 (γ x^T z + r)² = γ²(x^T z)² + 2γr x^T z + r²,对应特征空间包含 x_i², x_i x_j, 1 等 O(d²) 维,但我们从未显式算这些维度。详见 §4.1-4.2。

9. 推荐资源

视频

• StatQuest《SVM》合集 —— 从最大间隔到 RBF 核图解
• Andrew Ng CS229 Lecture 7 —— SVM 数学推导完整版
• 李宏毅《机器学习》SVM 章节 —— 中文直观

教科书

• 《统计学习导论》(ISLR) 第 9 章 —— 理论 + 实践平衡
• **《模式识别与机器学习》(PRML)》第 7 章 —— 核方法数学最严谨
• **《动手学机器学习》(D2L)》—— 含 sklearn 实现

论文

• Cortes & Vapnik 1995《Support-Vector Networks》 —— 软间隔 SVM 原论文
• Platt 1998《Sequential Minimal Optimization》 —— SMO 算法原论文
• Boser, Guyon, Vapnik 1992《A Training Algorithm for Optimal Margin Classifiers》 —— 核技巧引入
• Schölkopf 2001《The Kernel Trick for Distances》 —— 核函数几何性质

博客 / 课程

• Lilian Weng《SVM》 —— 从几何到对偶的完整推导笔记
• 《SVM 在 sklearn 文档》 —— 参数 + RBF 几何含义
• 《LIBSVM README》 —— 工业求解器作者视角
• Distill.pub《How to Use t-SNE Effectively》 —— 配套讲降维时常见的核视角

代码

• scikit-learn svm 模块 —— SVC / LinearSVC / NuSVC / SVR
• LIBSVM —— C++ 工业级实现
• liblinear —— 大规模线性 SVM
• cvxpy + 1-范数 SVM —— 教学用凸优化二次规划

10. 本节要点

• 几何直觉:SVM 找使两类间隔最大的超平面,几何间隔 = 2/‖w‖,目标 min ½‖w‖² 等价于最大化间隔。
• 支持向量:对偶变量 α_i > 0 的样本,位于间隔边界上,定义马路两个边线;决策边界只由它们决定,稀疏解是 SVM 的核心优势。
• 软间隔:松弛变量 ξ + 惩罚 C 把硬约束放松;C 越大越不容忍误分,等价 L2 正则强度。
• 对偶 + KKT:对偶问题只依赖 Gram 矩阵 ⟨x_i, x_j⟩;KKT 互补松弛直接给出 α_i > 0 ⇔ 支持向量;SMO 把大 QP 拆成两变量解析子问题。
• 核技巧:用 K(x, z) 直接替换内积,无需显式映射到高维;常见核 = 线性 / 多项式 / RBF / Sigmoid;合法核需满足 Mercer 条件(Gram 矩阵半正定)。
• RBF γ:γ 大 ⇒ 影响半径小 ⇒ 过拟合;γ 小 ⇒ 过度平滑 ⇒ 欠拟合;gamma='scale' 是 sklearn 默认起点。
• 实战铁律:必先 StandardScaler;(C, γ) 必须 CV 网格搜索;大规模数据用 LinearSVC / SGDClassifier;不平衡设 class_weight='balanced';回归用 SVR。

11. 下一节:Day 12 · 聚类与降维

主题:K-Means、PCA、t-SNE。覆盖:

• 无监督学习的两个核心任务:「找中心」(聚类)和「找主成分」(降维)
• K-Means 初始化:K-Means++ 用 D² 概率显著降低局部最优
• PCA = 协方差矩阵的特征值分解,新基 = 特征向量;特征缩放必做,否则量级大的特征绑架主成分
• t-SNE 是非线性的可视化工具,只保留局部邻居结构,簇间距离失真不能用于下游任务
• 评估:无标签用轮廓系数 (-1~1),有标签用 ARI / NMI

产出物:StandardScaler + PCA(95%) 流水线在 MNIST 上降到 50 维再 K-Means,可视化 t-SNE 2D 嵌入。

作者:林馨予 + 林晓月 最后更新:2026-07-04 版权:CC BY-NC-SA 4.0