支持向量机:在两类之间画最宽的街

支持向量机:在两类之间画最宽的街

本节摘要:支持向量机(Support Vector Machine, SVM)的核心理念只有一句——在两类数据之间找到最宽的「街」。给你两类点,能分开它们的直线有无穷多条,该选哪一条?选间隔(Margin)最大的那条:决策边界到两侧最近点的距离越宽,分类器越自信、泛化越好。SVM 是深度学习崛起前统治 ML 的算法,在 20 世纪 90 年代末到 2010 年代初称王。今天它在小数据集、高维稀疏数据(如 TF-IDF 文本)、需要数学保证的场景仍是首选。本节将从零实现线性 SVM(铰链损失 + L2 正则 + 梯度下降的原始形式),讲透最大间隔、支持向量、软间隔与 C 参数的权衡、铰链损失与对数损失之别,再用对偶形式引出核技巧(Kernel Trick)——如何不显式映射到高维空间就能学到任意非线性边界。

学习目标

阅读完本节,你应当能够:

1. 用铰链损失(Hinge Loss)和梯度下降在原始形式上从零实现线性 SVM。
2. 解释最大间隔(Maximum Margin)原理,并从训练好的模型中识别支持向量。
3. 对比线性、多项式、RBF 核,解释核技巧如何避免显式高维映射。
4. 评估 C 参数在间隔宽度与分类错误之间的权衡。

一、问题与直觉

你有两类数据点,需要画一条线(或超平面)把它们分开。能用的线有无穷多条,该选哪条?

选间隔最大的那条。间隔是决策边界到两侧最近点的距离。间隔越宽,分类器越自信,对未见数据泛化越好。

这个直觉引出 SVM,ML 里数学上最优雅的算法之一。深度学习之前,SVM 是统治性的分类方法,如今仍是小数据集、高维数据、需要原理清晰且有理论保证的问题的最佳选择。

SVM 直接呼应第 1 章:优化是凸的(第 18 节),间隔用范数度量(第 14 节),核技巧利用点积处理非线性边界,却从不在高维空间里计算。

最大间隔分类器

给定线性可分数据,标签 y_i ∈ {-1, +1},特征向量 x_i,我们要一个超平面 w^T x + b = 0 分开两类。

点 x_i 到超平面的距离:

distance = |w^T x_i + b| / ||w||
​

对正确分类的点:y_i * (w^T x_i + b) > 0。间隔是超平面到两侧最近点距离的两倍。

优化问题:

maximize    2 / ||w||     (间隔宽度)
subject to  y_i * (w^T x_i + b) >= 1  对所有 i
​

等价地(最小化 ||w||² 更好优化):

minimize    (1/2) ||w||^2
subject to  y_i * (w^T x_i + b) >= 1  对所有 i
​

这是凸二次规划,有唯一全局解。恰好落在间隔边界上(y_i * (w^T x_i + b) = 1)的数据点是支持向量。只有它们决定决策边界。移动或删除任何非支持向量点,边界都不变。

支持向量:关键的少数

大多数训练点无关紧要,只有支持向量算数。这就是 SVM 预测时省内存的原因:只需存支持向量,不用存整个训练集。

支持向量的数量还给出泛化误差上界。相对于数据集规模,支持向量越少,泛化越好。

软间隔:用 C 参数处理噪声

真实数据极少完美可分。有些点可能在边界错误一侧,或在间隔内部。软间隔形式用松弛变量允许违规。

minimize    (1/2) ||w||^2 + C * sum(xi_i)
subject to  y_i * (w^T x_i + b) >= 1 - xi_i
            xi_i >= 0  对所有 i
​

松弛变量 xi_i 度量点 i 多大程度违反间隔。C 控制权衡:

C 是正则化强度的倒数。大 C = 弱正则,小 C = 强正则。

铰链损失:SVM 的损失函数

软间隔 SVM 可改写为无约束优化:

minimize    (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b)))
​

max(0, 1 - y_i * f(x_i)) 就是铰链损失。点正确分类且在间隔外时它为零;在间隔内或被误分时它线性增长。

单点铰链损失:

loss
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

y*f(x) >= 1(正确分类且在间隔外)时损失为 0。
y*f(x) < 1 时线性惩罚。
​

对比逻辑回归的逻辑损失:

铰链:     max(0, 1 - y*f(x))          间隔处硬截断
逻辑:     log(1 + exp(-y*f(x)))        光滑,永不为零
​

铰链损失产生稀疏解(只有支持向量贡献非零)。逻辑损失用到所有点。这让 SVM 预测时更省内存。

用梯度下降训练线性 SVM

可以在铰链损失加 L2 正则上用梯度下降训练线性 SVM,无需解约束 QP:

L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b)))

对 w 的梯度:
  若 y_i * (w^T x_i + b) >= 1:  dL/dw = lambda * w
  若 y_i * (w^T x_i + b) < 1:   dL/dw = lambda * w - y_i * x_i

对 b 的梯度:
  若 y_i * (w^T x_i + b) >= 1:  dL/db = 0
  若 y_i * (w^T x_i + b) < 1:   dL/db = -y_i
​

这叫原始形式(Primal)。每个 epoch O(n * d),n 是样本数、d 是特征数。对大型稀疏高维数据(文本分类)很快。

对偶形式与核技巧

SVM 问题的拉格朗日对偶(第 1 章第 18 节 KKT 条件)是:

maximize    sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j))
subject to  0 <= alpha_i <= C
            sum(alpha_i * y_i) = 0
​

对偶只涉及数据点之间的点积 x_i . x_j。这是关键洞见:把每个点积换成核函数 K(x_i, x_j),SVM 就能学非线性边界,却从不必显式计算那个变换。

线性核:      K(x, z) = x . z
多项式核:    K(x, z) = (x . z + c)^d
RBF(高斯):  K(x, z) = exp(-gamma * ||x - z||^2)
​

RBF 核把数据映射到无穷维空间。输入空间里靠近的点核值接近 1,远离的点核值接近 0。它能学任何光滑决策边界。

核技巧在高维空间算点积,却从不去那里。对 D 维的 d 次多项式核,显式特征空间有 O(D^d) 维,但 K(x, z) 只用 O(D) 时间算出来。

SVM 用于回归(SVR)

支持向量回归(SVR)在数据周围拟合一个宽度为 epsilon 的管。管内的点损失为零,管外的点被线性惩罚。

minimize    (1/2) ||w||^2 + C * sum(xi_i + xi_i*)
subject to  y_i - (w^T x_i + b) <= epsilon + xi_i
            (w^T x_i + b) - y_i <= epsilon + xi_i*
            xi_i, xi_i* >= 0
​

epsilon 控制管宽。管越宽 = 支持向量越少 = 拟合越光滑;管越窄 = 支持向量越多 = 拟合越紧。

SVM 为何输给深度学习(以及何时仍胜)

SVM 在 20 世纪 90 年代末到 2010 年代初统治 ML。深度学习因以下原因超越它:

SVM 在这些情况仍胜:

• 小数据集(几百到几千样本)
• 高维稀疏数据(TF-IDF 特征的文本)
• 需要数学保证(间隔界)
• 训练时间必须最短(线性 SVM 很快)
• 有清晰间隔结构的二分类
• 异常检测(单类 SVM)

二、从零实现

第 1 步:铰链损失与梯度

基础。为一批数据算铰链损失及其梯度。

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n
​

第 2 步:梯度下降训练线性 SVM

最小化正则化铰链损失,无需 QP 求解器。

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]
​

第 3 步:核函数

实现线性、多项式、RBF 核。

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))
​

第 4 步:间隔与支持向量识别

训练后,识别哪些点是支持向量,并算间隔宽度。

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors
​

完整实现(含全部演示)见 code/svm.py。

三、框架对比

用 scikit-learn:

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
print(f"Support vectors: {clf['svm'].n_support_}")
​

⚠️ 训练 SVM 前务必缩放特征。SVM 对特征量级敏感,因为间隔依赖 ||w||,未缩放的特征扭曲几何。

对大数据集,用 LinearSVC(原始形式,每 epoch O(n))而非 SVC(对偶形式,O(n²)~O(n³)):

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])
​

四、可复用产物

本节的从零实现位于 code/svm.py,含铰链损失、线性 SVM 训练器、三种核函数、支持向量识别和可视化演示。把它当模板,套用到自己的二分类问题上,观察 C、gamma、核选择如何影响决策边界和支持向量数量。

五、练习

1. 生成一个二维线性可分数据集,训练 LinearSVM 并识别支持向量,验证它们就是离决策边界最近的点。
2. 在噪声数据集上把 C 从 0.001 调到 1000,画出每个 C 值的决策边界,观察从宽间隔(欠拟合)到窄间隔(过拟合)的过渡。
3. 造一个圆形类别边界(非线形)的数据集,展示线性 SVM 失败;计算 RBF 核矩阵,展示在核诱导的特征空间里两类变得可分。
4. 在同一数据集上对比铰链损失与逻辑损失,训练线性 SVM 与逻辑回归,数一数各有多少训练点对决策边界有贡献(支持向量 vs 全部点)。
5. 实现 SVR(epsilon 不敏感损失),拟合 y = sin(x) + 噪声,画出预测周围的 epsilon 管,高亮支持向量(管外的点)。

本节要点回顾

1. SVM 找最宽的街:在所有能分开两类的超平面里,选间隔最大的那个,泛化最好。
2. 支持向量是关键少数:只有落在间隔边界上的点决定超平面,其余点无关,预测时只需存支持向量。
3. 软间隔用 C 权衡:大 C 间隔窄误分少易过拟合,小 C 间隔宽误分多易欠拟合;C 是正则化强度的倒数。
4. 铰链损失稀疏:max(0,1-y*f(x)),间隔外为零、间隔内线性;逻辑损失光滑且永不为零,SVM 因稀疏更省内存。
5. 原始形式可梯度下降:铰链损失 + L2 正则,每 epoch O(n*d),对稀疏高维文本很快。
6. 对偶只含点积:这为核技巧铺路,把每个点积换成核函数即得非线性 SVM。
7. 核技巧免高维映射:RBF 映无穷维、多项式映 O(D^d) 维,但 K(x,z) 都只需 O(D) 时间。
8. SVR 拟合 epsilon 管:管内零损失、管外线性惩罚,epsilon 控制光滑度。
9. SVM 何时仍胜:小数据、高维稀疏文本、需数学保证、训练时间敏感、有清晰间隔的二分类、单类异常检测——深度学习在这些场景反而不占优。

下一节,我们换一种「懒」思路——k 近邻不学习任何模型,预测时直接查最近的邻居,顺便吃透欧氏、曼哈顿、余弦等距离度量的本质。