EM算法及其在半监督学习中的运用

半监督学习(Semi-supervisedLearning)有监督的学习：学习器通过对大量有标记的训练例进行学习，从而建立模型用于预测未见示例的标记(label)。很难获得大量的标记样本。无监督的学习：无训练样本，仅根据测试样本的在特征空间分布情况来进行标记，准确性差。半监督的学习：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。学习分类半监督学习的过程传统的训练学习算法需要利用大量有标记的样本进行学习。随着信息技术的飞速发展，收集大量未标记的（unlabeled）样本已相当容易，而获取大量有标记的示例则相对较为困难，因为获得这些标记可能需要耗费大量的人力物力。如何利用大量的未标记样本来改善学习性能成为当前模式识别研究中备受关注的问题。优点：半监督学习（Semi-supervisedLearning）能够充分利用大量的未标记样本来改善分类器的性能，是目前利用未标记样本进行学习的主流技术。半监督学习背景在进行Web网页推荐时，需要用户标记出哪些网页是他感兴趣的，很少会有用户愿意花大量的时间来提供标记，因此有标记的网页示例比较少，但Web上存在着无数的网页，它们都可作为未标记示例来使用。这类问题直接来自于实际应用：例如，大量医学影像，医生把每张片子上的每个病例都标出来再进行学习，是不可能的，能否只标一部分，并且还能利用未标的部分？半监督学习的应用领域半监督学习的主要方法生成模型（GenerativeModel）图基方法(graph-basedmethods)转导支持向量机（TransductiveSupportVectorMachines）生成模型（GenerativeModel)概述：样本数据分为标记样本和未标记样本，按照统计的观点，对于每一个样本的产生，其背后都有一个模型，即样本生成模型（generativemodels）。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。生成模型（GenerativeModel)中目前最流行的方法是期望最大化（EM）算法，期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。是最早的半监督学习方法。EM算法描述9EM是一种聚类算法聚类：将数据集中的数据分成若干类（簇），使类内相似度尽可能大，类间相似度尽可能小EM算法是基于模型的聚类方法，假设样本分布符合高斯混合模型，算法目的是确定各个高斯部件的参数，充分拟合给定数据，并得到一个模糊聚类，即每个样本以不同概率属于每个高斯分布，概率数值将由以上各个参数计算得到。极大似然估计(MLE)10独立同分布(IID)的数据其概率密度函数为似然函数定义为log似然函数定义为的极大似然估计为),,,(21nXXX)|(xfniiXffL1)|()|()|()|(log)|(Ll)|(maxarg)|(maxarg^lL极大似然估计(MLE)11如求正态分布均值和方差的MLE：EM问题描述高斯混合模型被定义为M个高斯密度函数的线性组合：其中为均值为，协方差为的高斯分布，是混合参数，看做第i个高斯分布的权重，表征先验概率。且(;,)iiiNx1()(;,)MiiiiiPxNxiii111Miii且0EM问题描述的概率密度函数为参数估计的最常用方法是最大似然估计，通过使似然函数达到最大值得到参数的估计值。将高斯混合密度函数中所有待定的参数记为，则似然函数为：/21/2111()exp()()2(2)diTiiiiNxxx(;,)iiiNx1(|)(|)argmax(|)NiiPXPxPXEM问题描述为了使问题简化，我们求的最大值。这里由于有和的对数，求导后形式复杂，因此不能使用一般的求偏导并令导数为零的方法。111log((|))log(|)log((;,))NNKikikkiikpXpxNxEM算法原理简化的问题：某混合高斯分布一共有k个分布，并且对于每一个观察到的x，如果我们同时还知道它是属于k中哪一个分布的，则求各个参数并不是件难事。比如用z来表示每一个高斯分布，那么我们的观察集不仅仅是{x1,x2,x3…},而是{(x1,z2),(x2,z3),(x3,z1)…}而现实往往是：我们不知道每个x属于哪个分布，也就是说z是我们观察不到的，z是隐藏变量。EM算法原理假定可以观察到Z，问题变为求下式最大值但是Z是观察不到的，因此EM算法假设Z的分布依据上一轮的估计参数确定，求取上式期望的最大值。定义：11(,|)log(,|)log((;,))iiNNiiiizziiPXZpxzNx(,)[log(,Z|)|X,]oldoldzQEpX111(,)[log(,Z|)|X,]log(,|)(|,)log(,Z|)(|,)log((;,))(|,)log((;,))(|,)...log((;,oldoldzoldzoldzNoldziiziziziNNoldziizizijjzijziiziQEpXpXZfZXdZpXpZXpxpZXpxpzxpx1121111111111))(|,)log((;,))(|,)log()(|,)log((;,))(|,)NMMMNoldzijjzzZnijMNoldkkikkikiMNMNoldoldkikikkikikipzxpxpkxpkxpxpkx对上式使用拉格朗日乘数法可得求偏导并令值为零分别得：11(|,)NnewoldkiipkxN11(|,)(|,)NoldiinewikNoldiixpkxpkx11(|,)()()(|,)NoldnewnewTiikiknewikNoldiipkxxxpkx其中，可由下式求得。(1)(|,)iipkx11(,|)(|,)(|)(|)(|,)(|)(|,)(|,)(|,)oldoldiioldioldoldiMoldoldiloldoldoldkikkMoldoldoldlilllpkxpkxpxpkpxkplpxlNxNx抛硬币实例20抛硬币实例21EM—Expectation22观测数据X已知，参数的当前值已知，在完整似然函数中，缺失数据(隐含变量)Y未知，完整log似然函数对Y求期望。定义其中是待确定的参数通过求期望，去掉了完整似然函数中的变量Y。即EM的E步。tEM—Maximization23对E步计算得到的完整似然函数的期望求极大值（EM的M步），得到参数新的估计值，即每次参数更新会增加非完整似然值反复迭代后，会收敛到似然的局部最大值EM的收敛性24其中，当Q取极大值时，观测数据的似然也在相同点取极大值EM算法会收敛到似然的局部极大值),(),(),()|()|(111ttttttttDQQllytttttdyyfyfyfD0),|(),|(),|(log),(11)|(),|()),|(log(),|())|(),|(log(),|()),|(log(],|),|([log),(ldyyfyfdyyffyfdyyfyLLQtytytyttEM算法缺点1）EM算法比K-means算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means算法计算结果稳定、准确。2）需要已知样本聚类数目3）对初值敏感4）爬山技术，局部最优解5）对孤立点敏感，有噪音时效果差生成模型中的EM算法假设我们有两种类型的数据集：2612,1,2...,(;,),,[,,...,]luiTMuNxRipxPPPPPD这个数据集由个样本构成我们假设这些数据是相互独立、并且按照相同概率分配给随机向未标注数量，这些向量来自边缘分布它也受等参据：数的限定，由定义相应集合。1,2,...,,=,1,2,...,,1,2,...,{,1,2,...,,1,2,...,}lylyiyyliyyNNyyMNyNziNyMyiDiNyM假设样本独立、随机生成，后随由专家标注。让其中的个样本归于类，其中。我们用符号表示第类的第个样本，标注的标注数据样：本集用表示。27生成模型中的EM算法1111112111221:()(;)(|;)!:()(,|;)!!...!!((|;))!!...!E(;())(|;())((|;,)))uuuuNNMuuiyiiiyNMllliyyiMNMlyiyyiMMiiyyyyDLInpxInPpxyNDLInpyzyInNNNNInppzyInNNNQtpyxtInpxyP步骤：121((|;,))ulNiNiyyyyiInpzyP2.图基方法定义：通过相似度度量将标记和未标记数据放在联系起来的图当中。实际当中，很多图基方法就是基于图估计一个函数这个函数需满足下面两个前提假设。对于已标记样本点，尽可能的接近标记，表现为在损失函数(lossfunction)的选择。在整个图上函数要比较平缓，表现为正交器regularizer。适用：具有相似特征的点往往被分在同一类当中Lyff特点：不同的图基方法大体上都差不多，只不过是损失函数和正规则器的选择不同而已，其关键是要构建一个好的图。优点：物理原理能够很好的解释。缺点：目前对于图的构建研究还不是很深入。2.1图基方法背景：TSVM是为了改进SVM在文本分类中本已出色的表现而做的更一步改进.使用SVM进行文本分类一个问题是难于建造出那么多的标记文档，要么是可用的训练数据本身就少，或者是用人工方法把无标记的文档分类为有标记的文档所花费的功夫无法承受。这样就引出了TSVM。定义：是标准SVM在半监督学习当中的拓展，是通过加入约束项使得未标记数据落在Margin之外，即使得分类的超平面避开数据密度高的区域。这里的未标记样本的特点就是使得决策面避开样本的密集区。优点：考虑无标签样本对分类器的影响，并且结合SVM算法实现的一种高效的分类算法。适用：能够用SVM的地方，自然想到用转导支持向量机能够获得更好的效果缺点：时间复杂度比较高，需要预先设置正负比例等的不足。3转导支持向量机（TSVM）返回半监督学习的不足通过半监督学习利用未标记示例后，有时不仅不能提高泛化能力，反而会使得性能下降。在模型假设不符合真实情况或者未标记示例的分布与有标记示例的分布有较大差异时，进行半监督学习有可能导致性能下降。另一方面，随着训练不断进行，自动标记的示例中的噪音会不断积累，其负作用会越来越大。谢谢！