【周志华机器学习】十三、半监督学习_constrained k-means

参考资料

1. Machine-learning-learning-notes
2. LeeML-Notes
3. ML-NLP

本博客是根据周志华的西瓜书和参考资料1、2、3所做的笔记，主要用于学习，非技术类博客，因此存在大量复制粘贴，请见谅。
如果本篇博客有后记部分，则该部分表示的是在书本原有的基础知识上，进行的知识点的扩充。

1. 未标记样本

1.1 主动学习

对于未标记样本，若直接丢弃掉无标记样本集，使用传统的监督学习方法，常常会由于训练样本的不充足，使得其刻画总体分布的能力减弱，从而影响了学习器泛化性能。

一种简单的做法是通过专家知识对这些未标记的样本进行打标，但随之而来的就是巨大的人力耗费。

若我们先使用有标记的样本数据集训练出一个学习器，再基于该学习器对未标记的样本进行预测，从中挑选出不确定性高或分类置信度低的样本来咨询专家并进行打标，最后使用扩充后的训练集重新训练学习器，这样便能大幅度降低标记成本，这便是主动学习（active learning），其目标是使用尽量少的查询（query）来获得尽量好的性能。

显然, 主动学习引入了额外的专家知识, 通过与外界的交互来将部分未标记样本转变为有标记样本 ,若不与专家交互, 没有获得额外信息, 还能利用未标记样本来提高泛化性能吗?

事实上,未标记样本虽未直接包含标记信息,但若它们与有标记样本是从同样的数据源独立同分布采样而来,则它们所包含的关于数据分布的信息对建立模型将大有裨益, 图13.1给出了一个直观的例示,若仅基于图中的一个正例和一个反例, 则由于待判别样本恰位于两者正中间,大体上只能随机猜测; 若能观察到图中的未标记样本, 则将很有把握地判别为正例。

让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能, 就是半监督学习(semi-supervised learning).

半监督学习的现实需求非常强烈, 因为在现实应用中往往能容易地收集到大量未标记样本, 而获取“标记”却需耗费人力、物力。

例如,在进行计算机辅助医学影像分析时, 可以从医院获得大量医学影像,但若希望医学专家把影像中的病灶全都标识出来则是不现实的,“有标记数据少,未标记数据多”这个现象在互联网应用中更明显,例如在进行网页推荐时需请用户标记出感兴趣的网页,但很少有用户愿花很多时间来提供标记,因此,有标记网页样本少,但互联网上存在无数网页可作为未标记样本来使用.

半监督学习恰是提供了一条利用“廉价”的未标记样本的途径。

1.2 常见假设

要利用未标记样本,必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设,最常见的是“聚类假设”(cluster assumption),即假设数据存在簇结构,同一个簇的样本属于同一个类别。

图13.1就是基于聚类假设来利用未标记样本,由于待预测样本与正例样本通过未标记样本的“撮合”聚在一起,与相对分离的反例样本相比,待判别样本更可能属于正类。

半监督学习中另一种常见的假设是“流形假设” (manifold assumption),即假设数据分布在一个流形结构上,邻近的样本拥有相似的输出值.

“邻近”程度常用“相似”程度来刻画,因此,流形假设可看作聚类假设的推广,但流形假设对输出值没有限制,因此比聚类假设的适用范围更广,可用于更多类型的学习任务,事实上,无论聚类假设还是流形假设,其本质都是“相似的样本拥有相似的输出”这个基本假设.

1.3 半监督学习划分

半监督学习可进一步划分为纯(pure)半监督学习和直推学习(transductive learning),。

纯半监督学习假定训练数据中的未标记样本并非待预测的数据；是基于“开放世界”假设,希望学得模型能适用于训练过程中未观察到的数据;

直推学习则假定学习过程中所考虑的未标记样本恰是待预测数据,学习的目的就是在这些未标记样本上获得最优泛化性能，是基于“封闭世界”假设,仅试图对学习过程中观察到的未标记数据进行预测.

图13.2直观地显示出主动学习、纯半监督学习、直推学习的区别,需注意的是,纯半监督学习和直推学习常合称为半监督学习,

2. 生成式方法

生成式方法(generative methods)是直接基于生成式模型的方法,此类方法假设所有数据(无论是否有标记)都是由同一个潜在的模型“生成”的,这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来,而未标记数据的标记则可看作模型的缺失参数,通常可基于EM算法进行极大似然估计求解.

此类方法的区别主要在于生成式模型的假设,不同的模型假设将产生不同的方法。

当参数迭代更新收敛后，对于待预测样本x，便可以像贝叶斯分类器那样计算出样本属于每个类簇的后验概率，接着找出概率最大的即可：

可以看出：基于生成式模型的方法十分依赖于对潜在数据分布的假设，即假设的分布要能和真实分布相吻合，否则利用未标记的样本数据反倒会在错误的道路上渐行渐远，从而降低学习器的泛化性能。

基于半监督的高斯混合模型有机地整合了贝叶斯分类器与高斯混合聚类的核心思想，有效地利用了未标记样本数据隐含的分布信息，从而使得参数的估计更加准确。

3. 半监督SVM

监督学习中的SVM试图找到一个划分超平面，使得两侧支持向量之间的间隔最大，即“最大划分间隔”思想。

半监督支持向量机(Semi-Supervised Support Vector Machine,简称S3VM)是支持向量机在半监督学习上的推广。

在不考虑未标记样本时,支持向量机试图找到最大间隔划分超平面,而在考虑未标记样本后,S3VM试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面,如图13.3所示,这里的基本假设是“低密度分隔”(low-density separation),显然,这是聚类假设在考虑了线性超平面划分后的推广。

TSVM (Transductive Support Vector Machine)与标准 SVM一样, TSVM是半监督支持向量机中的最著名代表，其核心思想是：尝试为未标记样本找到合适的标记指派，使得超平面划分后的间隔最大化。TSVM采用局部搜索的策略来进行迭代求解，即首先使用有标记样本集训练出一个初始SVM，接着使用该学习器对未标记样本进行打标，这样所有样本都有了标记，并基于这些有标记的样本重新训练SVM，之后再寻找易出错样本不断调整。

整个算法流程如下所示：

4. 基于分歧的方法

基于分歧的方法通过多个学习器之间的**分歧（disagreement）/多样性（diversity）**来利用未标记样本数据，协同训练就是其中的一种经典方法。协同训练最初是针对于多视图（multi-view）数据而设计的，多视图数据指的是样本对象具有多个属性集，每个属性集则对应一个视图。例如：电影数据中就包含画面类属性和声音类属性，这样画面类属性的集合就对应着一个视图。首先引入两个关于视图的重要性质：

相容性：使用单个视图数据训练出的学习器的输出空间是一致的。例如都是{好，坏}、{+1,-1}等。
互补性：不同视图所提供的信息是互补/相辅相成的，实质上这里体现的就是集成学习的思想。

协同训练正是很好地利用了多视图数据的“相容互补性”，其基本的思想是：首先在每个视图上基于有标记样本分别训练一个初始分类器，然后让每个分类器去挑选分类置信度最高的未标记样本并赋予标记，并将带有伪标记的样本数据传给另一个分类器作为新增的有标记样本用于训练更新，这个“互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或达到预先设定的轮数为止。

算法过程如下：

基于分歧的方法只需采用合适的基学习器,就能较少受到模型假设、损失函数非凸性和数据规模问题的影响,学习方法简单有效、理论基础相对坚实、适用范围较为广泛,为了使用此类方法,需能生成具有显著分歧、性能尚可的多个学习器,但当有标记样本很少,尤其是数据不具有多视图时,要做到这一点并不容易,需有巧妙的设计.

5. 半监督聚类

前面提到的几种方法都是借助无标记样本数据来辅助监督学习的训练过程，从而使得学习更加充分/泛化性能得到提升；半监督聚类则是借助已有的监督信息来辅助聚类的过程。一般而言，监督信息大致有两种类型：

必连与勿连约束：必连指的是两个样本必属于同一个类簇，勿连则是必不属于同一个类簇。
标记信息：少量的样本带有真实的标记。

5.1 Constrained k-means

约束k均值(Constrained k-means) 算法是利用第一类监督信息的代表。给定样本集$D=[x_1,x_2,...,x_m]$以及“必连”关系集合M和“勿连”关系集合C, $(x_i,x_j)\in M$表示$x_i,x_j$必属于同簇; $(x_i,x_j)\in C$表示$x_i,x_j$必不属于同簇。该算法是k均值算法的扩展,它在聚类过程中要确保M与C中的约束得以满足,否则将返回错误提示,算法如图所示.

5.2 少量有标记样本