ml-multiclass-strategieslisted

# 多分类拆解策略 — 用二分类器搭出 N 类工程 ## R — 原文 (Reading) > "现实中常遇到多分类学习任务。……多分类学习的基本思路是'拆解法'，即将多分类任务拆为若干 > 个二分类任务求解。……这里的关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集 > 成。" > > — 周志华，《机器学习》第3章 3.5节 "多分类学习" > "容易看出，OvR 只需训练 N 个分类器，而 OvO 需训练 N(N-1)/2 个分类器，因此，OvO 的存 > 储开销和测试时间开销通常比 OvR 更大。但在训练时……OvO 的每个分类器仅用到两个类的样例， > 因此，在类别很多时，OvO 的训练时间开销通常比 OvR 更小。" > > — 周志华，《机器学习》第3章 3.5节 > "对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。……并不 > 是编码的理论性质越好，分类性能就越好……一个理论纠错性质很好、但导致的二分类问题较难的编 > 码，与另一个理论纠错性质差一些、但导致的二分类问题较简单的编码，最终产生的模型性能孰强孰 > 弱很难说。" > > — 周志华，《机器学习》第3章 3.5节 --- ## I — 方法论骨架 (Interpretation) 多数经典分类器是二分类的；要解决 N 类问题，标准做法是**拆解法**两步走——先把 N 类拆成若干二分类任务各训一个分类器，再把它们的预测集成为最终结果。全部工程决策落在三个策略的选择上： 1. **OvO（一对一）**: N 类两两配对，训 N(N-1)/2 个分类器，测试时投票。每个分类器只见两类样本——训练快，但存储与测试开销随 N 平方膨胀。 2. **OvR（一对其余）**: 每次一类为正、其余全为反，只训 N 个分类器。存储省，但每个分类器都要吃全部训练样例——类别多时训练反而更慢。多个分类器同时判正时，取置信度最大者。 3. **MvM（多对多）/ ECOC**: 每次若干类为正、若干类为反，靠编码矩阵系统化组织；预测编码与各类编码比距离、取最近者。冗余编码带来**纠错能力**——个别分类器出错仍可能解码出正确类别。 两条反直觉纪律贯穿其中：其一，性能上 OvO 与 OvR 在多数情形差不多，选择依据是开销结构而非精度；其二，ECOC 码本不是越长/理论码距越大越好——拆分方式形成的两个"类别子集"区分难度不同，理论纠错好但子任务难的编码可能输给纠错稍差但子任务简单的编码。 --- ## A1 — 书中的应用 (Past Application) ### 案例 1: ECOC 纠错实例——f₂ 出错仍解码 C₃ (c21) - **问题**: 四个类别用五位二元码拆解后，某个二分类器在测试时出错，结果会崩吗？ - **方法论的使用**: 作者构造具体演算：正确预测编码应为 (-1,+1,+1,-1,+1)；假设 f₂ 出错把第二位翻成 -1，得到错误编码 (-1,-1,+1,-1,+1)。按欧氏距离与各类编码逐一比较，该错误编码仍离 C₃ 的编码最近。 - **结论**: 单个分类器的错误被编码间的距离"吸收"了——这就是"纠错输出码"名称的由来；码越长纠错能力越强，但训练开销增大且有限类别数的组合有限、码长超过一定范围便失去意义。 - **结果**: 确立了"以码距换容错"的设计哲学，并引出理论最优编码是 NP 难、实践中非最优编码往往已足够好的工程立场。 ### 案例 2: OvO/OvR 开销对照分析 -