《内点法在支撑向量机中的应用》由会员分享，可在线阅读，更多相关《内点法在支撑向量机中的应用（45页珍藏版）》请在金锄头文库上搜索。
1、 摘要 支撑 向量 机方法 是近年来兴起的一种 重要的机器 学习 方法， 主要 应用于 信 息分 类问题. 其核心 技巧是利用高维超平面 将需 要被分类的 信息 分开 ， 并且使得 类与类之间的距离最 大化 在训练支撑向 量机的 过程中斤面临的最大间题是需要求解一个大规模的二次规划间题.这 个二次 规 划问 题可以 在优化理论的框架下 被解决. 本丈针对支撑向量机中遇到的这类特殊的二次规划问题给出了很 好的解映方案. 该方法整合了 “ 初值技巧” 和 “ 动态权” 技巧. 从数值试 验的结 吴 可以看出， 该 方法提高了 训练模型的准确度和计算 速度. 这 一方法还 被应用于数字手写检索中，被
2、证明是一种行之有效的方法. K e tv vo r d s :内 点法， 二次 规划， 支 撑向量 机， 信息 检索 I n t e r i o r P o i n t Me t h o d i n S u p p o r t V e c t o r Ma c h i n e Ka i S lid S u p e r v i s e d b y P r o f e s s o r Y a - x i a n g Y u a n In s t it u t e o f C o m p u t a t i o n a l Ma t h e m a t i c s a n d S c i e n t
3、 i fi c / E n g i n e e r i n g C o mp u t i n g , A c a d e my o f Ma t h e m a t i c s a n d S y s t e m S c ie n c e s , C h i n e s e A c a d e m y o f S c i e n c e s , B e ij i n g , 1 0 0 0 8 0 , P e o p l e s R e p u b li c o f C h i n a Abs t r a c t T h i s t h e s i s p r o p o s e s a n
4、e w r o b u s t a l g o r i t h m f o r S u p p o r t V e c t o r Ma - c h i n e ( S V M) . T h e S u p p o r t V e c t o r Ma c h i n e i s a n e w a n d v e r y p o w e r f u l c l a s s i fi c a t i o n t e c h n i q u e . T h e k e y i d e a o f t h i s t e c h n i q u e i s t o s e p a r a t e
5、t h e c l a s s e s w i t h a h y p e r - s u r f a c e t h a t m a x i m i z e s t h e m a r g i n b e t w e e n t h e m . I n t r a i n i n g t h e S V M, t h e c o r e p r o b l e m o n e m u s t f a c e i s t o m i n im i z e a c e r t a i n q u a d r a t i c f u n c t i o n . T h e r e f o r e
6、, t h e S V M p r o b l e m c a n b e c o n v e r t e d i n t o a ma t h e ma t i c a l f o r m u n d e r t h e f r a me w o r k o f o p t i mi z a t i o n t h e o r y . I n t r a i n i n g S VM o r o t h e r o p t i mi z a t i o n p r o b l e ms , t h e i n i t i a l f e a s i b le p o i n t h a s
7、d i r e c t e ff e c t o n t h e p e r f o r m a n c e o f a n a l g o r i t h m . W e p r e s e n t a d e c o m p o s i t i o n a l g o r i t h m t h a t c a n b e u s e d t o t r a i n S V M o v e r l a r g e d a t a s e t s . T h i s a l g o r i t h m c o m b i n e s w i t h t h e t e c h n i q u
8、 e o f c h o o s i n g p r o p e r i n i t i a l p o i n t a n d d y n a mi c w e i g h t t e c h n i q u e t o i mp r o v e t h e s p e e d a n d t h e a c c u r a c y o f c l as s i c a l a l g o r i t h m We h a v e d e v e l o p e d a s o f t w a r e p a c k a g e b a s e d o n t h i s n e w a l
9、 g o r i t h m T h i s s o f t w a r e p a c k a g e o p e n s p o t e n t i a l in m a n y P z p e c t s , s u c h a s b e t t e r o p t i - m iz a t io n a lg o r it h m s , t h e u s e o f S V M in in fo r 哭 a tio n r e t r ie v a l, p a t te r n r e c o g - n i t i o n o r o t h e r a p p l i c
10、a t io n s . Ke y w o r d s Q u a d r a t i c P r o g r a m m i n g , I n t e r io r P o i n t Me t h o d , S u p p o r t V e c t o r Ma c h i n e . I n f o r ma t i o n Re t r i e v a l 致谢 作 者要对导师袁 亚湘研究员和北京大学的徐树方教授 表示衷心的 感谢和崇高的敬意.在我攻读硕士学位的三年期间，袁老师给了我非 常多的帮助.徐老师对我多年来持续不断的指导在我的成长中起到了 非常重 要的作用. 他们不仅在学
11、习 和科研方面给我指导和 鼓励， 还在 思想方面给我深刻的启迪.作为 良 师，他们精深渊博的学识， 严谨的 治学态度，独特新颖的思考和诲人不倦的教导，无不在我的脑海里留 下了不可 磨灭的印象， 并将一直影响着我今后的 学习 和工 作， 令 我终 身受益. 作 者非常 感谢M ic r o so ft R e s e a r c h A s ia 的王 坚老师， D a rt m o u th U n i- v e r s ity 的吕 思伟 师兄 和M ic r o s o ft R e s e a r c h A s ia 的 邹宇师兄 ， 是他们在 我对支 撑向 量机一无 所知的时 候给
12、予我非 常多帮 助和鼓励 另外没有 U n iv e r s ity o f M a ry la n d C o lle g e P a rk 的凌海滨师兄和 U n iv e r s ity o f C a li- fo r n ia B e rk e le y 的 魏子乐 师兄的帮 助， 我的 很多问 题是无法 完成的. 他 们都是我在学习工作中的朋友，他们的榜样作用一直鼓励着我不断前 进.在此对他们一并感谢，也祝他们今后的事业成功. 作者还要非常感谢王明艳和王彦飞博士，他们在许多问题上给了 我很多宝 贵的 经验和 现实的帮助 作者也要同时感谢课题 组的魏紫变 老师，戴或虹老师，以及优化讨
13、论班的所有其他成员，他们都是我的 良 师益友 每次 讨论班 上大家的热 烈探讨都带给我新的想 法和启示. 另外， 对M c M a s t e r U n iv e rs ity 的T a m a s T e r la k y 在我做 论文 期间的 关心和帮助表示感谢. 作 者 要 感 谢 科 学 与 工程 计 算国 家 重点 实 验室 的 张时 珍 老 师 和白 ，英 老师，感谢他们对我学业和生活上的帮助. 最后， 作者愿意把本文献给他的家人 一 亲爱的父亲， 母亲和爱人 庞海英，正是他们对我一如既往的全力支持，热情鼓励和他们最无私 最伟大的爱支持着我在自己选择的道路上坚定地走下去. 第一章
14、引言 在这一 章里， 我们将简 要地介 绍支撑向量机理 论的 现状以 及其与 最优化数学理论的联系. 经 1 .1 机器学习理 论简介 人类 文明 之所以 能够发展到今天， 一个很重要的原因 就是人具有 很强的学习 能力. 这种能力帮助人们对未知 世界 做出 正确的判断， 在 人们 对计 算机人工 智能的探索中 ， 希望计算机能够 模拟 人类的 这种学 习能力，这就是我们所谓的机器学习问题我们的目的是通过对己知 的数 据进行分析， 发现数据之间内在的联系 或规律， 从而对未知数据 进行判断. 在大约4 0 年以 前，F . R o s e n b la t t 1 1 1 提出了第 一个学习机
15、 器的 模 型，称作感知器.这标志着人们对学习过程进行数学研究的第一步. R o s e n b la t 做的 不同 寻常 的事就 是把这个 模型表现为 一个计 算机程序， 并且 通过实 验说明 这个感知 器模型的可 推广性.在R o s e n b la tt 的感知 器实验后， 人们很 快提出 了其他类型的学习机器模 型. 这些模 型从一 开始就被用来解决实际问题，而没有被看作是学习现象的一般模型. R o s e n b l a t t 的第一个实验是针对数字识别问题做的.甚至在 8 0 到 9 0 年代，数字识别问题也一直是一个重要的研究方向.为了得到更好 的决策规则，现在人们甚至采
16、用数百万以上的几百维观测数据.人工 智能的研究者在这 一领域里起到了很 大的 作用.值 得一 提的 是， 感知 器被改称为神 经网 络. 在 6 0 和7 0 年 代，学习问 题的主要目 标 是从少 量样本出 发寻找规则; 而 8 0 年代，目 标 变为研究人是 如何学习的. 这 些 研究 很多 是与生物生 理学者共同 进行的，但是 这并不一定是建立学 习机器的好方法. 1 9 8 4 年，V a lia n t 1 7 1 提出了可能 近似度模型 (P r o b a b ly A p p ro x i- m a t e ly C o r r e c t ， 简称P A C ) . 他使得人 工智能领域认识到统计学在机器 学习中的重要性 在过去的 1 0 几年中， 与神经网络相关的研究集中在对神经网络的 替代方法的研究上. 统计 学习理 论中的比 较高级的内 容吸引了很 多的 研究人员.在过去的几年里，结构风险最小化原则和最小描述长度原 则成了 一个研究热门. 在很多的实际问 题中， 神经网络都显示出了比 第一章 引言了 较好的 效果， 从这 个
