一种多标签半监督学习方法

一种多标签半监督学习方法

近年来，半监测学习方法是机械学习领域的研究重点。先后设计了模型、合作培训、半监测图像和直推支持向量机的方法。区别于有监督和无监督学习方法,半监督学习同时从已标签数据和无标签数据中学习,使得最终的目标函数在全部数据(包括已标签和无标签数据)上满足流形或者聚类等假设。多数情况下,如果无标签数据有助于对数据分布或者结构的学习,半监督学习方法比纯粹的有监督或无监督学习方法有更好的学习效果,因此在已标签数据获得困难,且又存在大量无标签数据的应用中,半监督学习方法的作用显得尤其重要。多标签学习(multi-labellearning)是目前机器学习领域中的一个热点问题。传统的分类学习包括多类学习(multi-classlearning)问题,每个样本只属于一个类别。然而在很多实际问题中,一个样本可能同时属于多个类别。例如,一篇文档可能属于多个预定义的主题;一张图片可能同时具有多个语义;一个基因可能具有多种功能。至今,研究者们已经提出了多种多标签学习方法,大致可以分为问题转换方法,包括ClassifierChains、Randomk-labelsets,以及算法改进方法,包括MLKNN(multi-labelk-nearestneighbor)多标签图半监督学习方法。MLKNN作为近邻法在多标签情况下的推广,在多篇报道中的多个数据集上都有略好于其他方法的表现,是多标签学习中最好的方法之一。与以往的所有半监督学习方法相比,笔者提出的最大化依赖性多标签半监督学习方法以最大化所有样本特征集(包括已标签和未标签样本)和标签集之间的依赖程度作为学习的假设前提和目标,与传统半监督学习方法将聚类假设或流形假设等作为利用无标签样本的方式不同。样本特征集和标签集之间的依赖性可以采用CCA(canonicalcorrelationanalysis)、KCC(KernelConstrainedCovariance)以及HSIC(Hilbert-SchmidtIndependenceCriterion)。HSCI对再生核希尔伯特空间(RKHS)上的希尔伯特-施密特算子进行统计估计,提出的依赖性经验估计值在理论上具有收敛速度快和计算简单等特点。因此,笔者选用HSIC作为样本特征集和标签集之间依赖程度的度量和优化目标,并在添加样本已有标签作为约束的情况下,将DMMS转换为线性系统求解问题,具有实现简单、无参的特点。本质上,无论样本点有多少个标签,DMMS总是将其所有的标签看成一个点映射至标签集所在的再生核希尔伯特空间。类似地,每个样本的样本值也映射至样本集所在的再生核希尔伯特空间,进而通过最大化该两个空间的互协方差(cross-covariance)算子对应统计量的估计值得到未标签样本所有可能的标签。因此,DMMS不仅是一个半监督学习方法,而且不需做任何改进,本身就是多标签学习方法。笔者在多个真实多标签数据库对比了DMMS、MLKNN和同样适用于多标签学习的图半监督学习方法,实验结果表明,DMMS作为一种新的多标签半监督学习方法是可行的。1hsic的基本原理HSIC是一种基于核的独立性度量方法。该类方法总的原则是在再生核希尔伯特空间上定义互协方差算子,进而从这些算子中推导出适合度量独立性的统计量来决定独立性的大小。HSIC采用的是Hilbert-Schmidt互协方差算子,通过对该算子范数的经验估计得到独立性判断准则。假设M和N都是可分度量空间。令F为M的再生核希尔伯特空间,F中元素f是M到R的函数。M到F上的映射记为Φ:M→F,于是核函数可以写为式中,〈·,·〉F表示空间F上的内积。类似地,将N的再生核希尔伯特空间记为G,有N到G的映射Ψ:N→G,相应的核函数为假设PrX×Y是(M×N,Γ×Λ)上的联合分布,Γ和Λ分别是M和N的Borel集。相应的边缘分布分别记为PrX和PrY,互协方差算子Cxy:G→F定义为式中,μx和μy分别表示Φ(x)和Ψ(y)的期望,ue3c1表示张量积,对任意f∈F和g∈G,有fue3c1g:G→F为Cxy可以看成Hilbert-Schmidt算子,而所谓的HSIC即定义为Cxy的Hilbert-Schmidt算子范数,也即在观察得到数据Z=((x1,y1),(x2,y2),…,(xn,yn))的基础上,可以给出HSIC的经验估计值为式中,H,K,L∈Rn×n,H=I-(1/n)eeT,I为单位矩阵,e是元素值全为1的列向量,K和L分别是核k和l关于Z观测值的Gram矩阵,即Kij=k(xi,xj)以及Lij=l(yi,yj)。HSIC的经验估计值在理论上已经被证明具有收敛速度快以及计算简单等优点,其值越大说明M和N的关联性越强,等于0时说明M和N相互独立。2学习目标与方法考虑到样本特征与其标签具有一定联系的基本假设,本文利用HSIC量化样本特征集与标签集之间的关联程度,并通过最大化HSIC为无标签样本打上标签。给定已标签数据集和未标签数据集分别为:式中,M和N分别是样本特征集和标签集所在空间。假设样本可能的类别总数为m,则已标签样本xi(i=1,2,…,l)的标签yi是一个m维列向量,且:假设无标签数据xj(j=v+1,v+2,…,v+u)的标签yj∈Rm已知(与已标签样本的标签表示方法类似,yj也是m维列向量,只是其中元素是实数,可以看成是样本的“软标签”,本文目标即是求得这些“软标签”),记:给定M和N上的核函数分别为k(x,x′)(x,x′∈M)和l(y,y′)(y,y′∈N),则可得到它们关于X和Y的Gram矩阵K和L,从而有式中,F和G分别是M和N的再生核希尔伯特空间,H的定义同式(6),n=v+u表示样本总数。简单起见,标签集上的核函数取为线性核,即l(y,y′)=y′Ty(y,y′∈N),重写式(9)的迹,有DMMS方法的目标就是求解Y,使得样本特征集和标签集的关联性即式(10)的值最大。然而,因为K是一个半正定的Gram矩阵,而H又是对称矩阵,因此HKH同样是个半正定矩阵,如果没有其他的限制条件,式(10)事实上没有最大值。针对该问题,常见的方法是对Y进行限制,比如限制YTY=I,但可能会对求解带来一些麻烦。本文的方法是添加正则项,修改式(10)为优化目标:式中,D是对角矩阵,且。显然,H(K+D)H是半负定矩阵,因此式(11)有最大值。注意到Y对应于已标签样本部分是已知的,本文将已知标签作为边界条件。记YV为Y中对应于已标签样本部分,并令DMMS最终写为以下优化问题:显然,DMMS的学习效果取决于对依赖性进行估计的准确程度。从式(3)和(5)可知,依赖性取决于对互协方差算子的估计,而互协方差算子是张量积的期望和μx的和。大量无标签样本的加入对于该两项的估计无疑都有帮助。因此,可以期望DMMS能够利用无标签样本提高对依赖性估计的准确程度,从而提高学习准确率。此外,从式(7)可知DMMS对于标签集中元素的维数和值并没有限制,且无论样本的标签是多少维和值是多少,都只能将其看Y中一个点映射至再生核希尔伯特空间,因此DMMS同时也是一种多标签学习方法。3解析解求解为了求解具有边界条件的最优化问题式(13),将A按照已标签和无标签样本的划分分成4部分,有式中,AV和AU分别对应已标签和未标签样本,ATUV=AVU。类似地有于是有YV=[y1,y2,…,yv]是固定值,优化问题进一步转换为由式(12)和(14)可知,AU是半负定矩阵,因此式(17)存在解析解。令可得求解上述线性方程组可以得到无标签样本的“软标签”YU。“软标签”可以认为是给出了无标签样本属于某类的置信值,比如Yij是第j个样本属于第i类的置信值,其值越大就越有理由相信其是属于第i类。此外,从DMMS的求解步骤来看,DMMS具有实现简单以及无参的特点,求解主要可分成两步:1)根据指定的核函数求出样本特征集的Gram矩阵以及相应的A矩阵;2)求解线性方程组式(20)。4反k折交叉验证为了凸显无标签样本对学习效果的影响,实验评测采取本文提出的反k折交叉验证(reversek-foldcrossvalidation)的方式。所谓反k折交叉验证指样本集被分成k组,每一组轮流当训练集,剩下的k-1组作为测试集,与k折交叉验证正好相反。通过反k折交叉验证,本文对比了DMMS、MLKNN和图半监督学习方法在多标签学习问题方面的学习效果。4.1基于近邻图的监督学习方法DMMS在样本特征集上的核函数选为常用的高斯核,即另外,MLKNN和图半监督学习方法均需要构建近邻图。设近邻数目统一为15,并将式(21)作为构图过程中任意两个样本特征之间的相似度(距离)计算公式。最后,取定MLKNN中的平滑参数值为1。4.2清体现代机械系统实验所用的数据集可以从开源项目mulan下载得到。这些数据集被广泛用于多标签学习中[6,7,8,9,10,11,12,13],如表1所示。4.3单标记类预测结果传统的单标签分类问题中的评测指标包括的准确率、查准率、查全率和F-measure等都不适用于多标签学习问题。多标签学习问题中的评测要比单标签学习的评测复杂很多。文献定义了目前多标记学习中的5种常用评价指标,具体公式可参见原文。简介如下:1)汉明损失:指定阈值后,可以通过样本类属置信值预测得到任意未标签样本的类属,比如yji大于阈值,则认为第i个样本属于第j类。汉明损失可衡量预测结果与样本实际类属之间的不一致程度,即样本属于某类但未被识别出,或不属于某类却被误判的可能性。2)1-错误率:描述对任一样本类属置信值最高的类属不是其实际类别的平均可能性,在单标记学习中,演化成普通的分类错误率。3)覆盖率:将任意样本对应的类属置信值降序排序,覆盖率衡量从置信值最高的类别开始,平均需要跨越多少个类属才能覆盖样本所属的全部类别。4)排序损失:表明预测结果里真实所属类别的置信值低于非所属类别置信值的可能性。5)平均精度:平均精度反映置信值大于真实类别置信值的类属全是样本所属真实类别的可能性。5项指标值中,只有平均精度是越大越好(最大为1),其他指标都是越小说明学习方法越有效。4.4dmms和gsl在sc环境保护基本参数下的差异本文在Emotions、Yeast、Scene三个真实数据库上对比了图半监督学习(GSL)、MLKNN和DMMS三种方法的分类效果。实验分为两组:第一组实验是反5折交叉验证,即已标签数据占总数据的1/5,实验结果分别如表2、3和4所示,分别是Emotions,Yeast和Scene三个数据库上的结果;第二组实验是反10折交叉验证,已标签数据只占总数据的1/10,类似地,实验结果分别如表5、6和7所示。表中的黑体表示在某指标里表现最好的值。从第一组的实验结果可以看到,DMMS在Scene数据集中的各项指标都要好于其他两个方法,Emotions数据集上DMMS方法要好于MLKNN方法,略差于GSL方法。Yeast数据集是DMMS表现最差的一个数据集,尽管如此,DMMS在该数据集的one-error指标上依然得到了一个最小值,说明如果只返回一个类属,则DMMS的结果最可信。MLKNN的结果在Emotions数据集上的效果不理想,可能的原因是在反5折交叉验证实验里,该数据集用于实验的已标签样本只有一百多个,对MLKNN影响很大,而对属于半监督学习方法的GSL和DMMS的影响则小很多。类似的结果可以从第二组实验看到,DMMS在Scene数据集上的各项指标值依然都要略好于其他两个方法,并且在Yeast数据集的hammingloss指标上取得了略好于其他方法的结果,由原来的第二位上升到了第一位。此外,因为第二组实验中已标签数据的数目下降为原来的一半,所有方法在各个指标上的值都略为变差。DMMS和GSL作为半监督学习方法,相较于MLKNN受该方面的影响比较轻微。比如,对比DMMS方法在Scene数据集上两次的实验结果,基本上没有很大变化,平均精度都维持在了0.83上。总之,上述实验说明DMMS作为多标签半监督学习方法可以有效地从无标签样本中学习,并且适用于多标签学习问题。5最大化依赖多标签半监督学习方法的局限性在希尔伯特-施密特独立性(Hilbert-Schmidtindependencecriterion,HSIC)的基础上提出了最大化依赖性多标签半监督学习方法。该方法是一种多标签半监督学习方法,具有实现简单且无参等特点。在Scene等真实数据库上的实验表明,最大化依赖性多标签半监督学习方法具有类似于其他多标签方法的学习效果,甚至有可能在已标签样本稀少的情况下略