英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
多标签学习
1.定义
多标签学习是标准监督学习设置的延伸。与一个训练实例与单个类标签相关联的标准监督学习不同，在多标签学习中，一个训练实例是同时与多个类标签相关联。多标签学习者诱导一个能够给未见实例指定多个适当标签(来自给定的标签集)的函数。多标记学习通过将每个实例的类标签数量限制为一个降为标准监督学习。
2.动机和背景
大多数分类学习方法将类值看作是不相交的，每个对象可能只属于一个类，例如ON或OFF。然而，有些应用程序的类别并不相互排斥——一个对象可能属于多个类[14]。例如，在文本分类中，一个关于总统选举的新闻文件可以涵盖政治、经济、外交和电视辩论等多个主题[10]；在图像分类中，一个自然场景图像可以包含多个场景，例如，天空、海洋、船只和海滩[2]。
事实上，多标签对象在生物信息学、多媒体内容注释、信息检索和网络挖掘等许多应用中经常遇到[14]。
多标签学习的目的是诱导一个能够预测来自给定标签集的不可见实例对应的标签子集的函数。在这个重要问题的研究涌现在2000年初，之后，研究取得了重大进展[14]。
3.学习系统的结构
让表示d维实例空间，表示由q个类标签组成的标签空间。给定多标签训练集，多标签学习的任务是为了学习一个从实例空间到标签空间子集的映射函数。对于每个多标签训练实例,是d维特征向量，是与相关联的类标签集。学习函数为任何未知实例预测合适的标签集。
一个被大多数多标签学习系统承认的的替代模型对应于一个真值函数。在这里，能被认为是作为合适标签的预测置信度。另一句话说，对于多标签实例，在相关标签的预测输出应该比不相关标签的预测输出大得多，即。通过运用一个阈值函数，能通过从实值函数中被得到。
4.评价方法
在标准监督学习中，常用的评价学习效果的方法有准确率、精确率、召回率等。然而，在多标签学习中，这些单标签评价方法由于数据的多标签性质不能直接采用。因此，有一些为多标签学习的评价方法已经被设计出来。这些方法大致可以分为两组，即基于实例的度量方法和基于标签的度量方法[14]。基于实例的度量方法分别评估了对被学习的多标签预测器在每个测试实例上的的泛化性能，然后返回整个测试集的平均值;基于标签的度量方法分别评估了预测器在每个类标签上的泛化性能，然后返回所有类标签的宏/微平均值。
让表示多标签训练集，（或）表示学习到的标签预测器。典型的基于实例的度量方法包括：
子集准确率：。这个方法评估了测试实例中预测的标签集与真正的标签集一致的比例。在这里，如果谓词成立，返还1，否则为0。
汉明损失：。该方法评估了错分实例-标签对的比例，例如一个相关标签丢失或者不相关标签被预测。在这里，表示两个集合的对称差。表示集合的基数。
One-error：。该方法评估测试实例中排序为1的预测标签没能成为相关标签的比例。
覆盖率：。该方法评估为了覆盖测试实例的所有相关标签所需要向下移动等级列表的步数。在这里，返回在标签空间中根据降序排列的类标签的次序。
排序损失：。这个方法评估不相关被排序成对标签的比例，例如一个不相关标签比相关标签的输出值更大。是在Y上的补集。
平均精确率：。这个方法评估相关标签高于一个特定相关标签的平均比率。
对于汉明损失、One-error、覆盖率、排序损失，值越小，优化表现越好。对于其它基于实例的评估方法，值越大，表现越好。
对于基于标签的方法，为了评价在每个标签上的分类器的二元分类表现，四个有关测试实例的基本量是常用的：（真阳性），（假阴性），（真阴性），（假阴性）。很明显，许多二元分类方法能基于这些量被得到。让表示某一个二元分类方法，基于标签的多标签方法能被定义在下列任何一种方式：
宏-B：。这个多标签方法通过假定每个标签一样重要被得到的。
微-B:。这个多标签方法通过假定每个实例一致重要被得到的。
在的公共选择中，宏/微-B值越大，表现越好。
5.标签关联性
学习多标签数据的主要挑战在于潜在的巨大输出空间。在这里，预测标签集的可能数量随着类标签数量的增长以指数倍方式增长。举个例子，一个带有20个类标签的标签空间将导致超过一百万可能标签集。因此，出现在训练集的许多标签集将很少有实例，如果它们单独学习将导致坏的表现。
为了处理巨大输出空间的挑战，一个共同的方法是利用标签关联性来促进学习过程[14]。举个例子，如果我们已经知道图片有标签“草”和“狮子”，图片带有标签“非洲”的可能性很高；如果文件与“法律”和“政治”相关联，该文件不太可能被标上“娱乐”。事实上，区分多标签学习和传统监督学习的基本问题在于实际上在多标签学习中利用标签关联性是至关重要的。
一个广泛使用的策略是直接从基于假定的关联模型的训练集中评估标签间的关联性。基于关联性的次序来被建模，评估技术能被大致分为三类：（a）第一阶 技术在一个逐个标签模式中解决多标签学习任务，因此忽略其它标签的共存，例如将多标签学习问题分解为许多的独立二元分类问题（一个问题对应一个标签）[2,13]；（b）第二阶 技术通过考虑标签间成对关联性来解决多标签学习任务，例如相关和不相关标签的次序[4,10]；（c）高阶 技术通过考虑标签间的高阶关联性来解决多标签学习任务，例如假定所有标签间关联性或标签的随机子集[11]。
另一个策略是采用标签关联性的领域知识作为多标签学习算法的输入。领域知识的一个传统来源对应于在某些应用例如文本分类上可得的标签分层（分类）[9]。这儿也有最近的策略，它尝试在学习多标签预测器的过程中发现和利用多标签关系[14]。
6.学习算法
为设计多标签数据的学习算法，自然会产生两种互补的思想。一方面，算法的自适应方法是通过算法适应数据，即采用流行的标准监督学习算法来处理多标签数据。另一方面，问题转化方法是通过将数据适应算法来实现的，例如将多标签数据转化以适应其他完善的学习框架。在过去的十年中，许多算法都是按照这些原理开发的[14]。本节简要介绍了四种代表性的算法，包括算法自适应方法Ml-knn(多标签k近邻)[13]和Rank-svm(排序支持向量机)[4]，问题转换方法CC(分类器链)[8]，Rakel(随机k-标签集)[11]。选择这些算法只是为了体现两个关键设计哲学的要点，这绝不排除其他多标签学习算法的重要性。
Ml-knn采用k近邻技术处理多标签数据[13]。具体地说，最大后验(MAP)规则通过对邻域标签信息进行推理被利用来对不可见的实例进行预测。给定多标签训练集和不可见实例，让表示定义在的的k邻域集。因此，下面的统计能够基于在中邻居的标签信息被计算：。即记录把第j个类标签作为它们的相关标签的邻居的数量。让代表在（例如拥有个带有相关标签的邻居）的条件下事件（例如把作为它的相关标签）成立的后验概率。相似的，让表示在相同条件下不为真的后验概率。基于MAP规则，的预测标签为：
（1）
根据贝叶斯规则，我们有和。因此，它足够通过评估先验概率和概率来做预测。这些条件可能性能通过频数计数策略从训练集中被评估[13]。总的来说，ML-KNN假定在标签学习过程中标签独立性和优化汉明损失（或相等地 宏/微-精确率）的评估方法。
RANK-SVM采用最大边界法来处理多标签数据[4]。尤其地，一组线性分类器被优化用来最小化经验等级损失。给定带有q个线性分类器的学习系统，它在每个多标签训练实例的边缘对应于
（2）
在这里，返还两个向量的内积。相等地，公式（2）考虑对每个相关-不相关成对标签判定超平面的l2距离：，此时返回在上最小余量。因此，在整个训练集上学习系统的边缘是：。在理想情况下，学习系统能够适当地排序对于每个训练实例中每个相关-不相关的标签对，大边际优化问题转变成为：
（3）
通过求和逼近最大值并引入松弛变量来适应违反的约束，公式（3）能被重构为：
（4）
在这里，是松弛变量集。公式（4）第一项对应学习系统的边缘，反之第二项对应于经验排序损失。公式（4）的解能通过以原始形式调用标准二次规划(QP)过程来被发现，或者结合在其对偶形式中核技巧。未见实例的标签集通过对每个在的分类器的输出取阈值来被预测。总体而言，RANK-SVM假定在它学习过程中二阶标签关联性和优化排序损失的评估方法。
CC将多标签学习问题转化为一系列二进制分类问题。具体而言，链中的子分类器是建立在前面预测的基础上的。在不失去通用性的情况下，假设中的所有类标签都在一条链中排序：。对于链中的第j个类标签，可以通过将前面的每个标签的相关性作为实例的额外特征来构造相应的二进制训练集：
（5）
Where
在这儿，表示类标签关于标签集的二进制值。如公式（5）所示，每个实例都附加一个额外的特征向量，表示这些在之前标签的相关性。在这之后，一个二进制分类器利用一些二进制学习算法B（例如可以对进行归纳。对于未见实例，它的标签集是通过迭代遍历分类器链来预测的。在上预测的的二进制赋值表示为，由下面递归地
（6）
因此，预测的标签集对应于：。显然，类标签上的链接顺序对CC的有效性有很大的影响。为了考虑链序的影响，可以用不同的随机链序来建立分类器链的集合。通常，cc假定在学习过程中高阶标签相关性（在所有标签之间）和优化了汉明损失的评价方法（或相当于宏/微-精度）。
RAKEL将多标签学习问题转化为多类分类问题的集合。具体而言，集合中的每个组件学习者都是通过考虑的随机集生成的。设表示含有k个随机类标签的k-标签集。相应地，设表示的幂集到自然数集的内射函数映射。针对，通过将原始标签空间缩小为可以构造相应的多类培训集：
（7）
在这里，在中的新转换标签集对应于：。如公式（7）所示，每个实例被转换为一个多类的单标签实例，方法是将和之间的交集映射为中的一个新标签。在此基础上，利用多类学习算法M，例如，为引入了一个多类分类器。为了彻底探索带有k-标签集的原始标签空间，可以创建n个随机k-标签集的集合，其中每个标签集都会产生一个多类分类器。对于未见的实例，它的标签集是通过引用以下两个量来预测的：
（8）
从概念上讲，计算可以从集合中获得的最大票数，而则计算从集合中得到的实际投票数。因此，预测的标签集对应于：。一般来说，CC在其学习过程假定高阶标签相关性(在标签子集之间)和对子集精度（关与K-标签集的评估)的评价方法进行了优化。
值得一提的是，许多标签学习算法主要是在标签空间包含中等数量(几十个或数百个)类标签的情况下工作的。尽管如此，在许多应用程序中的类标签数量可能很大。例如，一个网页可能会被来自超过一百万个维基百科类别的相关标签注释。在这种情况下，许多标签学习算法的计算复杂度可能会高得令人望而却步。即使对于二进制分解，这是学习多标签数据最简单的方式，考虑到大量的类标签，建立每个标签的一个独立分类器仍然是计算量太大的。因此，需要采用特定的策略来处理大量标签。一次可行策略是利用相关标签的稀疏性找到原始标签空间的低维嵌入，并在嵌入的标签空间内建立分类模型[12]。另一种策略是根据树结构将原始标签空间划分为不同的簇，在每个叶节点内建立分类模型[1]。
7.理论
多标签损失函数通常不凸且不连续，很难直接优化。因此，在实践中，大多数学习算法都采用优化(凸)代理损失函数。关于代理损失函数的一致性，有几种理论研究，即随着训练集大小的增加，学习者的代理损失的预期风险是否收敛于多标签损失的贝叶斯风险。近年来，基于代理损失函数的多标签学习的一致性得到了一个充分必要条件[5]。
对于汉明损失，最先进的多标签学习方法被证明是不一致的[5]。对于排序损失，证明了在标签对上定义成对的凸代理损失不可能是一致的；因此，引入了部分排序损失的多标签学习，并提供了一些成对一致的代理损失函数[5]。定义在单标号上单变量凸代理损失与基于双向排序问题[3]的部分排序损失是一致的，尽管约简放松了原始目标。
8.延申
多实例多标签学习(MIML)[15]试图从训练集导出函数，其中是一组实例包，而是一组与关联的类标签集。MIML与多标签学习的主要区别在于MIML中的每个例子都由一组实例集而不是单个实例表示。该框架适用于涉及具有固有结构的复杂对象的任务；例如，文本文档可以由一组实例集表示，每个实例对应于一节或一段。MIML除了利用关于学习预测器的结构信息外，还提供了发现语义信息和输入模式之间关系的可能性；例如，可以发现，由于文档的几个特殊段落，文档可以拥有一个特定的标签。
超集标签学习(SLL)[7]试图从训练集导出一个函数，其中是一个实例，是与相关联的候选标签的集合。这样，(未知的)真正标签就属于了。SLL和多标签学习的主要区别在于SLL中的每个实例都与其中只有一个标签有效的多个候选标签相关联。此框架适用于可随时获得超集标签信息的任务；例如，图像中的人脸可以与所有的在图像周围的文本中提到的名称相关联，其中只
全文共6146字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[3028]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
