AI 原生开放教材

外观

AI 工程从零到一（中文）源码研读·中文原文 ↗原件 ↓仓库 ↗

支持向量机 ​

在两个类之间找出最宽的那条街。这就是全部思想。

类型： Build 语言： Python 前置要求： 阶段 1（第 08 课优化、第 14 课范数与距离、第 18 课凸优化） 预计时间： ~90 分钟

学习目标 ​

  • 用 hinge loss 在原始形式上做梯度下降，从零实现一个线性 SVM
  • 解释最大间隔原则，并从训练好的模型里识别支持向量
  • 对比线性、多项式和 RBF 核，解释核技巧如何避免显式的高维映射
  • 评估 C 参数在间隔宽度和分类错误之间所控制的权衡

问题背景 ​

你有两类数据点，需要画一条线（或超平面）把它们分开。可行的线有无穷多条。你该挑哪一条？

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

这个直觉引出了支持向量机，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。间隔是超平面到任一侧最近点距离的两倍。

mermaid
graph LR
    subgraph Margin
        direction TB
        A["w^T x + b = +1"] ~~~ B["w^T x + b = 0"] ~~~ C["w^T x + b = -1"]
    end
    D["+ 类的点"] --> A
    E["- 类的点"] --> C
    B --- F["决策边界"]

优化问题：

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

等价地（最小化 ||w||^2 更好优化）：

minimize    (1/2) ||w||^2
subject to  y_i * (w^T x_i + b) >= 1  for all i

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

支持向量：关键的少数 ​

mermaid
graph TD
    subgraph Classification
        SV1["支持向量（+ 类）<br>y(w'x+b) = 1"] --- DB["决策边界<br>w'x+b = 0"]
        DB --- SV2["支持向量（- 类）<br>y(w'x+b) = 1"]
    end
    O1["其他 + 点<br>（不影响边界）"] -.-> SV1
    O2["其他 - 点<br>（不影响边界）"] -.-> SV2

大多数训练点都无关紧要，只有支持向量重要。这就是为什么 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  for all i

松弛变量 xi_i 衡量点 i 违反间隔的程度。C 控制权衡：

C 取值行为
C 大重罚违规。窄间隔，更少误分类。过拟合
C 小允许更多违规。宽间隔，更多误分类。欠拟合

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

Hinge loss：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)) 就是 hinge loss。当点被正确分类且在间隔之外时它为零。当点落在间隔内或被误分类时它是线性的。

单个点的 hinge loss：

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

y*f(x) >= 1 时（正确分类、间隔之外）损失为零。
y*f(x) < 1 时线性惩罚。

和 logistic loss（逻辑回归）对比：

Hinge:     max(0, 1 - y*f(x))          在间隔处硬截断
Logistic:  log(1 + exp(-y*f(x)))        平滑，永不恰好为零

hinge loss 产生稀疏解（只有支持向量有非零贡献）。logistic loss 用到所有数据点。这让 SVM 在预测时更省内存。

用梯度下降训练线性 SVM ​

你可以在 hinge loss 加 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 formulation）。每个 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 就能学到非线性边界，而全程不用显式计算那个变换。

Linear kernel:      K(x, z) = x . z
Polynomial kernel:  K(x, z) = (x . z + c)^d
RBF (Gaussian):     K(x, z) = exp(-gamma * ||x - z||^2)

RBF 核把数据映射到一个无限维空间。在输入空间里靠得近的点，核值接近 1；离得远的点，核值接近 0。它能学到任意平滑的决策边界。

mermaid
graph LR
    subgraph "输入空间（不可分）"
        A["二维数据点<br>圆形边界"]
    end
    subgraph "特征空间（可分）"
        B["更高维的数据点<br>线性边界"]
    end
    A -->|"核技巧<br>K(x,z) = phi(x).phi(z)"| B

核技巧在高维空间里计算点积，却从不真的进入那个空间。对于 D 维空间里 d 次的多项式核，显式特征空间有 O(D^d) 维。但 K(x, z) 在 O(D) 时间内就能算出来。

用于回归的 SVM（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 为什么输给了深度学习（以及它何时仍然赢） ​

从 1990 年代末到 2010 年代初，SVM 统治着 ML。深度学习超越它有几个原因：

因素SVM深度学习
特征工程需要自己学特征
可扩展性核方法是 O(n^2) 到 O(n^3)用 SGD 时每 epoch O(n)
图像/文本/音频需要手工特征从原始数据学
大数据集（>10 万）慢扩展性好
GPU 加速收益有限大幅加速

SVM 在这些场景仍然赢：

  • 小数据集（几百到几千个样本）
  • 高维稀疏数据（带 TF-IDF 特征的文本）
  • 你需要数学保证时（间隔界）
  • 训练时间必须极短时（线性 SVM 非常快）
  • 有清晰间隔结构的二分类
  • 异常检测（单类 SVM）
figure
svm-margin

动手构建 ​

第 1 步：hinge loss 和梯度 ​

基础。为一个批次计算 hinge loss 及其梯度。

python
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 ​

通过最小化正则化 hinge loss 来训练。不需要 QP 求解器。

python
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 核。

python
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 步：间隔和支持向量识别 ​

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

python
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：

python
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^2) 到 O(n^3)）：

python
from sklearn.svm import LinearSVC

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

练习 ​

  1. 生成一个二维线性可分数据集。训练你的 LinearSVM，识别支持向量。验证支持向量正是离决策边界最近的那些点。

  2. 在一个有噪声的数据集上让 C 从 0.001 变到 1000。为每个 C 值画出决策边界。观察从宽间隔（欠拟合）到窄间隔（过拟合）的转变。

  3. 造一个类边界是圆形（非线性）的数据集。说明线性 SVM 会失败。计算 RBF 核矩阵，说明在核诱导的特征空间里两类变得可分。

  4. 在同一数据集上对比 hinge loss 和 logistic loss。训练一个线性 SVM 和一个逻辑回归。数一数有多少训练点对各自模型的决策边界有贡献（支持向量 vs 全部点）。

  5. 实现 SVR（epsilon 不敏感损失）。把它拟合到 y = sin(x) + 噪声。画出预测周围的 epsilon 管子，并高亮支持向量（管子外的点）。

关键术语 ​

术语它实际是什么
支持向量离决策边界最近的训练点。唯一决定超平面的点
间隔决策边界到最近支持向量的距离。SVM 要把它最大化
Hinge lossmax(0, 1 - y*f(x))。正确分类且在间隔外时为零，否则线性惩罚
C 参数间隔宽度和分类错误之间的权衡。C 大 = 窄间隔，C 小 = 宽间隔
软间隔通过松弛变量允许间隔违规的 SVM 形式。能处理不可分数据
核技巧在高维特征空间里计算点积，而不显式映射到那个空间
线性核K(x, z) = x . z。等价于标准点积。用于线性可分数据
RBF 核K(x, z) = exp(-gamma * ||x-z||^2)。映射到无限维。学任意平滑边界
多项式核K(x, z) = (x . z + c)^d。映射到多项式组合的特征空间
对偶形式SVM 问题的重新表述，只依赖数据点之间的点积。让核成为可能
SVR支持向量回归。在数据周围拟合一个 epsilon 管子。管子内的点损失为零
松弛变量xi_i：衡量一个点违反间隔的程度。对间隔外正确分类的点为零
最大间隔选择那个使到各类最近点距离最大化的超平面的原则

延伸阅读 ​