当前位置:首页 >> >> MIL

MIL


多示例学习*
周志华
南京大学 软件新技术国家重点实验室, 江苏 南京 210093
摘 要: 在多示例学习中,训练样本是由多个示例组成的包,包是有概念标记的,但示例本身却没有概念标记。如

果一个包中至少包含一个正例,则该包是一个正包,否则即为反包。学习的目的是预测新包的类别。由于多示例学 习具有独特的性质,目前被认为是一种新的学习框架。本文对该领域的研究进展进行了综述,并对有待深入研究的 一些问题进行了讨论。

1 引言
20 世纪 90 年代以来,从例子中学习(learning from examples)被认为是最有希望的机器学习途 径 。如果以训练样本的歧义性(ambiguity)作为划分标准,则目前该领域的研究大致建立在三种 学习框架(learning framework)[2] 下,即监督学习、非监督学习和强化学习。 监督学习通过对具有概念标记(concept label)的训练例进行学习,以尽可能正确地对训练集之 外的示例的概念标记进行预测。这里所有的训练样本都是有标记的,因此其歧义性最低。非监督学 习通过对没有概念标记的训练例进行学习,以发现数据中隐藏的结构。这里所有的训练样本都是没 有标记的,因此其歧义性最高。强化学习通过对没有概念标记、但与一个延迟奖赏或效用(可视为 延迟的概念标记)相关联的训练例进行学习,以获得某种从状态到行动的映射。这里所有的训练样 本都是有标记的,但与监督学习不同的是,标记是延迟的,因此强化学习的歧义性介于监督学习与 非监督学习之间。 20 世纪 90 年代中后期,研究者们[3]在对药物活性预测(drug activity prediction)问题的研究中, 提出了多示例学习(multi-instance learning)的概念。在此类学习中,训练集由若干个具有概念标记 的包(bag)组成,每个包包含若干没有概念标记的示例。若一个包中至少有一个正例,则该包被标 记为正(positive) ,若一个包中所有示例都是反例,则该包被标记为反(negative) 。通过对训练包的 学习,希望学习系统尽可能正确地对训练集之外的包的概念标记进行预测。 与监督学习相比,多示例学习中的训练示例是没有概念标记的,这与监督学习中所有训练示例 都有概念标记不同;与非监督学习相比,多示例学习中训练包是有概念标记的,这与非监督学习的 训练样本中没有任何概念标记也不同;而与强化学习相比,多示例学习中又没有时效延迟的概念。 更重要的是,在以往的各种学习框架中,一个样本就是一个示例,即样本和示例是一一对应关系; 而在多示例学习中,一个样本(即包)包含了多个示例,即样本和示例是一对多的对应关系。因此, 多示例学习中训练样本的歧义性与监督学习、非监督学习、强化学习的歧义性都完全不同,这就使 得以往的学习方法难以很好地解决此类问题。由于多示例学习具有独特的性质和广泛的应用前景, 属于以往机器学习研究的一个盲区,因此在国际机器学习界引起了极大的反响,被认为是一种新的 学习框架[2]。
[1]

* 本文得到国家杰出青年科学基金(60325207)和国家自然科学基金(60473046)资助

本文首先介绍多示例学习的起源,然后对该领域的研究进展进行综述,最后对有待深入研究的 一些问题进行讨论。

2 问题的提出
大多数药物都是一些分子,它们通过与较大的蛋白质分子例如酶等绑定来发挥作用,药效则是 由绑定的程度决定的。对适于制造药物的分子来说,它的某个低能形状和期望的绑定区域将耦合得 很紧密;而对不适于制造药物的分子来说,它和期望的绑定区域将耦合得不好。 20 世纪 90 年代中后期,T. G. Dietterich 等人[3]对药物活性预测问题进行了研究。其目的是让学 习系统通过对已知适于或不适于制药的分子进行分析,以尽可能正确地预测某种新的分子是否适合 制造药物。该问题的困难主要在于,每个分子都有很多种可能的低能形状,图 1 给出了一个例子。 而生物化学专家目前只知道哪些分子适于制药,并不知道具体的哪一种形状起到了决定性作用。如 果直接使用监督学习框架,将适于制药的分子的所有低能形状都作为正例,而将所有不适于制药的 分子的所有低能形状都作为反例,则会由于正例中噪音度太高而难以成功地进行学习。这是因为一 个分子可能有上百种低能形状,而这么多形状中只要有一种是合适的,这个分子就适于制药。

旋转

图1

一个内部键发生旋转,分子的形状就发生了显著变化

为了解决这个问题,T. G. Dietterich 等人[3]将每一个分子作为一个包,分子的每一种低能形状作 为包中的一个示例, 由此提出了多示例学习的概念。 为了将分子的低能形状表示成属性-值对的形式, 他们首先将分子固定在标准位置和朝向,然后从原点比较均匀地放射出 162 条射线,每条射线被原 点与分子表面所截出的线段长度就被作为一个属性,如图 2 所示。再加上 4 个表示固定的氧原子位
x2 x4 x5 x8 x7 x6 x3 x1

图2

利用射线来表示分子形状
2

置的属性,这样,包中的每个示例就由 166 个数值属性来描述。 在此基础上,他们提出了三个 APR(Axis-Parallel Rectangles)学习算法[3]。这些算法都是通过 对属性值进行合取,在属性空间中寻找合适的轴平行矩形。GFS elim-count APR 算法先找出覆盖了 所有正包示例的轴平行矩形,再以排除反包中的各示例所分别需要排除的正包示例数为标准,通过 贪心算法逐渐排除反包示例以缩小矩形。图 3 给出了一个例子。图中同样颜色和形状的点表示同一 个包中的示例,白色表示正包,黑色表示反包。GFS elim-count APR 算法先找出一个包含所有正包 示例的轴平行矩形,如图中实线所示。对该矩形所包含的每一个反包示例,图中都标出了为了通过 收缩矩形的边界以将其排除所需付出的代价,即所需附带排除的最少的正包示例数。GFS elim-count APR 算法就根据这些代价,贪心式地逐渐缩小矩形,从而得到了图中虚线所示的结果。最后,该算 法通过贪心属性选择确定该矩形在相关属性上的边界,这样就得到了学习结果。

图3

GFS elim-count APR 算法运行的例子

GFS kde APR 算法则是在 GFS elim-count APR 的基础上, 考虑矩形所覆盖的各正包中的示例数, 利用一个代价函数来使得在排除反包示例时,尽可能少地排除剩余示例较少的正包中的示例。 Iterated-discrim APR 算法先通过贪心式的 backfitting 算法[4]找出一个覆盖了每个正包中至少一个示例 的最小矩形,然后利用该矩形挑选出最具有区别能力的一组属性,在此基础上,通过核密度估计 (kernel density estimation)对最可能出现正包示例的矩形边界不断进行扩展。 T. G. Dietterich 等人[3]利用麝香(musk)分子的数据进行了实验,发现 Iterated-discrim APR 算法 在药物活性预测问题上取得了最好的效果,而 C4.5 决策树、BP 神经网络等常用的监督学习算法效 果很不理想。这说明如果不考虑多示例学习本身的特点,将难以很好地完成此类学习任务。另外, T. G. Dietterich 等人[3]指出,由于 Iterated-discrim APR 算法根据麝香分子的数据进行了优化,因此, 在该数据集上该算法的性能也许代表了一个上限。 实际上,多示例学习问题其实是一直存在的,并不是由于对药物活性预测问题的研究而突然出 现的。只是以往的机器学习研究[5, 6]并没有明确考虑此类问题的特性,到了 T. G. Dietterich 等人的工 作中才正式地把这个问题界定出来。

3

值得注意的是, 多示例学习还引起了归纳逻辑程序设计 (inductive logic programming, 简称 ILP)
[7]

领域的研究者的兴趣。机器学习常用的属性-值对表示方法实际上是一种命题知识表示,而 ILP 领

域的研究使用的是一阶知识表示。一阶知识表示的表达能力比命题知识表示强得多,但要高效地进 行学习却非常困难。L. De Raedt[8]认为,多示例表示为命题知识表示和一阶知识表示建立了联系,在 这种表示下,既有助于利用一阶表示的表达力又有助于发挥命题学习的高效性。因此,ILP 领域的 研究者也对多示例学习进行了研究,但由于这些工作与目前一般意义上的机器学习有较大差别,本 文没有对此进行介绍。

3 研究进展
3.1 可学习性
T. G. Dietterich 等人的工作刚公布, M. Long 和 L. Tan[9]就对多示例学习框架下 APR 的 PAC 可 P. 学习性[10]进行了研究。他们证明,在多示例学习框架下,如果包中的示例是独立的,且符合积分布 (product distribution) ,则 APR 是可以 PAC 学习的。在此基础上,他们提出了一种学习复杂度很高 的理论算法。 此后,P. Auer 等人[11]提出了一种改进的理论算法,该算法不再要求包中示例符合积分布,而且 其学习复杂度比 P. M. Long 和 L. Tan 的算法低得多。更进一步,P. Auer[12]将该理论算法转变为一种 可以用于解决实际问题的应用算法 MULTINST,并且通过在麝香分子数据上的实验显示出该算法在 药物活性预测问题上的可用性。 1998 年,A. Blum 和 A. Kalai[13]将多示例学习框架下的 PAC 学习归结为单边随机分类噪音下的 PAC 学习。这就使得双边随机噪音模型以及校验函数等在单边噪音下可学习的概念类可以从多示例 的角度进行学习。在此基础上,他们得到了一个比 P. Auer 等人[9]的结果更高效的理论算法。 表 1 对上述工作进行了总结,其中(1-ε)与 δ 分别表示精确度与置信度,d 和 n 分别为 APR 的维 数以及每个包中所含的示例数,样本复杂度是指训练包的数目, O 表示忽略结果中的对数项。值得 注意的是,这些工作都假设包中示例是独立的,但遗憾的是,该假设在真实问题中显然是难以成立 的,例如在药物活性预测问题中,同一个分子的低能形状之间是有密切联系的。 表1
样本复杂度 P. M. Long 和 L. Tan 的结果 P. Auer 等人的 结果 A. Blum 和 A. Kalai 的结果

多示例学习可学习性的主要研究结果
时间复杂度 假设条件 主要分析工具 P-concept VC 维的变体 VC 维 统计查询模型 VC 维

O(

d n
2

6

ε

10 2 2

log

nd

εδ δ

)

O(

d n

5 12 20

ε

log 2 d n
3 2

nd

εδ

)

包中示例相互独立, 且满足积分布 包中示例相互独立 包中示例相互独立

O(

d n

ε

2

d log )
2

O( O(

ε2
d 3n 2

) )

O(

d 2n

ε

)

ε

2

总的来看,计算学习理论界为了分析多示例学习的可学习性,提出了一系列多示例学习理论算 法。但由于理论工具的制约,几乎所有的理论算法都对包中示例的分布等施加了种种限制,这就使 得这些理论算法难以直接用于解决实际的问题。因此,这些工作更重要的是丰富了 PAC 理论本身的
4

研究。但有一些结果对解决实际的多示例学习问题也有一定的指导意义,例如,P. Auer 等人[11]通过 分析多示例学习框架下 APR 的可学习性与 DNF 公式(DNF formulas)可学习性之间的关系,证明 了如果包中示例不是独立的,则在多示例框架下对 APR 进行学习是一个 NP 难问题。这一结果在一 定程度上说明,寻找假设结构简单且可以高效完美地解决多示例学习问题的方法几乎是不可能的。

3.2 算法
在 T. G. Dietterich 等人的工作之后,很多研究者开始致力于设计实用的多示例学习算法。 1998 年,O. Maron 和 T. Lozano-Pérez[14]提出了多样性密度(Diverse Density,简称 DD)算法。 在他们的定义中,在属性空间中某点附近出现的正包数越多,反包示例出现得越远,则该点的多样 性密度越大。令 Bi+代表第 i 个正包,Bij+代表第 i 个正包的第 j 个示例,Bijk+代表第 i 个正包的第 j 个 示例的第 k 个属性的值;类似的,令 Bijk-代表第 i 个反包的第 j 个示例的第 k 个属性的值;再令 t 代 表属性空间中多样性密度最大的点。则可通过最大化 Pr(x = t | B1+, …, Bn+, B1-, …, Bm-) 确定 t。假设 各包独立,则根据 Bayes 理论,可通过式(1)确定 t:

arg max ∏ Pr ( x = t | Bi+ )∏ Pr ( x = t | Bi? )
x i i

(1)

式 (1) 就是多样性密度的一般定义。 在实际使用时, 需要对式 (1) 中的乘积项进行例化。 Maron O. 和 T. Lozano-Pérez[14]采用了 noisy-or 模型:
+ Pr ( x = t | Bi+ ) = 1 ? ∏ 1 ? Pr ( x = t | Bij ) ? Pr ( x = t | Bi? ) = ∏ 1 ? Pr ( x = t | Bij ) j

(

j

(

)

(2) (3)

)

他们将示例出现在潜在目标处的因果概率定义为该示例与潜在目标之间的距离,即:

Pr ( x = t | Bij ) = exp ? Bij ? x

(

2

)

(4)

在此基础上,他们使用梯度下降法来寻找最大多样性密度点。由于多样性密度空间中存在多个 局部极小点,因此他们将每一个正包示例都作为初始点进行一次搜索。上述做法不仅可以确定多样 性密度最大点,还可以用来挑选相关属性。即如果用权 sk 来表示第 k 个属性的相关度,则式(4)中 的距离计算式如式(5)所示。最大化多样性密度不仅可以得到一个目标位置,还可以得到一组反映 属性相关度的权值。值得注意的是,由于要多次进行梯度下降搜索,因此 DD 算法的训练时间开销 相当大,但如果不这样做,又难以找到较好的解。

Bij ? x = ∑ sk ( Bijk ? xk )
2 k

2

(5)

O. Maron 等人用麝香分子数据对 DD 算法进行了测试,发现其效果不如 Iterated-discrim APR 算 法,但优于或相当于 GFS elim-kde APR 算法和 MULTINST 算法。随后,他们对 DD 算法进行了一系 列的应用,这将在 3.3 节介绍。 DD 算法对后来的研究有很大影响,很多工作就是直接以该算法为基础进行的。例如,2002 年 Q. Zhang 和 S. A. Goldman[15]将 DD 算法与 EM 算法相结合提出了 EM-DD 算法。他们首先在 EM 算 法的 E 步中估计出决定各训练包概念标记的训练示例, 然后在 M 步中对这些训练示例使用多样性密
5

度算法以最大化多样性密度,反复进行 E 步和 M 步直到收敛为止。该算法在麝香分子数据上取得了 当时最好的结果。 2000 年,J. Wang 和 J.-D. Zucker[16]对 k-近邻(k-nearest neighbor)算法进行了扩展,使其可以处 理多示例学习问题。他们不使用常用的欧氏距离而是使用修正的 Hausdorff 距离,这样就可以有效地 计算不同的包之间的距离。在此基础上,他们提出了两种算法,即 Bayesian-kNN 和 Citation-kNN。 前者使用 Bayes 理论来分析邻包,从而获得新包的概念标记。后者借用了科学文献“引用(citation) ” 的概念, 即在求新包的概念标记时, 不仅考虑其邻包, 还考虑将该新包作为邻包的包。 Wang 和 J.-D. J. Zucker 用麝香分子数据对这两个算法进行了测试,发现 Citation-kNN 略优于 Bayesian-kNN,且其效 果与 Iterated-discrim APR 算法相当接近。如前所述,Iterated-discrim APR 算法专门针对麝香分子数 据进行了优化,因此,该算法在处理别的问题时未必有如此优越的性能。而 J. Wang 和 J.-D. Zucker 提出的 Bayesian-kNN 和 Citation-kNN 是两种比较通用的算法,并没有专门针对该问题进行优化,这 两种算法取得如此好的效果说明,它们比 Iterated-discrim APR 算法有更好的应用前景。但值得注意 的是,虽然这两种算法在预测包的概念标记上性能相当优越,但其无法预测包中示例的概念标记, 而 DD 算法却可以做到这一点。此外,这些扩展的 k-近邻算法需要将整个训练集保存起来留待测试 时计算距离,因此虽然其几乎不需要训练时间开销,但存储开销和测试时间开销却非常大。 2000 年,G. Ruffo[17]对决策树算法 C4.5 进行了扩展,得到了多示例决策树 Relic。2001 年,Y. 他们用式 (6) Chevaleyre 和 J.-D. Zucker[18]对决策树算法 ID3 以及规则学习算法 RIPPER 进行了扩展。 定义的多示例熵函数代替 ID3 使用的标准熵函数,从而得到了多示例决策树算法 ID3-MI;用式(7) 定义的多示例覆盖函数代替 RIPPER 使用的标准覆盖函数,从而得到了多示例规则学习算法 RIPPER-MI。

Infomulti ( S ) = ?

? ? ? π (S ) ? v(S ) v(S ) log ? log ? ?? ? (6) π (S ) + v(S ) ? π (S ) + v(S ) ? π (S ) + v(S ) ? π (S ) + v(S ) ? ? ? ? ?

π (S )

Covermulti ( R, Bi ) ? ?j Cover ( R, Bij )

(7)

式(6)中π(S)和 v(S)分别表示示例集 S 覆盖的正包数和反包数。式(7)中 Cover(R, Bij)表示规 则集 R 覆盖了第 i 个包的第 j 个示例。 2002 年,Z.-H. Zhou 和 M.-L. Zhang[19]对常用的 BP 神经网络算法进行了扩展,他们用式(8) 定义的误差函数代替标准 BP 使用的误差函数,从而得到了多示例神经网络算法 BP-MIP。
N 1 E = ∑ ? max oij ? di ? ? 1≤ j ≤ M ? j ? i =1 2 ? 2

(8)

式(8)中 N 为训练包的数目,Mi 为第 i 个训练包中的示例数,oij 为网络在第 i 个训练包的第 j 个训练示例上的输出,di 为第 i 个训练包的期望输出。BP-MIP 算法的一个优点是它不仅可以处理多 示例分类问题, 还可以直接处理下文将要介绍的多示例回归问题。 此后, M.-L. Zhang 和 Z.-H. Zhou [20] 利用特征选择技术对 BP-MIP 算法进行了改进,提出了 BP-MIP-DD 算法和 BP-MIP-PCA 算法。 最近,S. Andrews 等人[21]和 T. G?rtner 等人[22]分别对支持向量机和核方法进行了扩展,使其可 用于多示例学习。Z.-H. Zhou 和 M.-L. Zhang[23]将集成学习(ensemble learning)技术引入到多示例学
6

习中,有效地提高了多种多示例学习方法的泛化能力,对 EM-DD 的集成在麝香分子数据上取得了 迄今为止最好的结果。 在提出多示例学习的概念时,T. G. Dietterich 等人[3]就指出,当前一个非常值得研究的课题是如 何对决策树、神经网络等常用的机器学习方法进行修正,使它们可以处理多示例学习任务。该问题 对多示例学习领域的发展起到了推动作用。经过过去几年的研究,常用的机器学习方法基本上都有 了对应的多示例学习版本,但遗憾的是,不同的学习方法在向多示例学习转化时并没有一个一般性 的方法或法则。最近,Z.-H. Zhou 和 M.-L. Zhang[23]指出,可以通过将学习方法的注意焦点从对示例 的区分转变到对包的区分,从而将监督学习方法转化为多示例学习方法。这个一般性的法则揭示了 多示例学习与监督学习之间的联系,为多示例学习算法的设计提供了一种通用的途径。从一定意义 上说,T. G. Dietterich 等人提出的 Open Problem 已经基本上得到了解决。

3.3 应用
O. Maron 等人对 DD 算法进行了一系列应用。 第一个应用是从序列图像中学习人的简单描述[14]。 在该应用中,O. Maron 和 T. Lozano-Pérez 将图像作为包,从图像中取样出的小图像块作为包中的示 例。对每幅图像来说,如果出现了某个人则对应的包被标记为正包,否则标记为反包。第二个应用 是股票选择[14],即从大量股票中挑选出由于自身的基本因素良好而上涨的绩优股。在该应用中,O. Maron 和 T. Lozano-Pérez 对一整年的股票数据进行分析,将每个月收益率最高的 100 只股票作为一 在该应用中, Maron O. 个正包, 收益率最低的 5 只股票作为一个反包。 第三个应用是自然场景分类[24]。 和 A. L. Ratan 将整幅自然场景图像作为一个包,从图像中取样出的小色块作为包中的示例,如果用 户对该图象中的某个部分(例如瀑布或山峦或田野等)感兴趣,则对应的包被标记为正包,否则标 记为反包。在该应用中,他们尝试了多种不同的为包生成示例的方法,发现不同的包生成方法对系 统的性能有显著影响。图 4 显示出了 O. Maron 和 A. L. Ratan 使用的 5 种包生成方法[24]。

图4

O. Maron 和 A. L. Ratan 使用的 5 种包生成方法

C. Yang 和 T. Lozano-Pérez[25]对 DD 算法进行了扩展,并将其用于基于内容的图像检索。他们先 将初始的颜色图像转变为灰度图像,然后从图像中选择出一些方差较大的区域,对每一区域,通过 左右对称变换产生两个子图像,再通过对子图像的平滑、采样得到特征向量,最后使用加权相关系 数的思想来度量距离。图 5 给出了他们的一个实验结果及对应的查准率-查全率曲线[25]。 由于包生成方法对图像检索性能有显著影响,Z.-H. Zhou 等人[26]对此进行了研究,他们在一种 基于 SOM 神经网络的图像分割方法[27]的基础上,提出了一种包生成方法。该方法将整幅图像作为 包,而将从图像中分割出的不同区域作为包中示例,并以该区域的颜色特征作为描述示例的属性。 他们的实验显示出该方法显著优于 C. Yang 和 T. Lozano-Pérez[25]的包生成方法,但却不如 O. Maron 。这一结果从一个侧面显示出了多示例 和 A. L. Ratan[24]的 SBN 方法(即图 4 中的 Blob with neighbs)

7

图5

C. Yang 和 T. Lozano-Pérez 的一个实验结果及对应的查准率-查全率曲线

学习的威力。因为与目前基于内容的图像检索领域所使用的相当复杂的特征抽取技术相比,SBN 是 一种非常简单的技术,但以此为基础竟然能取得相当好的检索结果。这说明多示例学习可以为基于 内容的图像检索提供一条新的、很有希望的途径。 最近,Z.-H. Zhou 等人[28]将多示例学习技术应用于 Web 目录页面推荐。用户在浏览 Internet 上 的信息时经常会遇到目录网页,这些网页仅提供标题或摘要,而把具体的内容放在其链接到的下级 网页中。例如各大门户网站都包含了大量的目录网页。由于目录网页包含大量的链接,难以要求用 户花费大量时间来指出其感兴趣的具体每个链接,只能请用户反馈该目录网页中“是”或“不是” 包含了其感兴趣的链接内容,因此,普通的网页推荐方法难以处理此种情况。Z.-H. Zhou 等人将目 录页面及其所有链接内容组成的整体视为包,而将具体的链接内容视为包中的示例,从而将该问题 转化为一个多示例学习问题。在此基础上,他们提出了 Fretcit-kNN 算法来解决这个问题。图 6 给出 了一个包及其示例的例子[28]。 多示例学习技术还被应用到机器人领域。为了正确地引导机器人在大范围环境中的移动,通常 需要准确实时地完成界标匹配(landmark matching) 。传统的做法是采用模式匹配方法,该方法由于 稳定性、容错性以及实时性较差,并且存储开销较大,因此具有一定的局限性。一种较好的做法是 使用基于学习的方法来代替模式匹配,在这种做法中,界标匹配问题被转化为对几何模式的学习问 题。S. A. Goldman 等人[29]从不可知论学习(agnostic learning)模型入手,提出了一种可用于多示例 学习的在线不可知论学习算法。该算法将几何模式的学习转化成对大量(指数级)布尔变量合取式 的学习, 主要用于对常数维几何模式的学习, 不仅可以容忍噪音, 还可以容忍概念偏移 (concept shift) 。 在此基础上,S. A. Goldman 和 S. D. Scott[30]又对该算法进行了扩展,使其可以处理实值几何模式。

8

图6

Z.-H. Zhou 等人在 Web 目录页面推荐中使用的包生成方法

此外,多示例学习还有其他一些应用。例如,G. M. Weiss 和 H. Hirsh[31]将事件预测(event prediction)转化为多示例学习问题,从而将一类时序数据分析问题在多示例学习框架下求解创造了 条件。G. Ruffo[17]将多示例学习技术应用于计算机安全领域例如口令检查、入侵检测、网络管理等。

3.4 扩展
在多示例学习研究的最初几年,研究者们主要关注的是输出为离散值的多示例分类问题。但正 如 T. G. Dietterich 等人[3]所指出的,在药物活性预测问题上,如果能得到实值表示的输出,就可以表 征出分子绑定的强弱,这对药物设计会有更大的帮助。最近几年,一些研究者开始关注输出为实值 寻找多示例回归问题的精确解是一个 NP 难问题, 的多示例回归问题。 Ray 和 D. Page[32]首先证明, S. 然后他们提出了一种基于 EM 算法的多示例回归算法。该算法先产生一个随机假设,然后从每个包 中挑选一个与当前假设误差最小的示例,再根据这些示例对假设进行调整,如此反复进行直到算法 收敛为止。几乎在同时,R. A. Amar 等人[33]对 Citation-kNN 算法和 DD 算法进行了扩展,使其可以 用于解决多示例回归问题。为了测试多示例回归算法的性能,R. A. Amar 等人[33]设计了一种人工生 成 多 示 例 回 归 数 据 集 的 方 法 , 而 且 他 们 生 成 的 数 据 集 可 以 从 http://www.cs.wustl.edu/~sg/ multi-inst-data/ 免费获得。 Y. Chevaleyre 和 J.-D. Zucker[18]认为,严格地来说,O. Maron 等人在图象理解[14]和自然场景分类
[24]

等方面的工作与药物活性预测问题并不相同。因为后者的示例实际上是对整个包的描述,对一个

包来说,在同一时刻只会出现一种描述,即同一个包中的不同示例是不会同时出现的;而前两者的 示例实际上是对包的部分的描述,对一个包来说,在同一时刻可能要出现所有的部分描述才能得到 完整的包的描述,即同一个包中的不同示例是会同时出现的。为了进行区分,Y. Chevaleyre 和 J.-D. Zucker[18]提出了多部分学习(multi-part learning)的概念,用来表征包中示例是对包的部分描述的情 况。值得注意的是,如果严格地按上述观点进行区分,则除了最初的药物活性预测问题之外,迄今 为止几乎所有的多示例学习应用实际上都是在解决多部分学习问题。但从学习的角度来看,多部分 学习问题完全可以通过多示例学习方法来解决[18],因此,目前机器学习界所使用的“多示例学习” 这个术语仍然同时包含了上述两个概念。
9

最近,N. Weidmann 等人[34]对多示例学习的概念进行了进一步扩展,提出了“广义多示例学习” (generalized multi-instance learning) 在标准的多示例学习中, 。 包的类别是由一个概念决定的, 例如, 当包中包含一个隶属于“适于制药的低能形状”概念的示例时,就是一个正包,否则就是反包。而 在广义多示例学习中,包的类别是由多个概念决定的,只有多个概念都得到满足,包才被标记为正。 具体来说,N. Weidmann 等人提出的广义多示例学习有三种形式。第一种是基于出现的多示例 学习(presence-based multi-instance learning) ,这里对每一个需要满足的概念,正包中都需要有对应 的示例出现。 标准的多示例学习其实是基于出现的多示例学习的特例 (当只有一个概念需要满足时) 。 第二种是基于阈值的多示例学习(threshold-based multi-instance learning) ,这里对每一个需要满足的 概念,正包中不仅需要有对应的示例出现,而且出现的次数需要超过一定的阈值。对不同的概念, 可以有不同的阈值。第三种是基于计数的多示例学习(count-based multi-instance learning) ,这里对 每一个需要满足的概念,正包中不仅需要有对应的示例出现,而且出现的次数需要在一定的范围内, 既不能太多,也不能太少。对不同的概念,可以有不同的计数范围。由于上述三种情况的约束越来 越强,因此 N. Weidmann 等人[34]认为,其学习难度也是逐渐加大。

4 讨论
在对多示例学习的研究中,T. G. Dietterich 等人[3]提出的 Open Problem,即设计常用机器学习方 法的多示例版本,极大地推动了该领域的发展。正是在该问题的刺激下,机器学习界近年来研制出 相当多的多示例学习算法。但如前所述,该问题现在基本已经得到了解决。因此,该领域迫切需要 有新的挑战性的 Open Problem 的出现,以推动其进一步发展。 基准测试数据对新算法的设计以及不同算法的比较起着重要作用。但遗憾的是,在多示例学习 领域,尤其是在对多示例分类的研究中,目前仅有一个基准测试数据集,即麝香分子数据(确切地 说,实际上是两个数据集,即 Musk1 和 Musk2) 。随着研究的深入,在该数据上学习算法的性能已 经趋于极限,很难再有所提高。表 2 给出了现有算法在麝香分子数据上的测试误差统计(各文献中 报道的最好结果) 。 迄今为止,多示例学习已经被应用到药物活性预测、图像检索等多个领域。但遗憾的是,除了 药物活性预测的麝香分子数据之外,其他应用中使用的数据都不是公开可得的。由于数据的收集往 往需要很大的代价,不公开数据是一种可以理解的做法,但这给相关研究工作的进行产生了障碍。 虽然一些研究者[33][34]提供了人造数据的生成技术,甚至公开了一些人造数据集,但与来自真实问题 的数据相比,人造数据的意义显然要小得多。值得庆幸的是,一些研究者[30]已经开始公开他们的真 实世界数据,相信这将有助于该领域的进一步发展。 随着研究的深入,该领域中出现了一些新的研究内容,例如多示例回归、广义多示例学习等。 但遗憾的是,到目前为止,相关研究工作都只是在理论上进行探讨,尚没有直接解决真实世界的问 题。为了显示或证明这些新的研究内容及其成果的价值,寻找示范性应用将是一个不容忽视的方面。 总的来说,多示例学习的研究迫切需要有新的推动力和测试基。而将现有的多示例学习技术付 诸应用,再从应用中寻找新问题,可能是一个较好的解决途径,因为这不仅可以带来新的挑战,还 有助于缓解测试数据缺乏的状况,并且有助于验证新的研究内容的实际价值。

10

表 2.
算法

在麝香分子数据上的测试误差统计(各文献报道的最好结果)
Musk1 %误差 3.1 3.2 5.2 7.2 7.6 7.6 7.6 8.2 8.7 9.8 9.8 10.9 11.1 12.0 16.3 16.3 23.3 25.0 31.5 算法 Ensemble EM-DD [23] EM-DD [15] Ensemble Iterated-discrim APR [23] MI Gaussian RBF kernel [22] Iterated-discrim APR [3] Ensemble Diverse Density [23] MI polynomial kernel [22] Relic [17] Ensemble Citation-kNN [23] Citation-kNN [16] MULTINST [2] Diverse Density [14] Bayesian-kNN [16] BP-MIP [19] GFS elim-kde APR [3] RIPPER-MI [18] GFS elim-count APR [3] BP [3] C4.5 [3] Musk2 %误差 3.0 4.0 6.9 7.8 10.8 11.0 11.8 12.7 12.9 13.7 16.0 17.5 17.6 19.6 19.6 23.0 24.5 32.3 41.2

Ensemble EM-DD [23] EM-DD [15] Ensemble Citation-kNN [23] Ensemble Iterated-discrim APR [23] Iterated-discrim APR [3] Citation-kNN [16] MI polynomial kernel [22] Ensemble Diverse Density [23] GFS elim-kde APR [3] GFS elim-count APR [3] Bayesian-kNN [16] MI Gaussian RBF kernel [22] Diverse Density [14] RIPPER-MI [18] BP-MIP [19] Relic [17] MULTINST [12] BP [3] C4.5 [3]

参 考 文 献
Mitchell T M. Machine Learning, New York: McGraw-Hill, 1997. Maron O. Learning from ambiguity. PhD dissertation, Department of Electrical Engineering and Computer Science, MIT, Jun. 1998. 3 Dietterich T G, Lathrop R H, Lozano-Pérez T. Solving the multiple-instance problem with axis-parallel rectangles. Artificial Intelligence, 1997, 89(1-2): 31-71. 4 Friedman J H, Stuetzle W. Projection pursuit regression. Journal of the American Statistical Association, 1981, 76(376): 817-823. 5 Lindsay R, Buchanan B, Feigenbaum E, Lederberg J. Applications of Artificial Intelligence to Organic Chemistry: The Dendral Project, New York, NY: McGraw-Hill, 1980. 6 Zucker J-D, Ganascia J-G. Changes of representation for efficient learning in structural domains. In: Proceedings of the 13th International Conference on Machine Learning, Bary, Italy, 1996, 543-551. 7 Muggleton S H. Inductive logic programming. New Generation Computing, 1991, 8(4): 295-318. 8 De Raedt L. Attribute-value learning versus inductive logic programming: the missing links. In: Proceedings of the 8th International Conference on Inductive Logic Programming (LNAI 1446), Madison, WI, 1998, 1-8. 9 Long P M, Tan L. PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Machine Learning, 1998, 30(1): 7-21. 10 Valiant L G. A theory of the learnable. Communications of the ACM, 1984, 27(11): 1134-1142. 11 Auer P, Long P M, Srinivasan A. Approximating hyper-rectangles: learning and pseudo-random sets. Journal of Computer and System Sciences, 1998, 57(3): 376-388. 12 Auer P. On learning from multi-instance examples: empirical evaluation of a theoretical approach. In: Proceedings of the 14th International Conference on Machine Learning, Nashville, TN, 1997, 21-29. 1 2
11

13 Blum A, Kalai A. A note on learning from multiple-instance examples. Machine Learning, 1998, 30(1): 23-29. 14 Maron O, Lozano-Pérez T. A framework for multiple-instance learning. In: Jordan M I, Kearns M J, Solla S A eds. Advances in Neural Information Processing Systems 10, Cambridge, MA: MIT Press, 1998, 570-576. 15 Zhang Q, Goldman S A. EM-DD: an improved multiple-instance learning technique. In: Dietterich T G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems 14, Cambridge, CA: MIT Press, 2002, 1073-1080. 16 Wang J, Zucker J-D. Solving the multiple-instance problem: a lazy learning approach. In: Proceedings of the 17th International Conference on Machine Learning, San Francisco, CA, 2000, 1119-1125. 17 Ruffo G. Learning single and multiple instance decision trees for computer security applications. PhD dissertation, Department of Computer Science, University of Turin, Torino, Italy, Feb. 2000. 18 Chevaleyre Y, Zucker J-D. Solving multiple-instance and multiple-part learning problems with decision trees and decision rules. Application to the mutagenesis problem. In: Proceedings of the 14th Biennial Conference of the Canadian Society for Computational Studies of Intelligence (LNAI 2056), Ottawa, Canada, 2001, 204-214. 19 Zhou Z-H, Zhang M-L. Neural networks for multi-instance learning. Technical Report, AI Lab, CS Dept., Nanjing Univ., Aug. 2002. 20 Zhang M-L, Zhou Z-H. Improve multi-instance neural networks through feature selection. Neural Processing Letters, 2004, 19(1): 1-10. 21 Andrews S, Hofmann T, Tsochantaridis I. Multiple instance learning with generalized support vector machines. In: Proceedings of the 18th National Conference on Artificial Intelligence, Edmonton, Canada, 2002, 943-944. 22 G?rtner T, Flach P A, Kowalczyk A, Smola A J. Multi-instance kernels. In: Proceedings of the 19th International Conference on Machine Learning, Sydney, Australia, 2002, 179-186. 23 Zhou Z-H, Zhang M-L. Ensembles of multi-instance learners. In: Proceedings of the 14th European Conference on Machine Learning (LNAI 2837), Cavtat-Dubrovnik, Croatia, 2003, 492-502. 24 Maron O, Ratan A L. Multiple-instance learning for natural scene classification. In: Proceedings of the 15th International Conference on Machine Learning, Madison, WI, 1998, 341-349. 25 Yang C, Lozano-Pérez T. Image database retrieval with multiple-instance learning techniques. In: Proceedings of the 16th International Conference on Data Engineering, San Diego, CA, 2000, 233-243. 26 Zhou Z-H, Zhang M-L, Chen K-J. A novel bag generator for image database retrieval with multi-instance learning techniques. In: Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, Sacramento, CA, 2003, 565-569. 27 Jiang Y, Chen K-J, Zhou Z-H. SOM-based image segmentation. In: Proceedings of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (LNAI 2639), Chongqing, China, 2003, 640-643. 28 Zhou Z-H, Jiang K, Li M. Multi-instance learning based web mining. Applied Intelligence, 2005, 22(2): 135-147. 29 Goldman S A, Kwek S S, Scott S D. Agnostic learning of geometric patterns. Journal of Computer and System Sciences, 2001, 62(1): 123-151. 30 Goldman S A, Scott S D. Multiple-instance learning of real-valued geometric patterns. Technical Report UNL-CSE-99-006, Department of Computer Science and Engineering, University of Nebraska, Lincon, NE, 2000. 31 Weiss G M, Hirsh H. Event prediction: learning from ambiguous examples. In: Working Notes of the NIPS-98 Workshop on Learning from Ambiguous and Complex Examples, Breckenridge, CO, 1998. 32 Ray S, Page D. Multiple instance regression. In: Proceedings of the 18th International Conference on
12

Machine Learning, Williamstown, MA, 2001, 425-432. 33 Amar R A, Dooly D R, Goldman S A, Zhang Q. Multiple-instance learning of real-valued data. In: Proceedings of the 18th International Conference on Machine Learning, Williamstown, MA, 2001, 3-10. 34 Weidmann N, Frank E, Pfahringer B. A two-level learning method for generalized multi-instance problems. In: Proceedings of the 14th European Conference on Machine Learning (LNAI 2837), Cavtat-Dubrovnik, Croatia, 2003, 468-479.

13


更多相关文档:

MIL 标准 2010.pdf

MIL 标准 2010 - MIL 美国军用标准标准 2010 年最新标准目录 以下 MIL 美国标准化组织标准信息只供参考,具体情况,请咨询--中国标准信息网 MIL-PRF-22684/...

美国空军有人驾驶飞机飞行品质规范MIL-F-8785C_图文.pdf

美国空军有人驾驶飞机飞行品质规范MIL-F-8785C_兵器/核科学_工程科技_专业资料。美国空军军标美国空军有人驾驶飞机飞行品质规范MIL-F-8785C ...

MIL-STD-202G Method 310(中文版).doc

MIL-STD-202G Method 310(中文版)_电子/电路_工程科技_专业资料。MIL-STD-202G Method 310(中文版) MIL-STD-202G METHOD 310 CONTACT-CHATTER MONITORING 接...

mil-std-1916抽样标准(中文版).doc

MIL-STD-1916 抽样标准简介一、 前言 为强调过程品管与持续不断改进的重要性,美军于 1996 年推出新版的抽样标准: MIL-STD-1916,用以取代 MIL-STD-105E 作为...

毫米mil转换表.xls

毫米mil转换表_电子/电路_工程科技_专业资料。毫米 to ML 0.1 3.

MIL-A-8625中文版_图文.pdf

MIL-A-8625中文版_材料科学_工程科技_专业资料。好东西 您的评论 发布评论 用户评价 太感谢了,MIL-A-8625中文版 2018-06-27 06:15:01 ...

MIL-STD-810G标准解析与试验机构.doc

MIL-STD-810G标准解析与试验机构 - 广电计量环境可靠性与电磁兼容试验中心 http://www.kkxtest.org 什么是 MIL-STD-810G MIL-STD-810,...

PCB常用mil-mm对照表.xls

PCB常用mil-mm对照表_电子/电路_工程科技_专业资料。ALtium PCB中常用尺寸 mil 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 mm 0.025...

MIL.doc

1.MIL 编程环境设置 MIL 全称为 Matrox Imaging Library,由加拿大 Matrox 公司开发;MIL 软件包是一个 独立于硬件的、含有多个标准模块或组件的 32 位图像库,...

Cognex与Mil对比.doc

Cognex与Mil对比 - Cognex 和 Mil 的对比 1. 概述 1.1. Mil Mil 是 Matrox 公司开发的高层图像处理软件开发包, 是一个图像采集、 传输、 处理、 分...

美国常用军用标准 MIL-STD.txt

美国常用军用标准 MIL-STD_军事/政治_人文社科_专业资料。美国常用军用标准 MIL-STD 分类: 美军 | 标签:美军标 MIL-STD-469-1966 雷达工程电磁兼容*设计要求 ...

PCB设计单位mil.txt

PCB设计单位mil - mil: n.千分之一寸 〔计〕密耳(=0.001英寸,线径单位文字) 1mil=1/1000inch=0.00254cm=0.0254mm ...

MIL的使用.doc

MIL的使用 - MIL 即为 Matrox Imaging Library 的

MIL-PRF-13830B中文版.pdf

MIL-PRF-13830B中文版_机械/仪表_工程科技_专业资料。MIL-PRF-13830B中文版 美国军用标准 MIL-PRF-13830B 性能标准 光学元件用于军火控制设备;监控生产制造、装配...

毫米与Mil的转换.doc

毫米与Mil的转换 - 1、n.千分之一英寸 〔计〕密耳(=0.001英寸,线径单位文字) 1mil=1/1000inch=0.00254cm=0.0254mm 1inch=1000mil=2...

MIL8.0.pdf

MIL8.0 - 主要特点 图像采集, 显示和存档的编程库完整、 易用 TM 全

MIL-A-8625 中文版.pdf

MIL-A-8625 中文版 - 铝阳极氧化 MIL-A-8625F 标准中文版 铝阳极氧化 MIL-A-8625F 标准中文版 美国军事标准 铝和铝合金的阳极氧化膜 此标准由由美国国防部...

mil单位转mm.doc

mil单位转mm - 1mil=0.0254mm 2mil=0.0508mm 3mil=0.0762mm 4mil=0.1016mm 5mil=0.127mm 6mil=0.1524mm 7mi...

mil-std-1916(中文版).doc

mil-std-1916(中文版)_信息与通信_工程科技_专业资料。抽样标准 MIL-STD-1916 抽样标准简介一、 前言 为强调过程品管与持续不断改进的重要性,美军于 1996 年...

mm-mil换算.doc

mm-mil换算 - mm?mil 换算 mm 1 2 3 4 5 6 7 8 9 10 mil 39.74 78.74 118.11 157.48 196.85 236.22 275.59 3...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com