纠错输出编码(ECOC)综述和基本原理

纠错输出编码相关论文综述和要点

纠错输出编码（ECOC）综述和基本原理 目录

<机器学习导论> ....................................................................................................................... 1

《Solving Multiclass Learning Problems via Error-Correcting Output Codes》 ....................... 2

A Subspace to ECOC .................................................................................................................. 3

中文参考文献 ........................................................................................................................... 5

<机器学习导论>

在纠错输出编码中，主要的分类任务通过由基学习器实现的一组子任务来定义。其思想是：将一个类从其他类区分开来的原始任务可能是一个困难的问题。作为替代，我们定义一组简单的分类问题，每个专注于原始任务的一个方面，并通过组合这些简单的分类器来得到最终的分类器。

这时，基分类器是输出为-1/+1的二元分类器，并且有一个K*L的编码矩阵W，其K行是关于L个基学习器dj类的二元编码。例如，M(2, ) [ 1 1 1 1]表示若一个样本属于第2类(C2)，则该样本应在h1和h4上取负值，在h2和h3上取正值；M(, 3) [ 1 1 1]T可理解为第三个基分类器h3的任务是将属于C1类的样本与属于C2和C3类的样本区分开。同时M(, 3)也决定了如何构造基分类器h3的训练样本集T3：所有标记为C2类及C3类的样本形成正样本 3 ，而标记为C1类的实例构成负样本 3 ，对h3的训练应使得 xi T3，当xi 3 时，h3(xi) 1；当xi 3 时，h3(xi) 1。

这样，编码矩阵使得我们可以用二分类问题定义多分类问题，并且这是一种适用于任意可以实现二分基学习器的学习算法的方法，例如，线性或多层感知器，决策树或初始定义的两类问题的SVM。

典型的每类一个判别式的情况对应于对角矩阵，其中L=K，例如，对于K=4，我们有

W=【】

这里的问题是：如果某一个基学习器存在错误，就会有误分类，因为类的码

纠错输出编码相关论文综述和要点

字之间非常相似，因而纠错码采用的方法是使L>K来增加码字之间的汉明距离。一种可能的方法是类逐对分开，其中对i<j有一个不同的基学习器将ci和cj分开。在这种情况下，当K=4时，L=K(K-1)/2，编码矩阵为W=[]。

其中的0表示无关，这就是说，训练d1来将C1与C2分开并且在训练中不使用属于其他类的实例。类似地，一个实例属于C2如果有d1=-1,并且d4=d5=+1,并且我们不考虑d2,d3,d6的值。这种方法的问题是对于比较大的K，逐对分开是不可行的。

方法是预先设定L值，然后寻找w使得以汉明距离衡量的行间距以及列间距离都尽可能的大。对K类问题而言，存在2k-1-1中可能列，即两类问题。这是因为K位可以写成2K种不同的形式和补（比如，“0101”和“1010”，从我们的角度来看，二者定义相同的判别式），将所有可能组合除以2减1，因为全为0（或1）的列是无用的。例如K=4时，我们有

1 1M 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

当K很大时，对于一个给定的L值，我们从2k-1-1列中选取L列，我们希望W的这些列尽可能的不相同，以便每个基学习器所学习的子任务尽可能互不相同。同时，我们希望W的行业尽可能的不相同，使得在一个活多个基学习器失效时，可以获得最大的纠错。 ECOC可以用投票方式来表述，其中W的元素wij可以看作投票权值：

yi wijdj

j 1L

然后我们选取具有最高yi的类。通过求加权和并选择最大值（判别类别）取代寻求一个精确的匹配使得dj也不必是二元的，二是可取-1到+1之间的任意值，以软确定性取代硬判决。注意位于0到1之间的pj值（例如后验概率）可以很简单地被转换为-1到+1之间的dj值： Dj=2pj-1

。

ECOC的一个问题是：由于编码矩阵W被设置为先验，因此不能保证由W的列所定义的子任务一定是简单。Dietterich的研究表明二分树可能要比多分树大，而且当使用多层感知器时，后向传播可能收敛较慢。

《Solving Multiclass Learning Problems via Error-Correcting Output Codes》

最早的ECOC文献：

纠错编码设计。

定义一个K*L维二值矩阵为纠错输出编码矩阵。矩阵的列数即为编码的长度，矩阵的行数即为多分类问题的分类类数。矩阵中的每行M(r,·)表示一个类别的码文。

对于K类问题，一个好的纠错输出编码矩阵应该满足两个要求：

纠错输出编码相关论文综述和要点

一是行尽量分开。即每个类别的码文与其它类别的码文间的汉明距离要尽可能大。

二是列尽量分开。每个基学习器决策函数hi应该与其余的基学习器决策函数hj，j不等于i，是相互独立的。这可以通过强调列i和其余列之间的汉明距离要大以及列i与其它列的补之间的距离要大来获得。

编码的纠错输能力与行间汉明距离直接相关。而列间汉民距离需要大的目的还不明确。如果两列列i和列j十分相似或完全一样，那么基学习器的判决函数hi和hj的决策结果会含有相同的错误。仅当错误出现在不同的编码位置时，纠错输出编码才是有效的，所以不同位置同时出现的错误的机会必须少。当同时出现错误较多时，纠错码将不能纠正。

互补列之间的错误也是相互关联的。….当两列互补时，他们之间的汉明距离也最大。因此列尽量分开的条件就是试图使列既不相同又不互补。

除非分类类别数大于等于5，否则同时满足上述两个条件是很困难的。例如，当分类类别为3时，仅有8

这8列中，4列与另外4列中还有一列是全0或是全1列，这对于分类时毫无作用的。结果是仅剩下三列可以作为纠错输出编码矩阵的列，这与一对多的编码数是一样的。

通常地，如果是K类问题，除去互补和全0或全1的列，最多还有2k-1-1列可用，对于4类问题，我们能获得一个7列输出编码矩阵，使得行间的最小汉明距离为4. 对于5类问题，我们能获得一个15列输出编码矩阵，使得行间的最小汉明距离为

文中介绍了四种设计纠错输出编码的方法：Exhaustive Codes(EC); Column Selection from Exhaustive Code(CSEC); Randomized Hill Climbing; BCH编码[1,2]选择哪种设计方法由分类类数K

本文仅将障碍分为四类（采集样本有困难），可以用EC编码的方法。

A Subspace to ECOC

二分类器（基学习器）的独立性是设计ECOC矩阵的关键问题（Key factor），若基学习器相互之间不独立，则ECOC方法失效。本文为了提高基学习器之间的独立性，提出了一种新的有效的ECOC矩阵设计方法。主要思想是基于不同的特征子空间训练基学习器，即子空间ECOC。提出的算法为了增加更多独立的基学习器，可以设计更长输出代码的ECOC矩阵。In addition to creating more independent classifiers in the proposed technique，ECOC matrices with longer codes can be built.

纠错输出编码相关论文综述和要点

对子空间ECOC方法、传统ECOC方法、一对一、一对多方法进行了对比实验，实验结果表明本文提出的方法与state of the art coding methods相比，分类准确率有所提高。

三个最有名的多类分类方法是one-versus-all (OVA) , one-versus-one (OVO) (Anand et al., 1995; Clark and Boswell, 1991), and Error Correcting Output Codes (Dietterich and Bakiri, 1995).如**方法。

一对多的基本思路；

一对一的基本思路；

ECOC的基本思想；

Nc×L维编码矩阵M，其中矩阵中元素取值为{-1,+1}，L表示每类需要编码的个数。编码矩阵表示L个二类机器学习问题，其中每一列代表一个基学习器。也就是说每一列表示一个二分类器，命名为二分器hj，将一系列样本分成两个元类。例如模式样本x属于第i类，当且仅当Mij=+1时，x为第j个二分器的正样本；当且仅当Mij=-1时，x为第j个二分器的负样本。例如，式中给出了四分类问题{c1,…,c4}用六个基学习器{h1,…,h6}学习多分类器对应编码矩阵M的一种可能情况。在M矩阵中，每一列对应一个二分基学习器，hj，每一行对应一个目标类的特定二值编码向量。例如，h3识别两个元类：由原始类1和原始类4组成的第一元类，以及有其余两个原始类（类2和类3）组成的第二元类。

1 1M 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

当测试一个为分类模式，x*时，每一个二分器（基学习器）输出一个码值+1或是-1，组成L维编码输出向量。编码输出向量与所有目标类对应的二值编码向量逐一进行对比，最接近于编码输出向量的二值编码向量所对应的目标类即为模式x*的预测类别。逐一对比的过程称为解码，常用的解码方法为汉明距离(Hamming distance)法，该方法通过寻找编码输出向量和二值编码向量之间的最小距离来确定待测模式的预测类别。

yh arg(min|M(r,i) fi(x*)|) r {1,...,Nc}2i 1 L

式中arg表示求取得最小值时对应的类别r；yh {1,...,Nc}；M(r,i)表示第r类对应的二值编码向量第i个元素值，fi(x*)表示待测模式x*对应编码输出向量第i个元素值。

纠错输出编码相关论文综述和要点

ECOC方法扩展为三值编码{-1,0,+1}，0表示“无关”。扩展后的ECOC称为稀疏ECOC，不扩展的称为稠密ECOC。传统的一对多和一对一方法可以用ECOC方法来表示，在一对一方法中，编码矩阵有Nc(Nc-1)/2列，每列对应将ci和cj分开，该列中第i行为+1，第j行为-1，其余行都为0。在一对多方法中，编码矩阵M是一个NC*NC维对角矩阵，其中主对角线元素都为+1，其余元素都为-1。值得指出的是，无论是稀疏方法还是稠密方法，测试模式的编码输出矩阵都不能包含0元素，这是因为每个基分类器的输出只能为{-1,+1}

其余的还有很多多类分类方法，如有向无序图，

据笔者所知，还没有相关特征选择在ECOC独立性方面的应用。

中文参考文献