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

时间:2021-06-12 10:45:01 论文 我要投稿

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

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

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

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

【纠错输出编码相关论文综述和要点】相关文章:

2017年论文文献综述写作要点及格式05-07

和晨间锻炼相关的论文06-18

小学数学特点和趋势综述论文06-23

细胞的物质输出和输入11-26

关于论文的文献综述03-23

医学论文综述内容要求及综述范文05-25

部队心理教育和疏导工作研究综述论文06-17

基于GSM红外报警系统设计和PDU编码的技术分析论文04-20

综述论文范文07-14