13.2 Label Propagation算法#

在上一节内容中，我们详细地介绍了半监督学习算法中一种用于分类问题的Self-Training算法，其核心思想是先通过少量的标注数据来训练一个弱分类器，其次再通过这个弱分类器来对无标签样本进行标注并选择其中的有效部分作为样本的真实标签，然后再次以当前已有的标注数据来训练模型并对无标签的样本进行标注并反复迭代，最后直到达到停止条件时结束。在本节内容中，将会介绍另外一种基于图结构的半监督学习模型——标签传播算法（Label Propagation）。

如图13-3所示便是标签传播算法的学习路线图，我们将先介绍其对应的思想以及sklearn的建模过程，然后再来介绍其背后的原理、计算示例和收敛性证明等过程，最后再一步步来从零实现整个算法。

图 13-3 标签传播算法学习路线图

13.2.1 Label Propagation算法思想#

标签传播算法的基本思想认为，在样本空间中距离越是相近的样本点越有可能具有相同的样本标签[1]，而这一点也非常符合现实直觉。因此，在这样的假设条件下可以通过构建一个有向完全图来表示样本点之间的位置关系，其中图上的结点表示样本点，边表示两个结点之间的权重（样本点相距越近，则其对应的权重值便越大）。进一步，根据该权重图可以构造得到一个概率迁移矩阵$T$，其中$T_{ij}$表示样本点$j$转移到样本点$i$的概率。如果结点$i$是一个无标签的样本点，结点$j$是一个有标签的样本点，那么此时便可以根据$T_{ij}$的大小来判断样本点$i$是否与$j$具有相同的样本标签。

图 13-4 标签传播算法思想图

如图13-4所示，黑色圆点和白色圆点分别表示已知标签和未知标签的样本点，箭头表示传播方向，数值表示转移概率。根据标签传播算法的思想，白色样本点的所属类别可以通过黑色样本点到白色样本点的转移概率来进行确定。例如对于图13-4中间的白色样本点来说，其所属类别最有可能便是由右下角的黑色样本点所确定，因为此时对应的转移概率0.76在所有可能的转移情况中最大。

可以看出，标签传播算法的关键在于建立任意两个样本点之间转移的概率，然后通过已知标签的样本点来推断未知标签的样本点。

13.2.2 Label Propagation示例代码#

在sklearn中，我们可以从sklearn.semi_supervised中来导入标签传播算法LabelPropagation模块，以下完整示例代码可参见 AllBooKCode/Chapter13/C03_label_propagation.py 文件。同时，需要构造半监督学习所需要使用到的训练集，即将部分样本的标签置为-1，这是由模型在实现时所确定，示例代码如下：

1 def load_data():
2     x, y = load_iris(return_X_y=True)
3     x_train, x_test, y_train, y_test = \
4         train_test_split(x, y, test_size=0.3, random_state=2022)
5     rng = np.random.RandomState(20)
6     random_unlabeled_points = rng.rand(y_train.shape[0]) < 0.8
7     y_mixed = deepcopy(y_train)
8     y_mixed[random_unlabeled_points] = -1
9     return x_train, x_test, y_train, y_test, y_mixed

在上述代码中，第2~4行是导入原始数据集并进行训练集和测试集的划分。第5~8行则是将训练集中$80\%$样本的标签重置为-1，同时也保留了原始重置之前的标签便于后续在训练集上测试模型的效果。第9行是返回最后各个部分的结果。

进一步，可以导入LabelPropagation进行模型训练和测试，示例代码如下：

 1 from sklearn.semi_supervised import LabelPropagation
 2 def test_label_propagation():
 3     x_train, x_test, y_train, y_test, y_mixed = load_data()
 4     model = LabelPropagation(gamma=20,max_iter=1000)
 5     model.fit(x_train, y_mixed)
 6     y_pred = model.predict(x_train)
 7     print(f"模型在训练集上的准确率为: {accuracy_score(y_pred, y_train)}")
 8     y_pred = model.predict(x_test)
 9     print(f"模型在测试集上的准确率为: {accuracy_score(y_pred, y_test)}")
10 
11 if __name__ == '__main__':
12     test_label_propagation()

在上述代码中，第1行是导入标签传播算法模块。第4行是实例化LabelPropagation模型，其中gamma便是式(13-1)中的$\sigma$，max_iter指的是模型（第13.3.3节中计算标签矩阵$Y$）的迭代次数。第5行是模型的拟合过程。第6~9行是分别在训练集和测试集上的预测结果。

上述代码运行结束后可以得到类似如下所示的输出结果：

1 模型在训练集上的准确率为: 0.9619
2 模型在测试集上的准确率为: 1

13.3.3 Label Propagation算法原理#

在介绍完标签传播算法的思想及使用示例后我们再来详细介绍其背后的数学原理。设 $(x_1,y_1),(x_2,y_2),...,(x_l,y_l)$ 为已知标签的数据样本，其中$Y_L=\{y_1,y_2,...,y_l\}$ 是样本点对应的标签；同时样本的类别数为$C$，并且假定所有的类别均出现在 $Y_L$ 中。继续，设$(x_{l+1},y_{l+1}),(x_{l+2},y_{l+2}),...,(x_{l+u},y_{l+u})$ 为不含标签的样本点，其中 $Y_U=\{y_{l+1},y_{l+2},...,y_{l+u}\}$ 未知，且通常情况下$l\ll u$，即未知标签的样本远多于已知标签的样本。此时有 $X=\{x_1,...,x_{l+u}\}$，且$x_i\in R^D$。

根据标签传播算的思想可知，首先需要构建一个有向完全图，并完成任意两个样本点之间的权重计算，计算公式如式(13-1)所示

$$ w_{ij}=\exp\left(-\frac{d^2_{ij}}{\sigma^2}\right)=\exp\left(-\frac{\sum_{d=1}^D(x^d_i-x^d_j)^2}{\sigma^2}\right)\tag{13-1} $$

其中$\sigma$为控制权重的超参数，$w_{ij}$表示样本点$x_i$和$x_j$之间的距离权重。

通过式(13-1)计算任意两个样本点之间的距离权重后便可以得到一个结点与边之间的权重矩阵 $W$ ，并且还可以知道 $W$ 是一个对称矩阵，其形状为$(l+u,l+u)$。同时，值得一提的是这里还可以用其它距离来计算两个结点之间的距离权重。

进一步，定义形状为 $(l+u,l+u)$ 的概率迁移矩阵 $T$，且任意两个节点之间的转移概率计算公式为

$$ \begin{aligned} T_{ij}=P(j \to i)=\frac{w_{ij}}{\sum_{k=1}^{l+u}w_{kj}} \end{aligned}\tag{13-2} $$

其中 $T_{ij}$ 表示结点 $j$ 转移到结点 $i$ 的概率，同时需要注意的是 $T$ 并不是一个对称矩阵。可以看出，此时是对矩阵 $w$ 在列上进行归一化，即每一列的和为1。

接着，再定义一个形状为 $(l+u,C)$ 的标签矩阵 $\overline{Y}$，其每一行用于表示每个样本属于各个类别的概率分布。初始化时的结果如图13-8中第2个矩阵所示。

最后，只需要迭代如下3个步骤便可以求解得到未知标签样本的预测结果：

第1步：计算更新后的 $Y$

$$ Y=T\overline{Y}\tag{13-3} $$

第2步：在行上对 $Y$ 进行标准化

$$ \overline{Y}_{ij}=\frac{Y_{ij}}{\sum_{c=1}^CY_{ic}}\tag{13-4} $$

第3步：将 $\overline{Y}$ 中已知标签位置上的结果替换为原始的正确标签，然后重复前面两步直到收敛。

13.2.4 Label Propagation 计算示例#

在介绍完标签传播算法的基本原理之后，下面再通过一个实际的计算示例来展示其中的计算细节，同时也好再次从感官上来认识什么是标签传播算法。假设现在一共有a,b,c,d,e这5个样本点，类别标签分别为[0,1,1,-1,-1]，其中-1表示无标签，如图13-5所示。

图 13-5 标签传播计算示例图

如图13-5所示，5个样本点分别为[[0.5, 0.5], [1.5, 1.5], [2.5, 1.5], [1.5, 2.5], [3.5, 2.5]]。此时，根据式(13-1)可以计算得到权重矩阵$W$，如图13-6所示。

图 13-6 权重矩阵结果图

从图13-5中可以看出，样本b与样本d和样本c之间的距离最近，因此图13-6中对应的权重也是所有权重中最大的，为0.368。进一步，根据式(13-2)可以计算得到概率迁移矩阵如图13-7所示。

图 13-7 概率迁移矩阵图

接着，初始化标签矩阵 $Y$ 并根据式(13-3)和式(13-4)可以计算得到更新后的标签矩阵，如图13-8所示。

图 13-8 标签矩阵计算图

如图13-8所示便是标签矩阵的计算过程，其中最右边的矩阵便是更新后的标签矩阵（已归一化），不过这两个矩阵相乘的意义在哪里呢？

以样本点d为例，根据概率迁移矩阵可知，样本a转移到d的概率为0.006，其含义便是样本d的标签有0.6%的可能性和样本a的标签相同。同理，b转移到d的概率为0.196，c到d的概率为0.082，d到d的概率为0.654，e到d的概率为0.016。从图13-5也可以看出，b是所有样本点中距离d最近的样本点，因此样本d的标签最有可能和样本b的相同，计算过程如图13-9所示。