面向半监督分类的快速双重重建亲和传播(Fast Doubly Reconstructed Affinity Propagation for Semi-Supervised Classification)

《Neurocomputing》:Fast doubly reconstructed affinity propagation forsemi-supervised classification

【字体: 大 中 小 】 时间:2026年05月19日 来源:Neurocomputing 6.5

编辑推荐:

  作为一种典型的半监督学习手段,标签传播(Label Propagation, LP)通常旨在利用极小比例的有标签样本来预测无标签样本。研究人员在简要回顾了现有基于流形假设(Manifold Assumption)的LP方法后,总结了所有这些方法中存在的三个现象

  
作为一种典型的半监督学习手段,标签传播(Label Propagation, LP)通常旨在利用极小比例的有标签样本来预测无标签样本。研究人员在简要回顾了现有基于流形假设(Manifold Assumption)的LP方法后,总结了所有这些方法中存在的三个现象级问题,包括矩阵求逆的显式或隐式计算、对K近邻(K-Nearest Neighbor, KNN)图的强依赖性以及亲和(Affinity)学习不足。为解决这些问题,研究人员相应地提出了一种新颖的LP方法,称为面向半监督数据分类的快速双重重建亲和传播(Fast Doubly Reconstructed Affinity Propagation, FDRAP),该方法借助亲和图的快速双重重建来实现。FDRAP始于两个独特的理念:(1)通过每个节点强度表征每个节点对中两两样本的典型性(Typicality),重建给定的亲和图,以反映每个节点对在代表各自两个簇中的倾向。(2)通过每个节点对与其内部每个样本自身不亲和性(Disaffinity)的差值来估计每个节点对的标签传播概率,利用该概率再次重建源自重建亲和图的每个不亲和性,从而增强最终传播矩阵的分离性。相应地,每个无标签样本的简易标签传播仅通过对重建的不亲和性与标签向量的乘积求和来完成。在多个测试用例上的显著结果表明,FDRAP具有具有竞争力的分类准确率和离群点检测能力、快速的运算速度以及强大的可扩展性。
论文解读:面向半监督分类的快速双重重建亲和传播(FDRAP)
该研究发表于期刊《Neurocomputing》。
研究背景与意义
在目标识别和社交媒体等许多现实场景中,样本标注往往成本高昂且耗费大量人力时间。众所周知,为了可靠地标记无标签样本,半监督学习应基于合理的假设。目前半监督学习中使用的两种较为流行的假设是聚类假设(Cluster Assumption)和流形假设(Manifold Assumption)。基于流形假设,许多高效的标签传播(Label Propagation, LP)方法得到了发展。这些LP方法通常将样本集表示为一个亲和图(Affinity Graph),其中每个样本被表示为一个节点,它们的关系由边定义,其节点亲和性由基于欧氏距离或高斯核函数(Gaussian Kernel Function)的相似性度量简单地确定的接近程度来定义。然后通过物理定理或统计定律的解释巧妙地构建亲和矩阵,在通过额外耗时的努力加强该矩阵的可分性后,最终通过矩阵求逆形式的解析解或其近似的迭代更新实现,逐步平滑地传播标签,从而通过极小比例的有标签样本预测无标签样本。
然而,这种工作方式的LP通常会导致繁琐的超参数确定、过多的计算负担,甚至在大尺度数据上不切实际。此外,大多数这些LP方法没有从初始数据表示中进行亲和(Affinity)学习的能力,导致对相似性度量高度敏感且算法鲁棒性受损。近年来,尽管一些研究试图填补上述问题的空白,例如结合自适应权重学习与LP,或将其纳入图卷积网络(Graph Convolutional Networks),但这些方法要么未能改变给定图的初始属性,要么未针对LP的通用缺点做出相应改进,且往往涉及耗时的迭代算法或对数据质量有较高要求。
为此,Yichen Sun、Guanjin Wang、Chi Man Vong和Shitong Wang等研究人员提出了一种名为快速双重重建亲和传播(Fast Doubly Reconstructed Affinity Propagation, FDRAP)的新型LP方法,通过亲和图的快速双重重建和简单的标签传播来解决上述瓶颈。该方法的核心是将半监督学习的重点创新性地转向亲和学习,从而彻底简化标签传播规则的公式。研究结果表明,FDRAP在分类准确率、离群点检测、运行速度和可扩展性方面均具有竞争优势。
主要关键技术方法
研究人员开展的FDRAP研究主要基于流形假设,核心包括两个双重亲和重建步骤和一个简易标签传播规则。关键技术首先引入了现有LP研究中被忽视的两个量:一是节点对中两两样本的典型性(Pairwise Typicality),定义为图中一个样本的强度乘以另一个样本的强度,衡量两样本代表各自簇(甚至不同类别)的倾向;二是节点对的传播概率,依赖于该节点对的不亲和性(Disaffinity)与其内部每个样本自身不亲和性的差值。具体方法为:第一步,将每个节点对的亲和重建为其给定亲和减去由其典型性负正则化的量;第二步,将每个节点对的不亲和重建为其传播概率与从第一步获得的重建亲和得出的不亲和性的乘积,形成第二重重建亲和矩阵;第三步,利用该矩阵通过简单的求和运算完成无标签样本的标签预测。该方法无需矩阵求逆计算,参数易于调整。
研究结果
Introduction(引言)
研究人员指出,半监督学习中的LP方法多基于流形假设构建亲和图并依赖矩阵求逆或迭代更新进行标签传播,存在计算负担重、依赖KNN图、亲和学习能力不足等共性问题。近期的一些改进方法如自适应嵌入标签传播(AELP-WL)、自动加权标签传播(ALP-TMR)及结合图卷积的LERP等,仍未能从根本上解决初始图属性不变、仍需复杂学习或存在可解释性与效率问题。这进一步激励了研究人员关注亲和重建在半监督学习中的关键作用,从而提出FDRAP。
A brief review on existing LP methods(现有LP方法简述)
研究人员回顾了基于图的半监督学习应用及典型的LP方法(如HF、FLAP、LPGMM等),指出它们普遍通过物理或统计定律构建亲和矩阵,并经过复杂处理后进行标签传播,导致高计算成本和对初始相似性的敏感。
Doubly Reconstructed Affinity for Label Propagation(用于标签传播的双重重建亲和)
研究人员详细阐述了双重亲和重建的过程。第一重重建利用节点强度定义的典型性负正则化给定亲和,以抑制属于不同簇节点对间的亲和;第二重重建引入传播概率重构不亲和性,使得最终亲和矩阵具备更强的分离能力,且第二重重建亲和矩阵满足Hessian矩阵性质,可直接作为传播矩阵使用。
Fast Doubly Reconstructed Affinity Propagation Algorithm(快速双重重建亲和传播算法)
研究人员说明了FDRAP的三个步骤:计算节点强度与典型性、第一重亲和重建、计算不亲和与传播概率并进行第二重亲和重建、最后通过简易求和规则预测标签。该算法不涉及矩阵求逆,计算高效。
Experimental Studies(实验研究)
研究人员安排了七组实验来验证FDRAP的性能:第一组验证其在合成数据集上的基本标签传播性能;第二组通过与六种现有LP方法比较,表明FDRAP在UCI数据集上保持高准确率;第三和第四组实验提供了统计检验和参数分析;其余组进一步验证了其在不同场景下的鲁棒性、可扩展性及离群点检测能力。显著结果显示FDRAP在准确率和效率上均具竞争力。
Conclusions(结论)
研究人员总结,现有许多LP方法(如FLAP和LPGMM)通过基于物理定理或统计定律设计的亲和矩阵上进行复杂的传播来工作。而FDRAP通过考虑典型性tij和传播概率pij两个量,自动仅作用于从数据原始亲和构建的Hessian亲和矩阵,并通过这种亲和的快速双重重建突破了现有LP方法。FDRAP将半监督学习重点转向亲和学习,简化了传播规则,具备强分离性、快速性、易调参和出色的离群点检测能力。
讨论与总结
该论文针对半监督分类中基于图的标签传播方法普遍存在的计算效率低、对初始图依赖强及亲和学习不足等问题,提出了FDRAP算法。通过引入节点强度典型性和标签传播概率两个关键量,FDRAP实现了亲和图的双重重建,生成具有强分离性的Hessian传播矩阵,进而仅需简单求和即可完成标签预测,避免了矩阵求逆。实验证明其在多种数据集上取得了有竞争力的分类精度与运行效率,并具备良好的离群点检测能力,为半监督学习中的图基方法提供了新颖且高效的思路。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号