【NSR特别专题】周志华：弱监督学习简介「全文翻译」

2018 年 3 月 24 日 德先生

本文经授权转载自“人工智能前沿讲习班”

编者按：《国家科学评论》于2018年1月发表“机器学习”特别专题，由周志华教授组织并撰写文章。专题内容还包括对AAAI前主席Tom Dietterich的访谈，徐宗本院士、杨强教授、朱军博士、李航博士、张坤博士和Bernhard Scholkopf等人的精彩文章。本文是对周志华教授所写的《弱监督学习简介》的全文翻译。

弱监督学习简介

作者：周志华

翻译：遢遢

校对：叶奎宋平雷智文刘市祺

摘要

监督学习技术通过学习大量训练数据来构建预测模型，其中每个训练样本都有其对应的真值输出。尽管现有的技术已经取得了巨大的成功，但值得注意的是，由于数据标注过程的高成本，很多任务很难获得如全部真值标签这样的强监督信息。因此，能够使用弱监督的机器学习技术是可取的。本文综述了弱监督学习的一些研究进展，主要关注三种弱监督类型：不完全监督，即只有一部分样本有标签；不确切监督，即训练样本只有粗粒度的标签；以及不准确监督，即给定的标签不一定总是真值。

关键词：机器学习，弱监督学习，监督学习

1 概述

机器学习在多种任务中取得了巨大成功，尤其是在分类和回归等监督学习任务中。预测模型是从一个包含大量训练样本的训练数据集中学习，其中每个样本都对应一个事件或对象。一个训练样本由两部分组成：一个描述事件/对象的特征向量（或实例），以及一个表示真值输出的标签。在分类任务中，标签代表训练样本所属的类别；在回归任务中，标签是样本所对应的实数值。大部分成功的技术，例如深度学习【1】，都需要含有真值标签的大规模训练数据集；然而在很多任务中，由于数据标注过程的高昂代价，很难获得强监督信息。因此，研究者十分希望机器学习技术能够在弱监督前提下工作。

弱监督通常分为三种类型。第一种是不完全监督，即只有训练数据集的一个（通常很小的）子集有标签，其它数据则没有标签。在很多任务中都存在这种情况。例如，在图像分类中，真值标签是人工标注的；从互联网上获得大量的图片很容易，然而由于人工标注的费用，只能标注其中一个小子集的图像。第二种是不确切监督，即只有粗粒度的标签。又以图像分类任务为例。我们希望图片中的每个物体都被标注；然而我们只有图片级的标签而没有物体级的标签。第三种是不准确监督，即给定的标签并不总是真值。出现这种情况的原因有，标注者粗心或疲倦，或者一些图像本身就难以分类。

弱监督学习是一个总括性的术语，它涵盖了试图通过较弱的监督来构建预测模型的各种研究。在本文中，我们将会讨论这一领域的一些进展，重点放在不完全、不确切和不准确的监督条件下进行的学习。我们会分别讨论这三种情形，但是值得指出的是，在实际操作中，它们常常同时出现。为了简便起见，在本文中我们考虑有两个可交换的类别Y、N的二分类问题。形式化表达为，在强监督条件下，监督学习任务就是从训练数据集D = {(x_1, y_1), …, (x_m, y_m)}中学习 f: X -> Y , 其中X是特征空间，Y = {Y, N}, x_i 属于X, y_i 属于Y。

我们假设 (x_i, y_i) 是根据未知的独立同分布D生成的。换言之，是 i.i.d. 样本。

图1示例了我们将在本文中讨论的三种弱监督学习。

图1:三种弱监督学习的示意图。长方形表示特征向量；红色或蓝色表示标签；“？”表示标注可能是不准确的。中间的子图表示了几种弱监督的混合情形。

2 不完全监督

不完全监督是指训练数据中只有一小部分数据有标签，而大部分数据没有标签，且这一小部分有标签的数据不足以训练一个好的模型。形式化表达为，模型的任务是学习：f: X -> Y，训练数据为：D = {(x_1, y_1), …, (x_l, y_l), x_{l+1}, …, x_m}, 即有l个数据有标签（如y_i所示），u = m-l 个数据没有标签，其他条件与强监督学习（如摘要最后的定义）相同。为便于讨论，我们将l个已经标注的数据记为「标注数据」，u个没有标签的数据称为「未标注数据」。

有两种主要的技术能够实现此目的，即主动学习（active learning)【2】和半监督学习（semi-supervised learning）【3-5】。

主动学习假设有一个「神谕」（oracle），比如人类专家，可以向它查询所选未标注数据的真值标签。相比之下，半监督学习试图在没有人为干预的前提下，自动利用已标注数据、以及未标注数据来提升学习性能。有一种特殊的半监督学习，称为直推式学习（transductive learning），它与（纯）半监督学习之间的差别在于，对测试数据（训练模型要预测的数据）的假设不同。直推式学习持有“封闭世界”的假设，即测试数据是事先给定的，且目标就是优化模型在测试数据上的性能；换句话说，未标注数据就是测试数据。纯半监督学习持有“开放世界”的假设，即测试数据是未知的，且未标注数据不一定是测试数据。图2直观的表示了主动学习、（纯）半监督学习、直推学习之间的区别。

图2: 主动学习、（纯）半监督学习以及直推学习。

2.1 有人为干预

主动学习【2】假设未标注数据的真值标签可以向先知查询。简单起见，假设标注成本只与查询次数有关。那么主动学习的目标就是最小化查询次数，以使训练一个好模型的成本最小。

给定少量标注数据以及大量未标注数据，主动学习倾向于选择最有价值的未标注数据来查询先知。衡量选择的价值，有两个广泛使用的标准，即信息量（informativeness）和代表性（representativeness）【6】。信息量衡量一个未标注数据能够在多大程度上降低统计模型的不确定性，而代表性衡量一个样本在多大程度上能代表模型的输入分布。

不确定抽样（uncertainty sampling）和投票询问（query-by-committee）是基于信息量的典型方法。前者训练单个学习器，选择学习器最不确信的样本向先知询问标签信息【7】。后者生成多个学习器，选择各个学习器争议最大的样本向先知询问标签信息【8，9】。基于代表性的模型通常的目标是用聚类方法来挖掘未标注数据的集群结构【10，11】。

基于信息量的方法，主要缺点是为了建立选择查询样本所需的初始模型，而严重依赖于标注数据，并且当标注样本较少时，其性能通常不稳定。基于代表性的方法，主要缺点在于其性能严重依赖于由未标注数据控制的的聚类结果，当标注数据较少时尤其如此。因此，几种最近的主动学习方法尝试同时利用信息量和代表性度量【6，12】。

关于主动学习有很多理论性的研究。例如，已经证明对于可实现（realizable）情况（假设数据在假设的空间中完全可分），随着样本复杂性的增加，主动学习的性能可以获得指数提升【13，14】。对于不可实现（non-realizable）的情况（即由于噪声的存在，以致数据在任何假设下都不完全可分），在没有对噪声模型的先验假设时，主动学习的下确界相当于被动学习的上确界，换句话说，主动学习并不是非常有用。当假设噪声为Tsybakov噪声模型时，我们可以证明，在噪声有界的条件下，主动学习的性能可呈指数级提升【16，17】；如果能够挖掘数据的一些特定性质，像多视角结构（multi-view structure），那么即使在不对噪声进行限制的情况下，其性能也能呈指数级提升【18】。换句话说，只要设计得巧妙，主动学习在解决困难问题时仍然有用。

2.2 无人为干预

半监督学习【3-5】是指在不询问人类专家的条件下挖掘未标注数据。为什么未标注数据对于构建预测模型也会有用？做一个简单的解释【19】，假设数据来自一个由n个高斯分布混合的高斯混合模型，也就是说：f(x | \theta) = \sum_{j=1}^n \alpha_j f(x | \theta_j) (1)其中\alpha_j为混合系数，\sum_{j=1}^n \alpha_j = 1 并且 \theta = {\theta_j} 是模型参数。在这种情况下，标签y_i可以看作一个随机变量，其分布 P(y_i | x_i, g_i)由混合成分g_i和特征向量x_i决定。最大化后验概率有：h(x) = argmax_c \sum_{j=1}^n P(y_i = c | g_i = j, x_i) \times P(g_i = j | x_i) (2)。其中：P(g_i = j | x_i) = \frac{\alpha_j f(x_i | \theta_j)} {\sum_{k=1}^n \alpha_k f(x_i | \theta_k)} (3)

h(x)可以通过用训练数据估计 P(y_i = c | g_i = j, x_i) 和 P(g_i = j | x_i) 来求得。很明显只有第一项需要需要标签信息。因此，未标注数据可以用来估计提升对第二项的估计，从而提升学习模型的性能。

图3: 未标注数据的作用。

图3给出了一个直观的解释。如果我们只能根据唯一的正负样本点来预测，那我们就只能随机猜测，因为测试样本恰好落在了两个标注样本的中间位置；如果我们能够观测到一些未标注数据，例如图中的灰色样本点，我们就能以较高的置信度判定测试样本为正样本。在此处，尽管未标注样本没有明确的标签信息，它们却隐晦地包含了一些数据分布的信息，而这对于预测模型是有用的。

实际上，在半监督学习中有两个基本假设，即聚类假设（cluster assumption）和流形假设（manifold assumption）；两个假设都是关于数据分布的。前者假设数据具有内在的聚类结构，因此，落入同一个聚类的样本类别相同。后者假设数据分布在一个流形上，因此，相近的样本具有相似的预测。两个假设的本质都是相似的数据输入应该有相似的输出，而未标注数据有助于揭示出样本点之间的相似性。

半监督学习有四种主要方法，即生成式方法（generative methods），基于图的方法（graph-based methods），低密度分割法（low-density separation methods）以及基于分歧的方法（disagreement methods）。

生成式方法【19，20】假设标注数据和未标注数据都由一个固有的模型生成。因此，未标注数据的标签可以看作是模型参数的缺失，并可以通过EM算法（期望-最大化算法）等方法进行估计【21】。这类方法随着为拟合数据而选用的不同生成模型而有所差别。为了达到好的性能，通常需要相关领域的知识来选择合适的生成模型。也有一些将生成模型和判别模型的优点结合起来的尝试【22】。

基于图的方法构建一个图，其节点对应训练样本，其边对应样本之间的关系（通常是某种相似度或距离），而后依据某些准则将标注信息在图上进行扩散；例如标签可以在最小分割图算法得到的不同子图内传播【23】。很明显，模型的性能取决于图是如何构建的【26-28】。值得注意的是，对于m个样本点，这种方法通畅需要O(m^2)存储空间和O(m^3)计算时间复杂度。因此，这种方法严重受制于问题的规模；而且由于难以在不重建图的情况下增加新的节点，所以这种方法天生难以迁移。

图4: SVM和S3VM的不同分类界面，SVM只考虑标注数据（“+／-”点），S3VM既考虑标注数据也考虑未标注数据（灰色点）。

低密度分割法强制分类边界穿过输入空间的低密度区域。最著名的代表就是S3VMs（半监督支持向量机）【29-31】。图4示意了一般的监督SVM和S3VM的区别。很明显，S3VM试图在保持所有标注样本分类正确的情况下，建立一个穿过低密度区域的分类界面。这一目标可以通过用不同方法给未标注数据分配标签来达成，而这往往会造成优化问题很复杂。因此，在这个方向很多的研究都致力于开发高效的优化方法。

基于分歧的方法【5，32，33】生成多个学习器，并让它们合作来挖掘未标注数据，其中不同学习器之间的分歧是让学习过程持续进行的关键。最为著名的典型方法——联合训练（co-traing），通过从两个不同的特征集合（或视角）训练得到的两个学习器来运作。在每个循环中，每个学习器选择其预测置信度最高的未标注样本，并将其预测作为样本的伪标签来训练另一个学习器。这种方法可以通过学习器集成来得到很大提升【34，35】。值得注意的是，基于分歧的方法提供了一种将半监督学习和主动学习自然地结合在一起的方式：它不仅可以让学习器相互学习，对于两个模型都不太确定或者都很确定但相互矛盾的未标注样本，还可以被选定询问“先知”。

值得指出的是，尽管我们期望通过利用未标注数据来提升学习性能，但是在一些情况下，在经过半监督学习之后性能反而会下降。这个问题已经被提出并且研究了很多年【36】，然而直到最近才有一些实质性的进展被报道出来【37】。我们现在知道，对未标注数据的利用自然会要在多个模型中进行选择，而不恰当的选择可能会导致较差的性能。让半监督学习“更安全”的基本策略是优化最差情况下的性能，也许可以通过模型集成机制来实现。

关于半监督学习有大量的理论研究【4】，有些甚至要早于“半监督学习”这个词语的出现【38】。实际上最近有一篇研究，透彻研究了基于分歧的方法【39】。

3 不确切监督

不确切监督是指在某种情况下，我们有一些监督信息，但是并不像我们所期望的那样精确。一个典型的情况是我们只有粗粒度的标注信息。例如，在药物活性预测中【40】，目标是建立一个模型学习已知分子的知识，来预测一种新的分子是否能够用于某种特殊药物的制造。一种分子可能有很多低能量的形态，这种分子能否用于制作该药物取决于这种分子是否有一些特殊形态。然而，即使对于已知的分子，人类专家也只知道其是否合格，而并不知道哪种特定形态是决定性的。

形式化表达为，这一任务是学习 f: X -> Y ，其训练集为 D = {(X_1, y_1), …, (X_m, y_m)}，其中 X_i = {x_{I, 1}, …, x_{I, m_i}}, X_i属于X，且被称为一个包（bag），x_{i, j}属于X，是一个样本（j属于{1, …, m_i}）。m_i是X_i中的样本个数，y_i属于Y = {Y, N}。当存在x_{i, p}是正样本时，X_i就是一个正包（positive bag），其中p是未知的且p属于{1, …, m_i}。模型的目标就是预测未知包的标签。这被称为多示例学习（multi-instance learning）【40，41】。

对于多示例学习，有很多有效的算法。实际上，几乎所有的监督学习算法都有其对应的多示例版本。大多数算法都试图调整单实例监督学习算法，使其适配多示例表示，其主要方法是将对示例区分转变到对包的区分上来【42】；其他一些算法试图通过表示转换，调整多实例表示使其适配单实例算法【43，44】。还有一种分类方式，将算法分为：示例空间模型，即将示例级的反馈进行融合；包空间模型，即将包做为一个整体；以及嵌入空间模型，即学习是在一个嵌入特征空间中进行的。值得注意的是，示例通常被视为独立同分布的样本；然而【46】表明，尽管包可假设为独立同分布的，但是多示例学习中的样本不应被假设为相互独立的。基于这一观点，一些有效的算法被提了出来【47】。

多示例学习已经成功应用于多种任务，例如图像分类、检索、注释【48-50】，文本分类【51，52】，垃圾邮件检测【53】，医疗诊断【54】，人脸、目标检测【55，56】，目标类别发现【57】，目标跟踪【58】等等。在这些任务中，我们可以很自然地将一个真实的目标（例如一张图片或一个文本文档）看作一个包；然而，不同于药物活性预测中包里有天然的示例（即分子的不同形态），这里的示例需要生成。一个包生成器明确如何生成示例来组成一个包。通常情况下，从一幅图像中提取的很多小图像块就作为可以这个图像的示例，而章节、段落甚至是句子可以作为一个文本文档的示例。尽管包生成器对于学习效果有重要的影响，但直到最近才出现关于图像包生成器的全面研究【59】；研究表明一些简单的密集取样包生成器要比复杂的生成器性能更好。图5显示了两个简单而有效的图像包生成器。

图5: 图像包生成器。假设每张图片的尺寸为8*8个像素，每个小块的尺寸为2*2个像素。单块（Single Blob, SB）以无重叠地滑动的方式，会给一个图片生成16个实例，即每个实例包含4个像素。领域单块（SBN）以有重叠地滑动的方式，则会给每一个图片生成9个实例，即每个实例包含20个像素。

多示例学习的原始目标是预测未知包的标签；但有研究试图识别使得正包为正的关键示例（key instance）【31，60】。这对于有些任务是很有用的，例如在没有精细标注的图像数据中寻找感兴趣的区域。值得注意的是，标准的多示例学习【40】假设每个正包都必须包含一个关键示例，而有的研究则假设没有关键示例，每个示例都对包的标签有贡献【61，62】，或甚至假设有多个概念，仅当包中示例同时满足所有概念时才是正包【63】。在【41】中可以找到更多变体。

早期的理论研究结果【64-66】表明多示例学习很难应对异质（heterogeneous）案例，即包中的示例由不同的分类规则进行分类，而在同质（homogeneous）案例是可学习的，即包所有示例按照同一规则进行分类。幸运的是，几乎所有实际的多示例任务都属于同质案例。他们假设包中示例相互独立。包中示例没有相互独立假设的分析更具挑战性，也出现得晚得多，这些分析表明在同质性类中时，至少在一些情况下包之间的任意分布都是可学习的【67】。然而，与算法和应用研究的繁荣相比，多示例学习的理论成果非常少，因为这种分析实在是太困难了。

4 不准确监督

不准确监督关注监督信息不总是真值的情形；换句话说，有些标签信息可能是错误的。其形式化表示与概述结尾部分几乎完全相同，除了训练数据集中的y_i可能是错误的。

一个典型的情况是在标签有噪声的条件下学习【68】。已有很多相关理论研究【69-71】，这些研究大多都假设存在随机类型的噪声，即标签受制于随机噪声。在实际中，一个基本的想法是识别潜在的误分类样本【72】，而后进行修正。例如，数据编辑（data-editing）方法【73】构建了一个相对邻域图，其中的每个节点对应一个训练样本，连接标签不同的两个节点的边称为一个切边（cut edge）。而后衡量切边权重的统计数据，直觉上，示例连接的切边越多则越可疑。可以删除或者重新标注可疑示例，如图6所示。值得指出的是，这种方法通常依赖近邻信息，因此，这类方法在高维特征空间并不十分可靠，因为当数据稀疏的时候，领域识别常常并不可靠。

图6: 识别并删除或重新标注可疑点。

一个最近出现的不准确监督的情景发生在众包模式中（crowdsourcing）【74】，即一个将工作外包给个人的流行模式。对机器学习而言，用众包模式为训练数据收集标签是一种经济的方式。具体而言，未标注数据被外包给大量的工人去标注。在著名的众包系统 Amazon Mechanical Turk（ AMT）上用户可以提交一个任务，例如标注图像有树还是没有树，并向标注工人支付少量的报酬。这些工人通常来自大社会，他们每个人都会执行多种多样的任务。他们通常是相互独立的，报酬不高，并根据自己的判断提供标签。在工人之中，一些可能比另一些更可靠；然而用户通常不会事先知道，因为工人的身份是保密的。还有可能存在“垃圾制造者”，他们几乎是随机地提供标签（例如一个机器人冒充人类来获取报酬），或者“反抗者”，他们故意提供错误答案。除此之外，有些任务对于很多工人来说可能太困难了。因此，用从众包返回的不准确的监督信息进行学习，并保持学习到的性能，是有意义的。

很多研究试图从众包标签中推理出真值标签。有集成方法【35】的理论支持的多数票策略在实际中得到了广泛应用，并有不错的性能【75，76】，因此常常作为基线标准。如果工人的质量和任务的难度可以建模，那么我们就可期望实现更好的性能，其典型的方法是在不同的任务中给工人不同的权重。为此，一些方法试图建立概率模型，而后使用EM算法来进行估计【77，78】。最小最大化熵准则也在一些方法中得到使用【35】。垃圾提供者可以在概率模型中被剔除【79】。最近有研究给出了剔除低品质工人的一般理论条件【80】。

对机器学习而言，众包通常用来收集标签，而从这些数据中学习得到的模型的性能要比标签的质量更为重要。有很多关于在弱老师或众包标签学习的研究【81，82】，这与用噪声标签学习很相近（在本节开头部分有介绍）；其中的区别在于，对于众包系统而言，我们很容易重复提取某个示例的众包标签。因此，在众包学习中考虑节约成本的效果是很重要的，【83】给出了一个最小化的众包标签数量的上界，也就是说有效众包学习的最小化成本。很多研究工作致力于任务分配和预算分配，试图在精度和标注花费之间取得平衡。为此，离线的不能自适应的任务分配机制【84，85】，以及在线的自适应的任务分配机制【86，87】都有理论支撑。值得注意的是，大多数研究都采用了Dawid-Skene模型，它假设不同任务的潜在成本都是相同的，而很少研究更复杂的成本设置。

设计一个有效的众包协议也十分重要。在【89】中，提供了不确定选项，这样工人在不确定的时候不会被强制要求给出标签；这个选项在理论上能够提升标签的可靠性【90】。在【91】中，引入了一个“双倍或没有”的刺激兼容机制，以确保工人在自已确信的基础上进行诚实的回答；假设所有的工人都想最大化他们期望报酬，该机制可以剔除垃圾提供者。

5 结论

在带有真值标签的大量训练样本的强监督条件下，监督学习技术已经取得了巨大的成功。然而，在真实的任务中，收集监督信息往往代价高昂，因此探索弱监督学习通常是更好的方式。

本文聚焦于三种典型的弱监督学习：不完全、不确切和不准确监督。尽管三者可以分开讨论，但在实际中它们常常同时发生，如图1所示。当然也有针对“混合”情况的相关研究【52，92，93】。此外，还有一些其他类型的弱监督。例如，延时监督也可以视为弱监督，它主要出现在增强学习环境中【94】。由于篇幅限制，本文与其说是一个全面的总结回顾，不如说只是一个文献的索引。对于一些细节感兴趣的读者可以阅读参考文献中的相关文章。值得注意的是，越来越多的研究者开始关注弱监督学习，例如部分监督学习（partially supervised learning），主要关注不完全监督的学习【95】，【96，97】，同时还有一些其他关于弱监督的讨论。

为了便于讨论，本文只关注了二分类问题，而大多数讨论经稍事修改后就可推广至多类问题或回归问题。在多类分类任务中可能出现更复杂的情况【98】。在考虑多标签学习（multi-label learning）【99】时情况可能更为复杂，此时每个样本可能被同时赋予多个标签。用不完全监督举个例子：除了标注示例和未标注示例，多标签任务还会遇到部分标注示例，也就是说一个训练示例只给出了一部分标签【100】。即使只考虑标注数据和未标注数据，这种情况也要比单标签有更多选项，例如在主动学习中，对于选定的未标注示例，既可以询问示例的所有标签【101】，也可以询问某一个特定标签【102】，还可以给一对标签的相关排序【103】。尽管如此，不论是何种数据、何种任务，弱监督学习正在变得越来越重要。

参考文献：

1、Goodfellow I, Bengio Y and Courville A. Deep Learning. Cambridge: MIT Press, 2016.

2、Settles B. Active learning literature survey. Technical Re- port 1648. Department of Computer Sciences, University of Wisconsin at Madison, Wisconsin, WI, 2010 [ http://pages. cs.wisc.edu/∼bsettles/pub/settles.activelearning.pdf].

3、Chapelle O, Scho ̈lkopf B and Zien A (eds). Semi-Supervised Learning. Cambridge: MIT Press, 2006.

4、Zhu X. Semi-supervised learning literature survey. Technical Report 1530. Department of Computer Sciences, University of Wisconsin at Madison, Madison, WI, 2008 [ http://www.cs. wisc.edu/∼jerryzhu/pub/ssl ̇survey.pdf].

5、Zhou Z-H and Li M. Semi-supervised learning by disagreement. Knowl Inform Syst 2010; 24: 415–39.

6、Huang SJ, Jin R and Zhou ZH. Active learning by querying informative and representative examples. IEEE Trans Pattern Anal Mach Intell 2014; 36: 1936–49.

7、Lewis D and Gale W. A sequential algorithm for training text classi ers. In 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Dublin, Ireland, 1994; 3–12.

8、Seung H, Opper M and Sompolinsky H. Query by committee. In 5th ACM Workshop on Computational Learning Theory, Pitts- burgh, PA, 1992; 287–94.

9、Abe N and Mamitsuka H. Query learning strategies using boosting and bagging. In 15th International Conference on Ma- chine Learning, Madison, WI, 1998; 1–9.

10、Nguyen HT and Smeulders AWM. Active learning using pre- clustering. In 21st International Conference on Machine Learn- ing, Banff, Canada, 2004; 623–30.

11、Dasgupta S and Hsu D. Hierarchical sampling for active learn- ing. In 25th International Conference on Machine Learning, Helsinki, Finland, 2008; 208–15.

12、Wang Z and Ye J. Querying discriminative and representative samples for batch mode active learning. In 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, 2013; 158–66.

13、Dasgupta S, Kalai AT and Monteleoni C. Analysis of perceptron-based active learning. In 28th Conference on Learn- ing Theory, Paris, France, 2005; 249–63.

14、Dasgupta S. Analysis of a greedy active learning strategy. In Advances in Neural Information Processing Systems 17, Cambridge, MA: MIT Press, 2005; 337–44.

15、Ka ̈a ̈ria ̈inen M. Active learning in the non-realizable case. In 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Sydney, Australia, 2006; 63–77.

16、Balcan MF, Broder AZ and Zhang T. Margin based active learn- ing. In 20th Annual Conference on Learning Theory, San Diego, CA, 2007; 35–50.

17、Hanneke S. Adaptive rates of convergence in active learning. In 22nd Conference on Learning Theory, Montreal, Canada, 2009.

18、Wang W and Zhou ZH. Multi-view active learning in the non-realizable case. In Advances in Neural Information Processing Systems 23, Cambridge, MA: MIT Press, 2010; 2388–96.

19、Miller DJ and Uyar HS. A mixture of experts classi er with learning based on both labelled and unlabelled data. In Advances in Neural Information Processing Systems 9, Cam- bridge, MA: MIT Press, 1997; 571–7.

20、Nigam K, McCallum AK and Thrun S et al. Text classi cation from labeled and unlabeled documents using EM. Mach Learn 2000; 39: 103–34.

21、Dempster AP, Laird NM and Rubin DB. Maximum likelihood from incomplete data via the EM algorithm. J Roy Stat Soc B Stat Meth 1977; 39: 1–38.

22、Fujino A, Ueda N and Saito K. A hybrid genera- tive/discriminative approach to semi-supervised classier design. In 20th National Conference on Articial Intelligence, Pittsburgh, PA, 2005; 764–9.

23、Blum A and Chawla S. Learning from labeled and unlabeled data using graph mincuts. In ICML, 2001; 19–26.

24、Zhu X, Ghahramani Z and Lafferty J. Semi-supervised learn- ing using Gaussian elds and harmonic functions. In 20th International Conference on Machine Learning, Washington, DC, 2003; 912–9.

25、Zhou D, Bousquet O and Lal TN et al. Learning with local and global consistency. In Advances in Neural Information Processing Systems 16, Cambridge, MA: MIT Press, 2004; 321–8.

26、Carreira-Perpinan MA and Zemel RS. Proximity graphs for clustering and manifold learning. In Advances in Neural Information Processing Systems 17, Cambridge, MA: MIT Press, 2005; 225–32.

27、Wang F and Zhang C. Label propagation through linear neighborhoods. In 23rd International Conference on Machine Learning, Pittsburgh, PA, 2006; 985–92.

28、Hein M and Maier M. Manifold denoising. In Advances in Neural Information Processing Systems 19, Cambridge, MA: MIT Press, 2007; pp. 561–8.

29、Joachims T. Transductive inference for text classi cation using support vector machines. In 16th International Conference on Machine Learning, Bled, Slovenia, 1999; 200–9.

30、Chapelle O and Zien A. Semi-supervised learning by low density separation. In 10th International Workshop on Articial Intelligence and Statistics, Barbados, 2005; 57–64.

31、Li YF, Tsang IW and Kwok JT et al. Convex and scalable weakly labeled SVMs. J Mach Learn Res 2013; 14: 2151–88.

32、Blum A and Mitchell T. Combining labeled and unlabeled data with co- training. In 11th Conference on Computational Learning Theory, Madison, WI, 1998; 92–100.

33、Zhou Z-H and Li M. Tri-training: exploiting unlabeled data using three classiers. IEEE Trans Knowl Data Eng 2005; 17: 1529–41.

34、Zhou Z-H. When semi-supervised learning meets ensemble learning. In 8th International Workshop on Multiple Classi er Systems, Reykjavik, Iceland, 2009; 529–38.

35、Zhou Z-H. Ensemble Methods: Foundations and Algorithms. Boca Raton: CRC Press, 2012.

36、Cozman FG and Cohen I. Unlabeled data can degrade classi cation performance of generative classi ers. In 15th International Conference of the Florida Arti cial Intelligence Research Society, Pensacola, FL, 2002; 327–31.

37、Li YF and Zhou ZH. Towards making unlabeled data never hurt. IEEE Trans Pattern Anal Mach Intell 2015; 37: 175–88.

38、Castelli V and Cover TM. On the exponential value of labeled samples. Pattern Recogn Lett 1995; 16: 105–11.

39、Wang W and Zhou ZH. Theoretical foundation of co-training and disagreement-based algorithms. arXiv:1708.04403, 2017.

40、Dietterich TG, Lathrop RH and Lozano-Pe ́rez T. Solving the multiple-instance problem with axis-parallel rectangles. Artif Intell 1997; 89: 31–71.

41、Foulds J and Frank E. A review of multi-instance learning assumptions. Knowl Eng Rev 2010; 25: 1–25.

42、Zhou Z-H. Multi-instance learning from supervised view. J Comput Sci Technol 2006; 21: 800–9.

43、Zhou Z-H and Zhang M-L. Solving multi-instance problems with classi er ensemble based on constructive clustering. Knowl Inform Syst 2007; 11: 155–70.

44、Wei X-S, Wu J and Zhou Z-H Scalable algorithms for multi-instance learning. IEEE Trans Neural Network Learn Syst 2017; 28:975–87.

45、Amores J. Multiple instance classi cation: review, taxonomy and comparative study. Artif Intell 2013; 201: 81–105.

46、Zhou Z-H and Xu J-M. On the relation between multi-instance learning and semi-supervised learning. In 24th International Conference on Machine Learning, Corvallis, OR, 2007; 1167–74.

47、Zhou Z-H, Sun Y-Y and Li Y-F. Multi-instance learning by treating instances as non-i.i.d. samples. In 26th International Conference on Machine Learning, Montreal, Canada, 2009; 1249–56.

48、Chen Y and Wang JZ. Image categorization by learning and reasoning with regions. J Mach Learn Res 2004; 5: 913–39.

49、Zhang Q, Yu W and Goldman SA et al. Content-based image retrieval using multiple-instance learning. In 19th International Conference on Machine Learning, Sydney, Australia, 2002; 682–9.

50、Tang JH, Li HJ and Qi GJ et al. Image annotation by graph-based inference with integrated multiple/single instance representations. IEEE Trans Multimed 2010; 12: 131–41.

51、Andrews S, Tsochantaridis I and Hofmann T. Support vector machines for multiple-instance learning. In Advances in Neural Information Processing Systems 15, Cambridge, MA: MIT Press, 2003; 561–8.

52、Settles B, Craven M and Ray S. Multiple-instance active learning. In Advances in 53、Neural Information Processing Systems 20, Cambridge, MA: MIT Press, 2008; 1289–96.

Jorgensen Z, Zhou Y and Inge M. A multiple instance learning strategy for combating good word attacks on spam lters. J Mach Learn Res 2008; 8: 993– 1019.

54、Fung G, Dundar M and Krishnappuram B et al. Multiple instance learning for computer aided diagnosis. In Advances in Neural Information Processing Sys- tems 19, Cambridge, MA: MIT Press, 2007; 425–32.

55、Viola P, Platt J and Zhang C. Multiple instance boosting for object detection. In Advances in Neural Information Processing Systems 18, Cambridge, MA: MIT Press, 2006; 1419–26.

56、Felzenszwalb PF, Girshick RB and McAllester D et al. Object detection with discriminatively trained part-based models. IEEE Trans Pattern Anal Mach Intell 2010; 32: 1627–45.

57、Zhu J-Y, Wu J and Xu Y et al. Unsupervised object class discovery via saliency- guided multiple class learning. IEEE Trans Pattern Anal Mach Intell 2015; 37: 862–75.

58、Babenko B, Yang MH and Belongie S. Robust object tracking with online multi- ple instance learning. IEEE Trans Pattern Anal Mach Intell 2011; 33: 1619–32.

59、Wei X-S and Zhou Z-H. An empirical study on image bag generators for multi-instance learning. Mach Learn 2016; 105:155–98.

60、Liu G, Wu J and Zhou ZH. Key instance detection in multi-instance learning. In 4th Asian Conference on Machine Learning, Singapore, 2012; 253–68.

61、Xu X and Frank E. Logistic regression and boosting for labeled bags of instances. In 8th Paci c-Asia Conference on Knowledge Discovery and Data Mining, Sydney, Australia, 2004; 272–81.

62、Chen Y, Bi J and Wang JZ. MILES: multiple-instance learning via embedded instance selection. IEEE Trans Pattern Anal Mach Intell 2006; 28: 1931–47.

63、Weidmann N, Frank E and Pfahringer B. A two-level learning method for gen- eralized multi-instance problem. In 14th European Conference on Machine Learning, Cavtat-Dubrovnik, Croatia, 2003; 468–79.

64、Long PM and Tan L. PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Mach Learn 1998; 30: 7–21.

65、Auer P, Long PM and Srinivasan A. Approximating hyper-rectangles: learning and pseudo-random sets. J Comput Syst Sci 1998; 57: 376–88.

66、Blum A and Kalai A. A note on learning from multiple-instance examples. Mach Learn 1998; 30: 23–9.

67、Sabato S and Tishby N. Homogenous multi-instance learning with arbitrary dependence. In 22nd Conference on Learning Theory, Montreal, Canada, 2009.

68、Fre ́nay B and Verleysen M. Classi cation in the presence of label noise: a survey. IEEE Trans Neural Network Learn Syst 2014; 25: 845–69.

69、Angluin D and Laird P. Learning from noisy examples. Mach Learn 1988; 2: 343–70.

70、Blum A, Kalai A and Wasserman H. Noise-tolerant learning, the parity problem, and the statistical query model. J ACM 2003; 50: 506–19.

71、Gao W, Wang L and Li YF et al. Risk minimization in the presence of label noise. In 30th AAAI Conference on Arti cial Intelligence, Phoenix, AZ, 2016; 1575–81.

72、Brodley CE and Friedl MA. Identifying mislabeled training data. J Artif Intell Res 1999; 11: 131–67.

73、Muhlenbach F, Lallich S and Zighed DA. Identifying and handling mislabelled instances. J Intell Inform Syst 2004; 22: 89–109.

74、Brabham DC. Crowdsourcing as a model for problem solving: an introduction and cases. Convergence 2008; 14: 75–90.

75、Sheng VS, Provost FJ and Ipeirotis PG. Get another label? Improving data 8. quality and data mining using multiple, noisy labelers. In 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Ve- gas, NV, 2008; 614–22.

76、Snow R, O’Connor B and Jurafsky D et al. Cheap and fast - but is it good? Evaluating non-expert annotations for natural language tasks. In 2008 Conference on Empirical Methods in Natural Language Processing, Honolulu, HI, 2008; 254–63.

77、Raykar VC, Yu S and Zhao LH et al. Learning from crowds. J Mach Learn Res 2010; 11: 1297–322.

78、Whitehill J, Ruvolo P and Wu T et al. Whose vote should count more: opti- mal integration of labels from labelers of unknown expertise. In Advances in Neural Information Processing Systems 22, Cambridge, MA: MIT Press, 2009; 2035–43.

79、Raykar VC and Yu S. Eliminating spammers and ranking annotators for crowd- sourced labeling tasks. J Mach Learn Res 2012; 13: 491–518.

80、Wang W and Zhou ZH. Crowdsourcing label quality: a theoretical analysis. Sci China Inform Sci 2015; 58: 1–12.

81、Dekel O and Shamir O. Good learners for evil teachers. In 26th International Conference on Machine Learning, Montreal, Canada, 2009; 233–40.

82、Urner R, Ben-David S and Shamir O. Learning from weak teachers. In 15th International Conference on Arti cial Intelligence and Statistics, La Palma, Canary Islands, 2012; 1252–60.

83、Wang L and Zhou ZH. Cost-saving effect of crowdsourcing learning. In 25th International Joint Conference on Arti cial Intelligence, New York, NY, 2016; 2111–7.

84、Karger DR, Sewoong O and Devavrat S. Iterative learning for reliable crowd- sourcing systems. In Advances in Neural Information Processing Systems 24, Cambridge, MA: MIT Press, 2011; 1953–61.

85、Tran-Thanh L, Venanzi M and Rogers A et al. Ef cient budget allocation with accuracy guarantees for crowdsourcing classi cation tasks. In 12th Interna- tional conference on Autonomous Agents and Multi-Agent Systems, Saint Paul, MN, 2013; 901–8.

86、Ho CJ, Jabbari S and Vaughan JW. Adaptive task assignment for crowd- sourced classi cation. In 30th International Conference on Machine Learning, Atlanta, GA, 2013; 534–42.

87、Chen X, Lin Q and Zhou D. Optimistic knowledge gradient policy for opti- mal budget allocation in crowdsourcing. In 30th International Conference on Machine Learning, Atlanta, GA, 2013; 64–72.

88、Dawid AP and Skene AM. Maximum likelihood estimation of observer error- rates using the EM algorithm. J Roy Stat Soc C Appl Stat 1979; 28: 20– 8

89、Zhong J, Tang K and Zhou Z-H. Active learning from crowds with unsure op- tion. In 24th International Joint Conference on Arti cial Intelligence, Buenos Aires, Argentina, 2015; 1061–7.

90、Ding YX and Zhou ZH. Crowdsourcing with unsure opinion. arXiv:1609.00292, 2016.

91、Shah NB and Zhou D. Double or nothing: multiplicative incentive mechanisms for crowdsourcing. In Advances in Neural Information Processing Systems 28, Cambridge, MA: MIT Press, 2015; 1–9.

92、Rahmani R and Goldman SA. MISSL: multiple-instance semi-supervised learn- ing. In 23rd International Conference on Machine Learning, Pittsburgh, PA, 2006; 705–12.

93、Yan Y, Rosales R and Fung G et al. Active learning from crowds. In 28th Inter- national Conference on Machine Learning, Bellevue, WA, 2011; 1161–8.

94、Sutton RS and Barto AG. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998.

95、Schwenker F and Trentin E. Partially supervised learning for pattern recognition. Pattern Recogn Lett 2014; 37: 1–3.

96、Garcia-Garcia D and Williamson RC. Degrees of supervision. In Advances in Neural Information Processing Systems 17, Cambridge, MA: MIT Press Work- shops, 2011.

97、Herna ́ ndez-Gonza ́ lez J, Inza I and Lozano JA. Weak supervision and other non-standard classification problems: a taxonomy. Pattern Recogn Lett 2016; 69: 49–55.

98、KunchevaLI,Rod ́ıguezJJandJacksonAS.Restrictedsetclassi cation:who is there? Pattern Recogn 2017; 63:158–70.

99、Zhang M-L and Zhou Z-H. A review on multi-label learning algorithms. IEEE Trans Knowl Data Eng 2014; 26: 1819–37.

100、Sun YY, Zhang Y and Zhou ZH. Multi-label learning with weak label. In 24th AAAI Conference on Arti cial Intelligence, Atlanta, GA, 2010; 593–8.

101、Li X and Guo Y. Active learning with multi-label SVM classi cation. In 23rd International Joint Conference on Arti cial Intelligence, Beijing, China, 2013; 1479–85.

102、Qi GJ, Hua XS and Rui Y et al. Two-dimensional active learning for image classi cation. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Anchorage, AK, 2008.

103、Huang SJ, Chen S and Zhou ZH. Multi-label active learning: query type matters. In 24th International Joint Conference on Arti cial Intelligence, Buenos Aires, Argentina, 2015; 946–52.

周志华：南京大学计算机软件新技术国家重点实验室（National Key Laboratory for Novel Software Technology）教授。NSR专题特邀编辑（Guest Editor of Special Topic of NSR）