第7章：支持向量机（Support Vector Machine）
一、导读
1.1 本章学习目标
第7章介绍支持向量机（SVM）——最强大的分类方法之一。SVM的核心思想是找到一个最大间隔超平面，使两类样本之间的间隔最大化。SVM不仅理论基础扎实，而且通过核技巧可以高效地处理非线性问题。
本章的核心学习目标包括：
- 理解最大间隔超平面：为什么最大间隔是最优的？支持向量是什么？
- 掌握对偶问题：拉格朗日对偶、KKT条件的含义
- 理解软间隔SVM：如何处理线性不可分数据？
- 掌握核技巧：如何将数据映射到高维空间实现非线性分类？
- 了解常用核函数：线性核、多项式核、高斯核（RBF）
- 了解SMO算法：SVM的高效优化方法
1.2 为什么本章如此重要
SVM是统计学习理论的代表性方法。Vapnik的统计学习理论为SVM提供了严格的理论保证：在有限样本下也能获得良好的泛化性能。SVM在高维空间、小样本、非线性问题上表现出色，在深度学习兴起之前，SVM是许多任务的首选方法。
SVM的核技巧思想影响深远——它不仅用于SVM，还广泛应用于高斯过程、核PCA等方法中。理解核技巧，就是理解"隐式高维映射"的思想。
1.3 核心问题引导
在阅读本章时，请带着以下问题思考：
为什么最大间隔超平面是最优的？间隔最大化有什么理论保证？
什么是支持向量？为什么只有支持向量影响决策边界？
对偶问题相比原始问题有什么优势？
软间隔SVM中的参数C有什么含义？C大和C小分别意味着什么？
核技巧的直觉是什么？为什么可以在不显式计算高维映射的情况下工作？
不同的核函数适用于什么场景？
二、核心概念详解
7.1 线性可分SVM：最大间隔超平面
7.1.1 间隔最大化
给定线性可分的训练数据，SVM的目标是找到一个超平面 (w, b)，使得两类样本的间隔最大。
函数间隔：γ̂_i = y_i(w·x_i + b)
几何间隔：γ_i = y_i(w·x_i + b) / ||w||
SVM的目标是最大化几何间隔的最小值：
max_{w,b} γ = min_i y_i(w·x_i + b) / ||w||
s.t. y_i(w·x_i + b) > 0, ∀i等价地（通过缩放 w 和 b）：
min_{w,b} (1/2)||w||^2
s.t. y_i(w·x_i + b) ≥ 1, ∀ipython
import numpy as np
# 最大间隔超平面的直觉
# 在二维空间中，间隔 = 2/||w||
# 最大化间隔等价于最小化 ||w||
w1 = np.array([1, 0])
w2 = np.array([2, 0])
margin1 = 2 / np.linalg.norm(w1)
margin2 = 2 / np.linalg.norm(w2)
print(f"w={w1}: 间隔 = {margin1:.4f}")
print(f"w={w2}: 间隔 = {margin2:.4f}")
print(f"||w||越小，间隔越大")7.1.2 支持向量
支持向量是距离决策边界最近的训练样本点。它们满足 y_i(w·x_i + b) = 1。
关键性质：决策边界只由支持向量决定。移除或移动非支持向量的样本不会改变决策边界。
python
import numpy as np
def find_support_vectors(X, y, w, b, tol=1e-6):
"""找到支持向量"""
margins = y * (X @ w + b)
sv_mask = np.abs(margins - 1) < 0.1 # 近似等于1的点
return X[sv_mask], y[sv_mask]
# 示例
np.random.seed(42)
X_pos = np.random.randn(20, 2) + np.array([2, 2])
X_neg = np.random.randn(20, 2) + np.array([-1, -1])
X = np.vstack([X_pos, X_neg])
y = np.array([1] * 20 + [-1] * 20)
# 假设已经找到最优超平面
w = np.array([0.5, 0.5])
b = -0.5
svs_x, svs_y = find_support_vectors(X, y, w, b)
print(f"支持向量数量: {len(svs_x)} / {len(X)}")
print(f"支持向量占总样本的比例: {len(svs_x)/len(X):.2%}")7.2 对偶问题
7.2.1 拉格朗日函数
原始问题的拉格朗日函数：
L(w, b, α) = (1/2)||w||^2 - Σ_i α_i [y_i(w·x_i + b) - 1]7.2.2 对偶问题
通过对 w 和 b 求偏导并代入，得到对偶问题：
max_α Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j (x_i · x_j)
s.t. α_i ≥ 0, Σ_i α_i y_i = 0对偶问题的优势：
更容易求解（只有 α 一个变量）
自然地引入核函数
解的稀疏性（大部分 α_i = 0，只有支持向量的 α_i > 0）
python
import numpy as np
def svm_dual_simple(X, y, C=1.0, max_iter=100):
"""简化的SVM对偶问题求解（SMO的简化版）"""
n = len(y)
alpha = np.zeros(n)
b = 0.0
# 预计算核矩阵（线性核）
K = X @ X.T
for iteration in range(max_iter):
alpha_changed = 0
for i in range(n):
# 计算预测
f = np.sum(alpha * y * K[i]) + b
E_i = f - y[i]
# 检查KKT条件
if (y[i] * E_i < -1e-3 and alpha[i] < C) or \
(y[i] * E_i > 1e-3 and alpha[i] > 0):
# 随机选择j
j = np.random.randint(n)
if j == i:
continue
f_j = np.sum(alpha * y * K[j]) + b
E_j = f_j - y[j]
# 计算eta
eta = 2 * K[i, j] - K[i, i] - K[j, j]
if eta >= 0:
continue
# 更新alpha_j
alpha_j_new = alpha[j] - y[j] * (E_i - E_j) / eta
# 裁剪
if y[i] != y[j]:
L = max(0, alpha[j] - alpha[i])
H = min(C, C + alpha[j] - alpha[i])
else:
L = max(0, alpha[i] + alpha[j] - C)
H = min(C, alpha[i] + alpha[j])
alpha_j_new = np.clip(alpha_j_new, L, H)
if abs(alpha_j_new - alpha[j]) < 1e-5:
continue
alpha_i_new = alpha[i] + y[i] * y[j] * (alpha[j] - alpha_j_new)
alpha[i] = alpha_i_new
alpha[j] = alpha_j_new
alpha_changed += 1
if alpha_changed == 0:
break
# 计算w和b
w = np.sum((alpha * y)[:, np.newaxis] * X, axis=0)
sv_idx = np.where(alpha > 1e-5)[0]
if len(sv_idx) > 0:
b = np.mean(y[sv_idx] - X[sv_idx] @ w)
return w, b, alpha
# 测试
np.random.seed(42)
X_pos = np.random.randn(30, 2) + np.array([2, 2])
X_neg = np.random.randn(30, 2) + np.array([-1, -1])
X = np.vstack([X_pos, X_neg])
y = np.array([1] * 30 + [-1] * 30)
w, b, alpha = svm_dual_simple(X, y, C=1.0, max_iter=100)
predictions = np.sign(X @ w + b)
accuracy = np.mean(predictions == y)
n_sv = np.sum(alpha > 1e-5)
print(f"SVM准确率: {accuracy:.4f}")
print(f"支持向量数: {n_sv} / {len(X)}")
print(f"w = [{w[0]:.4f}, {w[1]:.4f}]")
print(f"b = {b:.4f}")7.3 线性SVM：软间隔
7.3.1 松弛变量
当数据线性不可分时，引入松弛变量 ξ_i ≥ 0：
min_{w,b,ξ} (1/2)||w||^2 + C Σ_i ξ_i
s.t. y_i(w·x_i + b) ≥ 1 - ξ_i, ξ_i ≥ 0参数 C 控制间隔和误分类之间的权衡：
- C 大：惩罚误分类多，间隔小，容易过拟合
- C 小：允许更多误分类，间隔大，容易欠拟合
python
import numpy as np
def effect_of_C():
"""演示参数C的影响"""
np.random.seed(42)
# 生成近似线性可分但有噪声的数据
X_pos = np.random.randn(50, 2) + np.array([1, 1])
X_neg = np.random.randn(50, 2) + np.array([-0.5, -0.5])
# 添加一些噪声点
X_pos[:5] = X_pos[:5] - 3 # 几个正类点跑到负类区域
X = np.vstack([X_pos, X_neg])
y = np.array([1] * 50 + [-1] * 50)
print(f"{'C值':>8} {'准确率':>10} {'支持向量数':>12} {'||w||':>10}")
print("-" * 42)
for C in [0.01, 0.1, 1.0, 10.0, 100.0]:
w, b, alpha = svm_dual_simple(X, y, C=C, max_iter=50)
pred = np.sign(X @ w + b)
acc = np.mean(pred == y)
n_sv = np.sum(alpha > 1e-5)
print(f"{C:>8.2f} {acc:>10.4f} {n_sv:>12} {np.linalg.norm(w):>10.4f}")
effect_of_C()7.4 非线性SVM：核技巧
7.4.1 核技巧的直觉
核技巧的核心思想：将数据从原始空间映射到高维特征空间，在高维空间中寻找线性决策边界。
关键洞察：对偶问题中只涉及样本之间的内积 x_i · x_j。如果我们能找到一个函数 K(x_i, x_j) = φ(x_i) · φ(x_j)，其中 φ 是高维映射，那么我们不需要显式计算 φ(x)，只需要计算 K(x_i, x_j)。
python
import numpy as np
def kernel_trick_demo():
"""核技巧的直观演示"""
# 一维数据，非线性可分
X = np.array([-3, -2, -1, 1, 2, 3], dtype=float).reshape(-1, 1)
y = np.array([1, -1, 1, 1, -1, 1]) # XOR-like pattern
print("原始空间（一维）:")
for xi, yi in zip(X.flatten(), y):
print(f" x={xi:+.0f}, y={yi:+d}")
print(" → 线性不可分")
# 映射到高维空间：φ(x) = (x, x^2)
X_phi = np.column_stack([X, X**2])
print("\n映射后空间（二维）:")
for i in range(len(X)):
print(f" φ({X[i,0]:+.0f}) = ({X_phi[i,0]:+.0f}, {X_phi[i,1]:+.0f}), y={y[i]:+d}")
print(" → 在高维空间中可能线性可分")
# 核函数：K(x, z) = (x·z + 1)^2（二阶多项式核）
def poly_kernel(x, z):
return (x @ z + 1) ** 2
print("\n核函数计算（不需要显式映射）:")
K = np.zeros((len(X), len(X)))
for i in range(len(X)):
for j in range(len(X)):
K[i, j] = poly_kernel(X[i], X[j])
print(f" 核矩阵K:\n{K}")
kernel_trick_demo()7.4.2 常用核函数
python
import numpy as np
def linear_kernel(x, z):
"""线性核：K(x,z) = x·z"""
return x @ z
def polynomial_kernel(x, z, degree=3, coef0=1):
"""多项式核：K(x,z) = (x·z + c)^d"""
return (x @ z + coef0) ** degree
def rbf_kernel(x, z, gamma=1.0):
"""高斯核（RBF）：K(x,z) = exp(-γ||x-z||^2)"""
return np.exp(-gamma * np.sum((x - z) ** 2))
# 对比不同核函数
x = np.array([1, 2])
z = np.array([3, 4])
print(f"线性核: {linear_kernel(x, z):.4f}")
print(f"多项式核(degree=2): {polynomial_kernel(x, z, degree=2):.4f}")
print(f"多项式核(degree=3): {polynomial_kernel(x, z, degree=3):.4f}")
print(f"RBF核(γ=0.1): {rbf_kernel(x, z, gamma=0.1):.4f}")
print(f"RBF核(γ=1.0): {rbf_kernel(x, z, gamma=1.0):.4f}")7.4.3 核SVM的实现
python
import numpy as np
class KernelSVM:
def __init__(self, kernel='rbf', C=1.0, gamma=1.0, max_iter=100):
self.kernel = kernel
self.C = C
self.gamma = gamma
self.max_iter = max_iter
def _compute_kernel(self, X1, X2):
if self.kernel == 'linear':
return X1 @ X2.T
elif self.kernel == 'rbf':
sq_dists = np.sum(X1**2, axis=1, keepdims=True) + np.sum(X2**2, axis=1) - 2 * X1 @ X2.T
return np.exp(-self.gamma * sq_dists)
elif self.kernel == 'poly':
return (X1 @ X2.T + 1) ** 3
def fit(self, X, y):
self.X_train = X
n = len(y)
K = self._compute_kernel(X, X)
alpha = np.zeros(n)
b = 0.0
for _ in range(self.max_iter):
for i in range(n):
f = np.sum(alpha * y * K[i]) + b
E_i = f - y[i]
if (y[i] * E_i < -1e-3 and alpha[i] < self.C) or \
(y[i] * E_i > 1e-3 and alpha[i] > 0):
j = np.random.randint(n)
if j == i:
continue
f_j = np.sum(alpha * y * K[j]) + b
E_j = f_j - y[j]
eta = 2 * K[i, j] - K[i, i] - K[j, j]
if eta >= 0:
continue
alpha_j_new = alpha[j] - y[j] * (E_i - E_j) / eta
if y[i] != y[j]:
L = max(0, alpha[j] - alpha[i])
H = min(self.C, self.C + alpha[j] - alpha[i])
else:
L = max(0, alpha[i] + alpha[j] - self.C)
H = min(self.C, alpha[i] + alpha[j])
alpha_j_new = np.clip(alpha_j_new, L, H)
if abs(alpha_j_new - alpha[j]) < 1e-5:
continue
alpha[i] += y[i] * y[j] * (alpha[j] - alpha_j_new)
alpha[j] = alpha_j_new
self.alpha = alpha
self.b = np.mean(y[np.where(alpha > 1e-5)[0]] -
np.sum(alpha[:, np.newaxis] * y[:, np.newaxis] * K[np.where(alpha > 1e-5)[0]], axis=0))
return self
def predict(self, X):
K = self._compute_kernel(X, self.X_train)
return np.sign(np.sum(self.alpha * self.y_train * K, axis=1) + self.b)
def fit(self, X, y):
self.y_train = y
self.X_train = X
n = len(y)
K = self._compute_kernel(X, X)
alpha = np.zeros(n)
b = 0.0
for _ in range(self.max_iter):
for i in range(n):
f = np.sum(alpha * y * K[i]) + b
E_i = f - y[i]
if (y[i] * E_i < -1e-3 and alpha[i] < self.C) or \
(y[i] * E_i > 1e-3 and alpha[i] > 0):
j = np.random.randint(n)
if j == i:
continue
f_j = np.sum(alpha * y * K[j]) + b
E_j = f_j - y[j]
eta = 2 * K[i, j] - K[i, i] - K[j, j]
if eta >= 0:
continue
alpha_j_new = alpha[j] - y[j] * (E_i - E_j) / eta
if y[i] != y[j]:
L = max(0, alpha[j] - alpha[i])
H = min(self.C, self.C + alpha[j] - alpha[i])
else:
L = max(0, alpha[i] + alpha[j] - self.C)
H = min(self.C, alpha[i] + alpha[j])
alpha_j_new = np.clip(alpha_j_new, L, H)
if abs(alpha_j_new - alpha[j]) < 1e-5:
continue
alpha[i] += y[i] * y[j] * (alpha[j] - alpha_j_new)
alpha[j] = alpha_j_new
self.alpha = alpha
sv_idx = np.where(alpha > 1e-5)[0]
if len(sv_idx) > 0:
self.b = np.mean(y[sv_idx] - K[sv_idx] @ (alpha * y))
else:
self.b = 0.0
return self
# 在非线性数据上测试
from sklearn.datasets import make_circles
X, y = make_circles(n_samples=200, noise=0.1, random_state=42)
y = 2 * y - 1 # 转换为 +1/-1
svm_rbf = KernelSVM(kernel='rbf', C=10.0, gamma=5.0, max_iter=50)
svm_rbf.fit(X, y)
accuracy = np.mean(svm_rbf.predict(X) == y)
print(f"RBF核SVM准确率（环形数据）: {accuracy:.4f}")三、实战案例
3.1 不同核函数的对比
python
import numpy as np
from sklearn.datasets import make_classification, make_moons
def compare_kernels():
"""对比不同核函数在不同数据上的效果"""
datasets = {
'线性可分': make_classification(n_samples=200, n_features=2, n_informative=2,
n_redundant=0, random_state=42),
'月牙形': make_moons(n_samples=200, noise=0.15, random_state=42),
}
for name, (X, y) in datasets.items():
y = 2 * y - 1
print(f"\n{name}数据集:")
print(f"{'核函数':>10} {'准确率':>10} {'支持向量':>10}")
print("-" * 32)
for kernel in ['linear', 'rbf']:
svm = KernelSVM(kernel=kernel, C=1.0, gamma=2.0, max_iter=50)
svm.fit(X, y)
acc = np.mean(svm.predict(X) == y)
n_sv = np.sum(svm.alpha > 1e-5)
print(f"{kernel:>10} {acc:>10.4f} {n_sv:>10}")
compare_kernels()3.2 参数C和gamma的影响
python
import numpy as np
def parameter_sensitivity():
"""演示C和gamma参数的影响"""
from sklearn.datasets import make_classification
X, y = make_classification(n_samples=200, n_features=5, random_state=42)
y = 2 * y - 1
split = 150
X_train, X_test = X[:split], X[split:]
y_train, y_test = y[:split], y[split:]
print(f"{'C':>8} {'gamma':>8} {'训练准确率':>12} {'测试准确率':>12}")
print("-" * 42)
for C in [0.1, 1.0, 10.0]:
for gamma in [0.1, 1.0, 10.0]:
svm = KernelSVM(kernel='rbf', C=C, gamma=gamma, max_iter=50)
svm.fit(X_train, y_train)
train_acc = np.mean(svm.predict(X_train) == y_train)
test_acc = np.mean(svm.predict(X_test) == y_test)
print(f"{C:>8.1f} {gamma:>8.1f} {train_acc:>12.4f} {test_acc:>12.4f}")
parameter_sensitivity()四、本章小结
第7章介绍了支持向量机：
最大间隔超平面：SVM寻找使两类样本间隔最大的超平面。间隔 = 2/||w||。
支持向量：距离决策边界最近的样本点，只有它们影响决策边界。
对偶问题：通过拉格朗日对偶将问题转化为只依赖样本内积的形式，便于引入核函数。
软间隔SVM：引入松弛变量处理线性不可分，参数C控制间隔和误分类的权衡。
核技巧：通过核函数隐式地将数据映射到高维空间，避免显式计算高维映射。
常用核函数：线性核（线性可分）、多项式核（低维非线性）、RBF核（通用非线性）。
SVM的核心启示是：间隔最大化提供了良好的泛化保证，核技巧使得线性方法可以处理非线性问题。
五、思考与练习
思考题
为什么最大间隔超平面是最优的？从VC维的角度解释。
支持向量有什么特殊性质？如果移除一个非支持向量的样本，决策边界会改变吗？
对偶问题相比原始问题有什么优势？为什么对偶问题更自然地引入核函数？
参数C对模型有什么影响？C→∞时SVM退化成什么？
RBF核的gamma参数有什么影响？gamma→0和gamma→∞时分别会怎样？
编程练习
实现线性SVM的对偶问题求解，在二分类数据上测试。
实现RBF核SVM，在非线性可分数据（如环形数据）上测试。
对比不同C值和gamma值对SVM性能的影响。