多分类学习

有些二分类学习方法（如LDA）可以直接推广到多分类，但现实中我们更多地是基于一些策略，把多分类任务分解为多个二分类任务，利用二分类模型来解决问题。有三种最经典的拆分策略，分别是一对一，一对其余，和多对多。

一对一

一对一（One vs. One，简称OvO）的意思是把所有类别两两配对。假设样例有N个类别，OvO会产生 %7D%7B2%7D#card=math&code=%5Cfrac%7BN%28N-1%29%7D%7B2%7D&id=FdMhy) 个子任务，每个子任务只使用两个类别的样例，并产生一个对应的二分类模型。测试时，新样本输入到这些模型，产生 %7D%7B2%7D#card=math&code=%5Cfrac%7BN%28N-1%29%7D%7B2%7D&id=jqECV) 个分类结果，最终预测的标记由投票产生，也即把被预测得最多的类别作为该样本的类别。

一对其余

一对其余（One vs. Rest，简称OvR）在有的文献中也称为一对所有（One vs. All，简称OvA），但这种说法并不严谨。因为OvR产生 个子任务，每个任务都使用完整数据集，把一个类的样例当作正例，其他类的样例当作反例，所以应该是一对其余而非一对所有。OvR产生 个二分类模型，测试时，新样本输入到这些模型，产生 个分类结果，若只有一个模型预测为正例，则对应的类别就是该样本的类别；若有多个模型预测为正例，则选择置信度最大的类别（参考模型评估与选择中的比较检验）。

OvO和OvR各有优劣：OvO需要训练的分类器较多，因此OvO的存储开销和测试时间开销通常比OvR更大；OvR训练时要用到所有样例，因此OvR的训练时间开销通常比OvO更大。测试性能取决于具体的数据分布，大多情况下这两个拆分策略都差不多。

多对多

多对多（Many vs. Many，简称MvM）是每次将多个类作为正例，其他的多个类作为反例。OvO和OvR都是MvM的特例。书中介绍的是一种比较常用的MvM技术——纠错输出码（Error Correcting Outputs Codes，简称ECOC）。

MvM的正反例划分不是任意的，必须有特殊的构造，否则组合起来时可能就无法定位到预测为哪一类了。ECOC的工作过程分两步：

• 编码：对应于训练。假设有N个类别，计划做M次划分，每次划分把一部分类别划为正类，一部分类别划分为反类，最终训练出M个模型。而每个类别在M次划分中，被划为正类则记作+1，被划为负类则记作-1，于是可以表示为一个M维的编码。
• 解码：对应于预测。把新样本输入M个模型，所得的M个预测结果组成一个预测编码。把这个预测编码和各个类别的编码进行比较，跟哪个类别的编码距离最近就预测为哪个类别。

类别划分由编码矩阵（coding matrix）指定，编码矩阵有多重形式，常见的有二元码（正类为+1，负类为-1）和三元码（多出了停用类，用0表示，因为有停用类的存在，训练时可以不必使用全部类别的样例）。举个三元码的例子：

| | f1

| f2

| f3

| f4

| f5

| 海明距离

| 欧氏距离

| | —- | —- | —- | —- | —- | —- | —- | —- | | | -1 | +1 | -1 | +1 | +1 | 4 | 4 | | | +1 | -1 | -1 | +1 | -1 | 2 | 2 | | | -1 | +1 | +1 | -1 | +1 | 5 | 2
| | | -1 | -1 | +1 | +1 | -1 | 3 | | | 测试样本
| -1 | -1 | +1 | -1 | +1 | - | - |

这里一共有4个类别，对应每一行。计划做5次划分，得到f1至f5共五个二分类器，对应每一列。可以看到每一个类别有一个5位的编码表示。测试时，把新样本输入到5个模型，得到预测编码。然后计算这个预测编码和每个类别编码的距离。这里举了海明距离（不同的位数的数目）和欧氏距离作为例子。可以看到测试样本与类别2的距离最近，因此预测该样本为类别2。

特别地，为什么称这种方法为纠错输出码呢？因为ECOC编码对分类器的错误有一定的容忍和修正能力。即使预测时某个分类器预测成了错误的编码，在解码时仍然有机会产生正确的最终结果。具体来说，对同一个学习任务，编码越长，纠错能力越强。但是相应地也需要训练更多分类器，增大了计算和存储的开销。

对同等长度的编码来说，理论上任意两个类别之间的编码距离越远，纠错能力越强。但实际任务中我们一般不需要获取最优编码，一方面非最优编码已经能产生不错的效果；另一方面，即使获得理论上最优的编码，实际性能也不一定最好。因为机器学习还涉及其他一些方面，在划分多个类时产生的新问题难度往往也不同，有可能理论最优的编码产生的类别子集难以区分，问题难度更大，从而使得性能下降。