传统监督学习假定每个学习对象只隶属于一个概念标记^[1],然而在现实问题中,学习对象通常可同时与多个概念标记相关.例如,一篇报道亚洲杯的新闻可能既与“体育”相关,又与“经济”、“博弈”等相关;一幅摄于巴黎的自然场景照片可能既与“铁塔”相关,又与“人群”、“花鸟”等相关.多标记学习(multi-label learning)^{[2, 3]}对多标记对象进行学习是这方面的一个主流研究领域,目前已在文本分类^{[4, 5]}、图像标注^[6]、生物信息学^[7,8,9]、个性化推荐^{[10, 11]}等很多领域取得了应用.

多标记对象的标记存在相关性,否则,多个标记不会同时隶属于同一个对象.事实上,标记之间关系的发现与利用是多标记学习领域的一个关键问题^[12].理由主要有两个方面:一是当处理多标记对象时,预测的输出结果不再是一个二元值(+1或-1)而变为标记的集合,因此,输出结果的数量与标记数量呈指数增长,必须要通过发现和利用标记关系来缩减输出结果的空间;二是若不考虑标记关系,将多个标记视为独立的成分进行分类,则将失去丰富的标记关系信息,性能通常不够理想.

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

本文第1节介绍多标记学习及相关工作.第2节给出本文分类器圈方法.第3节汇报实验结果.最后,第4节总结全文.

1 多标记学习及相关工作

由于多标记学习适用于处理很多现实复杂对象,自多标记学习提出以来,得到很多学者的关注,发展出一系列方法.从利用标记关系的视角,这些方法大致可以分为以下3类^[3]:

•     第1类为一阶方法.这类方法不考虑标记之间的关系,将多标记学习问题分解为多个独立的二类分类问题^{[6, 8, 17]}来解决.这类方法实现简单,但其忽略标记之间的关系信息,很多时候性能并不理想.

•      第2类为二阶方法.这类方法考虑了标记对之间的关系,如相关标记与非相关标记的排序关系^{[7, 18, 19]}.这类方法考虑了标记关系,通常可取得比一阶方法更好的性能,但它无法利用更复杂的标记关系.

•      第3类为高阶方法.这类方法通过考虑多个^{[14, 20]}乃至全部^{[21, 22]}标记之间的关系来构建多标记决策函数.这类方法有时可得到更好的学习性能^[15].

从发现标记关系的视角,多标记学习方法也可以分为如下两类:

•      第1类是利用相关领域知识作为先验构造出标记之间的关系^{[23, 24, 25, 26]},如层次关系等.这种方法得到的标记关系往往准确且有助于提高性能,但现实情况中,这种准确的关系通常难以获得.

•      第2类是通过训练数据自动发现标记关系,如统计规律^{[27, 28]}等.这种方法更贴合现实任务的需求,但有时标记关系选择不当会导致性能提高受限.

值得一提的是,分类器链方法^{[13, 14]}是利用标记关系方面的一类简单而有效的高阶多标记学习方法.该方法的思想是:构造一条二类分类器链,链上每个节点对应于一个标记.该方法随后依次对链上的标记构建分类器,其中,链后面的标记可以结合链前面标记的学习结果用于学习当前标记.显然,分类器链方法利用到了标记之间的关系,而且分类器链方法实现简单,在不少实验报道中取得了良好的性能^[12-15].然而,其学习过程需要事先给定标记的学习次序,这个信息现实情况下通常难以准确得到.此外,实验结果表明,学习次序的选择会严重影响最终的学习性能^[16].为了缓解这个困难,Read等人提出了集成分类器链方法^{[13, 14]}.该方法构造多条分类器链,其中每条分类器链对应一个随机选取的标记次序.最终,每个标记上的预测结果由多个分类器链的投票结果产生.但标记可能的学习次序数量很大(与标记数目呈阶乘函数增长),集成分类器链方法很难有效遍历所有甚至大部分次序,因此它仍存在因次序选择不当而导致性能受限的情况.为了克服以上困难,本文提出分类器圈方法.

2 本文分类器圈方法

首先给出多标记学习的形式化描述.在多标记学习中,用户输入一组训练样本D={(x_i,y_i)|i=1,2,…,m},其中,x为一个训练示例;y∈{+1,-1}^q为该示例的标记向量(label vector),+1(或-1)分别指对应位置的标记为该示例的相关(或不相关)标记;m表示训练样本数量,q为标记总数量.记 $ \chi ={{\mathbb{R}}^{d}}$(或 ${{\mathbb{Z}}^{d}}$)为示例输入空间,多标记学习的目标是:学到一个决策函数h:Χ→{+1,-1}^q,使得对于任意未见示例z,预测其相关标记的集合.

本文的分类器圈方法与分类器链方法最大的不同是:本文方法使用圈结构,而不是链.具体来说,分类器链方法沿着链结构遍历每个标记一次,分类器圈方法考虑沿着圈结构遍历每个标记若干次.图 1分别给出了分类器链方法与本文分类器圈方法的示意图.直观上,分类器圈方法沿着标记或分类器的圈反复修正每个标记的分类器,充分利用到了它与每个标记或分类器之间的关系,避免分类器链方法次序选择不当时,链前面的标记难以利用它与链后面标记的关系的情况.此外,由于分类器圈方法具有这个优势,它对学习次序不敏感,本文方法可随机生成标记次序.第3节给出实验结果说明随机次序与固定次序的性能没有显著差异.

具体来说,本文方法随机地将q个标记{l₁,l₂,…,l_q}连成一个圈,其中,l_j(1≤j≤q)表示一个标记.不失一般性,记产生的圈为{l_τ(1),l_τ(2),…,l_τ(q)},其中,τ:{1,2,…,q}→{1,2,…,q}是一个随机排列函数.本文方法依次对{l_τ(1), l_τ(2),…,l_τ(q)}构建二类分类器(如Logistic回归、支持向量机等),该过程循环T次,每次分类器更新利用之前的学习结果.形式化看,记B为二类分类学习算法,沿着标记圈循环T次,得到q×T个二类分类器h_k,j,即

${h_k}_{,j} \leftarrow B({D_k}_{,j}),k = 1,2, \ldots ,T,j = 1,2, \ldots ,q $

(1)

利用之前的学习结果存在多种方式,例如,利用前面所有分类器的结果;利用前面q个分类器的结果(如果已得分类器的数量小于q,则利用之前所有分类器的结果).为了防止过拟合现象,本文采用后者,即,仅利用之前q个分类器的结果.具体来说,第k轮的第j个标记上的分类器所用的单标记训练集D_k,j按如下方式构造:

${D_{k,j}} = \{ ([{x_i},pre_{k,j}^i],y_i^{(\tau (j))})|i = 1,2,...,m\} $

(2)

其中,pre表示分类器的预测结果:

$pre_{k,j}^i = [{h_{k,1}}([{x_i},pre_{k,1}^i]),...,{h_{k,j - 1}}([{x_i},pre_{k,j - 1}^i]),{h_{k - 1,j}}([{x_i},pre_{k - 1,j}^i]),...,{h_{k - 1,q}}([{x_i},pre_{k - 1,q}^i])] $

(3)

为简便符号,记第0轮所有标记上的预测结果为空,即h_0,j(x)≡0,则对于k=1,2,…,T和j=1,2,…,q,有|pre_k,j|=q.预测阶段,对于未见示例z,依下式预测其标记向量:

$\hat y = h(z) = [{h_{T,{\tau ^{ - 1}}(1)}}([z,pr{e_{T,{\tau ^{ - 1}}(1)}}]),{h_{T,{\tau ^{ - 1}}(2)}}([z,pr{e_{T,{\tau ^{ - 1}}(2)}}]),...,{h_{T,{\tau ^{ - 1}}(q)}}([z,pr{e_{T,{\tau ^{ - 1}}(q)}}])] $

(4)

算法1和算法2分别给出本文方法的训练和预测过程.

算法1. 本文CCE方法训练过程.

输入:训练数据集D={(x_i,y_i)∈ $ {{\mathbb{R}}^{d}}$×{+1,-1}^q|i=1,2,…,m};轮数T.

输出:q×T个二类分类器h_k,j,k=1,2,…,T,j=1,2,…,q;排列函数τ.

1. 初始化D'={([x_i,0],y_i)|i=1,2,…,m},其中,0是长度为q的零向量

2. 随机初始化一个排列函数τ:{1,2,…,q}→{1,2,…,q}

3. for k←1 to T

4.     for j←1 to q

5.         $ D{'_{k,j}} \leftarrow \{ ({x'_i},y_i^{(\tau (j))})|i = 1,2,...,m\} $

6.         $ {h_{k,j}} \leftarrow B(D{'_{k,j}})$

7.         for all x' in D'

8.             x'^(d+j)←h_k,j(x')

9.         end for

10.     end for

11. end for

算法2. 本文CCE方法预测过程.

输入:q×T个二类分类器h_k,j,k=1,2,…,T,j=1,2,…,q;排列函数τ;待预测示例z∈ $ {{\mathbb{R}}^{d}}$.

输出:预测结果 $ \hat y$.

1. 初始化z'=[z,0],其中,0是长度为q的零向量

2. for k←1 to T

3.     for j←1 to q

4.         z'^(d+j)←h_k,j(z')

5.     end for

6. end for

7. $ \hat y \leftarrow [{z'^{(d + {\tau ^{ - 1}}(1))}},{z'^{(d + {\tau ^{ - 1}}(2))}},...,{z'^{(d + {\tau ^{ - 1}}(q))}}]$

分类器圈方法与集成分类器链方法的时间复杂度相当.具体而言,分类器圈方法训练和预测的时间复杂度分别为 $ O(T \cdot q \cdot {F_B}(m,d + q))$和 $ O(T \cdot q \cdot {F_B}'(d + q))$,其中, $ {F_B}( \cdot , \cdot )$和 $ {F_B}'( \cdot )$分别为二类分类器用于训练和测试的时间复杂度;集成分类器链的训练和预测时间复杂度分别为 $ O(K \cdot q \cdot {F_B}(m,d + q))$和 $O(K \cdot q \cdot {F_B}'(d + q)) $,其中,K是集成个数.实验中,K的取值与T相当.因此,与集成分类器链方法相比,分类器圈方法没有增加时间开销.但后面的实验结果表明,分类器圈方法取得了更好的性能.

3 实验结果 3.1 实验数据

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

•      LCard指标记基数(label cardinality),即,每个样本相关标记的平均个数:

$LCard(D) = \frac{1}{m}\sum\limits_{i = 1}^m {\mathop \sum \limits_{j = 1}^q } \left[\kern-0.15em\left[ {y_i^{(j)} = + 1} \right]\kern-0.15em\right] $

(5)

其中, $ \left[\kern-0.15em\left[ \cdot \right]\kern-0.15em\right]$表示:

$\left[\kern-0.15em\left[ \pi \right]\kern-0.15em\right] = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ if }}\pi {\rm{ holds}}}\\ {0,{\rm{ otherwise}}} \end{array}} \right. $

(6)

•      LDen指标记密度(label density),即,标记基数相对于标记数目的比例:

$LDen(D) = \frac{1}{q}LCard(D) $

(7)

•      LDiv指标记多样性(label diversity),即,样本相关标记集合的总数:

$LDiv(D) = \left| {\{ y} \right|\exists x:\left( {x,y} \right) \in \Delta \} | $

(8)

3.2 评价指标

本文采用多标记学习领域两个常用的评价指标F_macro¹和F_micro¹来衡量方法的预测性能,值越大性能越好.

•      F_macro¹指每个标记上F¹指标的平均,计算方式如下:

$F_{{\rm{macro}}}^1 = \frac{1}{q}\sum\limits_{j = 1}^q {\frac{{2 \cdot T{P_j}}}{{2 \cdot T{P_j} + F{N_j} + F{P_j}}}} $

(9)

其中,

$T{P_j} = |\{ {x_i}|y_i^{(j)} = + 1 \wedge {h^{(j)}}({x_i}) = + 1,i = 1,2,...,m\} | $

(10)

$F{N_j} = |\{ {x_i}|y_i^{(j)} = + 1 \wedge {h^{(j)}}({x_i}) = - 1,i = 1,2,...,m\} | $

(11)

$F{P_j} = |\{ {x_i}|y_i^{(j)} = - 1 \wedge {h^{(j)}}({x_i}) = + 1,i = 1,2,...,m\} | $

(12)

分别为true positive(真阳性)、false negative(假阴性)和false positive(假阳性)样本总数.

•      F_micro¹指所有样本在所有标记上的总体F¹指标,计算方式如下:

$F_{{\rm{micro}}}^1 = \frac{{2 \cdot \sum\limits_{j = 1}^q T {P_j}}}{{2 \cdot \sum\limits_{j = 1}^q T {P_j} + \sum\limits_{j = 1}^q F {N_j} + \sum\limits_{j = 1}^q F {P_j}}} $

(13)

关于F_macro¹和F_micro¹的详细介绍可参阅文献[3, 20].

3.3 比较方法

本文比较如下多标记方法:

1) BR(binary relevant)方法^{[2, 21]}:该方法不考虑标记关系,独立训练每个标记的二类分类器,是一阶方法.

2) ML-kNN(multi-label k-nearest neighbor)方法^[17]:该方法拓展k近邻方法用于处理多标记学习问题.它没有考虑标记间的关系,属于一阶方法,近邻个数采用文献的推荐参数k=10.

3) CLR(calibrated label rank)方法^[18]:该方法考虑相关标记与不相关标记的排序关系,属于二阶方法.

4) CC(classifier chains)方法^{[13, 14]},即,分类器链方法:该方法考虑多个标记间的关系,属于高阶方法.

5) ECC(ensemble classifiers chains)方法^{[13, 14]},即,集成分类器链方法:与CC类似,属于高阶方法.分类器链的集成个数采用文献推荐参数K=10.

6) CCE(classifier circle)方法,即,本文的分类器圈方法:本文方法考虑了全部标记之间的关系,属于高阶方法.轮数T固定为5.

以上方法的二类分类器采用线性Logistic回归,线性Logistic回归采用Liblinear工具包^[33]实现.其中, Logistic回归模型的正则化系数C根据5折交叉验证确定.

3.4 实验结果

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

表 3、表 4进一步给出了60%和40%训练样本下的实验结果.可以看出,CCE方法同样在两个指标上都取得了比ECC及其他多标记方法更好的性能.总体上讲,在一共18种情况中,CCE方法均在11种情况下取得了最好的F_macro¹和F_micro¹性能,而ECC方法只分别在3种和5种情况下取得相应的性能.这一结果进一步验证了本文方法的有效性适用于不同数量的训练样本.

图 2给出了模型参数对CCE方法和ECC方法的预测性能的影响.CCE方法的参数为迭代轮数,ECC方法的参数为集成分类器个数.实验采用80%训练样本,重复20轮,汇报平均F_macro¹和F_micro¹结果.可见,CCE方法对模型参数不敏感.当迭代轮数大于3时,CCE方法通常取得比较稳定的结果.ECC方法在有些情况下对模型参数敏感(如Genbase数据集).在相同参数情况下,CCE方法的性能通常优于ECC方法.

图 3、图 4进一步给出了CCE方法在随机标记序和固定标记序的实验结果(采用80%样本做训练,重复30轮).成对t检验(95%置信度)的结果表明,随机序与固定序的性能没有显著差异.即,CCE方法的性能对学习次序不敏感.

4 结束语

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