基于标记因果顺序挖掘的多标记分类方法- 陈加略，姜远.pdf

上善若水

320

7页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(4):1267−1273 [doi: 10.13328/j.cnki.jos.006475] http://www.jos.org.cn

基于标记因果顺序挖掘的多标记分类方法

∗

陈加略

姜

远

(南京大学计算机科学与技术系, 江苏南京 210023)

通信作者: 姜远, E-mail: jiangyuan@nju.edu.cn

摘要: 在多标记学习(MLL)问题中, 每个示例都与一组标记相关联. 为了实现对未见示例的高效预测, 挖掘和利

用标记之间的关系是至关重要的. 大多数已有的研究都将关系简化为标记之间的相关性, 而相关性又通常基于标

记的共现性. 揭示了因果关系对于描述一个标记在学习过程中如何帮助另一个标记更为重要. 基于这一观察, 提

出了两种策略来从标记因果有向无环图(DAG)中生成标记的因果顺序, 同时使得生成的因果顺序都遵循因标记应

该在果标记之前的准则. 第 1 种策略的主要思想是对随机顺序进行排序, 使其满足 DAG 中的因果关系. 而第 2 种

策略的主要思想是根据 DAG 的结构, 将标记放入许多不相交的拓扑层次中, 再通过它们的拓扑结构进行排序. 进

一步, 通过将因果顺序纳入到分类器链(CC)模型中, 提出了一种有效的 MLL 方法, 从而从更加本质的角度来利用

标记关系. 在多个数据集上的实验结果验证了该方法确实能够挖掘出有效的标记因果顺序, 并帮助提升学习性能.

关键词: 多标记学习; 因果; 标记顺序; 有向无环图; 分类器链

中图法分类号: TP181

中文引用格式: 陈加略, 姜远. 基于标记因果顺序挖掘的多标记分类方法. 软件学报, 2022, 33(4): 1267–1273. http://www.

jos.org.cn/1000-9825/64 75.ht m

英文引用格式: Chen JL, Jiang Y. Multi-label Learning by Exploiting Causal Order of Labels. Ruan Jian Xue Bao/Journal of

Software, 2022, 33(4): 1267−1273 ( in Chinese). http://www.jos.org.cn/1000-9825/6475.htm

Multi-label Learn ing by Exploi ting Causal Order of Labels

CHEN Jia-Lüe , JIANG Yuan

(Department of Computer Science and Technology, Nanjing University, Nanjing 210023, China)

Abstra ct : In multi-label learning (MLL) problems, each example is associated with a set of labels. In order to train a well-performed

predictor for unseen examples, exploiting relations between labels is crucially important. Most exiting studies simplify the relation as

correlations among labels, typically based on their co-occurrence. This study discloses that causal relations are more essential for

describing how a label can help another one during the learning process. Based on this observation, two strategies are proposed to

generate causal orders of labels from t he label causal directed acyclic graph (DAG), following the constraint th at the cause label should be

prior to the effect label. The main id ea of the first strate gy is to sort a random order to make it satisfied the cause-effect relations in DAG.

And the main idea of the second strategy is to put labels into many non-intersect topological levels based on the structure of the DAG,

then sort these labels through th eir topological structure. Further, by incorporating the causal orders into the classifi er chain (CC) model,

an effective MLL approach is proposed to exploit the label relation from a more essential view. Experiments results on multiple datasets

validate that the extracted causal o rder of l abels indeed p rovides h elpful inf ormation to boost t he performan ce.

Key words: multi-label learning; causality; label-order; directed acyclic graph; classifier chain

在监督学习场景中, 每个示例都只有一个标记来描述其语义. 然而在很多实际应用中, 为了充分描述对

象的语义, 需要为每个示例标注一个以上的标记. 为了处理这种应用场景, 多标记学习

[1,2]

假设训练集中的每

∗ 基金项目: 国家自然科学基金(61673201, 61921006)

本文由“面向开放场景的鲁棒机器学习”专刊特约编辑陈恩红教授、李宇峰副教授、邹权教授推荐.

收稿时间: 2021-05-29; 修改时间: 2021-07-16; 采用时间: 2021-08-27; jos 在线出版时间: 2021-10-26

1268

软件学报 2022 年第 33 卷第 4 期

个示例都由一个特征向量表示, 并与一组标记相关联, 而其任务则是预测未见示例的标记集. 从形式上看, 多

标记学习的关键是训练一个从特征空间到标记空间的映射. 然而, 从标记的幂集中考虑所有的组合是不切实

际的, 因此多标记学习的任务将变得相当具有挑战性. 为了解决这个问题, 如何有效利用标记之间的关系来

促进多标记的学习是其中的关键. 分类器链(C C)

[3]

算法作为一种具有代表性的多标记学习方法, 试图将每个

示例的标记代入一个确定性的马尔科夫链模型中, 以获取标记之间的相关性. 在 CC 的训练过程中, 会按照特

定的顺序训练出一组分类器, 其中, 它们的训练输入的是示例的特征向量和之前标记的集合. 由于分类器的

性能对标记顺序的选择很敏感, 这个问题的关键就成了如何确定 CC 的最佳顺序.

因果关系

[4,5]

是一种描述随机变量之间潜在的数据生成过程的更加本质的关系. 通过观察数据发现因果

关系, 在很多领域都发挥了举足轻重的作用, 如医疗卫生

[4]

和经济学研究

[6]

. 在多标记学习中, 通过将每个标

记视为一个变量, 标记之间可能存在一些自然的因果关系, 而这种因果关系通常比标记之间的共现关系更加

能够反映数据的结构信息. 例如, 仙人掌通常生长在沙漠地区, 而沙漠上相对干燥的环境可能是仙人掌更加

适合生活的原因. 因此, 在图像数据集

[7]

中, 标记沙漠也可以成为标记仙人掌的因. 直观上, 特征集作为标记

的因是被普遍接受的, 但这种常识即使在图像分类问题中也未必成立. 例如, 一个人想要写数字 7, 这个需求

会导致一个运动模式产生数字 7 的图像. 在这种情景下, 作为需求表示的数字的类标记可以看成是其图像的

因. 这种因果顺序相反的情况, 也被称为反向因果关系推断

[8]

在本文中, 将使用有向无环图(DAG)来描述标记之间的因果关系

[4]

. 在这个 DAG 中, 每个顶点对应一个

标记, 每条边对应两个标记之间的因果关系. 基于标记因果 DAG 的描述方式, 我们提出了两种新颖的抽取标

记顺序的方法, 并将其与 CC 算法相结合. 不幸的是, 在大多数多标记任务中, 因果关系(即 DAG 中的边)是未

知的, 所以我们必须探索标记之间的因果关系. 为了简单起见, 本文将使用广泛应用的 PC 算法

[9]

. 通过计算

标记之间的条件独立性, 来探索 DAG 中的因果关系. 当我们知道 DAG 中的所有边的方向后, 通过 DAG 的结

构和本文策略, 将生成一个特定的标记顺序, 这个标记顺序将一定满足因标记应该出现在果标记之前的合法

性定义. 最后, 标记的顺序将决定 CC 算法的分类器的训练序列. 更具体地说, 在每一轮训练中, 一个示例的

特征向量和该轮之前顺序的标记都将被视为当前轮分类器的输入. 与其他优化方法相比, 本文的策略具有以

下优点: 1) 本文的策略是非启发式的优化方法, 因此在期望上具有更强的自适应性; 2) 本文的策略易于实现;

3) 本文的策略可以同时适用于正向和反向因果推理. 大量的实验验证了我们的方法可以为 CC 算法挖掘出有

效的标记因果序列.

1 相关工作

现有的多标记学习方法可以根据其利用的标记之间相关性的阶数大致分为 3 类: 一阶方法将 MLL 问题分

解为若干个独立的二元分类问题

[10−12]

; 二阶方法考虑的是标记之间的对偶关系

[13,14]

; 高阶方法考虑的则是标

记之间更高阶的关系

[15−18]

. 分类器链是一种典型的高阶方法, 即根据特定的标记顺序依次训练多个分类器.

基于现在的研究, 已经有一些优化方法被提出来, 解决 CC 中标记顺序的问题. 在文献[19]中, 作者提出了一

个概率框架, 从风险最小化和贝叶斯最优预测的角度来看待 MLL 问题, 然后将其应用到 CC 中, 从而得到了

得到 probabilistic CC. 在文献[20 ]中, 作者提出了一个贝叶斯网络, 来在不完全赋值的情况下, 系统地获取不

同标记之间的依赖关系.

因果发现是因果研究的工作中最关键的问题之一. 基于约束的方法是因果发现方法的一种, 它通过随机

变量之间的条件独立性来探寻因果关系. PC 算法是一种著名的基于约束的因果发现方法, 它假设变量之间的

所有条件独立性都是基于因果马尔科夫条件的. 已经有很多研究工作在考虑在多标记学习问题中利用因果关

系. 在文献[21]中, 作者提出了一种 MLL 算法, 该算法使用贝叶斯网络结构来有效地编码标记和特征集之间

的条件依赖性. 在文献[22]中, 作者从特征的角度出发, 通过在因果特征的超平面上编码不同标记对应的边距

来发现标记之间的因果关系. 这些工作大多假设特征集是标记的共同原因. 但遗憾的是, 即使在一些通用的

应用中, 这个假设也未必成立. 我们唯一能够利用的资源就只剩下标记之间的信息, 因为此时特征集无法对