多标记学习的分类器圈方法范文

《软件学报》2015年第十一期

传统监督学习假定每个学习对象只隶属于一个概念标记,然而在现实问题中,学习对象通常可同时与多个概念标记相关.例如,一篇报道亚洲杯的新闻可能既与“体育”相关,又与“经济”、“博弈”等相关;一幅摄于巴黎的自然场景照片可能既与“铁塔”相关,又与“人群”、“花鸟”等相关.多标记学习(multi-labellearning)对多标记对象进行学习是这方面的一个主流研究领域,目前已在文本分类、图像标注、生物信息学、个性化推荐等很多领域取得了应用.多标记对象的标记存在相关性,否则,多个标记不会同时隶属于同一个对象.事实上,标记之间关系的发现与利用是多标记学习领域的一个关键问题.理由主要有两个方面:一是当处理多标记对象时,预测的输出结果不再是一个二元值(+1或1)而变为标记的集合,因此,输出结果的数量与标记数量呈指数增长,必须要通过发现和利用标记关系来缩减输出结果的空间;二是若不考虑标记关系,将多个标记视为独立的成分进行分类,则将失去丰富的标记关系信息,性能通常不够理想.

分类器链方法(classifierchainsmethod)及其变型是利用标记关系方面的一类有效技术,它将标记按照某种次序排成链,然后依次对链上的标记构建分类器,其中,链后面的标记可利用链前面标记所学习到的分类结果.虽然分类器链方法实现简单,但已在很多文献的实验报道中指出,分类器链方法利用标记关系取得了比不用标记关系的方法更好的性能.然而,分类器链方法的学习过程需要预先给定标记的学习次序,这个信息在真实情况中难以获得.此外,若次序选择不当,分类器链方法或许性能提高有限.一种改进的办法是集成分类器链方法(ensembleclassifierchainsmethod).它生成多个标记学习次序,然后对多个次序的结果加以集成.集成分类器链虽然在一定程度上缓解了分类器链性能受限的问题,但是标记次序的数量庞大(与标记数目呈阶乘增长),集成分类器链方法仍面临次序选择的困难,性能仍然受限.本文针对以上问题,提出分类器圈方法(classifiercirclemethod)用于多标记学习.与分类器链方法不同,该方法随机生成标记的学习次序,通过构建分类器圈结构,依次迭代地对每个标记的分类器进行更新.本文方法实现简单.实验结果表明,本文方法在多个数据集、多种不同数量的训练样本设置下,均取得比分类器链方法及一系列经典多标记方法更好的性能.本文第1节介绍多标记学习及相关工作.第2节给出本文分类器圈方法.第3节汇报实验结果.最后,第4节总结全文.

1多标记学习及相关工作

由于多标记学习适用于处理很多现实复杂对象,自多标记学习提出以来,得到很多学者的关注,发展出一系列方法.从利用标记关系的视角,这些方法大致可以分为以下3类:•第1类为一阶方法.这类方法不考虑标记之间的关系,将多标记学习问题分解为多个独立的二类分类问题来解决.这类方法实现简单,但其忽略标记之间的关系信息,很多时候性能并不理想.•第2类为二阶方法.这类方法考虑了标记对之间的关系,如相关标记与非相关标记的排序关系.这类方法考虑了标记关系,通常可取得比一阶方法更好的性能,但它无法利用更复杂的标记关系.•第3类为高阶方法.这类方法通过考虑多个乃至全部标记之间的关系来构建多标记决策函数.这类方法有时可得到更好的学习性能[15].从发现标记关系的视角,多标记学习方法也可以分为如下两类:•第1类是利用相关领域知识作为先验构造出标记之间的关系,如层次关系等.这种方法得到的标记关系往往准确且有助于提高性能,但现实情况中,这种准确的关系通常难以获得.•第2类是通过训练数据自动发现标记关系,如统计规律[27,28]等.这种方法更贴合现实任务的需求,但有时标记关系选择不当会导致性能提高受限.值得一提的是,分类器链方法是利用标记关系方面的一类简单而有效的高阶多标记学习方法.该方法的思想是:构造一条二类分类器链,链上每个节点对应于一个标记.该方法随后依次对链上的标记构建分类器,其中,链后面的标记可以结合链前面标记的学习结果用于学习当前标记.显然,分类器链方法利用到了标记之间的关系,而且分类器链方法实现简单,在不少实验报道中取得了良好的性能.然而,其学习过程需要事先给定标记的学习次序,这个信息现实情况下通常难以准确得到.此外,实验结果表明,学习次序的选择会严重影响最终的学习性能.为了缓解这个困难,Read等人提出了集成分类器链方法[13,14].该方法构造多条分类器链,其中每条分类器链对应一个随机选取的标记次序.最终,每个标记上的预测结果由多个分类器链的投票结果产生.但标记可能的学习次序数量很大(与标记数目呈阶乘函数增长),集成分类器链方法很难有效遍历所有甚至大部分次序,因此它仍存在因次序选择不当而导致性能受限的情况.为了克服以上困难,本文提出分类器圈方法.

2本文分类器圈方法

首先给出多标记学习的形式化描述.在多标记学习中,用户输入一组训练样本={(xi,yi)|i=1,2,…,m},其中,x为一个训练示例;y{+1,1}q为该示例的标记向量(labelvector),+1(或1)分别指对应位置的标记为该示例的相关(或不相关)标记;m表示训练样本数量,q为标记总数量.记=d(或d)为示例输入空间,多标记学习的目标是:学到一个决策函数h:{+1,1}q,使得对于任意未见示例z,预测其相关标记的集合.本文的分类器圈方法与分类器链方法最大的不同是:本文方法使用圈结构,而不是链.具体来说,分类器链方法沿着链结构遍历每个标记一次,分类器圈方法考虑沿着圈结构遍历每个标记若干次.图1分别给出了分类器链方法与本文分类器圈方法的示意图.直观上,分类器圈方法沿着标记或分类器的圈反复修正每个标记的分类器,充分利用到了它与每个标记或分类器之间的关系,避免分类器链方法次序选择不当时,链前面的标记难以利用它与链后面标记的关系的情况.此外,由于分类器圈方法具有这个优势,它对学习次序不敏感,本文方法可随机生成标记次序.第3节给出实验结果说明随机次序与固定次序的性能没有显著差异.

3实验结果

3.1实验数据本文在6个多标记基准数据集上进行实验比较.这些数据集来自多标记学习不同应用领域:Medical[29]来自于文本分类,Enron[30]来自于电子邮件分析,Scene[6]来自于图片分类,Emotions[31]来自于音乐标注,Yeast[7]来自于基因功能预测,Genbase[32]来自于蛋白质分类.表1给出数据集的统计信息。

3.2评价指标本文采用多标记学习领域两个常用的评价指标1macroF和1microF来衡量方法的预测性能,值越大性能越好。

3.3比较方法本文比较如下多标记方法:1)BR(binaryrelevant)方法[2,21]:该方法不考虑标记关系,独立训练每个标记的二类分类器,是一阶方法.2)ML-kNN(multi-labelk-nearestneighbor)方法[17]:该方法拓展k近邻方法用于处理多标记学习问题.它没有考虑标记间的关系,属于一阶方法,近邻个数采用文献的推荐参数k=10.3)CLR(calibratedlabelrank)方法[18]:该方法考虑相关标记与不相关标记的排序关系,属于二阶方法.4)CC(classifierchains)方法[13,14],即,分类器链方法:该方法考虑多个标记间的关系,属于高阶方法.5)ECC(ensembleclassifierschains)方法,即,集成分类器链方法:与CC类似,属于高阶方法.分类器链的集成个数采用文献推荐参数K=10.6)CCE(classifiercircle)方法,即,本文的分类器圈方法:本文方法考虑了全部标记之间的关系,属于高阶方法.轮数T固定为5.以上方法的二类分类器采用线性Logistic回归,线性Logistic回归采用Liblinear工具包[33]实现.其中,Logistic回归模型的正则化系数C根据5折交叉验证确定.

3.4实验结果对每个数据集,本文随机选取80%样本做训练,余下20%做测试.实验重复30次,表2给出平均结果和标准差,()表示CCE方法显著优(劣)于比较方法(成对t检验根据95%置信度),括号里的数字为对应方法性能序(越小性能越好).表中还给出每个方法的平均序.可见,CCE方法取得了不错的性能,在1macroF与1microF两个指标上都取得了最小的平均序.CCE方法在3个数据集上取得了最好的1macroF性能,在4个数据集上取得了最好的1microF性能。

4结束语

利用标记关系来提高学习性能,是多标记学习的关键.分类器链方法及其变型是这方面一类经典做法,但它依赖于标记学习次序的选择.这个信息现实情况难以可靠得到,使用不当会使性能提高有限.针对这个问题,本文提出了分类器圈方法CCE.CCE通过圈结构迭代训练每个标记的分类器,避免了分类器链方法学习次序选择的问题.实验结果表明,CCE方法取得了比分类器链方法及一系列经典多标记学习方法更好的性能.未来将研究更精确设置CCE的迭代轮数(比如经验风险不再变化)、将CCE用于大规模数据以及CCE工作的理论基础.

作者：王少博 李宇峰 单位：计算机软件新技术国家重点实验室