本章主要关注数据中一部分已标注，一部分未标注的情形，一般记为，\ D_l = {(x_1, y_1), …, (x_l, y_l)}, D_u = {x_{l+1}, …, x_{l+u}}\
\( y_i \in \lbrace-1, +1\rbrace \)。
13.1 未标记样本
一个简单的做法是主动学习：用 $D_l$ 先训练一个模型，拿这个模型去地里挑一个瓜，询问瓜农好不好，然后把这个新获得的有标记样本加入 $D_l$ 中重新训练一个模型，再去挑瓜。这一做法类似于强化学习，强调挑选对提升模型性能有帮助的未标注样本。
但这样需要引入额外的标注，而半监督学习(semi-supervised learning)则强调让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能。一个典型思路是利用未标注样本和已标注数据的同分布性，比如利用未标注数据形成的数据簇可以帮助判定数据点对应的类别。
要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与 类别标记相联系的假设。最常见的是” 聚类假设” (cluster assumption) ，即假设数据存在簇结构，同一个簇的样本属于同一个类别。半监督学习中另一种常见的假设是”流形假设” (manifold assumption) ， 即假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。流形假设可看作聚类假设的推广， 但流形假设对输出值没有限制。事实上，无论聚类假设还是流形假设，其本质都是”相似的样本拥有相似的输出”这个基本假设，其思想非常接近于高斯过程。
半监督学习可进一步划分为纯(pure)半监督学习和直推学习(transductive learning) ，前者假定训练数据中的未标记样本并非待预测的数据， 而后者则假定学习过程中所考虑的未标记样本恰是待预测数据。
13.2 生成式方法
此类方法假设所有数据(无论是否有标记)都是由同一个潜在的模型” 生成”的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，而未标记数据的标记则可看作模型的缺失参数，通常可基于EM 算法进行极大似然估计求解。有点类似于GP中inducing points的选取，这么看来也要区分GP的目标是纯（对未知的新的y*预测）还是半监督（对已知的某些点预测）。
Eg：N分类高斯混合模型
设定上沿循传统，假设高斯混合成分$\Theta$和实际类别$y$一一对应，即x空间上的簇对应了不同的类别。
| $p(y=j | \Theta=i, x)$这一项必须要用到标注y，但是$p(\Theta=i | x)$可以利用未标注项得到更精确的估计。整体数据的对数似然函数为 |
针对此目标函数应用EM算法即可迭代得到未标记样本属于各高斯混合成分的概率。
此类方法有一个关键：模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合·否则利用未标记数据反倒会降低泛化性能[Cozman and Cohen, 2002]。遗憾的是，在现实任务中往往很难事先做出准确的模型假设，除非拥有充分可靠的领域知识。
13.3 半监督SVM
半监督支持向量机(Semi-Supervised Support Vector Machine，简称S3VM) 是支持向量机在半监督学习上的推广在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后， S3VM 试图找到能将两类有标记样本分开且穿过数据低密度区域的划分超平面， 如图13 . 3 所示，这里的基本假设足”低密度分割” (low-density separation)，显然，这是聚类假设在考虑了线性超平面划分后的推广。
半监督支持向量机中最著名的是TSVM (Transductive Support Vector Machine) [Joachims, 1999]。与标准SVM 一样， TSVM 也是针对二分类问题的学习方法。TSVM 试图考虑对未标记样本进行各种可能的标记指派(label assignment) ，即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中， 寻求一个在所有样本(包括有标记样本和进行了标记指派的未标记样本)上间隔最大化的划分超平面. 一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。
注意这一过程中，可能的指派$\hat{y}$也是用于优化的参数。尝试未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解，在一般情形下必须考虑更高效的优化策略。
TSVM 采用局部搜索来迭代地寻找式(13.9) 的近似解。具体来说，
- 它先利用有标记样本学得一个SVM ，即忽略式(13.9) 中关于Du 与$\hat{y}$的项及约束。
- 然后，利用这个SVM 对未标记数据进行标记指派，即将SVM预测的结果作为”伪标记” (pseudφlabel)赋予未标记样本。
- 此时$\hat{y}$成为己知，将其代入式(13.9) 即得到一个标准SVM 问题，于是可求解出新的划分超平面和松弛向量；注意到此时未标记样本的伪标记很可能不准确，因此$C_u$要设置为比$C_l$小的值，使有标记样本所起作用更大。
- 接下来，TSVM 找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于式(13.9)求解出更新后的划分超平面和松弛向量。
- 然后再找出两个标记指派为异类且很可能发生错误的未标记样本……
- 标记指派调整完成后，逐渐增大$C_u$以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直到$C_u=C_l$ 为止。
关于“很可能发生错误的未标记样本”：若存在一对未标记样本$x_i, x_j$，其标记指派$y_i$与$y_j$不同，且对应的松弛变量满足$\xi_i + \xi_j > 2$，则意味着$y_i$与$y_j$很可能是错误的，需对二者进行交换后重新求解式(13.9) ，这样每轮迭代后均可使式(13.9) 的目标函数值下降。
在对未标记样本进行标记指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另命类，这将对SVM的训练造成困扰。可对以上算法稍加改进：将优化目标中的$C_u$项拆分为$C_u^+$与$C_u^-$两项，分别对应基于伪标记而当作正、反例使用的未标记样本，并在初始化时令$C_u^+ = \frac{u_-}{u_+} C_u^-$。其中$u_+$与$u_-$为基于伪标记而当作正、反例使用的未标记样本数。
12.4 图半监督学习
给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点。若两个样本之间的相似度很高(或相关性很强)，则对应的结点之间存在一条边，边的”强度” (strength) 正比于样本之间的相似度(或相关性)。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是，半监督学习就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。
多分类问题需要迭代求解，设$F(t)$为第t轮时各观测的标记矩阵（每行是观测$x_i$的标记向量，每个元素是归属于对应类的信念强度）
13.5 基于分歧的方法
显式地考虑多视图有很多好处。仍以电影为例，某个片段上有两人对视，仅凭图像画面信息难以分辨其类型，但此时若从声音信息昕到”我爱你”则可判断出该片段很可能属于”爱情片”；另一方面，若仅凭图像画面信息认为”可能是动作片”，仅凭声音信息也认为”可能是动作片”，则当两者一起考虑时就有很大的把握判别为”动作片”。
显然，在”相容性”基础上，不同视图信息的”互补性”会给学习器的构建带来很多便利。
一种利用多视图的”相容互补性”的方法是协同训练。假设数据拥杳两个充分(sufficient )且条件独立视图，”充分”是指每个视图都包含足以产生最优学习器的信息，”条件独立”则是指在给定类别标记条件下两个视图独立。在此情形下，可用一个简单的办法来利用未标记数据：首先在每个视图上基于有标记样本分别训练出一个分类器，然后让每个分类器分别去挑选自己”最有把握的”未标记样本赋予伪标记，并将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新……这个”互相学习、共同进步”的过程不断迭代进行，直到两个分类器都不再发生变化，或达到预先设定的迭代轮数为止。
不过，视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度不会那么大。
基于分歧的方法只需采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、适用范围较为广泛。为了使用此类方法，需能生成具有显著分歧、性能尚可的多个学习器，但当有标记样本很少，尤其是数据不具有多视图时，要做到这一点并不容易，需有巧妙的设计。
13.6 半监督聚类
聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可通过半监督聚类(semi-supervised clustering)来利用监督信息以获得更好的聚类效果。聚类任务中获得的监督信息大致有两种类型，第一种类型是”必连”(must-link) 与”勿连” ( cannot-link) 约束，前者是指样本必属于同一个簇，后者是指样本必不属于同一个簇;第二种类型的监督信息则是少量的有标记样本.
约束k 均值(Constrained k-means) 算法[Wagstaff et al. , 2001] 是利用第一类监督信息的代表，即给定样本集D = {X1, X2, …, Xm} 以及”必连”, “勿连”关系。该算法是k 均值算法的扩展，它在聚类过程中要确保约束得以满足，否则将返回错误提示（分配当前点到其他的簇）。算法如图13. 7 所示：
第二种监督信息是少量有标记样本。给定样本集D = {X1, …, Xm} ，和少量的有标记样本$S \in D$，包含某个观测隶属于哪一个聚类簇的信息。这样的监督信息利用起来很容易：直接将它们作为”种子”，用它们初始化k均值算法的k个聚类中心，并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系。这样就得到了约束种子k 均值(Constrained Seed k-means) 算法[Basu et al., 2002]。
