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

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

　　纠错输出编码（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。