基于最大间隔的多类核支持向量机（Multiclass Kernel SVM）的多类问题求解策略：一对一（One-vs-One）与一对多（One-vs-Rest）策略的原理、决策过程与优化
题目描述
支持向量机（SVM）本质上是一种二分类算法。但当面对多类分类问题时（例如类别数 \(K \geq 3\)），需要将其扩展为多类分类器。本题将详细讲解两种经典的多类SVM扩展策略：一对多（One-vs-Rest, OvR） 和 一对一（One-vs-One, OvO），并深入分析它们在核支持向量机（Kernel SVM） 中的应用原理、决策过程、优化方法及各自的优缺点。
解题过程
我们假设有 \(K\) 个类别，训练集为 \(\{ (\mathbf{x}_i, y_i) \}_{i=1}^N\)，其中 \(y_i \in \{1, 2, \dots, K\}\)。目标是构建一个分类器 \(f(\mathbf{x}): \mathbb{R}^d \to \{1, \dots, K\}\)。
步骤1：回顾核支持向量机（Kernel SVM）的二分类原理
核SVM通过映射 \(\phi(\mathbf{x})\) 将数据映射到高维特征空间，并在该空间中寻找最优分离超平面：
\[\min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^N \xi_i \]
\[ \text{s.t.} \quad y_i (\mathbf{w}^\top \phi(\mathbf{x}_i) + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \]
通过核技巧，对偶问题仅依赖于核函数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)\)，无需显式计算 \(\phi(\mathbf{x})\)。最终决策函数为：
\[f(\mathbf{x}) = \operatorname{sign}\left( \sum_{i \in SV} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b \right) \]
其中 \(SV\) 表示支持向量。
步骤2：一对多（One-vs-Rest, OvR）策略的原理与实现
核心思想：为每个类别训练一个二分类SVM，将“该类”作为正类，其余所有类别作为负类。
- 训练过程：
- 对于第 \(k\) 类（\(k = 1, \dots, K\)），构造标签：
\[ y_i^{(k)} = \begin{cases} +1, & \text{if } y_i = k \\ -1, & \text{otherwise} \end{cases} \]
- 用所有数据训练一个二分类核SVM，得到决策函数：
\[ f_k(\mathbf{x}) = \sum_{i \in SV_k} \alpha_i^{(k)} y_i^{(k)} K(\mathbf{x}_i, \mathbf{x}) + b_k \]
其中 $ f_k(\mathbf{x}) $ 的符号表示是否属于第 $ k $ 类，其**绝对值大小**反映了置信度。
- 决策过程：
- 对于新样本 \(\mathbf{x}\)，计算所有 \(K\) 个分类器的决策值 \(f_k(\mathbf{x})\)。
- 两种常见决策规则：
a) 最大函数值规则：选择决策值最大的类别：
\[ \hat{y} = \arg\max_{k=1,\dots,K} f_k(\mathbf{x}) \]
该规则直接利用SVM输出（符号表示类别，数值表示到超平面的函数间隔）。
b) **置信度阈值规则**：若 $ f_k(\mathbf{x}) > 0 $ 的类别不唯一，可进一步比较置信度（例如到超平面的距离）。
- 优缺点分析：
- 优点：仅需训练 \(K\) 个分类器，训练成本相对较低。
- 缺点：当类别数 \(K\) 较大时，每个分类器的正负样本数可能极不均衡（负类样本远多于正类），影响训练效果；且可能存在“拒绝区域”（多个分类器输出为正）。
步骤3：一对一（One-vs-One, OvO）策略的原理与实现
核心思想：为每两个类别组合训练一个二分类SVM，总共训练 \(\binom{K}{2} = \frac{K(K-1)}{2}\) 个分类器。
- 训练过程：
- 对于任意两个类别 \(p\) 和 \(q\)（\(1 \leq p < q \leq K\)），从数据集中选出所有属于第 \(p\) 类或第 \(q\) 类的样本。
- 为这些样本构造二分类标签（例如 \(p\) 类标为 \(+1\)，\(q\) 类标为 \(-1\)），训练一个二分类核SVM：
\[ f_{pq}(\mathbf{x}) = \sum_{i \in SV_{pq}} \alpha_i^{(pq)} y_i^{(pq)} K(\mathbf{x}_i, \mathbf{x}) + b_{pq} \]
$ f_{pq}(\mathbf{x}) > 0 $ 表示预测为第 $ p $ 类，否则为第 $ q $ 类。
-
决策过程：通常采用投票法（Voting） 或决策有向无环图（DDAG）。
- 投票法：
a) 初始化一个长度为 \(K\) 的票数数组 \(\text{votes}[k] = 0\)。
b) 对于每个分类器 \(f_{pq}\)，如果 \(f_{pq}(\mathbf{x}) > 0\)，则 \(\text{votes}[p] \gets \text{votes}[p] + 1\)；否则 \(\text{votes}[q] \gets \text{votes}[q] + 1\)。
c) 预测类别为得票最多者：\(\hat{y} = \arg\max_k \text{votes}[k]\)。 - 平票处理：若多个类别票数相同，可进一步根据决策函数值之和或到超平面的平均距离来打破平局。
- 投票法：
-
优缺点分析：
- 优点：每个分类器只用到两个类别的数据，训练数据更均衡，且通常训练速度更快（每个子集样本较少）。
- 缺点：需要训练 \(O(K^2)\) 个分类器，当 \(K\) 很大时存储和测试开销大；且投票法可能存在“循环优胜”问题。
步骤4：核支持向量机在多类策略中的优化细节
无论采用OvR还是OvO，核心训练过程均为二分类核SVM。优化时需注意：
- 核函数选择：需统一用于所有子分类器。常用核包括：
- 高斯核（RBF）：\(K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)\)
- 多项式核：\(K(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^\top \mathbf{x}_j + c)^d\)
- 超参数调优：惩罚系数 \(C\) 和核参数（如RBF的 \(\gamma\)）通常通过交叉验证确定。在OvR/OvO中，可对所有子分类器使用相同的超参数，或为每个子问题独立调参（计算开销大）。
- 决策值校准：若需概率输出，可对每个二分类SVM的输出进行Platt缩放（拟合sigmoid函数），再组合成多类概率。
步骤5：对比与选择建议
| 方面 | 一对多（OvR） | 一对一（OvO） |
|---|---|---|
| 训练分类器数量 | \(K\) | \(K(K-1)/2\) |
| 每个分类器训练数据 | 全部样本 | 仅两个类别的样本 |
| 数据均衡性 | 可能严重不均衡 | 相对均衡 |
| 存储与测试开销 | 较小（\(K\) 个模型） | 较大（\(O(K^2)\) 个模型） |
| 预测速度 | 需计算 \(K\) 个决策函数 | 需计算 \(O(K^2)\) 个决策函数，但每个计算量小 |
| 适用场景 | \(K\) 较大，或各类样本分布相对均匀 | \(K\) 较小（通常 < 10），各类样本数均衡 |
实际应用：
- 许多机器学习库（如scikit-learn）默认使用OvO，因为其训练更快且通常精度更高。
- 当 \(K\) 很大时，OvR更常用，因其模型更简洁。
总结
多类核支持向量机通过OvR或OvO策略将多类问题分解为多个二分类问题。两种策略在训练复杂度、数据均衡性、预测方式上各有特点。在实际应用中，需根据类别数量、数据分布及计算资源进行选择。理解其原理有助于合理设计多类分类系统，并为后续学习更复杂的结构化输出SVM或多类SVM的统一优化框架（如Crammer-Singer方法）打下基础。