一种具有保序性的带权多标记学习算法

宋中山，周玮瑜，孙翀，艾勇，刘越

(中南民族大学 计算机科学学院，湖北省制造企业智能管理工程技术研究中心，武汉 430074)

多标记学习的概念源自文档分类中的歧义性问题[1]，一个对象可关联多个标记.如一篇名为“David Beckham to face trial over speeding offense”的新闻，尽管它的新闻分类可同时属于“体育”、“社会”，甚至“娱乐”，但用户在搜索这条新闻时，会倾向于在“体育”类别下检索，甚至一些新闻网站可能只会把它归于“体育”类中.这说明在一个事物对应的标记集合中，每个标记对这个事物描述的“程度”各异，标记集合内的每个标记应存在既定权重.若算法未同时考虑标记间的序及权重，会影响预测的准确性.本文针对以上问题，提出一种具有保序性的带权多标记学习算法WMLARP(Weighted Multi-label Learning Algorithm with Rank Preservation).WMLARP主要针对标记间的相关性，分别从“相关-无关”、“相关-相关”标记对入手来考虑标记间的序和权重.在“相关-无关”标记对上计算标记间的序关系，序关系是用来区分示例的相关标记与无关标记的，分别将标记值带入线性函数，函数值较大的对应标记即为相关标记；在“相关-相关”标记对上计算标记间的权重关系，同样都是示例的正确标记，仍存在哪个标记对示例的重要性程度更大的问题，因此，在两个相关标记间计算权重关系，决定输出的标记序列中各个标记的位置.

多标记学习的经典算法主要分为两类：数据转换类算法和方法适应类算法[2].前者将问题从多标记转换为多个单标记，以已有的单标记算法学习.BR(Binary Relevance)算法[3]是典型的数据转换类算法，因其将多标记问题分解为多个独立的单标记问题求解，忽略了标记间的相关性.LP(Label Powerset)算法[4]考虑了标记间的序，将标记集合内的标记两两一组作为一个新的标记，模型的输出为每个标记组合的概率值；在此基础上改进的RAkEL(Randomk-labelsets)算法[5]、PPT(Pruned Problem Transformation)算法[6]、CLR(Calibrated Label Ranking)算法[7]均计算了标记间的序.适应类算法则将单标记算法改进适应到多标记问题，Adaboost.MH、Adaboost.MR算法[8]是在Adaboost[9]上进行扩展的两种算法，可最小化汉明及排序损失.基于SVM的多标记算法[10]将训练集中每个标记看作SVM分类器；概率生成模型[11]是在训练集中为每个标记生成不同的词，那么标记集合元素便由其标记所生成的混合词来产生，并对每个混合词组中的词分布进行学习.另一个发展方向是考虑标记间的权重大小，CHEN等人[12]提出了基于BR的优化算法，通过在BR中加入拷贝和选择，考虑标记的概率因素.CHASE算法[13]通常用于不完整的数据集上，将其转换为基于概率的数据集，各个标记被赋予一组概率值作为权重.多媒体领域中通常会涉及到给标记赋予权重的过程，例如，JIANG等人[14]将每个乐器标记赋予了不同的权重，即可判别给定的音乐中有哪些演奏乐器.标记间的相关性对模型质量的影响尤为关键，若未充分挖掘标记间的序与权重，会使算法应用受限.因此，本文提出了一种具有保序性的带权多标记学习算法WMLARP，分别在两种类型的标记对上挖掘标记间的关系，可有效提高生成模型的质量.

1 问题描述与形式化定义

WMLARP的目标是从训练集中学习并输出一组实数函数，可区分不同示例对应的标记集合，且输出的结果综合考虑了标记间的序关系与权重大小.设d维示例空间：X=d，标记集：y={1,…,Q}，样本集D={(x1,Y1),(x2,Y2), …,(xm,Ym)}，其中，|D|=m，xiX，Yi2y，多标记分类器h:X2y.

假定对D中任一样本(xi,Yi)，Yi均服从y上的同一概率分布，存在函数fk=wk,x+bk，其中，ky.多标记算法的目标是从D中习得Q个决策函数fn(ny)，h=(f1,f2, …,fQ)，WMLARP对这一组决策函数的损失函数最小化来求得最优解.

2 损失函数

定义1(相关-相关)标记对.对于某个示例，(相关-相关)标记对为两个均与该示例相关的标记组成的标记对，即：对D中任意(xi,Yi)，标记RYi，R′Yi，则这两个标记构成的标记对(R,R′)为(相关-相关)标记对，简写为：(R-R′).

2.1 标记间序关系

对D中某一样本(xi,Yi)，WMLARP训练一组决策函数f构成分类器h，即：存在函数fk=wk,xi+bk，其中kYi，wkd为第k个标记对应的“权值向量”，bk为第k个标记对应的“偏置”.决策模型的损失函数取排序损失函数，该函数用于考察在样本标记集合的排序序列中出现排序错误的情况，损失函数R(f)公式为：

(1)

其中R(xi)={(y1,y2)|f(xi,y1)≤f(xi,y2),(y1,y2)

2.2 标记间权重

对于D中样本(xi,Yi)的任一标记对(R-R′)，有fR(x)=wR,xi+bR，fR′(x)=wR′,xi+bR′.假设在有序标记集Yi中，标记R排在标记R′的前面，那么标记R的权重值应大于标记R′的权重值：WeightR>WeightR′.对于任意的xi，标记R比R′更相关的概率值用权重概率PR,R′(f)来表示.设(R-R′)间的真实权重概率为则以交叉熵的形式定义权重概率的损失函数为：

PR,R′(f)).

(2)

3 模型学习

WMLARP算法分别对训练集每个样本示例的(R-U)和(R-R′)进行训练，在(R-U)上，定义超平面，根据样本点到该平面上的距离关系构建分类器，同时最小化排序损失；在(R-R′)上，定义标记对的权重概率，计算大小以确定标记集中标记权重的排序.

3.1 (R-U)的线性分类问题求解

WMLARP在(R-U)上，定义超平面，根据样本点(xi,Yi)到该平面上的距离关系构建决策函数来区分xi的R与U，同时最小化排序损失，训练(xi,Yi)的线性分类模型的具体算法如算法1所述.

定义3(R-U)的决策边界.将向量空间划分为两个集合，决策边界g(xi)表示为：

wR-wU,xi+bR-bU= 0.

(3)

定义4(R-U)的间隔.基于(R-U)的决策边界的间隔m(xi)表示为：

(4)

具体到训练集D上：

(5)

假设标记集合中的元素是排好序的，那么公式(5)应为正值，即wR-wU,xi+bR-bU> 0，对参数w正则化，可得wR-wU,xi+bR-bU≥ 1.那么最大化间隔可定义为如下优化问题：

(6)

理想情况下，公式(6)可进一步被优化：

(7)

(8)

(9)

那么，标记对的线性分类问题求解算法的输入为训练集D和参数I，对于每一个标记对(R-U)，定义其决策边界与间隔，可在最小化间隔的过程中求得最优参数；另外，定义排序损失函数，将间隔与排序损失函数转化为二次规划问题，输出线性模型参数.

算法1训练分类模型.

输入：训练集D和参数I

输出：Q个分类模型的参数w,b

//fori= 1:m；

//for each(R-U)，(R-U)

//对当前标记对(R-U)定义决策边界(公式(3))；

//根据决策边界g(xi)定义间隔(公式(4))；最大化间隔求解参数(公式(6))；

//最小化损失函数来优化参数(公式(1))；

//将间隔与损失函数求解转换为二次规划问题，求解参数；

//end for

//end for

标记对的线性分类问题求解算法可解决标记间的序关系，然而其并未考虑标记间的权重关系，于是WMLARP算法第2步对(R-R′)上的权重进行定义并计算相对大小.

3.2 (R-R′)的权重概率计算

WMLARP在(R-R′)标记对上，根据3.1中计算的样本点(xi,Yi)的决策函数，定义标记对的权重概率，计算大小以确定标记集中标记权重的排序，优化(xi,Yi)的线性分类模型参数w，具体算法如算法2所述.

定义5(R-R′)的权重概率.它表示标记R比标记R′更相关的概率，参数δ为标记集内调节标记权重比值的算子，公式为：

(10)

其中PR,R′(f)[0,1].

如果WeightR>WeightR′，权重概率PR,R′(f)应无限趋近于1；如果WeightR

(11)

最小化损失函数得到进一步优化的分类模型参数wR：

(12)

那么，优化分类模型参数算法的输入为训练集D和参数w,δ，为当前(R-R′)定义权重概率，计算实际权重概率并以此定义损失函数，最小化损失函数的过程中求解最优参数，输出参数w.

算法2优化分类模型参数.

输入：训练集D和参数w,δ

输出：Q个分类模型的参数w

//fori= 1:m；

//for each(R-R′)，R,R′Yi；

//对当前标记对(R-R′)定义权重概率(公式(10))；

//对当前标记对(R-R′)计算实际权重概率(公式(11))；

//最小化损失函数来优化参数(公式(2))；

//end for

//end for

3.3 标记集序列预测

以上是如何构建分类模型，下文将确定标记集合内标记序列及标记集合大小以输出最终结果.

定义6标记集合大小.标记集合大小S(x)可由如下规则确定：

S(x)= |{fk(x)>t(x)}|,

(13)

其中t(x)为相应阈值函数.

设阈值函数t(x)=w*,f*(x)+b*为线性函数，f*(x)=(f(x,y1),f(x,y2), …,f(x,ym))Td，w*d为权值向量，b*为偏置.那么标记集合大小S(x)的求解过程也就是最小化损失函数的过程：

(14)

最终，基于线性模型和阈值函数的解，可得多标记分类模型：

h(x)= {yj|wj,x+bj>w*,f*(x)+b*,

1≤j≤m}.

(15)

4 实验与分析

4.1 数据集及实验环境

本文数据集选用yeast数据集[11](Yeast Saccharomyces cerevisiae)，每个基因按照功能被分为多个类别.yeast数据集包括2417个样本，103个属性，14个类别标记，其基数为4.237，密度为0.303；取其中62%的样本数据作为训练集，38%作为测试集.本文使用的yeast数据集为经人工预处理的数据集，将样本对应的标记集合处理为服从某个概率分布的标记序列.本文实验了3种概率分布：随机分布、均匀分布、正态分布.

实验环境为8G内存的Windows7操作系统，其CPU为Intel Core i7-6700，主频为3.40GHz.本算法实验平台为MATLAB，部分用Python语言进行数据处理.

4.2 实验结果与分析

本文提出的WMLARP算法充分考虑了标记间的相关性，同时考虑了标记间的序关系以及相对权重大小，使得模型能准确给出示例对应的标记序列.为了实现标记间相对权重大小序列，验证WMLARP算法的有效性，本文将就1-AveragePrecision、2-OneError、3-RankingLoss、4-MRR(Mean Reciprocal Rank)这四项评价指标与经典RankSVM算法进行对比.1-AveragePrecision考察在计算序关系的多分类系统中排在相关标记之前的标记仍是示例的相关标记的情况；2-OneError用于统计标记序列中排在靠前位置的标记不是示例的相关标记的情况；3-RankingLoss考察标记序列中出现排序错误的情况；4-MRR考察标记序列的优劣，根据示例的相关标记在序列中的排序位置来评估分类器的性能.

WMLARP中参数δ用来调节数据集上权重占比，将δ的取值范围定为{0.32,0.37,…,0.77}，分别取值进行实验，观察4个指标的变化，分别取3个变化阶段中最具代表性的3个值：0.37,0.43,0.50代入公式进行实验.

假设标记权重服从[0,1]内的连续随机分布，实验结果如图1所示.δ=0.50时，除了在1-AveragePrecision上WMLARP比RankSVM低0.1个百分点，其余3项指标WMLARP均优于RankSVM；δ=0.37、δ=0.43时，WMLARP的4项指标均明显优于RankSVM，其中，δ取0.43时WMLARP性能最佳，权重关系被充分挖掘，WMLARP性能可明显优于RankSVM.

图1 WMLARP与RankSVM四项指标对比(随机分布)

假设标记服从[0,1]内的均匀概率分布，实验结果如图2所示.WMLARP的四项评价指标均明显优于RankSVM，且MRR提升最高；当δ=0.43时，WMLARP性能最优.

图2 WMLARP与RankSVM四项指标对比(均匀分布)

假设标记服从正态概率分布，实验结果如图3所示.δ=0.50时，WMLARP与RankSVM相比，1-AveragePrecision低0.02个百分点，3-RankingLoss高0.02个百分点，其余两项指标WMLARP均明显优于RankSVM；δ=0.37、δ=0.43时，WMLARP的4项指标均优于RankSVM，其中，δ取0.43时，WMLARP性能最佳.

由以上分析可看出，在同时考虑标记间的序及权重大小关系的情况下，WMLARP的性能明显优于RankSVM，特别是当标记权重服从均匀分布的情况时，WMLARP性能最优，原因可能是均匀分布的标记权重相对更容易被WMLARP挖掘，这说明标记的权重分布情况对分类结果有影响.当δ的取值发生变化时，WMLARP的实验结果也会发生变化，这说明对数据集赋予某个权重值的占比会对模型的性能产生影响.δ取值过小时，权重占比太小，WMLARP在计算权重关系上作用不大；δ取值过大时，会造成模型的过拟合；因此，当δ取在稍小于0.5的值时，分类模型的质量更优.另外，WMLARP的参数δ共取了3次值，在第3次取值时存在两项指标差别不大的结果，其他情况下均优于RankSVM，这说明WMLARP挖掘标记间关系的性能更优.综上，WMLARP算法充分考虑了标记间的相关性，性能相对较优.

图3 WMLARP与RankSVM四项指标对比(正态分布)

5 结语

本文提出的WMLARP算法通过计算标记集合内标记间的权重概率，来考虑原始标记权重对分类结果的影响，有效提高了多标记学习算法的精度；同时，充分挖掘了多标记学习问题中标记间的相关性，使模型具有更好的实用性.实验验证了WMLARP的性能.然而，WMLARP的算法复杂度与数据集规模有一定的关系，当规模较大时，有效降低算法的复杂度成为下一步的主要工作.