第 3 章 · 第 6 讲 / 共 7 讲
多分类学习
只会二分类的算法，怎么对付十个类别？拆开来用：OvO、OvR、ECOC。
能对比 OvO 和 OvR 的分类器数量与各种开销（并说出那个反直觉的结论）；能讲清 ECOC 的编码与解码两步，并用一个具体错码说明「纠错」是怎么发生的。
上一讲结束时，我们手上只有「分两类」的工具。可现实里常常是 N 类。办法很朴素：拆。这一讲的全部内容，就是「怎么拆」和「怎么合」。
3.5 多分类学习只会二分类怎么办
前面两节（3.3、3.4）解决的都是二分类：只有"是/不是"两种答案。但现实中经常是 N 类：这个瓜是西瓜、南瓜、冬瓜还是黄瓜？
书里说得很实在："有些二分类学习方法可直接推广到多分类，但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。"
这一节讲的就是这些"基本策略"。核心思路只有两个字：拆解。
① 拆：把多分类任务拆成若干个二分类任务；
② 训：为拆出来的每一个二分类任务，训练一个分类器；
③ 合：测试时，把这些分类器的预测结果集成起来，得到最终答案。
所以这一节真正要回答的只有两个问题：怎么拆？怎么合？ 不同的拆法和合法，就是不同的策略。
策略一：OvO（一对一）
One vs. One，读作"一对其一"。数据集是 D = {(x1,y1), …}，yi ∈ {C1, C2, …, CN}。
怎么拆：把 N 个类别两两配对。每配一对，就造一个二分类任务——"是 Ci 还是 Cj？"，其中 Ci 的样例当正例，Cj 的样例当反例。
一共多少个？从 N 个里挑 2 个的组合数：
比如 4 个类，就是 4×3/2 = 6 个分类器：{C₁C₂}、{C₁C₃}、{C₁C₄}、{C₂C₃}、{C₂C₄}、{C₃C₄}。
怎么合：测试时，新样本同时喂给所有分类器，得到 N(N−1)/2 个预测。然后投票——被预测得最多的类别就是最终结果。
4 个类、6 个分类器。假设某个测试样本的结果是：{C₁C₂}→C₁，{C₁C₃}→C₁，{C₁C₄}→C₁，{C₂C₃}→C₃，{C₂C₄}→C₂，{C₃C₄}→C₃。
数票：C₁ 得 3 票，C₂ 得 1 票，C₃ 得 2 票，C₄ 得 0 票。所以判为 C₁。
一个有意思的细节：每个类被投票的次数上限是 N−1（因为它只出现在 N−1 对里）。所以 C₁ 得 3 票就是满分——全票通过。
策略二：OvR（一对其余）
One vs. Rest，读作"一对其余"（书里也提了另一个名字 OvA = One vs. All，但原书说 OvA 这个说法不严格，因为不可能把"所有类"都当反类）。
怎么拆：每次把一个类的样例当正例，其余所有类的样例当反例。这样每个类造一个任务，共 N 个分类器。
怎么合：书里分了两种情况：
- 只有一个分类器预测为正 → 那个类就是答案。
- 有多个分类器都预测为正 → "通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果"。
因为每个分类器都是独立训练的，各自给了"是"的答案，没有互相协商。比如"苹果"和"番茄"都可能被判为"圆的红色物体"，两个分类器都说"是"。
这时就只能比"谁更确定"。置信度就是概率输出的高低——对率回归天然就有这个（3.3 节那个 p1），所以用它做 OvR 很自然。
OvO 和 OvR 到底怎么选
书里这一段信息密度很高，几乎每一句都是考点，我们拆成表格看：
| 维度 | OvO | OvR | 结论 |
|---|---|---|---|
| 分类器数量 | N(N−1)/2 | N | OvR 少得多 |
| 每个分类器用的样本 | 只用到两个类的样例 | 用到全部样例 | — |
| 训练时间 | 类别很多时反而更小 | 类别很多时更大 | OvO 占优（N 大时） |
| 存储开销 | 更大（模型多） | 更小 | OvR 占优 |
| 测试时间 | 更大（要跑 N(N−1)/2 个模型） | 更小 | OvR 占优 |
| 预测性能 | 取决于具体的数据分布，多数情形下两者差不多 | 打平 | |
这个表格里有个反直觉的地方，值得停下来想一下：分类器多的 OvO，训练时间居然可能更小？
原因就在"每个分类器用多少样本"这一行。OvO 的每个分类器只看两类样本（比如 m=10000 个样本、10 个类，每个分类器可能只看 2000 个），而 OvR 的每个分类器要看全部 10000 个。虽然 OvO 要训 45 个模型，但每个都小得多。类别越多、每类样本越少，这个差距越明显。
类别很多、训练时间吃紧 → OvO；模型要小、预测要快（比如线上服务）→ OvR。
再用 sklearn 的话：OneVsOneClassifier 和 OneVsRestClassifier 就是这两个，多分类器默认的行为在文档里写得很清楚。
策略三：MvM（多对多）
Many vs. Many：每次把若干个类当正类、另外若干个类当反类。
显然 OvO 和 OvR 都是 MvM 的特例（OvO 是"1 个对 1 个"，OvR 是"1 个对其余"）。
但书里紧接着说了一句关键的限定："MvM 的正、反类构造必须有特殊的设计，不能随意选取。"为什么不能随便？
因为如果随便挑，你可能造出一堆"几乎没法分"的二分类问题。比如把"西瓜、南瓜"当正类、"黄瓜、冬瓜"当反类——如果这些类的样本在特征空间里混在一起，这个二分类器根本学不好，白白浪费时间。
更重要的原因藏在后面：不同的划分方式，导致二分类问题本身的难度不同。所以划分得好不好，直接决定最终模型好不好。这也是下面 ECOC 那两段的伏笔。
ECOC：把"纠错码"的思想搬过来
纠错输出码（Error Correcting Output Codes，ECOC）是最常用的 MvM 技术，由 Dietterich 和 Bakiri 在 1995 年提出。
书里一句话点明了它的野心："将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。"
它的工作过程分两步，这两步一定要分清：
第一步：编码（训练阶段）
对 N 个类别做 M 次划分。每次划分把一部分类划为正类、一部分划为反类，形成一个二分类训练集。M 次划分 → M 个训练集 → 训练出 M 个分类器。
这些划分用一个编码矩阵记录下来：每一行是一个类别，每一列是一个分类器。格子里的值表示"这个分类器把这个类当正例还是反例"。
| 类别 | f1 | f2 | f3 | f4 | f5 |
|---|---|---|---|---|---|
| C1 | −1 | +1 | −1 | +1 | −1 |
| C2 | +1 | −1 | −1 | +1 | +1 |
| C3 | −1 | +1 | +1 | −1 | +1 |
| C4 | +1 | −1 | +1 | −1 | −1 |
读法："+1" 表示该分类器把这个类的样本当正例，"−1" 表示当反例。
按这张表，f2 那一列是 (+1, −1, +1, −1)，意思是：分类器 f₂ 把 C₁ 和 C₃ 的样例作为正例，C₂ 和 C₄ 的样例作为反例——这正是原书图 3.5(a) 里的描述。每一行则是一个类别的"身份证"：C₃ 的编码是 (−1, +1, +1, −1, +1)。
编码矩阵有两种常见形式：
| 类型 | 每个格子的取值 | 特点 |
|---|---|---|
| 二元码 （Dietterich & Bakiri, 1995） |
只有 +1 / −1 | 每个分类器都必须对每一类给出明确的正/反判断 |
| 三元码 （Allwein et al., 2000） |
+1 / −1 / 0 | 0 表示"停用类"——这个分类器不使用该类的样本，既不参与训练也不参与判断。更灵活 |
书里举了三元码的例子："在图 3.5(b) 中，分类器 f₄ 将 C₁ 类和 C₄ 类的样例作为正例，C₃ 类的样例作为反例"——剩下的 C₂ 就是被"停用"了（矩阵里对应位置是 0）。
第二步：解码（测试阶段）
M 个分类器各自对测试样本给出一个预测（是/否），把这些预测按顺序排成一个长度 M 的编码。然后拿这个"预测编码"和每个类别自己的编码逐一比较距离，距离最小的那个类别就是答案。
距离怎么算？常用欧氏距离或海明距离（数不同位置的个数）。书里的例子说"若基于欧氏距离，预测结果将是 C₃"。
为什么叫"纠错"？一个具体例子
这是本节最精彩的部分，一定要跟着算一遍。
假设测试样本真实的类别是 C3，那它的正确编码应该是 (−1, +1, +1, −1, +1)（看表里 C₃ 那一行）。
现在假设分类器 f2 判错了——它本该输出 +1，却输出了 −1。于是我们拿到的编码变成：
| f1 | f2 | f3 | f4 | f5 | 与预测码的距离 | |
|---|---|---|---|---|---|---|
| 预测得到的编码 | −1 | −1 | +1 | −1 | +1 | — |
| C1 | −1 | +1 | −1 | +1 | −1 | 4 |
| C2 | +1 | −1 | −1 | +1 | +1 | 3 |
| C3 | −1 | +1 | +1 | −1 | +1 | 1 ← 最小 |
| C4 | +1 | −1 | +1 | −1 | −1 | 2 |
距离为 1（只有 f₂ 那一位不同），是所有类别里最小的——所以最终仍然判为 C₃，正确答案。
一个分类器错了，但它的错被其他分类器"投票"抵消了。因为每个类的编码都足够"独特"，一位出错不足以把它认成别的类。
这跟通信里的纠错码是一个道理：发一串 1011，路上翻了 1 位变成 1001，接收方还是能靠"离哪个合法码最近"还原出 1011。ECOC 就是把这个思路搬到了分类上。
码长 M 的取舍
书里给了两条权衡，方向相反：
- M 越大，纠错能力越强。因为编码之间的差异位更多，能容忍更多分类器同时出错。
- 但 M 越大，代价也越大。"编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大。"
还有一条更微妙的限制："对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义。"
因为每一列（每个分类器）只能把类别分成"正类组"和"反类组"。N 个类别，可能的划分方式是有限的。如果把同一列重复写两遍，那多出来的那个分类器提供不了任何新信息——码变长了，但"有效信息"没增加。
所以码长不是越长越好，而是有个上限。
两个容易忽略的深层提醒
"对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。因此，在码长较小时可根据这个原则计算出理论最优编码。"
但——"码长稍大一些就难以有效地确定最优编码，事实上这是 NP 难问题"。
好消息是："通常我们并不需获得理论最优编码，因为非最优编码在实践中往往已能产生足够好的分类器。"
这一段原书写得很克制，但意思很锋利："并不是编码的理论性质越好，分类性能就越好，因为机器学习问题涉及很多因素。"
具体来说：把多个类拆成两个"类别子集"，不同拆解方式所形成的两个类别子集的区分难度往往不同。于是可能出现这种情况——
编码 A：理论纠错性质很好，但它造出来的二分类问题都很难；
编码 B：理论纠错性质差一些，但它造出来的二分类问题都很简单。
"最终产生的模型性能孰强孰弱很难说。"
这背后是机器学习里一个反复出现的道理：理论上的好性质，只有在问题本身"难度相同"的前提下才等价于实际的好效果。
随堂自测 · 3.5
在 ECOC 的三元码编码矩阵中，格子里的 "0" 表示什么？
原书说得很明确：三元码中"0"表示"停用类"，即 fi 不使用该类的样本。三元码的灵活性正来自这里——允许某些分类器"弃权"，而不是强迫它在每一类上都站队。这也解释了为什么书上举例 f₄ 时只说了正例和反例，剩下的 C₂ 就是被停用的。
本讲小结
- 拆解法三步：拆 → 训 → 合。
- OvO：N(N−1)/2 个模型，投票；OvR：N 个模型，比置信度。
- OvO 模型多但每个只看两类样本，所以类别多时训练反而更快；代价是存储和测试开销大。
- ECOC：编码阶段做 M 次划分，解码阶段找编码距离最近的类，一位出错还能纠回来。
- 理论纠错能力好 ≠ 实际性能好 —— 因为不同划分造出的二分类问题难度不同。
下一讲：类别不平衡。998 个反例配 2 个正例，一个「永远猜反例」的模型精度 99.8%，却一个正例都抓不到。
卡住了就直接问我 —— 把没看懂的那一句原样抄给我，我单独展开讲，不用客气。