多示例学习研究---Home---LAMDA

多示例学习研究武岩松*(南京大学计算机科学与技术系,南京210093)Multiple-InstanceLearning:ASurveyYan-SongWu(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:Multiple-instancelearningisavariationonsupervisedlearning.Itiscategorizedasthefourthlearningframeworkbesidessupervisedlearning,unsupervisedlearningandenforcementlearningbecauseofitsuniqueproperties.Inmulti-instancelearning,thetrainingsetcompriseslabeledbagsthatarecomposedofunlabeledinstances,andthetaskistopredictthelabelsofunseenbags.Thispaperprovidesasurveyonthistopic.ThepaperfirstlyintroducesthebackgroundofMILandthehistoryofMILlearning.ThenthispaperwillintroducefourpopularMIL-learningalgorithmsseparatelywhichareDiverseDensity,Citation-kNN,BP-MIPandRBF-MIP.Empiricalexperienceswillbedoneandresultswillbeanalysed.Inparticular,thispaperemploysaunifiedviewtolookintomulti-instancelearningalgorithms.Intheendofthepaperwillgivesomepersonalviewofthesealgorithms.Keyword:Multiple-instancelearning;supervisedlearning;bag;label摘要：多示例学习是监督学习的一种变形，因为其独特的性质，多示例学习被认为是与监督学习、非监督学习和强化学习并列的第四种学习框架。在多示例学习中，训练集由被标记的包构成，而包是由未被标记的示例构成，多示例学习的目的是通过对训练集的学习从而预测不可见包的标签。这篇论文是对多示例学习的一个研究，本文先简要介绍多示例学习的背景和历史成果，之后分别介绍四种多示例学习算法，他们分别是:DiverseDensity、Citation-kNN、BP-MIP和RBF-MIP。通过对数据集进行实验验证，并通过统一的标准对结果进行比较，简要说明这些算法各自的优点与不足之处。最后提出对多示例学习的一些个人想法以及对未来发展的展望。关键词：多示例学习;监督学习;包;标签1引言过去的几年中，基于示例的学习(learningfromexamples)是机器学习领域的一个热点。所谓基于示例的学习指通过对已有示例的训练和学习得到一个目标概念，通过概念建立模型用于对未知示例进行预测。根据数据训练集的模糊性，该方向的研究大致分成三种学习框架：监督学习、非监督学习和强化学习。其中监督学习的训练集由已知标签的数据构成，通过对训练集的学习构造一个目标概念，从而对未知标签的数据进行分类。非监督学习的训练集由未知标签的数据构成因为其模型的模糊性最大。强化学习的目的是通过学习得到一个从状态到动作的映射，训练集中的数据虽然是无标签的，但是每个动作都有一个延迟奖励(delayedrewards)，可被认为是延迟获得的标签，因而强化学习的模糊性介于监督学习和非监督学习之间。多示例学习是由Dietterich等人[1]在关于分子活性预测问题的研究时首次提出的。1.1分子活性预测研究表明，多数药物分子通过与比其大得多的蛋白质分子连接从而产生治疗的效果。效果的大小（药物分子活性大小）取决于药物分子与目标蛋白质分子连接的紧密程度，连接越紧密，效果越好，反之则越差。然而分子中原子之间的链接是可旋转的，如图1.1所示。图1.1这些旋转可构成不同的分子组合，对于一个具有n个链接的分子其组合数多达O(n3)。在这个巨大的数量空间中，只有少量结构的能量足够低，并且只有低能量的结构才能使分子与目标蛋白质分子紧密连接。所以如果一个药物分子可以用于制药，那么它所有结构的分子中至少有一种可以紧密连接目标分子，相反，不适合制药的分子其所有结构的分子均不能与目标分子紧密连接。目前的科学水平只能确认每个活跃的分子，其众多结构中至少存在一种结构使其具有活跃性，但是不能确定究竟是哪种结构使其有效。Dietterich等人[1](1997)对药物活性问题的研究提出了多示例学习模型。他们把药物分子抽象为包(Bag)的概念，分子的众多不同结构被抽象成包中的示例(Instance)。在多示例学习模型中，已知其活性的药物分子被赋予一个标签，但是包中的示例是没有标签的。因此一个包被标记为正(positive)的包当其中至少包含一个正的示例，否则其被标记为负(negative)的包。1.2论文主要研究内容本文的主要目标是介绍四种多示例学习算法，分别是DiverseDensity(DD)[2]，Citation-kNN[3]，BP-MIP[4]和RBF-MIP[5]。分别介绍他们的基本思想和实现流程，然后通过实验进行验证，并使用相对统一的评价标准对四种算法进行一定程度上的比较，评价角度主要包含对相同数据集的预测准确率(Accuracy)和过程时间消耗程度(Timeconsuming)等。并简要说明作者自己对每种算法的优点及其不足之处的看法。2多示例学习的算法研究2.1多示例概念多示例学习可以这样描述：训练数据集中每一个数据看做一个包(Bag)，每个包由多个示例(Instance)构成，每个包有一个可见的标签，包中的示例没有可见的标签。如果包中至少包含一个标签为正(positive)的示例，则包的标签为正;如果包中所有示例的标签都是负(negative)的，则包的标签为负。图2.1表现了包和示例的关系，多示例学习的过程就是通过模型对包及其包含的多个示例进行分析预测得出包的标签。图2.12.2多示例问题在药物分子活性预测问题中，一个分子可能有上百种低能量形状结构，这些结构中可能只有一种或少量几种结构是有效的，如果用传统的监督学习的方法简单的认为活跃分子的所有结构都是有效的，则会导致大量假正例的产生，因而对预测模型产生极大的干扰。为了解决这个问题，Dietterich等人[1]采用基于射线的分子结构表示方法。具体来说，每个分子的位置与方向都与标准笨环分子对齐，再使用发自原点的162条射线，对分子表面进行采样得到一个162维的向量，分子表面氧原子的位置用另外4条射线表示，这样将分子的结构抽象成一个166维的特征向量。如图2.2所示，由原点发出的8条射线与曲线交点到原点之间的距离可以得到一个8维的向量：(x1,x2,…x8)T。图2.2假设D为包Bi的集合，f(Bi)为包Bi的观察结果。对于活跃的药物分子Bi，f(Bi)=1；对于非活跃分子，f(Bi)=0。函数f表示多示例学习的过程函数。每个包Bi由mi个示例组成，这mi个示例记为Bi,1，Bi,2，„，Bi,mi。每个示例被表示成一个d维向量，则完整的训练集为：)(,，,,im,2,1,iiiiBfVVV一个包被标记为正(positive)包，当包中至少存在一个正示例，否则被标记为负(negative)包。可作如下描述：otherwise0,1)G(Vif,1)(ji,BiBfG(·)为分类模型的中间函数。2.3多示例学习的理论与算法研究Dietterich等人[1](1997)提出的三种轴平行矩形(AxisParallelHyper-Rectangle:APR)算法构成了多示例学习研究的基础。GFSelim-countAPR算法先构造一个包含了所有正包示例的轴平行矩形，如图2.3中实线矩形所示，通过贪心算法排除负包的示例缩小范围。图2.3中颜色和形状相同的点代表同一个包中的示例，白色表示正包，黑色表示负包。每个负包的示例边上的数字代表排除该示例所需的代价(附带排除的最少正包示例数)。GFSelim-countAPR使用这个方法最终得到图中的虚线矩形。GFSkdeAPR算法考虑矩形覆盖的正包示例数，使用代价函数在排除负包示例时尽量少的排出剩余示例较少的正包中的示例。Iterated-discrimAPR算法则是先找出覆盖每个正包中至少一个示例的最小矩形，然后挑选出最具有区别能力的一组属性，在此基础上通过核密度估计(kerneldensityestimation)对矩形边界进行扩展。Dietterich等人[1](1997)通过对麝香分子的数据集(MUSK)进行试验，发现Iterated-discrimAPR算法的效果最好。决策树、神经网络等常用的监督学习方法效果不理想，这说明必须要考虑到多示例本身的特点才能对多示例分类产生好的效果。但是Iterated-discrimAPR算法对数据集进行了优化，在该数据集上Iterated-discrimAPR算法的性能也许代表了一个上限。自从多示例学习的概念被提出，对于多示例学习机器学习领域提出了许多算法研究。这一章主要介绍分析了四种重要的多示例学习算法，并且这些算法在MUSK数据集上都取得不错的效果。图2.32.3.1DiverseDensityMaron和Lozano-Perez[2](1998)提出了DiverseDensity(DD)算法。该算法将候选分子的每个示例抽象成一个n维空间的特征向量，随着分子形状的改变，这些特征向量对应的点在n维空间形成一个轨迹。如果一个候选分子被标记为正(positive)的，那么这些轨迹中至少有一条诡计能够以有效的形状结构和目标蛋白质分子紧密连接。反之负的包不包含这样的轨迹。总的说来，在这个n维空间中，如果只有一种结构能够紧密连接目标蛋白质分子，那应该是空间中的某个区域，满足每一个正包至少有一个示例的轨迹在该区域内或者距离该区域足够近，并且所有负包的示例均远离该区域。因此这个区域的多样性密度定义为：不同的正包距离该区域足够近的程度以及负包示例远离该区域的程度。如图2.3.1(b)所示，其中A点是一个多样性高密度区，然而B点只是高密度区。算法要查找的是类似A点的多样性高密度区。图2.3.1定义正包为Bi+，Bi,j+表示第i个正包的第j个示例，Bi,j,k+表示第j个示例的第k个特征值。同时Bi-表示第i个负包，Bi,j-表示第i个负包的第j个示例。假设正确的概念是一个单一的点t，我们可以通过遍历所有的点，最大化m11B,,B,B,,B|txPrn根据Bayes定理可知相当于最大化：tnx|B,,B,B,,BPrm11假设各个包是相互独立的，则最好的假设转化为：(1)然后再次使用贝叶斯定理，假设就转化为(1)式：iiiiBtxBtx)|Pr()|Pr(maxargx(2)式(1)是多样性密度的一般定义，并使用noisy-or方法对其进行实例化：jji,i))B|tPr(x-(1-1)B|tPr(x(3)jji,i))B|tPr(x-(1)B|tPr(x(4)(2)式表明包中只要至少有一个点离t距离够近，这样结果是正包的概率就会很大，(3)式表明包中所有的点都距离t够远，这样结果是负包的概率将会很大。非常准确的实例化了多示例的特点。iiiitxBtxB)|Pr()|Pr(maxargx算法将示例出现在t点处的概率定义为示例到t点之间的距离：)Bexp()B|t