（计算机软件与理论专业论文）多类模式的支持向量机及其在笔迹鉴定中的应用.pdf

中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 论文题目： 专业： 硕士生： 指导老师： 多类模式的支持向量机及其在笔迹鉴定中的应用 计算机软件与理论 肖国华 欧贵文副教授 摘要 近年来为研究有限样本情况下的统计模式识别和更广泛的机器学习问题，发 展了一种新的模式识别方法支持向量机，它能够较好的解决小样本学习问 题。支持向量机是一个典型的两类模式分类器，对于多类模式下的研究还是一个 开放性的问题，因而本文的重点集中于多类模式下的支持向量机的研究，包括对 支持向量机的核空间理论和优化算法的相关研究及其在笔迹鉴定中的应用。 笔迹鉴定在安全保卫和司法等方面有重要的现实意义。联机的笔迹鉴定技术 已趋于成熟，但是脱机的文本无关的笔迹鉴定还处在研究阶段，将多类模式的文 本无关的笔迹鉴定推向应用的主要问题是训练样本的有限和识别正确率之间的 矛盾，多类模式下的支持向量机可以较好的解决这个矛盾。 本文的研究内容有：支持向量机的核空间理论和优化算法的选择：在原有算 法的基础上，提出了一种通过支持向量机的两类模式构造多类模式下的分类器的 方法：将支持向量机作为分类器引入到文本无关的笔迹鉴定系统的研究中；同时 对笔迹图像的预处理过程提出了相应的改进算法。 在本文的实验中，采集到1 7 个人文本内容不同的笔迹图像作为实验对象。 在小样本训练空间的前提下，通过和传统的模式分类方法比较( 例如：加权欧氏 距离) ，采用支持向量机的笔迹鉴定系统的正确率可以提高1 0 左右。本文的部 分结果，曾在第1 1 届全国图像图形学术论文会议上宣读，并在核心期刊小型 微型计算机系统上发表。从初步的实验结果看，支持向量机理论为脱机的笔迹 鉴定系统推向应用提供了一个有效的方法。 关键字：支持向量机，笔迹鉴定，图像预处理，多通道g a b o r 滤波器 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 t i t l e ： m u l t i c l a s ss u p p o r tv e c t o rm a c h i n e sf o rt e x ti n d e p e n d e n t h a n d w r i t i n g i d e n t i f i c a t i o ns y s t e m m a j o r ：c o m p u t e r s o f t w a r ea n d t h e o r y n a m e ：x i a og u o h u a s u p e r v i s o r ：o u g u i w e n a b s t r a c t s u p p o a v e c t o r m a c h i n e s ( s v m ) r e p r e s e n t s an e w a p p r o a c h t o p a t t e r n c l a s s i f i c a t i o nw h i c hh a sr e c e n t l ya t t r a c t e dag r e a td e a lo fi n t e r e s ti nt h em a c h i n e l e a r n i n gc o m m u n i t y s v m i sa t y p i c a lb i n a r y c l a s s c l a s s i f i e r , b u t m u l t i - c l a s s c l a s s i f i e r sb a s e do ns v i v la l ed i f f i c u l tp r o b l e m s s ot h i st h e s i si sm a i n l yf o c u s e do n h a n d w r i t i n gi d e n t i f i c a t i o ns y s t e m b a s e do ns v i v la n dm u l t i c l a s ss v l v li n c l u d i n g k e r n e lf u n c t i o na n do p t i m i z a t i o nt h e o r y h a n d w r i t i n gi d e n t i f i c a t i o ns y s t e m h a si m p o r t a n tm e a n i n gi ns e c u r i t ya n d j u s t i c e o n - l i n e h a n d w r i t i n g i d e n t i f i c a t i o n s y s t e m h a sb e e n p r a c t i c a b l e ，b u t o f f - l i n e h a n d w r i t i n gi d e n t i f i c a t i o ns y s t e m i ss t u d y i n g t h em a i np r o b l e mi no f f - l i n es y s t e mi s t h ec o n f l i c tb e t w e e ns a m p l e sl i m i ta n dc l a s s i f i c a t i o nr a t e s ，m u l t i c l a s ss v v lm a y s o l v et h i sc o n f l i c t i nt h i st h e s i s ，t h er e s e a r c hm a i n l yc o n s i s t so ft h ef o l l o w i n gp a r t s ：s e l e c t i n gk e r n e l f u n c t i o na n do p t i m i z a t i o na r i t h m e t i ca b o u ts v m ；p u t t i n gf o r w a r dan e wm e t h o d w h i c hd e s i g n sm u l t i c l a s sc l a s s i f i e r sa b o v eb i n a r y c l a s sc l a s s i f i e r s ；d e v e l o p i n ga h a n d w r i t i n g i d e n t i f i c a t i o n s y s t e mb a s e do ns v m ；d e v e l o p i n g am e t h o dw h i c h p r e p r o c e s st h ec h a r a c t e ri m a g e s i nt h i st h e s i s ，o n eh u n d r e da n ds e v e n t yh a n d w r i t i n gi m a g e sw e r ec o l l e c t e df r o m s e v e n t e e np e r s o n s c o m p a r i n gt ot r a d i t i o n a lc l a s s i f i e r s ，f o re x a m p l e ，w e d ，s v mm a y i m p r o v e t h ec l a s s i f i c a t i o nr a t e si nh a n d w r i t i n gi d e n t i f i c a t i o ns y s t e mw h e nt h es a m p l e s a r el i m i t e d b yv i r t u eo ft h i sm e t h o d ，ap a p e ri se m b o d i e db ym i n i m i c r os y s t e m s ， a n dt h ea u t h o rt o o k p a r ti nn c i g i n2 0 0 3 a c c o r d i n gt ot h er e s u l to ft h e s i s ，s v mm a y b e c o m ean e w a p p r o a c h t or e s e a r c ho fh a n d w r i t i n gi d e n t i f i c a t i o ns y s t e m k e y w o r d s ： s u p p o r t v e c t o rm a c h i n e s ，h a n d w r i t i n gi d e n t i f i c a t i o n ，i m a g ep r e p r o c e s s ，m u l t i 。c h a n n e l g a b o r f i l t e r i n g 中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 v i 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 1 1 问题描述 第1 章概述 笔迹鉴定是通过分析手写字符的书写风格来判断书写人身份的一门技术。 正如俗话所说的“字如其人”，每个人写的字都有自己的特征。这种方法在政府、 法律和贸易中仍然广泛地被用来鉴定人的身份。高准确率的笔迹鉴别会使我们的 生活质量得到提高。从身份识别的角度，笔迹是一种稳定的行为特征，笔迹的获 取具有非侵犯性( 或非触性) ，是易为人所接受，非常有应用前景的身份识别方 式。 随着计算机技术和网络技术的发展和普及，笔迹鉴别技术的应用领域更为宽 广，突破了原有的应用范畴，比如，计算机登录、信息网入网、信用卡签字、电 子商务、合同文书、遗嘱、匿名信件、医疗纠纷处方、授权委托书的法庭鉴定、 银行支票的签名鉴定等等，广泛应用于公安、安全、法院、保险、银行及电子 商务等方面。 笔迹鉴定根据在线与否的情况分为两类：联机笔迹鉴定和脱机笔迹鉴定。联 机笔迹鉴定即从专用的输入设备( 如写字板和光笔) 输入文字，通过机器辨别该 笔迹对照系统已有的数据模型来辨别是否为同一个人的笔迹。联机笔迹鉴定技术 已趋于成熟，已有多项产品商业化。应用最为广泛的是签名识别，签名识别也被 称为签名力学辩识( d y n a m i cs i g n a t u r ev e r i f i c a t i o n d s v ) ，它分析的是笔的 移动，例如加速度、压力、方向以及笔划的长度，而非签名的图像本身。手写签 名识别技术正是通过计算机把手写签名的图像、笔顺、速度和压力等信息与真实 签名样本进行比对，以实时鉴别手写签名真伪的技术。签名力学的关键在于区分 出不同的签名部分，有些是习惯性的，而另一些在每次签名时都不同。签名的使 用已经被广泛地接受，应用范围从独立宣言到信用卡都可见到。手写签名识别技 术是公认的更容易被大众接受的一种身份认证方式，也是目前计算机模式识别领 中山大学硕士学位论文多类闽题的支持向量机及其在笔迹鉴定中的应用 域的前沿课题。签名识别主要应用于电子政务、电子商务、金融机构等系统。针 对不同的用户，提供各类具体解决方案。 脱机笔迹鉴定是从日常的手写文件、单据通过扫描仪扫描到计算机中，然后 对文字的鉴定实现对手写入的身份的确认。据了解，以前公安部门需要通过笔迹 来鉴定犯罪嫌疑人的时候主要凭文检专家的双眼，这种旧的笔迹检验手段不仅费 时费力，而且对文检鉴定结论的科学性存有疑惑。脱机笔迹鉴定系统针对公、检、 法可疑文档笔迹鉴定应用背景与市场需求，提出了利用计算机在人工智能方面的 能力，实现笔迹鉴别的自动化。该脱机笔迹鉴定系统的开发使用不仅使文检人员 从茫茫“字海”中解脱出来，而且使鉴定结论更具科学性。 由于脱机笔迹鉴定中手写人的笔迹来源广泛，而且具有很大的随意性，同时 扫描笔迹的时候会带来一定的噪音污染，因此它的总体识别率还不是很高。采用 加权欧氏距离( w e d ) 作为分类器，在训练样本量足够大的时候能够取得比较 好的正确识别率【i j ，识别正确率可以达到9 4 2 ；而在调练样本较少的情况下， 识别的正确率急剧下降( 见表l 一1 ) 。 表1 1 采用w e d 作为分类器的识别正确率 t a b l e1 。1r e s u l t sb a s e do nw e d l训练样本特征个数 1 01 0 1 52 52 5 l 待识别样本特征个数 351 0 1 02 5 i识别正确率 7 5 5 7 7 8 8 3 4 8 7 4 9 3 5 但是在很多脱机笔迹鉴别系统中，训练样本是极其有限的，例如在公安部门 的犯罪嫌疑人的身份确认时，公安部门可能只能得到少量的嫌疑人的笔迹，这个 时候就要求系统能够在有限样本的情况下取得令人满意的识别正确率。为了解决 有限样本和理想识别正确率的矛盾，本文首次将支持向量机( s u p p o r t v e c t o r m a c h i n e s 简称s v m ) 作为分类器引入到脱机笔迹鉴别系统。近年来为研究有限 样本情况下的统计模式识别和更广泛的机器学习问题，发展了一种新的模式识别 方法一支持向量机【2 8 】，它能够较好的解决小样本学习问题。目前，支持向量 机已经成为国际上机器学习领域新的研究热点。 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 1 2 支持向量机( s v m ) 的研究现状 基于结构化风险最小化方法的统计学习理论是一种专门的小样本统计理论。 它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一 个较好的理论框架，同时也发展了一种新的模式识别方法一一支持向量机。支持 向量机是由v v a p n i k 与其领导的贝尔实验室的小组 v a p n i k ，1 9 9 5 ；c o r t e s a n d v a p n i k ，1 9 9 5 ；b u r g e s ，1 9 9 8 】_ 。起开发出来的一种新的机器学习技术，是近年来在 统计学习理论的基础上发展起来的一种新的模式识别方法，在解决小样本、非线 性及高维模式识别问题中表现出许多特有的优势。由于其出色的学习性能，该技 术已成为机器学习界的研究热点，并在很多领域都得到了成功的应用，如人脸检 澳l j 9 】、手写体数字识别【1 0 】、文本自动分类【1 1 1 等。 s v m 是一种基于统计的学习方法，它是对结构化风险最小化归纳原则 ( s t r u c t o r a lr i s k m i n i m i z a t i o ni n d u c t i v ep r i n c i p l e ) 的近似，其理论基础是统计学习 理论 1 2 1 。s v m 根据结构风险最小化准则，在使调练样本分类误差极小化的前提 下，尽量提高分类器的泛化推广能力。其技术要点是：根据有限的样本信息，在 模型的复杂性和学习能力之间寻求最佳折衷点，以此寻求获得最好的推广能力。 从实施的角度，使得分隔特征空间中两类模式点的两个超平面之间的距离最大， 而且它能够保证得到的解为全局最优点，从而具有较好的泛化和推广能力。支持 向量机的主要优点有： 1 ) ：专门针对有限样本情况的，目标是得到现有信息下的最优解而不仅仅是 样本数趋于无穷大时的晟优值。 2 ) ：算法最终将转化成为在线性条件限制下的二次优化问题，从理论上说， 得到的是全局最优点，解决了在神经网络方法中无法避免的局部极值问题； 3 ) ：算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ， 在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能 保证机器有较好的推广能力，同时巧妙地解决了维数问题，其算法复杂废与特征 空间的维数无关。 由于s v m 找到的是全局最优解，因此，在很多间题上它都有着其他统计学 习技术所难以比拟的优越性，并已在一些领域获得了成功。但是，作为一种尚未 成熟的新技术，s v m 目前仍然存在着很多局限。 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 首先，最大的局限就在于核函数的选择。由于在核函数确定之后，用户只能 对参数c 进行调整，因此，核函数的选择对于s v m 的性能非常重要。目前已有 一些研究者对利用先验知识来进行核函数的选择进行了研究 1 3 1 4 】，但如何针对 特定问题选择最佳的核函数仍是个难以解决的问题。 其次，s v m 对两类模式下的划分问题已解决得非常好，但其对多类模式下 的划分问题及回归问题的处理能力仍有待进一步研究和改善。 最后，s v m 的训练速度极大地受到训练集规模的影响。对于超大规模的数 据集( 数百万支持向量) ，如何高效地进行训练和辨认也是一个需要研究的重要问 题。 1 3 笔迹鉴定 1 3 1 笔迹鉴定的主要分类 从笔迹鉴定的笔迹数据来源的角度来说可以将笔迹鉴定分为与文本相关的 ( t e x t d e p e n d e n t ) 笔迹鉴定和与文本无关的( t e x t i n d e p e n d e n t ) 笔迹鉴定两大类。一 幅笔迹图像实际上包含的信息有两部分：与笔迹所写的内容相关的信息和与手写 人特征相关的信息，目前尚没有什么方法可以把这两部分信息完全分离开来。因 此，一些手写人识别方法中将手写的内容固定，这样手写人识别的比较过程中就 可以抵消因手写笔迹内容引起的差异，这就是文本相关的笔迹鉴定。另一种方法 是通过对较大量的笔迹进行统计分析从而消除具体的笔迹手写内容引起的差异， 这就是文本无关的笔迹鉴定。这两种手写人识别各自有不同的应用，前者由于识 别所需的笔迹内容相对少，因此识别处理速度更快，适用于安全、金融等领域的 相关签名笔迹识别；而后者因为对识别条件的限制小，不需要指定的或者固定的 文本，因此在现实中有更广阔的应用。 笔迹鉴定从具体应用的角度可以分为两部分：笔迹辨认( h a n d w r i t i n g i d e n t i f i c a t i o n ) 和笔迹确认( h a n d w r i t i n gv e r i f i c a t i o n ) 。顾名思义，前者是根据一幅 笔迹图像从一个笔迹图像的集合中找出最可能的手写入，是一个n 分之一的问 题；而后者是根据一幅笔迹图像来判断是或者不是由某一个人写出来的，是一个 二分之一的问题。这两种笔迹鉴定在现实生活中有它们各自不同的应用，如警察 4 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 根据在匿名信件或者反动字报上的笔迹图像来寻找犯罪嫌疑人的过程，即应用了 笔迹辨认，而银行根据手写签名验证来进行账户操作则应用了文本相关笔迹确 认。本论文研究的重点是笔迹辨认。 1 3 2 笔迹鉴定的应用 随着经济的曰益发展，笔迹作为一种个人身份辨识的有效手段，在当今社会 中的作用越来越明显。利用验证人的笔迹特征来进行身份验证具有如下的优点： 第一：笔迹的反映性是笔迹鉴定的物质基础。书写习惯必然要在书写的笔迹 材料中不同程度地反映出来，是不依人的意志为转移的客观存在。它不仅在长篇 的、正常书写的笔迹材料中能反映出来，而且能在笔迹数量少和非正常的笔迹材 料中不同程度地反映出来，就是有故意伪装也不会彻底改变。 第二：笔迹的相对稳定性是笔迹鉴定的基本条件。一个人的笔迹在长时间内 不会发生重大变化，这是由于人的书写动力定性的守常性，语言文字的社会规范 与规则变化的缓慢性等，决定了一个人不同时期形成的笔迹虽有差别，但其本质 特征不变。 第三：笔迹的总体特殊性是笔迹鉴定的鉴别依据。这是由于个人的书写习惯 具有共同性与特殊性的双重属性，决定了不同人的笔迹特征既有相同又有差异， 而特征总和则各不相同。 第四：书写动力定型决定书写习惯。书写动力定型，是指自动支配和调节书 写活动的大脑皮层机能系统性的效应活动体系。人在书写练习过程中。大脑皮层 接受一定顺序出现的复合刺激。形成与之相适应的暂时联系( 条件反射) 系统。 经过反复的书写练习刺激，即可形成书写动力定型。书写习惯的生理机制就是建 立在条件反射基础上的书写动力定型。 第五：笔迹特征可以方便地实时采集并分析，采集的便利性也是在笔迹鉴定 可行性的基础，不会受到地域或者时间的限制。 鉴于采用笔迹特征来进行身份鉴别有上述的优点，主要的应用已经涉及了各 国政府和各个部门。其主要应用领域包括以下几个方面： 第一：各国之间的协议和备忘录的鉴定，国家文件和法律法规的颁发。 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 第二：银行个人支票的签署和兑换，都需经当事人的签名才有效。包括银行 的一些预约业务中的签名确认转账、汇款、余额通知、股票行情咨询，以及未来 可能出现的i n t e r n e t 信息服务中的网上签名身份确认。 第三：用特定人的笔迹来实现机密场所的出入人员检查等。 第四：在公安、司法领域，通过对作案者留下的笔迹进行检验，分析判断其 书写习惯的本质特征是否与嫌疑人笔迹相同，从而断定是否为同一人所写，常常 用于帮助擒拿、捕获各种从事匿名信制造。伪造发票、证件、文件和其他文字材 料的罪犯，从而协助公安部门侦破案件和法院进行判决。笔迹鉴定在犯罪侦破中 也有不可估量的作用。 1 3 3 笔迹鉴定的原理 笔迹鉴别的基本原理如图1 1 所示； 1 3 4 笔迹鉴定的难点 尽管目前笔迹鉴定技术已经取得了很大的进展，在实验室条件下已经取得了 很好的识别效果，但将笔迹鉴定大规模地运用到实应用中仍有很长的一段路要 走。这主要是因为实验室条件和实际条件有很大的差异。一方面，实验室条件较 少考虑到笔迹图像存在较多噪声的问题，而在实际应用中，噪声是不可避免的， 尤其在一些特殊应用中。例如银行签名的纸张背景的噪声，手写纸张的背景存在 行或者格的线条等等。又例如，i n t e m e t 的信息服务中，图像通过通讯线路传播， 不可避免地引入一些随机噪声。另一方面。实验室里使用到的笔迹鉴定时集合往 往是比较小的，而在实际应用中手写人集合可能非常大，当手写人集合扩大时， 不管是系统效率，还是识别率往往会急剧变化。具体来说，笔迹鉴定的难点包括 以下四个方面： 第：手写笔迹图像信号中既包含了手写人所说的内容信息，也包含了手写 人的个性信息，是笔迹信息和手写人个性信息的混合体，而目前还没有好的方法 将这两者完全分离开来。 第二：手写人的笔迹常常与环境、情绪、健康状况等有密切关系，具有长时 变动特性，会随着时间和年龄的变化而变化。 6 中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 图1 - 1 笔迹鉴别原理图 f i g 1 - 1t h e o r y o f h a n d w r i t i n gi d e n t i f i c a t i o ns y s t e m 第三：笔迹往往是可以模仿的，并且使用扫描或者临摹的方法可以窃取他人 的签名字迹，使得笔迹鉴定在身份验证方面的可靠性降低。 第四：通过扫描时，不可避免地带来背景噪声，并且，不同的背景所带来的 噪声情况可能是不同的，即使是同一台扫描仪在不同时间的扫描，其噪声也往往 是不同的。 尽管笔记鉴定有一定的难度，但笔迹的特征代表性是笔迹鉴定的物质基础。 书写习惯必然会在书写的笔迹材料中不同程度地反映出来，是不依人的意志为转 中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 移的客观存在。它不仅在长篇的、正常书写的笔迹材料中能反映出来，而且能在 笔迹数量少和非正常的笔迹材料中不同程度地反映出来。 在目前没有将手写人笔迹的个性特征从笔迹特征中分离出来的较好办法时， 笔迹鉴定的方法主要基于两大类：第一类所采用的是固定文本内容，从而得出手 写人个性特征的方法( 即与文本相关的笔迹识别) ，第二类是采用不固定文本内 容，从笔迹图像信号的统计信息中得出手写人个性特征的方法( 即与文本无关的 手写人识别) 。本文中讨论的基于多通道g a b o r 滤波器的笔迹鉴定方法即属于后 面一种情况。 1 4 本文的研究内容 本文研究的内容包括： 第一：研究统计学习理论和支持向量机的基本理论，研究支持向量机的核空 间理论和优化算法，根据笔迹鉴别系统的实际情况，选择恰当的核函数和优化算 法来训练支持向量机分类器。 第二：支持向量机属于典型的两类分类器，对于多类模式下的分类情况需要 其他方法辅助解决，在现在的研究情况下，支持向量机有三种策略来解决多类分 类情况：1 一a r 算法、1 - a ，l 算法和二叉树型的多级分类算法，本文在综合1 - a - l 算法和二叉树型的多级分类算法的优点的基础上提出了一种改进的二叉树型的 多级分类算法。 第三：在对支持向量机进行充分的理论研究的基础上，本文第一次把支持向 量机作为分类器引入笔迹鉴定之中，开发出基于支持向量机的文本无关的笔迹鉴 定系统，取得了优异的实验结果。 第四；在笔迹鉴定系统的研究和笔迹图像的预处理中，由于手写的内容可以 是文字或其它任意符号，文字或符号的尺寸是任意的，问题比较复杂，使得预处 理的工作非常困难。通常采用投影直方1 虱 1 5 1 来解决这个问题。对于西文，文献 【1 5 】的方法可以成功，但是对于中文情况要复杂很多，尤其是当笔迹的每行互相 交错的时候，该算法就会失败。为了解决这个问题，本文根据中文的特点，在原 来的基础上提出了投影直方图的改进方法。 8 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 本文的大致内容如下：第2 章主要研究了统计学习理论和支持向量机的基本 理论：第3 章主要研究了支持向量机的核空间理论和优化算法；第4 章主要研究 了支持向量级的分类构成情况：两类模式下的构成情况和多类模式下的构成情 况，同时提出了改进后的二叉树型的多级分类构成：第5 章主要研究了基于支持 向量机的文本无关的笔迹鉴定系统的算法构成和实现技术；第6 章主要介绍了作 者所实现的笔迹鉴定系统的设计方案和实现细节，同时给出了详细的实验结果， 并对结果进行分析和对比，得出结论，最后对未来的工作进行了展望。 9 中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 第2 章统计学习理论和支持向量机的基本理论 支持向量机( s v m ) 的理论基础来自于v a p n i k 等提出的统计学习理论，它的 基本思想是，对于一个给定的具有有限数量训练样本的学习任务，如何在准确性 ( 对于给定训练集) 和机器容量( 机器可无错误地学习任意训练集的能力) 进行 折衷，以得到最佳的推广( g e n e r a l i z a t i o n ) 性能。在本章中，我们将首先介绍统 计学习理论，给出s v m 的理论基础；然后介绍s v m 的具体实现；最后介绍s v m 目前常用的训练算法。 2 1 统计学习理论 2 1 1 经验风险最小化归纳法 我们针对典型的二元模式识别问题进行讨论。设给定的训练集为 ( x l ，y t ) ，( x 2 ，y 2 ) ，( x i ，y 1 ) ，x r 8 ，y f + i ，一l ( 2 ，1 ) 训练样本与测试样本都满足一个未知的联合概率p ( x ) 。 通过一旗函数 ，( x ，口) ，口a 进行学 - 3 ，学习的目的是确定参数口。通常称 f ( x ，口) 为假设( h y p o t h e s i s ) ，称f f ( x ，d ) ，口a ) 为假设空间( h y p o t h e s i ss p a c e ) ， 记为h 。对于一个已训练的机器，它的测试错误的期望为 r ( g ) = 一l y 一，( x ，酬卯( x ，y ) ( 2 2 ) 尺 ) 称为期望风险。由于p f x ) - 未知，因此无法直接计算r ) 。但是，对 于给定的训练集，我们可定义经验风险足 ) ( 咖寺酗叫x f ，口) i 3 对于一个给定的训练集和o t ，尺( 口) 是确定的。我们通常将上式中的 1 0 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 i 1 | ) ，。一，( x ；，口) i 称为损失函数。 ( 2 4 ) 大数定理可保证随着训练样本数目的增加，r 。) 可收敛于r ) 。经验风 险最小化归纳法( e r m i n d u c t i v e p r i n c i p l e ) 就是用经验风险r e m p ( 口) 代替期望风 险r ( c t ) ，用使经验风险g e t u p ) 最小的f ( x ，) 来近似使期望风险r ( 口) 最小的 f ( x ，) 。e r m 建立在一个基本假设上，即如果尺。( o r ) t 渐r ( o t ) ，则e e r n p ) 的最小值收敛于r ) 的最小值。这也称之为e r m 是收敛的。v a p n i k 和 c h e r v o n e n k i s v a p n i k ，1 9 9 5 】证明，e r m 收敛的充要条件是也。 ) 依概率一致收 敛于r ( c o 。 2 1 2v c 维数与v c 上界 学习系统的容量对其泛化能力有重要影响【1 6 1 8 1 。低容量学习系统只需要 较小的训练集，高容量学习系统则需要较大的训练集，但其所获的解将优于前者。 对给定训练集来说，高容量学习系统的训练集误差和测试集误差之间的差别将大 于低容量学习系统。v a p n i k 【1 8 】指出，对学习系统来说，训练集误差与测试集 误差之间的差别是训练集规模的函数，该函数可以由学习系统的v c 维表征。换 言之，v c 维表征了学习系统的容量。 a n t h o n y 【1 9 】将v c 维定义为：设，为一个从n 维向量集x 至t l o ，1 ) 的函数 族，则，的v c 维为x 的子集e 的最大元素数，其中e 满足：对于任意s e ， 总存在函数工f ，使得当工s 时五0 ) = 1 ，x 芒s 但x e 时工0 ) = o 。 v c 维可作为函数族f 复杂度的度量，它是一个自然数，其值有可能为无穷 大，它表示无论以何种组合方式出现均可被函数族f 正确划分为两类的向量个数 的最大值。对于实函数族，可定义相应的指示函数族，该指示函数族的v c 维即 为原实函数族的v c 维。 为便于讨论，我们针对典型的二元模式识别问题进行分析。设给定训练集为 0 l ，) 1 ) ，y 2 ) ，y t ) ，其中靖r n ，y 0 ，1 。显然，x i 是一个n 维输入 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 向量，y 为二值期望输出。再假设训练样本与测试样本均满足样本空间的实际概 率分布p ( x ，y ) 。 对基于统计的学习方法来说，学习系统可以由一族二值函数t f ( x ，叻，口a 表征，其中参数羽以唯一确定函数苁) ，a 为撕有可能的取值集合。因此，【，b ， 国，口a 的v c 维也表征了该学习系统的复杂度，即学习系统的最大学习能力， 我们称其为该学习系统的v c 维。学习的目的就是通过选择一个参数矿，使得学 习系统的输出兵h 与期望输出y 之间的误差概率最小化，即出错率最小化。 出错率也称为期望风险( e x p e c t e dr i s k ) ，如式( 2 5 ) 所示： 尺( 口) = 片i y 一，( x ，口) i d 尸( x ，y ) ( 2 5 ) 其中p ( x ，y ) 为样本空间的实际概率分布。由于p ( x ，y ) 通常是未知的，因此无 法直接计算r ( 国。但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) r 。w ( 却是确定的，如式( 2 6 ) 所示： 咒，( g ) = 击f y ，一f ( x 。，口) ( 2 ，6 ) 其中国，m ) 为训练样本，z 为训练集中样本数，即训练集规模。由数理统计中 的大数定理可知，随着训练集规模的扩大，r 。( 叻将逐渐收敛于尺( 。 基于统计的学习方法大多建立在经验风险最小化原则( p r i n c i p l eo f e m p i r i c a l r i s km i n i m i z a t i o n ) 基础上，其思想就是利用经验风险r 。( 叻代替期望风险尺( ， 用使r 。( 最小的f ( x ，a 0 来近似使r ( 国最小的几x ，) 。这类方法有一个基本的 假设t l p 女d 果凡j ，t p ( 收敛于尺( ，则r 。w ( 叻的最小值收敛于r ( 功的最小值。 v a p n i k 与c h e r v o n e n k i s 2 0 】证明，该假设成立的充要条件是函数族l 触，田，盯e a l 的v c 维为有限值。 v a p n i k 【1 8 1 还证明，期望风险r ( 回满足一个上界，即任取，7 满足o 叩 l ， 下列边界以概率1 - 玎成立： r ( 叻r e i n p ( 口) + h ( 1 n ( 2 1 h ) _ 1 ) - l n ( r 4 ) ( 2 7 ) 其中h 为函数族【触。，口a 的v c 维，f 为训练集规模。 式( 2 7 ) 右侧第二项通常称为v c 置信度( v cc o n f i d e n c e ) 。由式( 2 7 ) 可以看 出，在学习系统v c 维与训练集规模的比值很大时，即使经验风险尺。( 叻较小。 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 也无法保证期望风险r ( 0 0 较小，即无法保证学习系统具有较好的泛化能力。因 此，要获得一个泛化性能较好的学习系统，就需要在学习系统的v c 维与训练集 规模之间达成一定的均衡。 2 1 3 结构风险最小化归纳法 e r m 原则在样本有限时是不合理的 需要同时最小化经验风险和置信范围。 其实，在传统方法中，选择学习模型和算法的过程就是调整置信范围的过程，如 果模型比较适合现有的训练样本，则可以取得比较好的效果，但因为缺乏理论指 导，这种选择只能依赖先验知识和经验。造成了如神经网络等方法对使用者“技 巧”的过分依赖。 统计学习理论提出了一种新的策略，在假设空间h 中定义一个函数集子集， s lc s 2c cs 。c ( 2 8 ) 每个h 。的v c 维数h 。为有限值，于是有 啊s h 2 h 。 ( 2 9 ) 对于每个子空间h 。，计算出它的，找到h 。中使经验风险最小的函数，得 到h 。中期望风险的最佳上界。在嵌套结构中，逐层进行这一过程，直至得到期 望风险的最佳上界。即使各个子集按照vc 维的大小排列，在每个子集中寻找最 小经验风险，在子集间折衷考虑经验风险和置信范围，以取得实际风险的最小， 如图2 1 所示。 欠学习过学习 风 险 图2 1 结构风险最小化归纳法示意图 f i g 2 - 1s k e t c hm a p o fs t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e 1 3 中山大学硕士学位论文多类阀题的支持向量机_ 及其在笔迹鉴定中的应用 这种方法称作结构风险最小化归纳法( s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ， 或译为有序风险最小化归纳法) 即s r m 归纳法。实现s r m 归纳法可以有2 种思 路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之 和最小的子集。显然这种方法比较费时，当子集数目很大甚至无穷时不可行。因 此有第2 种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验 风险( 如使训练误差为o ) ，然后只需选择适当的子集使置信范围最小，则这个子 集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种归纳 法的具体实现。 2 2 支持向量机( s v m ) 我们对s v m 的讨论从一种新的超平面一最佳超平面( o p t i m a lh y p e r p l a n e ) 开始，然后介绍如何构建线性s v m 来解决线性可分与线性不可分的问题，最后 将线性s v m 推广到非线性s v m 。 2 2 1 最佳超平面 设给定的训练集为 ( x l ，y i ) ，( x 2 ，y 2 ) ，( x f ，y ) ， x r ”，y + l ，一1 ( 2 1 0 ) 且可被一个超平面线性分割，该超平面记为 ( w x ) + 6 = 0( 2 1 1 ) 如果一个训练集中的向量能被一个超平面无错误地线性分割，且距该超平面 最近的向量之间的距离最大( 又称为间隔( m a r g i n ) 晟大) ，则称该超平面为最 佳超平面( 如图2 2 所示) 。其中距离超平面最近的点称为支持向量( s u p p o a v e c t o r ) 。 对于线性可分的情形，不失一般性，我们可假定训练集中的向量满足下列不 等式： w x f + ? 1l ，y i 。l 。 ( 2 1 2 ) w - x f + 6 - 1 fy j = 一1 我们称上述不等式为规范形式( c a n o n i c a lf o r m ) 。可将上述不等式合并为 1 4 中山大学硕士学位论文 多类问题的支持向量机及其在笔迹鉴定中的应用 o 图2 2 线性可分时的最佳超平面( 环绕的点为支持向量) f i g 2 - 2o p t i m a ls e p a r a t i n gh y p e r p l a n e o ft h el i n e a r l ys e p a r a b l ec a s e y l ( w x ；+ 扫) l i = l ，z ( 2 1 3 ) 于是构造最佳超平面的问题转化为，在条件( 2 1 3 ) 下，求 中( w ) - - l l w l l 2 ( 2 1 4 ) 的最小值的问题。事实上，支持向量到超平面的距离为l 州w 于是支持向 量之间的间隔为2 州w i l 。 寻求具有最大间隔的最佳超平面的依据是，一个规范超平面子集的v c 维数 满足下列不等式 v a p n i k ，1 9 9 5 ： h m i n ( r 2 a 2 】，1 ) + l ( 2 1 5 ) 其中n 为向量空间的维数，所有待分割的向量位于半径为r 的超球内，而 1 1 w l i a 。这样我们就可在固定经验风险的情况下，将使v c 景信度最小的问题 转化为使1 1 w 0 最小的问题。 2 2 2 线性s v m 解决线性可分问题 根据前面的讨论，构建最佳超平面来分割属于两类的训练集 ( x i ，y i ) ，( x 2 ，y 2 ) ，( x f ，y ，) ， x r 4 ，y ( + 1 ，一1 ) 1 5 ( 2 1 6 ) 中山大学硕士学位论文多类问题的支持向量机及其在笔迹鉴定中的应用 的问题，转化为解决下述二次规划问题： 在约束条件 y 。( w x f + b ) 1 i = 1 ，f ( 2 1 7 ) 下，求 m ( w ) = 去( w w ) ( 2 1 8 ) 的最小值。 这个最优化问题的解是下列l a g r a n g e 函数的鞍点： l ( w 。b ，= 劲w 2 一圭q 叭w x + 扫) 一1 ) ( 2 1 9 ) 其中口为非负l a g r a n g e 乘数。值得注意的是，( 2 1 9 ) 是一个凸二次规划问 题，因此存在唯一的最优解。在鞍点处，由关于w 和b 的梯度为零，可得 f w = 口y 。x ， ( 2 2 0 ) 江i 并且由k u h n t u c k e r 定理可知，最优解要满足 a f ( y f ( w x + b ) 一1 ) = 0 v i( 2 2 2 ) ( 2 2 1 ) 因此只有支持向量的系数纯才可能不为零，也即只有支持向量影响最终的 结果。于是w 可以表示为 w = o c i y f x ( 2 2 3 ) s u p p o r tv i 协 将( 2 2 0 ) 和( 2 2 1 ) 代入到( 2 1 9 ) 中，根据对偶原理，构建最佳超平面的问 题转化为下列简单的二次规划问题： 求 w ( 口) = 一去q 口，y 。y j ( x ，x 1 ) ( 2 2 4 ) 扛li ， 在约束条件 口0 ，i = 1 ，f 1 6 ( 2 2 5 ) 量坐堕苎塑生兰型兰堕一童耋塑壁塑塞茎塑量垫墨苎垄兰堕些塞主塑壁里 q y ，= o 下的最大值。 ( 2 2 6 ) 假定= ( 钟，0 ，钟) 是这个二次最优化问题的一个解，则w 的范数可以 表示为 1 w 1 2 = 2 w ( t z o ) = q 0 “0 ) i y ，( x 我们可通过选择i 使得钟0 ，然后利用( 2 2 2 ) 解出b 。 在训练得到最佳平面后，对于给定的未知样本x ，只需计算s g n ( w x + 6 ) ， 即可判定x 所属的分类。 2 2 3 线性s v m 解决线性不可分问题 在遇到线性不可分的问题对，上述方法中的目标函数w 位) 的最大值将为无 穷大a 为此，我们引入非负的松弛变量毒，i = 1 ，f ，来放宽条件( 2 1 7 ) ，从而 变为 y f ( w x f + 6 ) 1 - 晏i = 1 ，1 毒0 i = 1 ，l ( 2 2 8 ) ( 2 2 9 ) 显然，当分割出现错误时，毒大于零，于是蓐是训练错误数量的一个上 界。为此，引入错误惩罚分量，目标函数变为 西( w 伊吉( w - w ) + c