半监督学习

Posted on

半监督学习

1. 未标记样本

在现实学习任务中，我们获取到的数据大多数包含有标记数据和未标记数据，若直接使用传统的监督学习算法学习有标记数据，那么未标记数据中所包含的信息就被浪费了。同时，通常有标记数据的样本容量较小，所以学得模型的泛化能力往往不佳，我们需要思考能否在构建模型的过程中利用未标记数据。

主动学习：先利用有标记样本训练一个模型，利用这个模型去对未标记样本进行预测，选出对改善模型性能帮助大的样本进行专家预测，这样就能通过很少的人工成本构建出性能较强的模型。例如，基于有标记样本训练一个SVM，挑选距离分类超平面最近的未标记样本进行查询，之后加入有标记样本中重新训练模型。

主动学习引入了额外的专家知识，通过与外界的交互将部分未标记样本转换为有标记样本，我们希望通过不与专家交互的形式，利用未标记样本提高模型的泛化性能。

事实上，未标记样本虽未直接包含标记信息，但若它们与有标记样本是从同样的数据源独立同分布采样而来，那么它们所包含的信息对于模型的建立还是很有帮助。如下图，若只基于图中的一个正例和一个负例，对于待判别样本只能是随机猜测；若能观察到图中其他未标记样本，将有很大的把握判别为正例。

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

要利用未标记样本，需要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设：

  • 聚类假设（cluster assumption）：假设数据存在簇结构，同一个簇的样本属于同一类别；
  • 流形假设（manifold assumption）：假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。“邻近”程度常用“相似”程度来刻画，因此，流形假设可看作聚类假设的推广，但流形假设对输出值没有限制，因此比聚类假设的适用范围更广，可用于更多类型的学习任务。

无论是聚类假设还是流形假设，其本质都是相似的样本拥有相似的输出这个基本假设。

半监督学习可进一步划分为纯半监督学习和直推学习（transductive learning）：

  • 纯半监督学习：假定训练数据中的未标记样本并非待预测的数据，希望学得模型能使用于训练过程中未观察到的数据；
  • 直推学习：假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能，即试图对学习过程中观察到的未标记数据进行预测。

2. 生成式方法

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

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

给定样本\(\pmb{x}\)，其真实类别标记记为\(y \in \mathscr{Y}\)，其中\(\mathscr{Y} = \{1,2,\cdots,N\}\)为所有可能的类别。假设样本由高斯混合模型生成，且每个类别对应一个高斯混合成分。即数据样本是基于如下概率分布产生： \[p(\pmb{x}) = \sum_{i=1}^N \alpha_i \cdot p(\pmb{x}|\pmb{\mu}_i, \pmb{\Sigma}_i)\] 其中，混合系数\(\alpha_i \geqslant 0, \sum_{i=1}^N \alpha_i = 1\)；\(p(\pmb{x}|\pmb{\mu}_i, \pmb{\Sigma}_i)\)是样本\(\pmb{x}\)属于第\(i\)个高斯混合成分的概率；\(\pmb{\mu}_i\)和\(\pmb{\Sigma}_i\)为该高斯混合成分的参数。

令\(f(\pmb{x}) \in \mathscr{Y}\)表示模型\(f\)对\(\pmb{x}\)的预测标记，\(\Theta \in \{1,2,\cdots,N\}\)表示样本\(\pmb{x}\)所属的高斯混合成分。由最大化后验概率可知 \[\DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \begin{align} f(\pmb{x}) &= \argmax_{j \in \mathscr{Y}} p(y = j | \pmb{x}) \nonumber \\ &= \argmax_{j \in \mathscr{Y}} \sum_{i=1}^N p(y=j, \Theta = i | \pmb{x}) \nonumber \\ &= \argmax_{j \in \mathscr{Y}} \sum_{i=1}^N p(y = j| \Theta = i, \pmb{x})\cdot p(\Theta = i| \pmb{x}) \nonumber \end{align}\]

其中 \[p(\Theta = i | \pmb{x}) = \frac{\alpha_i \cdot p(\pmb{x}|\pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{i=1}^N \alpha_i \cdot p(\pmb{x}|\pmb{\mu}_i, \pmb{\Sigma}_i)}\] 为样本\(\pmb{x}\)由第\(i\)个高斯混合成分生成的后验概率，\(p(y = j| \Theta = i, \pmb{x})\)为\(\pmb{x}\)由第\(i\)个高斯混合成分生成且其类别为\(j\)的概率。由于假设每个类别对应一个高斯混合成分，因此\(p(y=j|\Theta = i. \pmb{x})\)仅与样本\(\pmb{x}\)所属的高斯混合成分\(\Theta\)有关，可用\(p(y=j|\Theta=i)\)代替。不失一般性，假定第\(i\)个类别对应于第\(i\)个高斯混合成分，即\(p(y=j|\Theta = i) = 1\)当且仅当\(i=j\)，否则\(p(y=j|\Theta = i) = 0\)。

从式中可以看出估计\(p(y=j | \Theta = i, \pmb{x})\)需要知道样本标记，因此使用有标记数据；而\(p(\Theta = i| \pmb{x})\)不涉及样本标记，因此有标记和未标记数据均可利用，通过引入大量的未标记数据，对这一项的估计可望由于数据量的增长而更为准确，于是公式整体的估计可能也会更准确。从这里也可以看出未标记数据对于分类模型性能的提升。

给定有标记样本集\(D_l = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_l,y_l)\}\)和未标记样本集\(D_u = \{\pmb{x}_{l+1},\pmb{x}_{l+2},\cdots,\pmb{x}_{l+u}\}, l \ll u, l+u = m\)，假设所有样本独立同分布，且都是由同一个高斯混合模型生成的。用极大似然法来估计高斯混合模型的参数\(\{(\alpha_i, \pmb{\mu}_i, \pmb{\Sigma}_i)| 1 \leqslant i \leqslant N\}\)，\(D_l \cup D_u\)的对数似然为 \[\begin{align} LL(D_l \cup D_u) = & \sum_{(\pmb{x}_j,y_j) \in D_l} \ln (\sum_{i=1}^N \alpha_i \cdot p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i) \cdot p(y_j | \Theta = i, \pmb{x}_j)) \nonumber \\ &+ \sum_{\pmb{x}_j \in D_u} \ln(\sum_{i=1}^N \alpha_i \cdot p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i)) \nonumber \end{align}\]

上式由两项组成：基于有标记数据\(D_l\)的有监督项和基于未标记数据\(D_u\)的无监督项。显然，高斯混合模型参数估计可用EM算法求解，迭代更新式如下：
E步：根据当前模型参数计算未标记样本\(\pmb{x}_j\)属于各高斯混合成分的概率 \[\gamma_{ji} = \frac{\alpha_i \cdot p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{i=1}^N \alpha_i \cdot p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i)}\]

M步：基于\(\gamma_{ji}\)更新模型参数，其中\(l_i\)表示第\(i\)类的有标记样本数目 \[\begin{align} \pmb{\mu}_i &= \frac{1}{\sum_{\pmb{x}_j \in D_u}\gamma_{ji} + l_i} (\sum_{\pmb{x}_j \in D_u} \gamma_{ji} \pmb{x}_j + \sum_{(\pmb{x}_j,y_j) \in D_l \wedge y_j = i} \pmb{x}_j) \nonumber \\ \pmb{\Sigma}_i &= \frac{1}{\sum_{\pmb{x}_j \in D_u}\gamma_{ji} + l_i} (\sum_{\pmb{x}_j \in D_u} \gamma_{ji} (\pmb{x}_j - \pmb{\mu}_i)(\pmb{x}_j - \pmb{\mu}_i)^T \nonumber \\ &\quad + \sum_{(\pmb{x}_j,y_j) \in D_l \wedge y_j = i} (\pmb{x}_j - \pmb{\mu}_i)(\pmb{x}_j - \pmb{\mu}_i)^T ) \nonumber \\ \alpha_i &= \frac{1}{m} (\sum_{\pmb{x}_j \in D_u} \gamma_{ji} + l_i) \nonumber \end{align}\]

以上过程不断迭代直至收敛，即可获得模型参数。由\(f(\pmb{x})\)就能对样本进行分类。

将上述过程中的高斯混合模型换成混合专家模型、朴素贝叶斯模型等即可推导出其他的生成式监督学习方法。此类方法简单，易于实现，在有标记数据极少的情形下往往比其他方法性能更好。
此类方法有一个关键：模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合；否则利用未标记数据反倒会降低泛化性能。遗憾的是，现实任务中往往很难实现做出准确的模型预测，除非拥有充分可靠的领域知识。

3. 半监督SVM

半监督支持向量机（Semi-Supervised Support Vector Machine，S3VM）是支持向量机在半监督学习上的推广。在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。如下图所示，这里的基本假设是“低密度分隔”（low-density separation），这是聚类假设在考虑线性超平面划分后的推广。

半监督支持向量机中最著名的是TSVM（Transductive Support Vector Machine）。与标准SVM一样，TSVM也是针对二分类问题的学习方法。TSVM试图考虑对未标记样本进行各种可能的标记指派（label assignment），即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

形式化地说，给定\(D_l = \{(\pmb{x}_1,y_1), (\pmb{x}_2,y_2),\cdots,(\pmb{x}_l,y_l)\}\)和\(D_u = \{\pmb{x}_{l+1}, \pmb{x}_{l+2},\cdots,\pmb{x}_{l+u}\}\)，其中\(y_i \in \{-1,+1\}, l \ll u,l + u = m\)。TSVM的学习目标是为\(D_u\)中的样本给出预测标记\(\hat{\pmb{y}} = (\hat{y}_{l+1}, \hat{y}_{l+2},\cdots, \hat{y}_{l+u}), \hat{y}_i \in \{-1,+1\}\)，使得 \[\begin{align} & \min_{\pmb{w},b,\hat{\pmb{y}},\pmb{\xi}} \quad \frac{1}{2} ||\pmb{w}||_2^2 + C_l \sum_{i=1}^l \xi_i C_u \sum_{i=l+1}^m \xi_i \nonumber \\ & s.t. \qquad y_i (\pmb{w}^T \pmb{x}_i + b) \geqslant 1 - \xi_i, \quad i=1,2,\cdots,l \nonumber \\ & \qquad \qquad \hat{y}_i (\pmb{w}^T \pmb{x}_i + b) \geqslant 1 - \xi_i, \quad i=l+1,l+2,\cdots,m \nonumber \\ & \qquad \qquad \xi_i \geqslant 0, i=1,2,\cdots,m \nonumber \end{align}\]

其中，\((\pmb{w},b)\)确定了一个划分超平面；\(\pmb{\xi}\)为松弛变量，\(\xi_i(i=1,2,\cdots,l)\)对应于标记样本，\(\xi_i(i=l+1,l+2,\cdots,m)\)对应于未标记样本；\(C_l\)与\(C_u\)是由用户指定的用于平衡模型复杂度、有标记样本与未标记样本重要程度的折中参数。

显然，尝试未标记样本的各种指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解。一般情形下，必须考虑更高效的优化策略。

TSVM采用局部搜索来迭代寻找上式的近似解：

  1. 先利用有标记样本学得一个SVM，即忽略上式中涉及\(C_u\)与\(\hat{\pmb{y}}\)的项及约束。然后利用这个SVM对未标记数据进行标记指派，即将SVM预测的结果作为“伪标记”赋予未标记样本，此时\(\hat{\pmb{y}}\)成为已知；
  2. 将其带入上式即得到一个标准SVM问题，于是可求解出新的划分超平面和松弛变量；此时未标记样本的伪标记很可能不准确，因此\(C_u\)要设置为比\(C_l\)小的值，是有标记样本所起的作用更大。
  3. TSVM找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，重新基于上式求解更新后的划分超平面和松弛变量，对此过程迭代；
  4. 标记指派完成后，逐渐增大\(C_u\)以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直至\(C_u = C_l\)为止。此时求解得到的SVM不仅给未标记样本提供标记，还能对训练过程中未见的示例进行预测。

在对未标记样本进行标记指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类，这将对SVM的训练过程造成困扰。为了减轻类别不平衡所造成的不利影响，可对上述算法进行改进：将优化目标的\(C_u\)项拆分为\(C_u^+\)和\(C_u^-\)两项，分别对应基于伪标记而当作正、反例使用的未标记样本，并在初始化令： \[C_u^+ = \frac{u_-}{u_+} C_u^-\] 其中\(u_+\)与\(u_-\)为基于伪标记而当作正、反例使用的未标记样本数。

显然，搜寻标记指派可能出错的每一对未标记样本进行调整，是一个涉及巨大计算开销的大规模优化问题。因此，半监督SVM研究的一个重点是如何设计出高效的优化求解策略。由此发展出很多方法，如基于图核（graph kernel）函数梯度下降的LDS、基于标记均值估计的meanS3VM等。

4. 图半监督学习

4.1. 二分类问题

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个节点，若两个节点之间的相似度很高（或相关性很强），则对应的节点之间存在一条边，边的“强度”正比于样本之间的相似度（或相关性）。可将有标记样本所对应的节点想象为染过色，而未标记样本所对应的节点未染色，于是，半监督学习就对应于“颜色”在图上扩散或传播的过程。由于一个图就对应一个矩阵，使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。

给定\(D_l = \{(\pmb{x}_1,y_1), (\pmb{x}_2,y_2),\cdots,(\pmb{x}_l,y_l)\}\)和$D_u = {{l+1}, {l+2},,_{l+u}}, l u, l+u = m \(，首先基于\)D_l D_u\(构建一个图\)G = (V,E)\(，其中节点集\)V = {1,,l,{l+1},, {l+u}}\(，边集\)E$可表示为一个亲和矩阵（affinity matrix），常基于高斯函数定义为 \[(\mathbf{W})_{ij} = \begin{cases} \exp(\frac{- ||\pmb{x}_i - \pmb{x}_j||_2^2}{2 \sigma^2}), \quad if \quad i \neq j ; \\ 0, \qquad \qquad \qquad \quad otherwise \end{cases} \tag{13.11}\] 其中\(i,j \in \{1,2,\cdots,m\},\sigma > 0\)使用户指定的高斯函数带宽参数。

假定从图\(G=(V,E)\)将学得一个实值函数\(f:V \to \mathbf{R}\)，其对应的分类规则为：\(y_i = sign(f(\pmb{x}_i)), y_i \in \{-1,+1\}\)。直观上看，相似的样本应具有相似的标记，于是可定义关于\(f\)的能量函数（energy function）： \[\begin{align} E(f) &= \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij} (f(\pmb{x}_i) - f(\pmb{x}_j))^2 \nonumber \\ &= \frac{1}{2} \left(\sum_{i=1}^m d_i f^2(\pmb{x}_i) + \sum_{j=1}^m d_j f^2(\pmb{x}_j) - 2 \sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij} f(\pmb{x}_i) f(\pmb{x}_j) \right) \nonumber \\ &= \sum_{i=1}^m d_i f^2(\pmb{x}_i) - \sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij} f(\pmb{x}_i) f(\pmb{x}_j) \nonumber \\ &= \pmb{f}^T(\mathbf{D} - \mathbf{W}) \pmb{f} \tag{13.12} \end{align}\]

其中\(\pmb{f} = (\pmb{f}_l^T;\pmb{f}_u^T), \pmb{f}_l = (f(\pmb{x}_1),f(\pmb{x}_2),\cdots,f(\pmb{x}_l)),f_u=(f(\pmb{x}_{l+1}),f(\pmb{x}_{l+2}),\cdots,f(\pmb{x}_{l+u}))\)分别为函数\(f\)在有标记样本与未标记样本上的预测结果，\(\mathbf{D} = diag(d_1,d_2,\cdots,d_{l+u})\)是一个对角矩阵，其对角元素\(d_i = \sum_{j=1}^{l+u} (\mathbf{W})_{ij}\)为矩阵\(\mathbf{W}\)的第\(i\)行元素之和（\(\mathbf{W}\)为对称矩阵，因此\(d_i\)也为\(\mathbf{W}\)第\(i\)列元素之和），能量函数最小化时即得到最优结果。

具有最小能量的函数\(f\)在有标记样本上满足\(f(\pmb{x}_i) = y_i(i=1,2,\cdots,l)\)，在未标记样本上满足\(\mathbf{\Delta} \pmb{f} = \pmb{0}\)，其中\(\mathbf{\Delta} = \mathbf{D} - \mathbf{W}\)为拉普拉斯矩阵（Laplacian matrix）。以第\(l\)行与第\(l\)列为界，采用分块矩阵表示方式:\(\mathbf{W} = \left[ \begin{matrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{matrix} \right]\)，\(\mathbf{D} = \left[ \begin{matrix} \mathbf{D}_{ll} & \mathbf{D}_{lu} \\ \mathbf{D}_{ul} & \mathbf{D}_{uu} \end{matrix} \right]\)，则能量函数可重写为 \[\begin{align} E(f) &= (\pmb{f}_l^T \pmb{f}_u^T) \left( \left[ \begin{matrix} \mathbf{D}_{ll} & \mathbf{D}_{lu} \\ \mathbf{D}_{ul} & \mathbf{D}_{uu} \end{matrix} \right] - \left[ \begin{matrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{matrix} \right] \right) \left[ \begin{matrix} \pmb{f}_l \\ \pmb{f}_u \end{matrix} \right] \nonumber \\ &= \pmb{f}_l^T (\mathbf{D}_{ll} - \mathbf{W}_{ll}) \pmb{f}_l - 2 \pmb{f}_u^T \mathbf{W}_{ul} \pmb{f}_l + \pmb{f}_u^T (\mathbf{D}_{uu} - \mathbf{W}_{uu}) \pmb{f}_u \nonumber \end{align}\]

由\(\frac{\partial E(f)}{ \partial \pmb{f}_u} = \pmb{0}\)可得 \[\pmb{f}_u = (\mathbf{D}_{uu} - \mathbf{W}_{uu})^{-1} \mathbf{W}_{ul} \pmb{f}_l \tag{13.15}\] 令 \[\begin{align} \mathbf{P} &= \mathbf{D}^{-1} \mathbf{W} = \left[ \begin{matrix} \mathbf{D}_{ll}^{-1} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu}^{-1} \end{matrix} \right] \left[ \begin{matrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{matrix} \right] \nonumber \\ &= \left[ \begin{matrix} \mathbf{D}_{ll}^{-1} \mathbf{W}_{ll} & \mathbf{D}_{ll}^{-1} \mathbf{W}_{lu} \\ \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul} & \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu} \end{matrix} \right] \nonumber \end{align}\]

即\(\mathbf{P}_{uu} = \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu}, \mathbf{P}_{ul} = \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul}\)，则式（13.15）可重写为 \[\begin{align} \pmb{f}_u &= (\mathbf{D}_{uu} (\mathbf{I} - \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu}))^{-1} \mathbf{W}_{ul} \pmb{f}_l \nonumber \\ &= (\mathbf{I} - \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu})^{-1} \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul} \pmb{f}_l \nonumber \\ &= (\mathbf{I} - \mathbf{P}_{uu})^{-1} \mathbf{P}_{ul} \pmb{f}_l \nonumber \end{align}\] 将\(D_l\)上的标记信息作为\(\pmb{f}_l = (y_1,y_2,\cdots,y_l)\)代入上式即可利用求得的\(\pmb{f}_u\)对未标记样本进行预测。

4.2. 多分类问题

假定\(y_i \in \mathscr{Y}\)，仍基于\(D_l \cup D_u\)构建一个图\(G=(V,E)\)，其中节点集\(V = \{\pmb{x}_1,\cdots, \pmb{x}_l, \cdots, \pmb{x}_{l+u}\}\)，边集\(E\)所对应的\(\mathbf{W}\)仍使用式（13.11），对角矩阵\(\mathbf{D} = diag(d_1,d_2,\cdots,d_{l+u})\)的对角元素\(d_i= \sum_{j=1}^{l+u} (\mathbf{W})_{ij}\)。定义一个\((l+u) \times \mathscr{Y}\)的非负标记矩阵\(\mathbf{F} = (\mathbf{F}_1^T,(\mathbf{F}_2^T,\cdots,(\mathbf{F}_{l+u}^T)^T\)，其中第\(i\)行元素\(\mathbf{F}_i = ((\mathbf{F})_{i1},(\mathbf{F})_{i2}, \cdots, (\mathbf{F})_{i|\mathscr{Y}|})\)为示例\(\pmb{x}_i\)的标记向量，相应的分类规则为：\(y_i = \arg \max_{1 \leqslant j \leqslant |\mathscr{Y}|} (\mathbf{F})_{ij}\)。

对\(i=1,2,\cdots,m, j=1,2,\cdots, |\mathscr{Y}|\)，将\(\mathbf{F}\)初始化为 \[\mathbf{F}(0) = (\mathbf{Y})_{ij} = \begin{cases} 1, \quad if \quad (1 \leqslant i \leqslant l) \wedge (y_i = j); \\ 0, \quad otherwise \end{cases}\] 显然，\(\mathbf{Y}\)的前\(l\)行就是\(l\)个有标记样本的标记向量。

基于\(\mathbf{W}\)构造一个标记传播矩阵\(\mathbf{S} = \mathbf{D}^{- \frac{1}{2}} \mathbf{W} \mathbf{D}^{- \frac{1}{2}}\)，其中\(\mathbf{D}^{- \frac{1}{2}} = diag(\frac{1}{\sqrt{d_1}},\frac{1}{\sqrt{d_2}},\cdots,\frac{1}{\sqrt{d_{l+u}}})\)，于是迭代计算式 \[\mathbf{F}(t+1) = \alpha \mathbf{S} \mathbf{F}(t) + (1 - \alpha) \mathbf{Y}\] 其中\(\alpha \in (0,1)\)为用户指定的参数，用于对标记传播项\(\mathbf{S} \mathbf{F}(t)\)与初始化项\(\mathbf{Y}\)的重要性进行折中。基于上式迭代至收敛可得 \[\mathbf{F}^* = \lim_{t \to \infty} \mathbf{F}(t) = (1 - \alpha) (\mathbf{I} - \alpha \mathbf{S})^{-1} \mathbf{Y}\]

由\(\mathbf{F}^*\)可获得\(D_u\)中样本的标记\((\hat{y}_{l+1}, \hat{y}_{l+2}, \cdots, \hat{y}_{l+u})\)。

算法如下：

上述算法对应于正则化框架： \[\min_{\mathbf{F}} \frac{1}{2} \left( \sum_{i,j=1}^{l+u} (\mathbf{W})_{ij} \parallel \frac{1}{\sqrt{d_i}} \mathbf{F}_i - \frac{1}{\sqrt{d_j} \mathbf{F}_j} \parallel^2 \right) + \mu \sum_{i=1}^l \parallel \mathbf{F}_i - \mathbf{Y}_i \parallel^2 \tag{13.21}\]

其中\(\mu > 0\)为正则化参数，当\(\mu = \frac{1 - \alpha}{\alpha}\)时，上式的最优解为算法的迭代收敛解\(\mathbf{F}^*\)。

上式的第二项是迫使结果在有标记样本上的预测与真实标记尽可能相同，第一项则迫使相近样本具有相似的标记，这也是基于半监督学习的假设。

式（13.21）考虑离散的类别标记，而式（13.12）则是考虑输出连续值。
图半监督学习方法在概念上比较清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也比较明显：

  • 存储开销：若样本数为\(O(m)\)，则算法中涉及的矩阵规模为\(O(m^2)\)，此类算法很难直接处理大规模数据；
  • 难以判知新样本在图中的位置：构图过程仅能考虑训练样本集，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是引入额外的预测机制。例如将\(D_l\)和经标记传播后得到标记的\(D_u\)合并作为训练集，另外训练一个学习器例如SVM来对新样本进行预测。

5. 基于分歧的方法

与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法（disagreement-based methods）使用多学习器，而学习器之间的“分歧”对未标记数据的利用至关重要。

协同训练（co-training）是此类方法的重要代表，它最初是针对“多视图”（multi-view）数据设计的，因此也被看作“多视图学习”（multi-view learning）的代表。

很多现实应用中，一个数据对象往往同时拥有多个“属性集”，每个属性集就构成了一个“视图”。如一部电影拥有多个属性集：图像画面信息对应的属性集、声音信息对应的属性集、字幕信息对应的属性集、宣传评论对应的属性集……每个属性集可看作一个视图。假设\(\pmb{x}^1\)为图像视图中的属性向量，\(\pmb{x}^2\)为声音视图中的属性向量，\(y\)为标记，如动作片，爱情片。\((<\pmb{x}^1, \pmb{x}^2>,y)\)就是多视图数据。

假设不同视图具有“相容性”，即其所包含的关于输出空间\(\mathscr{Y}\)的信息是一致的：\(\mathscr{Y}^1\)和\(\mathscr{Y}^2\)分别是从\(\pmb{x}^1\)和\(\pmb{x}^2\)判别的标记空间，\(\mathscr{Y}^1 = \mathscr{Y}^2 = \{爱情片，动作片\}\)。在此假设下，只从单一属性描述中判别其标记的确定性通常不及从多个属性描述中判别其标记，例如，仅凭图像信息认为“可能是动作片”，而仅凭声音信息也认为“可能是动作片”，当两者一起考虑时就有较大把握判别为“动作片”。在相容性的基础上，不同视图信息的互补性会给学习器的构建带来很多便利。

协同训练很好的利用了多视图的“相容互补性”。假设数据拥有两个充分且条件独立视图，“充分”是指每个视图都包含足以产生最优学习器的信息；“条件独立”指在给定类别标记条件下两个视图独立。
在此情形下，可用一个简单的办法利用未标记数据：

  1. 首先在每个视图上基于有标记样本分别训练出一个分类器；
  2. 让每个分类器分别去挑选自己“最有把握的”未标记样本赋予伪标记；
  3. 将伪标记样本提供给另一个分类器作为新增的有标记样本用于训练更新；
  4. 迭代进行上述过程，直到两个分类器不再发生变化，或达到预先设定的迭代次数为止。

若在每轮学习中都考察分类器在所有未标记样本上的分类置信度，会有很大的计算开销，因此在算法中使用了未标记样本缓冲池。分类置信度的估计则因基学习算法\(\mathscr{L}\)而异，例如使用朴素贝叶斯分类器，则可将后验概率转化为分类置信度；如使用SVM，则可将间隔大小转化为分类置信度。

理论证明显示出，若两个视图充分且条件独立，则可利用未标记样本通过协同训练将弱分类器的泛化性能提升到任意高。不过，视图的条件独立性在现实任务中通常很难满足，因此性能提升幅度不会那么大，但研究表明，即便在更弱的条件下，协同训练仍可有效地提升弱分类器的性能。

协同训练算法本身是为多视图数据而设计的，但此后出现了一些能在单视图数据上使用的变体算法，它们或是使用不同的学习算法、或使用不同的数据采样、甚至使用不同的参数设置来产生不同的学习器，也能有效地利用未标记数据来提升性能。此类算法事实上无需数据拥有多视图，仅需弱学习器之间具有显著的分歧（或差异），即可通过相互提供未标记样本的方式来提升泛化性能。不通试图、不同算法、不同数据采样、不同参数设置等，都仅是产生差异的渠道，而非必备条件。

基于分歧的方法只需采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模问题的影响，学习方法简单有效、理论基础相对坚实、适用范围较为广泛。

6. 半监督聚类

聚类是一种典型的无监督学习任务，然而在显示聚类任务中往往能获得一些额外的监督信息，于是可通过半监督聚类（semi-supervised clustering）来利用监督信息以获得更好的聚类效果。
聚类任务中获得监督信息大致分为两种：

  • 必连与勿连约束：必连指样本必属于同一个簇，勿连指样本必不属于同一个簇；
  • 少量的标记样本：提供少量的标记样本。

约束k均值（Constrained k-means）算法是利用第一类监督信息的代表，给定样本集\(D = \{\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m\}\)以及“必连”关系集合\(\mathscr{M}\)和“勿连”关系集合\(\mathscr{C}\)，\((\pmb{x}_i, \pmb{x}_j) \in \mathscr{M}\)表示\(\pmb{x}_i\)与\(\pmb{x}_j\)必属于同簇，\((\pmb{x}_i, \pmb{x}_j) \in \mathscr{C}\)表示\(\pmb{x}_i\)与\(\pmb{x}_j\)必不属于同簇。该算法是k均值算法的扩展，它在聚类过程中要确保\(\mathscr{M}\)和\(\mathscr{C}\)中的约束得以满足，否则将返回错误提示。

算法如下：

第二种监督信息是少量的有标记样本。给定样本集\(D = \{\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m\}\)，假定少量的有标记样本为\(S = \bigcup_{j=1}^k S_j \subset D\)，其中\(S_j \neq \emptyset\)为隶属于第\(j\)个聚类簇的样本。

使用：直接将有标记样本作为“种子”，用它们初始化k均值算法的k个聚类中心，并且在聚类簇迭代更新过程中不改变种子样本的簇隶属关系。这就得到了约束种子k均值（Constrained Seed k-means）算法。

算法如下：