（运筹学与控制论专业论文）动态存储和在线学习的svm算法.pdf

摘要 近年来支持向量机取得了长足的发展，并广泛应用到模式识别、回归分析、 信号处理、函数估计等诸多领域，但仍有待进一步的研究和改善。 训练支持向量机可以归结为求解一个凸二次规划问题，而求解凸二次规划的 计算时间和对计算机内存的需求是随着样本数量的增加而显著增加的，因此一些 传统的求解凸二次规划的方法对于学习大规模的训练样本往往会失效。针对这个 问题，本文提出了一种动态存储的支持向量机算法。该算法采用有效集法求解凸 二次规划，并针对所要求解凸二次规划的特点，减小了有效集法中要求解的仅含 有等式约束凸二次规划的规模，从而很大程度上减小了求解凸二次规划的计算时 间；在对计算机内存的需求方面，该算法采用了一种动态存储核函数矩阵的方法， 很大程度上降低了算法对计算机内存的需求，因此该算法能够处理一些大规模的 训练数据。通过数值实验表明该算法与m a n a b 的s v m 工具包中的算法相比，无 论是在对计算机内存的需求还是计算时间上都有优势。此外，本文提出的算法在 求解凸二次规划时要首先确定初始可行点，为此，本文提出了一种初始可行点的 确定方法，进一步加快了学习的速度。 近几年，在线学习方法的应用越来越广泛。根据动态存储的支持向量机算法， 本文提出了一种在线s v m 算法，并根据支持向量的空间分布特点，提出了一种遗 忘准则，对在线s 算法进行了改进，数值实验结果表明算法是有效的。 关键词支持向量机：动态存储：在线学习：有效约束 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名 j 生蹶避韭。日 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇二掣翩躲盔盐啉蚰r 曰 1 1 引言 第1 章绪论 支持向量机( s u p p o n v e c t o rm a c h i n e ，简称s v 旧是在统计学习理论基础之上 发展起来的一种全新的机器学习方法。s “基于统计学习理论的结构风险最小 化原则，它将最大化分类间隔的思想和基于核函数的方法结合在起，表现出很 好的泛化能力，近年s v m 成为人们研究的热点。 1 2 研究课题背景与研究意义 支持向量机是一类新型机器学习方法，是数据挖掘中的一项新技术，是借助 于最优化方法解决机器学习问题的新工具。它最初于2 0 世纪9 0 年代由v a p 血提 出，近年在其理论研究和算法研究实现方面取得了突破性的进展，开始称为克服 “维数灾难”和“过学习”等困难的有力手段。 与传统统计学相比，统计学习理论( s t 撕s t i c a ll e a r n i n g 皿r y 或s l t ) 是一种 专门研究小样本情况下机器学习规律的理论。v a p n i k 等人从六、七十年代开始致 力于此方面的研究，到九十年代中期，随着其理论的不断发展和成熟，统计学习 理论开始受到越来越广泛的重视。统计学习理论是建立在一套较坚实的理论基础 之上的，为解决有限样本学习问题提供了个统一的框架，它能将很多现有方法 纳入其中，有望帮助解决许多原来难以解决的问题( 比如神经网络结构选择问题、 局部极小点问题等1 。支持向量机是建立在统计学习理论的v c 维和结构风险最小 化的原则的基础上，因此其具有坚实的理论基础。s v m 根据有限的样本信息在 学习模型的复杂性和学习能力之间寻求最佳折衷，因此具有很好的推广能力。目 前支持向量机广泛应用到了模式识别、回归分析、信号处理、函数估计等诸多领 域，并取得了很好的效果，有一些学者认为，统计学习理论和支持向量机正在成 为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发 为继神经网络研究之后新的研究热点，并将有力地推动机器学习理论和技术的发 展。 北京工业大学理学硕士学位论文 1 3 支持向量机的算法研究概况 支持向量机的训l 练过程可归结为一个求解凸二次规划的过程，求解过程中要 涉及到存储核函数矩阵的问题，但存储由4 0 0 0 个训练样本构成的核函数矩阵大约 需要1 2 8 兆的内存，所以在求解大规模的问题时，求解时间会很长，所需的内存 空间也会很大，以至于不能求解。为了克服这些困难，许多学者将很大的精力投 入到寻找快速有效的支持向量机训练方法，并取得了很多成果，主要分两类：选 块算法和分解算法。 ( 1 ) 选块算法。当训练样本增加时，凸二次规划的规模急剧增大，由于内存 和运算时间方面的限制无法用计算机正常处理。为此，c o r t e s 和v a p n i k 提出了处 理大规模训练集的s v m 选块训练算法。其基本思想是：去掉对应于非支持向量 的l a g r a n g e 乘子口：= 0 的那些训练点，而只对支持向量计算相应的l a 醉a ：n g e 乘子 口，。可将一个大型凸二次规划问题分解为一系列较小规模的凸二次规划问题。 但这种算法当支持向量很多时，求解速度就会下降，所需要的计算机内存也会增 加。 ( 2 ) 分解算法。q s u l l a 【4 1 等人证明了选块算法的收敛性，并提出了新的s v m 算法，固定分解算法。基本思想是建立一个工作集( w o 越n gs c t ) ，保持其大小 不变，在解决每个凸二次规划子问题时，先从工作集中移走一个样本，并加入一 个不满足硒汀条件的样本，再进行优化。该算法效率较低，因为在每一步中，进 行一次凸二次规划问题的最优化只能使一个样本符合k k t 条件。q s u n a 的工作集 选择算法不是最优的，但是他的工作可以说是开创性的，为后来的研究奠定了基 础。 j o a c h i m s l 5 1 提出一种解决大型s v m 学习的算法，称为s l i g h t 。该算法实 际上是q s u n a 方法的推广。其基本思想是，如果存在不满足瞄( t 条件的样本，则 以某种方式选择g 个样本作为工作集，其它样本保持不变，在这个工作集上解决 凸二次规划问题。重复这一过程，直至所有样本都满足鼬汀条件。 p 1 a t t 提出了具有深远影响意义的s m o ( s e q u e n t i a l m i n i m a l o p t i m i z a t i o n 序贯 最小优化) 算法。该算法可以说是q s u n a 分解算法的一个特例，工作集中只有2 个样本，其优点是针对2 个样本的凸二次规划问题可以有解析解的形式，从而避 2 第1 章绪论 免了多样本情况下的数值解不稳定及耗时问题，同时该算法也不需要存储传统方 法要存储的核函数矩阵，特别适合稀疏样本的情况。并且其工作集的选择不是传 统的最速下降法，而是启发式。通过两个嵌套的循环来寻找待优化的样本，然后 在内环中选择另一个样本，完成一次优化，再循环，进行下一次优化，直到全部 样本都满足最优条件。s s k e e r t l l i 等通过对s m o 算法的分析，在文献 6 中提出 了重大改进，即在判别最优条件时用两个阈值代替一个阀值，从而使算法更加合 理、更快。 此外对于支持向量机算法的研究，学者们还提出了增量算法、多变量更新算 法。 ( 3 ) 增量算法。训练方式是在训练样本单个输入的情况下训l 练，其训练样本 总的个数是未知的，最典型的应用是系统的在线辨识。在第4 章第1 节有详细介绍。 ( 4 ) 多变量更新算法。分解算法虽然取得了成功，大大减少了s v m 学习算法 的计算复杂性，但是这种算法的具体实施比较困难，具有相当的经验启发成分， 尤其是工作集的选择和迭代策略的确定。为了克服这个难题，很多学者提出了多 变量迭代更新算法，它不像分解算法一次迭代只更新工作集的学习系数一样，而 是更新全部训练集的学习系数。 1 4 支持向量机其他方面的发展 1 4 1 改进的支持向量机问题 人们通过各种方法使标准的支持向量机中的最优化问题变形，产生出能解决 某一类问题或在某方面有优势的算法，其中比较典型的有以下几种： ( 1 ) f u s s y - s v m ，冯瑞等人研究了模糊集支持向量机。提出了用模糊支持 向量分类器对输入数据进行预处理，并以得到的模糊隶属度作为分类依据。文献 【7 】中提出了模糊支持向量机方法，在应用中取得了一定的效果。 ( 2 ) y s v m ：标准的支持向量机需要选取合适的参数c ，定性地讲c 的值 有着咀确的含义，选取值越大，意味着更强调最小化训练错误，但定量地讲本身 没有确切的含义，所以c 的取值在实际应用中比较困难，因此在文献 1 2 中提出 了，一s v m 方法，用参数y 代替c ，且，有直观的上的意义。 从图( 2 1 ) 可以看出，显然有许多直线能将两类点正确分开，接下来产生了一 个问题：哪条直线更好一些? 设为一条能够将两类点正确划分的直线，当直 线z 。的法方向w 已经确定时，f 。沿着两个方向平移，直到分别碰到两类点，这样 就得到另外两条直线，：，。，可见在，之间的任何一条直线都能够将两类点正确 划分，不过，显然，：，z ，中间的直线，最好。这样问题就转化为怎么确定划分直线 的法方向w 。我们称，：，之间的距离称为与法方向w 相对应的间隔，应当选取 使得间隔最大的那个法方向。 当法方向影给定以后，不妨设f 2 ，。分别为( 谛- 石) + f = 麓和( 谛x ) + f = 七2 ， 调整f ，可以把两条直线分别表示为( 谛z ) + i = 一e 和( 谛- x ) + f = ，显然，：，f 3 中 间的直线，：( 罚x ) + i eo 作为划分直线。令w = 詈，6 = 睾，表示k l 的两式可以 等价表示为 ( w x ) + 6 = 一1 和( w x ) + 6 = 1 可以计算得到，：，之间的距离为 2 因此用极大化间隔的思想得到下面的最优化问题 骢珈2 5 j _ y 裭套莎酿 藤霸一蕊。来讲疆硫箍缸p嘉鳃罂；剥慝崭菇殿砖蝴矧一埘魁薷型噬j药 蜮詈捌ji!坦藤器越蘸i丽孵睡鲋籀鲥嚣葬鞭矸鲥艘q积眨口弛捌雌酗蜮囊鞋鼬裂 驰墅邕群。蛰转强一 。般来讲，当输入x 与某个算的距离很近时，x 和 x，对应输出的y和”应该相同，我们自然希望我们的决策函数具有这种 北京工业大学稼学硕士擎位论文 设x = 葺+ 缸，其中| | 缸 r ，显然只要， o ，舀为任意蹙数。 ( b ) g a u s 。径翔基棱函数世( 墨：e x p 卜l 苎二垩) 仃。 ( c ) 竹维傅立时核函数匿( x ，x ) = 建墨( _ ，工，) 其中 l l x 2 ( 并l ，x 2 ，x 3 ，南) x = ( x i ，x ；，x ；一，) 墨( d ，6 ) = 可是满足o 口 o ，c o ，并疆此计算 n 邶一譬) 一笠_ y 属胃硇； ( 5 ) 构造决策函数，( z ) = s 牡( 薯a ? 弘蜀( x ) + 6 ( 5 ) 构造决策函数，( z ) = s 牡l a ? 弘蜀( t ，x ) + 6 i i o l 4 3 4 数值实验 实验环境：w i n d o wx p 系统，p 4 ，m a t l a b 6 5 此数值实验蝣然采用3 。2 5 实验一中用猁的数据，模拟在线学习。此数据共 有3 1 9 6 个样本，随机选取6 9 6 个样本作为测试数据。然后从剩下2 5 0 0 个数据中 随机选取2 3 0 0 个样本，先对其进行学习。然后再加入剩下的2 0 0 个样本。 实验结果：应羯基予兹态存储s 懈算法豹在线s 硼算法，与从毅学习相比， 所用的训练 r 百r 可飞r ti f 3 3 矗 4 t 5 a 图4 3 线性可分离的样本 f i g 4 - 3 址es 雠率l e so fl h 档s 印拯t i o n ( b ) 训练全部样本得到的支持向量，图4 4 中用“o ” 1 o 5 e 0 盎，5 圈4 - 4 训练得到的支持向量 f i g 4 4t h es u p p o r tv e c t o ro b t a i n e db yl e a r r l i n g 选取不同炎别彼此靠近的样本，用“o ”栎出。 计l吲i 鹕 o ( b ) 训练全部样本褥到豹支持向量，恩中恩“o ”标出 窝4 7 训练得到的支待淘量 f i g 4 _ 7m es u p p o r tv e c t o r0 b t 如e d b y 1 e 蛐1 i i l g 选取不同类掰彼此靠近的样本，月“o ”标出。 图4 - 8 获得的彼此靠近的样本 f i g 4 8o b t a i m i n gt h es a m p l e s c 1 0 8 i n gw i e a c ho t l l e r 茜；_|j小jjj夺_0o舭 第4 章基于动态存储的在线s v m 算法 ( 2 ) 如果m a x o ，并据此计算 牡”( 1 一务一杰胪淑b 哟； ( 6 ) 梅造决策丞数厂( x ) = s 翳( 喜疗玩耍瓯+ 6 。 、r = l， 4 4 5 数值实验 实验环境：i n d o wx p 系统，p 4 ，m a t l a b 6 5 此实验仍然用3 2 5 实验一中用到数据，模拟在线学习。设定m a x = 2 3 0 0 ， c = 4 0 。同4 3 4 中豹实验一样，随机选取6 9 6 个样本作为、攫l 试数据，然后从剩 下2 5 0 0 个数据随机选取2 3 0 0 个样本，先对其进行学习。然后再加入剩下的2 0 0 个样本。采取从新学习和本文提出的在线学习方法进行学习。 实验结柒： 离斯核s i g m 铲o 6 ，c = 7 0 0 表4 - 2 利用c h e s 8 数据使用两种方法的结果比较 t a b l e4 2c o m p 硪s o no f 谯er e s 棚船曲t a i n e db yt 、om e t 量l o 蠡u s i n gt 圭狞吐e s sd 曩f a 方法l 谵练时润 正确率支持向照个数 从新学习 4 2 5 s8 6 3 5 1 2 4 改进后基于动态荐储的淼线s v 骐算法l2 0 9 6 9 s8 6 2 1 1 1 3 4 5 本耄小结 通过嵇始可行点的构造，可将动态存储的s v m 算法运用于禚线学习，握此 本文提出了基于动态霹罐的在线s v m 算法，数值实验表明冀法是有效的。睫彗 时间的推移，样本无限增多，因此本文对算法进行了改进，即根据支持向蓬空间 分布特点，绘出一个遗忘准则，舍去一部分样本。但此遗忘准则只在一定程度上 减小了瞻予会弃样本丽造成的分类精度降低的问题，随着舍去样本的增多，也会 影响分类精度，所以算法在这个方面还需要改进。 。7 1 6 7 l 葚 1 4 郑舂颗种改进的s 算法航空计算技术v 0 1 3 5 ，n o 2 ，j m ，2 0 0 5 1 5 涯西莉，焦李戒。一种基于马氏躐离的支持向量快速提取算法，西安墩子科按大学学报， 2 0 0 4 年8 胃第3 l 卷第4 期 1 6 薛毅最优化原理与方法北京工业大学出版社2 0 0 1 年2 月 1 7k w l a uq h w u o “n et r a m i 端o fs u p p o r tv e c t o rc l a s s i 最e r 潮p 甜e nr e c o 辨j t i o n ，2 3 ， 3 6 ：1 9 】3 * 1 9 2 0 。 1 8 史朝辉，王晓丹，杨建勋一种s v m 增量训练淘汰算法计算工程与应2 0 0 5 2 3 1 9 代六玲，黄河燕，陈肇雄一种文本分类的在线s v m 学习算法中文信感学报2 0 0 5 年第1 9 襁第5 期 2 0t j o a c h i m s e s 廿m a n n g 出eg e n e r a l i 盟虹曲p e 汀c 毗矬a n c eo f as v me 塌c i e n 廿y a 】i n ：n o c ，o f 畦l e1 7 t hh t c o n f o nm a c h m el e a m i n g c 】m o 堵a nk a u 蜘a n n ，2 0 0 0 2 la 虢b e n - h u r d 枷dh o m ，h a v at s i e g e l 靴a 越a n dv l a d 抛i i rv a p n i k s 坤p o r tv e c t o f c l u s t e r i i 】g j o u m a lo f m a c h i l l el e a m i 工l g r e s e a r c h2 ( 2 0 0 1 ) ：1 2 5 1 3 7 2 2b s c h o o l k o p ta s m o l a r w i l i i a i i l s o n 甜dp l b a r h e t t n e ws u p p o r tv e c t o r 趣| o r l 吐l m s 烈e u c o c tt e 娃西c 啦r e p b r t n c - t r _ 9 8 一0 3 1 ，r o y a l h o l l o w a y c o l l e g e ，u 试v e r s i t y o f l o n d o n ，u k ，1 9 9 8 p u b u s h e d 血n e u r a lc o m p u t “o n1 2 ( 5 ) ：1 2 0 7 1 2 4 5 ，2 0 0 0 2 3n e a y a t ，m c h e r i 峨c y s u e l l ，k m o d - a 仰。呻a r 锄e 诧rs v mk e m e lf o rp a 札e mr e c o g n j 廿o n ， i b e e 2 0 0 2 2 4o l 押i e rc h a p e l l e ，v l a d i m i rv a p n i k ，o l i v i e rb o u g q u e t 雒ds a y a nm u k l l 嘲e e c h o o s m gm p l e p a r 呦砷e r s f o rs u p p o nv e c t o rm a c h m e s m a c h i n el e 黜j n g k 1 u w e ra c a d 咖i cp u b l i s h e r s ， h i n 曲娜，m a ，u s a 2 0 0 2 ，v o l u m e4 6 ，i s s u el - 3 ：1 3 l - 1 5 9 2