（计算机应用技术专业论文）基于支持向量数据描述的多示例学习算法研究.pdf

i j i iii f i f li ii f l li l l iiii y 19 0 9 13 6 d i s s e r t a t i o ns u b m i t t e dt oh a n g z h o ud i a n z iu n i v e r s i t y f o r t h ed e g r e eo fm a s t e r r e s e a r c ho nt h em u l t i - - i n s t a n c el e a r n i n g a l g o r i t h mb a s e do ns u p p o r t v e c t o rd a t a d e s c r i p t i o n c a n d i d a t e ：l i ub e i j i a s u p e r v i s o r ：p r o f f a n gj i n g l o n g d e c e m b e r ，2 0 1 0 杭州电子科技大学 学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得 的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过 的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 刘见锭 日期：力年3 月马日 学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或 使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件， 允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其 它复制手段保存论文。( 保密论文在解密后遵守此规定) 论文作者签名： 刊足欲日期：列j 年3 月躬日 指导教师签名：日期：2 d 力年3 月鲳日 i v 杭州电子科技大学硕士学位论文 摘要 上世纪9 0 年代，d i e t t e r i c h 等人在药物活性预测问题的研究中提出了多示 例学习的概念。在该学习模型中，训练样本的歧义性比较特殊，使得多示例学习 模型与传统的机器学习模型有很大的差别。由于多示例学习本身独特的性质和良 好的应用前景，被称为是与监督学习、非监督学习和强化学习并列的第四种机器 学习框架，并起了国内外研究者的极大关注。 随着研究的深入，多示例学习的理论体系日趋成熟，目前对多示例学习问题 的处理主要有三种途径：第一种是根据多示例学习本身的特殊性，构造专门的算 法来解决；第二种是通过将多示例学习的约束条件引入到传统的单示例学习算法 的目标函数中，对算法进行扩展，使其能够处理多示例问题；第三种是通过一定 的转换机制，将多示例学习问题转化为传统的单示例学习问题，然后用传统的单 示例算法对其进行学习。在上述三类途径下，研究者提出了大量的多示例学习算 法，并将算法应用到社会生产的多个领域中，如：图像分类、股票选择、入侵检 测等多个领域，取得了良好的经济效益。 本文主要研究了以下内容： 第一章和第二章主要对多示例学习的研究现状进行了综述。简单介绍了多示 例问题的提出背景、基本理论，多示例学习与传统机器学习的区别与联系，并对 几种经典的多示例学习算法进行了阐述。介绍了多示例学习的几个应用领域，并 对多示例学习的扩展研究进行了分析。 第三章对支持向量数据描述算法进行了研究。首先对统计学理论基础进行了 介绍，接着介绍了支持向量机，然后对支持向量数据描述算法的基本原理和求解 方法进行分析与讨论，最后引入核函数的概念，并对核函数对支持向量数据描述 算法的影响进行了实验与分析。 第四章是本文的主要研究内容。首先介绍了三种基于支持向量机的多示例学 习算法：m i s v m ，m i s v m 和d d s v m ，将其作为与本文算法的对比算法。然后提 出了一种消除正包中示例歧义性的方法，通过该方法，可以消除正包中示例的歧 义性，将多示例数据集转化为单示例数据集。最后，在多示例学习的第三种途径 下，通过对多示例数据集的转化，将其转化为传统的单示例问题，并用支持向量 数据描述算法对其求解。提出了三种基于支持向量数据描述的多示例学习算法： m i - n s v d d 算法、m i - n s v d d 算法和m i l p n s v d d 算法。 第五章是实验与分析，首先在多示例学习基准测试集( m u s k ) 上验证本文算 法的有效性，并与现有算法进行对比分析，以及参数对算法的影响。接着将本文 杭州电子科技大学硕士学位论文 提出的m i l _ p n s v d d 算法应用到图像分类中，在实践中验证本文算法，并通过实 验，观察样本的种类和数量对算法精度的影响。通过实验证明，本文提出的算法 具有良好的性能和应用前景。 第六章总结文章的主要工作，并对未来工作进行展望。 关键词：多示例学习，机器学习，支持向量机，支持向量数据描述 i l 杭州电子科技大学硕士学位论文 a bs t r a c t i nt h e9 0 so fl a s tc e n t u r y , d i e r e r i c he t c f i r s t l yp r o p o s e dm u l t i - i n s t a n c el e a r n i n g c o n c e p tw h i c h w a so r i g i n a t e df r o mt h e i rr e s e a r c ho fd r u ga c t i v i t yp r e d i c t i o n i nt h el e a r n i n gm o d e l ，t h ea m b i g u i t yo ft r a i n i n gs a m p l e sa r es p e c i a l ，s o m u l t i i n s t a n c el e a r n i n gm o d e li sd i f f e r e n tf r o mt r a d i t i o n a lm a c h i n el e a r n i n gm o d e l s a su n i q u en a t u r eo fm u l t i i n s t a n c el e a r n i n gi t s e l fa n dag o o dp r o s p e c t ，i sk n o w na s s u p e r v i s e dl e a r n i n g ，u n s u p e r v i s e dl e a r n i n ga n dr e i n f o r c e m e n tl e a r n i n ga l o n g s i d et h e f o u r t hm a c h i n el e a r n i n gf r a m e w o r k ，a n df r o md o m e s t i ca n df o r e i g nr e s e a r c h e r so f g r e a tc o n c e r n w i t hf t l r t h e rr e s e a r c h , t h et h e o r e t i c a ls y s t e mo fm u l t i i n s t a n c el e a r n i n gh a s m a t u r e d , t h e r ea r et h r e em a i nw a y st os o l v em u l t i i n s t a n c el e a r n i n gp r o b l e m s ：f i r s ti s b a s e do nt h ep a r t i c u l a r i t yo fm u l t i i n s t a n c el e a r n i n gp r o b l e m t oc o n s t r u c tas p e c i a l a l g o r i t h mt os o l v e ；s e c o n ds p e c i e sa r eb yi n t r o d u c i n gc o n s t r a i n t so fm u l t i i n s t a n c e l e a r n i n gt ot h et r a d i t i o n a ls i n g l e i n s t a n c el e a r n i n ga l g o r i t h mo f t h eo b je c t i v ef u n c t i o n t oe x t e n dt h ea l g o r i t h m , s ot h a ti tc a l lh a n d l em u l t i i n s t a n c ep r o b l e m s ；t m r di st h r o u g h s o m ec o n v e r s i o nm e c h a n i s m ，c h a n g et h em u l t i s a m p l el e a r n i n gp r o b l e mi n t oa t r a d i t i o n a ls i n g l e - i n s t a n c el e a r n i n gp r o b l e m s ，a n dt h e nu s et h et r a d i t i o n a ll e a r n i n g a l g o r i t h mt os o l v ei t i nt h et h r e et y p e so fa p p r o a c h , t h er e s e a r c h e r sm a d ea n u m b e ro f m u l t i i n s t a n c el e a r n i n ga l g o r i t h m s ，a n da l g o r i t h mi sa p p l i e dt om a n yf i e l d so fs o c i a l p r o d u c t i o n , s u c ha s ：i m a g ec l a s s i f i c a t i o n ，s t o c ko p t i o n s ，i n t r u s i o nd e t e c t i o na n do t h e r f i e l d s ，h a v ea c h i e v e dg o o de c o n o m i cb e n e f i t s t h i sp a p e rs t u d i e st h ef o l l o w i n g ： f i r s ta n ds e c o n dc h a p t e rs t u d yo fm u l t i - i n s t a n c el e a r n i n gw a sr e v i e w e d ab r i e f e x a m p l eo ft h em u l t i i n s t a n c ep r o b l e mb a c k g r o u n d ，b a s i ct h e o r y , m a n ye x a m p l e so f t r a d i t i o n a lm a c h i n el e a r n i n ga n dl e a r n i n gd i f f e r e n c e sa n dc o n n e c t i o n s ，a n ds e v e r a l c l a s s i c a lm u l t i i n s t a n c el e a r n i n ga l g o r i t h m sa r ed e s c r i b e d i n t r o d u c e daf e wm o r e e x a m p l e so fl e a r n i n ga p p l i c a t i o n s ，a n dt h ee x p a n s i o no fm u l t i i n s t a n c el e a r n i n gi s a n a l y z e d i nt h et h i r dc h a p t e r ，t h es u p p o r tv e c t o rd a t ad e s c r i p t i o na l g o r i t h mi ss t u d i e d f i r s t , t h et h e o r e t i c a lb a s i so fs t a t i s t i c sw e r ei n t r o d u c e d ，a n dt h e ni n t r o d u c e dt h es u p p o r t v e c t o rm a c h i n e ，a n dt h e nt h es u p p o r tv e c t o rd a t ad e s c r i p t i o na l g o r i t h mf o rs o l v i n gt h e b a s i cp r i n c i p l e sa n dm e t h o d so fa n a l y s i sa n dd i s c u s s i o n ，a n df i n a l l yt oi n t r o d u c et h e i i i 杭州电子科技大学硕士学位论文 c o n c e p to fk e r n e lf u n c t i o n ，a n dt h ek e m e lf u n c t i o no fs u p p o r tv e c t o rd a t ad e s c r i b i n g t h ee f f e c t so ft h ee x p e r i m e n t a lm e t h o da n da n a l y s i s t h ef o u r t hc h a p t e ri st h em a i nc o n t e n t f i r s ti n t r o d u c e dt h r e es u p p o r tv e c t o r m a c h i n eb a s e dm u l t i i n s t a n c e l e a r n i n ga l g o r i t h m ：m i s v m ，m i s v ma n dt h e d d s v m a sc o m p a r e dw i t ht h ea l g o r i t h m t h e nas a m p l ep a c k a g et oe l i m i n a t e a m b i g u i t yi st h em e t h o d ，t h em e t h o dc a nb ee l i m i n a t e di sa l le x a m p l eo ft h ea m b i g u i t y o ft h ep a c k a g e ，t h em u l t i s a m p l ed a t as e t si n t oas i n g l es a m p l ed a t as e t f i n a l l y , f o l l o w e dt h et h i r dm u l t i i n s t a n c el e a r n i n ga p p r o a c h ，t h em u l t i i n s t a n c ed a t as e tb yt h e t r a n s f o r m a t i o nw i l lb et r a n s f o r m e di n t oat r a d i t i o n a ls i n g l e i n s t a n c ep r o b l e m s ，a n d s u p p o r tv e c t o rd a t ad e s c r i p t i o na l g o r i t h mo fi t ss o l u t i o n p r o p o s e dt h r e em e t h o d s b a s e do ns u p p o r tv e c t o rd a t ad e s c r i p t i o no ft h em u l t i i n s t a n c el e a r n i n ga l g o r i t h m ： m i - n s v d da l g o r i t h m ，m i - n s v d da l g o r i t h ma n dm i l - p - n s v d da l g o r i t h m c h a p t e rf i f t hi se x p e r i m e n ta n da n a l y s i s ，t h ef i r s ti nam u l t i - i n s t a n c el e a r n i n g b e n c h m a r ks e t ( m u s k ) v e r i f yt h ev a l i d i t yo ft h i sa l g o r i t h ma n dw e r ec o m p a r e dw i n l e x i s t i n ga l g o r i t h m s ，a n dp a r a m e t e r s o ft h e a l g o r i t h m t h e n , t h ep r o p o s e d m i l p - n s v d da l g o r i t h mi sa p p l i e dt oi m a g ec l a s s i f i c a t i o n ，v e r i f i c a t i o na l g o r i t h mi n p r a c t i c e ，a n dt h r o u g he x p e r i m e n t ，o b s e r v a t i o nt y p e sa n dq u a n t i t i e so fs a m p l e so nt h e a l g o r i t h ma c c u r a c y t h ee x p e r i m e n ts h o w st h a tt h ep r o p o s e da l g o r i t h mh a sg o o d p e r f o r m a n c ea n da p p l i c a t i o np r o s p e c t s i nt h el a s tc h a p t e r , w es u m m a r i z et h em a i ni d e ao ft h ew o r k ，a n dt h ep r o s p e c to f f u t u r ew o r k k e y w o r d s ：m u l t i i n s t a n c el e a r n i n g ，m a c h i n el e a r n i n g ，s u p p o r tv e c t o rm a c h i n e s ， s u p p o r tv e c t o rd a t ad e s c r i p t i o n i v 杭州电子科技大学硕士学位论文 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 研究背景及意义1 1 1 1 研究背景1 1 1 2 研究意义3 1 2 论文的研究内容4 1 3 论文的结构4 第2 章多示例学习研究6 2 1 多示例学习概念6 2 1 1 多示例问题。6 2 1 2 多示例学习模型7 2 1 3 多示例学习与传统机器学习算法的区别8 2 2 多示例学习研究现状9 2 2 1 多示例学习的可学习性研究9 2 2 2 多示例学习算法研究1 0 2 2 3 多示例学习的应用研究13 2 3 多示例学习扩展1 4 2 3 1 多示例回归问题1 4 2 3 2 多部分学习1 4 2 3 3 广义多示例学习1 5 2 3 4 多示例多标记学习1 5 第3 章支持向量数据描述方法l7 3 1 统计学理论1 7 3 1 1 问题的表示1 7 3 1 2 经验风险和结构风险最小化1 7 3 1 3 统计学习理论的核心内容1 8 3 2 支持向量机2 0 3 2 1 线性可分支持向量机2 0 3 2 2 线性不可分支持向量机2 3 3 3 支持向量数据描述2 3 3 3 1 单类s v d d 2 4 3 3 2 带负类的s v d d 2 5 3 4 核函数2 6 3 4 1 常用核函数2 7 3 4 2 高斯核参数对s v d d 的影响2 7 第4 章基于支持向量数据描述的多示例学习方法3 0 4 1 基于支持向量机的多示例学习3 0 4 1 1m i s v m 和m i s v m 算法3 0 4 1 2d d s v m 算法3 1 v 4 2 4 3 第5 章 5 1 5 2 5 3 第6 章 6 1 6 2 谢 考文 录： 致参附 杭州电子科技大学硕士学位论文 第1 章绪论 1 1 研究背景及意义 1 1 1 研究背景 近年来，从例子中学习( 1 e a r n i n gf r o me x a m p l e s ) - - 直是机器学习和数据挖掘 领域的一个研究热点【l 】。根据训练数据的歧义性大小，大致可以把在该领域进行 的研究划分为三种学习框架：监督学习、非监督学习和强化学习【2 】。监督学习模 型中的样例是具有概念标记( c o n c e p tl a b e l ) 的，通过对样例的学习和训练，得到 一个目标概念，以尽可能正确地预测新事例的概念标记。非监督学习模型的样例 数据是没有概念标记的，因此该学习模型的歧义性是最大的。强化学习通过对没 有概念标记、但与一个延迟奖赏或效用( 可看做延迟的概念标记) 相关联的训练 样例进行学习，从而获得从某种从状态到行为的映射。其中所有的训练样本都是 具有概念标记的，但不同于监督学习的是，标记是延迟的，因此，强化学习的歧 义性介于监督学习与非监督学习之间。d i e t t e r i c h 等人1 1 j 于1 9 9 7 年在对药物活性 预测( d r u ga c t i v i t yp r e d i c t i o n ) 问题的研究中，首次提出了多示例学习的概念。 多示例学习属于以往机器学习的一个盲区，具有独特的性质和广泛的应用前景， 因此该模型被认为是与监督学习、非监督学习和强化学习并列的第四种学习模 型，并引起了机器学习领域学者的广泛关注。 多示例学习问题是由研究者在研究药物分子的活性预测问题时提出的。通过 机器学习的方法来处理分子活性预测问题有很多好处。通过学习可以得到一个分 类器，研究者可以利用该分类器从大量的备选合成分子中选出最具活性的分子， 从而可以使公司把有限的资源集中于研究这些具有开发价值的合成分子，为只要 公司节省大量的人力和物力，节省掉那些无谓的成本。药物分子活性预测的目的 是让学习系统通过对已知适于或不适于制药的分子进行分析学习，以尽可能正确 地预测某种新的分子是否适合制造药物。 研究表明，大多数药物都是一些相对较小的分子，它们通过与比它大得多的 目标蛋白质分子的绑定来发挥作用，从而起到对疾病的治疗效果，药效则取决于 药物分子与目标分子连接的绑定程度。如果药物分子与目标蛋白质连接的越紧 密，则药力越大：反之则越小。通常药物分子与目标蛋白分子不形成共价键连接， 而是以基于分子的形状形成的弱连接。常见的弱连接形式：( 1 ) 静电连接、( 2 ) 氢键链接、( 3 ) 范德瓦尔连接、( 4 ) 厌水连接等【l 】。当药物分子的与目标蛋白分子 的形状是互补时，药物分子与目标蛋白质分子两者结合点处附近的表面就会有复 杭州电子科技大学硕士学位论文 合连接产生，并且，两者的形状越相似，则连接力就越强，药物分子的活性也就 越高；反之则连接就越弱，甚至不能够与目标分子连接，分子的活性也就越弱。 一个好的药物分子能非常牢固地联结到目标蛋白分子的表面。 构成分子的各个原子之间的链接是能够旋转的，不同的旋转链接的组合对应 不同形状的分子，称为分子的同分异构体，如图1 1 【l 】所示。如果一个分子具有n 个链接，那么链接的组合数可达到o ( ，2 3 ) 。这是一个相当巨大的空间，但幸运的 是在这些异构体中，仅仅有很少一部分构型的能量是足够低的，而且，只有这些 低能量级的形状才能使分子与目标分子紧密的连接。因此，若一个合成分子能够 被用于制药，则在该分子所有可能的低能量形状中，至少存在一种分子形态，可 以使合成分子与受体分子的目标区域紧密连接到一起，而那些不适合的低能分子 形态均不能使合成分子与目标分子紧密地连接。 图i i 一个内部键发生旋转，分子的形状就发生了显著变化 虽然使分子具有药学研究价值的低能分子形态，在分子的形状空间中只占很 少的一部分。不过困难的是，以当前的生物化学技术条件，生物化学专家只能知 道哪些分子适于制药，但并不知道具体是哪一种形状起到了决定性作用。因为一 个分子可能有上百种低能形状，而这么多形状中只要有一种是合适的，这个分子 就适于制药，这使得分子活性预测问题表现出与其他学习问题不同的特点。 d i e t t e r i c h 等人【l 】在总结了他们对于药物活性预测问题的研究后，提出了 多示例学习的概念。他们将药物分子所有低能形状看做是一个集合，称之为包 ( b a g ) ，而分子的每一种低能形状被抽象为集合中的一个元素，称为包中的示例。 在多示例学习模型中，为了与实际的药物分子活性预测问题保持一致，样例集合 中的包是有概念标记的，而包中的示例是没有概念标记的。若包中含有至少一个 正示例，则包被标记为正( p o s i t i v e ) 包，否则被标记为负( n e g a t i v e ) 包。多示 例学习的目标是通过对训练样例集的学习，得到一个能够正确对新包类标签进行 预测的目标函数。 在d i e t t e r i c h 等人【l 】提出用多示例学习来解决药物分子活性预测问题之前， 有很多学者尝试通过传统机器学习的途径来解决这类问题。例如，h a n s c h 和 f u j i t a 【3 j 、h a n s c h 和l e o 【4 1 分别提出了两种药物分子活性预测方法，由于这两种方 2 杭州电子科技大学硕士学位论文 法在对分子表示的时候忽略了分子形状的多样性，使得这两种方法只是在预测简 单分子的活性，或者预测具有大量共享结构的分析的活性时有较好的效果。但 b l a n k l e y 5 】指出，如果当预测分子结构比较复杂时，这两种算法的效果却不能令 人满意。 随着生化科学的发展，人们对药物分子的形状对其活性的影响有了进一步的 认识，同时研究者可以使用先进的仪器来测量分子的形状，于是一种基于形状 ( s h a p e - - o r i e n t e d ) 的分子表示方法被提了出来。1 9 9 8 年，c r a m e r ，p a t t e r s o n s d b u n c e 6 】在基于形状的分子表示方法的基础上提出了c o m f a 算法，不过在预测 药物分子的活性之前，需要猜测每个分子可能的活跃形状。虽然c o m f a 算法在选 取分子的活跃形状时遇到了困难，但它仍旧揭示了基于外形的分子表示法的是解 决此类问题的一个好途径。同年，c r i p p e n 和h a v e l 7 j 提出了一个经典的基于距离 一几何( d is t a n c e - - g e o m e t r y ) 分子活性预测算法。该算法是一个具有多示例特 性、直接面向分子的算法，遗憾的是，由于无法解决搜索空间中遇到的组合爆炸 问题，使得该算法只适合于预测连接点仅仅包含四到五个关键原子的分子活性。 总的来说，以往的这些算法，都没有真正认识到药物分子活性预测问题所具 有的多示例学习性质。只是简单地认为，在适合制药的分子的所有低能量形状都 能使之与目标分子紧密联结。实际上在药物分子的所有可能形状中，只是有很少 一部分与目标分子连接区域的形状互补。因此d i e t t e r i c h 等人l l 】提出了多示例问 题模型，用来描述药物分子活性预测的独特性，并且他们通过实验证明，如果不 考虑多示例问题本身的独特性，传统的机器学习算法是不可能很好地解决该问题 的。其实，多示例学习问题是一直存在的，并不单单局限于药物分子活性预测研 究领域，可惜在以往的机器学习研究中，研究者并没有关注此类问题的特性，只 是将其作为传统的机器学习问题来对待，直至u d i e t t e r i c h 等人【l 】于1 9 9 7 年才正 式将此类问题界定为多示例学习问题。 1 1 2 研究意义 由于多示例学习具有独特的性质，目前被认为是一种与监督学习、非监督学 习、强化学习并列的新的学习框架，并且具有广泛的应用前景，属于以往机器学 习领域的一个盲区，因此引起了国内外机器学习领域研究人员极大的关注。对多 示例学习的研究在理论和实际上都有深远的意义。 支持向量数据描述方法是由t a x 等人于1 9 9 9 年，在支持向量机算法的基础上 提出来的，它是一种单值分类方法。由于其良好的模型构造和广泛的实际应用， 国内外许多学者对其进行了深入的研究，不管是其建模理论还是应用领域、应用 形式的研究都引起了极大的关注，成为机器学习和模式识别领域新的研究热点， 并被广泛应用于实践当中，对社会的发展起到了巨大的推动作用。 杭州电子科技大学硕士学位论文 依据在课题研究中对支持向量数据描述算法的研究和取得的成果，结合当前 多示例学习问题的研究现状，并对当前多示例学习问题应用的主要领域进行了分 析，并从中选取了几个关键领域作为论文的研究对象j 将支持向量数据描述理论 与求解多示例学习问题结合，提出基于支持向量数据描述的多示例学习算法，并 通过相应的实验来验证算法的性能。 因此，本课题的研究不但具有重要的理论和实际意义，而且对未来的研究工 作也具有一定的参考价值和指导意义。 1 2 论文的研究内容 本文主要对多示例学习问题和支持向量数据描述算法进行分析与研究，在现 有研究的基础上，将s v d d 算法应用到多示例学习中，提出了三种基于s v d d 的多示例学习算法：m i - n s v d d 、m i n s v d d 、m i lp - n s v d d 。主要研究内容 有以下几个部分： 1 对多示例学习问题的研究。主要研究了多示例问题的模型，多示例学习的 框架，当前多示例学习算法的研究状况。 2 多示例学习的应用研究。对多示例学习的一些常用领域进行了研究，如 基于内容的图像检索、文本分类、药物活性预测、w e b 目录页面推荐等。 3 对支持向量数据描述算法的研究。 以及支持向量数据描述算法的相关研究， 了研究。 主要研究了统计学和s v m 理论基础， 并对核函数对s v d d 算法的影响进行 4 基于支持向量数据描述的多示例学习研究。首先对目前基于s v m 的多示 例学习算法进行了研究，如m i s v m 、m i s v m 和d d s v m 等。并在不同的多 示例学习途径下，将s v d d 方法应用到多示例学习中，提出了三种基于s v d d 的多示例学习算法。这一部分是本文研究的重点。 5 实验设计与分析。在多示例学习的基准测试集上验证本文提出的算法，并 将所提出的算法应用到基于内容的图像分类中。 1 3 论文的结构 论文共包括六章，结构安排如下： 第一章绪论部分介绍了多示例学习问题产生的背景，以及本文的选题依据和 研究意义，介绍了本文的主要研究内容和论文的结构。 第二章是多示例学习的研究，给出了多示例问题的模型，以及多示例学习框 架，并对目前多示例学习概况进行了阐述，介绍了当前多示例学习算法的研究状 况，并简要列举了多示例学习的几个应用领域。 第三章是对支持向量数据描述算法的研究，首先对统计学理论基础和支持向 量机进行了介绍，然后对s v d d 算法以及带负类的s v d d 算法进行阐述，并研 4 杭州电子科技大学硕士学位论文 究了核函数对s v d d 算法的影响： 第四章是基于支持向量数据描述的多示例学习算法研究，首先介绍了几种当 前基于s v m 的多示例学习算法，然后介绍了一种消除正包中示例歧义性的方法， 并提出三种基于s v d d 的多示例学习算法。 第五章是实验设计与分析。首先给出了本文所使用的数据集，然后将本文所 提出的算法应用到相应数据集上，并与基于支持向量的多示例学习算法进行比较 分析，并将所提出的算法应用到基于区域分割的图像分类中，以验证算法的实用 性。 第六章是对本文的研究工作进行总结，并提出了当前多示例学习面临的一些 问题，以及对未来工作的展望。 杭州电子科技大学硕士学位论文 第2 章多示例学习研究 2 1 多示例学习概念 2 1 1 多示例问题 在药物活性预测问题中，绝大部分药物都是一些分子，它们通过分子间的作 用与较大的蛋白质分子( 例如各种酶等) 来发挥效用，和蛋白质分子的绑定程度 决定了药效的大小。如果分子的某种低能形状和期望的绑定区域能够很紧密的耦 合，则说明该分子适于制造药物；如果不能和期望的绑定区域很好的耦合，则说 明该分子不适于制造药物。 d i e t t e r i c h 等人i l j 于2 0 世纪9 0 年代中后期对药物活性预测问题进行了研究， 他们希望通过让学习系统对那些已知适于或者不适于制药的分子进行分析学习， 从而可以尽可能准确的对未知分子是否适合制造药物进行预测。正如图1 1 所示， 每个分子的低能形状都有很多种，从而给该问题的解决带来了很大的困难。以当 前的技术，生化学家只能知道哪些分子适于制药，而无法知道究竟是哪一种低能 形状起了决定性的作用。以监督学习框架来分析该问题，若把适于制药的分子的 所有低能形状都看做正类，而把所有不适于制药的分子的所有低能形状都看做负 类，这样的假设会因为正类中的噪声太高无导致无法很好的学习。因为只要一个 分子的低能形状中有一种是合适的，那么这个分子就适于制药。 d i e t t e r i c h 等人i l j 提出了多示例学习的概念用以解决该问题，将每一个分子 看做是一个包，分子的每一种低能形状看做是包中的一个示例。他们采用基于射 线的分子外形表示方法，将低能形状表示成属性值对的形式，他们首先将分子 位置和朝向与标准苯分子对齐，然后以原点为中心，放射出1 6 2 条比较均匀地射 线，将每条射线与分子表面的交点到原点之间的距离长度作为一个属性，图2 1 所示为一个简单的例子。另外，再加上分子表面固定氧原子的位置4 条射线来表 示，从而可以将包中的每个示例用1 6 6 个数值属性描述出来。 1 9 9 7 年，d i e t t e r i c h 等人【l 】总结了他们的研究成果，正式提出了一种新的问 题模型：多示例问题模型。在该模型中，每个分子模型被看做是一个包( b a g ) ，而 分子的各种低能形状看做是一个个示例，根据是否适于制药分子分别标记为 “p o s i t i v e 或“n e g a t i v e ，并将相应的包标记为“+ 一 ；包中的元素由描 述分子形状的数值特征向量组成，称为示例，示例是没有标记的。如果包中的示 例至少有一个是正的，则该包被标记为正包；反之则为负包。利用基于射线的分 子形状表示法，己将每个示例用一个1 6 6 数值的特征向量来表示，因此，包可以 6 杭州电子科技大学硕士学位论文 瓷药。 1 髟 。向| 7 冬一 ，x 6 ， x 图2 1 利用射线来表示分子形状 看做是由多个特征向量构成的向量集合，因此，d i e e r i c h 等人将这种新的学习 框架称为多示例学习。图2 2 1 1 3 i g l 图2 3 m 分别表述了传统学习框架与多示例学习 框架。 移i a _ p ，d 嘴 图2 2 传统学习框架示意图 。 l l h 翻雕砌 b 甜峨 b 懿嘞 1 e l n 幻附- 慑 p 玎糯 图2 3 多不例学习框架不意图 2 1 2 多示例学习模型 在1 9 9 7 年，d i e t t e r i c h 等人【1 】总结他们对分子活性预测问题的研究工作，提 出了多示例学习模型： 假设d = 忍| f = 1 仂 为脚个包的集合，其中每个包e 对应一个映射标记 厂( e ) ，若适于药物分子，记为厂( 垦) = l ；若不适于药物分子，则厂( e ) = 0 。映 射厂对应的是相应的未知学习过程，学习的目标是通过对训练样本集的学习，得 到映射厂的一个最佳近似映射厂。每个包中拥有，个不同的示例，记为 包。，匆：，其中的每一个示例都是一个d 维的向量，则一个训练样本可以表示 杭州电子科技大学硕士学位论文 为： 并且，若包中至少存在一个正示例，则包被标记为正包； 则多示例学习可用下面的公式描述： 肥，= 长糍三1 ( 2 1 1 ) 否则标记为负包。 ( 2 1 2 ) 其中g ( ) 为判别示例类别的中间函数。 2 1 3 多示例学习与传统机器学习算法的区别 在传统的机器学习中，对象与相应的描述之间是一对一的关系，但在一些现 实问题中，某个对象会可能同时具有多个描述，而在这些描述中，只有一个或者 某几个对对象的属性具有据定性，但并不清楚具体是哪些描述对对象的性质起决 定作用。多示例学习模型的提出，就是为了解决“对象：描述：类别 之间关系 是1 ：n ：1 的问题。从以上的描述可知，多示例学习中训练样本的歧义性与以 往的机器学习中样本歧义性有很大的区别，导致以往的机器学习方法不能很好的 解决此类问题。 回、， ih t s t a n c c 卜 匡一 曰 图2 4 传统机器学习和多示例学习模型的区别 如图2 4 所示，多示例学习与传统监督学习区别主要有以下几方面： ( 1 ) 在传统监督学习中，训练对象与特征向量之间是一对一的关系；而在多 示例学习中，训练对象是由多个示例组成的包来表示的，是多对一的关系。 ( 2 ) 在传统的监督学习中，每个对象都对应有一个标记，用于训练和学习； 而在多示例学习中，每个包对应有一个标记，而包中的示例是没有标记的。 ( 3 ) 在传统的监督学习中，新对象的分类由该对象在目标函数上的输出决定； 而在多示例学习中，若包被标记为正包，则包中至少包含一个正示例，否则标记 为负包，预测包的标记取决于某个中间函数在包中的示例上的最大输出值。 由上可知，可以将多示例学习看做是传统监督学习的泛化，因为多示例问题 本身的特殊性，导致多示例学习比监督学习的歧义性大很多。所以，我们所选用 杭州电子科技大学硕士学位论文 的机器学习算法必须能够克服这一歧义性。 2 2 多示例学习研究现状 2 2 1 多示例学习的可学习性研究 在d i e t t e r i c h 等人【l 】公布其研究成果后，p m l o n g 和l t a n l 2 7j 对多示例 学习框架下的a p r 算法的可学习性【2 8 j 进行了研究，他们指出，在多示例学习框 架下，