支持向量机 SVM：最大间隔分类器

支持向量机（Support Vector Machine，简称 SVM）是机器学习中最经典的二分类算法之一。它的核心思想可以用一句话概括：在所有能把正负样本分开的超平面中，选择那个离两类样本都最远的。

这个直觉非常优雅。想象你在桌子上放了两堆不同颜色的豆子，你想用一根筷子把它们分开。你可以放很多种位置，但最好的放法是让这根筷子离两堆豆子都尽量远——这样即使有轻微的扰动（豆子滚动了一点），分类结果也不会改变。

超平面是 SVM 的决策边界。在二维空间中，它就是一条直线；在三维空间中，它是一个平面；在更高维空间中，它被称为超平面。超平面的数学表达是：wᵀx + b = 0，其中 w 是法向量（决定超平面的方向），b 是偏置项（决定超平面的位置）。

间隔（Margin）是指超平面到最近样本点的距离。SVM 的目标是最大化这个间隔。那些恰好落在间隔边界上的样本点，就是著名的支持向量（Support Vectors）。它们是「支撑」着这个最大间隔的关键样本——去掉其他样本不影响模型，但去掉支持向量会改变决策边界。

SVM 的优势在于：它只依赖于支持向量，具有天然的泛化能力；它通过核技巧可以处理非线性分类问题；它的优化目标是凸优化问题，保证能找到全局最优解而不是局部最优解。这些特性使得 SVM 在深度学习时代之前，长期是分类任务的首选算法。

理解 SVM 的最好方式是看它的决策过程。下图展示了 SVM 在不同场景下的行为。

要理解 SVM 的数学推导，我们需要从几何间隔和函数间隔的概念开始。

对于一个样本点 (xᵢ, yᵢ)（其中 yᵢ ∈ {+1, -1} 是类别标签），它到超平面 wᵀx + b = 0 的几何距离是 |wᵀxᵢ + b| / ||w||。SVM 要求所有样本都被正确分类，即 yᵢ(wᵀxᵢ + b) > 0，并且要求这个距离至少达到某个值。

为了简化优化问题，我们引入函数间隔的概念：ŷᵢ = yᵢ(wᵀxᵢ + b)。通过缩放约束（令最小函数间隔等于 1），SVM 的优化目标可以写成：

最小化 ||w||² / 2，约束条件为 yᵢ(wᵀxᵢ + b) ≥ 1（对所有样本 i）。

这个形式非常优雅：目标函数是凸的二次函数，约束是线性不等式，这是一个标准的凸二次规划问题。这意味着我们可以使用成熟的优化算法（如 SMO、内点法）找到全局最优解。

对偶问题是 SVM 推导中的关键一步。通过引入拉格朗日乘子 αᵢ，我们将原始问题（Primal）转化为对偶问题（Dual）：

最大化 Σαᵢ - ½ΣΣαᵢαⱼyᵢyⱼ(xᵢᵀxⱼ)，约束条件为 αᵢ ≥ 0 且 Σαᵢyᵢ = 0。

对偶形式的重要性在于：它揭示了 SVM 决策只依赖于样本之间的内积 xᵢᵀxⱼ，这为后续的核技巧奠定了理论基础。同时，根据 KKT 条件，只有支持向量对应的 αᵢ 才大于零，其他样本的 αᵢ 都为零——这就是 SVM 的稀疏性。

# SVM 原始问题与对偶问题的推导演示
import numpy as np
from scipy.optimize import minimize

def svm_primal_objective(params, X, y):
    """
    原始问题：最小化 ||w||²/2
    约束：yᵢ(wᵀxᵢ + b) ≥ 1
    """
    w = params[:-1]
    b = params[-1]
    return 0.5 * np.dot(w, w)

def svm_constraint(params, X, y):
    """约束函数：yᵢ(wᵀxᵢ + b) - 1 ≥ 0"""
    w = params[:-1]
    b = params[-1]
    return y * (X @ w + b) - 1

# 生成简单的二维线性可分数据
np.random.seed(42)
X_pos = np.random.randn(50, 2) + np.array([2, 2])
X_neg = np.random.randn(50, 2) - np.array([2, 2])
X = np.vstack([X_pos, X_neg])
y = np.concatenate([np.ones(50), -np.ones(50)])

# 使用 scipy 求解原始问题
initial_params = np.zeros(3)  # w1, w2, b
constraints = {'type': 'ineq', 'fun': lambda p: svm_constraint(p, X, y)}
result = minimize(svm_primal_objective, initial_params,
                  args=(X, y), constraints=constraints)

w_opt = result.x[:-1]
b_opt = result.x[-1]
print(f"最优 w: {w_opt}")
print(f"最优 b: {b_opt}")
print(f"间隔大小: {2 / np.linalg.norm(w_opt):.4f}")

SVM 最强大的特性之一是核技巧（Kernel Trick）。它允许我们在不显式计算高维特征映射的情况下，在高维特征空间中进行线性分类。

核心思想是：如果原始数据在低维空间中线性不可分，我们可以将数据映射到一个更高维的空间，在那里它们可能就变得线性可分了。但直接计算高维映射的计算量可能非常大（甚至无穷维）。核函数提供了一种聪明的替代方案：我们不需要显式地做映射，只需要计算样本之间的某种内积替代——核函数 K(xᵢ, xⱼ)。

常用的核函数包括：

线性核（Linear Kernel）：K(xᵢ, xⱼ) = xᵢᵀxⱼ。等价于不做映射，适用于线性可分的情况。计算最快，是高维稀疏数据（如文本分类）的首选。

多项式核（Polynomial Kernel）：K(xᵢ, xⱼ) = (γxᵢᵀxⱼ + r)ᵈ。其中 d 是多项式阶数，γ 和 r 是可调参数。当 d = 1 时退化为线性核。多项式核可以捕捉特征之间的交互关系。

高斯核 / RBF 核（Radial Basis Function Kernel）：K(xᵢ, xⱼ) = exp(-γ||xᵢ - xⱼ||²)。这是最常用的核函数。它将数据映射到无穷维空间。参数 γ 控制核函数的宽度：γ 越大，单个样本的影响范围越小，模型越复杂（容易过拟合）；γ 越小，模型越平滑（容易欠拟合）。

Sigmoid 核：K(xᵢ, xⱼ) = tanh(γxᵢᵀxⱼ + r)。形式上类似于神经网络中的激活函数。在某些情况下表现良好，但不如 RBF 核常用。

核技巧的数学保证来自 Mercer 定理：只要核函数满足正半定性（即对应的核矩阵是半正定的），它就对应某个（可能是无穷维的）特征空间中的内积。

在实际应用中，RBF 核通常是默认选择——它几乎在所有数据集上都能取得不错的效果。但如果你的数据维度很高（比如文本分类中的 TF-IDF 向量），线性核可能更快且效果相当。

# 核函数的可视化比较
import numpy as np
import matplotlib.pyplot as plt

def linear_kernel(x, y):
    return np.dot(x, y)

def polynomial_kernel(x, y, degree=3, gamma=1.0, coef0=0.0):
    return (gamma * np.dot(x, y) + coef0) ** degree

def rbf_kernel(x, y, gamma=1.0):
    return np.exp(-gamma * np.linalg.norm(x - y) ** 2)

def sigmoid_kernel(x, y, gamma=1.0, coef0=0.0):
    return np.tanh(gamma * np.dot(x, y) + coef0)

# 在 1D 上可视化不同核函数
x = np.linspace(-3, 3, 200)
y = np.zeros_like(x)  # 参考点

kernels = {
    'Linear': lambda t: linear_kernel(t, y),
    'Polynomial (d=2)': lambda t: polynomial_kernel(t, y, degree=2),
    'RBF (γ=0.5)': lambda t: rbf_kernel(t, y, gamma=0.5),
    'RBF (γ=2.0)': lambda t: rbf_kernel(t, y, gamma=2.0),
    'Sigmoid': lambda t: sigmoid_kernel(t, y),
}

fig, axes = plt.subplots(1, 5, figsize=(20, 4))
for ax, (name, kernel_fn) in zip(axes, kernels.items()):
    ax.plot(x, [kernel_fn(t) for t in x])
    ax.axhline(y=0, color='k', linestyle='--', alpha=0.3)
    ax.set_title(name)
    ax.grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

面对不同的数据集，如何选择合适的核函数？下面的决策树可以帮助你做出决策。

在现实世界中，数据往往不是完美线性可分的。有些样本会落在错误的区域，或者存在异常值（outliers）。硬间隔 SVM（要求所有样本都必须被正确分类）在这些情况下会失败——要么无解，要么因为一个异常值而产生极端的决策边界。

软间隔 SVM（Soft Margin SVM）通过引入松弛变量（Slack Variables）ξᵢ 来解决这个问题。它允许某些样本违反间隔约束，但需要为此付出代价。

优化目标变为：最小化 ||w||²/2 + C·Σξᵢ，约束条件为 yᵢ(wᵀxᵢ + b) ≥ 1 - ξᵢ 且 ξᵢ ≥ 0。

这里的关键参数是 C（正则化参数），它控制了间隔最大化和分类错误之间的权衡：

C 很大（比如 1000）：模型对分类错误零容忍，几乎等同于硬间隔 SVM。间隔会很窄，模型可能过拟合。

C 很小（比如 0.001）：模型允许更多的分类错误，追求更大的间隔。间隔会很宽，模型可能欠拟合。

C 的选择是 SVM 调参的核心。通常的取值范围是 0.01 到 1000，在对数尺度上搜索（0.01, 0.1, 1, 10, 100, 1000）。

软间隔 SVM 的对偶形式与硬间隔类似，唯一的区别是拉格朗日乘子 αᵢ 有了上界：0 ≤ αᵢ ≤ C。这个上界直接对应了 C 的作用——它限制了单个样本对决策边界的影响力。

在损失函数的视角下，软间隔 SVM 等价于使用 Hinge Loss 加上 L2 正则化的优化问题：

最小化 (1/n)Σmax(0, 1 - yᵢf(xᵢ)) + λ||w||²

其中 max(0, 1 - yᵢf(xᵢ)) 就是 Hinge Loss。当样本被正确分类且间隔足够大时（yᵢf(xᵢ) ≥ 1），损失为零。否则，损失与违规程度成正比。

Hinge Loss 的特点是：它只关心「是否足够正确地分类」，而不关心「正确到什么程度」。一旦样本被正确分类且间隔达标，再增加间隔也不会减少损失。这与逻辑回归使用的 Log Loss 不同——Log Loss 即使对正确分类的样本也会继续减小损失（只是减小得很慢）。

# Hinge Loss vs Log Loss 对比
import numpy as np
import matplotlib.pyplot as plt

z = np.linspace(-2, 3, 300)

# Hinge Loss: max(0, 1 - z)
hinge_loss = np.maximum(0, 1 - z)

# Log Loss (Logistic): log(1 + exp(-z))
log_loss = np.log(1 + np.exp(-z))

# Zero-One Loss (理想但不可导)
zero_one_loss = (z < 0).astype(float)

plt.figure(figsize=(10, 6))
plt.plot(z, zero_one_loss, 'k--', linewidth=2, label='0-1 Loss（理想）')
plt.plot(z, hinge_loss, 'b-', linewidth=2.5, label='Hinge Loss（SVM）')
plt.plot(z, log_loss, 'r-', linewidth=2.5, label='Log Loss（逻辑回归）')
plt.axvline(x=1, color='g', linestyle='--', alpha=0.5, label='间隔边界')
plt.axvline(x=0, color='gray', linestyle='--', alpha=0.3, label='决策边界')
plt.xlabel('y·f(x)（函数间隔）')
plt.ylabel('Loss')
plt.title('不同损失函数的对比')
plt.legend()
plt.grid(True, alpha=0.3)
plt.ylim(0, 3)
plt.show()

# 分析：Hinge Loss 在 z > 1 时为零（正确分类且有足够间隔）
# 而 Log Loss 即使在 z 很大时也趋近于零但永不为零
print("Hinge Loss 的关键特性：")
print("- 对正确分类且有足够间隔的样本，损失为零")
print("- 只惩罚间隔不足的样本，不惩罚过度正确的样本")
print("- 这使得 SVM 具有稀疏性（只有支持向量有贡献）")

SVM 的对偶问题是一个凸二次规划问题，理论上可以使用通用的 QP 求解器。但对于大规模数据集（几十万甚至上百万样本），通用 QP 求解器的计算复杂度是 O(n³) 到 O(n⁴)，完全不实用。

SMO 算法（Sequential Minimal Optimization）是 John Platt 在 1998 年提出的专门用于求解 SVM 对偶问题的高效算法。它的核心思想是：每次只优化两个拉格朗日乘子 αᵢ 和 αⱼ，而固定其他所有乘子。为什么是两个？因为约束条件 Σαᵢyᵢ = 0 意味着至少需要同时调整两个乘子才能保持约束满足。

SMO 的优势在于：两个变量的子问题有解析解（闭式解），不需要数值优化。这大大降低了计算复杂度。SMO 的实际复杂度通常在 O(n²) 到 O(n³) 之间，对于稀疏数据可以接近 O(n)。

现代 SVM 实现（如 LIBSVM、scikit-learn 的 SVC）通常使用 SMO 的改进版本，加入了以下优化：

工作集选择（Working Set Selection）：不是随机选择两个乘子，而是选择最违反 KKT 条件的乘子对。这加速了收敛。

缓存机制（Kernel Cache）：核函数值的计算很耗时，缓存最近使用的核矩阵元素可以减少重复计算。

收缩启发式（Shrinking）：在优化过程中，某些乘子已经收敛到最优值，可以将它们从优化问题中移除，减小问题规模。

对于超大规模数据集（百万级以上），线性 SVM 可以使用 SGD（随机梯度下降）或 坐标下降（Coordinate Descent）算法。scikit-learn 中的 LinearSVC 和 SGDClassifier(loss='hinge') 就是这类实现，它们的复杂度是 O(n)，适合大数据场景。

多分类 SVM 的实现策略有两种：

One-vs-Rest（OvR）：训练 K 个二分类器（K 是类别数），每个分类器将一个类别与其余所有类别分开。预测时选择得分最高的分类器对应的类别。

One-vs-One（OvO）：训练 K(K-1)/2 个二分类器，每对类别之间训练一个分类器。预测时通过投票决定最终类别。

LIBSVM 默认使用 OvO，因为它在训练样本不均衡时表现更好。但 OvR 的训练成本更低（K vs K²/2 个分类器），在类别数很多时更有优势。

本节通过一个完整的分类任务，演示如何使用 scikit-learn 实现 SVM 分类，并进行系统的超参数调优。

我们以经典的 Iris 数据集为例，但会扩展到一个更复杂的场景：手写数字识别（MNIST 的子集），展示 SVM 在处理高维数据时的表现。

首先，我们比较不同核函数在同一个数据集上的表现。然后，我们使用网格搜索（Grid Search）和交叉验证（Cross-Validation）来找到最优的超参数组合。最后，我们分析支持向量的分布，理解模型学到了什么。

在特征预处理方面，SVM 对特征缩放极其敏感。如果特征的尺度差异很大（比如一个特征的范围是 [0, 1]，另一个是 [0, 10000]），那么尺度大的特征会主导核函数的计算。因此，标准化（StandardScaler）或归一化（MinMaxScaler）是 SVM 的必备步骤。

调参的系统方法：

1. 先标准化数据（StandardScaler）
2. 选择核函数（先试 RBF）
3. 用对数尺度的网格搜索调 C 和 γ
4. 用交叉验证评估
5. 在测试集上报告最终结果

# SVM 完整实战：从预处理到调参到评估
from sklearn import datasets
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.metrics import classification_report, confusion_matrix
import numpy as np

# 1. 加载数据：手写数字识别（简化版，只使用前两类）
digits = datasets.load_digits()
X = digits.data
y = digits.target

# 取前 4 类做一个多分类任务
mask = y < 4
X, y = X[mask], y[mask]

# 2. 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

# 3. 特征标准化（SVM 必须！）
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

print(f"训练集: {X_train_scaled.shape}, 测试集: {X_test_scaled.shape}")
print(f"特征维度: {X_train_scaled.shape[1]} (64 维图像像素)")

# 4. 基线模型：默认参数的 RBF 核 SVM
baseline_svm = SVC(kernel='rbf', random_state=42)
baseline_svm.fit(X_train_scaled, y_train)
baseline_acc = baseline_svm.score(X_test_scaled, y_test)
print(f"\n基线 SVM (默认参数) 准确率: {baseline_acc:.4f}")
print(f"支持向量数量: {len(baseline_svm.support_vectors_)} / {len(X_train_scaled)}")

# 5. 网格搜索调参
param_grid = {
    'C': [0.01, 0.1, 1, 10, 100],
    'gamma': ['scale', 'auto', 0.001, 0.01, 0.1, 1],
    'kernel': ['rbf', 'linear', 'poly']
}

grid_search = GridSearchCV(
    SVC(random_state=42),
    param_grid,
    cv=5,
    scoring='accuracy',
    n_jobs=-1,
    verbose=1
)
grid_search.fit(X_train_scaled, y_train)

print(f"\n最优参数: {grid_search.best_params_}")
print(f"交叉验证最优准确率: {grid_search.best_score_:.4f}")

best_svm = grid_search.best_estimator_
test_acc = best_svm.score(X_test_scaled, y_test)
print(f"测试集准确率: {test_acc:.4f}")

# 6. 详细评估
y_pred = best_svm.predict(X_test_scaled)
print(f"\n分类报告:")
print(classification_report(y_test, y_pred))

# 7. 分析支持向量
print(f"\n支持向量分析:")
print(f"总支持向量: {len(best_svm.support_vectors_)}")
for cls in range(4):
    sv_count = np.sum(best_svm.support_ == cls)
    print(f"  类别 {cls}: {sv_count} 个支持向量")

SVM 不是万能的。在不同的场景下，不同的算法各有优劣。理解 SVM 的适用场景和局限性，比盲目使用它更重要。

SVM vs 逻辑回归：

逻辑回归和线性 SVM 在很多情况下表现相近。主要区别在于：逻辑回归输出的是概率估计（通过 Sigmoid 函数），而 SVM 输出的是类别标签和决策函数值。如果你需要概率输出（比如医疗诊断中的风险评分），逻辑回归更合适。如果你只关心分类边界，SVM 的最大间隔特性可能带来更好的泛化能力。

在计算效率方面，逻辑回归训练更快（可以使用 SGD），而 SVM 需要解二次规划问题。对于超大规模数据，逻辑回归 + SGD 是更好的选择。

SVM vs 决策树/随机森林：

决策树和随机森林的优势在于：不需要特征缩放、可以处理类别特征、提供特征重要性、对异常值鲁棒。SVM 在这些方面都不占优。

但 SVM 的优势在于：在高维空间中的表现通常更好（尤其是使用核函数时）、对过拟合的控制更精确（通过 C 参数）、在小样本高维度场景下表现优异。

SVM vs 神经网络：

深度学习兴起后，SVM 在很多领域被神经网络取代。但 SVM 仍有其不可替代的优势：

小数据集（几百到几千样本）：神经网络需要大量数据才能发挥威力，而 SVM 在小数据集上往往表现更好。

可解释性：SVM 的决策边界是显式的超平面（线性核）或核函数的组合（RBF 核），而神经网络的决策过程是黑箱的。

计算效率：训练 SVM 通常比训练神经网络快得多，尤其是在不需要核函数的情况下。

凸优化保证：SVM 的优化问题是凸的，保证找到全局最优解。神经网络的优化是非凸的，可能陷入局部最优。

总结来说，SVM 最适合的场景是：中小规模数据集、特征维度中等或较高、需要强泛化能力保证、对可解释性有一定要求的分类任务。

虽然 SVM 是上世纪 90 年代提出的算法，但它的思想和方法仍在不断发展和扩展。

支持向量回归（SVR）是 SVM 在回归任务中的扩展。与分类不同，SVR 的目标是找到一个函数 f(x)，使得预测值与真实值的偏差在 ε 以内时不计损失（ε-不敏感损失）。这类似于分类中的间隔概念——在回归中，我们允许预测值在一定范围内偏离真实值而不受惩罚。

一类 SVM（One-Class SVM）用于异常检测。它学习正常样本的边界，将边界之外的样本识别为异常。这在工业缺陷检测、网络安全入侵检测等场景中非常有用。

结构化 SVM（Structured SVM）将 SVM 推广到结构化输出（如序列标注、图像分割、句法分析等）。它被广泛应用于自然语言处理中的命名实体识别（NER）、词性标注（POS Tagging）等任务。

多核学习（Multiple Kernel Learning, MKL）是一种自动学习最优核函数组合的方法。它不是手动选择单个核函数，而是学习多个核函数的加权组合，在数据驱动下找到最适合当前任务的核表示。

深度核学习（Deep Kernel Learning）是 SVM 与深度学习的结合。它使用神经网络学习特征表示，然后在学到的特征空间上应用 SVM 进行分类。这种方法结合了深度学习的表征能力和 SVM 的泛化保证。

量子 SVM（Quantum SVM）是量子计算与 SVM 的结合。在量子计算机上，某些核函数的计算可以实现指数级加速。虽然目前还处于理论研究阶段，但随着量子计算硬件的发展，这可能成为未来 SVM 的重要方向。

从更广阔的视角来看，SVM 的最大间隔思想深刻影响了后续机器学习的发展。边际最大化（Margin Maximization）成为了许多现代算法（如 AdaBoost、深度学习中的正则化方法）的理论基础。理解 SVM，不仅是学习一个算法，更是理解机器学习中的一个核心设计哲学：好的分类器不仅要正确分类，还要分类得从容不迫。

SVM 是机器学习中最优雅的算法之一。它的核心思想——最大间隔分类——简单而深刻：在所有能正确分类的决策边界中，选择那个离数据最远的。

回顾本文的关键要点：

几何直觉：SVM 找一个超平面，使得它到最近样本点的距离最大化。这个距离就是间隔。支持向量是那些恰好落在间隔边界上的样本。

数学推导：SVM 的原始问题是凸二次规划，通过拉格朗日对偶转化为只依赖样本内积的形式。这为核技巧奠定了基础。

核技巧：通过核函数隐式地将数据映射到高维空间，在不需要显式计算高维特征的情况下实现非线性分类。RBF 核是最常用的选择。

软间隔：通过松弛变量和参数 C，SVM 可以处理线性不可分的数据。C 控制了间隔最大化和分类错误之间的权衡。

实战要点：SVM 对特征缩放极其敏感，必须先标准化数据。调参的核心是 C 和 γ，建议用对数尺度的网格搜索。

适用场景：中小规模数据集、中等或高维特征、需要强泛化保证。超大规模数据、需要概率输出、需要在线学习的场景不太适合 SVM。

SVM 虽然在深度学习时代不再是主流选择，但它所蕴含的最大间隔哲学、核方法的优雅、凸优化的保证，仍然是每个机器学习从业者应该深入理解的核心知识。