引用本文

征察, 吉立新, 高超, 李邵梅, 吴翼腾. 基于成对约束的偏标记数据消歧算法. 自动化学报, 2020, 46(7): 1367-1377. doi: 10.16383/j.aas.c170522

ZHENG Cha, JI Li-Xin, GAO Chao, LI Shao-Mei, WU Yi-Teng. Partial Label Data Disambiguation Algorithm Based on Pairwise Constraints. ACTA AUTOMATICA SINICA, 2020, 46(7): 1367-1377. doi: 10.16383/j.aas.c170522

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170522

关键词

偏标记数据，消歧，数据不平衡，低秩表示，成对约束 

摘要

偏标记数据消歧是利用偏标记数据进行机器学习的基础.针对偏标记数据中广泛存在的数据不平衡问题, 以及现有消歧算法对样本间约束信息利用不足的问题, 本文提出一种基于成对约束的偏标记数据消歧算法.首先, 基于低秩表示, 推导出数据不平衡条件下样本低秩表示系数和样本相似度之间的关系; 其次, 基于推导结果, 分别构建基于样本间正约束和负约束的图模型, 通过最小化图模型的能量函数求解偏标记数据的标签.在5个公开数据集上的实验结果表明本文方法相对基准算法在消歧准确率上平均提高了2.9 % ~ 14.9 %.

文章导读

偏标记数据是一种常见的弱监督数据.在这类数据中, 每个样本同时具备多个候选类别标签, 但只有一个标签是正确的. 图 1展示了两例典型的偏标记数据, 将新闻标题中的人名作为新闻图像中人脸的姓名标签, 则一个人脸可能对应多个姓名标签[1]; 将诊断图像对应的可能病因作为医学图像的标签, 则图像可能对应多个病因标签[2].和带有唯一、正确标签的强监督数据集类似, 偏标记数据集也常具有高维、数据不平衡的特点.但由于偏标记数据获取成本远低于传统监督学习所需的强监督数据, 如何利用偏标记数据进行弱监督学习已成为机器学习中的一个研究热点, 具有广阔的应用前景.

图 1  典型的偏标记数据

为利用偏标记数据进行学习, 文献[3]提出一种基于纠错输出编码的偏标记学习方法, 直接利用偏标记数据训练一个多分类器, 但该方法在训练过程中可能存在部分数据未被利用的情况.为充分利用偏标记数据, 大多数偏标记学习算法[4-10]首先对偏标记数据进行消歧, 确定每个偏标记样本的正确类别标签.根据是否需要利用参数模型来假设样本分布, 现有的消歧方法可以分为两类: 1)基于辨识(Identification)的消歧; 2)基于平均(Averaging)的消歧.

基于辨识的消歧将偏标记样本的真实标签设为参数模型的隐变量, 并基于最大似然准则[2], 或最大间隔准则[5, 10]建立目标函数, 之后采用迭代的方式优化目标函数求解隐变量实现消歧.如文献[6]提出一种基于字典学习的消歧算法, 首先假设每类数据呈高斯混合分布, 然后迭代地对样本标签置信度矩阵–字典矩阵进行更新, 并根据最终的样本标签置信度矩阵来确定样本标签.基于辨识的方法需要进行合理的模型假设, 错误的模型假设将对消歧带来不利影响[4].基于平均的消歧通过赋予偏标记样本的各个候选标签相同的权重, 综合学习模型在各候选标签上的输出实现消歧[7-9].在基于平均的消歧算法中, 图模型因无需模型假设, 以及便于描述样本间的标签关系而得到广泛应用[7, 9].它是根据一定规则在样本间建立一个有权图G=(V,E,W), 通过分析图模型上节点候选标签间的关系来消歧.其中V代表样本集合, E为样本间的边集合, W为相应的边权重集合.文献[7]采用近邻消歧算法, 根据弱监督学习中的流形假设[11]构建图模型:假设邻近样本具有相同的标签, 令样本x和其近邻样本建立连边, 通过对近邻样本的候选标签集加权投票来确定x的标签.文献[9]改进了文献[7], 提出基于实例的偏标记学习算法[9] (Instance-based partial label learning, IPAL).在构建图模型后, 该方法采用迭代的标签传播算法进行消歧.

虽然现有的基于图模型的消歧算法具有无需模型假设的优势, 但仍存在问题.首先, 偏标记数据通常具有较高的维度, 而欧氏距离等一些常用于度量相似度的方法在高维空间中通常难以奏效.近年来, 在半监督学习和聚类领域, 低秩表示[12]因擅于表达高维数据结构而在构建图模型时取得良好效果[13-15].然而, 这些方法都是针对数据平衡的数据集, 而偏标记数据常面临数据不平衡问题, 因此无法直接将低秩表示用于偏标记数据消歧.其次, 现有消歧算法中, 建立图模型时只利用一种样本间约束, 即更相似样本之间边权重越大, 标签相同的可能性越大.但在半监督、聚类领域, 有两种约束得到广泛使用, 其中一种被称为正约束(Must-link), 即部分样本必定属于同一类, 另一种为负约束(Cannot-link), 即部分样本必定属于不同类.这两种约束通常共同使用, 因此被合称为成对约束.研究表明利用成对约束能有效提高聚类效果[16-17].受此启发, 本文将成对约束的概念迁移至偏标记数据消歧中, 将"相似样本应具有相同标签''定义为正约束, 将"差异较大的样本应具有不同标签''定义为负约束, 采用成对约束对偏标记数据消歧.

综上, 本文提出一种基于成对约束的偏标记数据消歧算法(Partial label data disambiguation algorithm based on pairwise constraints, PLDPC), 其创新之处在于: 1)针对偏标记数据中广泛存在的数据不平衡问题, 研究该条件下低秩表示系数和样本相似度的关系; 2)在考虑数据不平衡后, 利用低秩表示构建两个分别基于正、负约束的图模型, 并基于定义在图模型上的能量函数[18], 结合类块标准化(Class mass normalization)准则[19]进行消歧.

本文主要分为5个部分:第1节简要介绍低秩表示算法; 第2节和第3节是本文的主要工作:第2节对数据不平衡条件下低秩表示系数和样本相似度的关系进行分析, 第3节基于第2节中的结论提出基于成对约束的偏标记数据消歧算法; 第4节是仿真实验及结果; 第5节对本文进行总结.

图 2  正负约束作用于消歧的效果

图 3  基于成对约束的偏标记数据消歧算法流程

基于图模型的偏标记数据消歧是近年来的研究热点, 而采用何种方式构建图模型是该问题的关键.低秩表示作为一种效果优异的子空间分割算法, 在基于图模型的聚类、半监督学习等领域得到了广泛应用.然而这些领域在利用低秩表示来分析样本间的相似度时, 未考虑数据不平衡对低秩表示的影响, 以及数据不平衡时低秩表示系数表示样本间相似度的合理方式.而在偏标记数据中, 数据不平衡是一种普遍存在的问题, 因此本文详细研究了数据不平衡时低秩表示系数表示样本相似度的合理方式, 并在实验中验证了研究结论的正确性.此外, 针对现有方法仅利用样本间正约束, 忽略了负约束的问题, 本文综合利用正负约束来设计图模型, 并通过最小化基于图模型的能量函数求解出样本的标签.实验结果表明, 相比PL-KNN、IPAL、PL-LEAF等基准算法, 本文方法在所有数据集上都有更高的准确率; 相比MMS算法, 本文方法尽管在Lost、Yahoo!News两个数据集上准确率略低, 但平均消歧准确率优于MMS, 且效率平均提高了约10倍, 说明本文方法能够在保证效率的情况下具有更高的消歧准确率, 适用于对消歧准确率要求较高的应用场景.

作者简介

吉立新

国家数字交换系统工程技术研究中心研究员.主要研究方向为电信网信息关防, 信息安全. E-mail: jlx@ndsc.com.cn

高超  

国家数字交换系统工程技术研究中心助理研究员.主要研究方向为计算机视觉. E-mail: chaosndsc@163.com

李邵梅  

国家数字交换系统工程技术研究中心副研究员.主要研究方向为计算机视觉. E-mail: lishaomei may@126.com

吴翼腾  

国家数字交换系统工程技术研究中心博士研究生.主要研究方向为网络大数据分析. E-mail: wuyiteng1992@163.com

征察  

国家数字交换系统工程技术研究中心硕士研究生.主要研究方向为机器学习, 计算机视觉.本文通信作者. E-mail: zcpi31415926@163.com