介绍
在机器学习中，已标记的数据是较少的，其价值是非常高的。但在现实情况下，获取未标记的数据常常是非常容易的，因此研究少量已标记大量未标记的半监督学习的算法非常必要。
本文主要整理了半监督学习的标签传递算法（Label Propagation Algorithm），通过将已标记的数据，按照传递矩阵，传递给未标记数据，从而得到了软标记的数据。基于软标记的数据在模型的准确性和泛化能力上都优于仅有少量标记的数据的模型。
样本介绍
对于N个样本数据，其中L个已标记，U个未标记数据，标记数据共有C分类，样本数据(\mathbf x_i, y_i)，其中i \in { 1,2,3,\cdots,N }，分类为y_1, y_2, \cdots,y_C，于是有
L + U = N
其中每个样本\mathbf x_i有m个属性，分别为(x_1, x_2, \cdots, x_m)。
对于C个类别，进行向量化处理，使用C维的航向量处理，其中y_1为(1,0,0,\cdots,0),
y_2为(0,1,0,\cdots,0)，那么y_C 就是(0,0,0,\cdots,1)，已标记标签矩阵定义为：
Y_L = (\mathbf y_1,\mathbf y_2, \cdots,\mathbf y_C)^T
未标记的矩阵记为：
Y_U = (\mathbf y_{C+1}, \mathbf y_{C+2}, \cdots, \mathbf y_N)
显然未标记矩阵是要计算的部分。
转移矩阵
对于整个样本空间，可以认为距离越近，属于同一类的可能性较大，类似于K最近最邻算法(KNN)。于是考虑权重与的欧式空间距离有关：
\omega_{ij} = \exp(-\frac{||\mathbf x_i – \mathbf x_j|| ^2}{\alpha^2})
其中\alpha 为参数。
根据样本的权重 即可定义出样本标签的转移矩阵：
P_{ij} = \frac{\omega_{ij}}{\sum\limits_{k} \omega_{ik}}
P_{ij} 表示节点i到节点j的转移概率。
算法
全部的标签矩阵为\mathbf Y=(\mathbf Y_L,\mathbf Y_U)^T,现在已经计算了状态转移矩阵，用状态转移矩阵乘以标签矩阵，就得到第一次转移以后标签矩阵,此时矩阵中存在不为1的数，标签的最终归类为向量中最大的分量。第一次转移矩阵中，已标记的部分也发生了转移，这部分数据是标记好的，一次重置为原来的Y_L，得到新的Y，继续用状态转移矩阵与Y相乘。如此迭代直到标签矩阵Y收敛。
算法的基本过程为：
- 状态转移矩阵乘以标签矩阵，\mathbf Y = \mathbf P \mathbf Y
- 重置已标记矩阵 \mathbf Y = \mathbf Y_L，原始的Y_L 覆盖以上的\mathbf Y部分
- 重复上述过程，直到\mathbf Y 收敛，计算结束。
优化算法
如果样本空间很大，对与计算的开销也是非常巨大。在上述迭代过程中，有部分计算是不必要的，目标是计算Y_U，那就直接计算未标记矩阵。
\mathbf P = \left( \begin{array}{cc} \mathbf P_{LL} & \mathbf P_{LU} \\ \mathbf P_{UL} & \mathbf P_{UU} \\ \end{array} \right)
\mathbf Y_U =\mathbf P_{UL} \mathbf P_{YL} + \mathbf P_{UU} \mathbf Y_U
\mathbf Y_U = (1 – \mathbf P_{UU})^{-1} \mathbf P_{UL} \mathbf Y_L
当数据量不大时，可以选择计算(1-\mathbf P_{UU})^{-1}，如果数据量很大，使用迭代会减少计算的消耗。只需要迭代至Y_U收敛即可。