Skip to content
返回搜索结果

标签传播

提出者
Zhu, X. & Ghahramani, Z.
年份
2002
类型
Graph-based semi-supervised classification

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

标签传播是一种基于图的半监督学习算法,由Zhu和Ghahramani于2002年提出,它通过在相似性图的边上迭代地扩散标签信息,将少量标记节点的类别标签传播到大量未标记节点,从而利用数据的流形结构。

方法背后的直觉

设想一个社交网络,其中一些人已经被分配了一个类别。谣言自然传播:每个人倾向于采纳其亲近邻居中最常见的标签。标签传播将这种直觉形式化——它构建一个加权图,其中相似的数据点通过强边连接,然后让已知标签逐步向外流动,直到每个未标记的点吸收了足够多的信号以进行分类。由于扩散遵循数据的几何形状而非任意决策边界,因此即使标记样本稀少,它也能产生高度准确的预测。

历史学

Zhu(Jerry)Xiaojin和Ghahramani Zoubin于2002年在卡内基梅隆大学的技术报告(CMU-CALD-02-107)中引入了标签传播。次年,Zhu、Ghahramani和John Lafferty在ICML 2003会议上发表了密切相关的“高斯场和调和函数”框架,通过随机游走和高斯马尔可夫随机场提供了概率解释。这些工作在2000年代中期引发了一波基于图的半监督方法。Dengyong Zhou及其同事于2004年提出了标签传播(Label Spreading)——一种正则化变体,允许标签信息部分覆盖强制标签,从而提高了对噪声注释的鲁棒性。这两种方法现在都是半监督学习基准的标准基线,并包含在广泛使用的机器学习库中。随着2010年代图神经网络的兴起,标签传播成为一个概念前身和有竞争力的基线,因其简单性和闭式保证而仍被引用。

何时使用

当标记样本相对于总数据集大小稀少,数据具有相似性图可以捕获的底层聚类或流形结构,并且有理由相信平滑性假设成立——即附近的点(在特征空间中)倾向于共享相同的标签时,标签传播是适用的。典型场景包括带有少量标注文档的文本分类、带有稀疏人工标签的图像分类以及网络节点分类。该方法要求图是连通的(或者至少每个未标记节点都可以从一个标记节点到达)。当特征空间不反映语义相似性、决策边界穿过密集区域或所有数据已标记时,它不适用。

局限与注意事项

  • 可扩展性:对于大型数据集,存储和操作n x n权重矩阵是不可行的,除非进行稀疏近似。
  • 图构建对核带宽sigma和邻域大小k的选择敏感;选择不当会严重降低准确性。
  • 假设平滑性(聚类)假设:违反它——当决策边界穿过密集区域时——会导致系统性误分类。
  • 默认情况下是归纳的:对新的、未见过测试点的预测需要重新运行算法或进行归纳扩展。
  • 标记节点上的标签噪声会传播并可能破坏图的大部分。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 有效地利用未标记数据,用极少的标记样本获得强大的准确性。
  • 闭式收敛保证:迭代更新总是达到唯一的固定点。
  • 自然地处理多类问题,无需修改。
  • 直观的几何解释,基于图扩散和调和分析。
  • 除了图构建选择(核带宽、邻域大小)之外,没有需要优化的模型参数。

应用

  • 文本和文档分类,当只有一小部分文档带有手动分配的标签时。
  • 图像或视频标注,其中手动标注成本高昂且未标记图像丰富。
  • 社交网络和引用图节点分类(例如,推断用户兴趣或论文主题)。
  • 生物信息学:从部分标注的生物网络中预测基因功能或蛋白质相互作用角色。
  • 通过相似性图传播已知的正常/异常标签进行半监督异常检测。

使用方式

使用方式

1

在所有n个数据点(包括标记和未标记)上构建一个加权相似性图。一个常见的选择是高斯(RBF)核:边权重W_ij是点i和j之间平方欧氏距离的递减函数,由带宽参数sigma控制。只保留k个最近邻或epsilon半径邻居,以保持图的稀疏性。

公式
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

权重矩阵W被逐列归一化以生成行随机转移矩阵T,其中每个条目T_ij表示标签信息从节点j流向节点i的概率。这确保了每个节点接收到的总影响之和为一。

公式
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

算法从初始标签矩阵F(每列代表一个类别)开始迭代:将F乘以T,然后将对应于标记节点的行强制恢复为其真实的独热标签Y_L。这种强制约束可防止已知标签漂移,并充当吸收边界条件。迭代重复进行,直到F的未标记条目收敛。

公式
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

对于未标记块F_U*的固定点解以闭式形式给出为(I - T_UU)^{-1} T_UL Y_L,其中T_UU是未标记节点之间的转移子矩阵,T_UL捕获从标记节点到未标记节点的转移。实际上,对于大型图,迭代版本因避免矩阵求逆而更受青睐;两种方法都 都产生相同的唯一解。

公式
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

常见陷阱

  • 使用完全连接的图而不进行稀疏化,这会模糊局部结构,并且在规模上计算上不可行。
  • 默认选择sigma而不对标记集进行交叉验证,导致标签分布过度平滑或平滑不足。
  • 忽略类别不平衡:如果一个类别在标记集中占主导地位,其标签会淹没整个图;需要重新加权或采样。
  • 将归纳预测视为已训练模型,并将其应用于新点,而没有归纳包装器。
  • 未能检查图的连通性:孤立组件中的未标记节点不接收任何信号,并默认为均匀类概率。

常见问题

标签传播和标签传播(Label Spreading)有什么区别?

Zhou等人(2004)提出的标签传播引入了一个正则化参数alpha,该参数控制每个节点在多大程度上保留其初始标签,而不是采纳其邻居的标签。在经典的标签传播中,标记节点被严格强制,使其完全吸收。标签传播允许标记节点被部分覆盖,这使其对标签噪声更具鲁棒性,但代价是增加了一个超参数。

标签传播能扩展到大型数据集吗?

朴素的闭式解需要求逆一个(n_U x n_U)的矩阵,这对于大的n是不可行的。实际上,稀疏的k近邻或epsilon半径图将内存减少到O(nk),然后迭代更新的计算量大致与每次迭代的边数成线性关系。对于非常大的图,可以使用近似最近邻方法和迷你批次变体。

需要多少标记样本?

标签传播专门为极度低标记样本的情况设计。即使每个类别只有一个标记节点,如果图结构与类别边界对齐,也能产生有意义的预测,但强烈建议每个类别至少有几个标记样本以确保可靠性。性能会随着标签噪声的增加或图对类别成员资格的信息量减少而下降。

标签传播可以预测新的、未见过的数据点吗?

在其标准的归纳形式下,不能——该算法作用于固定图,没有在图外进行预测的机制。对于归纳使用,一种常见的方法是将新点连接到其在现有图中的k个最近邻,并运行部分传播步骤,或者使用收敛的标签矩阵来训练标准的监督分类器作为第二阶段。

相关方法

参考文献

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    打开出版物文献
    已复制。
  2. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

    打开出版物文献
    已复制。
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN:978-0-262-03358-9
    已复制。