机器学习基础：支持向量机

1. 引言

支持向量机（Support Vector Machine, SVM）是一种经典的监督学习算法，由 Vapnik 等人在 1990 年代提出。SVM 在分类和回归任务中表现优异，尤其在高维空间和小样本数据集上具有显著优势。本文将从基本原理、数学推导、核函数技巧到实际应用，系统介绍 SVM 的核心概念。

2. 基本思想

2.1 线性可分问题

假设我们有一个二分类问题，训练数据集为：

$$D=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),...,({\mathbf{x}}_n,y_n)\}$$

其中 ${\mathbf{x}}_i\in {\mathbb{R}}^d$ 是特征向量，yi∈{−1,+1}y_i \in \{-1, +1\}yi​∈{−1,+1} 是类别标签。

SVM 的目标是找到一个超平面（hyperplane）将两类样本分开：

$${\mathbf{w}}^T\mathbf{x}+b=0$$

其中 $\mathbf{w}$ 是法向量，$b$ 是偏置项。

2.2 最大间隔原则

SVM 的核心思想是最大化分类间隔（margin）。间隔定义为两类样本到超平面的最小距离之和。

点 ${\mathbf{x}}_i$ 到超平面的距离为：

$$d_i=\frac{|{\mathbf{w}}^T{\mathbf{x}}_i+b|}{||\mathbf{w}||}$$

为了使所有样本正确分类，需满足：

$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\forall i$$

此时，间隔为 $\gamma =\frac{2}{||\mathbf{w}||}$，最大化间隔等价于最小化 $||\mathbf{w}|{|}^2$。

3. 数学建模

3.1 原始问题（Primal Problem）

SVM 的优化目标可表述为：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}||\mathbf{w}|{|}^2$$

$$\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,i=1,2,...,n$$

这是一个凸二次规划问题。

3.2 对偶问题（Dual Problem）

引入拉格朗日乘子 ${\alpha }_i\ge 0$，构造拉格朗日函数：

$$L(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}||\mathbf{w}|{|}^2-\sum _{i=1}^n{\alpha }_i[y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1]$$

对 $\mathbf{w}$ 和 $b$ 求偏导并令其为零：

$$\frac{\partial L}{\partial \mathbf{w}}=0\Rightarrow \mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i$$

$$\frac{\partial L}{\partial b}=0\Rightarrow \sum _{i=1}^n{\alpha }_i{y}_i=0$$

代入得对偶问题：

$$\underset{\mathbf{\alpha }}{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$$

$$\text{s.t.}{\alpha }_i\ge 0,\sum _{i=1}^n{\alpha }_i{y}_i=0$$

3.3 支持向量

根据 KKT 条件，只有满足 ${\alpha }_i>0$ 的样本点才对决策边界有贡献，这些点称为支持向量（Support Vectors）。支持向量位于间隔边界上，即满足 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1$。

4. 软间隔与正则化

4.1 软间隔 SVM

实际数据往往存在噪声或线性不可分的情况。引入松弛变量 ${\xi }_i\ge 0$ 允许部分样本违反约束：

$$\underset{\mathbf{w},b,\mathbf{\xi }}{\min }\frac{1}{2}||\mathbf{w}|{|}^2+C\sum _{i=1}^n{\xi }_i$$

$$\text{s.t.}{y}_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

参数 $C>0$ 控制对误分类的惩罚程度：

• $C$ 较大：对误分类惩罚严重，间隔较小
• $C$ 较小：允许更多误分类，间隔较大

4.2 Hinge Loss

软间隔 SVM 等价于最小化 Hinge 损失：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}||\mathbf{w}|{|}^2+C\sum _{i=1}^n\max (0,1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))$$

5. 核函数技巧

5.1 非线性映射

对于线性不可分问题，可将数据映射到高维特征空间：

$$\varphi :{\mathbb{R}}^d\to {\mathbb{R}}^D,D>>d$$

在高维空间中寻找线性超平面。

5.2 核函数定义

核函数 $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$ 可以隐式计算高维内积，避免显式映射的计算开销。

对偶问题变为：

$$\underset{\mathbf{\alpha }}{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)$$

5.3 常用核函数

核函数	表达式	特点
线性核	$K(\mathbf{x},\mathbf{z})={\mathbf{x}}^T\mathbf{z}$	适用于线性可分数据
多项式核	$K(\mathbf{x},\mathbf{z})=(\gamma {\mathbf{x}}^T\mathbf{z}+r{)}^d$	可学习特征交互
RBF（高斯）核	$K(\mathbf{x},\mathbf{z})=\exp (-\gamma |\mathbf{x}-\mathbf{z}{|}^2)$	最常用，可映射到无限维
Sigmoid 核	$K(\mathbf{x},\mathbf{z})=\tanh (\gamma {\mathbf{x}}^T\mathbf{z}+r)$	类似神经网络

5.4 核函数选择建议

1. 特征数量 >> 样本数量：使用线性核
2. 特征数量较少，样本适中：使用 RBF 核
3. 特征数量较少，样本很大：先尝试线性核，再考虑 RBF

6. SMO 算法

序列最小优化（Sequential Minimal Optimization, SMO）是求解 SVM 对偶问题的高效算法，由 John Platt 于 1998 年提出。

6.1 基本思想

每次选择两个变量 ${\alpha }_i,{\alpha }_j$ 进行优化，固定其他变量。由于约束 ${\sum }_k{\alpha }_k{y}_k=0$，两个变量的更新可以解析求解。

6.2 变量选择策略

1. 外层循环：选择违反 KKT 条件最严重的 ${\alpha }_i$
2. 内层循环：选择使目标函数下降最快的 ${\alpha }_j$

7. 多分类扩展

SVM 原生支持二分类，多分类问题可通过以下策略解决：

7.1 一对一（One-vs-One, OvO）

• 训练 $\frac{k(k-1)}{2}$ 个分类器
• 预测时投票决定类别
• 优点：每个分类器训练数据少，速度快

7.2 一对多（One-vs-Rest, OvR）

• 训练 $k$ 个分类器，每个区分一类与其他类
• 预测时选择置信度最高的类别
• 优点：分类器数量少

8. Python 实现示例

import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score, classification_report
from sklearn.preprocessing import StandardScaler

# 加载数据
iris = datasets.load_iris()
X, y = iris.data, iris.target

# 数据预处理
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

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

# 训练 SVM 模型
svm_model = SVC(
    kernel='rbf',      # 使用 RBF 核
    C=1.0,             # 正则化参数
    gamma='scale',     # 核系数
    random_state=42
)
svm_model.fit(X_train, y_train)

# 预测与评估
y_pred = svm_model.predict(X_test)
print(f"准确率: {accuracy_score(y_test, y_pred):.4f}")
print("\n分类报告:")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

# 查看支持向量
print(f"\n支持向量数量: {svm_model.n_support_}")
print(f"支持向量索引: {svm_model.support_[:10]}...")  # 前10个

运行结果如下：

8.2 参数调优

from sklearn.model_selection import GridSearchCV

# 定义参数网格
param_grid = {
    'C': [0.1, 1, 10, 100],
    'gamma': ['scale', 'auto', 0.1, 0.01],
    'kernel': ['rbf', 'linear', 'poly']
}

# 网格搜索
grid_search = GridSearchCV(
    SVC(), param_grid, cv=5, scoring='accuracy', n_jobs=-1
)
grid_search.fit(X_train, y_train)

print(f"最佳参数: {grid_search.best_params_}")
print(f"最佳交叉验证得分: {grid_search.best_score_:.4f}")

运行结果：

9. SVM 的优缺点

9.1 优点

• 高维有效：在高维空间表现良好，适合文本分类等任务
• 内存高效：只需存储支持向量
• 泛化能力强：最大间隔原则提供良好的泛化性能
• 核技巧灵活：可处理非线性问题

9.2 缺点

• 大规模数据慢：时间复杂度 $O(n^2)$ 到 $O(n^3)$
• 对噪声敏感：异常点可能成为支持向量
• 参数选择困难：$C$ 和核参数需要仔细调优
• 不直接输出概率：需要额外计算（如 Platt Scaling）

10. 应用场景

领域	应用
文本分类	垃圾邮件检测、情感分析
图像识别	人脸识别、手写数字识别
生物信息学	蛋白质分类、基因表达分析
金融	信用评分、欺诈检测
医学	疾病诊断、医学图像分析

11. 总结

支持向量机是机器学习中的经典算法，其核心思想是通过最大化分类间隔来获得良好的泛化能力。通过核技巧，SVM 可以有效处理非线性问题。虽然深度学习在许多任务上取得了更好的效果，但 SVM 在小样本、高维数据和可解释性要求高的场景中仍然是重要的选择。