多示例学习(周志华)

多示例学习*周志华南京大学软件新技术国家重点实验室,江苏南京210093摘要:在多示例学习中，训练样本是由多个示例组成的包，包是有概念标记的，但示例本身却没有概念标记。如果一个包中至少包含一个正例，则该包是一个正包，否则即为反包。学习的目的是预测新包的类别。由于多示例学习具有独特的性质，目前被认为是一种新的学习框架。本文对该领域的研究进展进行了综述，并对有待深入研究的一些问题进行了讨论。1引言20世纪90年代以来，从例子中学习（learningfromexamples）被认为是昀有希望的机器学习途径[1]。如果以训练样本的歧义性（ambiguity）作为划分标准，则目前该领域的研究大致建立在三种学习框架（learningframework）[2]下，即监督学习、非监督学习和强化学习。监督学习通过对具有概念标记（conceptlabel）的训练例进行学习，以尽可能正确地对训练集之外的示例的概念标记进行预测。这里所有的训练样本都是有标记的，因此其歧义性昀低。非监督学习通过对没有概念标记的训练例进行学习，以发现数据中隐藏的结构。这里所有的训练样本都是没有标记的，因此其歧义性昀高。强化学习通过对没有概念标记、但与一个延迟奖赏或效用（可视为延迟的概念标记）相关联的训练例进行学习，以获得某种从状态到行动的映射。这里所有的训练样本都是有标记的，但与监督学习不同的是，标记是延迟的，因此强化学习的歧义性介于监督学习与非监督学习之间。20世纪90年代中后期，研究者们[3]在对药物活性预测（drugactivityprediction）问题的研究中，提出了多示例学习（multi-instancelearning）的概念。在此类学习中，训练集由若干个具有概念标记的包（bag）组成，每个包包含若干没有概念标记的示例。若一个包中至少有一个正例，则该包被标记为正（positive），若一个包中所有示例都是反例，则该包被标记为反（negative）。通过对训练包的学习，希望学习系统尽可能正确地对训练集之外的包的概念标记进行预测。与监督学习相比，多示例学习中的训练示例是没有概念标记的，这与监督学习中所有训练示例都有概念标记不同；与非监督学习相比，多示例学习中训练包是有概念标记的，这与非监督学习的训练样本中没有任何概念标记也不同；而与强化学习相比，多示例学习中又没有时效延迟的概念。更重要的是，在以往的各种学习框架中，一个样本就是一个示例，即样本和示例是一一对应关系；而在多示例学习中，一个样本（即包）包含了多个示例，即样本和示例是一对多的对应关系。因此，多示例学习中训练样本的歧义性与监督学习、非监督学习、强化学习的歧义性都完全不同，这就使得以往的学习方法难以很好地解决此类问题。由于多示例学习具有独特的性质和广泛的应用前景，属于以往机器学习研究的一个盲区，因此在国际机器学习界引起了极大的反响，被认为是一种新的学习框架[2]。*本文得到国家杰出青年科学基金(60325207)和国家自然科学基金(60473046)资助2本文首先介绍多示例学习的起源，然后对该领域的研究进展进行综述，昀后对有待深入研究的一些问题进行讨论。2问题的提出大多数药物都是一些分子，它们通过与较大的蛋白质分子例如酶等绑定来发挥作用，药效则是由绑定的程度决定的。对适于制造药物的分子来说，它的某个低能形状和期望的绑定区域将耦合得很紧密；而对不适于制造药物的分子来说，它和期望的绑定区域将耦合得不好。20世纪90年代中后期，T.G.Dietterich等人[3]对药物活性预测问题进行了研究。其目的是让学习系统通过对已知适于或不适于制药的分子进行分析，以尽可能正确地预测某种新的分子是否适合制造药物。该问题的困难主要在于，每个分子都有很多种可能的低能形状，图1给出了一个例子。而生物化学专家目前只知道哪些分子适于制药，并不知道具体的哪一种形状起到了决定性作用。如果直接使用监督学习框架，将适于制药的分子的所有低能形状都作为正例，而将所有不适于制药的分子的所有低能形状都作为反例，则会由于正例中噪音度太高而难以成功地进行学习。这是因为一个分子可能有上百种低能形状，而这么多形状中只要有一种是合适的，这个分子就适于制药。为了解决这个问题，T.G.Dietterich等人[3]将每一个分子作为一个包，分子的每一种低能形状作为包中的一个示例，由此提出了多示例学习的概念。为了将分子的低能形状表示成属性-值对的形式，他们首先将分子固定在标准位置和朝向，然后从原点比较均匀地放射出162条射线，每条射线被原点与分子表面所截出的线段长度就被作为一个属性，如图2所示。再加上4个表示固定的氧原子位旋转图1一个内部键发生旋转，分子的形状就发生了显著变化x1x2x3x4x5x6x7x8图2利用射线来表示分子形状3置的属性，这样，包中的每个示例就由166个数值属性来描述。在此基础上，他们提出了三个APR（Axis-ParallelRectangles）学习算法[3]。这些算法都是通过对属性值进行合取，在属性空间中寻找合适的轴平行矩形。GFSelim-countAPR算法先找出覆盖了所有正包示例的轴平行矩形，再以排除反包中的各示例所分别需要排除的正包示例数为标准，通过贪心算法逐渐排除反包示例以缩小矩形。图3给出了一个例子。图中同样颜色和形状的点表示同一个包中的示例，白色表示正包，黑色表示反包。GFSelim-countAPR算法先找出一个包含所有正包示例的轴平行矩形，如图中实线所示。对该矩形所包含的每一个反包示例，图中都标出了为了通过收缩矩形的边界以将其排除所需付出的代价，即所需附带排除的昀少的正包示例数。GFSelim-countAPR算法就根据这些代价，贪心式地逐渐缩小矩形，从而得到了图中虚线所示的结果。昀后，该算法通过贪心属性选择确定该矩形在相关属性上的边界，这样就得到了学习结果。图3GFSelim-countAPR算法运行的例子GFSkdeAPR算法则是在GFSelim-countAPR的基础上，考虑矩形所覆盖的各正包中的示例数，利用一个代价函数来使得在排除反包示例时，尽可能少地排除剩余示例较少的正包中的示例。Iterated-discrimAPR算法先通过贪心式的backfitting算法[4]找出一个覆盖了每个正包中至少一个示例的昀小矩形，然后利用该矩形挑选出昀具有区别能力的一组属性，在此基础上，通过核密度估计（kerneldensityestimation）对昀可能出现正包示例的矩形边界不断进行扩展。T.G.Dietterich等人[3]利用麝香（musk）分子的数据进行了实验，发现Iterated-discrimAPR算法在药物活性预测问题上取得了昀好的效果，而C4.5决策树、BP神经网络等常用的监督学习算法效果很不理想。这说明如果不考虑多示例学习本身的特点，将难以很好地完成此类学习任务。另外，T.G.Dietterich等人[3]指出，由于Iterated-discrimAPR算法根据麝香分子的数据进行了优化，因此，在该数据集上该算法的性能也许代表了一个上限。实际上，多示例学习问题其实是一直存在的，并不是由于对药物活性预测问题的研究而突然出现的。只是以往的机器学习研究[5,6]并没有明确考虑此类问题的特性，到了T.G.Dietterich等人的工作中才正式地把这个问题界定出来。4值得注意的是，多示例学习还引起了归纳逻辑程序设计（inductivelogicprogramming，简称ILP）[7]领域的研究者的兴趣。机器学习常用的属性-值对表示方法实际上是一种命题知识表示，而ILP领域的研究使用的是一阶知识表示。一阶知识表示的表达能力比命题知识表示强得多，但要高效地进行学习却非常困难。L.DeRaedt[8]认为，多示例表示为命题知识表示和一阶知识表示建立了联系，在这种表示下，既有助于利用一阶表示的表达力又有助于发挥命题学习的高效性。因此，ILP领域的研究者也对多示例学习进行了研究，但由于这些工作与目前一般意义上的机器学习有较大差别，本文没有对此进行介绍。3研究进展3.1可学习性T.G.Dietterich等人的工作刚公布，P.M.Long和L.Tan[9]就对多示例学习框架下APR的PAC可学习性[10]进行了研究。他们证明，在多示例学习框架下，如果包中的示例是独立的，且符合积分布（productdistribution），则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的维数以及每个包中所含的示例数，样本复杂度是指训练包的数目，iO表示忽略结果中的对数项。值得注意的是，这些工作都假设包中示例是独立的，但遗憾的是，该假设在真实问题中显然是难以成立的，例如在药物活性预测问题中，同一个分子的低能形状之间是有密切联系的。表1多示例学习可学习性的主要研究结果样本复杂度时间复杂度假设条件主要分析工具P.M.Long和L.Tan的结果2610(log)dnndOεεδ512220(log)dnndOεεδ包中示例相互独立，且满足积分布P-conceptVC维的变体P.Auer等人的结果222(log)dndOεδi322()dnOε包中示例相互独立VC维A.Blum和A.Kalai的结果i22()dnOεi322()dnOε包中示例相互独立统计查询模型VC维总的来看，计算学习理论界为了分析多示例学习的可学习性，提出了一系列多示例学习理论算法。但由于理论工具的制约，几乎所有的理论算法都对包中示例的分布等施加了种种限制，这就使得这些理论算法难以直接用于解决实际的问题。因此，这些工作更重要的是丰富了PAC理论本身的5研究。但有一些结果对解决实际的多示例学习问题也有一定的指导意义，例如，P.Auer等人[11]通过分析多示例学习框架下APR的可学习性与DNF公式（DNFformulas）可学习性之间的关系，证明了如果包中示例不是独立的，则在多示例框架下对APR进行学习是一个NP难问题。这一结果在一定程度上说明，寻找假设结构简单且可以高效完美地解决多示例学习问题的方法几乎是不可能的。3.2算法在T.G.Dietterich等人的工作之后，很多研究者开始致力于设计实用的多示例学习算法。1998年，O.Maron和T.Lozano-Pérez[14]提出了多样性密度（DiverseDensity，简称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：()()argmaxPr|Pr|iixiixtBxtB+−==∏∏（1）式（1）就是多样性密度的一般定义。在实际使用时，需要对式（1）中的乘积项进行例化。O.Maron和T.Lozano-Pérez[14]采用了noisy-or模型：()()()Pr|11Pr|iijjxtBxt