多标记学习.pdf

多标记学习* 张 敏 灵 1 周 志 华 2 1东南大学计算机科学与工程学院，南京 210096 2南京大学计算机软件新技术国家重点实验室，南京 210093 1. 引言 在机器学习中，传统监督学习（traditional supervised learning）[1]是研究得最多、应用最广泛的 一种学习框架。在该框架下，对于真实世界的每一个对象，学习系统在输入空间用一个示例（instance， 通常为属性向量）刻画对象的性质，同时在输出空间将示例与反映该对象语义信息的类别标记（label） 相关联，这样就得到了一个样本（example）。在拥有了一个较大的样本集合即训练集（training set） 之后，学习系统利用某种学习算法学得输入空间（即示例空间）与输出空间（即标记空间）之间的 一个映射，基于该映射可以预测未见示例（unseen instance）的类别标记。形式化地说，假设 代表 示例空间， 代表标记空间，则学习系统的任务是从训练集 中学得函数 ，其中 为一个示例而 为示例 所属的类别标记。在待学习对象具有明确、 单一的语义，即对象的类别标记唯一时，上述传统监督学习框架已经取得了巨大的成功。 然而，真实世界的对象往往并不只具有唯一的语义，而是可能具有多义性的。对于图 1(a)所示 的一篇关于南非世界杯的新闻报道，既可以认为它属于“体育”这个类别，也可以认为它属于“非 洲”这个类别，该报道可能还谈及了本次世界杯对南非在经济层面的影响从而属于“经济”类；再 比如，对于图 1(b)所示的图像而言，既可以认为它属于“日落”这个类别，也可以认为它属于“云”、 “树木”甚至“乡村”类。这样的例子还有很多，一个基因可能同时具有多种功能如“新陈代谢”、 “转录”以及“蛋白质合成”，一首乐曲可能传达了多种信息如“钢琴”、“古典音乐”、“莫扎特”以 及“奥地利”，等等。 由上可见，多义性对象由于不再具有唯一的语义，这就使得前述的只考虑明确、单一的语义的 传统监督学习框架难以取得好的效果。为了直观地反映多义性对象所具有的多种语义信息，一种很 自然的方式就是为该对象显式地赋予一组合适的类别标记，即标记子集。基于上述考虑，作为一种 多义性对象学习建模工具，多标记学习（multi-label learning）框架[2][3]由此应运而生。在该框架下， 每个对象由一个示例描述，该示例具有多个而不再是唯一的类别标记，学习的目标是将所有合适的 类别标记赋予未见示例。 *本文得到国家自然科学基金、教育部博士点基金新教师项目（200802941009）以及东南大学引进人才 启动基金的资助 (a) 一篇文档 (b) 一幅图像 图 1 多义性对象的两个例子 早期，多标记学习的研究主要集中于分档分类（text categorization）中遇到的多义性问题[4][5][6][7]。 经过近十年来的发展，多标记学习技术已在多媒体内容自动标注[8][9][10]、生物信息学[11][12][13]、Web 挖掘[14][15]、信息检索[16][17][18]、个性化推荐[19][20]等领域得到了广泛应用。据笔者不完全统计，近四 年以来（2007 年—2010年），在与机器学习相关的一流国际会议 ICML、NIPS、ECML/PKDD、KDD、 ICDM、IJCAI以及 AAAI 上，标题部分出现“多标记（multi-label / multilabel）”这一关键词的论文 即超过了 30篇。此外，近两年召开的 ECML/PKDD’09以及 ICML/COLT’10均设置了以“Learning from Multi-Label Data”为主题的 Workshop1。多标记学习的研究进展也得到了国际机器学习界权威刊物 《Machine Learning》的关注，将于近期推出一期以多标记学习为主题的专辑2。 总的来说，多标记学习的研究对于多义性对象的学习建模具有十分重要的意义，现已逐渐成为 国际机器学习界一个新的研究热点。本章将对多标记学习的研究现状做一个简介，首先给出多标记 学习的定义与面临的主要问题，并介绍多标记性能评价指标，然后重点介绍几种具有代表性的多标 记学习算法，最后简要讨论多标记学习的拓展研究课题及相关学术资源。 2. 学习框架 2.1 问题定义 假设 代表 d维的示例空间， 代表包含 q 个类别的标记空间。给定多 标记训练集 ，其中 为d维的属性向量 ，而