基于采样策略的主动学习算法研究进展

计算机研究与发展　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　ＩＳＳＮ　１０００—１２３９／ＣＮ　１　１－１７７７门ｒＰ　４９（６）：１１６２－１１７３，２０１２　基于采样策略的主动学习算法研究进展　吴伟宁　刘　扬　郭茂祖　刘晓燕　（哈尔滨工业大学计算机科学与技术学院　哈尔滨　１５０００１）　（ｗｗｎ＠ｈｉｔ．ｅｄｕ．ｃｎ）　Ａｄｖａｎｃｅｓ　ｉｎ　Ａｃｔｉｖｅ　Ｌｅａｒｎｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　Ｂａｓｅｄ　ｏｎ　Ｓａｍｐｌｉｎｇ　Ｓｔｒａｔｅｇｙ　Ｗｕ　Ｗｅｉｎｉｎｇ，Ｌｉｕ　Ｙａｎｇ，　ＧＵＯ　Ｍａｏｚｕ，ａｎｄ　Ｌｉｕ　Ｘｉａｏｙａｎ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　［ｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　１５０００１）　Ａｂｓｔｒａｃｔ　Ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ　ｉｎ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｔｒａｉｎｅｄ　ｂｙ　ｃｈｏｏｓｉｎｇ　ｔｈｅ　ｍｏｓｔ　ｉｎｆｏｒｍａｔｉｖｅ　ｕｎｌａｂｅｌｅｄ　ｉｎｓｔａｎｃｅｓ　ｆｏｒ　ｈｕｍａｎ　ｅｘｐｅｒｔｓ　ｔｏ　ｌａｂｅ１．Ｉｎ　ｔｈｅ　ｃｙｃｌｉｎｇ　ｐｒｏｃｅｄｕｒｅ，ｔｈｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｃｃｕｒａｃｙ　ｏｆ　ｔｈｅ　ｍｏｄｅｌ　ｉｓ　ｉｍｐｒｏｖｅｄ，　ａｎｄ　ｔｈｅｎ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ　ｗｉｔｈ　ｈｉｇｈ　ｇｅｎｅｒａｌｉｚａｔｉｏｎ　ｃａｐａｂｉｌｉｔｙ　ｉｓ　ｏｂｔａｉｎｅｄ　ｂｙ　ｍｉ‘ｎｉ。ｍｉ’ｚｉ‘ｎｇ　ｔｈｅ　ｔｏｔａｌｌｙ　ｌａｂｅｌｉｎｇ　ｃｏｓｔ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｈａｓ　ａｔｔｒａｃｔｅｄ　ａｔｔｅｎｔｉｏｎｓ　ｏｆ　ｒｅｓｅａｒｃｈｅｒｓ　ｂｏｔｈ　ａｔ　ｈｏｍｅ　ａｎｄ　ａｂｒｏａｄ　ｗｉｄｅｌｙ．Ｉｔ　ｉｓ　ｐｏｉｎｔｅｄ　ｏｕｔ　ｔｈａｔ　ｔｈｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｔｅｃｈｎｉｑｕｅ　ｉｓ　ａ　ｖｅｒｙ　ｉｍｐｏｒｔａｎｔ　ｒｅｓｅａｒｃｈ　ａｔ　ｐｒｅｓｅｎｔ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｉｎｔｒｏｄｕｃｅｄ　ｂｙ　ｐｕｔｔｉｎｇ　ａ　ｐａｒｔｉｃｕｌａｒ　ｅｍｐｈａｓｉｓ　ｏｎ　ｔｈｅ　ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ．Ｔｈｅ　ｉｔｅｒａｔｉｖｅ　ｐｒｏｃｅｓｓｅｓ　ｏｆ　ｔｈｅ　ｌｅａｒｎｉｎｇ　ｅｎｇｉｎｅ　ａｎｄ　ｔｈｅ　ｓａｍｐｌｉｎｇ　ｅｎｇｉｎｅ　ａｒｅ　ｄｅｓｃｒｉｂｅｄ　ｉｎ　ｄｅｔａｉｌ．Ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｔｈｅｏｒｉｅｓ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｒｅ　ｓｕｍｍａｒｉｚｅｄ．Ｔｈｅ　ｒｅｃｅｎｔ　ｗｏｒｋ　ａｎｄ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｒｅ　ｄｉｓｃｕｓｓｅｄ，ｉｎｃｌｕｄｉｎｇ　ｔｈｅｉｒ　ａｐｐｒｏａｃｈｅｓ　ａｎｄ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ．　Ｆｉｒｓｔｌｙ，ｔｈｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｃａｔｅｇｏｒｉｚｅｄ　ｉｎｔｏ　ｔｈｒｅｅ　ｍａｉｎ　ｃｌａｓｓｅｓ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｄｉｆｆｅｒｅｎｔ　ｗａｙｓ　ｏｆ　ｓｅｌｅｃｔｉｎｇ　ｔｈｅ　ｅｘａｍｐｌｅｓ．Ａｎｄ　ｔｈｅｎ，ｔｈｅ　ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ　ａｒｅ　ｓｕｍｍａｒｉｚｅｄ　ｂｙ　ａｎａｌｙｚｉｎｇ　ｔｈｅｉｒ　ｃｏｒｒｅｌａｔｉｏｎｓ．Ｔｈｅ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｔｈｅ　ｓｈｏｒｔｃｏｍｉｎｇｓ　ｏｆ　ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ　ａｒｅ　ｄｉｓｃｕｓｓｅｄ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｄｅｅｐｌｙ　ｗｉｔｈｉｎ　ｒｅａｌ　ａｐｐｌｉｃａｔｉｏｎｓ．Ｆｉｎａｌｌｙ　ｔｈｅ　ｏｐｅｎ　ｐｒｏｂｌｅｍｓ　ｗｈｉｃｈ　ａｒｅ　ｓｔｉｌ１　ｒｅｍａｉｎｅｄ。ａｎｄ　ｔｈｅ　ｉｎｔｅｒｅｓｔｓ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　ｆｕｔｕｒｅ　ｒｅｓｅａｒｃｈ　ａｒｅ　ｆｏｒｅｃａｓｔｅｄ．　Ｋｅｙ　ｗｏｒｄｓ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ；ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ；ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｙ；ｌａｂｅｌｉｎｇ　ｃｏｓｔ；ｉｎｓｔａｎｃｅｓ　ｓｅｌｅｃｔｉｏｎ　摘要主动学习算法通过选择信息含量大的未标记样例交由专家进行标记，多次循环使分类器的正确　率逐步提高，进而在标记总代价最小的情况下获得分类器的强泛化能力，这一技术引起了国内外研究人　员的关注．侧重从采样策略的角度，详细介绍了主动学习中学习引擎和采样引擎的工作过程，总结了主　动学习算法的理论研究成果，详细评述了主动学习的研究现状和发展动态．首先，针对采样策略选择样　例的不同方式将主动学习算法划分为不同类型，进而，对基于不同采样策略的主动学习算法进行了深入　地分析和比较，讨论了各种算法适用的应用领域及其优缺点．最后指出了存在的开放性问题和进一步的　研究方向．　关键词机器学习；主动学习；采样策略；标记代价；样例选择　中图法分类号ＴＰ１８１　收稿日期：２０１０—０７　２９；修回日期：２０１１—１１一Ｏ８　基金项目：国家自然科学基金项目（６１１７１１８５，６０９３２００８，６０８３２０１０）；中国博士后科学基金特别资助项目（２０１００３４４６）　吴伟宁等：基于采样策略的主动学习算法研究进展　机器学习作为人工智能一个重要研究方向一直　循环训练的方法使分类器获得了更强的泛化能力．　受到计算机科学家的关注．当前，机器学习面临的现　实情况是：未标记样例数目众多，易于获得；标记样　例数量稀少，难于获得．研究表明，对于训练样例的　由于适用性广泛和高效利用人类专家的特点，主动　学习受到广泛关注并迅速发展，成为机器学习领域　的最重要方向之一．例如卡内基一梅隆大学、斯坦福　大学的机器学习实验室都将主动学习的算法理论以　精确标记不但需要该领域中大量的专家参与，并且　标记样例花费的时间是其获取时间的１Ｏ倍以上［１］，　与之形成对比的是，未标记样例却简单易得．这种现　实使传统的机器学习算法无法得以有效应用，原因在　于监督学习需要大量标记样例对分类器进行迭代训　练，否则根据ＰＡＣ学习理论，算法的泛化性能无法有　及实际应用，特别是对无标记样例的选择，即采样策　略的设计列为研究重点；机器学习、数据挖掘的重要　学术会议也收录主动学习技术的文章并将其列为重　要专题进行讨论　］．尽管主动学习领域涌现出大量　的研究工作，但是对于其算法的核心，即主动学习算　法的采样策略，尚缺乏全面的总结，分析和比较，进　效提高．无监督学习虽然直接利用未标记样例，但是　算法的精度不能使人满意．在这种情况下，半监督学　习（ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ）和主动学习（ａｃｔｉｖｅ　而限制了相应研究工作的进行．因此，本文从采样策　略的角度出发，对主动学习算法进行了归类比较，并　从该角度对主动学习算法进行了深入的分析和讨论．　ｌｅａｒｎｉｎｇ）算法就应运而生并迅速发展，成为解决上　述问题的重要技术．虽然两者都利用未标记样例和　已标记样例共同构建高精确度的分类器，降低人类　专家的工作量．但不同的是，主动学习算法模拟了人　的学习过程，选择标记部分样例加入训练集，迭代提　高分类器的泛化性能，因此近年来被大量地应用于　信息检索、图像和语音识别、文本分类和自然语言处　１主动学习算法简介　相对于传统监督学习，也称为被动学习，主动学　习是一种较新的机器学习算法．为了直观地展示主　理等领域．２Ｏ０９年，Ｔｏｍａｎｅｋ和０ｌｓｓｏｎ￣　］的一项调　动学习算法的有效性及其对分类器训练精度的提高　程度，本文首先以一个二维空间中的二分类问题ｌ＿３］　为例加以说明．从图１【３　可以看出，位于正确分类界　面ｚ一０附近的样本点最有助于分类器训练过程．　查显示，９ｏ．７　的研究者认为主动学习算法在他们　的项目应用中是有效的．而另一份调查证明　Ｇｏｏｇｌｅ，ＣｉｔｅＳｅｅｒ，ＩＢＭ，Ｍｉｃｒｏｓｏｆｔ和Ｓｉｅｍｅｎｓ等大　型公司也都在项目中使用主动学习算法提高性　能　ｊ．２０１０年，ＰＡＳＣＡＬ举办主动学习算法竞赛，竞　赛包含６个不同应用领域，目的是鼓励参赛者开发　优秀的主动学习算法＿４］．　主动学习最初由耶鲁大学的Ａｎｇｌｕｉｎ教授在　“Ｑｕｅｒｉｅｓ　ａｎｄ　ｃｏｎｃｅｐｔ　ｌｅａｒｎｉｎｇ”一文中提出Ｌ５　．与以　在有限的标记代价下（选择并标记样例的数目为　３０），标记这部分样本点最有利于找到正确的分类界　面．被动学习随机选择并标记的样本点大多数与　ｚ一０相距较远，很难找到正确的分类界面，因此，分　类精度较低（正确率仅有７Ｏ　）．主动学习选择并标　记的样本点大部分位于ｚ一０附近，积极推动分类　模型的训练过程，分类精度较高（正确率达到９Ｏ　）．　这个例子充分说明，与被动学习相比，主动学习选择　的样本点更有利于分类器训练过程，在相同的标记　代价下提高了分类模型的精确度．　往算法的不同点是使用未标记样例辅助分类器的训　练过程，方法是选择并标记部分未标记样例，然后放　入标记样例集合训练分类器，使用分类器再次选择　未标记样例．这种有选择地扩大有标记样例集合和　（ａ）Ａｔｏｙ　ｄａｔａｓｅｔ　ｃｏｎｓｉｓｔｓｏｆ４００　ｐｏｉｎｔｓ　ｅｖｅｎｌｙ　ｓａｍｐｌｅｄ　ｆｒｏｍ　ｔｗｏ　ｃｌａｓｓ　Ｇａｕｓｓｉａｎｓ　（ｂ）Ａ　ｃｌａｓｓｉｆｉｅｒ　ｉｓ　ｔａｉｒｎｅｄ　ｗｉｔｈ　３０　ｌａｂｅｌｅｄ　ｐｏｉｎｔｓｂｙ　ｒａｎｄｏｍｌｙ　ｓａｍｐｌｉｎｇｂｙ　（ｃ）Ａ　ｃｌａｓｓｉｆｉｅｒ　ｉｓ　ｔｒａｉｎｅｄ　ｗｉｔｈ　３０　ｐｏｉｎｔｓ　ｑｕｅｒｉｅｄ　ａｎｄ　ｌａｂｅｌｅｄ　ｂｙ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｐａｓｓｉｖｅ　ｌｅａｒｎｉｎｇ（７ｏ９６　ａｃｃｕｒａｃｙ）　ｆ９ｏ９６　ａｃｃｕｒａｃｙ）　Ｆｉｇ．１　Ａｎ　ｅｘａｍｐｌｅ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　２Ｄ　ｓｐａｃｅ（Ｔｈｅ　ｓｏｌｉｄ　ｌｉｎｅ　ｒｅｐｒｅｓｅｎｔｓ　ｔｈｅ　ｄｅｃｉｓｉｏｎ　ｂｏｕｎｄａｒｙ　ｏｆ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ）　图１一个二维空间中主动学习的例子（图中实线表示分类界面）　１．１　主动学习算法工作流程　主动学习算法的工作过程是一个迭代训练分类　器的过程，该过程由以下两个部分组成　］．　学习引擎（１ｅａｒｎｉｎｇ　ｅｎｇｉｎｅ，ＬＥ）：学习引擎的　工作过程是在标记样例集合上进行循环训练，当达　到一定精度后输出．该过程类似于传统监督学习中　的分类器训练过程，因此也被称为分类器．　采样引擎（ｓａｍｐｌｉｎｇ　ｅｎｇｉｎｅ，ＳＥ）：采样引擎是　主动学习算法不同于其他学习算法的部分．其任务　是在未标记样例集合上使用不同的采样算法选择样　例，将其交由人类专家进行标记，并将标记后的样例　加入已标记样例集，以供分类器进行循环训练．采样　引擎的目的是在最少标记代价下获得能最大程度提　高分类器的泛化性能的标记样例集．　主动学习算法的迭代过程是：在标记样例集上　训练分类器；使用分类器对无标记样例进行分类判　断；根据分类结果，使用采样引擎选择部分无标记样　例交由专家进行标记；将标记后的样例加入标记样　例集用于分类器的下一次训练．算法的终止条件是　标记代价或者分类器的泛化精度达到一定标准为　止．为了说明这一过程，本文给出算法的伪码描述，　如图２所示：　Ｆｉｇ．２　Ｐｓｅｕｄｏ—ｃｏｄｅ　ｏｆ　ｔｈｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ．　图２主动学习算法伪码描述　由于采样策略是采样引擎的核心，也是区分不　同主动学习算法的关键，因此本文的重点是采样引　擎中的采样策略研究．其中，采样策略选择样例的标　准也称为信息含量，即未标记样例对分类器泛化能　力的影响程度．信息含量可以是一个设定好的函数，　也可以是一个固定阈值．本文的第２节将对其进行　详细分析和讨论．　计算机研究与发展２０１２，４９（６）　１．２主动学习算法分类　根据采样策略选择未标记样例的方式不同，可　以将主动学习算法分为以下几种：成员查询综合　（ｍｅｍｂｅｒｓｈｉｐ　ｑｕｅｒｙ　ｓｙｎｔｈｅｓｉｓ）、基于流（ｓｔｒｅａｍ—　ｂａｓｅｄ）的主动学习和基于池（ｐｏｏｌ—ｂａｓｅｄ）的主动学　习＿３Ｊ．为了便于叙述，下面使用（ｚ，．ｙ）表示已标记样　例及其对应标记，使用　表示未标记样例．　成员查询综合是最早提出的使用查询进行学习　的思想ｌ＿５］，即假定学习系统对周围环境具有一定控　制能力，可以向人类专家提问．算法通过提问的方式　确定某些样例的标记和学习未知概念．该方法的缺　点是将所有未标记样例都交给人类专家进行标记，　而不考虑样例的实际分布情况［８］．　针对这一缺陷，研究人员提出了一系列样例选　择算法对该方法进行改进．当　大量易得时，Ｃｏｈｎ　等人提出标记Ｐ（　，　）超过某一阈值的样例Ｌ９　．　Ｓｅｕｎｇ等人提出在（ｚ，　）上分别训练参数为０　和０　的两个模型，选择这两个模型预测不一致的　进行　标记＿１　．这类做法也被称为基于流的采样策略，其　采样过程是将落在版本空间（ｖｅｒｓｉｏｎ　ｓｐａｃｅ）中的所　有ｘ按照顺序逐个依次进行标记ｎ　，并广泛应用于　词类标注　、信息检索口。　等实际问题．　虽然基于流的采样策略在一定程度上解决了直　接查询方法的问题，但是这种采样策略往往需要设　定一个固定阈值来衡量样例的信息含量，因此缺乏　对不同学习问题的普适性．具体应用问题不同，设定　的阈值也不同；更重要的是，算法是逐个将　的信　息含量与标准阈值进行比较，故无法掌握　的实际　分布，也无法得知　之间的差异．　为了解决上述问题，Ｌｅｗｉｓ等人提出将　组成　一个无标记样例“池”，采样策略从这个集合中选择　样例，即基于池的采样策略＿１　．与基于流的采样策　略相比，算法维护一个固定分布的由大量　组成的　“样例池”．采样策略计算　的信息含量并比较，选　择信息含量高的　进行标记．由于基于池的采样策　略继承了前面两种方法的优点，克服它们的不足，因　而成为当前研究最充分、应用最广泛的采样策略，在　文本分类　、信息提取Ｌ１。　、图像检索［２　］、视频　检索［２２－２３　和癌症检测　等领域都有具体的应用．　１．３主动学习算法的理论分析　主动学习算法的目的是减少训练所需的标记代　价，因此，在主动学习理论研究中，备受关注的是算　法对样本复杂度（ｓａｍｐｌｅ　ｃｏｍｐｌｅｘｉｔｙ）的降低程度．　相对于主动学习的大量应用研究工作而言，这方面　吴伟宁等：基于采样策略的主动学习算法研究进展　的理论研究依然有很多开放性问题．特别是目前　主动学习已有研究成果大多针对特定条件或模　针对不同的样例分布和模型类别，算法更精确地对　当前假设进行限制，达到了更少的标记代价．这些主　动学习算法类似于精确枚举空间中的所有假设，计　型，尚缺乏一般性结论．本文根据主动学习算法理　论研究针对的不同问题，将该方向成果划分为“可　达”（ｒｅａｌｉｚａｂｌｅ）和“不可达”（ｎｏｎ—ｒｅａｌｉｚａｂｌｅ）两种情　形，并分别加以阐述．　算复杂度高，所以很难直接应用于实际．而且，算法　的理论分析结论往往建立在样例均匀分布或近似均　匀分布的条件下，或者对假设空间有严格要求．在算　法具体实现中，这些方法局限于优化简单的０－１损　失函数，很难扩展到复杂监督模型或其他对象函　数口　．值得注意的是，Ｗａｎｇ和Ｚｈｏｕ使用全类扩张　可达类主动学习是指假设类（ｈｙｐｏｔｈｅｓｉｓ　ｃｌａｓｓ）　中存在可以完美划分数据的假设．对于可达情形，其　理论研究是主动学习理论研究中被关注时间较早，　相对较为充分的一种类型．大多数该方面的理论工　作证明：相对于监督学习而言，主动学习可以有效降　低样本复杂度．与监督学习相比，主动学习可以产生　“指数级”的样本复杂度改善　］．例如，Ｃｏｈｎ等人ｌ＿９］　证明在标准ＰＡＣ模型下，均匀分布的样例空间中，获　得一个最大错误率为ｅ的分类假设．监督学习需要　的样本复杂度是Ｏ（１／￡），而主动学习使用二分搜索　获得该分类假设所需要的样本复杂度为０（１ｏｇ　ｌｌｓ）．　Ｆｒｅｕｎｄ等人＿３　进一步提出，在贝叶斯条件下，获得　一个泛化误差小于ｅ的分类假设，基于版本空间缩　减的主动学习算法的样本复杂度为ｏ（　ｌｏｇ（１／ｅ））　（　表示当前空间中ＶＣ维的维度）．而相同条件下，　监督学习算法的样本复杂度为０（　／￡）．针对该结　论，Ｇｉｌａｄ—Ｂａｃｈｒａｃｈ等人使用核方法进一步限制版　本空间的大小，获得了更高的性能『３　．Ｂａｌｃａｎ等　人Ｌ２　５］证明样例均匀分布时，可达类主动学习的样本　复杂度是Ｏ（ｅ　『（Ｈ　），其中　表示噪声参数．　但是，由于存在噪声数据或者假设类学习能力　有限等因素，实际应用中的大多数问题属于“不可　达”情形，即假设类中不存在对数据进行完美划分的　假设．针对不可达情形，主动学习同样涌现出大量研　究工作，获得了丰富的研究成果．这部分研究成果可　以根据是否假定噪声模型划分为以下两种．　在不假定噪声模型的条件下，一些研究成　果［３。　］表明，主动学习算法的样本复杂度下界与被　动监督学习的样本复杂度上界相当，这意味着，主动　学习并不能起到实质性的改善作用．因此，基于　ＰＡＣ框架的不可达主动学习算法的特点是严格地　限制采样次数，从而达到减低样本复杂度的目的．例　如，Ｂａｌｃａｎ等人［３　提出基于ＰＡＣ框架的不可达主　动学习（ａｇｎｏｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ，Ａ　）算法证明样本　复杂度边界是０（１ｎ　ｌ／ｅ）．该结果表明只要样例是从　一个固定分布中选择的，主动学习就比监督学习算　法具有更大的优势．Ｈａｎｎｅｋｅ［　通过定义不一致系　数，进一步限制样本复杂度的上界．在此基础上，　Ｄａｓｇｕｐｔａ等人＿３　提出一种更有效的样例选择算法，　的ａ—ｅｘｐａｎｓｉｏｎ定义，显示出主动学习算法在数据存　在多视图时降低样本复杂度的有效性＿３　，同时，　Ｗａｎｇ和Ｚｈｏｕ也将半监督技术与多视图主动学习　相结合，并获得算法性能的进一步提高．　在假定噪声模型的条件下，现在一般考虑　Ｔｓｙｂａｋｏｖ噪声模型，又可以分为有界（ｂｏｕｎｄｅｄ）和　无界（ｕｎｂｏｕｎｄｅｄ）两种情形．有界情形相对简单，一　些研究表明［２　。　。　，主动学习可以产生指数级的样　本复杂度改善．例如，Ｋａａｒｉａｉｎｅｎ＿３　证明噪声率为　时主动学习算法的样本复杂度为０（　／ｅ　）．无界情　形则相对复杂，也更接近于大多数真实问题，一些　研究工作　。　“　表明主动学习仅能获得多项式　级的样本复杂度改善，并不能起到实质性提高．例　如，Ｃａｖａｌｌａｎｔｉ等人ｌ４ｏ］进一步提出，当标记噪声满　足线性条件时，主动学习算法的样本复杂度是　０（￡　。　ｎ¨　抖　）．Ｃａｓｔｒｏ和Ｎｏｗａｋ［４１］提出单视　图主动学习算法的样本复杂度的一般形式，即获得　一个分类错误率小于￡的分类假设，样本复杂度至　少为Ｄ（ｅ　），ｐ∈（０，２）．在分类边界和分布高阶平　滑至无限平滑的假设条件下，Ｗａｎｇ［４　基于放松的　Ｔｓｙｂａｋｏｖ噪声模型（ａｐｐｒｏｘｉｍａｔｅｌｙ　Ｔｓｙｂａｋｏｖ　ｍｏｄｅ１）获得了指数级改善．Ｗａｎｇ和Ｚｈｏｕ　。　的工作　首次发现，在数据存在多视图时，在无界Ｔｓｙｂａｋｏｖ　噪声模型条件下，主动学习可以达到指数级提升．该　工作具有很大的启发意义，说明主动学习算法的进　一步理论研究和算法设计都必须考虑一些具体的数　据条件，否则，一般通用角度无法获得样本复杂度的　指数级提升，即不能获得实质性改善．　２主动学习的采样策略　由于基于池的采样策略应用最广，且当样例池　中仅有一个未标记样例时，等同于基于流的采样策　略，因此，本文详细介绍这类采样策略．按照选择　的标准不同，分为以下３种：基于不确定性的采样策　略、基于版本空间缩减的采样策略以及基于误差缩　减的采样策略ｌ＿４　．　２．１基于不确定性的采样策略　基于不确定性的采样策略是适用性最广的一类　采样策略．这种采样策略选择分类器对Ｐ（　ｌ　ｘ）的　预测值最接近０．５的样例进行标记，其中歹是　的　预测标记．事实证明，这种采样策略不但适用于绝大　多数分类器，有效减少人类专家的工作量，而且极大　地提高分类器的分类精确度和泛化能力＿４　，是目前　研究最为充分的采样策略．根据选用的分类模型不　同，衡量样例不确定性的函数ｆ（ｘ，　）演化出很多　形式，下面进行详细说明．　最基本的做法是使用分类器直接估计Ｐ（　Ｉ　）　的值（ｕｎｃｅｒｔａｉｎ—ｂａｓｅｄ　ｓａｍｐｌｉｎｇ），算法选择样例的　标准是Ｐ（　ｌ　）的值最接近于０．５的样例．例如：　Ｌｅｗｉｓ和Ｃａｔｌｅｔｔ『】　将其应用于决策树模型，算法中　厂（　，　）的形式如下：　组　（ａ＋６　ｄ－。ｇ　Ｐ（ｃ　ｌ　）一　＋　户（口＋６　ｄ・。ｇ　其中ｃ，　分别表示样例所属正、负类别，Ｗ　表示样　例特征．继而，Ｓｃｈｅｆｆｅｒ等人＿４。　在隐Ｍａｒｋｏｖ模型　（ｈｉｄｄｅｎ　Ｍａｒｋｏｖ　ｍｏｄｅｌｓ，ＨＭＭ）中使用这种思想，　并将这一做法扩展到多类别问题中．当前，Ｃｕｌｏｔｔａ　和ＭｃＣａｌｌｕｍ＿４　把这种做法推广到结构化分类模型　中，使用结构化数据对应标记序列的后验概率作为　ｆ（ｘ，ｙ），也收到了很好的效果．　由于直接估计Ｐ（ｙ　Ｉ　）的做法很难应用于复杂　的概率模型，信息熵作为一种ｆ（ｘ，　）的形式得以　引入（ｅｎｔｒｏｐｙ－ｂａｓｅｄ　ｓａｍｐｌｉｎｇ）．信息熵的特点是易　于计算，并且能很方便地扩展到复杂的概率图模型　当中，例如条件随机场模型，判别随机场模型．近年　来，信息熵演化出适用于各种结构化数据的变体，例　如短数据序列熵、长数据序列熵、序列总熵等等　．　同时，为了解决标记序列随着样例序列自身长度增　加而指数化增长带来的计算量过大的问题，Ｋｉｍ等　人　将标记序列进行排序，选择其中后验概率最大　的Ｎ个标记序列计算样例的熵值．　由于支持向量机（ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅ，ＳＶＭ）　在小样本分类中的突出表现，采用ＳＶＭ作为基准　分类器的主动学习算法逐渐增加＿４　．ＳＶＭ分类是　在样例空间中找到一个能最大化分隔样例空间的超　平面．因此当分类器是ＳＶＭ模型时，采样策略使用　计算机研究与发展２０１２，４９（６）　样例与分类边界之间的距离作为ｆ（ｘ，　）的计算形　式．算法的具体学习步骤是：首先使用标记样例训练　ＳＶＭ模型，并使用该模型对　进行预测，获得样例　的类别标记和样例与超平面的距离．然后，根据样　例与超平面距离对　进行排序，选择与超平面距　离最小的　作为最不确定的样例　１６，２０１，并提交专　家进行标记．这也被称为最近边界策略（ｃｌｏｓｅｓｔ—ｔｏ—　ｂｏｕｎｄａｒｙ），并广泛应用于文本分类与检索，图像检　索等任务当中，收到良好效果．　上述两种基于不确定性的采样策略面临的重要　问题是避免选择野点．由于其无法代表一类样例的　特殊性，将其进行标记不能提高学习器的泛化能力．　而另外一个问题是当分类器为ＳＶＭ模型时，而　ＳＶＭ分界面刚好通过一个无标记样例密集区域，那　么位于该区域内的大部分样本一定是距离分类边界　最近的．但是同一个聚类的样例通常具有相同的标　记，将这种未标记样例交由人类专家进行标记会浪　费大量的时间．为了解决这个问题，在ＳＶＭ模型条　件下，研究人员将聚类算法与采样策略进行结合，即　根据样例间隔进行采样的同时考虑样例的实际分　布，选择标记具有代表性的样例．例如，Ｘｕ等人＿４　使用了Ｋ－Ｍｅａｎｓ算法，选择那些靠近分类边界的聚　类中心进行标记（ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｓａｍｐｌｉｎｇ），如图３　所示＿４　．Ｎｇｕｙｅｎ和Ｓｍｅｕｌｄｅｒｓ＿５。。使用了半监督学　习中的聚类思想，先对样例进行聚类，将相同聚类中　的样例标记进行传递，选择靠近边界的聚类中心进　行标记（ｐｒｏ－ｃｌｕｓｔｅｒ　ｓａｍｐｌｉｎｇ）．Ｓａｎｊｏｙ等人［５　使用　分层采样的方法（ｈｉｅｒａｒｃｈｉｃａｌ　ｓａｍｐｌｉｎｇ），根据样例　密度的高低进行采样，优点是当未标记样例分布不　均衡时，采样算法依然可以选择到最具有代表性的　未标记样例．虽然这些做法一定程度上解决了上述　问题，但是由于聚类算法本身的一些缺点，对这两个　问题的研究依然备受关注．Ｄｏｎｍｅｚ等人＿５　提出将　Ｒｅｐｒｅｓｅｎｔａｔｉｖｅｓ　Ｆｉｇ．３　Ｔｈｅ　ｃｅｎｔｅｒｓ　ｉｎ　ｃｌｕｓｔｅｒｓ　ｃｌｏｓｅｄ　ｔＯ　ｔｈｅ　ｃｌａｓｓｉｆｉｅｒ　ｂｏｕｎｄａｒｙ　ａｒｅ　ｓｅｌｅｃｔｅｄ．　图３选择靠近分类界面的聚类中心　吴伟宁等：基于采样策略的主动学习算法研究进展　样例密度与最近边界准则相结合的方法（ＤＵＡＬ），　在样例选择过程中，算法判断当前样例的密度信息，　选择代表性和不确定性的样例，算法优点是：即使在　噪声数据存在的条件下，算法保持较高的样例选择　的准确度．实验证明，该算法是目前基于不确定度的　采样策略中性能最好的样例选择算法ｌ｜５　．　当样例密集时，根据密度信息进行采样；当样例稀疏　时，选取距离分类边界最近的样例．Ｈｕａｎｇ等人　３＿　使用最小一最大视图方法（ＱＵＩＲＥ），在样例选择步　在表１中给出上述各种样例选择算法的应用领　骤中，算法同时考虑密度和边界分布的信息，目的是　域和优缺点比较：　Ｔａｂｌｅ　１　Ｔｈｅ　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　Ｕｎｃｅｒｔａｉｎ－Ｂａｓｅｄ　Ｓａｍｐｌｉｎｇ　Ｓｔｒａｔｅｇｉｅｓ　表１　基于不确定性的采样策略算法比较　Ｍｅｔｈｏｄｓ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｃｏｍｐａｒｉｓｏｎ　ｎ　ｃａ忙　。一　“Ｕｎｄｅｒｓｔｏｏｄ　ａｎｄｉｍ。Ｕｎｃｅｒｔａｉｎ－　ｅ　—ｅｘｔｒａｃｔＩＯｎ　…ａ　ｉｓｃｒｌｍｌｎａｔ１ｖｅ　ｍｏｃｌｅｌ；；＾ＩＩ　ｃｃ　【ｅⅡ　ｅａｓ　ｎ　Ｙ　Ｄ　Ｄｅ　０Ｕ　Ｉｉｅｒ　｜ｎｔ唧ｋ　ｙ【　Ｌ　ｓＵｓｅｄ　ｉｎ　ｏｐｔｉｍｉｚｉｎｇ　ｔｈｅ　ｃｏｎｔｉｎｕｏｕｓ　ｌｏｓｓ　ｆｕｎｃｔｉｏｎｓ；　Ｅｘｔｅｎｄｅｄ　ｔｏ　ｃｏｍｐｌｅｘ　ｍｏｄｅｌｓ　ａｎｄ　ｍｕｌｔｉ—ｃｌａｓｓ　ｅａｓｉｌｙ；　Ａｆｆｅｃｔｅｄ　ｅａｓｉｌｙ　ｂｙ　ｔｈｅ　ｏｕｔｌｉｅｒｓ　Ｃｌｏｓｅｄ－ｔｏ－Ｂｏｕｎｄａｒｙ　ｓｖ　Ｍ［１６　ｌ２０＿　ｒｒｅｘｔ　ｃａｔｅｇ　０ｒｉｚａｔｉ０ｎＩｍａｇｅｒｅ　ｅｖａｌ　ＯＵｔ１１ｅｒｓ　ｅｄ　ｉｎ幽ｅｓｖＭ　ｃｏｍｍｏｎ　ｙ’Ａｆｆｅｃ托ｄｅａｓ订ｙ　ｂｙ　Ｍａｋｅ　ｆｕｌｌ　ｕｓｅ　ｏｆ　ｔｈｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｔｈｅ　ｅｘａｍｐｌｅｓ　ｂｙ　ｔｈｅ　Ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　Ｔａｋｅ　ａｄｖａｎｔａｇｅ　ｏｆ　ｔｈｅ　ｐｒｉｏｒ　ｋｎｏｗｌｅｄｇｅ　ｏｆ　ｔｈｅ　ｕｎｌａｂｅｌｅｄ　Ｆａｃｅ　ｒｅｃｏｇｎｉｔｉｏｎ　ＯＣＲ　ｄｉｇｉｔ　ｉｍａｇｅ　ｄａｔａ　ｂｙ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ；Ａｖｏｉｄ　ｔｏ　ｌａｂｅｌｉｎｇ　ｔｈｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｅｘａｍｐｌｅｓ　ｒｅｐｅａｔｅｄｌｙ　Ｈｉｅｒａｒｅｎｉｃａｌ　Ｓａｍ　－ｉｎｓ　ｓ　０ｃＲ　ｉ　ｉ　。。　。ｉ　ｉ。　ｉ。“Ｔ。　Ｍ　ｈｅ　ｈｉｅｒａｒｃｈｉｃａｌ　ｓ　ｔ　ｒ　ｕｃ　ｔｕｒｅ　ｆｒｏｍ　ｔｈｅｄａｔａｉ　ｎｃｌｕｉ“　．　Ａ，．ｃａｔｅｇｏｒｌｚａｔｌｏｎ　ｎｏ１ｓｅ　；；Ａ　ｐｐｌｌｅｃｌ．，．，　ｔｏ　ＳａｍＰ　１ｌ　ｎ譬　Ｉ　ｔｏｍ　ｔｎｅ　ｕｎＩ）ａ　ａｎｃｅａ　。ｌ　ｎ　ａｔａ　ＤＵＡＬ［５２］　Ｄａｔａ　ｍｉｎｉｎｇ　Ｓｅｌｅｃｔ　ｔｈｅ　ｅｘａｍｐｌｅｓ　ｄｙｎａｍｉｃａｌｌｙ　ｂｙ　ｃｏｎｓｉｄｅｒｉｎｇ　ｔｈｅｉｒ　ｄｅｎｓｉｔｙ　ｉｎｆｏｒｍａｔｉｏｎ　Ａｖｏｉｄ　ｔｈｅ　ｅｆｆｅｃｔ　ｆｒｏｍ　ｔｈｅ　ｂｉａｓ　ａｎｄ　ｔｈｅ　ｎｏｉｓｅ；Ｓｅｌｅｃｔ　ｔｈｅ　Ｄａｔａ　ｍｉｎｉｎｇ　ｕｎｃｅｒｔａｉｎ　ｅｘａｍｐｌｅｓ　ｐｒｅｃｉｓｅｌｙ　２．２基于版本空间缩减的采样策略　点进行介绍．　基于版本空间缩减采样策略的主导思想是选择　第１个研究重点是如何有效地建立一个委员　能最大程度缩减版本空间的　进行标记．委员会投　会．委员会构建的一种策略是将委员会建立看作多　票选择算法（ｑｕｅｒｙ—ｂｙ－ｃｏｍｍｉｔｔｅｅ，ＱＢＣ）Ｅ１０３是这类　分类器集成问题，故很多原有的分类器集成的策略　采样策略中应用最广泛、最著名的算法．该算法具体　都被用于解决这一问题．例如：Ａｂｅ和Ｍａｍｉｔｓｕｋａ　步骤是：从当前版本空间中选择参数不同的一组假　在１９９８年提出了Ｂｏｏｓｔｉｎｇ—ＱＢＣ和Ｂａｇｇｉｎｇ—ＱＢＣ　设构成一个“委员会”；使用委员会中各个假设对无　的委员会建立策略［５　．这两种委员会的建立策略分　标记样例进行分类判别；选择标记版本空间中各个　别采用了两种著名的集成学习方法去建立委员会：　假设分类结果不一致程度最大的　．换言之，这种采　Ｆｒｅｕｎｄ等人ｌ＿５　于１９９７年提出的ｂｏｏｓｔｉｎｇ方法和　样策略是通过构造多个分类器模型来预测样例标　Ｂｒｅｉｍａｎ＿５　］于１９９６年提出的ｂａｇｇｉｎｇ方法，这两种　记，进而选择各模型都不确定的样例进行标记，其本　做法的共同特点是：使用了重采样技术训练并获得　质与基于不确定性采样策略类似．自从Ｓｅｕｎｇ等　多个候选假设；从未标记集中随机选择部分　对当　人＿１　构建第１个由两个随机假设模型组成的委员　前候选假设加以区分；选择在各个假设之间，不确　会后，ＱＢＣ算法在各种分类模型的实际应用中收到　定度最大的样例进行查询，进而达到缩减版本空　较好的效果．例如：朴素贝叶斯模型［１　、隐Ｍａｒｋｏｖ　间的目的．而不同的是，Ｂａｇｇｉｎｇ－ＱＢＣ目的是减少　模型＿１　等．这种采样策略的目的是建立一个具有较　假设偏置的影响，过程相对简单：算法过程是从样　强泛化能力和高效的委员会，下面对算法的研究重　例分布中进行多次独立同分布采样；使用所选样　计算机研究与发展２０１２，４９（６）　例训练候选假设；最终的输出假设是所有候选假　设的平均值．Ｂｏｏｓｔｉｎｇ—ＱＢＣ算法目的是增强弱分类　假设的性能，过程相对复杂：使用ＡｄａＢｏｏｓｔ算法对　采样过程进行加权并训练候选假设，在二分类问题　中，选择能够最小化两类权重差值的样例作为查询　样例．　另一个研究重点是如何衡量成员模型对样例的　分歧程度．Ｄａｇａｎ和ＥｎｇｅｌｓｏｎＥ　提出选举熵这一标　准（ＱＢＣ—ＶＥ），其计算公式如下：　Ⅷｃ　一　ｏｇ　，　广，将原有熵的形式进行了改进，使之能够衡量委员　会中各个假设对样例分歧的程度．ＭｃＣａｌｌｕｍ等　人［１　则提出将样例的分布密度与ＱＢＣ相结合　（ＥＭ—ＱＢＣ），引入信息论中的ＫＬ距离（Ｋｕｌｌｂａｃｋ—　Ｌｅｉｂｌｅｒ　ｄｉｖｅｒｇｅｎｃｅ）来计算两个概率分布的差异程　度，其公式如下：　ＫＬ（ｐ　Ｐ２一　ｉＥ　Ｐ　（　Ｌ　ｉ）ｌｏｇ（、　，ｚ、　ｌ　Ｉ），山／　　其中，Ｉ　Ｌ　１表示类别个数．算法认为最具有信息含量　的样例是在委员会成员模型中不一致程度最大的样　本分布区间上，并将位于这一区间内的样例交由人　其中，ｖ（ｙ，　）表示委员会中各个假设对　的投票　类专家进行标记．　在表２中，本文给出上述各种样例选择算法的　应用领域和优缺点比较：　结果，ｌ　Ｍｌ表示委员会中假设的个数．选举熵可以看　作是基于熵的不确定采样策略在ＱＢＣ算法中的推　Ｔａｂｌｅ　２　Ｔｈｅ　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ＱＢＣ　Ａｌｇｏｒｉｔｈｍｓ　表２委员会投票选择算法比较　２．３基于误差缩减的采样策略　基于误差缩减的采样策略是通过减少分类器误　型和回归模型中Ｅｓ８］．由于这种直接估计模型方差的　做法仅适用于方差简单可求的概率模型，而无法应　用于复杂的学习模型，所以很多替代性的标准被提　出，下面将分别介绍．　差直接提高学习算法的泛化能力．这种采样策略具　有很强的统计学基础．采样策略根据样例的实际分　布情况，选择使分类器未来泛化误差最大程度缩减　的　进行标记．因此，该算法的优势就是可以有效　地避免选择野点，缺点是采样策略需要大量的计算，　Ｚｈａｎｇ等人引入费舍尔信息函数来计算每一个　的费舍尔得分并构造费舍尔矩阵ｌ＿５　，计算公式　如下：　ｒｒ　ＪＪ　因为模型参数的变化使每一次样例选择都需要重新　２１２　口＾　Ｊ（　）一一Ｉｌｐ（ａ７，　ｌ　）　ｉｎ　ｐ（．　，夕１　）ｄ　ｄ歹．　费舍尔信息函数大多用于判别模型中衡量样例　标记对模型误差的影响程度，优点是可以有效地表　示出分类器对样例的不确定程度．特别是在多重参　数（ｍｕｌｔｉｐｌｅ　ｐａｒａｍｅｔｅｒｓ）模型中，可以直观地看出　训练分类器＿３］．算法的具体工作步骤是：采样策略把　每一个　都作为候选样例，将其标记后放入已标记　样例集中训练分类器；计算分类器训练后误差的变　化结果；选择能够最大程度缩减分类器误差的样例　进行标记．　样例对模型参数的影响程度．该方法易于选择使模　型方差更接近于样本实际分布的样例　．这种样例　基于误差缩减的采样方法是最早研究的采样方　法之一．在１９９２年，Ｇｅｍａｎ等人　就证明了学习模　型期望误差可以被分解为样本集的噪声、模型偏置　和模型方差三者之和．Ｃｏｈｎ等人在此基础上提出了　主动学习的统计学模型，即基于模型方差最小化的　选择标准被应用于各种主动学习模型当中，包括神　经网络　、条件随机场　以及其他概率模型［＂　．　由于多参数情况下，费舍尔信息函数表现为一个关　于样本方差的矩阵，因此针对费舍尔矩阵的计算也　缩减策略，并成功应用于人工神经网络、高斯混合模　有很多研究成果，包括降低参数空间的维数『５。　等．　吴伟宁等：基于采样策略的主动学习算法研究进展　另外一种替代性的标准是估计样例的未来期望　误差　］，其具体步骤是对每一个　进行标记并将其　加入到已标记样例集．算法估计当前概率分布函数　（ｚ，　），并计算　（　，　）与实际分布概率Ｐ（ｚ，　）的　学习中的样例选择过程进行改进Ｌ６　．目前，这种替　代性策略已经在很多分类模型中得以应用，例如朴　素贝叶斯方法＿６　、高斯随机域模型［６　、逻辑回归模　型ｌ＿６　和支持向量机模型等等　．　在表３中，本文给出上述各种样例选择算法的　应用领域和优缺点比较．　期望误差，最终选择标记使该误差最小的样例．Ｒｏｙ　等人　指出在贝叶斯模型下，该方法使分类精确度　提高了４倍．随后，Ｚｈｕ等人使用这种方法对半监督　Ｔａｂｌｅ　３　Ｔｈｅ　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　Ｓａｍｐｌｉｎｇ　Ｓｔｒａｔｅｇｉｅｓ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｒａｌｉｚｅｄ　Ｅｒｒｏｒ　Ｒｅｄｕｃｔｉｏｎ　表３基于泛化误差缩减的采样策略比较　Ｍｅｔｈｏｄｓ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｃｏｍｐａｒｉｓｏｎ　Ａｐｐｌｉｅｄ　ｗｈｅｎ　ｔｈｅ　ｖａｒｉａｎｃｅ　ｉｓ　ｅａｓｉｌｙ　ｏｂｔａｉｎｅｄ；Ａｖｏｉｄ　ｔｈｅ　ｅｆｆｅｃｔ　ｆｒｏｍ　ｔｈｅ　ｏｕｔｌｉｅｒｓ　Ｅｖａｌｕａｔｅ　ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｓｅｌｅｃｔｅｄ　ｅｘａｍｐｌｅｓ　ｗｈｅｎ　ｔｈｅ　ｍｏｄｅｌ　Ｆｉｓｈｅｒ　ＩｎｆｏｒｍａｔｉｏｎＥ１　７，ｌ　ｇ＇ｓ￣ｓ１　３Ｔｅｘｔ　ｃａｔｅ…趣ｉｇ　：　吐　ｎ　ｈａｓ　ｍｕｌｔｉｐｌｅ　ｐａｒａｍｅｔｅｒｓ；Ｓｅｌｅｃｔ　ｔｈｅ　ｅｘａｍｐｌｅｓ　ｗｈｉｃｈ　ｍａｋｅ　ｔｈｅ　ｖａｒｉａｎｃｅ　ｏｆ　ｔｈｅ　ｍｏｄｅ１　ｃｌｏｓｅ　ｔｏ　ｔｈｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ａｆｔｅｒ　ｂｅｉｎｇ　ｌａｂｅｌｅｄ　Ｅｘｐｅｃｔｅｄ　Ｅｒｒｏｒ　Ｒｅｄｕｃｔｉｏｎ［ｓ２　６ｓ３Ｔｅｘ。ｃＲｔ　：　眦　。　ｉｎ　ｓｕｐｅｒ　ｖｉｓ　ｅｄ　ａｎｄ　ｓｅ　ｍｉ　ｓｕｐ　ｅｒ　甜ｌｅａｒｎｉｎｇ　吐　；　足．Ｄｏｎｍｅｚ等人＿６。　提出了ＩＥＴｈｒｅｓｈ方法对在线专　３主动学习算法的新挑战　随着应用领域的扩展，不同学习任务对主动学　习算法提出新的要求．为了解决这些新问题，主动学　家精度进行动态估计，并在迭代过程中选择部分高　精度专家对查询样例进行重复标记．２０１０年又针对　该问题建立了Ｍａｒｋｏｖ模型ｌ６　，进一步证明即使专　家精度可变，主动学习依然可以获得较高质量的训　练集和较高泛化能力的分类器．　然而，这一领域依然存在一些开放性问题没有　解决ｌｌ３］，例如标记者精度是否与其所标记过的样例　相关，随着在线标记时间的增长，标记者精度是因标　记数量增长而更加熟练进而精度增加，还是会疲劳　以至于下降，进一步而言，主动学习应该如何判断所　选样例与标记者的关系，是否应当针对标记者的兴　趣来选择适当样例，是否应当选择标记者最擅长的　类别进行查询标记．如果样例含有噪声，主动学习应　习算法演变出不同的形式，发展出有别于传统主动　学习算法的新类型．本节根据主动学习面临的挑战　不同，我们对这些主动学习算法进行总结和介绍，并　指出其面ｌ临的开放性问题．　３．１在线标记任务中主动学习　为了解决标记获取困难这一瓶颈问题，很多数　据挖掘任务、自然语言处理、图像收集等都使用在线　标记工具（例如ＭＴｕｒｋ　ｔｏｏｌ｜６６］）对无标记样例进行　标记，该方法的优势是短时间内就可以获取大量廉　价标记，缺点是在线标记人员专业水平参差不齐，提　供的标记可能有错误或缺失．而传统主动学习的假　当怎样选择样例，怎样选择专家，重复标记会产生怎　样的影响．这些问题都有待进一步讨论和解决．　３．２代价敏感的主动学习　设条件是专家所提供的标记正确无误，这使得实际　应用中算法性能受到了很大的影响．Ｓｈｅｎｇ等人Ｅ６７３　对这一问题进行了研究和讨论，并提出重复标记同　一在实际应用中，样例的标记代价并非相等而且　保持不变．例如，被广泛应用于文本分类以及图像检　索的多示例学习．一个文本被看作是包含一组词汇　的“包”；一幅图像则被看作是包含一组视觉对象的　样例的解决办法，证明当专家标记精度高于平均　水平并相差较小时，重复标记方法可以有效减少标　记噪声对分类器的影响．但是，该方法的局限性是没　“包”，而“包”不同，标记代价也不同．以图像为例，如　图４所示［７　，图像包含的视觉对象不同，标记代价　也不同．标记代价高也不代表图像包含的信息含量　大，或者对训练过程更有效．这种情况下，需要精确　衡量标记代价与信息含量之间的关系来选择图像．　有区别对待精度不同的专家，特别是当专家水平相　差较大时，低质量专家会对算法产生较大负面影响，　而且，算法需要使用一个无噪声标记样例集对专家　水平进行衡量，这一要求在实际应用中往往很难满　计算机研究与发展２０１２，４９（６）　找到最有价值的标记样例．这些问题也是当前研究　热点和未来研究重点，下面将一一阐述．　首先，结合半监督学习思想改进主动学习的采　样策略可以有效地利用无标记样例的固有信息．原　（ａ）Ｌｏｗ　ｃｏｓｔ，ｈｉｇｈ　ｉｎｆｏｒｍａｔｉｏｎ　（ｂ）Ｈｉｇｈ　ｃｏｓｔ，ｌｏｗ　ｉｎｆｏｒｍａｔｉｏｎ　因是主动学习与半监督学习面临相同的挑战和问　题，即将有标记样例和无标记样例相结合进行训练，　构造分类器模型．传统的主动学习多数采用监督学　■ｌ　＿盥　习算法构造分类器，与半监督算法相结合的研究成　（ｃ）Ｈｉｇｈ　ＣＯＳｔ，ｈｉｇｈ　ｉｎｆｏｒｍａｔｉｏｎ　（ｄ）Ｌｏｗ　ｃｏｓｔ，ｌｏｗ　ｉｎｆｏｒｍａｔｉｏｎ　Ｆｉｇ．４　Ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｅ　ｌａｂｅｌｉｎｇ　ｃｏｓｔ　ａｎｄ　ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｎ　ｔｈｅ　ｉｍａｇｅｓ．　图４图像标记代价与信息含量比较　目前，主动学习已有一些针对代价敏感问题的　成果＿３］，但是，这些成果都是针对特定问题或者模　型，因而具有一定的局限性．例如在信息提取任务　中，“预标记”方法［４　的目的是减少结构学习任务　中的总标记代价，但是这一做法的假设条件是每次　标记行为的代价是一定的．标记行为多则标记代价　高．算法通过最小化标记行为的数量来间接减少标　记总代价．在生物信息提取任务中，Ｋｉｎｇ等人ｌ７　使　用了决策论方法通过减少生物实验所用物质总量来　间接减少一次实验代价．Ｋａｐｏｏｒ等人　则同时考　虑了样例的标记代价和误分类代价，使用二者之和　作为总代价，但该方法要求这两种代价都是固定且　已知的．当标记代价可变时，Ｓｅｔｔｌｅｓ等人　使用逻　辑回归模型对其进行预测，但仅适用于代价是标记　时间的函数这种简单情况，不适合其他复杂应用　情形．　这一领域存在的开放性问题有＿３］：当标记代价　随标记者不同而变化时，主动学习应当如何选择样　例或者标记者　。］；当标记代价并非样例自身的属　性决定，也不能直接计算时，主动学习算法该如何处　理这一情况；以及在仅有少量标记样例时，主动学习　如何去估计其他无标记样例获得标记的代价［７　。　．　４主动学习的研究趋势　当前，尽管主动学习算法已有一定研究成　果￣７８－７９］，但是主动学习算法研究方兴未艾，其采样策　略的设计、算法理论及实际应用依然有很多问题需　要解决．其核心是如何充分利用未标记样例的先验　信息，如何选择样例进行标记进而最大化减少训练　分类器所需的标记代价，如何在最少的查询次数中　果并不多见［８　８１＿．事实上，半监督学习已经发展出大　量成熟而效果显著的对无标记样例的进行利用技　术＿１］，充分利用这些技术可以使主动学习构造出泛　化能力更强的分类器ｒ６　．　其次，在主动学习与结构化预测等学习任务的　结合研究中选择标记结构化数据从而有效减少标记　代价．随着结构化数据研究的逐步深入，采样策略选　择样例进行标记并不局限在样例本身，而是以结构　化等形式存在．例如：在多示例学习中，对包进行标　记　；在序列预测任务中，对序列样例的特征进行　标记ｌ８　．这种趋势与当前机器学习领域的发展相一　致的，机器学习不仅仅关注对单个样例的学习问题，　更为关注的是对图，生物序列信息等复杂结构Ｌ４　进　行分类和识别．主动学习如何结合这些新的学习任　务对结构化信息进行选择，如何对实例以及实例的　特征进行标记，又将选择哪些特征交由人类专家进　行标记，进而得到通用性高的样例选择算法，是值得　进一步探讨的问题ｌ】　。引．　最后，不可达条件下的主动学习的采样策略研　究是研究的重点之一Ｌ８　，尤其是该条件下的理论研　究更加广受关注．尽管主动学习在实际应用中有出　色的表现，但是，算法的理论研究却局限于具体问题　而缺乏一般性的结论，这些都有待进一步＿的研究　解决．　５　总　结　主动学习在处理大量未标记样例、少量有标记　样例的学习问题时，其结果明显优于传统监督学习　算法，进而得到了日益广泛的关注和重视．主动学习　技术可以有效地减少构建分类器所需要的高质量训　练样例的数量，在不影响分类器泛化性能的基础上，　减少人类专家的负担．随着机器学习技术的进步和　应用领域的扩展，主动学习研究应当结合这些新理　论、新技术，以便更好地解决实际问题．　吴伟宁等：基于采样策略的主动学习算法研究进展　致谢　感谢《计算机研究与发展》审稿专家对本　文提出宝贵的修改意见和帮助！　参　考　文　献　［１］　Ｚｈｕ　Ｘｉａｏｊｉｎ．Ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ　ｌｉｔｅｒａｔｕｒｅ　ｓｕｒｖｅｙ，　ＴＲ１５３０［Ｒ］．Ｍａｄｉｓｏｎ，Ｗｉｓｃｏｎｓｉｎ：Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅｓ，　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｗｉｓｃｏｎｓｉｎ—Ｍａｄｉｓｏｎ，２００５　［２］　Ｔｏｍａｎｅｋ　Ｋ，Ｏｌｓｓｏｎ　Ｆ．Ａ　Ｗｅｂ　ｓｕｒｖｅｙ　ｏｎ　ｔｈｅ　ｕｓｅ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｔｏ　ｓｕｐｐｏｒｔ　ａｎｎｏｔａｔｉｏｎ　ｏｆ　ｔｅｘｔ　ｄａｔａ［ｃ］／Ｐｒｏｃ　ｏｆ　ＨＬＴ—ＮＡＡＣＬ．Ｓｔｒｏｕｄｓｂｕｒｇ，ＰＡ：ＡＣＬ，２００９：４５—４８　［３］　Ｓｅｔｔｌｅｓ　Ｂ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｌｉｔｅｒａｔｕｒｅ　ｓｕｒｖｅｙ，ＴＲ１６４８［Ｒ］．　Ｍａｄｉｓｏｎ，Ｗｉｓｃｏｎｓｉｎ：Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅｓ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｗｉｓｃｏｎｓｉｎ—Ｍａｄｉｓｏｎ，２００９　［４３　Ｇｕｙｏｎ　Ｉ，Ｃａｗｌｅｙ　Ｇ，Ｄｒｏｒ　Ｇ，ｅｔ　ａ１．Ｄｅｓｉｇｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＷＣＣＩ　２０１０　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｃｈａｌｌｅｎｇｅ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ／　ＩＮＮＳ　ＩＪＣＮＮ　２０１０．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２０１０：１—８　［５］　Ａｎｇｌｕｉｎ　Ｄ．Ｑｕｅｒｉｅｓ　ａｎｄ　ｃｏｎｃｅｐｔ　ｌｅａｒｎｉｎｇ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９８８，２（４）：３１９－３４２　［６］　Ｄａｓｇｕｐｔａ　Ｓ，Ｌａｎｇｆｏｒｄ　Ｊ．Ａ　ｔｕｔｏｒｉａｌ　ｏｎ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ＥＢ／　ＯＬ］．（２００９—０６—０４）［２０１０—０７—２９］．ｈｔｔｐ：／／ｈｕｎｃｈ．ｎｅｔ／～　ａｃｔｉｖｅｌｅａｒｎｉｎｇ／　［７］　Ｗｕ　Ｙｉ，Ｋｏｚｉｎｔｓｅｖ　Ｉ，Ｂｏｕｇｕｅｔ　Ｊ　Ｙ，ｅｔ　ａ１．Ｓａｍｐｌｉｎｇ　ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　ｐｅｒｓｏｎａｌ　ｐｈｏｔｏ　ｒｅｔｒｉｅｖａｌ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＥ　２００６．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２００６：５２９—５３２　［８］　Ｂａｕｍ　Ｅ　Ｂ，Ｌａｎｇ　Ｋ．Ｑｕｅｒｙ　ｌｅａｒｎｉｎｇ　ｃａｎ　ｗｏｒｋ　ｐｏｏｒｌｙ　ｗｈｅｎ　ａ　ｈｕｍａｎ　ｏｒａｃｌｅ　ｉｓ　ｕｓｅｄ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＩＪＣＮＮ　１９９２．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，１９９２：３３５—３４０　［９］　Ｃｏｈｎ　Ｄ，Ａｔｌａｓ　Ｌ，Ｌａｄｎｅｒ　Ｒ．Ｉｍｐｒｏｖｉｎｇ　ｇｅｎｅｒａｌｉｚａｔｉ０ｎ　ｗｉｔｈ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９４，１５（２）：２０１—　２２１　［ｉＯ］　Ｓｅｕｎｇ　Ｈ　Ｓ，Ｏｐｐｅｒ　Ｍ，Ｓｏｍｐｏｌｉｎｓｋｙ　Ｈ．Ｑｕｅｒｙ　ｂｙ　ｃｏｍｍｉｔｔｅｅ　［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＣＯＬＴ　１９９２．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，１９９２：２８７—　２９４　［１１］　Ｄａｓｇｕｐｔａ　Ｓ，Ｋａｌａｉ　Ａ，Ｍｏｎｔｅｌｅｏｎｉ　Ｃ．Ａｎａｌｙｓｉｓ　ｏｆ　ｐｅｒｃｅｐｔｒｏｎ－　ｂａｓｅｄ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｒｅｓｅａｒｃｈ，２００９。１０（２）：２８１—２９９　［１２］　Ｄａｇａｎ　Ｉ，Ｅｎｇｅｌｓｏｎ　Ｓ　Ｐ．Ｃｏｍｍｉｔｔｅｅ－ｂａｓｅｄ　ｓａｍｐｌｉｎｇ　ｆｏｒ　ｔｒａｉｎｉｎｇ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｃｌａｓｓｉｆｉｅｒｓ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　１９９５．　Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９５：１５０—１５７　［１３］　Ｙｕ　Ｈ．ＳＶＭ　ｓｅｌｅｃｔｉｖｅ　ｓａｍｐｌｉｎｇ　ｆｏｒ　ｒａｎｋｉｎｇ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｄａｔａ　ｒｅｔｒｉｅｖａｌ［Ｃ］／Ｐｒｏｅ　ｏｆ　ＡＣＭ　ＳＩＧＫＤＤ　２００５．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００５：３５４—３６３　［１４］　Ｌｅｗｉｓ　Ｄ，Ｃａｔｌｅｔｔ　Ｊ．　Ｈｅｔｅｒ０ｇｅｎｅ０ｕｓ　ｕｎｃｅｒｔａｉｎｔｙ　ｓａｍｐｌｉｎｇ　ｆｏｒ　ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　１９９４．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：　Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９４：１４８—１５６　［１５］　ＭｃＣａｌｌｕｍ　Ａ，Ｎｉｇａｍ　Ｋ．Ｅｍｐｌｏｙｉｎｇ　ＥＭ　ｉｎ　ｐｏｏｌ—ｂａｓｅｄ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｔｅｘｔ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　１９９８．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９８：３５９—３６７　１１７１　［　０］　Ｔｏｎｇ　Ｓ，Ｋｏｌｌｅｒ　Ｄ．Ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎｓ　ｔｏ　ｔｅｘｔ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ［ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２０００．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，２０００：９９９—１００６　［１７］　Ｈｏｉ　Ｓ　Ｃ　Ｈ，Ｊｉｎ　Ｒｏｎｇ，Ｌｙｕ　Ｍ　Ｒ．Ｌａｒｇｅ　ｓｃａｌｅ　ｔｅｘｔ　ｃａｔｅｇｏｒｉｚａｔｉｏｎ　ｂｙ　ｂａｔｃｈ　ｍｏｄｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＷＷＷ　２００６．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００６：６３３－６４２　［１８］　Ｔｈｏｍｐｓｏｎ　Ｃ　Ａ，Ｃａｌｉｆｆ　Ｍ　Ｅ，Ｍｏｏｎｅｙ　Ｒ　Ｊ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｎａｔｕｒａｌ　ｌａｎｇｕａｇｅ　ｐａｒｓｉｎｇ　ａｎｄ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｘｔｒａｃｔｉｏｎ［ｃ］／／　Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　１９９９．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，　１９９９：４０６—４１４　［１９３　Ｓｅｔｔｌｅｓ　Ｂ．Ｃｒａｖｅｎ　Ｍ．Ａｎ　ａｎａｌｙｓｉｓ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　ｓｅｑｕｅｎｃｅ　ｌａｂｅｌｉｎｇ　ｔａｓｋｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＥＭＮＬＰ　２００８．　Ｓｔｒｏｕｄｓｂｕｒｇ，ＰＡ：ＡＣＬ，２００８：１０６９—１０７８　［２０］　Ｔｏｎｇ　Ｓ，Ｃｈａｎｇ　Ｅ．Ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｉｍａｇｅ　ｒｅｔｒｉｅｖａｌ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ｍｕｌｔｉｍｅｄｉａ　２００１．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ，２００１：１０７—１１８　［２１］　Ｚｈａｎｇ　Ｃｈａ，Ｃｈｅｎ　Ｔ．Ａｎ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｃｏｎｔｅｎｔ　ｂａｓｅｄ　ｉｎｆｏｒｍａｔｉｏｎ　ｒｅｔｒｉｅｖａｌ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　、　Ｍｕｌｔｉｍｅｄｉａ，２００２，４（２）：２６０—２６８　［２２３　Ｙａｎ　Ｒｏｎｇ，Ｙａｎｇ　Ｊｉｅ，Ｈａｕｐｔｍａｎｎ　Ａ．Ａｕｔｏｍａｔｉｃａｌｌｙ　ｌａｂｅｌｉｎｇ　ｖｉｄｅｏ　ｄａｔａ　ｕｓｉｎｇ　ｍｕｌｔｉ—ｃｌａｓｓ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＩＣＣＶ　２００３．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２００３：５１６－５２３　［２３］　Ｈａｕｐｔｍａｎｎ　Ａ，Ｌｉｎ　Ｗｅｉｈａｏ，Ｙａｎ　Ｒｏｎｇ　ｅｔ　ａ１．Ｅｘｔｒｅｍｅ　ｖｉｄｅｏ　ｒｅｔｒｉｅｖａｌ：Ｊｏｉｎｔ　ｍａｘｉｍｉｚａｔｉｏｎ　ｏｆ　ｈｕｍａｎ　ａｎｄ　ｃｏｍｐｕｔｅｒ　ｐｅｒｆｏｒｍａｎｃｅ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ｍｕｌｔｉｍｅｄｉａ　２００６．Ｎｅｗ　Ｙｏｒｋ：　ＡＣＭ，２００６：３８５—３９４　［２４］　Ｌｉｕ　Ｙｉｎｇ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅ　ａｐｐｌｉｅｄ　ｔｏ　ｇｅｎｅ　ｅｘｐｒｅｓｓｉｏｎ　ｄａｔａ　ｆｏｒ　ｃａｎｃｅｒ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｅｍｉｃａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅｓ，　２００４，４４（６）：１９３６－１９４１　［２５］　Ｂａｌｃａｎ　Ｍ　Ｆ，Ｂｒｏｄｅｒ　Ａ　Ｚ，Ｚｈａｎｇ　Ｔｏｎｇ．Ｍａｒｇｉｎ　ｂａｓｅｄ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｇ］／／ＬＮＣＳ　４５３９：Ｐｒｏｃ　ｏｆ　ＣＯＬＴ　２００７．Ｂｅｒｌｉｎ：　Ｓｐｒｉｎｇｅｒ，２００７：３５—５０　［２６］　Ｄａｓｇｕｐｔａ　Ｓ，Ｋａｌａｉ　Ａ　Ｔ，Ｍｏｎｔｅｌｅｏｎｉ　Ｃ．　Ａｎａｌｙｓｉｓ　ｏｆ　ｐｅｒｃｅｐｔｒｏｎ—ｂａｓｅｄ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｇ］／／ＬＮＣＳ　３５５９：Ｐｒｏｃ　ｏｆ　ＣＯＬＴ　２００５．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００５：２４９—２６３　［２７］　Ｄａｓｇｕｐｔａ　Ｓ．Ｃｏａｒｓｅ　ｓａｍｐｌｅ　ｃｏｍｐｌｅｘｉｔｙ　ｂｏｕｎｄｓ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００５．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００６：２３５－２４２　［２８］　Ｂａｌｃａｎ　Ｍ　Ｆ，Ｈａｎｎｅｋｅ　Ｓ，Ｗｏｒｔｍａｎ　Ｊ．Ｔｈｅ　ｔｒｕｅ　ｓａｍｐｌｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＣＯＬＴ　２００８．　Ｍａｄｉｓｏｎ，ＷＩ：Ｏｍｎｉｐｒｅｓｓ，２００８：４５—５６　［２９］　Ｄａｓｇｕｐｔａ　Ｓ．Ａｎａｌｙｓｉｓ　ｏｆ　ａ　ｇｒｅｅｄｙ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｓｔｒａｔｅｇｙ［ｃ］　／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００４．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００５：　３３７—３４４　［３０］　Ｆｒｅｕｎｄ　Ｙ，Ｓｅｕｎｇ　Ｈ　Ｓ，ｅｔ　ａ１．Ｓｅｌｅｃｔｉｖｅ　ｓａｍｐｌｉｎｇ　ｕｓｉｎｇ　ｔｈｅ　ｑｕｅｒｙ　ｂｙ　ｃｏｍｍｉｔｔｅｅ　ａｌｇｏｒｉｔｈｍ［刀．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９７，　２８（２／３）：１３３－１６８　［３１］　Ｇｉｌａｄ—Ｂａｃｈｒａｃｈ　Ｒ。Ｎａｖｏｔ　Ａ，Ｔｉｓｈｂｙ　Ｎ．Ｑｕｅｒｙ　ｂｙ　ｃｏｍｍｉｔｔｅｅ　ｍａｄｅ　ｒｅａｌ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００５．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００６：４４３－４５０　ｌ１７２　［３２］　Ｂａｌｃａｎ　Ｍ，Ｂｅｙｇｅｌｚｉｍｅｒ　Ａ，Ｌａｎｇｆｏｒｄ　Ｊ．Ａｇｎｏｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００６．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００６：　６５—７２　［３３］　Ｈａｎｎｅｋｅ　Ｓ．Ａ　ｂｏｕｎｄ　ｏｎ　ｔｈｅ　ｌａｂｅｌ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ａｇｎｏｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００７．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，　２００７：３５３－３６０　［３４］　Ｄａｓｇｕｐｔａ　Ｓ，Ｈｓｕ　Ｄ，Ｍｏｎｔｅｌｅｏｎｉ　Ｃ．Ａ　ｇｅｎｅｒａｌ　ａｇｎｏｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ［ｃ］／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００７．Ｃａｍｂｒｉｄｇｅ，　ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００８：３５３－３６０　［３５３　Ｂｅｙｇｅｌｚｉｍｅｒ　Ａ，Ｄａｓｇｕｐｔａ　Ｓ，Ｌａｎｇｆｏｒｄ　Ｊ．　Ｉｍｐｏｒｔａｎｃｅ　ｗｅｉｇｈｔｅｄ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００９．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００９：４９—５６　Ｅ３６］　Ｗａｎｇ　Ｗｅｉ，Ｚｈｏｕ　Ｚｈｉｈｕａ．Ｏｎ　ｍｕｌｔｉ—ｖｉｅｗ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｗｉｔｈ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＡＣＭ　ＩＣＭＬ　２００８．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００８：１Ｉ５２～１Ｉ５９　［３７］　Ｈａｎｎｅｋｅ　Ｓ．Ｒａｔｅｓ　ｏｆ　ｃｏｎｖｅｒｇｅｎｃｅ　ｉｎ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｊ］．Ｔｈｅ　Ａｎｎａｌｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃｓ，２０１１，３９（１）：３３３—３６１　［３８］　Ｃａｓｔｒｏ　Ｒ　Ｍ，Ｎｏｗａｋ　Ｒ　Ｄ．Ｕｐｐｅｒ　ａｎｄ　ｌｏｗｅｒ　ｅｒｒｏｒ　ｂｏｕｎｄｓ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　Ａｌｌｅｒｔｏｎ　２００６．Ｒｅｄ　Ｈｏｏｋ，ＮＹ：　Ｃｕｒｒａｎ　Ａｓｓｏｃｉａｔｅｓ，２００７：２２５－２３４　［３９］　Ｋａａｒｉａｉｎｅｎ　Ｍ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　ｔｈｅ　ｎｏｎ—ｒｅａｌｉｚａｂｌｅ　ｃａｓｅ［Ｇ］　／／ＬＮＡＩ　４２６４：Ｐｒｏｃ　ｏｆ　ＡＬＴ　２００６．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００６：　６３—７７　［４０］　Ｃａｖａｌｌａｎｔｉ　Ｇ，　Ｃｅｓａ—Ｂｉａｎｅｈｉ　Ｎ，　Ｇｅｎｔｉｌｅ　Ｃ．Ｌｉｎｅａｒ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　ｓｅｌｅｃｔｉｖｅ　ｓａｍｐｌｉｎｇ　ｕｎｄｅｒ　ｌｏｗ　ｎｏｉｓｅ　ｃｏｎｄｉｔｉｏｎｓ［ｃ］／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００８．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００９：２４９－２５６　［４１］　Ｃａｓｔｒｏ　Ｒ　Ｍ，Ｎｏｗａｋ　Ｒ　Ｄ．Ｍｉｎｉｍａｘ　ｂｏｕｎｄｓ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，２００８，５４　（５）：２３３９－２３５３　［４２］　Ｗａｎｇ　Ｌｉｗｅｉ．　Ｓｕｆｆｉｃｉｅｎｔ　ｃｏｎｄｉｔｉｏｎｓ　ｆｏｒ　ａｇｎｏｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎａｂｌｅ［ｃ］／Ｐｒｏｅ　ｏｆ　ＮＩＰＳ　２００９．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００９：１９９９－２００７　［４３］　Ｗａｎｇ　Ｗｅｉ，Ｚｈｏｕ　Ｚｈｉｈｕａ．Ｍｕｌｔｉ—ｖｉｅｗ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　ｔｈｅ　ｎｏｎ—ｒｅａｌｉｚａｂｌｅ　ｃａｓｅ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２０１０．Ｃａｍｂｒｉｄｇｅ，　ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２０１０：２３８８－２３９６　［４４］　Ｍｕｓｌｅａ　Ｉ，Ｍｉｎｔｏｎ　Ｓ，Ｋｎｏｂｌｏｃｋ　Ｃ　Ａ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｍｕｌｔｉｐｌｅ－ｖｉｅｗｓ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　Ｒｅｓｅａｒｃｈ，２００６，２７：２０３－２３３　［４５］　Ｃｕｌｏｔｔａ　Ａ，ＭｃＣａｌｌｕｍ　Ａ．　Ｒｅｄｕｃｉｎｇ　ｌａｂｅｌｉｎｇ　ｅｆｆｏｒｔ　ｆｏｒ　ｓｔｒｕｃｔｕｒｅｄ　ｐｒｅｄｉｃｔｉｏｎ　ｔａｓｋｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＡＡＡＩ　２００５．Ｍｅｎｌｏ　Ｐａｒｋ，ＣＡ：ＡＡＡＩ，２００５：７４６—７５１　［４６］　Ｓｃｈｅｆｆｅｒ　Ｔ，Ｄｅｃｏｍａｉｎ　Ｃ，Ｗｒｏｂｅｌ　Ｓ．Ａｃｔｉｖｅ　ｈｉｄｄｅｎ　Ｍａｒｋｏｖ　ｍｏｄｅｌｓ　ｆｏｒ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｘｔｒａｃｔｉｏｎ［Ｇ］／／ＬＮＣＳ　２１８９：Ｐｒｏｃ　ｏｆ　ＣＡＩＤＡ　２００１．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００１：３０９—３１８　［４７１　Ｋｉｍ　Ｓ，Ｓｏｎｇ　Ｙｕ，Ｋ　Ｋｉｍ，ｅｔ　ａ１．ＭＭＲ—ｂａｓｅｄ　ａｃｔｉｖｅ　ｍａｃｈｉｎｅ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｂｉｏ—ｎａｍｅｄ　ｅｎｔｉｔｙ　ｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＨＬＴ＿　ＮＡＡＣＬ　２００６．Ｓｔｒｏｕｄｓｂｕｒｇ，ＰＡ：ＡＣＬ，２００６：６９—７２　［４８］　Ｓｃｈｏｈｎ　Ｇ，Ｃｏｈｎ　Ｄ．Ｌｅｓｓ　ｉｓ　ｍｏｒｅ：Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２０００．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，２０００：８３９—８４６　计算机研究与发展２０１２，４９（６）　［４９］　Ｘｕ　Ｚｈａｏ，Ｙｕ　Ｋａｉ，Ｔｒｅｓｐ　Ｖ，ｅｔ　ａ１．Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｓａｍｐｌｉｎｇ　ｆｏｒ　ｔｅｘｔ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｕｓｉｎｇ　ｓｕｐｐｏｒｔ　ｖｅｃｔｏｒ　ｍａｃｈｉｎｅｓ［Ｇ］／／　ＬＮＣＳ　２６３３：Ｐｒｏｃ　ｏｆ　ＥＣＩＲ　２００３．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００３：　３９３－４０７　［５０］　Ｎｇｕｙｅｎ　Ｈ　Ｔ，Ｓｍｅｕｌｄｅｒｓ　Ａ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｕｓｉｎｇ　ｐｒｅ－　ｃｌｕｓｔｅｒｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００４．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，　２００４：７９－８６　［５１］　Ｓａｎｊｏｙ　Ｄ，Ｄａｎｉｅｌ　Ｈ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｓａｍｐｌｉｎｇ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００８．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００８：　２０８－２１５　［５２］　Ｄｏｎｍｅｚ　Ｐ，Ｃａｒｂｏｎｅｌｌ　Ｊ　Ｇ，Ｂｅｎｎｅｔｔ　Ｐ　Ｎ．Ｄｕａｌ　ｓｔｒａｔｅｇｙ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｇ］／／ＬＮＡＩ　４７０　１：Ｐｒｏｅ　ｏｆ　ＥＣＭＬ　２００７．Ｂｅｒｌｉｎ：　Ｓｐｒｉｎｇｅｒ，２００７：１１６－１２７　［５３］　Ｈｕａｎｇ　Ｓｈｅｎｇｊｕｎ，Ｊｉｎ　Ｒｏｎｇ，Ｚｈｏｕ　Ｚｈｉｈｕａ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｂｙ　ｑｕｅｒｙｉｎｇ　ｉｎｆｏｒｍａｔｉｖｅ　ａｎｄ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｅｘａｍｐｌｅｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２０１０．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２０１０：８９２－９００　Ｅ５４］　Ａｂｅ　Ｎ，Ｍａｍｉｔｓｕｋａ　Ｈ．Ｑｕｅｒｙ　ｌｅａｒｎｉｎｇ　ｓｔｒａｔｅｇｉｅｓ　ｕｓｉｎｇ　ｂｏｏｓｔｉｎｇ　ａｎｄ　ｂａｇｇｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　１９９８．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９９８：１—９　［５５］　Ｆｒｅｕｎｄ　Ｙ，Ｓｅｈａｐｉｒｅ　Ｒ　Ｅ．Ａ　ｄｅｃｉｓｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ｇｅｎｅｒａｌｉｚａｔｉｏｎ　ｏｆ　ｏｎ—ｌｉｎｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ａｎ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｂｏｏｓｔｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅｓ，１９９７，５５（１）：１１９－１３９　［５６］　Ｂｒｅｉｍａｎ　Ｌ．Ｂａｇｇｉｎｇ　ｐｒｅｄｉｃｔｏｒｓ口］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ。　１９９６，２４（２）：１２３—１４０　［５７］　Ｇｅｍａｎ　Ｓ，Ｂｉｅｎｅｎｓｔｏｃｋ　Ｅ，Ｄｏｕｒｓａｔ　Ｒ．Ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ　ａｎｄ　ｔｈｅ　ｂｉａｓ／ｖａｒｉａｎｃｅ　ｄｉｌｅｍｍａ［Ｊ］．Ｎｅｕｒａｌ　Ｃｏｍｐｕｔａｔｉｏｎ，１９９２，４　（１）：１—５８　［５８］　Ｃｏｈｎ　Ｄ，Ｇｈａｈｒａｍａｎｉ　Ｚ，Ｊｏｒｄａｎ　Ｍ　Ｉ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｓｔａｔｉｓｔｉｃａｌ　ｍｏｄｅｌｓ口］．Ｊｏｕｒｎａｌ　ｏｆ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　Ｒｅｓｅａｒｃｈ，１９９６，４：１２９－１４５　［５９］　Ｚｈａｎｇ　Ｔｏｎｇ，Ｏｌｅｓ　Ｆ　Ｊ．Ａ　ｐｒｏｂａｂｉｌｉｔｙ　ａｎａｌｙｓｉｓ　ｏｎ　ｔｈｅ　ｖａｌｕｅ　ｏｆ　ｕｎｌａｂｅｌｅｄ　ｄａｔａ　ｆｏｒ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｐｒｏｂｌｅｍｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２０００．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，２０００：１１９１—１１９８　［６Ｏ］　Ｐａａｓｓ　Ｇ，Ｋｉｎｄｅｒｍａｎｎ　Ｊ．Ｂａｙｅｓｉａｎ　ｑｕｅｒｙ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｆｏｒ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ｍｏｄｅｌｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　１９９５．Ｃａｍｂｒｉｄｇｅ，　ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，１９９５：４４３—４５０　［６１］　Ｈｏｉ　Ｓ　Ｃ　Ｈ，Ｊｉｎ　Ｒｏｎｇ，Ｚｈｕ　Ｊｉａｎｋｅ　ｅｔ　ａ１．Ｂａｔｃｈ　ｍｏｄｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｍｅｄｉｃａｌ　ｉｍａｇｅ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ［ｃ］　／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００６．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００６：４１７－４２４　［６２］　Ｒｏｙ　Ｎ，ＭｃＣａｌｌｕｍ　Ａ．Ｔｏｗａｒｄ　ｏｐｔｉｍａｌ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｔｈｒｏｕｇｈ　ｓａｍｐｌｉｎｇ　ｅｓｔｉｍａｔｉｏｎ　ｏｆ　ｅｒｒｏｒ　ｒｅｄｕｃｔｉｏｎ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００１．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，２００１：４４１—　４４８　［６３］　Ｚｈｕ　Ｘｉａｏｊｉｎ，Ｌａｆｆｅｒｔｙ　Ｊ，Ｇｈａｈｒａｍａｎｉ　Ｚ．Ｃｏｍｂｉｎｉｎｇ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｓｅｍｉ—ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ　ｕｓｉｎｇ　Ｇａｕｓｓｉａｎ　ｆｉｅｌｄｓ　ａｎｄ　ｈａｒｍｏｎｉｃ　ｆｕｎｃｔｉｏｎｓ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＩＣＭＬ　２００３　Ｗｏｒｋｓｈｏｐ　ｏｎ　ｔｈｅ　Ｃｏｎｔｉｎｕｕｍ　ｆｒｏｍ　Ｌａｂｅｌｅｄ　ｔｏ　Ｕｎｌａｂｅｌｅｄ　Ｄａｔａ．Ｍｅｎｌｏ　Ｐａｒｋ，ＣＡ：ＡＡＡＩ，２００３：５８—６５　［６４］　Ｇｕｏ　Ｙｕｈｏｎｇ，Ｇｒｅｉｎｅｒ　Ｒ．Ｏｐｔｉｍｉｓｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｕｓｉｎｇ　ｍｕｔｕａｌ　ｉｎｆｏｒｍａｔｉｏｎ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＪＣＡＩ　２００７．Ｍｅｎｌｏ　Ｐａｒｋ，　ＣＡ：ＡＡＡＩ，２００７：８２３—８２９　吴伟宁等：基于采样策略的主动学习算法研究进展　［６５３　Ｍｏｓｋｏｖｉｔｃｈ　Ｒ，Ｎｉｓｓｉｍ　Ｎ，Ｓｔｏｐｅｌ　Ｄ　ｅｔ　ａ１．Ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｄｅｔｅｃｔｉｏｎ　ｏｆ　ｕｎｋｎｏｗｎ　ｃｏｍｐｕｔｅｒ　ｗｏｒｍｓ　ａｃｔｉｖｉｔｙ　ｕｓｉｎｇ　ａｃｔｉｖｅ　１１７３　（宫秀军，孙建平，史忠植．主动贝叶斯网络分类器ＬＪ］．计　算机研究与发展，２００２，３９（１５）：５７４—５７９）　［７９］　Ｌｏｎｇ　Ｊｕｎ，Ｙｉｎ　Ｊｉａｎｐｉｎｇ，Ｚｈｕ　Ｅｎ，ｅｔ　ａ１．Ａｎ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂｙ　ｓｅｌｅｃｔｉｎｇ　ｔｈｅ　ｍｏｓｔ　ｐｏｓｓｉｂｌｙ　ｗｒｏｎｇ—ｐｒｅｄｉｃｔｅｄ　ｌｅａｒｎｉｎｇ［Ｇ］／／１　ＮＣＳ　４６６７：Ｐｒｏｃ　ｏｆ　３ｏｔｈ　Ｇｅｒｍａｎ　Ｃｏｎｆ　ｏｎ　ＡＩ　２００７．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００７：４８９—４９３　［６６］　Ｓｏｒｏｋｉｎ　Ａ，Ｆｏｒｓｙｔｈ　Ｄ．Ｕｔｉｌｉｔｙ　ｄａｔａ　ａｎｎｏｔａｔｉｏｎ　ｗｉｔｈ　ａｍａｚｏｎ　ｉｎｓｔａｎｃｅｓ［Ｊ］．　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５（３）：４７２—４７８（ｉｎ　Ｃｈｉｎｅｓｅ）　ｍｅｃｈａｎｉｃａｌ　ｔｕｒｋ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＣＶＰＲＷ　２００８．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２００８：１—８　（龙军，殷建平，祝恩。等．选取最大可能预测错误样例的主　动学习算法［Ｊ］．计算机研究与发展，２００８，４５（３）：４７２—　４７８）　［６７］　Ｓｈｅｎｇ　Ｖ　Ｓ，Ｐｒｏｖｏｓｔ　Ｆ，Ｉｐｅｉｒｏｔｉｓ　Ｐ　Ｇ．Ｇｅｔ　ａｎｏｔｈｅｒ　ｌａｂｅｌ？　Ｉｍｐｒｏｖｉｎｇ　ｄａｔａ　ｑｕａｌｉｔｙ　ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇ　ｕｓｉｎｇ　ｍｕｌｔｉｐｌｅ，ｎｏｉｓｙ　ｌａｂｅｌｅｒｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＡＣＭ　ＳＩＧＫＤＤ　２００８．Ｎｅｗ　Ｙｏｒｋ：　［８Ｏ］　Ｚｈｏｕ　Ｚｈｉｈｕａ，Ｃｈｅｎ　Ｋｅｊｉａ，Ｄａｉ　Ｈｏｎｇｂｉｎ．　Ｅｎｈａｎｃｉｎｇ　ＡＣＭ，２００８：６１４－６２２　［６８］　Ｄｏｎｍｅｚ　Ｐ，Ｃａｒｂｏｎｅｌｌ　Ｊ　Ｇ，Ｓｃｈｎｅｉｄｅｒ　Ｊ．Ｅｆｆｉｃｉｅｎｔｌｙ　ｌｅａｒｎｉｎｇ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｌａｂｅｌｉｎｇ　ｓｏｕｒｃｅｓ　ｆｏｒ　ｓｅｌｅｃｔｉｖｅ　ｓａｍｐｌｉｎｇ［ｃ］／／　Ｐｒｏｃ　ｏｆ　ＡＣＭ　ＳＩＧＫＤＤ　２００９．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００９：２５９—　２６８　［６９］　Ｄｏｎｍｅｚ　Ｐ，Ｃａｒｂｏｎｅｌｌ　Ｊ　Ｇ，Ｓｃｈｎｅｉｄｅｒ　Ｊ．Ａ　ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｆｒａｍｅｗｏｒｋ　ｔｏ　ｌｅａｒｎ　ｆｒｏｍ　ｍｕｌｔｉｐｌｅ　ａｎｎｏｔａｔｏｒｓ　ｗｉｔｈ　ｔｉｍｅ—　ｖａｒｙｉｎｇ　ａｃｃｕｒａｃｙ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＳＤＭ　２０１０．Ｐｈｉｌａｄｅｌｐｈｉａ，ＰＡ：　ＳＩＡＭ，２０１０：８２６－８３７　［７０３　Ｖｉｊａｙａｎａｒａｓｉｍｈａｎ　Ｓ，Ｇｒａｕｍａｎ　Ｋ．Ｃｏｓｔ～ｓｅｎｓｉｔｉｖｅ　ａｃｔｉｖｅ　ｖｉｓｕａ１　ｃａｔｅｇｏｒｙ　ｌｅａｒｎｉｎｇ［Ｊ］．Ｉｎｔ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ，２０１１，　９１（１）：２４—４４　［７１］　Ｂａｌｄｒｉｄｇｅ　Ｊ，Ｏｓｂｏｒｎｅ　Ｍ．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ａｎｄ　ｔｈｅ　ｔｏｔａｌ　ｃｏｓｔ　ｏｆ　ａｎｎｏｔａｔｉｏｎ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＥＭＮＬＰ　２００４．Ｓｔｒｏｕｄｓｂｕｒｇ，ＰＡ：　ＡＣＬ，２００４：９－１６　［７２］　Ｋｉｎｇ　Ｒ　Ｄ，Ｗｈｅｌａｎ　Ｋ　Ｅ，Ｊｏｎｅｓ　Ｆ　Ｍ，ｅｔ　ａｌ，Ｆｕｎｃｔｉｏｎａ［　ｇｅｎｏｍｉｃ　ｈｙｐｏｔｈｅｓｉｓ　ｇｅｎｅｒａｔｉｏｎ　ａｎｄ　ｅｘｐｅｒｉｍｅｎｔａｔｉｏｎ　ｂｙ　ａ　ｒｏｂｏｔ　ｓｃｉｅｎｔｉｓｔ［Ｊ］．Ｎａｔｕｒｅ，２００４，４２７（６９７１）：２４７—５２　Ｅ７３３　Ｋａｐｏｏｒ　Ａ，Ｈｏｒｖｉｔｚ　Ｅ，Ｂａｓｕ　Ｓ．Ｓｅｌｅｃｔｉｖｅ　ｓｕｐｅｒｖｉｓｉｏｎ：　Ｇｕｉｄｉｎｇ　ｓｕｐｅｒｖｉｓｅｄ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｄｅｃｉｓｉｏｎ—ｔｈｅｏｒｅｔｉｃ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＪＣＡＩ　２００７．Ｍｅｎｌｏ　Ｐａｒｋ。ＣＡ：　ＡＡＡＩ，２００７：８７７－８８２　［７４３　Ｓｅｔｔｌｅｓ　Ｂ，Ｃａｒｖｅｎ　Ｍ，Ｆｒｉｅｄｌａｎｄ　Ｌ　ｅｔ　ａ１．Ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｗｉｔｈ　ｒｅａｌ　ａｎｎｏｔａｔｉｏｎ　ｃｏｓｔｓ［ｃ］／Ｐｒｏｅ　ｏｆ　ＮＩＰＳ　２００８　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｃｏｓｔ—ｓｅｎｓｉｔｉｖｅ　Ｌｅａｒｎｉｎｇ．　Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，　２００９：１－１０　［７５］　Ｒｉｎｇｇｅｒ　Ｅ，Ｃａｒｍｅｎ　Ｍ，Ｈａｅｒｔｅｌ　Ｒ　ｅｔ　ａ１．Ａｓｓｅｓｓｉｎｇ　ｔｈｅ　ｃｏｓｔｓ　ｏｆ　ｍａｃｈｉｎｅ－ａｓｓｉｓｔｅｄ　ｃｏｒｐｕｓ　ａｎｎｏｔａｔｉｏｎ　ｔｈｒｏｕｇｈ　ａ　ｕｓｅｒ　ｓｔｕｄｙ　［ｃ］／／Ｐｒｏｃ　ｏｆ　ＬＲＥＣ　２００８．Ｐａｒｉｓ：ＥＬＲＡ，２００８：３３１８—３３２４　［７６３　Ａｒｏｒａ　Ｓ，Ｎｙｂｅｒｇ　Ｅ，Ｒｏｓｅ　Ｃ　Ｐ．Ｅｓｔｉｍａｔｉｎｇ　ａｎｎｏｔａｔｉｏｎ　ｃｏｓｔ　ｆｏｒ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ　ｉｎ　ａ　ｍｕｌｔｉ—ａｎｎｏｔａｔｏｒ　ｅｎｖｉｒｏｎｍｅｎｔ［ｃ］／／　Ｐｒｏｃ　ｏｆ　ＮＡＡＣＬ　ＨＬＴ　２００９．Ｓｔｒｏｕｄｓｂｕｒｇ，ＰＡ：ＡＣＬ，２００９：　Ｉ８－２６　［７７３　Ｖｉｊａｙａｎａｒａｓｉｍｈａｎ　Ｓ，Ｇｒａｕｍａｎ　Ｋ．Ｗｈａｔ’８　ｉｔ　ｇｏｉｎｇ　ｔｏ　ｃＯＳｔ　ｙＯＵ？Ｐｒｅｄｉｃｔｉｎｇ　ｅｆｆｏｒｔ　ｖｓ．ｉｎｆｏｒｍａｔｉｖｅｎｅｓｓ　ｆｏｒ　ｍｕｈｉ一１ａｂｅｌ　ｉｍａｇｅ　ａｎｎｏｔａｔｉｏｎｓ［ｃ］／／Ｐｒｏｃ　ｏｆ　ＩＥＥＥ　ＣＶＰＲ　２００９．　Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ，２００９：２２６２—２２６９　［７８］　Ｇｏｎｇ　Ｘｉｕｊｕｎ，Ｓｕｎ　Ｊｉａｎｐｉｎｇ，Ｓｈｉ　Ｚｈｏｎｇｚｈｉ．Ａｎ　ａｃｔｉｖｅ　Ｂａｙｅｓｉａｎ　ｎｅｔｗｏｒｋ　ｃｌａｓｓｉｆｉｅｒ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ，２００２，３９（１５）：５７４—５７９（ｉｎ　Ｃｈｉｎｅｓｅ）　ｒｅｌｅｖａｎｃｅ　ｆｅｅｄｂａｃｋ　ｉｎ　ｉｍａｇｅ　ｒｅｔｒｉｅｖａｌ　ｕｓｉｎｇ　ｕｎｌａｂｅｌｅｄ　ｄａｔａ　［Ｊ］．ＡＣＭ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，２００６，２４（２）：　２１９－２４４　［８１］　Ｚｈｏｕ　Ｚｈｉｈｕａ，Ｃｈｅｎ　Ｋｅｊｉａ，Ｊｉａｎｇ　Ｙｕａｎ．Ｅｘｐｌｏｉｔｉｎｇ　ｕｎｌａｂｅｌｅｄ　ｄａｔａ　ｉｎ　ｃｏｎｔｅｎｔ—ｂａｓｅｄ　ｉｍａｇｅ　ｒｅｔｒｉｅｖａｌ［Ｇ］／／ＬＮＡＩ　３２０１：Ｐｒｏｅ　ｏｆ　ＥＣＭＬ　２００４．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００４：５２５—５３６　［８２］　Ｓｅｔｔｌｅｓ　Ｂ，Ｃｒａｖｅｎ　Ｍ，Ｒａｙ　Ｓ．　Ｍｕｌｔｉｐｌｅ—ｉｎｓｔａｎｃｅ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［ｃ］／Ｐｒｏｃ　ｏｆ　ＮＩＰＳ　２００８．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ　Ｐｒｅｓｓ，２００８：１２８９—１２９６　［８３３　Ｄｒｕｃｋ　Ｇ，Ｍａｎｎ　Ｇ，ＭｃＣａｌｌｕｍ　Ａ．Ｌｅａｒｎｉｎｇ　ｆｒｏｍ　ｌａｂｅｌｅｄ　ｆｅａｔｕｒｅｓ　ｕｓｉｎｇ　ｇｅｎｅｒａｌｉｚｅｄ　ｅｘｐｅｃｔａｔｉｏｎ　ｃｒｉｔｅｒｉａ［Ｃ］／Ｐｒｏｃ　ｏｆ　ＡＣＭ　ＳＩＧＩＲ　２００８．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ，２００８：５９５—６０２　［８４］　Ｓｔｅｍｐ－Ｍｏｒｌｏｃｋ　Ｇ．Ｌｅａｒｎｉｎｇ　ｍｏｒｅ　ａｂｏｕｔ　ａｃｔｉｖｅ　ｌｅａｒｎｉｎｇ［Ｊ］．　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，２００９，５２（４）：１１—１３　ａｎｄ　ｌＴｌａｌｎ　ｉｆｉｃｉａｌ