半监督学习

发表于 2024-12-04 更新于 2024-12-11 阅读次数： Waline：本文字数： 7.1k 阅读时长 ≈ 26 分钟

背景

未标记样本

我们有训练样本集 $D_{l}=\left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^l$ ，这 $l$ 个样本的类别标记已知，称为「有标记」（labeled）样本；此外，还有 $D_{u}=\left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=l+1}^{l+u}$ ，其中 $l \ll u$ ，这 $u$ 个样本的类别标记未知，称为「未标记」（unlabeled）样本。

若直接使用传统监督学习技术，则仅有 $D_{l}$ 能用于构建模型， $D_{u}$ 所包含的信息被浪费了；另一方面，若 $D_{l}$ 较小，则由于训练样本不足，学得模型的泛化能力往往不佳。那么，能否在构建模型的过程中将 $D_{u}$ 利用起来呢?

一种简单的做法是将 $D_u$ 中的示例全部标记后用于学习，但这样做的代价过高。

可以用 $D_l$ 先训练一个模型，使用这个模型在 $D_u$ 中挑选一个样本进行问询，得到新的有标记样本，再将其加入 $D_l$ 重新训练一个模型。若每次都能挑出对改善模型性能帮助较大的样本进行标记，则只需进行较少次问询就能构建出较强的模型，从而大幅降低标记成本。

这样的学习方法称为「主动学习」（active learning），其目标是使用尽可能少的「查询」（query）来获得尽可能好的性能。

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

未标记样本虽并未直接包含标记信息，但若它们与有标记样本是从同样的数据源 i.i.d. 采样而来，则它们所包含的关于数据分布的信息对建立模型大有裨益。

如下图所示，若基于图中的一个正例和一个反例，由于待判别的样本恰处于两者中间，大体上只能随机猜测。若能观察图中的未标记样本，可以有把握地判别为正例：

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

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

最常见的是「聚类假设」（cluster assumption），即假设数据存在簇结构，同一个簇的样本属于同一个类别。上图就是基于聚类假设来利用未标记样本。

另一种常见假设是「流形假设」（manifold assumption），即假设数据分布在一个流形结构上，邻近的样本具有相似的输出值。「邻近」程度常用「相似」程度来刻画，因此流形假设可以看作是聚类假设的推广，而且因为对于输出值没有限制，因此比聚类假设适用范围更广。

这两个假设本质都是「相似的样本具有相似的输出」这个基本假设。

半监督学习可以进一步划分为：

纯半监督学习（pure semi-supervised learning）：假定训练数据中的未标记样本并非待预测的数据；
直推学习（transductive learning）：假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能。

直观来说，纯半监督学习基于「开放世界」假设，希望学得模型能适用于训练过程中未观察到的数据；直推学习是基于「封闭世界」假设，仅试图对学习过程中观察到的未标记样本进行预测。

生成式方法

生成式方法（generative methods）是直接基于生成式模型的方法。此类方法假设所有数据（无论有无标记），都是由同一个潜在模型「生成」的。

这个假设使得我们能通过潜在模型的参数将未标记数据和学习目标联系起来，未标记数据的标记可看作模型的缺失参数，通常可基于 EM 算法进行极大似然估计求解。

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

给定样本 $\bm{x}$ ，其真实类别标记 $y \in \mathcal{Y}$ ，其中 $\mathcal{Y} = \left\lbrace 1, 2, \dots, N \right\rbrace$ 为所有可能的类别。

假设样本由高斯混合模型生成，且每个类别对应一个高斯混合成分，即数据样本基于如下概率密度生成：

$p(\bm{x}) = \sum_{i=1}^{N} \alpha_i \cdot p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i)$

其中混合系数 $\alpha_i \ge 0,\, \displaystyle \sum_{i=1}^{N}\alpha_i = 1$ ， $p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i)$ 是样本 $\bm{x}$ 属于第 $i$ 个高斯混合成分的概率， $\bm{\mu}_i, \bm{\Sigma}_i$ 是该高斯混合成分的参数。 $p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i)$ 表示样本 $\bm{x}$ 属于该高斯混合成分的概率，有 $p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i) = \dfrac{1}{(2\pi)^{d/2} \cdot |\bm{\Sigma}_i|^{1/2}} \cdot \exp\left( -\frac{1}{2} (\bm{x} - \bm{\mu}_i)^\intercal \bm{\Sigma}_i^{-1} (\bm{x} - \bm{\mu}_i) \right)$ 。

令 $f(\bm{x}) \in \mathcal{Y}$ 表示模型 $f$ 对 $\bm{x}$ 的预测标记， $\Theta \in \left\lbrace 1, 2, \dots, N \right\rbrace$ 表示样本 $\bm{x}$ 隶属的高斯混合成分。最大化后验概率有

$\begin{aligned} f(\bm{x}) &= \argmax_{j \in \mathcal{Y}} p(y=j \mid \bm{x}) \\ &= \argmax_{j \in \mathcal{Y}} \sum_{i=1}^{N} p(y=j, \Theta=i \mid \bm{x}) \\ &= \argmax_{j \in \mathcal{Y}} \sum_{i=1}^{N} p(y=j \mid \Theta=i, \bm{x}) \cdot p(\Theta=i \mid \bm{x}) \\ \end{aligned}$

其中

$p(\Theta = i \mid \bm{x}) = \dfrac{\alpha_i \cdot p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i)}{\sum\limits_{k=1}^{N} \alpha_k \cdot p(\bm{x} \mid \bm{\mu}_k, \bm{\Sigma}_k)}$

为样本 $\bm{x}$ 由第 $i$ 个高斯混合成分生成的后验概率， $p(y=j \mid \Theta=i, \bm{x})$ 为样本 $\bm{x}$ 由第 $i$ 个高斯混合成分生成且类别为 $j$ 的概率。

由于假设每个类别对应一个高斯混合成分，因此 $p(y = j \mid \Theta = i, \bm{x})$ 仅与样本 $\bm{x}$ 所属的高斯混合成分 $\Theta$ 有关，可用 $p(y = j \mid \Theta = i)$ 代替。

不失一般性，假定第 $i$ 个类别对应于第 $i$ 个高斯混合成分，即 $p(y = j \mid \Theta = i) = 1$ 当且仅当 $i = j$ ，否则 $p(y = j \mid \Theta = i) = 0$ 。

上式估计 $P(y = j \mid \Theta = i, \bm{x})$ 需知道样本的标记，因此仅能使用有标记数据；而 $p(\Theta = i \mid \bm{x})$ 不涉及样本标记，因此有标记和无标记数据均可利用，通过引入大量的未标记数据，对这一项的估计可望（？）由于数据量的增长而更为准确，于是上式整体的估计可能会更准确。由此可清楚看出未标记数据何以能辅助提高分类模型的性能。

假设所有样本独立同分布，且都是有同一个高斯混合模型生成的。用极大似然法来估计高斯混合模型的参数 $\left\lbrace (\alpha_i, \bm{\mu}_i, \bm{\Sigma}_i) \mid 1 \le i \le N \right\rbrace,\, D_l \cup D_u$ 的对数似然是

$\begin{aligned} LL(D_l \cup D_u) &= \sum_{(\bm{x}_{j}, y_{j}) \in D_l} \ln \left( \sum_{i=1}^N \alpha_i \cdot p(\bm{x}_{j} \mid \bm{\mu}_i, \bm{\Sigma}_i) \cdot p(y_{j} \mid \Theta = i, \bm{x}_{j}) \right) \\ &\phantom{=}+ \sum_{\bm{x}_{j} \in D_u} \ln \left( \sum_{i=1}^N \alpha_i \cdot p(\bm{x}_{j} \mid \bm{\mu}_i, \bm{\Sigma}_i) \right) \end{aligned}$

上面两项分别是：

基于有标记数据 $D_l$ 的有监督项；
基于未标记数据 $D_u$ 的无监督项。

高斯混合模型参数估计可用 EM 算法求解，迭代更新式如下：

E 步：根据当前模型参数计算未标记样本 $\bm{x}_{j}$ 属于各高斯混合成分的概率

$\gamma_{ji} = \dfrac{\alpha_i \cdot p(\bm{x}_{j} \mid \bm{\mu}_i, \bm{\Sigma}_i)}{\sum\limits_{k=1}^{N} \alpha_k \cdot p(\bm{x}_{j} \mid \bm{\mu}_k, \bm{\Sigma}_k)}$

M 步：基于 $\gamma_{ji}$ 更新模型参数，其中 $l_i$ 表示第 $i$ 类的有标记样本数目

$\begin{aligned} \bm{\mu}_i &= \dfrac{1}{\sum_{\bm{x}_{j} \in D_u}\gamma_{ji} + l_i} \left( \sum_{\bm{x}_{j} \in D_u} \gamma_{ji} \bm{x}_{j} + \sum_{(\bm{x}_{j}, y_{j}) \in D_l, y_{j} = i} \bm{x}_{j} \right) \\ \bm{\Sigma}_i &= \dfrac{1}{\sum_{\bm{x}_{j} \in D_u}\gamma_{ji} + l_i} \left( \sum_{\bm{x}_{j} \in D_u} \gamma_{ji} (\bm{x}_{j} - \bm{\mu}_i)(\bm{x}_{j} - \bm{\mu}_i)^\intercal + \sum_{(\bm{x}_{j}, y_{j}) \in D_l, y_{j} = i} (\bm{x}_{j} - \bm{\mu}_i)(\bm{x}_{j} - \bm{\mu}_i)^\intercal \right) \\ \alpha_i &= \dfrac{1}{m} \left( \sum_{\bm{x}_{j} \in D_u} \gamma_{ji} + l_i \right) \end{aligned}$

以上过程不断迭代直至收敛，即可获得模型参数。然后由 $p(\Theta = i \mid \bm{x})$ 与 $f(\bm{x})$ 可对样本进行分类。

将上述过程中的高斯混合模型换成混合专家模型，朴素贝叶斯模型等即可推导出其他的生成式半监督学习算法。

此类方法简单、易于实现，在有标记数据极少的情形下往往比其他方法性能更好。

然而，此类方法有一个关键：模型假设必须准确，即假设的生成式模型必须与真实数据分布吻合；否则利用未标记数据反而会显著降低泛化性能。

半监督支持向量机

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

在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面。而在考虑未标记样本后，S3VM 试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面，如下图所示：

这里的基本假设是「低密度分隔」（low-density separation），这是聚类假设在考虑线性超平面划分后的推广。

S3VM 最著名的是 TSVM(Transductive Support Vector Machine)。

TSVM 试图考虑对无标记样本进行各种可能的标记指派（label assignment），即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

下面是形式化的说明。给定训练数据 $D_l \cup D_u$ ，其中 $D_l = \left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^l$ 为有标记样本， $D_u = \left\lbrace \bm{x}_i \right\rbrace_{i=l+1}^{l+u}$ 为未标记样本， $y_i \in \left\lbrace -1, 1 \right\rbrace$ 。令 $m = l + u$ 。

TSVM 的学习目标是为 $D_u$ 中的样本给出预测标记 $\hat{\bm{y}} = (\hat{y}_{l+1}, \dots, \hat{y}_{l+u}),\, \hat{y}_i \in \left\lbrace -1, 1 \right\rbrace$ ，使得

$\begin{aligned} \min_{\bm{w}, b, \hat{\bm{y}}, \bm{\xi}} &\dfrac{1}{2} \left\lVert \bm{w} \right\rVert_2^2 + C_l \sum_{i=1}^l \xi_i + C_u \sum_{i=l+1}^m \xi_i\\ \quad \text{s.t.}\quad & y_i(\bm{w}^\intercal \bm{x}_i + b) \ge 1 - \xi_i,\, \forall i = 1, 2, \dots, l\\ & \hat{y}_i(\bm{w}^\intercal \bm{x}_i + b) \ge 1 - \xi_i,\, \forall i = l+1, \dots, m\\ & \xi_i \ge 0,\, \forall i = 1, 2, \dots, m \end{aligned}$

其中

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

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

具体来说，它先利用有标记样本学得一个 SVM，即忽略上式关于 $D_u$ 与 $\hat{\bm{y}}$ 的项及约束。然后利用这个 SVM 对未标记数据进行「标记指派」（label assignment），即将 SVM 的预测结果作为「伪标记」（pseudo-label）赋予未标记样本。

此时 $\hat{\bm{y}}$ 成为已知，将其代入上式可得标准 SVM 问题，于是可求解出新的划分超平面和松弛向量。这时候未标记样本的伪标记很可能并不准确，因此 $C_u$ 要设置为比 $C_l$ 小的值，使有标记样本所起的作用更大。

接下来 TSVM 找出两个标记指派为异类，且很可能发生错误的未标记样本，交换它们的标记，重新基于上式求解出更新后的划分超平面和松弛向量……

标记指派调整完成后，逐渐增大 $C_u$ 以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直到 $C_u = C_l$ 为止。此时求解得到的 SVM 不仅给未标记的样本提供了标记，还能对训练过程中未见的示例进行预测。

TSVM 算法流程

蓝框中，若存在一对未标记样本 $\bm{x}_i, \bm{x}_{j}$ ，其标记指派 $\hat{y}_i, \hat{y}_{j}$ 不同，且对应的松弛变量满足 $\xi_i + \xi_{j} > 2$ ，则意味着 $\hat{y}_i$ 和 $\hat{y}_{j}$ 很可能是错误的，需对而这进行交换后重新求解，这样每轮迭代后可使上面优化目标的目标函数值下降。

在对未标记样本进行标记指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类，这将对 SVM 的训练造成困扰。为了减轻类别不平衡性所造成的不利影响，可对上面的算法稍加改进：

将优化目标中的 $C_u$ 项拆分为 $C_u^{+}, C_u^{-}$ 两项，分别对应于基于伪标记而当作正、反例使用的未标记样本，并在初始化时令 $C_u^{+} = \dfrac{u_{-}}{u_{+}}C_u^{-}$ ，其中 $u_{+}, u_{-}$ 为基于伪标记而当作正、反例使用的未标记样本数目。

搜寻标记指派可能出错的每一对未标记样本进行调整，仍是一个涉及巨大计算开销的大规模优化问题。因此，半监督 SVM 研究的一个重点是如何设计出高效的优化求解策略。

图半监督学习

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高（或相关性很强），则对应的结点之间存在一条边，边的强度（strength）正比于样本之间的相似度（或相关性）。

我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点则尚未染色。于是，半监督学习就对应于「颜色」在图上扩散或传播的过程。

由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。

二分类问题

先基于 $D_l \cup D_u$ 构建一个图 $G = (V, E)$ ，其中顶点集 $V = \left\lbrace \bm{x}_1, \dots, \bm{x}_{l+u} \right\rbrace$ 。

边集 $E$ 可表示为一个「亲和矩阵」（affinity matrix），常基于高斯函数定义为

$\mathbf{W}_{ij} = \begin{cases} \exp\left( -\dfrac{\| \bm{x}_i - \bm{x}_j \|^2}{2\sigma^2} \right), & \text{if } i \ne j \\ 0, & \text{otherwise} \end{cases}$

其中 $i, j \in \left\lbrace 1, 2, \dots, m \right\rbrace$ ，而 $\sigma$ 是用户指定的高斯函数带宽参数。

假定从图 $G = (V, E)$ 将学得一个实值函数 $f\colon V \to \R$ ，其对应的分类规则为 $y_i = \operatorname{sign}(f(\bm{x}_i)), y_i \in \left\lbrace -1, 1 \right\rbrace$ 。

直观上看，相似的样本应具有相似的标记，于是可定义关于 $f$ 的能量函数（energy function）：

$\begin{aligned} E(f) &= \dfrac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \mathbf{W}_{ij} (f(\bm{x}_i) - f(\bm{x}_j))^2 \\ &= \dfrac{1}{2} \left( \sum_{i=1}^{m} d_i f^2(\bm{x}_i) + \sum_{j=1}^{m} d_j f^2(\bm{x}_j) - 2 \sum_{i=1}^{m} \sum_{j=1}^{m} \mathbf{W}_{ij} f(\bm{x}_i) f(\bm{x}_j) \right)\\ &= \sum_{i=1}^{m}d_i f^2 (\bm{x}_i) - \sum_{i=1}^{m} \sum_{j=1}^{m} \mathbf{W}_{ij} f(\bm{x}_i) f(\bm{x}_j)\\ &= \bm{f}^\intercal(\mathbf{D} - \mathbf{W}) \bm{f} \end{aligned}$

其中 $\bm{f} = (\bm{f}_l^\intercal \bm{f}_u^\intercal)^\intercal$ ， $\bm{f}_l = (f(\bm{x}_1); \dots; f(\bm{x}_l))$ 与 $\bm{f}_u = (f(\bm{x}_{l+1}); \dots; f(\bm{x}_{l+u}))$ 分别为 $f$ 在有标记样本与未标记样本上的预测结果， $\mathbf{D} = \operatorname{diag}(d_1, \dots, d_{l+u})$ 是一个对角矩阵，对角元素 $d_i = \sum_{j=1}^{l+u}\mathbf{W}_{ij}$ 为矩阵 $\mathbf{W}$ 的第 $i$ 行元素的和。

具有最小能量的函数 $f$ 在有标记样本上满足 $f(\bm{x}_i) = y_i$ ，在未标记样本上满足 $\bm{\Delta} \bm{f} = \bm{0}$ ，其中 $\bm{\Delta} = \mathbf{D} - \mathbf{W}$ 为拉普拉斯矩阵（Laplacian matrix）。

采用分块矩阵表示方法，有

$\mathbf{W} = \begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix}, \quad \mathbf{D} = \begin{bmatrix} \mathbf{D}_{ll} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu} \end{bmatrix}$

则能量函数可写为

$\begin{aligned} E(f) &= (\bm{f}_l^\intercal \bm{f}_u^\intercal) \begin{bmatrix} \mathbf{D}_{ll} - \mathbf{W}_{ll} & -\mathbf{W}_{lu} \\ -\mathbf{W}_{ul} & \mathbf{D}_{uu} - \mathbf{W}_{uu} \end{bmatrix} \begin{bmatrix} \bm{f}_l \\ \bm{f}_u \end{bmatrix} \\ &= \bm{f}_l^\intercal (\mathbf{D}_{ll} - \mathbf{W}_{ll}) \bm{f}_l + \bm{f}_u^\intercal (\mathbf{D}_{uu} - \mathbf{W}_{uu}) \bm{f}_u - 2 \bm{f}_u^\intercal \mathbf{W}_{ul} \bm{f}_l \end{aligned}$

由 $\dfrac{\partial E(f)}{\partial \bm{f}_u} = \bm{0}$ 有

$\bm{f}_u = (\mathbf{D}_{uu} - \mathbf{W}_{uu})^{-1} \mathbf{W}_{ul} \bm{f}_l$

令

$\begin{aligned} \mathbf{P} &= \mathbf{D}^{-1} \mathbf{W} = \begin{bmatrix} \mathbf{D}_{ll}^{-1} & \bm{0}_{lu}\\ \bm{0}_{ul} & \mathbf{D}_{uu}^{-1} \end{bmatrix} \begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix} \\ &= \begin{bmatrix} \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{bmatrix} \end{aligned}$

即 $\mathbf{P}_{uu} = \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu},\, \mathbf{P}_{ul} = \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul}$ ，则有

$\begin{aligned} \bm{f}_u &= (\mathbf{D}_{uu}(\mathbf{I} - \mathbf{D}_{uu}^{-1} \mathbf{W}_{uu}))^{-1} \mathbf{W}_{ul} \bm{f}_l\\ &= (\mathbf{I} - \mathbf{P}_{uu})^{-1} \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul} \bm{f}_l\\ &= (\mathbf{I} - \mathbf{P}_{uu})^{-1} \mathbf{P}_{ul} \bm{f}_l \end{aligned}$

于是，将 $D_l$ 上的标记信息作为 $f_l = (y_1; \dots; y_l)$ 代入上式，即可利用求得的 $\bm{f}_u$ 对未标记样本进行预测。

多分类问题

上面是针对二分类问题的「单步式」标记传播（label propagation）方法，下面会介绍一个适用于多分类问题的「迭代式」标记传播方法。

假定 $y_i \in \mathcal{Y}$ 仍基于 $D_l \cup D_u$ ，构建一个图 $G = \left\langle V, E \right\rangle$ ，其他类似的定义不变。

定义一个 $(l + u) \times |\mathcal{Y}|$ 的非负标记矩阵 $\mathbf{F} = (\mathbf{F}_1^\intercal, \dots, \mathbf{F}_{|\mathcal{Y}|}^\intercal)^\intercal$ ，其中 $\mathbf{F}_i = (\mathbf{F}_{i 1}, \dots, \mathbf{F}_{i |\mathcal{Y}|})$ 为示例 $\bm{x}_i$ 的标记向量，相应的分类规则为

$y_i = \argmax_{1 \le j \le |\mathcal{Y}|} \mathbf{F}_{ij}$

对于 $i = 1, \dots, m;\; j = 1, \dots, |\mathcal{Y}|$ ，将 $\mathbf{F}$ 初始化为

$\mathbf{F}(0) = \mathbf{Y}_{ij} = \begin{cases} 1, & \text{if } (1 \le i \le l) \text{ and } (y_i = j)\\ 0, & \text{otherwise} \end{cases}$

即 $\mathbf{Y}$ 的前 $l$ 行就是有 $l$ 个有标记样本的标记向量。

基于 $\mathbf{W}$ 构造一个标记传播矩阵 $\mathbf{S} = \mathbf{D}^{-1 / 2} \mathbf{W} \mathbf{D}^{-1 / 2}$ ，其中 $\mathbf{D}^{-1 / 2} = \operatorname{diag}\left( \dfrac{1}{\sqrt{d_1}}, \dots, \dfrac{1}{\sqrt{d_{l+u}}} \right)$ 。

于是有迭代计算式

$\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\limits_{t \to \infty} \mathbf{F}(t) = (1 - \alpha)(\mathbf{I} - \alpha \mathbf{S})^{-1} \mathbf{Y}$

由 $\mathbf{F}^{*}$ 可得未标记样本的标记 $(\hat{y}_{l+1}, \dots, \hat{y}_{l + u})$ 。

算法描述如下：

上面的算法对应于「正则化框架」

$\min_{\mathbf{F}} \dfrac{1}{2} \left( \sum_{i, j = 1}^{l + u} \mathbf{W}_{ij} \left\lVert \dfrac{1}{\sqrt{d_i}} \mathbf{F}_i - \dfrac{1}{\sqrt{d_{j}}} \mathbf{F}_{j} \right\rVert^2 \right) + \mu \sum_{i = 1}^l \left\lVert \mathbf{F}_i - \mathbf{Y}_i \right\rVert^2$

其中 $\mu > 0$ 为正则化参数。

$\mu = \dfrac{1 - \alpha}{\alpha}$ 时，上式的最优解恰为上面算法的迭代收敛解 $\mathbf{F}^{*}$ 。

上式第二项是迫使学得结果在有标记样本上的预测与真实标记
尽可能相同，而第一项则迫使相近样本具有相似的标记。这与 $E(f) = \bm{f}^\intercal(\mathbf{D} - \mathbf{W}) \bm{f}$ 都是基于半监督学习的基本假设。不同的是上式考虑离散的类别标记，而 $E(f)$ 则是考虑输出连续值。

图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。

但此类算法的缺陷也相当明显，

其存储开销高；
由于构图过程仅能考虑训练样本集，难以判知新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制。

基于分歧的方法

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

协同训练（co-training）是基于分歧的方法的重要代表，它最初是基于「多视图」数据设计的，因此也被看作「多视图学习」（multi-view learning）的代表。

在不少现实应用中，一个数据对象往往同时拥有多个「属性集」（attribute set），每个属性集就构成了一个视图（view）。例如对一部电影来说，它拥有多个属性集：图像画面信息所对应的属性集、声音信息所对应的属性集、字幕信息所对应的属性集等。每个属性集都可看作一个视图。

为简化讨论，暂且仅考虑图像画面属性集所构成的视图和声音属性集所构成的视图。于是一个电影片段可表示为样本 $\left(\left\langle \bm{x}^1, \bm{x}^2 \right\rangle, y\right)$ ，其中 $\bm{x}^i$ 是样本在视图 $i$ 中的示例，即基于该视图属性描述而得的属性向量。在这个例子中， $\bm{x}^1$ 为图像画面属性集所对应的属性向量， $\bm{x}^2$ 为声音属性集所对应的属性向量。 $y$ 是标记，假定是电影的类型，例如「恋爱」「喜剧」等。于是 $\left(\left\langle \bm{x}^1, \bm{x}^2 \right\rangle, y\right)$ 这样的数据就是多视图数据。

假设不同视图具有相容性（compatibility），即其所包含的关于输出空间 $\mathcal{Y}$ 的信息是一致的。对上面的例子，令 $\mathcal{Y}^1, \mathcal{Y}^2$ 分别表示从两个信息判别的标记空间，则有 $\mathcal{Y} = \mathcal{Y}^1 = \mathcal{Y}^2$ 。