半监督学习方法的评价.docx

《半监督学习方法的评价.docx》由会员分享，可在线阅读，更多相关《半监督学习方法的评价.docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、摘要半监督学习利用大量未标记数据结合少量标记数据提升学习性能。本文涉及几种半监督分类方法的评价。文章由三个主要部分组成。首先，介绍半监督学习的定义和基本假设；第二部分为本文的主体部分，介绍了四种半监督学习方法：弱监督学习、生成模型、直推式支持向量机、基于图的方法，结合数据集对其优势和缺陷进行评价；在第三部分中，本文从理论上分析了未标记数据对分类性能提升的作用。关键词：半监督学习 分类 生成模型 直推式支持向量机 基于图的方法AbstractSemi-supervised learning uses a large amount of unlabeled data, together with

2、the labeled data to build a better classifier. This paper is concerned with the evaluation of several semi-supervised methods. There are three major ingredients. The first is an introduction on the definition and some popular assumptions of semi-supervised learning. The second, which is the main ing

3、redient of this paper, studies the four main semi-supervised methods, including weakly supervised methods, generative model, transductive support vector machine and graph-based methods. Some experiments on datasets of these methods have been carried out, to characterize their advantages and limitati

4、ons. The third ingredient present the theoretical analysis of how unlabeled data can be used successfully for classification. Key words: semi-supervised leaning, classification, generative model, transductive support vector machine, graph-based method 第一章 前言1.1 研究背景与意义1.1.1 半监督学习的定义为定义半监督学习，首先我们需要明确

5、监督学习和无监督学习的含义。首先给出一些基本的定义Error! Reference source not found.Error! Reference source not found.。样例x通常指一个D维向量x=x1,x2,xd，它的每一维称为一个特征，D即为特征向量的维数。训练集xi,yii=1n则是由n个样本点组成的集合，它是学习过程的输入值。标签y与样例x相对应。在分类问题中，它指代类别，通常为整数。对于多分类问题，可令y1,2,C，其中，C是类别的数量。监督学习是指，通过给定的有标记训练集xi,yii=1l，训练一个从输入X到输出Y的映射f。监督学习根据标签y的类型可分为两类。如果

6、y是离散值，则为分类问题，此时f是一个分类器；否则为回归问题，f则为回归函数。无监督学习的输入是一个未标记数据集xii=1u，最常见的一类无监督学习是聚类问题，它的目标是将n个样本点分为若干簇。无监督学习还包括离群点检测和降维等类型。本文集中于讨论分类问题。半监督学习是一种介于监督学习和无监督学习之间的学习方法Error! Reference source not found.。对于半监督分类问题，它综合利用标记数据集xi,yii=1l和未标记数据集xii=l+1u进行训练，通常情况下有标签的样例数目远大于无标签的样例数目，即ul。根据学习目的，半监督学习可分为两种类型：纯半监督学习和直推式半

7、监督学习。前者的目标是利用给定训练集xi,yii=1l,xii=l+1u训练f:XY，使f在新的样本上依然能给出好的预测。后者根据训练集训练f:Xl+uYl+u，即只需预测训练集中无标记样本的标签，不需要对新的样本具备预测能力。1.1.2 半监督学习的动机传统的监督学习需要一定规模的标记训练集，然而，实际问题中标签的获取代价很高。相比于难以获得的标记数据，我们更容易获取大量无标记数据。例如，在文本分类问题中，根据内容对文档进行人工标记很费时，但未标注的文档容易获得。半监督学习的动机在于，有效利用大量相对廉价的未标记数据提升学习性能。半监督学习通常需要依赖某些基本假设。常用的假设有以下三种：1)

8、 平滑假设Error! Reference source not found.，即当样本x1,x2在样本分布密集的区域内距离相近时，它们的标签相同。2) 低密度分离假设Error! Reference source not found.，要求决策边界位于样本分布稀疏的区域。低密度分离假设的等价表述为聚类假设，即位于同一聚类的样本有相同标签。聚类假设也可被视为平滑假设的一个特例，因为通常样本集中的区域组成一个聚类。在聚类假设下，未标记数据指导分类器识别数据密集和稀疏的区域，使决策平面穿过低密度区域。3) 流形假设Error! Reference source not found.，这一假设认为在

9、一个小的局部邻域内，样本有相似的性质，因而有相似的输出，在分类问题中则是有相同的标签。在流形假设下，未标记数据让数据空间变得更加密集，从而准确反映空间的局部特征。流形假设可以看作是从局部角度描述的聚类假设。三种假设本质上是一致的，区别在于关注的角度不同。流形假设可以应用于半监督回归，因此更为普遍。1.2 研究成果回顾最早在分类问题中使用未标记数据的是自训练方法Error! Reference source not found.。自训练在学习过程中反复利用某种监督学习方法，是一种包裹算法。它将标记数据集作为初始训练集，在每一步迭代中通过决策函数将部分未标记数据联同新给定的标签并入训练集，在新的训

10、练集上再次训练分类器。之后提出的是直推式学习的概念Error! Reference source not found.，它基于Vapnik原理，即不在解决问题的过程中解决更复杂的问题。直推式学习只预测已有未标记数据的标签，对新的样本不具备预测能力。半监督学习在20世纪70年代取得重要发展。对于高斯混合分布模型或混合多项分布模型Error! Reference source not found.，利用EM算法可在由标记和未标记数据集组成的训练集上对模型参数进行最大似然估计。更进一步地，每个分类可以对应多个混合成分。20世纪90年代，由于自然语言处理和文本分类对利用未标记数据提升分类性能的需求，半

11、监督学习成为热点问题。我们通常认为，“半监督学习”这一术语在1992年首次出现Error! Reference source not found.。目前主要的半监督学习方法有协同训练Error! Reference source not found.、生成模型Error! Reference source not found.、直推式支持向量机Error! Reference source not found.和基于图的方法Error! Reference source not found.。1.3 论文的章节安排在第二章中，我们将介绍两种弱监督学习方法：自训练和协同训练，并在标准数据集上对其

12、分类性能进行简单评测。在第三章中我们将介绍生成模型的原理，并具体介绍了基于混合多项分布的朴素贝叶斯模型，以及如何在标签缺失的情况下用EM算法进行参数估计。同时，我们将其应用在文本分类问题中，在20 Newsgroups数据集上对比了朴素贝叶斯和半监督朴素贝叶斯模型的分类准确度。在第四章中我们将介绍直推式支持向量机的理论，在满足低密度分离假设的数据集和随机选取的数据集上，将其分类准确度与支持向量机进行比较。在第五章中，我们将给出三种基于图的半监督学习方法，在正则化框架下完成其理论推导，并在图像数据集USPS和文本数据集20 Newsgroups的一个子集上观测其分类性能。在第六章中，我们基于PA

13、C框架，对半监督学习进行简单的理论分析。在结论部分，我们对全文内容进行总结，并提及半监督学习在未来的发展方向。第二章 弱监督学习自训练和协同训练在分类器的学习过程中，通过自助法利用未标记样本扩大训练集的规模，但依然使用监督式的分类器，因此又称为“弱监督学习”Error! Reference source not found.。本章余下部分将介绍这两种学习方式，给出实验结果和评价。2.1 自训练自训练是一种简单高效的半监督学习方法。它不需要任何对于输入数据的假设，它所基于的假设是，对于每一次预测，置信度高的样本有更大的可能性获得正确分类。自训练的学习步骤如下：1. 给定有标签的训练集L，无标记样

14、本集U；2. 在L上训练初始分类器；3. 利用初始分类器对U中全部数据进行标记，将置信度最高的数据及其新获得的标签移入L中，从而完成对L的更新；4. 在新获得的L上重新训练分类器，如此迭代，直到所有的无标记数据都获得标记为止；5. 最后，原始的标记数据集与获得标签的无标记数据集将共同作为训练集，训练出最终的分类器，对新的样本仍可进行分类。上述训练过程中对分类器的类型没有任何限制。由此看出，自训练是一种包裹算法，即它在中间步骤中可以对分类方法进行开放性的选择。自训练通过在每次迭代中从未标记数据集中选取样本并入标记数据集，解决了标记样本数量有限的问题。然而，由于训练初始分类器的样本很少，对未标记样

15、本容易出现错误分类，错误在迭代过程中累积，因此无法直接判断自训练相比监督学习能否提升分类性能。为评估自训练在数据集上的表现，我们选取了9组标准数据集，随机抽取百分之十的数据作为标记样本，使用十折交叉验证法，隐去训练集中未标记样本的标签，对测试集中的标签则予以保留。本章实验使用KEEL软件Error! Reference source not found.。这里我们选用的分类方法是k最近邻(k=3)。此时自训练步骤中第2步的具体过程为：（1）对于U中任意未标记样本xU，选取欧氏距离最近的3个标记样本点，3个点投票决定它的标签。若三点标签不同，则选取其中距离最近的点并采纳标签；（2）取三个样本点中

16、与xU标签相同的点，计算它们到xU的平均距离作为置信度。取置信度最高的xU并入L中。数据集信息如表1所示：数据集样例数目维数类别bupa34562cleveland303135ecoli33678haberman30632iris15043monk241062pima76882vehicle846184wisconsin69992表1在这些数据集上分别采用监督式3NN和自训练3NN方法，分类准确度如图1所示。图 1 从图中看出，在大部分数据集上，自训练(3NN)相比3NN方法对分类准确度没有明显提升。在kNN算法中，未标记点的标签依靠近邻点确定，据此推测，对于使用kNN分类器的自训练方法，当数

17、据集呈现出明显分类时，由于没有离群点的干扰，kNN方法错误率低，自训练由于自主扩大了训练集可以获得更准确的分类。我们对使用自训练方法后分类准确度有大幅变化的haberman和iris数据集的前三个维度做可视化处理，如图2所示。图 2左图的haberman数据集没有明显的聚类特征，因此容易出现误分类，自训练过程中错误累积。右图的iris数据集类别间分界明显，通过自训练方法扩大了训练集的规模，获得了更好的分类精度。事实上，文献Error! Reference source not found.的结论表明没有一种自训练方法适合所有数据集，选用了某种分类器（kNN，决策树，支持向量机等）的自训练方法可

18、能会在某一数据集上准确分类，但在其他数据集上会降低原有分类器的性能。2.2 协同训练协同训练的基本思想是将数据特征划分为两个不相交的子集，子特征集又称为视图。在两个视图上分别训练分类器，对于每一个分类器而言，选取置信度最高的未标记样本，在另一个分类器的训练集中移入该样本。具体步骤如下：1. 将L据特征分为互不相交的L1,L2，在其上分别训练分类器h1,h2;2. 通过h1将U中置信度最高的样本移入L2，通过h2将置信度最高的样本移入L1；3. 在新的L1,L2上重新训练分类器h1,h2；4. 重复2,3步直到U中没有样本。协同训练依赖于两个重要的假设：（1）在有足够多的标记样本时，每个视图对于

19、作出好的分类是充分的；（2）在给定标签的前提下，两个视图条件独立。第一个假设是显然的，因为在任一视图上训练一个不好的分类器没有意义。第二个假设则是为了一个视图可以为另一个视图提供更多信息量。如果两个视图完全相关，协同训练则退化为自训练。 已有研究表明Error! Reference source not found.，当满足假设时，协同训练相对单视图训练一定可以提升分类性能。协同训练的提出背景为网页分类，两个视图分别为网页本身的信息和它的超链接所包含的信息。然而，在多数实际问题中，我们很难将特征划分为满足条件的两个子集。我们利用随机分割特征的方式对表1中的数据集采用协同训练(3NN)，从图3可

20、以看出，当假设条件不满足时，协同训练表现糟糕。图 32.3 本章小结在本章中，我们在9个标准数据集上运行了使用3NN分类器的自训练和协同训练方法，结合前文分析，得到结论如下：自训练是最简单的半监督学习方法，作为一种包裹算法，它可以结合使用任何一种分类器。但是在自训练早期出现的错误分类会在迭代过程中不断增强，导致其分类性能不如在少量标记数据集上训练出的监督式分类器。协同训练同样是包裹算法，它的主要缺陷在于，它所依赖的假设条件在实际应用中难以满足。并且在训练前期分类器较弱时，会将错误标签引入另一个分类器中，从而产生噪声。第三章 生成模型给定训练集T=LU，生成模型假定样本都生成于一个潜在的模型，即

21、它需要学习的是“生成数据的机制”。它通过观察大量样本估计条件分布p(x|y)与先验分布p(y)，再根据贝叶斯定理pyx=px,ypx=pypxypxpypxy#(3.1)得出判断准则。在半监督学习中，我们首先由标记数据获得联合分布px,y=p(y)p(x|y)的参数，再根据未标记数据对参数进行调整。常用的生成模型有混合高斯分布、朴素贝叶斯模型、隐马尔科夫模型等。生成模型需要满足两个假设：（1）数据由混合模型生成；（2）混合成分和类别一一对应。本章余下部分安排如下：首先阐述朴素贝叶斯模型的原理，在此基础上介绍半监督朴素贝叶斯模型，接下来在文本数据集20 newsgroup上比较二者的分类准确度，

22、最后总结本章。3.1 监督学习的朴素贝叶斯模型本节我们将介绍基于混合多项分布的朴素贝叶斯模型。首先给出混合模型的定义。混合模型用来描述不规则的概率分布。它通过混合多个形式相同的概率密度函数组成一个密度函数：px=k=1ckpxk#3.2其中每个概率密度函数称为一个混合成分；=k,kk=1c为模型的参数集合，k是第k个混合成分的参数，k是混合成分的权重，k=1ck=1,这样就保证了pxdx=k=1ckpxkdx=k=1ck=1#3.3给定训练集T=xi,yii=1l，其中y=1,c。我们的目标是训练出分类器，将新给定的x归入某一类，即计算出Py=1x,Py=cx，若k=argmaxkP(y=k|

23、x)，则x属于第k类。在朴素贝叶斯模型中，我们假设x的每一特征条件独立，则有pxypy=pyj=1dpxj#3.4根据贝叶斯定理我们得到：Py=kx=Pxy=kPy=kPx#3.5此时在每一类中，x符合多项分布：xMultN,y ，y=1,c#3.6其中N=i=1dxi,y=y1,yd，则有pxyj=1dyjxj#3.7它的对数似然为logpxy=j=1dxjlogyj+C#3.8其中C为常数。由此，在pxy与p(y)已知的情况下，分类准则为：y*=argmaxkPxy=kPy=k =argmaxkj=1dxjlogkj+logPy=k#3.9此时问题转化为求解pxy和p(y)，我们将其作为模

24、型参数，在训练集上利用最大似然求解。令Py=k=k,pxy=k=Mult(N,k)j=1dkjxj，则模型参数集=,1,c,似然函数写为：L=i=1nP(xi,yi;)=i=1nPxiyi;Pyi,=i=1nyij=1dyi,jxij=k=1ckIyi=ki:yi=kj=1dkjxij#3.10取对数似然：logL=k=1cIyi=klogk+k=1ci:yi=kj=1dkjxij=L1+L2#3.11则最大似然问题转化为两个约束优化问题：maxiL1s.t. k=1ck=1#3.12和maxL2s.t. j=1dkj=1,k=1,c#3.13使用拉格朗日乘子法解得：k=Iyi=knkj=i:

25、yi=kxijj=1di:yi=kxij#3.14可以看出P(y=k)与P(xi=(xi1,xid)|y=k)的最大似然解恰好与频率相等。我们注意到，如果在训练集中的某一类中，第j个分量的值始终为0，则对应的kj=0，由朴素贝叶斯模型的条件独立性，整个样本出现的概率为0，这显然是不符合实际的。我们对其进行平滑处理。为简化表达，我们同时引入ik:ik=1,yi=k0,yik此时参数估计可写为：k=i=1nik+ n+ckj=i=1nikxij+i=1nj=1dxij+d#3.15此时对于新给定的x，我们通过下式判断它的类别：y=argmaxkPy=kPxy=k =argmaxkkj=1dkjxj

26、#3.163.2 半监督朴素贝叶斯与EM算法在半监督学习中，我们希望利用大量的未标记数据提升分类准确度，这意味着，模型参数的选取建立在整个数据集上。给定训练集L=xi,yii=1l,U=xii=l+1l+u，在为U中样本加上标签之前，LU上的对数似然函数写为：logL=i=1llogPxi,yi +i=l+1nlogPxi;#3.17此时U中样本的标签为隐变量，将其记为z，用zk表示y=k，即有i=l+1nlogPxi=i=l+1nlogk=1cPxi,zk;#3.18在对数函数中有求和形式，因此似然函数的最大化不能通过求导直接完成，我们可以通过最大化它的下界增大似然函数。假设Qi为隐变量z的

27、某个分布函数，则有i=l+1nlogPxi=i=l+1nlogk=1cQizkPxi,zk;Qizk#3.19根据k=1cQizk=1，利用Jensen不等式，我们有i=l+1nlogPxii=l+1nk=1cQizklogPxi,zk;Qizk欲使i=l+1nlogPxi的下界最大化，即等号成立，由不等式等号成立条件得，Pxi,zk;Qizk为常数，即QizkPxi,zk;结合Qi的归一性，得到Qizk=Pxi,zk;k=1cPxi,zk;=Pxi,yi=k;Pxi;=P(yi=k|xi;)即Qizk实际上是每个样本的后验概率ik=Py=kxi;，ik又称责任参数，意指第k类对样本xi的生成

28、需承担的责任。这时，我们只要计算出ik，就能使不等式的等号成立，从而使似然函数中包含隐变量的部分达到最大下界，并消除了对数函数与求和函数的复合形式，将似然函数转换成只包含的函数，这一步骤称为E步，接下来我们可以用一般的最大似然方法求解参数，这一步骤则称为M步。在实际应用中，为了简化计算，我们选择用最大后验为U中样本赋予标签，即不考虑未标记样本分入其他类别的概率，然后在全部训练集上通过式(3.15)计算新参数。综上所述，半监督朴素贝叶斯模型训练步骤如下：1. 在L上训练朴素贝叶斯模型，得到初始参数集0=；2. （E步）利用当前的分类器给U中的样本加上标签，记录后验概率ik=Py=kxi；3. （

29、M步）在LU上利用最大似然法重新训练分类器；4. 重复第2,3步，直到似然函数不再上升。3.3 实验结果及分析半监督朴素贝叶斯常用于文本分类，即给定文档判断它的所属类别。将全部文本中所有的词归纳为字典，用x代表文档的词频向量，其中x的第j个分量为为字典中第j个词出现的次数。假设文档中任意单词出现的位置是独立的，不受文档内容影响，则对于每一类文本，x符合多项分布。我们选用的数据集为20 newsgroup，包含20类新闻文档，由约20000个文档组成。前期处理工作包括：(1)去除文档的开头、结尾和引用部分；(2)去除停用词（语气词、助词等）；(3)当一个词在少于五个文档中出现时，忽略这个词。我们

30、取一定比例的文档作为标记数据集，在标记数据集上使用监督朴素贝叶斯模型，在全部数据集上使用半监督朴素贝叶斯模型，比较两种方法的分类准确度，结果如图4所示。图 4从图中可以看出，在标记比例很少的时候，半监督朴素贝叶斯的分类准确度明显高于朴素贝叶斯模型。在拥有2%时的标签时，分类准确度达到50%；在拥有10%的标签时，分类准确度达到60%。在拥有较多标签时，监督和半监督分类效果没有明显差异。3.4本章小结本章介绍了基于混合多项分布的朴素贝叶斯模型和其对应的半监督学习方法，根据两种方法在20 newsgroups数据集上的运行结果可以看出，在标签数目很少时，半监督朴素贝叶斯模型在文本分类中相较于监督学

31、习有更准确的分类。生成模型的优势在于：（1）可以用标记数据确定初始值；（2）当对潜在模型的假设正确时，它利用少量标记数据即可取得很好的分类效果。然而，实际应用中，由于标记数据的稀缺，我们难以判断模型是否正确，甚至得到无用的模型。例如在图5中，样本符合高斯混合分布，正确分类如图5(b)所示，但由于图5(a)所表示的分布似然函数值更大，根据未标记数据拟合出的结果为图5(a),此时错误率会达到50%。另一方面，迭代过程中的似然函数计算时间开销很大。图 5ab第四章 直推式支持向量机直推式支持向量机是建立在监督学习方法支持向量机上的一种半监督学习方法，本章将首先阐释支持向量机的工作原理，在这一基础上介

32、绍直推式支持向量机，然后给出实验结果，结合数据集特征进行分析评价。在本章中只考虑二分类问题。4.1 支持向量机的原理与求解支持向量机(SVM)是一种应用广泛的分类方法，它的基本原理是，在保证正确分类的前提下，最大化分隔平面之间的距离。下面我们将从线性可分和线性不可分两种情况，对SVM进行介绍。线性可分对于D维训练集T=xi,yii=1l，线性可分指的是存在一个超平面，可以完全正确地将训练集划分为两部分。则在Rd中超平面的方程为wTx+b=0#4.1令fx=wTx+b，则超平面可表示为fx=0。该边界将特征空间分为f0与f0是惩罚参数。我们需要做到在间隔尽量大的情况下尽可能减少误分类样本点的数量

33、，C在这两者之间取得平衡。这一问题的求解方法与线性可分支持向量机类似。4.2 直推式支持向量机如前文所述，我们通过利用有标记样本训练支持向量机。直推式支持向量机(TSVM)则是在这一基础上，结合未标记数据，调整决策边界。假定数据集T=LU，其中L=xi,yii=1l,U=xi,yii=l+1l+u，不妨设l+u=t。按照第一章中对直推式学习的定义，此处L为训练集，U为测试集。对于线性可分数据集，图7可以体现出TSVM的意义：使超平面对于整个数据集（包括标记和未标记样本）间隔最大。它可以写成如下的优化问题：minw,b12|w|2s.t. yiwTxi+b1,i=1,l yj*wTxj+b1,j

34、=l+1,l+u#4.10其中，yj*指的是我们在解决问题的过程中为未标记数据找到的标签。图 7对于线性不可分数据集，类似于支持向量机，我们同样采用引入松弛变量的方法，得到的优化问题如下：minw,b12|w|2+Ci=1li+C*j=l+1tjs.t. yiwTxi+b1-i,i=1,l yj*wTxj+b1-j,j=l+1,l+ui0, i=1,lj0, j=l+1,t#4.11训练TSVM意味着需要求解优化问题（4.11）。在测试集规模很小(u10)的情况下，我们可以枚举出yi*的全部可能取值，找到问题的最优解。对于规模较大的数据集，一种普遍使用的方法是SVM light，步骤如下：1.

35、 在训练集L上利用支持向量机方法训练出超平面；2. 使用在步骤1中训练出的超平面对U进行分类，记录其中正负类别的样例数量为n+,n-；3. 给参数C+,C-按类别比例赋予很小的值（如C-=10-5,C+=10-5n+/(u-n-)）4. 当U中的样例xm,xn满足交换条件时，交换它们的标签，完成所有交换后，重新在整个数据集T上训练支持向量机，并更新C+,C-的值：C=minC*2,C*#4.12重复该步骤直到满足CC*为止。步骤4中重新训练的支持向量机对应优化问题:minw,b12w2+Ci=1li+C_j:yj=-1 j+C+j:yj=1js.t. yiwTxi+b1-i,i=1,lyj*w

36、Txj+b1-j,j=l+1,l+u #4.13交换条件指的是ym*yn*2。SVM light的核心步骤在于通过交换测试集中的样本标签，提升了原本仅在训练集上训练出的支持向量机的分类性能。不妨假定ym*=1，则我们可以得到12w2+ Ci=1li+C_j:yj=-1 j+C+j:yj=1j=12w2+Ci=1li+C+m+C-n+12w2+Ci=1li+C-2-m+C+2-n+=12w2+Ci=1li+C-m+C+n+#4.14由上式看出，在标签交换过程中，目标函数值不断减小。在无标记数据集样本数目有限（u0，当结点i,j间的距离di,j，i,j相连。显然，的选取会对图的连通性造成影响，因此的取值需要结合实际问题考虑。由于在稀疏图中，每个结点只与满足条件的结点相连，因此权重矩阵相对全连接图更为稀疏，计算速度快。它的缺点在