数学执本与用
几种多示例学习算法研究分析
杨雪洁赵凯
(合肥师范学院公共计算机教学部安徽合肥230601)
算法分析
摘要：多示例学寸与传统机器学习有很大不同,多示例学习中一个样本包中有多个示例样本包有类别而示例没有类别标记易于一对多的学习柜架。本文介绍了多示例学习提出背景及基本特点,从包层次和示例层次两方面分析比较了几种具有代表性的多示例学习算法,最后展望了多示例学习算法的进一步研究方向。
关键词：多示例学习机器学习BP算法KNN算法中图分类号：TP391.41
文献标识码:A
1引言
T.G.Dietterich等人在研究药物活性预测时提出了多示例学习的概念川。该问题是通过机器学习方法对样本分子(已标记适合制药及不适合制药进行学习，从而尽可能正确预测某些新分子是否适合制药。研究人员因技术原因只知道哪此分子适合制药，面对于该分子中哪一种具体形状适合制药并不清楚，因为一个药物分子可能有多种可能的形状(同分异构体),要有一个形状起作用，则这个分子就适于制药，若该分子所有示例都不适合制药，该分子才不适合制药，该问题提出了样本和示例一对多的学习框架，在该框架中若按监督学习直接以分子为对象进行学习,将所有适合制药的分子作为正例学习，会出现由于正例中噪声太高面难以学习，因为正例中也会有大量不适合制药的形状，所以该问题提出了一种新的学习方式一多示例学习。
2多示例学习
多示例学习中的训练示例没有被标记类别，监督学习中所有训练样本都有具体类别；多示例学习中训练分子(包)是有具体类别，非监督学习的训练样本都没有类别标记。在监督、非监督学习中，一个样本就是一个示例，不可以再次分割，一个样本只能属于一个具体的类别，即样本和示例是一一对应关系，面多示例学习，一个样本(即包)中有多个示例，训练集由若干个有类别的包组成，其中每个包包含一些没有类别的示例。若一个包中至少存在一个正示例，则该包被标记为正包；一个包中不含有任何正例，则该包为反包。学习系统通过对已经标定类别的包进行学习来建立模型，希望尽可能正确地预测训练集以外的包的类别标记[]。机器学习算法目标是要找出 unkownDrocess的最佳逼近方法，传统监督、非监督学习描述见
Bag
Bag
收移日期：2016-05-13
unkown process 图1传统学习描述
instance instance instance
Result
文章编号：1007-9416(2016)08-0151-01 图1，多示例学习问题描述见图2。
多示例学习的提出拓宽了机器学习解决问愿的领域，该问题在现实生活中可以找到很多原型，例如基于内容的图像检索、文本分类、视频内容检测、计算机安全预测等。国内外研究人员提出了多种多示例学习算法，大致可以分为两类，从具体示例角度的示例层次
算法和从包层次分析的包层次算法， 3示例层次算法
示例层次算法早期具有代表性的是T.G.Dietterich等人提出的三个轴一平行矩形(APR)算法。他们将一个分子看成一个包.该分子的不同形状作为包中的不同示例，为表示这些示例，将该分子固定在坐标原点，从原点放射出多条射线，射线与分子的交点到坐标原点的距离作为一个属性，再加上分子中氧原子位置属性，包中的每个示例可以用上述属性值来描述。APR算法基本思想是找出覆盖所有正包示例的轴平行矩形，再通过贪心算法逐步排除反包中的反示例以缩小矩形，最终找到一个最小矩形确定多示例数据集中上限和下限，从而将所有不在矩形内的样本排除，最终落在矩形中的样本即为正例。三种APR算法中预测效果较好的是Iterated-discrim APR算法，由于APR算法都是基于矩形的，对于解决离香分子问题效果较好，难以直接用于解决实际的多示例学习问题，不具有较好的通用性。
另一种有代表性的方法是基于概率的多样性密度(简称DD)算法。DD算法中每个包的示例是一个n维空间的向量，对应空间中的个点，空间中存在某个区域，满足每个正包中至少有一个示例在该区域内或者距离足够近，所有来自反包的示例到该区域的距离足够远。为找到该区域，Maron用多样性密度来衡量空间中的每个点。个点周图的正包数越多，反包示例越远，则该点多样性密度越大，空间中多样性密度最大的点被认为是目标区域。算法采用noisy-or 模型和梯度下降法来寻找多样性密度最大的点，将全部正包中的示例都作为候选的目标，进行一次全局搜索以避免局部最优解。该算
unkownprocess
图2多示例学习描述
.下转第154页
基金项目：合肥师范学院校级科研项目，编号：2012kj05;安微省高校优秀青年人才基金重点项目，编号：2013SQRL063ZD。作者简介：杨雪洁(1982一),女,安徽果湖人,颈士,讲师研究方向：驾能计算与机器学习
54
万方数据