几种多示例学习算法研究分析

杨雪洁　赵凯

摘要：多示例学习与传统机器学习有很大不同，多示例学习中一个样本包中有多个示例，样本包有类别，而示例没有类别标记，属于一对多的学习框架。本文介绍了多示例学习提出背景及基本特点，从包层次和示例层次两方面分析比较了几种具有代表性的多示例学习算法，最后展望了多示例学习算法的进一步研究方向。

关键词：多示例学习 机器学习 BP算法 KNN算法

中图分类号：TP391.41 文献标识码：A 文章编号：1007-9416（2016）08-0151-01

1 引言

T.G.Dietterich等人在研究药物活性预测时提出了多示例学习的概念[1]。该问题是通过机器学习方法对样本分子（已标记适合制药及不适合制药）进行学习，从而尽可能正确预测某些新分子是否适合制药。研究人员因技术原因只知道哪些分子适合制药，而对于该分子中哪一种具体形状适合制药并不清楚，因为一个药物分子可能有多种可能的形状（同分异构体），要有一个形状起作用，则这个分子就适于制药，若该分子所有示例都不适合制药，该分子才不适合制药，该问题提出了样本和示例一对多的学习框架，在该框架中若按监督学习直接以分子为对象进行学习，将所有适合制药的分子作为正例学习，会出现由于正例中噪声太高而难以学习，因为正例中也会有大量不适合制药的形状，所以该问题提出了一种新的学习方式—多示例学习。

2 多示例学习

多示例学习中的训练示例没有被标记类别，监督学习中所有训练样本都有具体类别；多示例学习中训练分子（包）是有具体类别，非监督学习的训练样本都没有类别标记。在监督、非监督学习中，一个样本就是一个示例，不可以再次分割，一个样本只能属于一个具体的类别，即样本和示例是一一对应关系，而多示例学习，一个样本（即包）中有多个示例，训练集由若干个有类别的包组成，其中每个包包含一些没有类别的示例。若一个包中至少存在一个正示例，则该包被标记为正包；一个包中不含有任何正例，则该包为反包。学习系统通过对已经标定类别的包进行学习来建立模型，希望尽可能正确地预测训练集以外的包的类别标记[2]。机器学习算法目标是要找出unkown process 的最佳逼近方法，传统监督、非监督学习描述见图1，多示例学习问题描述见图2。

多示例学习的提出拓宽了机器学习解决问题的领域，该问题在现实生活中可以找到很多原型，例如基于内容的图像检索、文本分类、视频内容检测、计算机安全预测等。国内外研究人员提出了多种多示例学习算法，大致可以分为两类，从具体示例角度的示例层次算法和从包层次分析的包层次算法。

3 示例层次算法

示例层次算法早期具有代表性的是T.G.Dietterich等人提出的三个轴-平行矩形（APR）算法。他们将一个分子看成一个包，该分子的不同形状作为包中的不同示例，为表示这些示例，将该分子固定在坐标原点，从原点放射出多条射线，射线与分子的交点到坐标原点的距离作为一个属性，再加上分子中氧原子位置属性，包中的每个示例可以用上述属性值来描述。APR算法基本思想是找出覆盖所有正包示例的轴平行矩形，再通过贪心算法逐步排除反包中的反示例以缩小矩形，最终找到一个最小矩形确定多示例数据集中上限和下限，从而将所有不在矩形内的样本排除，最终落在矩形中的样本即为正例。三种APR算法中预测效果较好的是Iterated-discrim APR算法，由于APR算法都是基于矩形的，对于解决麝香分子问题效果较好，难以直接用于解决实际的多示例学习问题，不具有较好的通用性。

另一种有代表性的方法是基于概率的多样性密度（简称DD）算法。DD算法中每个包的示例是一个n维空间的向量，对应空间中的一个点，空间中存在某个区域，满足每个正包中至少有一个示例在该区域内或者距离足够近，所有来自反包的示例到该区域的距离足够远。为找到该区域， Maron用多样性密度来衡量空间中的每个点。一个点周围的正包数越多，反包示例越远，则该点多样性密度越大，空间中多样性密度最大的点被认为是目标区域。算法采用noisy-or模型和梯度下降法来寻找多样性密度最大的点，将全部正包中的示例都作为候选的目标，进行一次全局搜索以避免局部最优解。该算法在麝香分子上测试效果虽然不如Iterated-discrim APR算法，但可以应用于其他方面，如股票选择、基于内容的图像检索等。

由于需要多次使用梯度下降搜索目标示例，DD算法训练时间花费较大，研究人员又提出了EM-DD算法，该算法在EM算法的E步从训练集的每个示例包中选出决定各包类别的训练示例，再在M步选出的示例中使用多样性密度算法以最大化多样性密度，反复进行E步和M步直至算法收敛，该算法在麝香分子数据集预测精度一度是最高的，与DD算法相比缩短了不少时间，但由于该方法是不断迭代的过程，比较容易陷入局部最优。

4 包层次算法

上述方法都是基于包中的每一个示例学习的，为更好的将传统机器学习方法修正后处理多示例学习任务，研究人员开始从包层次来设计算法，例如基于KNN、基于BP、基于SVM的多示例学习算法。

KNN算法用样本间的距离来度量样本间的相似度，基于K-NN的多示例学习算法使用修改的Hausdorff 距离，这样就可以有效地计算不同的包之间的距离。在此基础上，他们提出了两种算法，即Bayesian-kNN 和Citation-kNN。前者使用Bayes 理论来分析邻包，从而获得新包的标记。后者不仅考虑其邻包，还考虑将该新包作为邻包的包。这两种算法在麝香分子测试时，Citation-kNN效果与Iterated-discrim APR算法接近，略优于Bayesian-kNN，K-NN多示例学习算法未针对麝香分子进行优化，因而有更广泛的应用场合，但这两种算法只能预测包的类别，无法预测包中示例的类别，这点上无法与DD算法相比。同时两种算法需要将训练样本全部保存，存储空间较大，预测分类时需遍历所有样本空间，时间花费较大。

基于BP的多示例学习算法[10]是对神经网络中BP算法进行改造，通过改造传统BP误差函数，得到多示例下的学习算法，该误差函数是在包层次上定义，包的实值输出是由包中示例的最大实值输出所决定。

基于SVM的多示例算法将在输入数据的特征空间找到一个超平面，此超平面使训练数据之间的不同类样本的间距最大，在包层次中将最大分类间隔为包间隔，对于反包，由于反包中所有示例都是反示例，因此包之间的间隔与监督学习方式一致，对于正包，将包之间的最大间隔定义为分类超平面和正包中所有示例间距离的最大值。该方法试图寻找每个正包的正示例，适合处理小样本数据集，但该方法忽略了正包中的反示例。

5 结语

随着多示例学习算法的不断优化，可以考虑将专门的多示例算法和已扩展为多示例学习的原监督学习算法结合使用解决问题，如利用集成学习方法，先通过已有机器学习算法重新组织数据集，将包抽象为空间的点，找到正包中正示例（或者排除正包中大量的反例），然后利用选出的示例将多示例学习转为监督学习，这也是下一步努力的方向。

参考文献

[1]Dietterich T G，Lathrop R H，Lozano-Pérez T. Solving the multiple instance problem with axis-parallel rectangles[J].Artificial Intelligence，1997，89（1）：31-71.

[2]周志华.多示例学习[J].知识科学中的基本问题研究.北京：清华大学出版社，2006：322-336.

[3]蔡自兴，李枚毅.多示例学习及其研究现状[J].控制与决策，2004，19（6）：607-611.