【课堂笔记】标签传播算法Label Propagation Algorithm（LPA）

问题背景

  标签传播算法（Label Propagation Algorithm, LPA）主要解决的是数据标注不足的实际问题。在许多现实世界的机器学习任务中，获取大量标注数据（即带有正确标签的样本）成本高昂，例如需要专家参与（如医疗影像标注）或耗费大量时间（如语音转录）。
  未标注数据通常包含有关数据分布的宝贵信息，例如数据点之间的相似性或聚集模式（流形结构）。
  LPA通过构建图结构，基于数据的相似性（流形假设：相似的数据点倾向于具有相同标签）将已知标签传播到未标注数据，挖掘未标注数据的潜在结构。这是一种半监督学习的算法。

基本假设

（1）样本可用性假设：未标记的样本获取成本较低，所以有更多未标记的样本可供选择（相比已标记样本）
（2）流形假设：数据点在高维空间中分布在一个低维流形上，相似的数据点（即在流形上靠近的点）更有可能具有相同的标签。
（3）平滑性假设：模型的预测函数在数据空间中应该是平滑的
（4）簇假设：数据的不同类别形成分离的簇，决策边界应位于低密度区域，而不是穿过高密度区域。

算法步骤

（1）构建图结构
  将所有数据点（已标记和未标记，共 $M+N$ 个，其中 $M$ 是已标记数据，$N$ 是未标记数据）表示为图的节点。
  边的权重 $w_{i,j}$ 表示节点 $i$ 和 $j$ 之间的相似度（例如，基于欧氏距离、余弦相似度或高斯核）。通常只连接最近邻节点（通过 k-NN 或 $ϵ$-邻域方法）以减少计算复杂度。
（2）构建转移矩阵
  构造一个 $(M+N)\times (M+N)$ 的转移矩阵 $\mathbf{T}$，表示从节点 $j$ 到节点 $i$ 的归一化转移概率。其中
$${\mathbf{T}}_{i,j}=\frac{w_{i,j}}{\sum _k{w}_{i,k}}$$
  $\mathbf{T}$ 反映了标签传播的强度，基于数据点之间的相似性。
（3）初始化标签矩阵
  定义一个 $(M+N)\times C$ 的标签矩阵 $\mathbf{Y}$，其中 $C$ 是类别数。
  对于已标记数据，$\mathbf{Y}$ 的对应行初始化为独热编码（one-hot，例如 $[1,0,0]$ 表示类别 1）。
  对于未标记数据，$\mathbf{Y}$ 的对应行初始化为零向量或均匀分布。
（4）迭代传播标签
  迭代更新：$\mathbf{Y}\leftarrow \mathbf{TY}$，即通过转移矩阵传播标签概率。每次迭代后，归一化 $\mathbf{Y}$ 的每一行，使其表示有效的概率分布。
  对于已标记数据，固定其标签（将对应行重新设为独热编码），以防止标签被覆盖。
  重复迭代直到 $\mathbf{Y}$ 收敛（标签概率稳定）或达到最大迭代次数。
（5）输出预测
  收敛后，$\mathbf{Y}$ 的每一行表示对应数据点的类别概率分布。
  对未标记数据，取最大概率的类别作为最终预测标签。

数学原理解剖

  现在我们有了一张图$\mathbf{G}=(\mathbf{V},\mathbf{E})$，其中点集$|\mathbf{V}|=M+N$，边集 E = { e u , v = ( u , v , w u v ) } \mathbf{E} = \set{e_{u, v} = (u, v, w_{uv})} E={eu,v​=(u,v,wuv​)}，还有了一个标签矩阵 $\mathbf{Y}\in {\mathbb{R}}^{(M+N)\times C}$，一个转移矩阵$\mathbf{T}\in {\mathbb{R}}^{(M+N)\times (M+N)}$，我们来分析步骤中矩阵乘法在图上的意义：
（1）独热编码，初始化：如果某个点$i$的标签是$2$，标签集合为 { 1 , 2 , 3 } \set{1, 2, 3} {1,2,3}，则它的独热编码为$p_i^{(0)}=[0,1,0]$，这里实际上表示了它标签的概率分布。
  对于这个$i$（实际标签确定），则它标签为$2$的概率为$100\%$，其余为$0\%$；
  对于不确定标签的点，初始化为全零（注意这不是一个合法的概率分布，因为总和不为1，所以后续更新需要不断进行归一化）
（2）迭代更新：${\mathbf{Y}}^{(t+1)}=\mathbf{T}{\mathbf{Y}}^{(t)}$，每个节点的标签概率变成它所有邻居标签概率的加权平均，权重就是边的相似度。
  假设某个点第$t$次迭代的概率分布为$p_i^{(t)}=[p_{i,1}^{(t)},...,p_{i,C}^{(t)}]$，这是$\mathbf{Y}$的第$i$行；它对应的转移向量为$T_i=[T_{i,1},...,T_{i,(M+N)}]$，它是$\mathbf{T}$的第$i$行，则下一次更新的概率分布应为：
$$p_i^{(t+1)}=\underset{k=1}{\sum ^{M+N}}{T}_{i,k}{p}_k^{(t)}$$
即每个点$k$根据转移的权重把它们的分布加给点$i$。于是写成矩阵的样子也就是${\mathbf{Y}}^{(t+1)}=\mathbf{T}{\mathbf{Y}}^{(t)}$
（3）归一化：保证每个点的概率分布总和为$1$，否则不是个合法的概率。

算法收敛性

  怎么理解这个算法最终会趋于稳定？这里给出粗略的直观理解。
  关键在于有已知标签的点的存在，它们从始至终都是稳定的。而每次更新，不确定的点都会根据相似性从邻居那里获取信息，从而使信息不断在图中散布，稳定性从确定点开始不断影响不确定的点，最终使整张图趋于稳定。