双层多示例集成学习

袁汉宁

(武汉理工大学经济学院，湖北 武汉 430070)

在多示例学习(multiple instance learning，MIL)中，训练集由具有概念标记的包组成，包是若干示例的集合，如果包被标记为正，则包中至少有一个示例为正;如果包被标记为负，这个包中所有的示例都为负。多示例学习中存在的最大挑战在于虽然包的概念标记是已知的，但正包中的示例的概念标记是模糊的，不能将包的标记直接传递给包中的示例。其学习任务是通过对训练集中有标记包的学习，建立和优化目标概念模型，对未标记的包或示例分类或预测。

传统多示例集成(traditional multiple instance ensemble，TMIE)学习是在包层次上实施重抽样建立多个训练集，然后使用训练集生成集成个体。集成个体间的差异是提高集成学习性能的重要因素。在多示例集成学习中集成个体间的差异是通过训练数据的随机性和独立性提供的，TMIE只是在包层次上实现数据的重抽样，整个数据集合没有得到充分的搅动，限制了集成个体间的差异性，影响了集成学习性能。针对这种情况，笔者设计了包内示例的重抽样方法并提出了一种双层多示例集成(double multiple instance ensemble，DMIE)学习框架，该框架实现了包层次上和示例层次的重抽样，充分搅动训练数据，增强集成个体间的差异性，能更有效地提高分类器的分类精度。

1 多示例集成学习

多示例学习最先由DIETTERICH［1］等在药物活性预测中提出，是一类特殊的机器学习任务。目前多示例学习的研究内容主要包括:①基于监督学习的多示例学习算法。该类方法主要思想是将多示例学习转化成监督学习，如ANDREWS提出的支持向量机的mi-SVM算法和MI-SVM算法［2］，WANG 等提出的基于距离的 Bayesian-KNN和Citation-KNN算法［3］。②基于非监督学习的多示例学习算法，如ZHOU等提出的多示例学习的聚类算法Bamic［4］。③基于半监督学习和主动学习的多示例学习算法，该类算法是针对标记样本稀疏和标记代价昂贵的情况，利用未标记数据的学习算法。如RAHMANI等提出的MISSL(multiple instance semi-supervised learning)算法［5］;ZHOU 提出的 MissSVM(multiple instance learning by semi-supervised support vector machine)算法［6］。

由于其独特的性质，多示例学习在国际机器学习界引起了极大的反响，被认为是一种新的学习框架，其具体应用包括基于内容的图像检索，遥感图像检索、股票预测、药物活性研究、自然场景分类、Web目录页面推荐和计算机安全领域，如口令检查、入侵检测和网络管理等［7］。

与传统的分类器相似，大部分多示例学习的分类器受数据驱动且不稳定。集成学习是一种能有效提高不稳定的分类器分类精度的方法［8］。在传统的多示例集成学习TMIE［9］中，包被看作独立的样本，对训练集有放回地抽取训练样本，为每一个基本分类器都构造出一个与训练集同样大小但各不相同的训练集，通过抽样得到的训练集对基本分类器进行训练，得到不同的集成个体，再通过投票对集成个体的学习结果进行整合。TMIE在包层次上实现数据的重抽样，一旦包被选中，包中的所有示例就会全被选中，因而降低了训练集之间的差异性。如果想获得差异性最大的训练集集合，就要在示例层次上实现重抽样。因为重抽样后正包中的示例可能全部为负示例，因此直接简单地在所有示例上实现重抽样可能会破坏包的性质，导致正包的标记与内容矛盾。在设计示例层次上的重抽样算法时必须考虑保持正包的性质不变。

2 双层多示例集成学习方法

2.1 示例层次上的重抽样

在双层多示例集成学习中，样本重抽样是通过包层次和示例层次上的重抽样实现的。在包层次上的重抽样中，每个包作为独立的样本被抽取而在示例层次重抽样中，包中每个示例被作为独立的样本被抽取。实现示例层次重抽样的关键在于保证抽样后的包的性质不变。对于负包，在包中示例上实施重抽样不会改变包的性质。对于正包，因为包中示例的标记是模糊的，实施重抽样后不能保证抽样后的正包中至少有一个正示例，甚至会碰到最坏的情况，即正包中的所有正示例都没有被抽中，抽样后的正包中的示例全部是负示例，这样就导致了包的性质改变。因此，为了保证正包的性质，示例层次重抽样必须保证抽样后的正包中至少有一个正示例。多示例学习的特性决定了正包中示例的概念标记是模糊的，因此找到每个正包中的一个正示例是实现示例层次上重抽样的关键。

LI提出的Disambiguation方法［10］可以找到每个正包中最可能为正的示例t。定义多示例学习中的包为Bi，l(Bi)为该包的标记(+1为正包，-1表示负包)，Bi中的第k个示例为bik，给定一个有P个正包和N个负包的训练集T，Disambiguation方法中定义示例t为正的概率为:

包中最可能为正的示例是具有最大概率的示例:

θt的候选项集合为N}。P*(t)反映的是示例t区分训练集中包的能力，P*(t)的值越大，t为正示例的可能性就越大，每个包中最可能为正的示例就是P*(t)值最大的示例。LI通过Disambiguation方法找到所有包中最可能为正的示例t，用该示例代表所在的包，再使用传统的分类方法如支持向量机分类。笔者借鉴Disambiguation方法识别每个正包中最可能为正的示例，通过在正包示例层次上的重抽样中保留包中该示例，保持示例层次上重抽样后的正包性质不变，实现多示例集成学习中示例层次上的重抽样算法。

示例层次重抽样算法如下:

输入:有 M 个包的训练集 T={B1，B2，B3，…，BM}

for i←1到M do

m:包Bi中示例的个数

if包Bi的标记为正then

else

end if

end for

输出:抽样后的训练集 T={B'1，B'2，…B'M}

在示例层次重抽样算法中，对于正包，先采用Disambiguation方法找到每个正包中最可能为正的示例P*(t)，对正包中的示例实施重抽样后，在抽样得到的新包中加入最可能为正的示例P*(t)，就保证了抽样后得到的新包中至少有一个正示例，从而保证了新包的概念标记不变。对于负包，因为包中的示例标记都为负，可以直接实施重抽样。

在示例层次上实施重抽样的算法如上所述。设正包Bi中有m个示例，找到包Bi中最可能为正的示例t后，在包中实施m-1次有放回的抽样，得到含有m-1个示例的新包B'i，最后将示例t加入到新包中，这样抽样后的新包中至少保存了一个正示例从而保证了抽样后包的性质不变。

2.2 双层多示例集成学习框架

DMIE学习框架由包层次的重抽样和示例层次的重抽样组成，双层多示例集成学习框架如下:

输入包含M 个包的训练集T={B1，B2，B3，…，BM}

多示例基本分类器L，包层次上的重抽样次数I和示例层次上的重抽样次数J，未标记的包Bx

for i←1到I do

Ti←对T实施包层次上的重抽样for j←1到J do

return标记包Bx为yx

第一阶段实施包层次上的重抽样，即将训练集T中的每个包作为独立的样本，实施I次包层次上的重抽样得到一组Bootstrap集合T1，T2，…，TI，其中Ti拥有与训练集T相同的包的数目。第二阶段实施示例层次上的重抽样，即将包中的示例看作独立的样本，对每个Ti实施J次包层次上的重抽样。在第j(j≤J)次重抽样中，训练集Ti每个包中的示例被抽样并组成新包，所有抽样后得到的新包组成新的训练集。通过训练集对基本分类器训练得到分类器Lji。

DMIE在包层次和示例层次上实施了两种重抽样，每种重抽样都对应一次集成，因此DMIE包含了两种层次的集成。首先对由Ti实施J次包层次上的重抽样训练得到的分类器通过投票整合得到分类器Li，然后再对分类器Li的学习结果投票整合得到最终的分类器L。

3 实验

3.1 实验设置

为了分析DMIE学习框架的学习性能，笔者用Java和WEKA机器学习软件实现了DMIE和TMIE，并将DMIE与传统的多示例集成学习方法TMIE及单个多示例学习方法(single multiple instance learning，SMI)进行了比较。实验选取WEKA机器学习软件中的CKNN(citation-k nearest neighbors)、MIOptimalBall、MINND(multiple instance n nearest distance distribution)、MIDD(multiple instance diversity density)和MISVM(multiple instance support vector machine)5种方法作为SMI、TMIE和DMIE方法的基本分类器，对多示例学习中的 5 个典型数据集 musk1，musk2，tiger，fox和elephant采用了十折交叉验证。实验中基本分类器的参数均使用WEKA机器学习软件中的默认参数，包层次重抽样和示例层次重抽样的次数均设置为10。3种方法分类准确率的比较结果如表1所示，其中准确率最高的结果用黑体表示。

表1 不同方法的分类精度比较

3.2 实验结果及分析

对SMI、TMIE和DMIE的实验结果进行Win/lose/tie分析，分析结果如表2所示。

表2 Win/lose/tie分析结果

通过3种方法在5个数据集上分类准确率的比较分析，发现与SMI和TMIE相比，DMIE具有更高的学习精度，能有效地提高多示例分类学习的精度。如SMI在数据集elephant上的学习精度为69%，DMIE则在SMI的基础上将学习精度提高了10%左右。甚至对一些稳定的分类器，如SVM和CKNN，DMIE也能较好地提高分类学习的精度。这可能是因为在多示例学习中包的标记限制了该类分类器的稳定性，使该类稳定的分类方法变得相对不稳定。

4 结论

笔者提出了一种能有效提高分类精度的双层多示例集成学习方法。识别包中最可能为正的示例保留该示例实现包中示例层次上的重抽样。通过包层次和示例层次的双层重抽样充分搅动训练集，增强了集成个体的差异性。实验结果证明，该方法与单个的多示例学习方法和传统的多示例集成方法相比，能更有效地提高多示例学习分类器的学习精度。

［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-2):31-71.

［2］ANDREWS S，HOFMANN T，TSOCHANTARIDIS I.Multiple instance learning with generalized support vector machines［C］//IEEE National Conference on Artificial Intelligence.Edmonton:［s.n.］，2002:943-944.

［3］WANG J，ZUCKER J D.Solving the multiple instance problem:a lazy learning approach［C］//IEEE the 17th International Conference on Machine Learning.San Francisco:［s.n.］，2000:1119-1125.

［4］ZHOU Z H，SUN Y Y，LI Y F.Multi-instance learning by treating instances as non-I.I.D.samples［C］//IEEE Proceedings of the 26th International Conference on Machine Learning.Canada:［s.n.］，2009:1249-1256.

［5］RAHMANI R，GOLDMAN S A.Missl:multiple instance semi-supervised learning［C］//IEEE the 23rd International Conference on Machine Learning.Pittsburgh:［s.n.］，2006:705-712.

［6］ZHOU Z H，XU J M.On the relation between multiinstance learning and semi-supervised learning［C］//IEEE the 24th International Conference on Machine Learning.Corvalis:［s.n.］，2007:1167-1174.

［7］ZHOU Z H.Multi-instance learning from supervised view［J］.Journal of Computer Science and Technology，2006，21(5):800-809.

［8］ZHOU Z H，YU Y.Ensembling local learners through multimodal perturbation［J］.IEEE Transactions on Systems，2005，35(4):725-735.

［9］ZHOU Z H，ZHANG M L.Ensembles of multi-instance learners［C］//The 14th European Conference on Machine Learning.Croatia:［s.n.］.2003:492-502.

［10］LI W J.MILD:Multiple instance learning via disambiguation［J］.IEEE Transactions on Knowledge and Data Engineering，2010，22(1):76-89.