基于全局和局部标签相关性的MIMLSVM改进算法①

李村合,张振凯

(中国石油大学(华东)计算机与通信工程学院,青岛 266580)

在利用机器学习中的传统监督学习[1]解决实际问题时,常见的做法是先对真实的对象进行特征提取,用一个特征向量来描述这个对象,这样就得到了一个示例(instance),然后把示例与该对象所对应的类别标记(label)关联起来,就得到了一个例子(example).在拥有了一个较大的例子集合之后,就可以利用某种学习算法来学得示例空间与标记空间之间的一个映射,该映射可以预测未见示例的标记.在待学习对象具有明确的、单一的语义时,上面的学习框架已经取得了巨大的成功.但是真实世界中的对象往往具有复杂的含义,只用一个示例和一个标记来表达过于简单,在刚开始的表示阶段就失去了很多重要的信息.

为了解决上述问题,多示例多标签[2,3]框架应运而生.在该框架下一个对象用一组示例来表示,并且和一组类别标记相关联.比如一篇文章中的每个部分可以用一个示例来表示,而这篇文章可能同时属于“娱乐”、“旅游”、“经济”等不同的类别.多示例多标签已成功应用到了场景分类、基因功能注释、图像标注等领域,彰显了其强大的学习能力和潜力.

支持向量机(Support Vector Machines,SVM)[4]是一种高效的分类识别方法,在解决高维模式识别问题呈现出其独特的优势.它通过寻找一个最优分类超平面来实现分类.支持向量机以统计学习理论中的VC 维(Vapnik-Chervonenkis Dimension)理论[5]以及结构风险最小原理为基础,最终的决策函数由少量支持向量决定,其数学形式简单,同时有效克服样本空间的高维性带来的计算复杂问题,已经在系统辨识、人脸检测及生物信息等领域中被用到.多示例多标记框架下的许多算法或直接使用了SVM 或对其改造使其适应多示例多标记的学习,这些算法在学习过程中已经取得了不错的分类效果.在真实的学习问题中,标记之间通常具有局部标记相关性及全局相关性,如果仅仅考虑其一有可能会影响到实验分类的准确率,因此如何兼顾考虑二者是能否取得良好实验效果的关键.

本文的整体组织结构如下：第1 部分介绍相关工作,第2 部分提出改进的算法,第3 部分给出了实验及结果,最后进行了总结.

1 相关工作

传统的监督学习框架是一种单示例单标记(Single-Instance Single-Label,SISL)学习框架,形象化的来说,另x为 示例空间,y为标记空间,则学习的任务是从数据集{(x1,y1),(x2,y2),···,(xm,ym)}中 学得函数f:x→y,其中xi∈X为一个示例,yi∈y为 示例xi所属的类别标记[1].

多示例学习(Multi-Instance Learning,MIL)[2]中的每个对象是用一个示例包来表示,同时该对象只与一个类别标记相关联.给定数据集{ (x1,y1),(x2,y2),···,(xm,ym)},目标是学得f:2x→y.其中xi⊂x为 一组示例{xi1,xi2,···,xi,ni},xij∈x(j=1,2,···,ni),yi∈y为 与xi的 类别标记.ni为xi中所含示例的个数.近年来,也出现了很多多示例学习算法,比如Diverse Density[6]、EM-DD[7]、k-近邻,决策树算法RELIC[8],神经网络算法RBF-MIP[9]等.多示例学习也被广泛的应用于自然场景分类、基于内容的图像检索、WEB 目录页面推荐以及机器人领域中[10].

多标记学习(Multi-Label Learning,MLL)[2]中一个对象是用一个示例来表示,同时该对象与多个类别标记相关联.多标签学习近年来得到了广泛的研究.根据所使用的标签相关程度,它可以分为三类[11]：一阶,二阶和高阶.对于第一组,不考虑标签相关性,并将多标签问题转换为多个独立的二元分类问题.一个众所周知的例子是二元相关(BR)算法[12],它为每个标签独立地训练一个分类器.对于第二组,考虑成对标签关系.例如,校准标签排名(CLR)[13]将多标签学习问题转化为成对标签排序问题.最后,对于第三组,所有其他标签对每个标签施加的影响都被考虑在内.例如,分类器链(CC)[14]将多标签学习问题转换为二元分类问题链,将标注标签编码为特征.另一种考虑所有标签相关性的方法是通过学习一个潜在的标签空间来捕捉更高级别的标签语义.通常,这是通过标签矩阵的低秩分解[15]获得的.最近,Yeh CK 等人[16]也提出了深度学习方法来学习联合特征和标签嵌入.这些方法与典型相关分析(CCA)高度相关[17],它学习了一个潜在的子空间,以便将实例表示与相应的标签对齐.

要发挥多示例多标记框架的能力,要设计有效的学习算法.传统的监督学习、多示例学习以及多标记学习都可以看作是多示例多标记的退化表示形式,因此设计多示例多标记算法的一种思路是使用退化策略,将多示例多标记问题转化为多示例或者是多标记学习问题,进而再进一步转化为传统监督学习问题,最后使用传统的机器学习来解决相应问题.但是在退化的过程中会有重要信息丢失,比如标记之间的联系信息、示例与标记之间的联系信息等,进而影响到了最后的分类效果.为了避免退化策略中信息丢失问题的发生,衍生了另一种算法思路,即直接改造机器学习中相应的的算法使其适应多示例多标签框架.

基于退化策略,周志华等人提出了MIMLBOOST算法[3]和MIMLSVM 算法[3],基于正则化机制以及最大化间隔策略提出了D-MIMLSVM 算法[1]和M3MIML算法[18].MIMLBOOST 算法首先将多示例多标记样本(Xi,Yi)转 化为|y|个 多示例单标记样本{([Xi,y],φ[Xi,y])|y∈Y}( |y|是标记空间中标记的数目),其中,每一个示例[Xi,y]都 是由示例集合Xi和 类别标记y拼接而成,当类别标记y∈Yi时 ,φ [Xi,y]=+1,否则φ [Xi,y]=-1.转化完成后,多示例多标记问题已经变为多示例学习问题了,然后使用多示例学习中的MIBOOSTING 算法[19]对转化后的问题进行求解.MIMLSVM 算法则是以多标记为桥梁,首先利用聚类将多示例多标记转化为多标记学习问题,再借助于多标记学习的算法进行求解.MIMLBOOST 算法和MIMLSVM 算法都是使用的退化方法,因此均有信息丢失.D-MIMLSVM 算法假设类别标记集合Y中共含有T个类别标记,同时假设分类系统由T个函数f=(f1,f2,···,fT)构成,每一个函数都是由示例空间到实值空间的映射,即ft:2X→R,t=1,2,···,T,也就是为每一个标记建立一个分类器.该算法在训练集上定义了一个损失函数V,使用了某种定义在包上的多示例核函数[20],最后通过优化V,利用CCCP[21,22]的迭代优化策略对其求解.M3MIML 算法假设分类系统包含T个线性模型,每个线性模型对应于一个可能的概念类,一个测试样本是否属于第i类是由其包含的所有示例在上述对应的某个线性模型上的最大输出决定的.M3MIML 基于最大化间隔策略,将二次规划问题分解为一系列相对简单的线性规划问题求解,最后利用KKT 条件[23]求解对偶问题获得模型参数.

以前的大多数研究集中在全局标签相关性上,但是,有时标签关联只能由局部数据子集所共享.为了缓解这个问题,使用局部相关性的多标签学习(MLLOC)[24]通过嵌入代码来扩展每个实例的特征表示,所述代码编码实例标签对局部标签相关性的影响.MLLOC 在利用局部相关性方面取得了成功.但是像摘要所提到的那样,有时局部和全局同样重要,而MLLOC 仅仅可以处理局部标签并且无法处理缺失标签的情况.为了进一步解决这个问题,提出了本文的算法.

2 MIMLSVM 算法及改进算法

2.1 MIMLSVM 算法

MIMLSVM 算法是以多标记学习为桥梁,将多示例多标记学习问题退化为传统监督学习问题求解.首先,MIMLSVM 算法将每个多示例多标记样本(Xi,Yi)转化为一个单示例多标记样本 (φ(Xi),Yi).其中,函数φ是基于构造性聚类[25]将每个示例包Xi转化为一个示例Zi.该聚类过程将集合Λ ={X1,···,Xm}中的每个包看作一个原子对象,基于Hausdorff 距离度量包之间的距离并利用k-medoids 算法将集合 Λ划分为若干个聚类.此时Zi的每一维即为包Xi与各聚类中心的距离,这样,多示例多标记样本集就转换成了单示例多标记样本集,此过程完成后,MIMLSVM 算法利用MLSVM 算法[26]对转换得到的多标记学习问题进行求解.MLSVM算法将多标签学习问题分解为多个独立的二元分类问题,从而为每一个类别标记建立一个SVM 分类器,事实上,示例zi参 与了每一个分类器的构建,示例Zi对应的 标 签 集 合Yi包 含y时,即y∈Yi时φ (Zi,y)=+1,否 则φ(Zi,y)=-1.至此,已经将多标记学习转化为了传统的监督学习,可以使用SVM 进行训练分类了.对于未见标记的示例包,利用构造性聚类转化为单个的示例,然后交给训练出来的|y|个分类器,每个分类器在该示例上会有不同输出,用输出为正的分类器对应的类别来标记该示例即可.但是注意到,如果未见标记的示例在每个分类器上的输出都为负值,那该示例将会变得不可分,即没有类别标记与之对应.为了避免这种情况的出现,这里采用T-Criterion 准则[27]来进行预测,即当所有分类器的输出均是负值时,用输出值“最大”的分类器对应的类别来标记该示例.

但是在退化过程中存在一个明显的问题,那就是为每一个类别标记建立分类器的时候,忽略了标记之间的相关性.前文也提到过,针对此也提出了一些改进算法,比较有效的是MLLOC 算法,虽然此算法有一定效果,但是仅仅只是从局部标签相关性角度出发,忽略了全局相关性.这里使用多标记学习中的一种既考虑局部相关性又考虑全局相关性并且可以处理缺失标签的算法GLOCAL[28]对MIMLSVM 算法进行改进.

2.2 MIMLSVM 算法的改进算法

GLOCAL 算法[28]是Yue Zh、Kwok JT 和Zhou ZH 在研究多标记学习时提出的一种全新的多标记算法,通过学习潜在标签表示和优化标签流形,同时处理全标签和缺失标签情况,并且同时利用全局和局部标签相关性.GLOCAL 算法之所以能够取得成功,主要归咎于以下四点：(1)它使用标签矩阵的低秩结构来获得更紧凑和更抽象的潜在标签表示,这也为丢失标签恢复提供了自然的解决方案(2.2.1 中介绍)；(2)它利用全局和局部标签相关性,因此标签分类器可以利用来自所有标签的信息2.2.2 中介绍)；(3)它直接从数据中学习标签相关性,而不需要通过在关联矩阵中进行普通且困难的人工分辨(2.2.3 中介绍)；(4)将上述问题综合为一个联合学习问题,采用高效交替最优化策略进行优化(2.2.4 中介绍).

2.2.1 基本模型

基本GLOCAL 模型对标签矩阵应用低秩分解以获得潜在标签,并学习从特征空间到潜在标签的映射.因此,我们可以得到一个更紧凑和更抽象的潜在标签表示,它是密集的,实值的,并且是低维的.学习从特征空间到潜在标签空间的映射也比学习原始标签空间(稀疏,二进制值和更高维)更容易.此外,它直接提供缺少标签恢复的解决方案.

具体来说,我们使用：

为了将示例映射到潜在标签,我们学习了一个矩阵W ∈Rd×k,这个W 可以通过最小化平方损耗获得,其中 X=[x1,···,xn]∈Rd×n是包含所有示例的矩阵.随后,针对示例 x 所预测的标签是 s ign(f(x)),其中f(x)=UWTx.让其中 fj(x)是 x 的 第j 个预测标签,可以将所有 x ∈X 的 f(x)连接在一起成为结合低秩矩阵分解的重构误差最小化和从示例到潜在标签的线性映射的平方损失最小化,我们得到了基本GLOCAL 模型的以下优化问题：

其中,R (U,V,W)是 正则化参数,λ1,λ2是平衡参数,尽管问题(2)使用了平方损失,但它可以被任何可微分损失函数代替.

2.2.2 利用全局和局部相关性

利用标签相关性对多标签学习至关重要,在这里,我们使用标签相关性来规范模型.需要注意的是全局和局部相关性可以共存,本节,引入标签流形正则化项来兼顾考虑二者.全局流形正则化项的基本思想是从实例级流形正则化项[29]中改进而来.具体而言,两个标签越正相关,相应分类器输出越接近,反之亦然.

回想一下,对n 个示例的预测都存储在l ×n 的矩阵F0中,其第i 行 fi,:包含第i 个标签的预测.如果第i 个和第j 个标签更具正相关性,则 fi,:应 该更加相似于 fj,:,反之亦然.类似于实例级流形正则化项[29,30],标签流形正则项被定义为：

其中,S0是l ×l 的全局标签相关矩阵.如果标签i 和j是正相关的,那么 [ S0]i,j也是正数.通过最小化式(3),将变小.令 D0为 对角线S01的对角矩阵,其中1 是1 的向量表示.在式(3)中,流行正则化项可以等价写成t r(F0TL0F0)[31],其中L0=D0-S0是 S0的 l ×l 标签拉普拉斯矩阵.

由于局部之间的标签相关性可能不同,因此我们引入局部流形正则化式.假设数据集X 被分为g 个组其 中Xm∈Rd×nm具 有nm个 示 例.令Ym为Y 对应于 Xm的标签子矩阵,Sm∈Rl×l为组m 的局部标签相关矩阵,与全局标签相关性相似,我们支持分类器输出正(负)相关标签上相似(或不相似),并最小t r(FmTLmFm),其中 Lm是Sm的拉普拉斯矩阵,Fm=UWTXm是组m 的分类器输出矩阵.对于问题(2)加入全局和局部标签流形正则化式后,得到以下优化后的：

其中,λ1,λ2,λ3,λ4是平衡参数.

标签流形正则化之所以能兼顾二者或者说促进作用是因为全局标签相关性用拉普拉斯矩阵 L0编码,局部标签相关性用 Lm编码,直观来说,一个大的局部组对全局标签相关性的∑贡献更大,特别的,当使用余弦相似度计算 Sij时 ,通常,当全局标签相关矩阵是局部标签相关矩阵的线性组合时,相应的全局标签拉普拉斯矩阵也是具有相同组合系数的局部标签拉普拉斯矩阵的线性组合.综上所述,问题(4)可以被重写为：

2.2.3 学习标签相关性

标签流形正则化成功是取决于好的标签相关矩阵(或等价于一个好的拉普拉斯矩阵),在多标签学习中,一种基本的方法是用余弦距离计算两个标签之间的相关系数[32].但是,由于某些标签在训练数据中可能只有极少数正示例,因此估计值可能会很嘈杂.当标签可能丢失时,这个估计值甚至会引起很大的误差,因为观察到的标签分布可能与真实的标签分布有很大不同.在本算法中,没有直接指定任何相关度量或标签相关矩阵,而是直接学习拉普拉斯矩阵,这样省去了在关联矩阵中进行普通且困难的人工分辨.需要注意的是,拉普拉斯矩阵是对称正定的,因此,对于m∈{1,···,g},我们将Lm分 解为ZmZmT,其中Zm∈Rl×k.为了简单起见,将k设置为潜在表示V的维度.因此,学习拉普拉斯矩阵转换为学习注意,优化关于Zm可能会导致平凡解Zm=0.为了避免这种情况,我们添加约束条件,即每个对角线元素ZmZmT为1,这也使我们能够获得Lm的归一化拉普拉斯矩阵[33].

2.2.4 通过交替最小化进行优化学习

问题(6)可以通过交替最小化来解决.这使得我们能够迭代的调整变量以找到满意的解决方案.在每次迭代中,我们用梯度下降来更新 {Z,U,V,W}中的一个变量,并固定其他变量.整个优化问题进而简化为几个简单的子问题.具体来说,MANOPT 工具箱[34]被用来在欧几里得空间上用线搜索实现梯度下降以更新U,V,W以及更新Z的流形,详细更新过程将在下面讨论.

2.2.4.1 更新Zm

随着U,V,W的被固定,式(6)变为

由于约束diag(ZmZmT)=1,它没有闭式解,我们用投影的梯度下降来解决它,关于Zm的梯度为为了满足约束条件diag(ZmZmT)=1,每次更新后我们将Zm的每一行投影到单位标准球上：

2.2.4.2 更新V

随着Zm,U,W的被固定,式(6)变为：

注意,V的列彼此独立,因此可以逐列得到V.设ji和vi分别为j和v的第i列,vi的优化问题可以写为：

设置梯度关于vi到0,我们得到以下vi闭式解：vi=(UTdiag(ji)U+(λ+λ2)I)-1(λWTxi+UTdiag(ji)yi).这里涉及为每个i计算逆矩阵,如果计算代价很大,我们可以在式(8)上执行梯度下降,在式(8)上,关于V的梯度下降为：∇v=UT(J°(UV-Y))+λ(V-WTX)+λ2V.

2.2.4.3 更新U

随着Zm,V,W的被固定,式(6)变为：

我们再一次利用梯度下降,关于U的梯度为：

2.2.4.4 更新W

随着Zm,U,V的被固定,式(6)变为：

关于W的梯度为：

MIMLSVM 算法是针对多示例多标记框架设计的算法,在基于构造性聚类将每一个包转化为一个示例之后就变成了单示例多标记问题,GLOCAL 算法针对的是单示例多标签的分类问题,因此可以使用GLOCAL算法对原来的MIMLSVM 算法进行改进,替代原来的MLSVM 算法得到MIMLSVM-GLOCAL 算法,像前文提到的那样,GLOCAL 算法并没有仅仅从局部或者全局一方面出发,而是两者都考虑在内去解决相关问题,并且也可以在标签缺失的情况下去解决问题.MIMLSVMGLOCAL 的算法描述如表1所示.

表1 MIMLSVM-GLOCAL 算法

3 实验

为了检验MIMLSVM-GLOCAL 算法的分类效果,将MIMLSVM-GLOCAL 算法和其他的多示例多标记算法MIMLBOOST、MIMLSVM、MIMLSVM+进行了比较.MIMLBOOST 算法以多示例为桥梁,首先将多示例多标签样本转化为多示例单标签样本,然后使用多示例学习中的MIBOOSTING 算法对转化后的问题进行求解.MIMLSVM 算法则是以多标签为桥梁,首先利用聚类将多示例多标签问题转化为多标签问题,再借助于多标签学习中的MLSVM 算法进行求解.MIMLSVM+算法利用退化策略,将多示例转化成单示例,再把多标签分解成一系列的两类分类问题.实验中使用的SVM均使用高斯核函数,MIMLBOOST、MIMLSVM 算法中的参数根据文献[3]中的实验设置为最优,MIMLSVM+算法中的参数根据文献[1]中的实验设置为最优,GLOCAL算法根据文献[28]中的实验设置为最优.

这里我们使用周志华等人提供的图像样本集[3]和文本样本集[19]进行实验.实验中的算法均使用相同的样本集和测试集,均采用10 折交叉验证.其中图像样本集由2000 个自然场景图片构成,分为5 个类别,分别是沙漠、山、海、日落和树.属于一个以上的类(如山+日落)的样本的数目约占数据集的22%左右,许多组合类(如山+海+树)约占0.75%左右,单个标签的样本数目约约占77%左右.平均来说,每个样本都与大约1.24 个类标签相关联,如表2所示.

表2 场景样本集数据特征

每张图片通过SBN 方法用包含9 个示例、每个示例为15 维的特征向量的示例包来表示.文本数据集来自Reuters 数据集,此样本集被广泛利用,包含7 个类别的2000 个文本样本,这2000 个样本是由去除没有标记和没有正文的文本,再随机去除一些只有一个类别标记的文本后得到的.具有多个标记的文本样本约占15%,平均每个文本样本具有1.15±0.37 个类别标记.通过使用滑动窗口[27]技术将每一篇文档用一个包来表示,每个包中包含一组数量不等的特征向量,每个特征向量都是243 维的并且代表了这篇文档的某个部分.本实验采用10 折交叉验证的方式,每次从2000 个数据集中随机的抽取1500 个数据作为训练集,其余的500 个数据作为测试集,重复10 次实验之后求得实验的平均值以及方差.本实验中使用的场景样本集和文本样本集,其结构特征如表3所示.

对于评级指标,我们采用采用基本样本的也是广泛使用的hamming loss、one-error、coverage、ranking loss 和average precision[1]来衡量学习效果.简单来说,对于hamming loss、one-error、coverage 和ranking loss的值越小说明算法效果越好；对于average precision的值越大说明算法效果越好.表4和表5分别显示了MIMLBOOST、MIMLSVM、MIMLSVM+和MIMLSVMGLOCAL 算法在场景样本集和文本样本集上的分类效果.

从表4和表5的实验结果可以看出,无论在场景样本集还是文本样本集,MIMLSVM-GLOCAL 算法的性能都要高于其他算法,取得了良好的性能,这主要得益于文章2.2 节所论述的优势,此外,全局标签流形提供有关标签如何作为一个整体相关的信息,并帮助学习少数标签,如果少数标签与其他标签正相关(相反,负相关),我们可以鼓励其标签分类器输出与其他标签

的输出更相似(相反).局部标签流形还允许标签分类器的局部适应.拉普拉斯矩阵的学习发现了最适合全局和局部数据子集的标签相关性,并避免了手动指定标签相关性的常见任务和困难任务.从总体上看,MIMLSVM、MIMLBOOST、MIMLSVM+和MIMLSVM-GLOCAL 在文本样本集上分类的各项指标明显优于场景样本集,这可能与样本集内部的结构有一定的关系,文本样本集示例的维数远远多于场景样本集,文本样本集可以更加准确的来表示对象,因此造成了两个样本集上的结果差异较大.

表3 文本样本集和场景样本集特征

表4 场景样本集实验结果

表5 文本样本集实验结果

4 结束语

多示例多标记框架下的MIMLSVM 算法已经取得了不错的分类效果,针对其第二步中由于忽略标签相关性而导致信息丢失的问题在之前也提出了一些解决方案,但都考虑的不周全,与以前的工作相比,本文将一种既考虑到全局又考虑到局部标签相关性的GLOCAL 算法融入到了MIMLSVM 算法中,整体提升了算法的性能,提高了分类准确率,取得了良好的实验效果.