机器学习（四）

齐齐大魔王

482人浏览 · 2026-07-21 09:39:16

齐齐大魔王 · 2026-07-21 09:39:16 发布

1. 引言：从线性分类器到最大间隔边界

在二分类任务中，线性分类器的目标是找到一个超平面将不同类别的样本分开。对于线性可分的数据，存在无穷多个可行的决策边界。逻辑回归通过交叉熵损失学习一个概率化的决策边界，而支持向量机（Support Vector Machine, SVM）则追求一个更具“鲁棒性”的方案——最大间隔分类器。

SVM 的核心思想非常直观：在所有能够正确划分两类样本的超平面中，选择那个距离两侧数据点“最远”的决策边界。这样一来，新的测试样本即使有轻微波动，也不容易被误分，模型的泛化能力更强。

为了量化这种“远近”，SVM 引入了两个重要概念：

函数间隔（Functional Margin）：对于样本 $x^{(i)}, y^{(i)})$ ，其中 $y(i)∈{−1,1}y^{(i)} \in \{-1, 1\}$ ，函数间隔定义为 $γ^(i)=y(i)(wTx(i)+b)\hat{\gamma}^{(i)} = y^{(i)}(w^T x^{(i)} + b)$ 。它反映了分类的正确性和置信度，但会随着参数 $(w, b)$ 的等比例缩放而改变。
几何间隔（Geometric Margin）：通过归一化参数，得到真正点到超平面的欧氏距离 $γ(i)=y(i)(wTx(i)+b)∥w∥\gamma^{(i)} = \frac{y^{(i)}(w^T x^{(i)} + b)}{\|w\|}$ 。

SVM 的优化目标便转化为：寻找一组参数 $(w, b)$ ，使得所有样本中的最小几何间隔最大化。

2. SVM 的优化问题：从原始形式到拉格朗日对偶

2.1 原始优化问题的构造

将“最大化最小几何间隔”写成优化问题，可以得到：

$\max_{w, b} \quad \gamma \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \ge \gamma \|w\|,\; i=1,\dots,m$

由于该形式并不是凸优化，我们利用“分类间隔变化不影响决策边界”这一性质，将函数间隔固定为 1（即 $γ^=1\hat{\gamma}=1$ ），从而将问题等价变换为一个二次规划问题：

$\min_{w, b} \quad \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} + b) \ge 1,\; i=1,\dots,m$

该形式是一个标准的凸优化，可以使用求解器直接求解。但为了更深入地利用核技巧并导出高效算法，SVM 通常转而求解它的拉格朗日对偶问题。

2.2 拉格朗日对偶与 KKT 条件

对于带不等式约束的凸优化问题：

$\min_w f(w) \quad \text{s.t.} \quad g_i(w) \le 0,\; h_j(w)=0$

其拉格朗日函数为：

$\mathcal{L}(w, \alpha, \beta) = f(w) + \sum_i \alpha_i g_i(w) + \sum_j \beta_j h_j(w), \quad \alpha_i \ge 0$

由此定义原始问题 $p∗=min⁡wmax⁡α≥0,βL(w,α,β)p^* = \min_w \max_{\alpha\ge 0, \beta} \mathcal{L}(w,\alpha,\beta)$ 和对偶问题 $d∗=max⁡α≥0,βmin⁡wL(w,α,β)d^* = \max_{\alpha\ge 0, \beta} \min_w \mathcal{L}(w,\alpha,\beta)$ 。在满足 Slater 条件以及 KKT 条件时， $d^* = p^*$ ，我们可以通过求解对偶问题来得到原始问题的最优解。

具体到 SVM，将约束改写为 $gi(w)=−y(i)(wTx(i)+b)+1≤0g_i(w) = -y^{(i)}(w^T x^{(i)} + b) + 1 \le 0$ ，拉格朗日函数变为：

$\mathcal{L}(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^m \alpha_i \big[y^{(i)}(w^T x^{(i)} + b) - 1\big], \quad \alpha_i \ge 0$

2.3 求解对偶问题

先对 $w$ 和 $b$ 求偏导并置零：

$\frac{\partial \mathcal{L}}{\partial w} = w - \sum_{i=1}^m \alpha_i y^{(i)} x^{(i)} = 0 \;\Rightarrow\; w = \sum_{i=1}^m \alpha_i y^{(i)} x^{(i)}$

$\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^m \alpha_i y^{(i)} = 0 \;\Rightarrow\; \sum_{i=1}^m \alpha_i y^{(i)} = 0$

将上述关系代回拉格朗日函数，消去 $w$ 和 $b$ ，得到对偶优化问题：

$\max_{\alpha} \quad W(\alpha) = \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)} \rangle$

$\text{s.t.} \quad \alpha_i \ge 0,\; i=1,\dots,m, \quad \sum_{i=1}^m \alpha_i y^{(i)} = 0$

这个对偶形式有几个重要性质：

支持向量：由 KKT 互补条件 $αigi(w∗)=0\alpha_i g_i(w^*) = 0$ 可知，只有当 $g_i(w^*)=0$ （即样本恰好位于间隔边界上）时， $αi\alpha_i$ 才可能大于 0。这些样本称为支持向量，它们决定了最终的决策边界。
参数 $w^*$ 可以直接由 $α∗\alpha^*$ 表示： $w∗=∑i=1mαi∗y(i)x(i)w^* = \sum_{i=1}^m \alpha_i^* y^{(i)} x^{(i)}$ 。
$b^*$ 也可通过支持向量反解： $b∗=−max⁡i:y(i)=−1w∗Tx(i)+min⁡i:y(i)=1w∗Tx(i)2b^* = -\frac{\max_{i:y^{(i)}=-1} w^{*T} x^{(i)} + \min_{i:y^{(i)}=1} w^{*T} x^{(i)}}{2}$ 。

3. 序列最小优化（SMO）算法：高效求解对偶问题

对偶问题是一个关于 $α\alpha$ 的二次规划，但变量众多。直接使用常规方法效率较低，而 SMO（Sequential Minimal Optimization） 是一种非常适合手写实现的高效算法。

3.1 核心思想

SMO 来源于坐标上升法：如果变量之间没有等式约束，可以每次只优化一个变量，循环直至收敛。但在 SVM 的对偶问题中，由于存在约束 $∑αiy(i)=0\sum \alpha_i y^{(i)} = 0$ ，任意一个 $αi\alpha_i$ 的变化都会被其他变量约束，因此 SMO 每次选择两个变量 $αi,αj\alpha_i, \alpha_j$ 进行联合优化，其余变量固定。

3.2 更新公式与优点

假设我们固定 $α3,…,αm\alpha_3, \dots, \alpha_m$ ，只更新 $α1\alpha_1$ 和 $α2\alpha_2$ 。由等式约束可得 $α1=ζ−α2y(2)y(1)\alpha_1 = \zeta - \alpha_2 y^{(2)} y^{(1)}$ （其中 $ζ\zeta$ 为常数），于是目标函数 $W(α)W(\alpha)$ 可以整理成关于 $α2\alpha_2$ 的一元二次函数：

$\max_{\alpha_2} \quad a\alpha_2^2 + b\alpha_2 + c \quad \text{s.t.} \quad 0 \le \alpha_2 \le C$

（当引入松弛变量处理线性不可分时，上界 $C$ 出现；否则 $C=∞C=\infty$ ）。

这个一元二次优化可以在 $O (1)$ 时间内闭式求解，因此 SMO 的每次迭代都非常快。算法不断选取不满足 KKT 条件的两个变量进行更新，直到整体收敛（例如 $W(α)W(\alpha)$ 的变化小于阈值）。

SMO 的出现使得 SVM 的训练可以被轻易地在普通机器上实现，极大推动了 SVM 的普及。

4. 核方法：从线性到非线性

4.1 为什么要引入核函数

现实中很多数据并不是线性可分的，简单地使用原始特征空间中的直线/平面无法取得良好分类效果。SVM 的解决办法是：将数据映射到更高维的空间，期望在高维空间中变得线性可分。

定义特征映射函数 $ϕ:Rd→Rh\phi: \mathbb{R}^d \to \mathbb{R}^h$ ，我们希望在映射后的空间中应用 SVM。注意到对偶问题以及最终的预测公式都只依赖于样本之间的内积 $⟨x(i),x(j)⟩\langle x^{(i)}, x^{(j)} \rangle$ ，因此我们只需要知道映射后内积的形式，而不必显式计算 $ϕ(x)\phi(x)$ 。

4.2 核函数与核技巧

核函数 $K (x, z)$ 定义为：

$\langle \phi(x), \phi(z) \rangle$

使用核函数直接替换内积，对偶问题变为：

$\max_{\alpha} \quad \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j=1}^m y^{(i)} y^{(j)} \alpha_i \alpha_j K(x^{(i)}, x^{(j)})$

预测函数也变为：

$w^T \phi(x) + b = \sum_{i=1}^m \alpha_i y^{(i)} K(x^{(i)}, x) + b$

整个过程完全避开了高维映射 $ϕ\phi$ 的显式计算，这就是核技巧（Kernel Trick）。同时，只要核函数 $K$ 对应的核矩阵是半正定的（Mercer 条件），它就是一个合法的核函数。

4.3 常用核函数

多项式核： $K(x, z) = (x^T z + c)^d$ ，可以模拟高阶特征交互。
径向基函数（RBF）/高斯核： $\exp\left(-\frac{\|x - z\|^2}{2\sigma^2}\right)$ ，是最常用的核之一，等价于映射到无穷维空间，对局部数据有很强的拟合能力。
Sigmoid 核： $\tanh(\alpha x^T z + c)$ ，与神经网络有着天然的联系。

下表汇总了 SVM 中几种典型核函数的对比：

核函数	公式	主要参数	适用场景	优点	缺点
线性核	$K(x,z)=x^T z$	—	特征维度高、样本量大的线性可分数据	简单高效，不易过拟合，可解释性强	只能处理线性可分问题
多项式核	$K(x,z)=(x^T z + c)^d$	$d$ （次数）， $c$ （常数）	中等维度、需要特征交互的非线性数据	能模拟高阶特征交互	参数多、易过拟合，计算开销较高
RBF/高斯核	$K(x,z)=exp⁡(−∣x−z∣22σ2)K(x,z)=\exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right)$	$σ\sigma$ （带宽）或 $γ=12σ2\gamma=\frac{1}{2\sigma^2}$	通用非线性问题，特别是局部特征强的数据	映射到无穷维，拟合能力极强，最常用	易过拟合，需要仔细调参
Sigmoid 核	$K(x,z)=tanh⁡(αxTz+c)K(x,z)=\tanh(\alpha x^T z + c)$	$α\alpha$ ， $c$	与神经网络结合的场景	源自神经网络激活函数	核矩阵未必半正定，并非总满足 Mercer 条件

4.4 核函数选择与调参实践

在实际应用中，核函数的选择和超参数的调优对 SVM 的性能至关重要。没有一套“万能”的参数适合所有问题，但可以遵循一些经验法则。

核函数选择策略

数据场景	推荐核函数	原因
特征维度极高且稀疏（如文本分类的 TF‑IDF 特征，维度数万以上）	线性核	高维空间中数据往往已经接近线性可分；线性核训练快、不易过拟合，且无需额外调核参数
样本量极大（ $m > 10^5$ ）、特征维度适中	线性核	RBF 核在样本量大时核矩阵计算开销巨大（ $O(m^2)$ 空间），线性核可结合 SGD 类优化器高效求解
小样本（ $m < 10^4$ ）、中等维度、非线性明显	RBF/高斯核	RBF 是默认的通用选择，只需调一个参数 $γ\gamma$ ，且具备极强的非线性拟合能力
已知数据具有低阶多项式结构（如图像像素的局部交互）	多项式核	可直接建模指定阶数的特征交互，但需同时调 $d$ 和 $c$ ，复杂度较高
需要与神经网络联合建模或实验性探索	Sigmoid 核	与感知机激活函数形式一致，但需注意核矩阵未必正定，通常在其他核效果不佳时作为备选

经验法则：先用线性核快速得到一个基线；如果训练集上欠拟合明显（偏差高），再尝试 RBF 核；若 RBF 核过拟合，则可回退到线性核或增大正则化。

关键超参数调优

SVM 的两个核心超参数是 $C$ （惩罚系数） 和 $γ\gamma$ （RBF 核的带宽参数）。

$C$ ：控制对误分类的惩罚力度。 $C$ 越大，模型越不允许训练误差，决策边界更复杂，容易过拟合； $C$ 越小，间隔越大，允许更多误分类，模型更平滑，容易欠拟合。典型搜索范围为 $\in [10^{-3}, 10^3]$ ，以对数刻度采样（如 [0.001, 0.01, 0.1, 1, 10, 100, 1000]）。
$γ\gamma$ ：控制单个样本的影响半径。 $γ\gamma$ 越大，每个支持向量的影响范围越小，决策边界更曲折精细，容易过拟合； $γ\gamma$ 越小，影响范围越大，决策边界更平滑，容易欠拟合。典型搜索范围为 $γ∈[10−4,10]\gamma \in [10^{-4}, 10]$ ，同样建议对数采样。

$C$ 与 $γ\gamma$ 的交互关系：两者同时较大时极易过拟合（模型记住每一个训练样本）；同时较小时则欠拟合。实践中应使用网格搜索（Grid Search）+ 交叉验证联合调优。

调参实践流程

推荐的 SVM 调参流程如下：

数据标准化：SVM 对特征尺度敏感，务必在训练前对特征进行标准化（如 z‑score 或 Min‑Max 缩放），否则大数值特征会主导核函数计算结果。
粗搜索：在 $C$ 和 $γ\gamma$ 的全量对数范围（如 $10^{-3}, 10^3]$ × $10^{-4}, 10]$ ）上进行 3‑5 折交叉验证的网格搜索，快速锁定最优区域。
细搜索：在粗搜索找到的最优值附近缩小步长再次搜索（如 $C$ 在 $[0.5, 5]$ ， $γ\gamma$ 在 $[0.01, 0.5]$ 之间）。
验证与早停：保留独立的验证集评估泛化性能；若训练集上准确率远高于验证集，说明过拟合，应减小 $C$ 或 $γ\gamma$ 。
学习曲线诊断：绘制不同 $C$ 下的学习曲线，若训练误差和验证误差均较高 → 欠拟合（增大 $C$ 或换 RBF 核）；若训练误差低但验证误差高 → 过拟合（减小 $C$ / $γ\gamma$ 或增加数据）。

总结建议

问题类型	核函数	$C$ 范围	$γ\gamma$ 范围	备注
高维稀疏文本分类	线性核	$[0.01, 1]$	无需调	先试 $C = 1$ ，根据验证集调整
小样本非线性	RBF	$[1, 100]$	$[0.001, 1]$	网格搜索 $\gamma)$ 组合
图像/语音等	RBF 或多项式	$[1, 1000]$	$[0.0001, 0.1]$	先标准化，再网格搜索
基线快速实验	线性核	$C = 1$	无需调	为后续实验提供比较基线

代码示例：GridSearchCV 调参实战

下面是一个使用 scikit‑learn 对 RBF‑SVM 进行 (C, γ) 网格搜索的完整示例。代码生成二分类模拟数据，先标准化特征，再通过 5 折交叉验证选出最优参数并输出得分。

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

# 1. 生成模拟数据（非线性二分类）
X, y = make_classification(
    n_samples=1000, n_features=20, n_informative=10,
    n_redundant=5, n_clusters_per_class=2, random_state=42
)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# 2. 特征标准化（SVM 对尺度敏感）
scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.transform(X_test)

# 3. 定义参数搜索空间
param_grid = {
    'C': [0.01, 0.1, 1, 10, 100],
    'gamma': [0.0001, 0.001, 0.01, 0.1, 1]
}

# 4. 创建 SVC 实例并执行网格搜索
svc = SVC(kernel='rbf', random_state=42)
grid_search = GridSearchCV(
    svc, param_grid, cv=5, scoring='accuracy',
    verbose=1, n_jobs=-1
)
grid_search.fit(X_train, y_train)

# 5. 输出最佳参数与交叉验证分数
print("最佳参数组合：", grid_search.best_params_)
print("最佳交叉验证准确率：{:.4f}".format(grid_search.best_score_))
print("测试集准确率：{:.4f}".format(grid_search.score(X_test, y_test)))

# 6. 查看详细结果（可选）
cv_results = grid_search.cv_results_
best_idx = grid_search.best_index_
print("\n最佳组合的详细交叉验证结果：")
for i, (mean, std) in enumerate(zip(
    cv_results['mean_test_score'], cv_results['std_test_score']
)):
    if i == best_idx:
        print(f"  ✓ 排名第 1 名: C={cv_results['param_C'][i]}, "
              f"gamma={cv_results['param_gamma'][i]}, "
              f"mean={mean:.4f}, std={std:.4f}")

典型输出示例：

最佳参数组合： {'C': 10, 'gamma': 0.1}
最佳交叉验证准确率：0.9325
测试集准确率：0.9350

这个流程完美体现了前文总结的“先标准化、再网格搜索”的调参思想，并且代码中使用了 cv=5 和 n_jobs=-1 来加速搜索，可直接复现。

4.5 SVM 与逻辑回归的本质差异

在总结整个 SVM 框架时，一个值得思考的问题是它与逻辑回归的区别：

损失函数不同：SVM 采用 Hinge Loss $L = \max(0, 1 - y(w^T x + b))$ ，目的是最大化分类间隔，对正确分类但过于靠近边界的点也会施加惩罚；逻辑回归采用对数损失，直接建模后验概率 $P (y ∣ x)$ 。
输出解释不同：逻辑回归天然输出概率值；SVM 输出的是符号决策（或到超平面的距离），需额外使用 Platt Scaling 等方法才能得到概率。
参数化 vs. 非参数化：SVM 的决策函数依赖于支持向量（非参数化），模型容量随训练数据变化；逻辑回归的参数数量固定（参数化），在样本极大时依然高效。