搜索
陈加略第十三章：半监督学习背景（半监督学习）隔壁老王品瓜师吃背景（半监督学习）品瓜师吃模型有标记样本无标记样本直推学习（纯）半监督学习待测数据背景（主动学习）品瓜师吃背景（主动学习）品瓜师吃主动学习待测数据模型有标记样本无标记样本标注者未标记样本的效用未标记样本的假设要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设，其中有两种常见的假设。聚类假设（clusteringassumption）：假设数据存在簇结构，同一簇的样本属于同一类别。流形假设（manifoldassumption）：假设数据分布在一个流形结构上，邻近的样本具有相似的输出值。流形假设可看做聚类假设的推广大纲未标记样本生成式方法半监督SVM图半监督学习基于分歧的方法半监督聚类生成式方法假设样本由这个假设意味着混合成分高斯混合模型生成,且每个类别对应一个高斯混合成分：其中,生成式方法由最大化后验概率可知：生成式方法假设样本独立同分布，且由同一个高斯混合模型生成，则对数似然函数是：生成式方法高斯混合的参数估计可以采用EM算法求解，迭代更新式如下：E步：根据当前模型参数计算未标记样本属于各高斯混合成分的概率。生成式方法M步：基于更新模型参数生成式方法将上述过程中的高斯混合模型换成混合专家模型，朴素贝叶斯模型等即可推导出其他的生成式半监督学习算法。此类方法简单、易于实现,在有标记数据极少的情形下往往比其他方法性能更好。然而,此类方法有一个关键:模型假设必须准确,即假设的生成式模型必须与真实数据分布吻合;否则利用未标记数据反而会显著降低泛化性能。大纲未标记样本生成式方法半监督SVM图半监督学习基于分歧的方法半监督聚类半监督SVM半监督SVM半监督支持向量机中最著名的是TSVM(TransductiveSupportVectorMachine)半监督SVMTSVM采用局部搜索来迭代地寻找近似解.无标记样本有标记样本SVM0伪标记SVM1训练训练训练标注半监督SVMSVM1无标记样本搜索指派可能出错的样本交换样本标记有标记样本训练训练SVM2半监督SVM未标记样本的伪标记不准确半监督SVM未标记样本进行标记指派及调整的过程中,有可能出现类别不平衡问题,即某类的样本远多于另一类。为了减轻类别不平衡性所造成的不利影响,可对算法稍加改进:将优化目标中的项拆分为与两项,并在初始化时令：半监督SVM显然,搜寻标记指派可能出错的每一对未标记样本进行调整,仍是一个涉及巨大计算开销的大规模优化问题。因此,半监督SVM研究的一个重点是如何设计出高效的优化求解策略。例如基于图核(graphkernel)函数梯度下降的LaplacianSVM[ChapelleandZien,2005]、基于标记均值估计的meanS3VM[Lietal.,2009]等.大纲未标记样本生成式方法半监督SVM图半监督学习基于分歧的方法半监督聚类图半监督学习给定一个数据集,我们可将其映射为一个图,数据集中每个样本对应于图中一个结点,若两个样本之间的相似度很高(或相关性很强),则对应的结点之间存在一条边,边的“强度”(strength)正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色,而未标记样本所对应的结点则尚未染色.于是,半监督学习就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵,这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。图半监督学习我们先基于构建一个图，其中结点集边集E可表示为一个亲和矩阵(affinitymatrix),常基于高斯函数定义为:图半监督学习假定从图将学得一个实值函数。直观上讲相似的样本应具有相似的标记,即得到最优结果于是可定义关于f的“能量函数”(energyfunction)[Zhuetal.,2003]:图半监督学习采用分块矩阵表示方式:由可得:图半监督学习图半监督学习上面描述的是一个针对二分类问题的“单步式”标记传播(labelpropagation)方法,下面我们来看一个适用于多分类问题的“迭代式”标记传播方法[Zhouetal.,2004].仍基于构建一个图其中结点集定义一个的非负标记矩阵，其第i行元素为示例的标记向量,相应的分类规则为:将F初始化为：图半监督学习基于W构造一个标记传播矩阵，其中,于是有迭代计算式:基于迭代至收敛可得:图半监督学习事实上,算法对应于正则化框架[Zhouetal.,2004]:当时,最优解恰为迭代算法的收敛解。图半监督学习图半监督学习图半监督学习方法在概念上相当清晰,且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显.首先是在存储开销高。另一方面,由于构图过程仅能考虑训练样本集,难以判知新样本在图中的位置,因此,在接收到新样本时,或是将其加入原数据集对图进行重构并重新进行标记传播,或是需引入额外的预测机制。大纲未标记样本生成式方法半监督SVM图半监督学习基于分歧的方法半监督聚类基于分歧的方法基于分歧的方法(disagreement-basedmethods)使用多学习器,而学disagreement亦称diversity习器之间的“分歧”(disagreement)对未标记数据的利用至关重要。协同训练(co-training)[BlumandMitchell,1998]是基于分歧的方法的重要代表,它最初是针对“多视图”(multi-view)数据设计的,因此也被看作“多视图学习”(multi-viewlearning)的代表.基于分歧的方法网页分类任务中的双视图图片视图文字视图基于分歧的方法协同训练正是很好地利用了多视图的“相容互补性”.假设数据拥有两个“充分”(sufficient)且“条件独立”视图。视图1视图2模型1模型2最确信样本最确信样本基于分歧的方法基于分歧的方法协同训练过程虽简单,但令人惊讶的是,理论证明显示出,若两个视图充分且条件独立,则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高[BlumandMitchell,1998].不过,视图的条件独立性在现实任务中通常很难满足,不会是条件独立的因此性能提升幅度不会那么大,但研究表明,即使在更弱的条件下,协同训练仍可有效地提升弱分类器的性能[周志华,2013].基于分歧的方法协同训练算法本身是为多视图数据而设计的,性集合的常见数据但此后出现了一些能在单视图数据上使用的变体算法。它们或是使用不同的学习算法[GoldmanandZhou,2000]、或使用不同的数据采样[ZhouandLi,2005b]、甚至使用不同的参数设置[ZhouandLi,2005a]来产生不同的学习器,也能有效地利用未标记数据来提升性能。后续理论研究发现,此类算法事实上无需数据拥有多视图,仅需弱学习器之间具有显著的分歧(或差异),即可通过相互提供伪标记样本的方式来提高泛化性能[周志华,2013]。基于分歧的方法基于分歧的方法只需采用合适的基学习器,就较少受到模型假设、损失函数非凸性和数据规模问题的影响,学习方法简单有效、理论基础相对坚实、适用范围较为广泛。为了使用此类方法,需能生成具有显著分歧、性能尚可的多个学习器,但当有标记样本很少、尤其是数据不具有多视图时,要做到这一点并不容易。大纲未标记样本生成式方法半监督SVM图半监督学习基于分歧的方法半监督聚类半监督聚类聚类是一种典型的无监督学习任务,然而在现实聚类任务中我们往往能获得一些额外的监督信息,于是可通过“半监督聚类”(semi-supervisedclustering)来利用监督信息以获得更好的聚类效果.聚类任务中获得的监督信息大致有两种类型：第一种类型是“必连”(must-link)与“勿连”(cannot-link)约束，前者是指样本必属于同一个簇,后者则是指样本必不属于同一个簇；第二种类型的监督信息则是少量的有标记样本.半监督聚类约束k均值(Constrainedk-means)算法[Wagstaffetal.,2001]是利用第一类监督信息的代表。该算法是k均值算法的扩展,它在聚类过程中要确保“必连”关系集合与“勿连”关系集合中的约束得以满足,否则将返回错误提示。半监督聚类不冲突，选择最近的簇冲突，尝试次近的簇半监督聚类半监督聚类第二种监督信息是少量有标记样本。即假设少量有标记样本属于k个聚类簇。这样的监督信息利用起来很容易:直接将它们作为“种子”,用它们初始化k均值算法的k个聚类中心,并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系.这样就得到了约束种子k均值(ConstrainedSeedk-means)算法[Basuetal.,2002]。半监督聚类半监督聚类阅读材料半监督学习的研究一般认为始于[ShahshahaniandLandgrebe,1994],该领域在上世纪末、本世纪初蓬勃发展.国际机器学习大会(ICML)从2008年开始评选“十年最佳论文”,在短短6年中,半监督学习四大范型(paradim)中基于分歧的方法、半监督SVM、图半监督学习的代表性工作先后于2008年[BlumandMitchell,1998]、2009年[Joachims,1999]、2013年[Zhuetal.,2003]获奖.半监督学习在利用未标记样本后并非必然提升泛化性能,在有些情形下甚至会导致性能下降.对生成式方法,其成因被认为是模型假设不准确[CozmanandCohen,2002],因此需依赖充分可靠的领域知识来设计模型.对半监督SVM,其成因被认为是训练数据中存在多个“低密度划分”,而学习算法有可能做出不利的选择;S4VM[LiandZhou,2015]通过优化最坏情形性能来综“安全”指利用未标记数合利用多个低密度划分,提升了此类技术的安全性.据之后,确保泛化性能至少不差于仅利用有标记数据更一般的“安全”(safe)半监督学习仍是一个未决问题.阅读材料本章主要介绍了半监督分类和聚类,但半监督学习已普遍用于各类机器学习任务,例如在半监督回归[ZhouandLi,2005a]、降维[Zhangetal.,2007]等方面都有相关研究.更多关于半监督学习的内容可参见[Chapelleetal.,2006b,Zhu,2006],[周志华,2013,ZhouandLi,2010]则是关于基于分歧的方法的专门介绍.[Settles,2009]是一个关于主动学习的介绍.