基于图的半监督学习：标签传播算法（Label Propagation Algorithm）的原理与迭代过程
题目描述
在机器学习中，获取大量有标签数据成本高昂，而无标签数据则相对容易收集。半监督学习旨在利用少量有标签数据和大量无标签数据构建高性能模型。标签传播算法是一种基于图模型的半监督学习算法，其核心思想是构建一个图（节点表示数据样本，边表示样本间的相似度），让已标注节点的标签信息沿着图的边传播到未标注节点，最终为所有未标注节点预测标签。本题将详细讲解标签传播算法的原理、图构建方法、迭代传播过程及收敛性分析。
解题过程
1. 问题形式化
假设有 \(n\) 个数据样本，其中前 \(l\) 个样本有标签（类别已知），后 \(u = n - l\) 个样本无标签。每个样本 \(x_i\) 对应一个节点 \(v_i\)，目标是预测无标签样本的类别标签。算法将数据建模为一个图 \(G = (V, E)\)，其中 \(V\) 是节点集，\(E\) 是边集，边权重 \(w_{ij}\) 反映样本 \(x_i\) 和 \(x_j\) 的相似度。
2. 图的构建
构建图通常有两种方式：
- k-近邻图：每个节点只与最相似的 \(k\) 个节点连接。
- 全连接图：所有节点对之间都连接，权重由相似度函数定义，如高斯核函数：
\[ w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
其中 \(\sigma\) 是带宽参数，控制相似度衰减速度。权重矩阵 \(W\) 是一个 \(n \times n\) 的对称矩阵，且通常设 \(w_{ii} = 0\)。
3. 标签传播的迭代过程
定义标签矩阵 \(Y \in \mathbb{R}^{n \times C}\)，其中 \(C\) 是类别数。前 \(l\) 行对应有标签样本：若 \(x_i\) 属于第 \(c\) 类，则 \(Y_{ic} = 1\)，其他元素为0；后 \(u\) 行对应无标签样本，初始化为0。算法通过迭代更新所有节点的标签分布 \(F\)（与 \(Y\) 同维），步骤如下：
步骤3.1 计算转移概率矩阵
从权重矩阵 \(W\) 计算归一化的转移概率矩阵 \(P\)：
\[P_{ij} = \frac{w_{ij}}{\sum_{k=1}^n w_{ik}} \]
\(P_{ij}\) 表示从节点 \(i\) 到节点 \(j\) 的标签传播概率。矩阵 \(P\) 是行随机矩阵（每行和为1）。
步骤3.2 初始化与迭代更新
初始化标签分布矩阵 \(F^{(0)} = Y\)。迭代更新公式为：
\[F^{(t+1)} = P F^{(t)} \]
在每次迭代中，每个节点的新标签分布是其邻居节点当前标签分布的加权平均，权重为转移概率。但有标签节点的真实标签应在传播过程中保持固定，因此需修改更新规则。
步骤3.3 钳制有标签节点
确保有标签节点的标签不变：将前 \(l\) 个有标签节点“钳制”为其真实标签。定义矩阵 \(\tilde{P}\) 为将 \(P\) 的前 \(l\) 行替换为0（因有标签节点不接收传播），并设置一个对角矩阵 \(\tilde{Y}\)，其中前 \(l\) 行与 \(Y\) 相同，后 \(u\) 行为0。则更新公式修正为：
\[F^{(t+1)} = \tilde{P} F^{(t)} + \tilde{Y} \]
这样，有标签节点始终贡献其真实标签，而无标签节点接收邻居传播的标签。
4. 收敛性与解析解
上述迭代是一个线性系统，可证明收敛。将 \(F\) 分块为有标签部分 \(F_l\) 和无标签部分 \(F_u\)：
\[\begin{bmatrix} F_l \\ F_u \end{bmatrix}^{(t+1)} = \begin{bmatrix} I_l & 0 \\ P_{ul} & P_{uu} \end{bmatrix} \begin{bmatrix} F_l \\ F_u \end{bmatrix}^{(t)} + \begin{bmatrix} Y_l \\ 0 \end{bmatrix} \]
其中 \(P_{ul}\) 和 \(P_{uu}\) 是 \(P\) 的对应分块矩阵。由于有标签部分固定（\(F_l = Y_l\)），迭代收敛时 \(F_u\) 不再变化，得到稳态方程：
\[F_u = P_{ul} Y_l + P_{uu} F_u \]
整理得：
\[(I_u - P_{uu}) F_u = P_{ul} Y_l \]
这是一个线性方程组，可直接求解（无需迭代）：
\[F_u = (I_u - P_{uu})^{-1} P_{ul} Y_l \]
其中 \(I_u\) 是 \(u \times u\) 单位矩阵。由于 \(P_{uu}\) 是行随机矩阵的子块，其谱半径小于1，矩阵 \(I_u - P_{uu}\) 可逆，保证解唯一。
5. 预测与算法输出
对每个无标签样本 \(i\)，其预测类别为标签分布 \(F_u\) 中第 \(i\) 行最大概率对应的类别：
\[\hat{y}_i = \arg\max_{c} F_{ic} \]
算法最终输出所有无标签样本的预测标签，以及收敛时的标签分布矩阵 \(F\)。
总结
标签传播算法通过构建图模型，将标签信息从已标注节点传播到未标注节点，迭代过程可视为图上随机游走的平稳分布求解。其优势是直观高效，且可处理多分类问题；局限性是对图构建（如相似度度量、参数 \(\sigma\) 和近邻数 \(k\) ）敏感，可能受噪声影响。