南京大学学报(自然科学), 2020, 56(4): 549-560 doi: 10.13232/j.cnki.jnju.2020.04.013

一种基于嵌入式的弱标记分类算法

李亚重1, 杨有龙,1, 仇海全1,2

1.西安电子科技大学数学与统计学院,西安,710126

2.安徽科技学院信息与网络工程学院,蚌埠,233030

Label embedding for weak label classification

Li Yachong1, Yang Youlong,1, Qiu Haiquan1,2

1.School of Mathematics and Statistics,Xidian University,Xi'an, 710126,China

2.College of Information & Network Engineering,Anhui Science and Technology University,Bengbu,233030,China

通讯作者: E⁃mail:ylyang@mail.xidian.edu.cn

收稿日期: 2020-03-03   网络出版日期: 2020-08-05

基金资助: 国家自然科学基金.  61573266
安徽省高校自然科学研究重点项目.  KJ2019A0816

Received: 2020-03-03   Online: 2020-08-05

摘要

对于高维标签的分类问题,标签嵌入法已经受到广泛关注.现有的嵌入方法大都需要完整的标签信息,也没有将特征空间考虑在内;同时,由于数据进行人工标注的成本高以及噪声干扰等原因,仅能获得数据的部分标签信息,使得含有缺失标签的高维标签分类问题变得更加复杂.为解决这一问题,提出一种弱标记嵌入算法(Label Embedding for Weak Label Classification,LEWL).该算法利用矩阵的低秩分解模型,结合样本的流形结构恢复缺失标签;同时采用希尔伯特⁃施密特独立标准技术(Hilbert⁃Schmidt Independence Criterion,HSIC)使特征和标签相互作用,联合学习获得一个低维的嵌入空间,可以有效地减少模型的训练时间.通过在七个多标签数据集上与其他算法的对比实验,结果表明了所提算法的有效性.

关键词: 弱标记学习 ; 标签嵌入 ; 低秩分解 ; 希尔伯特⁃施密特独立标准 ; 缺失标签

Abstract

For the classification of high⁃dimensional labels,label embedding has attracted extensive attention of researchers in recent years. Current embedding methods require complete label information and do not take feature information into consideration. Meanwhile,due to the high cost of manual labeling and interference of noise,only part of the label information can be obtained. This makes the classification problem of high⁃dimensional labels with missing labels more complicated. To end this,a Label Embedding method for Weak Label Classification (LEWL) is proposed in this paper. The algorithm uses the low⁃rank factorization model on the label matrix and the flow pattern structure of the samples to recover the missing labels. In the meantime,the HSIC (Hilbert⁃Schmidt Independence Criterion) technique is adopted to obtain the low dimensional embedding space by making feature and labels interact with each other for joint learning,which can effectively reduce the training time of the model. Compared with other methods on seven data sets,comprehensive experimental results validate the effectiveness of proposed approach.

Keywords: weak label classification ; label embedding ; the low⁃rank factorization on the matrix ; HSIC(Hilbert⁃Schmidt Independence Criterion) ; missing labels

PDF (1124KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

李亚重, 杨有龙, 仇海全. 一种基于嵌入式的弱标记分类算法. 南京大学学报(自然科学)[J], 2020, 56(4): 549-560 doi:10.13232/j.cnki.jnju.2020.04.013

Li Yachong, Yang Youlong, Qiu Haiquan. Label embedding for weak label classification. Journal of nanjing University[J], 2020, 56(4): 549-560 doi:10.13232/j.cnki.jnju.2020.04.013

多标签分类中一个实例常常同时拥有多个标签,目前已经在文本分类[1]、图像注解[2]、基因功能分类[3]等方面得到广泛应用.现有的多标签分类算法可分两类:一类是问题转换法(Problem Transformation,PT),基本思想是把多标签分类任务转换成多个单标签分类任务,如:BR (Binary Relevance)[4]算法、LP (Label Powerset)[5]算法、CC (Classifier Chain)[6]算法等.另一类是算法转换法(AA,Algorithm Adaptation),即对现有的单标签分类算法进行改进使其能够处理多标签数据.代表算法有:ML⁃KNN[7],Adaboost.MH[8]等.随着数据采集和存储技术的发展[9],标签数量呈指数型爆炸式增长,传统的多标签分类算法需要较大的时间成本,也面临着标签维数过高引起的“维数灾难”问题.同时,多标签学习的输出是多个类别标签,且标签之间存在相关性,增加了模型学习的难度.为了缓解这个问题,研究人员开始研究标记空间维度下降法(Label Space Dimension Reduction,LSDR),利用标签之间的关系来降低标签空间的维度,希望在提升分类精度的同时能有效减少整个模型的训练和预测时间.

标记空间维度下降法是针对高维标签向量提出的一种嵌入技术,把初始的标签空间转化成低维的嵌入空间,在低维嵌入空间中实现对向量更有效的表示[10].对于一个测试数据来说,学习器将其映射到低维嵌入空间,再通过解码器将其恢复到原始的二值空间,最终希望预测到的仍是原始标签空间下的标签向量.Hsu et al[11]认为标签空间具有输出稀疏性,标签向量存在小支撑,首次提出基于压缩感知的多标签预测方法(Multi⁃Label Prediction via Compressed Sensing,ML⁃CS),即利用压缩感知理论对标签空间进行压缩.该方法采用随机生成的压缩函数,不能有效利用标签之间的关系来实现更好的压缩效果.Tai and Lin[12]提出PLST (Principal Label Space Transformation),通过对标签矩阵进行奇异值分解来降维.Chen and Lin[13]在PLST基础上提出CPLST (Conditional PLST)方法,在标签重构过程中引入相关特征信息,进一步提高模型对未知数据预测的准确率.最近基于典型相关分析(Canonical Correlation Analysis,CCA)理论,Lin et al[14]提出E2FE(End⁃to⁃End Feature⁃aware Label Space Encoding),该方法无需对编码方式进行任何假设,避免了不合理假设造成的风险.由于对数据进行人工标注的成本太高、用户更新频率大及噪声干扰等其它原因[15],获取训练数据的全部标签显得非常困难.在这种情况下产生了弱标记数据,即实例中含有未被标记或标记错误的标签.本文主要讨论前一种情况,即数据只有部分标签信息可以获得.Sun et al[16]最早将弱标签问题引入多标签学习,并提出WELL (WEak Leak Learning),让每个标签的分类边界跨越低密度区域,并考虑了类不平衡问题.MLML (Multi⁃label Learning with Missing Labels)[17]算法首次明确区分负类标签和缺失标签,即正类、负类和缺失标签分别用

+1,-1和0表示,该算法基于标签一致性和标签平滑性求出恢复后的完整标签.LRML (Low Rank Multi⁃label Classification with Missing Labels)[18]算法利用标签一致性(label consistency)和局部不变性(local invariance)假设得到完整的标签矩阵,同时又从特征空间到恢复后的标签空间学习线性函数矩阵,并假设其是低秩的.Han et al[19]提出ColEmbed (Collaborative Embedding),利用非线性嵌入将特征和标签嵌入到一个共享子空间,同时解决了特征不完整和标签缺失问题.综上,解决高维且含有缺失标签的多标签学习问题十分必要.

为了解决上述问题,本文提出一种基于嵌入式的弱标记算法LEWL (Label Embedding for Weak Label Classification).一方面通过对标签矩阵进行低秩分解来最小化嵌入空间返回原始标签空间的恢复误差.为了提高对嵌入空间的可预测性,采用希尔伯特⁃施密特独立标准技术(Hilbert⁃Schmidt Independence Criterion,HSIC)使得特征空间和嵌入空间的依赖关系更加紧密,这样获得的实值低维嵌入空间把标签信息和特征信息同时考虑在内,标签和特征的嵌入过程是紧密相关同时进行的.另一方面,由于矩阵的低秩分解对矩阵补全问题(标签恢复)起着重要作用,再利用样本流形结构对缺失标签进行填补.最后将以上模型整合成一个优化问题,并提出了一个有效的求解方法.实验结果表明,针对不同的数据集,本文提出的算法均具有较好的分类性能和泛化能力.

1 一种基于嵌入式的弱标记算法

1.1 定 义

X=x1,,xnTRn×m是由n个训练样本组成的数据矩阵,Y=y1,,ynT

Rn×c是原始标签矩阵,c为类别个数,其中yi0,

0.5,1c是第i个样本xi对应的标签.1,0,0.5分别表示正类、负类和缺失标签.若示例xi含有第j个标签,则Yi,j=1;若示例xi没有第j个标签,则Yi,j=0Yij=0.5表示该示例缺失该标签.

1.2 标签嵌入模型

由于不同标签之间存在相关性,故可以把整个标签矩阵看成是低秩的[20-21](即它的秩小于它的行数或列数).例如,当标签“蓝天”和“白云”同时出现的时候,很有可能会出现标签“晴天”.对于一个矩阵来说,根据其部分元素来推断其所有元素也非常困难.Candès and Tao[22]证明在矩阵低秩的情况下,大多数矩阵可以通过求解核范数最小化问题来恢复元素.为降低求解的计算复杂度,Wen et al[23]提出一种基于矩阵分解的低秩拟合算法,目的是寻找两个或多个矩阵,其乘积对原始矩阵具有良好的逼近能力,即尽可能地减小分解矩阵乘积与原始矩阵之间的近似误差.利用这一思想,可以将原始标签矩阵YRn×c分解成两个规模更小的矩阵的乘积:

Y=Z×D

其中,ZRn×d表示低维嵌入空间,集成了原始标签空间的整体信息,DRd×c是基矩阵.

假设初始的标签矩阵表示为Y=y1,,

ynT0,0.5,1n×c,真实的标签矩阵为Y˜,定义Ω1,,n×1,,c为观察到的Y中的元素的位置集合(非0.5所对应的下标),Ωc为缺失元素的位置集合.通过最小化嵌入空间返回原始标签空间的恢复误差,提出下列低秩分解模型:

minY˜,Z,DY˜-ZDF2s.t. Y˜i,j=Yi,j, (i,j)Ω

从全局方面考虑了标签关系后,进一步从局部来考虑.样本平滑性假设:当两个样本xixj距离很近时,对应的标签y˜iy˜j也是相似的.一般可以用正则化形式来呈现:

i,jn12ωi,jy˜i-y˜j2=tr(Y˜TLY˜)

其中L=P-W是拉普拉斯矩阵,PPii=j=1nωij

为对角矩阵,W表示样本相似性矩阵,如式(4)所示:

ωi,j=exp-xi-xj2t                         xiNk(xj) or xjNk(xi)0                                    otherwise

于是得到下列缺失标签恢复模型:

minY˜,Z,DY˜-ZDF2+tr(Y˜TLY˜)s.t. Y˜i,j=Yi,j, (i,j)Ω

这个模型能够通过恢复原始标签矩阵Y中的缺失元素来得到真实的标签矩阵Y˜.而且求得的真实标签除了缺失标签之外,剩下的标签保持不变,可以避免把正确的标签恢复错误.

1.3 特征嵌入模型

理论研究表明[24],强相关性往往意味着强可预测性.为了在标签空间压缩过程中更有效地使用特征信息,同时提高嵌入空间的可预测性(学习器在学习阶段学习相应的映射),本文认为应该尽量使嵌入空间与特征空间的依赖相关性最大化.

衡量依赖性的指标有很多,Gretton et al[25]于2005年提出希尔伯特⁃施密特独立标准(HSIC),该标准衡量的是两组变量在再生核希尔伯特空间(Reproducing Kernel Hilbert Spaces)中映射之间协方差算子的平方希尔伯特⁃施密特范数.由于其具有简洁的数学形式和优雅的理论性质,目前已经在很多领域被用来衡量变量之间的依赖性.

假定和G分别表示两组变量XY的再生核希尔伯特空间,给定数据集Z=(x1,y1),,

(xn,yn)X×Y,则HSIC的一个经验型估计是:

HSIC(Z,,G)=(n-1)-2tr(KHLH)

其中,Hn×n=I-1neet是中心矩阵,en×1是一个全1向量,In×n是一个单位矩阵.KRn×nLRn×n分别是特征核函数Ki,j=k(xi,xj)和标签核函数Li,j=l(xi,xj),显然值越大说明两个变量的依赖性越强.

为了方便起见,对于L本文考虑线性核L=ZZT.由于(n-1)-2是常数项,式(6)等同于maxZtr(KHZZTH)=maxZtr(ZTHKHZ).获得特征核矩阵K最有效的方法是利用高斯核函数进行计算[26],具体定义为:

K(x,x')=exp-αx-x'2

其中,α>0是核参数.

结合标签嵌入和特征嵌入模型得到最终的弱标记优化模型:

minY˜,Z,DY˜-ZDF2+βtr(Y˜TLY˜)-λtr(KHZZTH)s.t. Y˜i,j=Yi,j,(i,j)Ω                                      (7)

为了便于求解,定义PΩ(X)为矩阵X在集合Ω上的正交投影算子:

PΩ(X)i,j=Xi,j    (i,j)Ω0        (i,j)Ωc

优化模型可被写成:

minY˜,Z,DY˜-ZDF2+βtr(Y˜TLY˜)-λtr(KHZZTH)s.t. PΩ(Y˜)=PΩ(Y)                                                   (9)

目标函数的前两项通过低秩分解和样本的流形结构来恢复缺失标签,第一项和第三项采用标签和特征相互作用联合学习获得了低维嵌入空间和解码矩阵.因此,本文提出的优化模型不仅解决了弱标记问题,还有效地缓解了高维标签带来的影响,同时充分利用了标签之间的关系,提高了模型的分类精度.

2 模型的求解

为了更准确有效地求解目标函数,本文提出一种交替迭代的优化求解算法.即将优化问题划分为几个子问题进行交替迭代更新,直至收敛到问题的稳定点或局部极值点.

(1)更新矩阵D:当固定矩阵ZY˜时,D为唯一的变量,求解问题(9)可以转化为式(10):

L(D)=minDY˜-ZDF2

式(10)对D求导,并令其等于0:

L(D)D=ZT(ZD-Y˜)=0

可得到关于D的闭式解:

D=ZTZ)-1ZTY˜

为了消除嵌入空间中噪声和冗余信息的影响,同时使得解码过程更加方便,本文假设Z是列向量正交矩阵,即ZTZ=I.因此式(11)被重写为式(12):

D=ZTY˜

(2)更新矩阵Z:类似的,当固定DY˜时,目标函数(式(9))可写成:

L(Z)=minZY˜-ZDF2-λtr(KHZZTH)=maxZtr(ZTY˜Y˜TZ)+tr(ZTHKHZ)=maxZtrZT(Y˜Y˜T+HKH)Zs.t. ZTZ=I(13)

通过特征值分解[13,27],优化问题(式(13))能容易地被求解,最后得出Z是由A=YYT+λ(HKH)的前k个最大的特征值对应的特征向量组成.

(3)更新矩阵Y˜:固定ZD,从式(9)中可以得到关于Y˜的优化模型:

L(Y˜)=minY˜Y˜-ZDF2+βtr(Y˜TLY˜)s.t. PΩ(Y˜)=PΩ(Y)                                (14)

为了求解式(14),需要引入拉格朗日乘子ΛRn×c,其拉格朗日函数为:

L(Y˜,Λ)=Y˜-ZDF2+βtr(Y˜TLY˜)+ΛPΩ(Y˜-Y)

要得到Y˜的最优解,需先确定PΩ(Y˜)PΩc(Y˜)分别对应的两个子问题.其中,PΩ(Y˜)对应的子问题为:

L(Y˜,Λ)=PΩ(Y˜-ZD)F2+βtrPΩ(Y˜TLY˜)+ΛPΩ(Y˜-Y)                                                          (16)

Karush⁃Kuhn⁃Tucker (KKT)条件需要如下式子成立:

LΛ=PΩ(Y˜-Y)=0
LY˜=PΩ(Y˜-ZD)+βLY˜=Λ

另外,PΩc(Y˜)对应的子问题为:

L(Y˜)=PΩc(Y˜-ZD)F2+βtrPΩc(Y˜TLY˜)

类似的,它的KKT条件为:

LY˜=PΩc(Y˜-ZD)+βLY˜=0

根据式(17)和式(20),得到Y˜的解:

PΩ(Y˜)=PΩ(Y)PΩc(Y˜)=PΩc(I+βL)-1ZD

综上所述可以求得关于D,Z,Y˜的闭式解,其算法伪代码如下.

算法:LEWL算法

输入:数据矩阵X,原始标签矩阵Y,嵌入维数K,参数λβ,精度ε=10-6,最大迭代次数NMAX=2000

输出:补全的标签矩阵Y˜,测试数据xi的可预测标签集.

1.初始化:令Y˜=Y

2. While不收敛do

3. 固定Y˜并根据式(13)更新Z

4. 固定Y˜,Z并根据式(12)更新D

5. 固定Z,D并根据式(21)更新Y˜

6. 判断收敛条件:直至目标函数收敛(函数值不

再变化或变化小于一定精度)或达到最大迭代

次数NMAX

7. end while;

8.基于(xi,zi)i=1n训练得到回归模型f(x)

9.给定一个新的测试样例xi,预测其标签集合:

h(xi)=roundf(xi)D.

首先,从特征空间X到嵌入空间Z学习一个回归模型.由于Z维度较低,在训练过程中极大地降低了计算复杂度,提高了学习效率.其次,通过解码函数D将其解码到初始标签空间中.在整个过程中无须考虑编码形式.在步骤9中对测试数据预测时,结果可能包含非二值情况,这时需要选取一个阈值来进行决定属于哪一个类.Tai and Lin[12]证明固定值0.5是一个简单有效的方法.为了提升分类性能,本文采用类似文献[28-29]中提出的一种自适应阈值法.具体的,用步骤9对训练数据进行预测得到预测矩阵,将其预测值按降序(或升序)方式排列成一个一维向量,通过最大化(最小化)训练数据的评分标准来找到最好的分割点,如果超过这个阈值则为1,否则为0.

3 实 验

3.1 数据集

为了验证所提算法LEWL的有效性,从不同领域选取了七个公开的多标签数据集,具体信息如表1所示,其中标签基数(Label cardinality)表示每个样本的平均标签数.

表1   数据集基本信息

Table 1  The characteristics of the datasets

数据集样本特征标签领域标签基数
Emotions593726music1.869
Yeast241710314biology4.237
CAL50050268174music26.044
Medical978144945text1.245
Langlog1460100475images1.18
Enron1702100153text3.378
Corel5k5000499374images3.522

新窗口打开| 下载CSV


3.2 评价指标

在多标签分类中由于每个样本同时归属多个标签,因此传统的单标签分类评价指标已不再适用.本文采用以下三个常见的多标签分类指标[30]评价算法的性能.对于一个给定的数据集D=(xi,yi)1in,其中yi0,1c表示第i个样本的真实标记向量.

(1)排序损失(Rank Loss):用于衡量样本类别标签排序中出现排序错误的程度,如式(22)所示:

Rloss=1ni=1nQiyi+yi-

其中,

Qi=(y',y)f(xi,y')f(xi,y),(y',y)yi+×yi-

yi+yi-分别表示yi中正类和负类标签的数目.Rank Loss值越小表明预测函数f的性能越好.

(2)平均精度(Average Precision):用于衡量整体样本标签预测的平均精确度,如式(23)所示:

Ap=1ni=1n1yi+yyi+y'rankf(xi,y')rankf(xi,y),y'yi+rankf(xi,y)

Average Precision值越大表明预测函数f的性能越好.

(3)Macro F1:是查准率(Precision)和召回率(Recall)的调和平均值,如式(24)所示:

Macro F1=1ci=1c2piripi+ris.t. pi=TPTP+FP,ri=TPTP+FN

其中,TP表示真正例的个数,即正类被预测为正类的数量;FP表示假正例的个数,即负类被预测为正类的数量;FN表示假负例的个数,即正类被预测为负类的数量.Macro F1越大,表明算法的性能越好.

以上评价指标的值都在0,1区间中,一个好的多标签分类算法应该具有较低的Rank Loss及较高的Average Precision和Macro F1.

3.3 实验设置

从标签数据中随机选取30%和70%的标签作为缺失标签,缺失标签用0.5表示.为验证所提算法的有效性,与BR (Binary Relevance)[4],CPLST (Conditional Principal Label Space Transformation)[12],MLML (Multi⁃label Learning with Missing Labels)[17]和LRML (Low Rank multi⁃label classification with Missing Labels)[18]四种算法进行了比较.由于缺失标签的存在,BR和CPLST不能直接进行分类和预测,为了方便起见它们采用最简单的填补方法,即把缺失标签看成负类标签来对待.

对于所有比对算法来说,利用随机森林从特征空间到嵌入空间学习训练模型.模型参数如树的最大深度和个数通过灰度搜索分别从5,10,…,35和2,4,…,40中选择.在本文的实验中,对每个数据集进行5折交叉验证,其中四份被用来训练,一份用来测试.算法MLML中的权衡参数λxλc、LRML中的αβγ以及所提算法LEWL中的λβ通过交叉验证来选择.

3.4 结果及分析

通过前文提到的评价指标对多标签分类算法进行多角度比较,表2表3表4分别是在排序损失、平均精度和Macro F1三个评价指标下对缺失标签的恢复情况,表5对它们的恢复结果进行了t检验,表6表7表8分别给出了在三个指标下对测试数据的预测结果.其中ρ表示标签缺失率,表中的粗体字表明其在配对检验中优于其他结果,或与最优结果之间无显著性差异.

表2   缺失标签在平均精度上的恢复结果

Table 2  Recovery results for missing labels on Average Precision

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.918±0.0080.920±0.00440.843±0.0110.886±0.0050.886±0.005
0.70.839±0.0110.846±0.0120.772±0.0130.781±0.0100.781±0.010
Yeast0.30.894±0.0030.891±0.0010.792±0.0100.869±0.0020.869±0.002
0.70.811±0.0040.805±0.0030.716±0.0110.738±0.0050.738±0.005
CAL5000.30.832±0.0060.791±0.0050.784±0.0140.816±0.0040.816±0.004
0.70.663±0.0060.633±0.0070.652±0.0100.623±0.0040.623±0.004
Medical0.30.790±0.0190.776±0.0290.772±0.0420.766±0.0210.766±0.021
0.70.602±0.0240.588±0.0290.531±0.0440.542±0.0090.542±0.009
Langlog0.30.860±0.0050.811±0.0020.852±0.0310.827±0.0020.827±0.002
0.70.709±0.0060.667±0.0030.704±0.0220.643±0.0060.643±0.006
Enron0.30.819±0.0070.823±0.0060.764±0.0510.795±0.0060.795±0.006
0.70.632±0.0200.667±0.0280.543±0.0580.585±0.0130.585±0.013
Corel5k0.30.749±0.0050.735±0.0060.742±0.0040.733±0.0020.733±0.002
0.70.515±0.0080.510±0.0110.513±0.0090.511±0.0040.511±0.004

新窗口打开| 下载CSV


表3   缺失标签在Macro F1上的恢复结果

Table 3  Recovery results for missing labels on Macro F1

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.882±0.0090.905±0.0060.857±0.0480.847±0.0130.847±0.013
0.70.775±0.0100.801±0.0090.814±0.0350.666±0.0110.666±0.011
Yeast0.30.883±0.0070.874±0.0060.805±0.0150.850±0.0030.85±0.003
0.70.749±0.0080.738±0.0070.717±0.0230.660±0.0020.66±0.002
CAL5000.30.845±0.0040.776±0.0050.755±0.0210.849±0.0080.849±0.008
0.70.667±0.0070.633±0.0070.643±0.0200.657±0.0120.657±0.012
Medical0.30.804±0.0530.783±0.0290.755±0.0050.796±0.0490.796±0.049
0.70.566±0.0420.593±0.0290.565±0.0060.557±0.0380.557±0.038
Langlog0.30.859±0.0020.856±0.0020.855±0.0410.85±0.0010.85±0.001
0.70.685±0.0030.683±0.0030.682±0.0660.663±0.0050.663±0.005
Enron0.30.845±0.0130.822±0.0060.754±0.0160.822±0.0150.822±0.015
0.70.633±0.0330.648±0.0280.63±0.0130.651±0.0140.651±0.014
Corel5k0.30.817±0.0120.785±0.0070.801±0.0250.813±0.0170.813±0.017
0.70.619±0.0110.605±0.0130.614±0.0210.612±0.0160.612±0.016

新窗口打开| 下载CSV


表4   缺失标签在排序损失上的恢复结果

Table 4  Recovery results for missing labels on Rank Loss

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.132±0.0100.133±0.0130.229±0.0170.262±0.01210.262±0.012
0.70.274±0.0050.271±0.0110.324±0.0160.498±0.0180.498±0.018
Yeast0.30.116±0.0030.138±0.0020.209±0.0080.261±0.0030.261±0.003
0.70.227±0.0040.258±0.0070.288±0.0070.502±0.0070.502±0.007
CAL5000.30.130±0.0010.239±0.0060.249±0.0110.259±0.00550.259±0.005
0.70.248±0.0010.394±0.0110.339±0.0090.503±0.0060.503±0.006
Medical0.30.107±0.0070.254±0.0110.155±0.0080.257±0.0220.257±0.022
0.70.148±0.0220.444±0.0120.205±0.0120.505±0.0110.505±0.011
Langlog0.30.170±0.0040.233±0.0040.204±0.0510.251±0.0020.251±0.002
0.70.332±0.0120.339±0.0070.342±0.0180.493±0.0070.493±0.007
Enron0.30.129±0.0080.191±0.0100.213±0.0430.257±0.0080.257±0.008
0.70.272±0.0290.363±0.0210.291±0.0430.513±0.0110.513±0.011
Corel5k0.30.108±0.0020.271±0.0080.178±0.0080.259±0.0030.259±0.003
0.70.403±0.0040.496±0.0140.356±0.0070.503±0.0040.503±0.004

新窗口打开| 下载CSV


表5   不同算法关于恢复结果的t检验

Table 5  t⁃test of different algorithms on recovery results

MLMLLRMLCPLSTBR
Average Precision0.04550.00040.00010.0001
Macro F10.22730.01790.02300.0230
Rank Loss0.00150.00080.00030.0003

新窗口打开| 下载CSV


表6   测试数据在平均精度上的预测结果

Table 6  Prediction results for test data on Average Precision

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.732±0.0260.716±0.019990.729±0.02220.662±0.0380.645±0.020
0.70.708±0.0120.687±0.0390.682±0.0160.558±0.0230.568±0.021
Yeast0.30.708±0.0060.654±0.0050.441±0.0240.587±0.0040.573±0.005
0.70.698±0.0050.648±0.0080.44±0.0260.448±0.0080.450±0.003
CAL5000.30.365±0.0170.31±0.0130.202±0.0110.248±0.0120.248±0.004
0.70.369±0.0130.307±0.0130.197±0.0090.170±0.0080.175±0.009
Medical0.30.805±0.0250.734±0.0090.775±0.0080.675±0.0490.289±0.029
0.70.718±0.0390.685±0.0180.721±0.0380.332±0.0300.112±0.011
Langlog0.30.543±0.0190.419±0.0160.410±0.0170.461±0.0480.469±0.019
0.70.530±0.0160.531±0.0190.399±0.0170.308±0.0290.309±0.011
Enron0.30.536±0.0410.395±0.0510.348±0.0070.331±0.0450.296±0.043
0.70.493±0.0540.346±0.0550.252±0.0110.213±0.0200.197±0.025
Corel5k0.30.038±0.0030.027±0.0080.027±0.0050.030±0.0070.027±0.007
0.70.022±0.0020.025±0.0070.026±0.0040.027±0.0070.023±0.007

新窗口打开| 下载CSV


表7   测试数据在Macro F1上的预测结果

Table 7  Prediction results for test data on Macro F1

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.606±0.0570.576±0.0510.616±0.0360.429±0.0690.389±0.021
0.70.596±0.0380.523±0.0610.610±0.0360.152±0.0330.160±0.041
Yeast0.30.461±0.0040.334±0.0110.367±0.0080.251±0.0090.234±0.009
0.70.452±0.0060.313±0.0080.366±0.0090.058±0.0090.062±0.004
CAL5000.30.234±0.0120.073±0.0070.212±0.0110.035±0.0050.046±0.003
0.70.232±0.0080.066±0.0080.205±0.0100.008±0.0020.015±0.002
Medical0.30.358±0.0320.311±0.0120.325±0.0020.310±0.0230.098±0.018
0.70.306±0.0200.258±0.0080.287±0.0190.171±0.0290.01±0.003
Langlog0.30.448±0.0180.164±0.0110.389±0.0280.171±0.0250.185±0.014
0.70.434±0.0170.232±0.0090.374±0.0290.048±0.0090.059±0.0120.
Enron0.30.166±0.0110.065±0.0130.120±0.0150.063±0.0090.042±0.008
0.70.149±0.0100.051±0.0140.101±0.0160.022±0.0040.013±0.011
Corel5k0.30.025±0.0010.018±0.0050.020±0.0030.010±0.0030.009±0.003
0.70.019±0.0010.015±0.0060.016±0.0030.007±0.0040.006±0.002

新窗口打开| 下载CSV


表8   测试数据在排序损失上的预测结果

Table 8  Prediction results for test data on Rank Loss

Data setρLEWLMLMLLRMLCPLSTBR
Emotions0.30.446±0.0240.509±0.0420.441±0.0190.692±0.0520.731±0.018
0.70.457±0.0300.561±0.0710.453±0.0160.924±0.0230.915±0.013
Yeast0.30.385±0.0080.484±0.0090.709±0.0070.652±0.0080.679±0.011
0.70.401±0.0110.496±0.0130.722±0.0050.940±0.0110.933±0.011
CAL5000.30.461±0.0110.577±0.0060.518±0.0120.890±0.0140.885±0.003
0.70.457±0.0110.584±0.0180.528±0.0080.972±0.0080.969±0.005
Medical0.30.139±0.0370.476±0.0140.302±0.0190.345±0.0500.785±0.027
0.70.168±0.0050.529±0.0160.347±0.0170.462±0.0400.977±0.006
Langlog0.30.468±0.0140.716±0.0170.629±0.0570.716±0.0530.689±0.025
0.70.487±0.0150.761±0.0210.625±0.0500.811±0.0310.887±0.019
Enron0.30.315±0.0380.500±0.0560.548±0.0080.792±0.0410.835±0.041
0.70.349±0.0380.569±0.0550.771±0.0190.948±0.0150.967±0.023
Corel5k0.30.538±0.0010.745±0.0020.697±0.0020.825±0.0010.889±0.001
0.70.549±0.0010.783±0.0040.721±0.0020.889±0.0040.903±0.002

新窗口打开| 下载CSV


从实验结果可以很明显地发现:缺失的标签越少,即观察到的标签越多,算法的恢复性能和预测性能越好,这也符合事实.无论是对缺失数据的恢复还是对未知数据的预测,LEWL在绝大多数情况下都能获得比其他对比算法更好的结果.这也说明LEWL使用策略的有效性,即在恢复缺失标签的同时又利用标签和标签以及特征和标签之间的关系学习到一个低维、实值的嵌入空间.

表2表4可以看到,这三个表只关注对缺失标签的恢复效果.LEWL,MLML和LRML分别用不同的方式来处理缺失标签,故在多个数据集上性能都优于BR和CPLST.这也从另一个侧面反映了处理缺失标签的必要性.本文建立的LEWL模型能够确保除了缺失标签外,其余可观察到的标签保持不变,这样就避免了在恢复的过程中误把正确的标签填补错误.

表5给出LEWL和和其余四种算法对缺失标签的恢复结果在不同标准上的t检验结果.取置信度为95%,α=0.05.可以看出四种算法在平均精度和排序损失上置信水平值均小于0.05,说明LEWL和其余四种算法在平均精度和排序损失上均存在显著性差异,也进一步证明LEWL算法对缺失标签具有一定的恢复作用.在Macro F1标准上,MLML的p值为0.2273,大于0.05,表明LEWL的恢复结果和MLML没有显著性差异.

表6表8可以看出,LEWL在常用分类性能评价指标上均有提升.首先,对于一个分类器来说,从一个密集的、低维实值的嵌入空间学习比从一个稀疏的、高维二值的空间学习更加准确高效.其次,对于不平衡数据集,例如Corel5k数据集有300多个标签,而每个样本仅仅只有不超过10个正类标签,所以传统的BR分类器难以获得好的分类结果.MLML算法聚焦于恢复缺失标签,不关注分类过程,因此它的预测结果比BR好,但比新提出的LEWL算法略差.LRML和CPLST算法都属于标签嵌入法,两者考虑的是标签和特征之间的线性关系,对比实验结果也表明了本文所提算法采用HSIC的有效性和合理性.但LEWL在Emotions数据集上的效果不是很好,一方面是由于这个数据集只有六个标签,在压缩的过程中可能会损失有用信息;另一方面可能是由于优化过程陷入了局部最优.

表9给出了不同算法在预测结果上的t检验结果.表中所有算法的p值均小于0.05,说明LEWL算法性能较好.

表9   不同算法关于预测结果的t检验

Table 9  t⁃test of different algorithms on prediction results

MLMLLRMLCPLSTBR
Average Precision0.00460.00540.00000.0007
Macro F10.00080.00070.00010.0000
Rank Loss0.00070.00160.00010.0000

新窗口打开| 下载CSV


为了分析LEWL的收敛性,本文刻画了Emotions和Yeast数据集的目标函数值随着迭代次数的变化曲线,如图1所示.结果表明,目标函数值在经过较少次迭代后就趋于稳定.总体来说,该算法具有收敛速度快、迭代次数少的特点.对于其它数据集也有类似结果.

图1

图1   LEWL在Emotions(上图)和Yeast(下图)数据集上的收敛性

Fig.1   Convergence of LEWL on Emotions(up) and Yeast(down) datasets


3.5 缺失标签的影响

为了探索缺失标签和嵌入维数的影响,在Emotions和Medical两个数据集上进行实验.如图2所示,ρ表示缺失标签率,在0.3到0.7之间变化;d表示嵌入空间维数.以Emotions数据集为例,当ρ从0.3变到0.7时,AP从0.732下降到0.708,降低了2.4%;而当嵌入维数从6变成2时,AP从0.734下降到0.603,降低了13.1%.可以发现,随着ρ不断变化,LEWL的性能变化不大,相对还是比较稳定的,这也暗示其具有鲁棒性.然而,当嵌入维数d特别小的时候,这两个数据集的性能变差,这可能是由于嵌入空间维数太低,不能很好地提取全部标签的信息.因此,对于每个数据集来说,选择合适的嵌入维数是至关重要的.

图2

图2   在Emotions(上图)和Medical(下图)数据集上的平均精度

Fig.2   Average Precision on Emotions(up) and Medical(down) datasets


3.6 参数敏感度分析

在提出的LEWL算法中有两个参数:λβ.权衡参数λ控制特征嵌入和标签嵌入的权重比例,β是正则化参数.为了研究λβ的影响,分别选取λ=0.001,0.01,0.1,1,10,100

β=0,0.001,0.01,0.1,1,10六种情况,在Enron数据集上进行实验,如图3所示.

图3

图3   λβ对Emotions数据集的影响

Fig.3   Varying λ and β on Emotions


图3可以看出,当β=0时,该算法完全忽略样本的流形结构;当0<β<10时,曲线逐渐上升,说明样本平滑性假设对于缺失标签恢复具有一定的作用;β10时,则效果逐渐下降,这说明需要选取合适的β来使效果达到最佳.对于λ来说,当λ=0时,效果较差,随着λ的不断增加,性能不断提升,证明了算法采用HSIC标准的有效性和合理性.在其它数据集上也有类似的结果.

4 结 论

针对高维弱标记问题,本文提出一种基于嵌入式的弱标记分类算法LEWL.首先,将矩阵分解融入多标签算法中:一方面矩阵分解确实是一种有效的降维方法,通过利用标签之间的关系获得一个低维的嵌入空间;另一方面再结合样本的流形结构来恢复缺失的标签.其次,为了增强嵌入空间的可预测性,它的学习过程应当与特征空间有较强的相关性.本文采用HSIC技术来增强特征空间和嵌入空间的依赖性.实验结果表明,本文算法对缺失标签的恢复具有良好的效果,而且获得的嵌入空间具有可预测性和可恢复性,同时有效地缓解了面对高维标签空间时的低效性.但多标签学习领域还存在诸多挑战,例如准确地选取嵌入空间维数,高度类不平衡问题等,今后将会进一步考虑标签之间的相关性,使多标签的分类性能有更大的提升.

参考文献

Katakis ITsoumakas GVlahavas I.

Multilabel text classification for automated tag suggestion

Proceedings of the ECML⁃PKDD/2008 Workshop on Discovery Challenge. Antwerp,BelgiumSpringer, 200818:5.

[本文引用: 1]

Jia XSun F MLi H Jet al.

Image multi⁃label annotation based on supervised nonnegative matrix factorization with new matching measurement

Neurocomputing,2017219518-525.

[本文引用: 1]

Elisseeff AWeston J.

A kernel method for multi⁃labelled classification

Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic. Vancouver,CanadaMIT Press2001681-687.

[本文引用: 1]

Boutell M RLuo J BShen X Pet al.

Learning multi⁃label scene classification

Pattern Recognition,200437(9):1757-1771.

[本文引用: 2]

Tsoumakas GVlahavas I.

Random k⁃labelsets:An ensemble method for multilabel classification

European Conference on Machine Learning. Springer Berlin Heidelberg,2007406-417.

[本文引用: 1]

Read JPfahringer BHolmes Get al.

Classifier chains for multi⁃label classification

Machine Learning,201185(3):333-359.

[本文引用: 1]

Zhang M LZhou Z H.

ML⁃KNN:a lazy learning approach to multi⁃label learning

Pattern Recognition,200740(7):2038-2048.

[本文引用: 1]

Freund YSchapire R.

A short introduction to boosting

Journal of Japanese Society for Artificial Intelligence,199914(5):771-780.

[本文引用: 1]

马宏亮万建武王洪元.

一种嵌入样本流形结构与标记相关性的多标记降维算法

南京大学学报(自然科学),201955(1):92-101.

[本文引用: 1]

Ma M LWan J WWang H Y.

A multi⁃label dimensionality reduction algorithm embedded sample manifold structure and label correlation

Journal of Nanjing University (Natural Science)201955(1):92-101.

[本文引用: 1]

彭成伦. 多义性机器学习中的标记嵌入方法研究. 硕士学位论文. 南京东南大学2018.

[本文引用: 1]

Peng C L. Research on label embedding in ambiguous machine learning. Master Dissertation. NanjingSoutheast University2018.

[本文引用: 1]

Hsu D JKakade S MLangford Jet al.

Multi⁃label prediction via compressed sensing

2009

arXiv:0902

.1284.

[本文引用: 1]

Tai FLin H T.

Multilabel classification with principal label space transformation

Neural Computation,201224(9):2508-2542.

[本文引用: 3]

Chen Y NLin H T.

Feature⁃aware label space dimension reduction for multi⁃label classification

Advances in Neural Information Processing Systems. Lake Tahoe,NV,USANeural Information Processing Systems Foundation,Inc.,201221529-1537.

[本文引用: 2]

Lin Z JDing G GHan J Get al.

End⁃to⁃end fea⁃ture⁃aware label space encoding for multilabel classification with many classes

IEEE Transactions on Neural Networks and Learning Systems,201829(6):2472-2487.

[本文引用: 1]

刘阳. 多标签数据分类技术研究. 博士学位论文. 西安西安电子科技大学2018.

[本文引用: 1]

Liu Y. Research on Multi⁃label data classification technology. Ph.D. Dissertation. Xi'anXidian University2018.

[本文引用: 1]

Sun Y YZhang YZhou Z H.

Multi⁃label learning with weak label

Proceedings of the 24th AAAI Conference on Artificial Intelligence. Atlanta,GE,USAAAAI Press2010593-598.

[本文引用: 1]

Wu B YLiu Z LWang S Fet al.

Multi⁃label learning with missing labels

2014 22nd International Conference on Pattern Recognition. Stockholm,SwedenIEEE20141964-1968.

[本文引用: 2]

Guo BHou CShan Jet al.

Low rank multi⁃label classification with missing labels

2018 24th International Conference on Pattern Recognition (ICPR2018). Beijing,ChinaIEEE2018417-422.

[本文引用: 2]

Han Y FSun G LShen Yet al.

Multi⁃label Learning with Highly Incomplete Data via Collaborative Embedding

Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. London,United KingdomACM Press20181494-1503.

[本文引用: 1]

Xu MJin RZhou Z H.

Speedup matrix completion with side information:application to multi⁃label learning

Proceedings of the 27th Annual Conference on Neural Information Processing Systems. Montreal,CanadaMIT Press20132301-2309.

[本文引用: 1]

Xu L LWang ZShen Z Fet al.

Learning low⁃rank label correlations for multi⁃label classification with missing labels

2014 IEEE International Conference on Data Mining. Shenzhen,ChinaIEEE20141067-1072.

[本文引用: 1]

Candès E JTao T.

The power of convex relaxation:near⁃optimal matrix completion

IEEE Transactions on Information Theory,201056(5):2053-2080.

[本文引用: 1]

Wen Z WYin W TZhang Y.

Solving a low⁃rank factorization model for matrix completion by a nonlinear successive over⁃relaxation algorithm

Mathematical Programming Computation,20124(4):333-361.

[本文引用: 1]

Zhang YSchneider J.

Multi⁃label output codes using canonical correlation analysis

Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. Fort Lauderdale,FL,USAJMLR2011873-882.

[本文引用: 1]

Gretton ABousquet OSmola Aet al.

Measuring statistical dependence with Hilbert⁃Schmidt norms

International Conference on Algorithmic Learning Theory. Springer Berlin Heidelberg,200563-77.

[本文引用: 1]

Han S JQubo CMeng H.

Parameter selection in SVM with RBF kernel function

World Automation Congress 2012. Puerto Vallarta,MexicoIEEE20121-4.

[本文引用: 1]

Lin Z JDing G GHu M Qet al.

Multi⁃label classification via feature⁃aware implicit label space encoding

Proceedings of the 31st International Conference on International Conference on Machine Learning. Beijing, China: JMLR.org,2014325-333.

[本文引用: 1]

Han Y HWu FJia J Zet al.

Multi⁃task sparse discriminant analysis (MtSDA) with overlapping categories

Proceedings of the 24th AAAI Conference on Artificial Intelligence. Atlana,GA,USA:AAAI Press, 2010:469-474.

[本文引用: 1]

Pacharawongsakda ETheeramunkong T.

Towards more efficient multi⁃label classification using dependent and independent dual space reduction

Pacific⁃Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg,2012383-394.

[本文引用: 1]

Zhang M LZhou Z H.

A review on multi⁃label learning algorithms

IEEE Transactions on Knowledge and Data Engineering,201326(8):1819-1837.

[本文引用: 1]

/