多标记学习：问题、算法与数据#
张敏灵*
基金项目：教育部博士点基金新教师项目（200802941009）
作者简介：张敏灵，(1979-)，男，副教授，主要研究方向：机器学习、数据挖掘. E-mail: zhangml.seu@gmail.com
（东南大学计算机科学与工程学院，南京 210096）
5 摘要：在多标记学习框架下，每个样本由单个示例进行表示但同时隶属于多个概念标记。多
标记学习系统的目标是分析概念标记集合已知的训练样本，从而尽可能正确地预测未知样本
的概念标记集合。目前有关多标记学习已经取得了大量的研究成果，本文将对其研究现状进
行简要介绍。首先给出多标记学习的形式化定义及其评价指标，然后介绍已有的多标记学习
算法以及该领域内常用的实验数据集，最后对多标记学习有待进一步研究的问题进行讨论。
10 关键词：人工智能；机器学习；监督学习；多标记学习；泛化
中图分类号：TP181
 0 引言
多标记学习起源于文档分类[1]研究中遇到的歧义性问题，在该学习框架下，每个对象由
30 单个示例（属性向量）表示并对应于多个概念标记。实际上，真实世界的许多问题都可以归
结为多标记学习问题。例如，在文档分类[2,3]问题中，每篇文档可能同时隶属于多个预定义
的主题，例如“体育”、“北京奥运会”与“火炬传递”；在生物信息学[4]问题中，每个基
因可能同时具有多种功能，例如“新陈代谢”、“转录”以及“蛋白质合成”；在视频自动
标注[5]问题中，每个视频片断可能同时对应于多个语义类别，例如“城市”与“建筑”。上
35 述问题均可以很自然地利用多标记学习框架进行建模。
目前，已经出现了大量的多标记学习算法，并在文档分类、生物信息学以及场景分类等
许多领域得到了成功应用。本文将对该学习框架的研究现状进行简要综述。接下来首先给出
多标记学习问题的形式化定义，并给出多标记学习领域内常用的性能评价指标。然后，对已
有的多标记学习算法以及基准测试集进行介绍。最后，对多标记学习领域值得深入研究的问
40 题进行讨论。
 1 多标记学习
1.1 框架定义
设为d 维示例空间而为所有概念标记构成的集合。给定多标记
训练集，其中为d 维属性向量（示例）而为与
45 对应概念标记集合。多标记学习系统的目标是从训练集中进行学习，输出一个多标记分
类器。在一般情况下，为了得到上述的多标记分类器，学习系统将学习得到
某个实值函数。对于训练样本及其对应的概念标记集合而言，学习系统
希望对于任意的以及有成立，即在隶属于的概念
标记上输出较大的值，而在不属于的概念标记上输出较小的值。
50 基于学习所得的实值函数， 可导出多标记分类器为
。其中， 为相应的阈值函数且通常设为零常量函数。
此外， 实值函数还可转化为一个排序函数。该函数实现实值输出
到集合的映射， 从而当成立时
亦成立。
55 由于传统的二类(two-class)或多类(multi-class)监督学习问题中每个样本仅对应于一个概
念标记，因此均可看作多标记学习问题的特例(degenerated version)。一种解决多标记学习问
题的直观方法是将其分解为个独立的二类分类问题。其中，每个二类分类问题对应于中
的一个概念类。在构造与某概念类对应的二类分类器时，将所有包含该类的样本作为正例而
将所有不包含该类的样本作为反例。
60 值得注意的是，上述直观方法由于没有考虑到每个样本所含概念标记之间的相关性
(correlation)，因此其泛化性能往往并不理想[2-4]。例如，在场景分类问题中[6]，如果已知一
幅场景图像隶属于“灌木”类，则该图像同时隶属于“草原”类的可能性将大于其隶属于“海
洋”类的可能性。因此，多标记学习的一个主要问题是如何充分利用各训练样本所含概念标
记之间的相关性，从而有效地提高学习系统的泛化能力。
65 1.2 评价指标
在传统监督学习框架下，常用的评价指标包括精度(accuracy)、查准率(precision)、查全
率(recall)等[1]。由于在多标记学习框架下，每个样本不再对应于单一的概念标记，其性能评
价指标与传统监督学习系统有所不同。设为多标记测试集，以
下给出了目前多标记学习领域内常用的性能评价指标[2,4]：
70  Hamming loss：该指标用于考察样本在单个概念类上的误分类情况，即隶属于该样
本的概念类未出现在标记集合中而不属于该样本的概念类出现在标记集合中：
(1)
其中，算子用于度量两个集合之间的对称差(symmetric difference)。该指标取值越
小则系统性能越优，当时系统性能最优。值得注意的是，当中的每个样
75 本仅含有一个概念标记时，hamming loss 的取值即为传统分类误差的倍。
 One-error：该指标用于考察在样本的概念标记排序序列中，序列最前端的标记不
属于样本标记集合的情况：
 其中，对于任意的谓词，当成立时取值为1，否则取值为0。该指标取值
80 越小则系统性能越优，当时系统性能最优。值得注意的是，对于单
标记学习问题而言，one-error 即为传统的分类误差。
Coverage：该指标用于考察在样本的概念标记排序序列中，覆盖隶属于样本的所有
概念标记所需的搜索深度情况：
(3)
85 其中，函数的定义如1.1 节所示。该指标取值越小则系统性能越优。
 Ranking loss：该指标用于考察在样本的概念标记排序序列中出现排序错误的情况：
(4)
其中， 代表在集合中的补集。该指标取值越小则系统性能越优，当
90 时系统性能最优。
 Average precision：用于考察在样本的概念标记排序序列中，排在隶属于该样本的
概念标记之前的标记仍属于样本标记集合的情况：
(5)
95 该指标最先出现于信息检索(information retrieval)领域，用于度量给定查询下检索系
统返回文档的排序性能[7]。该指标取值越大则系统性能越优，当时系
统性能最优。
2 研究现状
2.1 多标记学习算法
100 如引言部分所述,多标记学习问题广泛存在于真实世界中。目前已经出现了大量的多标
记学习算法，并在文本分类、生物信息学、场景分类、视频自动标注以及数据挖掘等许多领
域得到了广泛应用。本节接下来将按照多标记学习技术的不同应用领域对多标记学习算法进
行简要介绍。
多标记学习的研究起源于文档分类中遇到的歧义性问题，因此有关多标记学习的研究内
105 容有很大一部分集中于多标记文档分类方面。Schapire 和Singer[2]对传统的AdaBoost[8]方法
进行了扩展，提出了BoosTexter 系统将文档归入多个类别。该方法在训练过程中不仅要改
变训练示例的权重，还要改变概念标记的权重。在此之后，McCallum[3]用一个混合模型来表
示文档类别，提出了一种Bayes 和EM[9] 相结合的方法用于多标记文档分类。该方法利用
EM 对混合模型中的混合权和每一混合成分中字的分布进行学习。Ueda 和Saito[10]基于
110 Bag-of-Words[11]的文档表示方法，提出了两种多标记文档的产生式概率模型(probabilistic
generative model)。该模型假设多标记文本有一个特征字的混合出现在每个类的单标记文档
 中。Gao 等人[12]将单标记情况下的“最大化性能指标(maximal figure-of-merit)”方法[13]进行
扩展以适应多标记学习问题的需求。该方法的基本思想是将分类器涉及的参数嵌入一个连续
可微函数，该函数近似地模拟了特定的性能评价指标。在预测阶段，该方法针对每一个可能
115 的概念类使用一个评分函数并利用传统的Bayes 决策规则进行分类。
研究者们通过对监督学习算法的扩展，还提出了一系列的多标记学习算法并在文档分类
问题中得到应用。Comité 等人[14]改造交替决策树 [15]使其可以处理多标记数据，并将其作为
ADABOOST.MH 算法[16]的基分类器(base learner)以训练多标记交替决策树。Crammer 和
Singer[17]将感知机算法[18]用于解决多标记文档分类问题，他们利用在线学习(online learning)
120 的方式为每一个可能的文档类别学习一个原型向量(prototype vector)，然后利用文档和每个
类的原型向量之间的相似度实现文档类别的排序。Zhang 和Zhou[19]改造BP 神经网络[20]的
全局误差函数以反映多标记学习问题的特性，即隶属于样本的概念标记应位于不属于该样本
的概念标记前列。Ghamrawi 和McCallum[21]以及Zhu 等人[22]分别提出了基于最大熵模型
(maximum entropy model)[23]的多标记学习算法，其基本思想是在传统的最大熵模型中加入二
125 阶(second-order)的统计限制条件来反映任意一对概念类之间的相关性。
Godbole 和Sarawagi[24]在原有的文本属性上加入额外的属性以反映类别之间相关信息，
并基于扩展后的属性向量设计特殊的核函数，从而将支持向量机(SVM)进行扩展以解决文档
分类问题。Kazawa 等人[25]将主题的集合看作一个新类，从而将多标记文档分类问题转化为
单标记学习问题。他们将类别嵌入一个基于相似度导出的新向量空间，其中相似的类别在新
130 的向量空间中将位于相近的位置。此外，他们还给出了一种近似的训练算法和高效的预测算
法来克服所提方法面临的巨大计算开销。Zhang 和Zhou[26]还提出了一种基于懒惰学习(lazy
learning)技术的多标记学习算法，该算法的优点在于可以直接使用测试样本与训练样本的相
似度来对概念标记进行预测，而无需大量的训练开销。近期，研究者们还提出了一些利用额
外信息或辅助学习技术，如类别层次信息[27,28]、未标记数据[29,30]、集成学习技术[31]等，来提
135 高多标记学习系统泛化性能的方法。
除了前述的文档分类问题，多标记学习技术还在生物信息学(bioinformatics)领域得到了
应用。Clare 和King[32]将数据集在每一概念类上的熵求和定义相应的“多标记熵(multi-label
entropy)”，从而将C4.5 决策树[33]进行扩展以处理多标记数据。所得多标记决策树可以转化
为一组等价的符号规则，从而可以和已知的生物知识进行比较。Elisseeff 和Weston[4]提出了
140 一种多标记SVM，该方法的优化目标函数综合了“ranking loss”评价指标(式(4))以及特定
的“多标记边际(multi-label margin)”。该方法在酵母(yeast)基因功能分类问题上取得了较好
学术论文网Tag：代写论文 论文发表 计算机论文 代发论文 职称论文发表