从二分类到多分类

在遇到多分类任务时，有些二分类学习方法可直接推广到多分类，例如线性判别分析LDA，但在更多情形下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。

一般的，对于N个类别$C_1, c_2, \cdots,C_N$，多分类学习器的基本思想是拆解法，即将多分类任务拆为若干个二分类任务求解。在测试时，对这些二分类器的预测结果进行集成以获得最终的多分类结果，比如说可以选择概率最大的那个结果。

拆分策略

OvO策略

给定数据集$D={(xi y_i)}{i=1}^{m}$，$y_i \in {C_1, C_2, \cdots, C_N }$，OvO将这N个类别两两配对，从而产生$\frac{N(n-1)}{2}$

个二分类任务。在一个二分类任务中，把一种类别当做正例(随便选定两者中的一个)，另一种类别当做负例。

在测试阶段，新样本将同时提交给所有分类器，将会得到$\frac{N(N-1)}{2}$个分类结果，最终结果结果可通过投票产生：即把被预测得最多的类别作为最终结果。

OvR策略

对于OvR，则是每次将一个类别的样例作为正例，所有其他类的样例作为反例来训练N个分类器。在测试时，若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果；若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别作为分类结果。

OvO于OvR策略比较

OvR相比于OvO只需要训练N个分类器，而OvO需训练$\frac{N(N-1)}{2}$个分类器，因此，OvO的存储开销和测试时间开销通常比OvR更大。但在训练时，OvR的每个分类器均使用全部训练样例，而OvO的每个分类器仅用两个类的样例，因此，在类别很多时，OvO的训练时间开销通常比OvR更小。至于预测性能，则取决于具体的数据分布，在多数情况下两种策略差不多

MvM

MvM是每次将若干个类作为正类，若干个其他类作为反类。MvM的正、反类构造必须有特殊的设计，不能随意选取。有一种常用的MvM技术：纠错输出码(Error Correcting Output Codes, ECOC)。

纠错输出码ECOC

ECOC工作过程主要分为两步：

编码：对N个类别分别做M次划分，每次划分将一部分类别划分为正类，一部分划分为反类，从而形成一个二分类训练集；这样一共产生M个训练集，可以训练出M个分类器。
解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个编码。将这个编码与每个类别各自的编码进行比较，返回其中距离(海明距离或者欧式距离)最小的类别作为最终预测结果

类别划分通过编码矩阵指定，编码矩阵有多种形式，常见的主要有二元码和三元码。二元码将每个类别分别指定正类和反类；三元码在正、反类之外，还可指定停用类。

在编码矩阵中，使用“+1”、“-1”分别表示正、反例，0表示不使用该类样本即停用类。在上图的例子中，(a)图中的测试用例最后分类结果应归为$C_3$类，(b)图中的测试用例最后分类结果应归为$C_2$类。

为什么叫做“纠错输出码”呢？原因是在测试阶段，ECOC编码对分类器的错误有一定的容错和纠正能力。例如，图(a)中对测试用例的正确预测编码是$(-1,+1,+1,-1,+1)$，假设在预测时某个分类器出错了，假设$f_2$分类器出错了，从而导致了错误的编码$(-1,-1,+1,-1,+1)$，但基于这个编码仍能产生正确的最终分类结果$C_3$。一般来说，对同一个学习任务，ECOC编码越长，纠错能力越强。然而，编码越长意味着所需训练的分类器越多，计算、存储开销都会增大；另一方面，对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义。

对于等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。因此，在码长较小时可根据这个原则计算出理论最优编码。然而一般很难求的最优的编码，选择一个较优的编码就足够了。