【机器学习基础】第九课:多分类学习

多分类任务,一对一,一对其余,多对多,纠错输出码,海明距离

Posted by x-jeff on December 5, 2019

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.前言

现实中常遇到多分类学习任务,通常有两种解决办法:

  1. 直接将二分类学习方法推广到多分类。
  2. 基于一些基本策略,利用二分类学习器解决多分类问题。

其中第2种方法更为常用,也是本文所要介绍的内容。

‼️不失一般性,考虑N个类别$C_1,C_2,…,C_N$,多分类学习的基本思路是“拆解法”,即将多分类任务拆为若干个二分类任务求解。通常可分为两步:

  1. 先对问题进行拆分,然后为拆出的每个二分类任务训练一个分类器。
  2. 在测试时,对这些分类器的预测结果进行集成以获得最终的多分类结果。

本文主要介绍拆分策略

最经典的拆分策略有三种:

  1. “一对一”(One vs. One,简称OvO)。
  2. “一对其余”(One vs. Rest,简称OvR)。
  3. “多对多”(Many vs. Many,简称MvM)。

OvR亦称OvA(One vs. All),但是OvA这个说法不严格,因为不可能把“所有类”作为反类。

2.OvO

给定数据集$D={ (\mathbf x_1,y_1), (\mathbf x_2,y_2), … , (\mathbf x_m,y_m) },y_i \in { C_1,C_2, … ,C_N }$。OvO将这N个类别两两配对,从而产生N(N-1)/2个二分类任务。最终结果可通过投票产生:即把被预测得最多的类别作为最终分类结果。

亦可根据各分类器的预测置信度等信息进行集成。

3.OvR

OvR则是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器。

  • 在测试时若仅有一个分类器预测为正类,则对应的类别标记作为最终分类结果。
  • 若有多个分类器预测为正类,则通常考虑各分类器的预测置信度,选择置信度最大的类别作为分类结果。

👉OvO与OvR示意图:

容易看出,OvR只需训练N个分类器,而OvO需训练N(N-1)/2个分类器,因此,OvO的存储开销和测试时间开销通常比OvR更大。

⚠️但在训练时,OvR的每个分类器均使用全部训练样例,而OvO的每个分类器仅用到两个类的样例,因此,在类别很多时,OvO的训练时间开销通常比OvR更小。

至于预测性能,则取决于具体的数据分布,在多数情况下两者差不多。

4.MvM

MvM是每次将若干个类作为正类,若干个其他类作为反类。显然,OvO和OvR是MvM的特例。

⚠️MvM的正、反类构造必须有特殊的设计,不能随意选取。

这里我们介绍一种最常用的MvM技术:“纠错输出码”(Error Correcting Output Codes,简称ECOC)。

4.1.纠错输出码

ECOC的工作过程分为两步:

  1. 编码:对N个类别做M次划分,每次划分将一部分类别划为正类,一部分划为反类,从而形成一个二分类训练集;这样一共产生M个训练集,可训练出M个分类器。
  2. 解码:M个分类器分别对测试样本进行预测,这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较,返回其中距离最小的类别作为最终预测结果。

⚠️类别划分通过“编码矩阵”指定。编码矩阵有多种形式,常见的主要有二元码三元码。前者将每个类别分别指定为正类和反类,后者在正、反类之外,还可指定“停用类”。

在ECOC编码示意图中,“+1”、“-1”分别表示学习器$f_i$将该类样本作为正、反例;三元码中“0”表示$f_i$不使用该类样本。

海明距离:

在信息编码中,两个合法代码对应位上编码不同的位数称为码距,又称海明距离

举例如下:1010100110从第一位开始依次有第一位、第四位和第五位不同,则海明距离为3。

为什么称为“纠错输出码”呢?
这是因为在测试阶段,ECOC编码对分类器的错误有一定的容忍和修正能力。例如上图(a)中,对测试示例的正确预测为类$C_3$,即编码为(-1,+1,+1,-1,+1),假设在预测时某个分类器出错了,例如$f_2$出错从而导致了错误编码(-1,-1,+1,-1,+1),但基于这个编码仍能产生正确的最终分类结果$C_3$。

⚠️在三元码中,对于“0”,即学习器没有使用的类别,海明距离记为0.5。

‼️一般来说,对同一个学习任务,ECOC编码越长,纠错能力越强。然而,编码越长,意味着所需训练的分类器越多,计算、存储开销都会增大;另一方面,对有限类别数,可能的组合数目是有限的,码长超过一定范围后就失去了意义。

5.参考资料

  1. 海明距离(百度百科)