《机器学习》-- 第十三章 半监督学习
前文推送
本文目录：
- 13.1 半监督学习
- 13.2 生成式方法
- 13.3 半监督SVM
- 13.4 图半监督学习
- 13.5 基于分歧的方法
- 13.6 半监督聚类
第十三章 半监督学习
13.1 半监督学习定义
监督学习指的是训练样本包含标记信息的学习任务，例如：常见的分类与回归算法；无监督学习则是训练样本不包含标记信息的学习任务，例如：聚类算法。在实际生活中，常常会出现一部分样本有标记 (labeled) 和较多(通常认为远多于)样本无标记 (unlabeled) 的情形，例如：做网页推荐时需要让用户标记出感兴趣的网页，但是少有用户愿意花时间来提供标记。若直接丢弃掉无标记样本集，使用传统的监督学习方法，常常会由于训练样本的不充足，使得其刻画总体分布的能力减弱，从而影响了学习器泛化性能。
一种简单的做法是先使用有标记的样本数据集训练出一个学习器，再基于该学习器对未标记的样本进行预测，并且问询专家知识对结果检验，最终达到改善模型性能，大幅降低标记成本，这便是 主动学习（active learning），其目标是 使用尽量少的/有价值的咨询来获得更好的性能。显然，主动学习需要与外界进行交互/查询/打标，引入了额外的专家知识，其本质上仍然属于一种监督学习。
假如，无标记样本与有标记样本是从同一个总体中独立同分布采样得到，那么 它们所包含的数据分布信息对学习器的训练大有裨益。要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设。最常见的是“聚类假设”( cluster assumption)，即假设数据存在簇结构,同一个簇的样本属于同一个类别；另一种常见的假设是“流形假设”( manifold assumption)， 假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。“邻近”程度常用“相似”程度来刻画，流形假设可看作聚类假设的推广，但流形假设对输出值没有限制，因此比聚类假设的适用范围更广，可用于更多类型的学习任务。
无论聚类假设还是流形假设，其本质都是“相似的样本拥有相似的输出”这个基本假设。
让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习(semi- supervised learning)。半监督学习还可以进一步划分为 纯(pure)半监督学习 和 直推学习(transductive learning)，两者的区别在于：前者假定训练数据集中的未标记数据并非待预测数据，而后者假定学习过程中的未标记数据就是待预测数据。
semi-supervised-learning
半监督学习的现实需求非常强烈，因为在现实应用中往往能容易地收集到大量未标记样本，而获取“标记”却需耗费人力、物力。例如，在进行计算机辅助医学影像分析时，可以从医院获得大量医学影像，但若希望医学专家把影像中的病灶全都标识出来则是不现实的。
“有标记数据少，未标记数据多”这个现象在互联网应用中更明显，例如在进行网页推荐时需请用户标记出感兴趣的网页，但很少有用户愿花很多时间来提供标记，因此，有标记网页样本少，但互联网上存在无数网页可作为未标记样本来使用。半监督学习恰是提供了一条利用“廉价”的未标记样本的途径。
13.2 生成式方法
生成式方法（generative methods）是基于生成式模型的方法，假设所有数据(无论是否有标记)都是由同一个潜在的模型“生成”的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，未标记数据的标记可看作模型的缺失参数，通常可基于EM算法进行极大似然求解。
此类方法的区别主要在于生成式模型的假设，不同的模型假设产生不同的方法。依赖于对潜在数据分布的假设，即假设的分布要能和真实分布相吻合，否则利用未标记的样本数据反而会降低学习器的泛化性能。需要极强的领域知识。
即先对联合分布 建模，从而进一步求解 ，此类方法假定样本数据服从一个潜在的分布，因此需要充分可靠的先验知识。例如：前面已经接触到的贝叶斯分类器与高斯混合聚类，都属于生成式模型。现假定总体是一个高斯混合分布，即由多个高斯分布组合形成，从而一个子高斯分布就代表一个类簇（类别）。
给定样本 , 其真实类别标记 , 其中 为所有可能的类别(即假设子簇与类别一一对应，各子簇对应一个分布)。高斯混合分布的概率密度函数如下所示：
其中，， ， 是样本 属于第 个高斯混合成分的概率， 和 为高斯混合成分的参数。
与高斯混合聚类类似，这里的主要任务也是估计出各个高斯混合成分的参数以及混合系数，不同的是：对于有标记样本，不再是可能属于每一个类簇，而是只能属于真实类标对应的特定类簇。
直观上来看，基于半监督的高斯混合模型有机地整合了贝叶斯分类器与高斯混合聚类的核心思想，有效地利用了未标记样本数据隐含的分布信息，从而使得参数的估计更加准确。
同样地，这里也使用 EM 进行求解，首先对各个高斯混合成分的参数及混合系数进行随机初始化，最大化似然函数（即LL（D）分别对α、u和∑求偏导 ），对参数进行迭代更新。
其中， 为第 类有标记样本数量
当参数迭代更新收敛后，对于待预测样本 ，便可以像贝叶斯分类器那样计算出样本属于每个类簇的后验概率，接着找出概率最大的即可：
13.3 半监督SVM
监督学习中的SVM试图找到一个划分超平面，使得两侧支持向量之间的间隔最大，即 最大划分间隔 思想。对于半监督SVM (Semi-Supervised Support Vector Machine, S3VM) 则考虑超平面在能将两类标记样本分隔的同时，穿过数据低密度的区域。
S3VM存在假设 “低密度分隔”(low-density separation)，是聚类假设在考虑了线性超平面划分后的推广。
S3VM
TSVM(Transductive Support Vector Machine) 是半监督支持向量机中最著名的，针对二分类问题，TSVM尝试为未标记样本找到合适的标记指派(label assignment)，即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中，寻求一个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上间隔最大化的划分超平面。
未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解，TSVM采用局部搜索的策略来进行迭代求(近似)解。即首先使用有标记样本集训练出一个初始SVM，接着使用该学习器对未标记样本进行打标，这样所有样本都有了标记(伪标记，pseudo-label)，并基于这些有标记的样本重新训练SVM，之后再寻找易出错样本不断调整。
TSVM.png
13.4 图半监督学习
给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图结点，若两个样本之间的相似度很高(或相关性很强)，则对应的结点之间存在一条边，边的“强度”(strength) 正比于样本之间的相似度(或相关性)。
可将有标记样本所对应的结点想象为染过色，标记样本所对应的结点尚未染色。半监督学习就对应于“颜色”在图上扩散或传播的过程。由于个图对应了一个矩阵，我们就能基于矩阵运算来进行半监督学习算法的推导与分析。
graph-semi-supervised-learning
13.5 基于分歧的方法
基于分歧的方法 (disagreement-based methods) 通过多个学习器之间的 分歧（disagreement）/多样性（diversity） 来利用未标记样本数据。
协同训练(co-training)是重要代表，最初针对于多视图（multi-view）数据而设计（故也被看作 multi-view learing 的代表）。
多视图数据指的是样本对象具有多个属性集(attribute set)，每个属性集则对应一个视图(view)。例如：电影数据中就包含画面类属性集、声音类属性集、字幕信息的属性集等，每个属性集就对应着一个视图。
比如，一个电影片段可表示为样本 $(,y)，其中x^{i}是样本在视图i中的示例，即基于该视图属性描述而得的属性向量，假定x^{1}为图像视图中的属性向量，x^{2}为声音视图中的属性向量；y是标记，假定是电影的类型例如动作片、爱情片等。(,y)$ 这样的数据就是多视图数据。
视图有两个重要性质：
相容性(compatibility)：使用各个单个视图数据训练出的学习器的输出空间（label）是一致的。例如都是{好，坏}、{+1,-1}等。互补性(complementarity)：即不同视图所提供的信息是互补/相辅相成的，体现的就是集成学习的思想。
协同训练正是很好地利用了多视图数据的 相容互补性 ，即假设数据拥有两个 充分( sufficient) 且条件独立 视图，“充分”是指每个视图都包含足以产生最优学习器的信息，“条件独立”则是指在给定类别标记条件下两个视图独立。
基本流程：首先基于有标记样本数据在每个视图上都训练一个初始分类器，然后让每个分类器去挑选分类置信度最高的样本并赋予伪标记，并将带有伪标记的样本数据传给另一个分类器作为新增的有标记样本去学习，不断迭代，直到两个分类器都不再发生变化，或者达到预定的迭代轮数。
基于分歧的方法只需采用合适的基学习器（不同视图、不同算法、不同数据采样、不同参数设置等，都仅是产生差异的渠道，而非必备条件），就能较少受到模型假设、损失函数非凸性和数据规模问题的影响,学习方法简单有效、理论基础相对坚实适用范围较为广泛。
为了使用此类方法,需能生成具有显著分歧、性能尚可的多个学习器，但当有标记样本很少，尤其是数据不具有多视图时，要做到这 一点并不容易，需有巧妙的设计。
13.6 半监督聚类
半监督聚类(semi-supervised clustering) 借助已有的监督信息来辅助聚类，聚类任务中获得的监督信息大致有两种类型：
必连(must-link)与勿连约束(cannot-link)：必连指的是两个样本必须在同一个类簇，勿连则是必不在同一个类簇。标记信息：少量的样本带有真实的标记。
下面主要介绍两种基于半监督的K-Means聚类算法：约束k均值(Constrained k-means) 利用第一种监督信息，约束种子 k 均值(Constrained Seed k-means) 利用第二种监督信息。
两种算法的基本思想都十分的简单：约束k均值，在迭代过程中对每个样本划分类簇时，需要 检测当前划分是否满足约束关系，若不满足则会将该样本划分到距离次小对应的类簇中，再继续检测是否满足约束关系，直到完成所有样本的划分。算法流程如下图所示：
iwJAzQ.png
image-20210301173415409
对于带有少量标记样本的k-均值算法，则可以 利用这些有标记样本进行类中心的指定，同时在对样本进行划分时，不需要改变这些有标记样本的簇隶属关系，直接将其划分到对应类簇即可。算法流程如下所示：
iwJkRg.png
