目录
一、半监督学习简介
二、生成式方法
三、半监督SVM
四、图半监督学习
五、基于分歧的方法
六、半监督聚类
本章假设给定有标记样本集和未标记样本集,。
一、半监督学习简介
定义:让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能,就是半监督学习。P294
要学习半监督学习,首先我们要了解未标记样本。
形式化地看我们有训练样本集,这l个的类别标记(即是否好瓜)已知,称为“有标记样本”;此外,还有,,这u个样本的类别标记未知(即不知是否有好瓜),称为“未标记”样本。半监督学习就是将这些未标记样本在构建模型的过程中利用起来。
此外半监督学习有多种形式:聚类假设与流形假设、纯半监督学习与直推学习、主动学习。
聚类假设与流形假设
事实上,未标记样本虽未直接包含标记信息,但若它们与有标记样本是从同样的数据源独立同分布采样而来,则它们所包含的关于数据分布的信息对建立模型将大有裨益.图13.1(P294)给出了一一个直观的例示.若仅基于图中的一一个正例和一个反例,则由于待判别样本恰位于两者正中间,大体上只能随机猜测;若能观察到图中的未标记样本,则将很有把握地判别为正例。
很明显,依赖未标记样本点的分布可以更有把握地判断正反例。同时这也是一种常见的利用未标记样本的方法:“聚类假设”,即假设数据存在簇结构,同一个簇的样本属于同一个类别,图13.1可以清晰地向我们展示。
流形假设即假设数据分布在一个流形的结构上,邻近的样本拥有相似的输出值。“邻近” 程度常用“相似”程度来刻画,因此,流形假设可看作聚类假设的推广,但流形假设对输出值没有限制,因此比聚类假设的适用范围更广,可用于更多类型的学习任务。
事实上,无论聚类假设还是流形假设,其本质都是“相似的样本拥有相似的输出”这个基本假设。
主动学习、纯半监督学习与直推学习
我们可以用先训练一个模型,拿这个模型去地里挑一个样本,查询正反例,然后把这个新获得的有标记样本加入中重新训练一个模型,再去挑样本...这样,若每次都挑出对改善模型性能帮助大的样本,则只需查询比较少的样本就能构建出比较强的模型,从而大幅降低标记成本.这样的学习方式称为“主动学习”。
纯半监督学习与直推学习前者假定训练数据中的未标记样本并非待预测的数据,而后者则假定学习过程中所考虑的未标记样本恰是待预测数据,学习的目的就是在这些未标记样本上获得最优泛化性能。
图13.2(P295)直观地显示出主动学习、纯半监督学习、直推学习的区别。
二、生成式方法
生成式方法定义
生成式方法是直接基于生成式模型的方法.此类方法假设所有数据(无论是否有标记)都是由同一一个潜在的模型“生成”的.这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来,而未标记数据的标记则可看作模型的缺失参数,通常可基于EM算法进行极大似然估计求解。
优点
方法简单,易于实现,在有标记数据极少的情形下往往比其他方法性能更好。
缺点
此类方法有一个关键:模型假设必须准确,即假设的生成式模型必须与真实数据分布吻合;否则利用未标记数据反倒会降低泛化性能。遗憾的是,在现实任务中往往很难事先做出准确的模型假设,除非拥有充分可靠的领域知识。
生成式方法生成模型高斯混合模型
数据样本是基于如下概率密度生成的:(13.1)P296
又由最大化后验概率可知:
(13.2)P296
不难发现,式(13.2)中估计需知道样本的标记,因此仅能使用有标记数据;而不涉及样本标记,因此有标记和未标记数据均可利用,通过引入大量的未标记数据,对这项的估计可望由于数据量的增长而更为准确,于是式(13.2)整体的估计可能会更准确。由此可清楚地看出未标记数据何以能辅助提高分类模型的性能。
高斯混合模型参数估计
高斯混合模型的参数有三个:。
用极大似然法来估计高斯混合模型的参数的 对数似然是:(13.4)P297
可见式中有基于有标记样本的有监督项和基于未标记样本的无监督项,因此可用EM算法求解:
E步:
M步:
以上过程不断迭代直至收敛,获得模型参数,然后代入式(13.3)和(13.2)以进行样本分类。
三、半监督SVM
半监督SVM定义
半监督支持向量机, 简称S3VM,是支持向量机在半监督学习上的推广,在不考虑未标记样时,支持向量机试图找到最大间隔划分超平面,而在考虑未标记样本后,S3VM试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面。书上的图13.3(P298)可以说是十分形象地表示了出来。
TSVM
定义:半监督支持向量机中最著名的是TSVM 。TSVM试图考虑对未标记样本进行各种可能的标记指派,即尝试将每个未标记样本分别作为正例或反例,然后在所有这些结果中,寻求一个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上间隔最大化的划分超平面,一旦划分超平面得以确定,未标记样本的最终标记指派就是其预测结果。
TSVM的学习目标是为中的样本给出预测标记,使得:
TSVM的算法描述如图13.4(P300):
TSVM采用局部搜索来迭代地寻找式(13.9)的近似解。
具体来说,
1、它先利用有标记样本学得一个SVM,然后,利用这个SVM对未标记数据进行标记指派,即将SVM预测的结果作为“伪标记”赋予未标记样本。
2、此时成为已知,将其代入式(13.9)即得到一个标准SVM问题,于是可求解出新的划分超平面和松弛向量;注意到此时未标记样本的伪标记很可能不准确,因此要设置为比小的值,使有标记样本所起作用更大。
3、接下来, TSVM找出两个标记指派为异类且很可能发生错误的未标记样本,交换它们的标记,再重新基于式(13.9)求解出更新后的划分超平面和松弛向量。
4、然后再找出两个标记指派为异类且很可能发生错误的未标记样本, ....标记指派调整完成后,逐渐增大以提高未标记样本对优化目标的影响,进行下一轮标记指派调整,直至 = 为止。
5、此时求解得到的SVM不仅给未标记样本提供了标记,还能对训练过程中未见的示例进行预测。
缺点
搜寻标记指派可能出错的每一对未标记样本进行调整,是一个涉及巨大计算开销的大规模优化问题。因此,半监督SVM研究的一个重点是如何设计出高效的优化求解策略,由此发展出很多方法。
四、图半监督学习
图半监督学习定义
给定一个数据集,我们可将其映射为-一个图,数据集中每个样本对应于图中一个结点,若两个样本之间的相似度很高(或相关性很强),则对应的结点之间存在一条边,边的“强度”正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色,而未标记样本所对应的结点尚未染色。于是,半监督学习就对应于“颜色”在图上扩散或传播的过程。
优点
图半监督学习方法在概念上相当清晰,且易于通过对所涉矩阵运算的分析来探索算法性质。
缺点
1、存储开销,若样本数为,则算法中所涉及的矩阵规模为,这使得此类算法很难直接处理大规模数据;
2、由于构图过程仅能考虑训练样本集,难以判知新样本在图中的位置,因此,在接收到新样本时,或是将其加入原数据集对图进行重构并重新进行标记传播,或是需引入额外的预测机制。
针对二分类问题的标记传播方法
基于有标记样本和未标记样本的并集构建一个图,常基于高斯函数定义为:
假定从图中学得一个实值函数:,然后可定义关于此实值函数的“能量函数”:
利用此函数可以求得实值函数在有标记样本和未标记样本上的预测结果,
采用分块矩阵表示方式:,,公示经过运算可
重写为:(式13.15)P302,
令,则式13.15可重写为式13.17:
于是将上的标记信息作为带入式13.17,即可利用求得的对未标记样本进行预测。
适用于多分类问题的标记传播方法
继承二分类问题标记传播的图,定义一个非负标记矩阵,将其初始化:
有迭代计算式:,
迭代至收敛可得:,
由可得未标记样本中的样本标记。
算法描述如图13.5(P303):
五、基于分歧的方法
多视图数据
每个属性集可看作一个视图。对一部电影来说图像画面、声音信息、字幕等等都是一个属性集对应一个视图,暂且仅考虑图像画面属性集所构成的视图和声音属性集所构成的视图。于是,一个电影片段可表示为样本,其中是样本在视图i中的示例,即基于该视图属性描述而得的属性向量,不妨假定为图像视图中的属性同量,为声音视图中的属性向量;是标记,假定是电影的类型,例如“动作片”、“爱情片” 等。 这样的数据就是多视图数据。
相容互补性
仍以电影为例,某个片段上有两人对视,仅凭图像画面信息难以分辨其类型,但此时若从声音信息听到“我爱你”,则可判断出该片段很可能属于“爱情片”;另一方面,若仅凭图像画面信息认为“可能是动作片”,仅凭声音信息也认为“可能是动作片”,则当两者一起考虑时就有很大的把握判别为“动作片”。显然,在“相容性”基础上,不同视图信息的“互补性”会给学习器的构建带来很多便利。
协同训练
协同训练正是很好地利用了多视图的“相容互补性”。
可用一个简单的办法来利用未标记数据:
首先在每个视图上基于有标记样本分别训练出一个分类器;
然后让每个分类器分别去挑选自己“最有把握的”未标记样本赋予伪标记,并将伪标记样本提供给另-一个分类器作为新增的有标记样本用于训练更新....
这个“互相学习、共同进步”的过程不断迭代进行,直到两个分类器都不再发生变化,或达到预先设定的迭代轮数为止。
算法描述如图13.6(P306):
优点
[1] 即便在更弱的条件下,协同训练以然可以有效地提升弱分类器的性能。
[2] 基于分歧的方法只需采用合适的基学习器,就能较少受到模型假设、损失函数非凸性和数据规模问题的影响,学习方法简单有效、理论基础相对坚实、适用范围较为广泛。
缺点
为了使用此类方法,需能生成具有显著分歧、性能尚可的多个学习器,但当有标记样本很少,尤其是数据不具有多视图时,要做到这一点并不容易,需有巧妙的设计。
六 半监督聚类
作用
聚类是一种典型的无监督学习任务,然而在现实聚类任务中我们往往能获得一些额外的监督信息, 于是可通过半监督聚类来利用监督信息以获得更好的聚类效果。
两种监督信息
聚类任务中获得的监督信息大致有两种类型.第一种类型是“必连”与“勿连”约束,前者是指样本必属于同一个簇,后者是指样本必不属于同一个簇;第二种类型的监督信息则是少量的有标记样本.
约束均值算法
约束均值算法是利用第一类监督信息(即“必连”和“勿连”)的代表。算法描述如图13.7(P307):
约束种子均值算法
利用少量有标记样本:
直接将它们作为“种子”,用它们初始化均值算法的个聚类中心,并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系.这样就得到了约束种子均值算法。
其算法描述如图13.9(P309):