【西瓜书】第13章 半监督学习

13.1 未标记样本

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

最常用的是“聚类假设”即假设数据存在簇结构，同一个簇的样本属于同一个类别。

半监督学习中另外一种常见的假设是流行假设，即假设数据分布在一个流形结构上，邻近样本拥有相似的输出值。

以上两种假设，其本质都是“相似的样本拥有相似的输出”

半监督学习可以划分为纯半监督和直推学习，前者假定训练数据中的未标记样本并非待预测数据，后者假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能。

13.2 生成式方法

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

假设样本由高斯混合模型生成，且每个类别对应一个高斯混合成分

数据样本概率密度函数加入高斯混合成分的参数

先验概率 P(y=yi) 就是alpha

公式13.2推导

如果已知x由那个高斯混合成分生成，就知道了其类别

公式第1项是针对有标记样本进行的最大似然估计，第二项直接运用的13.1式，因为不知道标记类型，它可能是N个高斯混合模型中的任何一个。

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

EM方法进行求解：

首先对各个高斯混合成分的参数及混合系数进行初始化，计算出各个PM（即γji，第i个样本属于j类，有标记样本则直接属于特定类），再最大化似然函数（即LL（D）分别对α、u和∑求偏导 ），对参数进行迭代更新。

13.5式与13.1式类似

以上就是通过已经有标记的样本对初始的参数进行初始化

上式的推导在第9章 中有

xj是未标记样本，li表示第i类的有标记样本数，所有两者不冲突，对于没有标记的样本，i的都是常数，这也是为什么ui能够提出来的原因

13.7的求解过程类似，在这不再搬运

13.8利用拉格朗日形式进行求解

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

看完这些，突然觉得很牛逼，但是模型假设必须准确，假设必须准确，这种在现实任务中很难实现。

13.3 半监督SVM

半监督支持向量机（S3VM）中最著名的是TSVM，与标准SVM一样，TSVM也是针对二分类问题的学习方法。

上式和SVM基本类似，就是添加了无标记样本的的松弛变量

上式和SVM基本类似，就是添加了无标记样本的的松弛变量

书中指出：尝试未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才可能求解。

TSVM

1.先通过利用有标记样本学习得到一个SVM

2.通过上面得到的SVM对未标记数据进行标记指派，将SVM预测的结果作为“伪标记”

3.基于SVM根据13.9求解划分超平面和松弛变量（Cu比Cl小使有标记样本所起作用更大）

4.找出两个标记指派为异类且很可能发生错误的未标记样本，交换标记，重新进入13.9求解划分超平面和松弛变量

5.循环3和4直到Cu=Cl为止

说明：

2.中的为伪标记

6.松弛变量越大表示距离超平面越近，越容易出错，while的条件就是确定误判点的条件！

11.增大Cu但是不超过Cl，未标记样本权重小于有标记样本

TSVM尝试为未标记样本找到合适的标记指派，使得超平面划分后的间隔最大化。TSVM采用局部搜索的策略来进行迭代求解，即首先使用有标记样本集训练出一个初始SVM，接着使用该学习器对未标记样本进行打标，这样所有样本都有了标记，并基于这些有标记的样本重新训练SVM，之后再寻找易出错样本不断调整。

13.4图半监督学习

给定的数据集可以映射为图，数据集中的每一个样本对应于图中的一个节点，若两个样本之间相关性强，则对应的节点之间存在一条边，边的强度正比于样本之间的相关性。

构建图G(V,E) 其中V为节点，E为亲和矩阵表示边，通常基于高斯函数定义

这个矩阵实对称矩阵，假定从图中学到一个实值函数f(x)，y=sign(f(x)),y∈{-1，1}，定义f的能量函数

该方法针对二分类问题（-1，1）的标记传播方法，我们希望能量函数越小越好，因为xi与xj越相似，Wij越大，因此要求能量函数的后半部分越小越好，即相似的样本应具有相似的标记，以下是上式的推导，在推导过程中关于矩阵转置的运用求和需要重点关注，也是从样本累加转变为矩阵相乘的一种手段，之前也接触过。

W矩阵是对称矩阵，行列变化可以互换

书中对f特意进行了说明，是有标记的样本集合和没有标记样本集合的在一起的

要让上面的能量函数最小，有标记样本要预测对，f(xi)=yi；没有标记的样本，是上式的代求变量，对13.12中f(xi)（未标记样本的）进行求导，为零就是取得最小值的f(x)

以下为如何求上面的最小值的方法，在西瓜书下面的论述过程中，将没有标记的和有标记区分对待

用使用标记的样本表示了未标记的样本

相同的样本具有相类似的标记，那么能量函数最小时就是对无标记样本预测最准确的时候，与我们有标记样本具有最相似标记的时候

*下面的多分类问题的标记传播有点看不大明白，先放着*

13.5基于分歧的方法

------以下为摘抄内容，写的很好----------------------------

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

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

协同训练正是很好地利用了多视图数据的“相容互补性”，其基本的思想是：

首先基于有标记样本数据在每个视图上都训练一个初始分类器

然后让每个分类器去挑选分类置信度最高的样本并赋予标记，并将带有伪标记的样本数据传给另一个分类器去学习，从而你依我侬/共同进步。

书中给出：

10、11步完成的工作就是把自己预测的给对方，这样互相促进

14步 就是如果没有变化，表示退出循环，再接下去训练没有任何效果，训练完毕，如果发生变化，则将加过虚标签的样本加入有标签的样本集，调整视图样本集

13.6 半监督聚类

聚类任务中获得监督信息大致有两种类型，第一种类型是“必连”与“勿连”，前者指样本必属于同一个簇，后者是样本比不属于同一个簇；第二种类型的监督信息则是少量的有标记样本。

约束k均值算法，在迭代过程中对每个样本划分类簇时，需要检测当前划分是否满足约束关系，若不满足则会将该样本划分到距离次小对应的类簇中，再继续检测是否满足约束关系，直到完成所有样本的划分。

4步：对样本所有集合进行遍历

11步至13步  如果符合约束则把样本点加入这个类簇中，退出循环

14步到19步尝试各类簇中均违背M和C中的约束，则16步为真，算法报错结束。

22行至25行 更新均值向量，重新开始新一轮迭代，直到均值均未更新

西瓜例子，直线是必连约束，虚线是勿连约束

第二种监督信息是少量有标记样本，此次样本标记为簇标记，不是类别标记，约束种子k均值，就是用有标记的样本初始化聚类中心，在迭代更新过程中不改变种子样本的簇隶属关系。

6步至10步将有标记的样本加入对应簇，就是不改变原来的样本标记

11至15步就是对没有簇标记的样本进行处理

16至18步更新均值向量，与k-means算法一致