基于图的半监督学习：标签传播算法（Label Propagation Algorithm）的迭代过程与收敛性分析
1. 题目描述
在机器学习中，当数据集中只有少量样本带有标签，而大部分样本无标签时，我们面临半监督学习问题。标签传播算法（Label Propagation, LP）是一种基于图的半监督学习算法，它利用数据点之间的相似性构建图结构，通过迭代传播过程，将少量有标签样本的标签信息扩散到大量无标签样本上，最终为所有节点预测标签。
核心思想：在图结构上，相似的节点（由边连接，边权重表示相似度）应有相同的标签。算法通过迭代地让每个节点的标签分布受其邻居节点的标签分布加权影响，最终使得整个图的标签分布达到稳定状态。
2. 解题过程
步骤1：问题定义与图构建
假设我们有 \(n\) 个数据点，其中前 \(l\) 个点有标签（标签数为 \(C\) 类），后 \(u = n - l\) 个点无标签。目标是为无标签点预测标签。
- 构建全连接图：
- 将每个数据点视为图中的一个节点。
- 计算任意两个节点 \(i\) 和 \(j\) 之间的相似度，通常使用高斯核（径向基函数）：
\[ w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
其中 $ \sigma $ 是带宽参数，控制相似度衰减速度。当 $ i = j $ 时，令 $ w_{ii} = 0 $。
- 定义权重矩阵 \(W \in \mathbb{R}^{n \times n}\)，其中 \(W_{ij} = w_{ij}\) 表示节点 \(i\) 和 \(j\) 之间的边权重。
- 计算度矩阵：
- 度矩阵 \(D\) 是一个对角矩阵，其对角线元素为每个节点的度（即与该节点相连的所有边的权重和）：
\[ D_{ii} = \sum_{j=1}^{n} W_{ij} \]
- 构建概率转移矩阵：
- 定义归一化的概率转移矩阵 \(P = D^{-1} W\)。其中 \(P_{ij}\) 表示从节点 \(i\) 随机游走到节点 \(j\) 的概率：
\[ P_{ij} = \frac{W_{ij}}{D_{ii}} \]
- 注意：\(P\) 的每一行和为1，因此它是随机矩阵。
步骤2：初始化标签矩阵
我们用一个 \(n \times C\) 的矩阵 \(Y\) 表示所有节点的标签分布（软标签）：
- 对于有标签节点 \(i\)（\(1 \leq i \leq l\)），其标签分布 \(Y_i\) 是 one-hot 向量。例如，如果节点 \(i\) 属于第 \(k\) 类，则 \(Y_{ik} = 1\)，其他元素为0。
- 对于无标签节点 \(i\)（\(l+1 \leq i \leq n\)），初始化时其标签分布是均匀分布或零向量，这里我们初始化为 \(Y_i = \mathbf{0}\)（后续迭代会更新）。
记初始标签矩阵为 \(F^{(0)} = Y\)。
步骤3：迭代传播过程
标签传播通过迭代更新每个节点的标签分布，使其受邻居节点的加权影响。迭代公式为：
\[F^{(t+1)} = P F^{(t)} \]
其中 \(F^{(t)} \in \mathbb{R}^{n \times C}\) 是第 \(t\) 次迭代后所有节点的标签分布矩阵。
物理意义：每个节点的新标签分布是其所有邻居节点当前标签分布的加权平均，权重由转移概率 \(P\) 决定。相似度越高（边权重越大）的邻居对当前节点的标签影响越大。
保持有标签节点的标签不变：在每次迭代后，我们需要将有标签节点的标签分布重置为初始真实标签，以确保有标签信息不被传播过程稀释。即：
\[F^{(t+1)}_{i} = Y_i, \quad \text{对于 } i = 1, 2, \dots, l \]
这相当于在每次迭代中，将有标签节点的行替换为初始 one-hot 向量。
因此，完整的迭代更新分为两步：
- 传播：\(\tilde{F}^{(t+1)} = P F^{(t)}\)
- 固定有标签节点：\(F^{(t+1)}_{i} = Y_i\)（对前 \(l\) 行）
步骤4：收敛性与停止条件
理论上，可以证明在满足一定条件下，迭代过程会收敛到一个固定点。我们可以通过以下方式判断收敛：
- 计算相邻两次迭代的标签矩阵变化：\(\|F^{(t+1)} - F^{(t)}\|_F\)（Frobenius 范数），当小于预设阈值 \(\epsilon\)（如 \(10^{-6}\)）时停止。
- 或者设置最大迭代次数 \(T_{\text{max}}\)（如 1000 次）。
收敛性分析：
将节点分为有标签集 \(L\) 和无标签集 \(U\)。将矩阵分块：
\[P = \begin{bmatrix} P_{LL} & P_{LU} \\ P_{UL} & P_{UU} \end{bmatrix}, \quad F = \begin{bmatrix} F_L \\ F_U \end{bmatrix}, \quad Y = \begin{bmatrix} Y_L \\ Y_U \end{bmatrix} \]
由于每次迭代后固定 \(F_L = Y_L\)，无标签部分的更新为：
\[F_U^{(t+1)} = P_{UL} Y_L + P_{UU} F_U^{(t)} \]
这是一个线性迭代系统，其收敛性取决于矩阵 \(P_{UU}\) 的谱半径。由于 \(P\) 是随机矩阵且无标签节点不与自身完全连接，可以证明 \(\rho(P_{UU}) < 1\)，因此迭代收敛。最终解为：
\[F_U^* = (I - P_{UU})^{-1} P_{UL} Y_L \]
这可以看作是一个解析解，但直接求逆计算量大，故通常用迭代法。
步骤5：预测与分类
迭代收敛后，得到最终的标签分布矩阵 \(F^*\)。对于每个无标签节点 \(i\)（\(i > l\)），取其标签分布中概率最大的类别作为预测标签：
\[\hat{y}_i = \arg\max_{c} F^*_{ic} \]
如果输出需要软标签（概率分布），则直接使用 \(F^*_i\)。
3. 算法总结与关键点
- 核心：基于图结构的标签平滑性假设，相似节点应有相似标签。
- 优点：简单直观，无需复杂优化，仅需矩阵迭代。
- 缺点：
- 计算复杂度为 \(O(n^2)\)（因需构建全连接图），大规模数据需使用稀疏近似（如k近邻图）。
- 对噪声标签敏感，可能传播错误标签。
- 结果受相似度度量（带宽 \(\sigma\)）影响较大。
- 变体：可加入正则化项，将问题形式化为最小化正则化损失函数，并与图拉普拉斯正则化相联系。
通过以上步骤，标签传播算法完成了从构建图、初始化、迭代传播到最终预测的全过程。