（计算机应用技术专业论文）基于csvm及凸锥方法的手写体数字识别研究.pdf

中国民航大学硕士学位论文 摘要 字符识另j ( o c r ) 是模式识别的一个重要分支，手写体数字识别则一直是o c r 中一个 极具有挑战性的难题，本文探讨的主要内容是脱机手写体数字识别。 本文首先讨论了支持向量机的一些训练算法，并给出了一种新型的核函数一时核 函数。在此基础上对层叠支持向量机( c a s c a d es v m ) 进行了深入地分析，同时提出了一 种改进的c a s c a d es v m 方法，较好地解决了训练集的划分问题。实验表明，改进后的方 法使得c a s c a d es v m 迭代次数更少，收敛速度更快。 最后，本文提出了一种新的方法一基于空间凸锥构造的手写体数字识别方法。该方 法通过构造每类样本的凸锥集，来描述了各类样本在高维空间中的几何分布，然后通过 判断样本所在的区域识别该样本。该方法不仅解决了手写体数字识别问题，对于其它的 模式识别问题也具有参考价值。 关键词：凸锥，手写体数字，层叠支持向量机，模式识别 中国民航大学硕士学位论文 a b s t r a c t o p t i c a lc h a r a c t e rr e c o g n i t i o n ( o c r ) i sa ni m p o r t a n ta r e a i np a t t e r nr e c o g n i t i o n r e s e a r c h ，a n dh a n d w r i t t e nd i g i tr e c o g n i t i o ni sr e g a r d e da saf a m o u sc h a l l e n g i n gp r o b l e mo f o c rr e s e a r c h t h i sp a p e rm a i n l yf o c u s e so no f f - l i n eh a n d w r i t t e nd i g i tr e c o g n i t i o n f i r s t l y , t r a i n i n ga l g o r i t h m so fs v m a r ed i s c u s s e di nt h i sp a p e ra n dan e wk e r n e lf u n c t i o n 一时k e r n e lf u n c t i o ni sp r o p o s e d s e c o n d l y , t h em e t h o do fc a s c a d es v m i sa n a l y z e d p a r t i c u l a r l y f u r t h e rm o r e ，a ni m p r o v e dm e t h o do fc a s c a d es v m i sp r o p o s e d ，w h i c hs o l v e s t h ep r o b l e mo ft h ed i v i s i o no ft h ec a s c a d es v mt r a i n i n gd a t ap r e f e r a b l y t h ee x p e r i m e n t r e s u l ts h o w st h a tt h ec a s c a d es v mw i t l lt 1 1 i sn e wm e t h o dh a sl e s si t e r a t i v et i m e sa n df a s t e r c o n v e r g e n ts p e e d l a s t l y , an o v e lm e t h o db yc o n s t r u c t i n gc o n v e xc o n e si nh i g h d i m e n s i o n a ls p a c ef o r h a n d w r i t t e nd i g i tr e c o g n i t i o ni sp r o p o s e d f i r s t l y , t h ec o n v e xc o n es e tw h i c hc o v e r st h e g e o m e t r yd i s t r i b u t i o nr e g i o no fs a m p l e so fe a c hc l a s s i nh i g h - d i m e n s i o n a ls p a c ei s c o n s t r u c t e d s e c o n d l y , t h es a m p l e sn e e d e dt ob er e c o g n i z e da r ec l a s s i f i e db yt h ec o n v e xc o n e s t h ep r o p o s e dm e t h o dp r o v i d e sas o l u t i o nf o rt h er e c o g n i t i o no fh a n d w r i t t e nd i g i t s ，a n di sa l s o p o t e n t i a l l ya p p l i c a b l et ot h er e c o g n i t i o no fo t h e rp a t t e r n s k e y w o r d s ：c o n v e xc o n e ，h a n d w r i t t e nd i g i t s ，c a s c a d es v m ，p a t t e r nr e c o g n i t i o n i i 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得中国民航大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意。 研究生签名： 日 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括 刊登) 授权中国民航大学研究生部办理。 研究生签名： 导师签名：妇) 日 中国民航大学硕士学位论文 1 1 问题的提出 第一章绪论 字符是人类思想的载体，是交流的工具，进入信息时代后，原来依靠图形记载在纸 上的字符就有了电子化的以序号为代表的记载方式，这就产生了图形字符与编码序号之 间的转换问题。由编码序号到图形是计算机输出，而由图形到编码序号就是字符识别。 字符识别是模式识别学科的一个重要研究领域。从五十年代开始，许多研究者就在这一 领域开展了广泛的探索o “3 1 l ，推动了模式识别的发展。近十几年来，随着大规模集成 电路和微电子技术的高速发展，计算机硬件技术的发展达到了一个从未有过的速度。同 时计算机及其相关设备价格的迅速下降以及性能的迅速提升，使计算机从以前昂贵庞大 的实验室用品走进人类社会工作与生活的各个方面，更多的人能够接触并使用计算机完 成他们的工作。随着计算机用户数量的大量增加，人们对计算机的要求也越来越高，希 望它不仅能够进行复杂的数值计算，而且希望计算机能在一定程度上模仿人类智力活 动，具有类似人类一样的智能。所以人们希望计算机能听懂人类的自然语言，看懂人们 所写的各种字符，认识人们的面容甚至理解人们此刻的心情。人类的这些需求都给模式 识别及人工智能的应用提供了动力，因此语音识别【6 - 9 ，人脸识别【1 0 , 1 1 , 3 4 和字符识别在这 一时期成为模式识别及人工智能研究的热点。 字符识别一般可以分为两类： 1 、联机手写字符识别，又称在线( o n - l i n e ) 手写字符识别； 2 、光学字符识另j j ( o p t i c a lc h a r a c t e rr e c o g n i t i o no c r ) 或称离线( o f f - l i n e ) 字符识别。 在联机手写字符识别中，计算机能够通过与计算机相连的手写输入设备获得输入字 符笔画的顺序，笔画的方向以及字符的形状，因此与o c r 相比较，联机字符识别能获 得更多的信息，所以相对于o c r 来说它更容易识别一些。但是联机字符识别有一个重 要的不足就是要求输入者必须在指定的设备上书写，然而人们在生活中大部分情况不满 足这一要求，比如人们填写各种表格材料，开具发票等等。如果需要计算机去认识这些 已经成为字符的东西，就需要o c r 技术。比起联机字符识别来，o c r 的应用更为广泛， 同时也是一个更具挑战性的问题。 1 2 模式识别基本步骤 对所有o c r 系统，其一般步骤如图1 1 所示。 中国民航大学硕士学位论文 图i i 模式识别系统的基本构成 1 、数据获取：为了使计算机能够对待识别对象进行分类，要用计算机可以运算的 符号来表示所要识别对象。获取原始的待识别对象的图像是识别的第一步。通常采用光 学的办法( c c d 摄像机，光学扫描仪等) ，得到的图像是待识别对象的像素描述。像素描 述的重要参数是分辨率，分辨率包括空f 司( - - 维平面) 分辨率和灰度分辨率，前者反映了 像素描述在空间上的精细程度，而后者则反映了像素描述在灰度( 色彩) 空间的精细程度。 由于空间分辨率对的高低对待识别对象识别影响较大，因此要认真选择。 2 、预处理：对上述采集到的图像进行识别前所必要的一些处理工作。预处理阶段 在实用系统中是一个很重要的阶段。预处理效果的好坏会直接影响到整个o c r 系统的 性能，其包含的内容非常广泛。一般而言，预处理包括去除噪声，尺寸标准化，加强有 用的信息，并对输入设备或其它因素所造成的退化现象进行复原等步骤。 3 、特征提取和选择：由于图像所获得的数据量是相当大的，为了有效地实现分类 识别，就要对原始数据进行变换，得到最能反映分类本质的特征。特征提取是为了去除 图像信息中对分类没有帮助的部分，将图像信息集中到有代表性的几个特征上来的过 程。选择稳定的、有代表性的特征往往是一个识别系统成功的关键。按照统计的观点， 好的特征提取方法必须满足三个条件：一是提取的一组特征相互独立或者说不相关，二 是特征向量的维数尽量小，三是该组特征能够很好的表示原来图像信息。而在实际应用 中，寻找满足这三点要求的特征提取方法是一项富有挑战性的工作，也是人们梦寐以求 的。 大体上来说特征可以分成结构特征和统计特征两类。基于结构特征识别方法的基本 思想是把待识别对象的图像分割简化为若干基元，如笔画、拓扑点、结构突变点等，与 模板比较，检查必要的基元是否存在，不可有的基元是否出现，从而判断所属的类别。 目前主要有针对骨架、轮廓、笔画得到结构基元的方法。而统计特征是从原始数据中提 取与分类最相关的信息，使得类内距离极小化，类间距离极大化。特征应对同一类字符 中国民航大学硕士学位论文 的形变尽量保持不变。 4 、分类决策：作为字符识别的关键步骤之一，指分类器依据特征提取阶段提取的 特征，用事先得到的文法规则或决策函数对待识别对象的类别做出判断。获取文法规则 或决策函数的过程称为训练或学习。训练或学习的过程既可以由机器自动完成，也可以 用手工方法进行，或两者结合。分类器包括模板匹配分类器、统计决策分类器、句法结 构分类器、神经网络分类器和支持向量机等。多数情况下，单一分类器往往难以获得好 的分类结果，因此，多分类器融合的方法在实际应用中常被采用。而在很多时候，为了 提高分类器的工作速度，分类过程常分为两级或多级，先进行粗分类，然后再逐步进行 细分类。 1 3 模式识别基本方法 l 、模板匹配法 这是模式识别中最常用的基本方法之一，其基本原理是：对每个模式类都定义一个 标准的模式并将它作为本模式类的模板。决策待识别字符时，把字符同所有的模板做比 较，差别最小的模板所属的类别即认为是该字符所属的类别。这种方法一般只适用于印 刷字符或受到相当限制的手写体字符，对于一般性的手写体字符，这种方法很难适用。 2 、统计模式识别方法 在概率论和数理统计的基础上产生了模式识别中的一个经典方法，即统计模式识别 方法。这一方法由于有着严格的数学基础，因此发展得较为成熟，同时它也是模式识别 中能用严格的数学计算来识别字符的方法之一。这种分类方法的一个重要代表是基于 b a y e s 的决策理论，其基本原理；用特征向量五= ( 五，屯，) 来描述模式类 q ，i = l ，2 ，c 。将模式类分布看成一种条件概率分布p ( x i q ) ，根据b a y e s 公式计算 出后验概率p ( 鸱| x ) ，则有b a y e s 决策规则：若p ( q l x ) = m a xp ( q i x ) ，f = 1 ，2 ，c ， 则x 纯。统计决策的优点是抗干扰能力强，但是难以反映模式的细节。 3 、结构模式识别方法【2 6 1 4 、与统计模式识别方法对应的是结构模式识别方法。其基本原理是：对每个模式 都用一个句法来表示，而对一个待识别的未知样本，通过抽取该样本的基元来构造该样 本的句子，然后分析该句子满足什么样的句法，从而推断出它该属于哪个模式类。这种 方法的优点是它能够反映模式的结构特征，而且对模式的结构特征变换不敏感，因此比 较适用于联机识别。但是由于抽取字符的基元比较困难，因而不是特别适用于脱机识别， 同时这一方法的理论基础不可靠，抗干扰能力比较弱。 5 、神经网络 中国民航大学硕士学位论文 在神经网络理论的基础上形成了神经网络方法，其基本原理就是利用神经网络的学 习和记忆功能，先让神经网络学习各个模式类别中的大量学习样本，以记住各模式类别 中的样本特征，然后在分类待识别样本时，把该样本的特征与各模式类别的特征相比较， 从而确定样本所属的模式类别。这种方法的优点是抗干扰能力强，允许样本有较大的变 化，但是它也依赖特征向量的选取。 6 、支持向量机 支持向量机方法【3 2 l 根据v a p n i k 的结构风险最小化原则，尽量提高学习机的泛化能 力，也就是使得由有限训练样本得到的决策规则对于独立的测试集仍能得到较小的误 差。此外，支持向量机算法是一个凸二次优化问题，能够保证找到的极值解就是全局最 优解。支持向量机的基本思想可以概括为：首先通过非线性变换将输入空间变换到一个 高维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适 当的内积函数实现的。 1 4 手写体数字识别研究 1 4 1 手写体数字识别的特殊性 数字的类别只有十种，笔划又简单，其识别问题似乎不是很困难。但事实上，测试 结果表明，数字的正确识别率并不如印刷体汉字识别正确率高，甚至也不如联机手写体 汉字识别率高，而只仅仅优于脱机手写体汉字识别。 这其中主要原因是： l 、某些数字的相似性很大，字形相差不大，使得准确区分某些数字相当困难： 2 、数字虽然只有十种，而且笔划简单，但同一数字写法千差万别，全世界各个国 家各个地区的人都用，其书写上带有明显的区域特性，很难完全做到兼顾世界各种写法 的极高识别率的通用性数字识别系统。 另外，在实际应用中，对数字识别单字识别正确率的要求要比文字要苛刻得多。这 是因为，数字没有上下文关系，每个单字的识别都事关重要，而且数字识别应用的领域 经常涉及的财会、金融领域其严格性更是不言而喻的。 因此，用户的要求不是单纯的高正确率，更重要的是极低的、千分之一甚至万分之 一以下的误识率。此外，大批量数据处理对系统速度又有相当的要求，许多理论上很完 美但速度过低的方法是行不通的。因此，研究高性能的手写数字识别算法是一个有相当 的挑战性的任务。 1 4 2 手写体数字识别国内外研究现状 手写体字符识别，国外从2 0 世纪7 0 年代初研制成“光学字符识别机( o c g ) ”，能够 自动识别印刷体的英文字符及阿拉伯数字。2 0 世纪7 0 年代中期出现了能识别手写体数 4 中国民航大学硕士学位论文 字的o c r 。在2 0 世纪7 0 年代末和8 0 年代初又出现了能识别手写体英文字符的o c r 。 日本于2 0 世纪8 0 年代初研制了印刷体汉字识别样机，这是最早的汉字o c r 。我国从 2 0 世纪7 0 年代就开始进行了字符( 英文字符和数字) 识别的研究，2 0 世纪8 0 年代末己进 入实用阶段，主要用于邮政信函自动分检，人口普查和生产统计报表。 手写体数字识别的研究主要包括：l 、特征提取方法；2 、分类方法；3 、基于多种 策略组合的识别系统，例如多种分类器的融合，多种模板的使用。 在过去数十年中，研究者们提出了许多特征提取方法。按使用的特征的不同属性， 这些方法主要可以分为两类：基于统计特征的方法以及基于结构特征的方法。统计特征 通常包括分布区域、矩、点密度的测量等，建立在统计数学，特别是贝叶斯决策理论基 础上【4 h 9 1 。结构特征通常包括笔划、端点、交叉点、轮廓等，对于一个复杂的模式，采 用分解的方法将其划分为若干较简单的子模式乃至基元，通过对基元和子模式识别的综 合集成来完成复杂模式的整体识另l j 5 0 , 5 1 。一般来说，两类特征各有优势。例如，使用统 计特征的分类器易于训练，而且在给定训练集上能够得到相对较高的识别率；而结构特 征的主要优点之一是能描述字符的结构，在识别过程中能有效的结合拓扑和几何属性的 知识，因此能够得到可靠性较高的识别结果。 除了特征提取方法以外，各种不同的分类方法也被用于手写体数字识别，例如统计 方法 4 9 , 5 2 ，结构方法 2 6 , 5 0 l ，神经网络【5 3 1 ，支持向量机1 5 4 , 5 5 。同时，依靠多种策略组合的 识别系统对识别率的提高起了重要作用1 5 6 , 6 0 。 表1 目前手写体数字识别的一些重要结论 正确率错误率拒绝率 方法数据库 ( )( ) ( ) c e d a r p e r t u r b a t i o nm e t h o d t 5 7 19 9 0 90 9 1 0 ( 2 ，2 1 3 ) s t a t i s t i c a ia n ds t r u c t u r a lf e a t t i r e sc o m b i n e di na l lc e d a r h m m b a s e dm e t h o d 【5 ” 9 6 1 63 8 4 0 ( 2 ，7 1 1 ) m o r p h o l o g i c a la n dt o p o l o g i c a lp r o p e r t i e s 9 9 3 70 2 7o 3 6 c e d a r ( g r a p hr e p r e s e n t a t i o n ) 1 5 q( 2 ，2 1 3 ) c e n p a r m l m u l t i p l e sf e a t u r e sa n dm u l t i p l en e u r a l 9 8 8 52 1 3 o ( 2 ，0 0 0 ) n e t w o r k s 6 0 9 9 7 7o 2 3 o c e d a r ( 2 ，2 1 3 ) c e n p a r m i n e u r a ln e t w o r k sa n dd i s c r i m i n a t i v et r a i n i n 9 1 6 1 】9 8 4 5 1 5 5 0 ( 2 ，o o o ) m n i s t m u l t i n e tl e a r n i n gf r a m e w o r k e 2 】9 9 0 10 9 9 0 ( 1 0 ，0 0 0 ) t r i o - w i s el i n e a rs v mw i t hd i r e e t i o i la n ds t r o k em n i s t f e a t u r e s 【6 3 】 9 9 4 lo 5 90 ( 1 0 ，o o o ) m _ n i s t s v m i “l9 9 5 80 4 20 ( 1 0 ，o o o ) 中国民航丈学硕士学位论文 f l e x i b l ei m a g em a t c h i n gw i t h1 0 ，0 0 0 9 9 3 7o 6 3 0 m _ n i s t t e m p l a t e s m q( 1 0 ，0 0 0 ) m n i s t s v m “】9 9 5 80 4 20 ( 1 0 ，o o o ) n i s t s d l 9 s v m t 6 7 i9 9 2 00 8 00 ( 6 0 ，0 8 9 ) c o m b i n a t i o no f c o m p l e m e n t a r yf e a t u r e si na l l n i s t s d l 9 h m m b a s e dm e t h o d 【6 ” 9 8 0 02 0 00 ( 6 0 ，0 8 9 ) 1 4 3 手写体数字识别研究意义 手写数字识别有着极为广泛的应用前景，这也正是它受到世界各国的研究工作者重 视的一个主要原因。下面将介绍一些以手写数字识别技术为基础的典型应用。 l 、手写数字识别在大规模数据统计中的应用 在大规模的数据统计( 如：行业年鉴、人1 3 普查等) 中，需要输入大量的数据，以前 完全要手工输入，则需要耗费大量的人力和物力。近年来在这类工作中采用o c r 技术 已成为一种趋势。因为在这种应用中，数据的录入是集中组织的，所以往往可以通过专 门设计表格和对书写施加限制以便于机器的自动识别。 2 、手写数字识别在财务、税务、金融领域中的应用 财务、税务、金融是手写数字识别大有可为的又一领域。随着我国经济的迅速发展， 每天等待处理的财务、税务报表、支票、付款单等越来越多。如果能把它们用计算机自 动处理，无疑可以节约大量的时间、金钱和劳力。 3 、手写数字识别在邮件分拣中的应用 随着人们生活水平的提高，经济活动的发展，通信联系的需求使信函的互换量大幅 度增加，我国函件业务量也在不断增长，一些大城市的中心邮局每天处理量将高达几百 万件，业务量的急剧上升使得邮件的分拣自动化成为大势所趋。 因此，手写数字的识别研究有着重大的现实意义，一旦研究成功并投入应用，将产 生巨大的社会和经济效益。在各种应用中，新的方法理论不断涌现，同时原有的方法也 不断被重新组合利用以达到更好的性能。 手写数字识别作为模式识别领域的一个重要问题，也有着重要的理论价值。 l 、阿拉伯数字是各国通用的符号，在这一领域各国的研究者可以探讨、比较各种 研究方法。 2 、数字识别的类别数较小，有助于做深入分析及验证一些新的理论。这方面最显 著的例子就是支持向量机，它正是以手写体数字识别作为具体的实验数据，验证理论的 有效性，评价各种方法的优缺点。 3 、尽管人们对手写体数字的识别已从事了长时间的研究，并取得了很多成果，但 到目前为止机器的识别本领还无法与人的认知能力相比，这仍是一个有难度的开放问 6 中国民航大学硕士学位论文 题。 4 、手写体数字的识别方法很容易推广到其它一些相关问题，一个直接的应用是对 英文字符的识别。例如本文第四章提出的基于空间凸锥构造的手写体数字识别方法，就 已经推广到英文字符的识别。 1 5 手写体数字库简介 本文所用实验数据均来自于n i s t1 9 号数据库。该数据库包括4 2 0 ，0 0 0 个数字样 本以及4 1 0 ，0 0 0 个英文字符样本。该数据库中的手写体数字都为1 2 8 x 1 2 8 像素的图像。 而本文中所采用的图像数据，为原图像数据通过小波变换为3 2 ) ( 3 2 像素的图像。 图1 20 - 9 手写体数字( 3 2 x 3 2 ) 样本 1 6 本文的研究内容和结构安排 本文主要研究手写体数字识别问题。 本文利用基于支持向量机和聚类的方法对手写体数字识别这一课题进行了研究，其 中主要的研究工作包括以下几点： 1 、第一章主要介绍了模式识别一些常用的基本方法，一般步骤，以及手写体数字 识别研究的特殊性、现状、应用及理论意义。 2 、第二章首先阐述了统计学习理论基本知识，然后描述了支持向量机方法，并且 给出了一种新型的核函数一删核函数，同时把该核函数用于手写体数字的识别，最后 讨论了传统的几种s v m 训练算法。 3 、第三章对一种新的支持向量机训练算法c a s e a d es v m 方法进行了深入研究与 分析，重点讨论了c a s c a d es v m 方法的原理及其特点：并在此基础上，结合一些新思想， 提出了一种改进的c a s c a d es v m 方法。 4 、第四章首先分析了传统特征提取方法的优缺点，然后提出一种新型的手写体数 字识别方法一基于空间凸锥构造的手写体数字识别方法，最后将该方法用于手写体数字 的识别。 7 中国民航大学硕士学位论文 2 1 引言 第二章统计学习理论与支持向量机 支持向量机【3 2 】是v a p n i k 等人根据统计学习理论提出的一种新型机器学习方法。由 于其出色的学习性能，该技术己成为机器学习界的研究热点，并在很多领域都得到了成 功的应用，如人脸检测【3 4 1 、手写体数字识别阅、文本自动分【3 6 】类等。s v m 方法基于结 构风险最小化原理( 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 p , m ) ，明显优于传统的基于经 验风险最小化原理( e m p i r i c a lr i s km i n i m i z a t i o np r i n c i p l e ，e g m ) 的常规分类方法。s r m 使 实际风险的上界最小化，而e r m 仅使相对于训练数据的误差最小化这使得s v m 具有 更好的泛化能力，这也是统计学习的目的。本章中，我们介绍统计学习基本理论【”1 和 s v m 方法。 2 2 统计学习理论 2 2 1 经验风险最小化原则 机器学习问题可以形式化地表示为：已知变量y 与输入x 之间存在一定的未知依赖关 系，即存在一个未知的联合概率f ( x ，j ，) ，机器学习就是根据行个独立同分布观测样本 ( 而，咒) ，( 屯，弘) ，( k ，以) ( 2 2 1 ) 在一组函数 厂( x ，w ) 中求一个最优的函数 厂( x ，) ，使预测的期望风险 r ( w ) = 弘( y ，( x ，w ) ) d f ( x ，y ) ( 2 2 2 ) 最小，其中 f ( x ，w ) ) 称作预测函数集，q 为函数的广义参数，故 ，( x ，w ) ) 可以表示 任何函数集；三( y ，厂( 工，w ) ) 为由于用厂( x ，w ) 对) ，进行预测而造成的损失。 学习的目的就是要在函数集 厂( x ，w ) ) 中寻找使r ( w ) 值最小的函数。由于联合分布 r ( x ，y ) 未知，所以很难计算期望风险r ( w ) 。我们所能得到的信息全都包含在训练集中， 为此构造经验风险函数作为近似： 中国民航大学硕士学位论文 r e m p ( w ) = i ： 喜工( 彬( ”) ) ( 2 2 3 ) ( ，) 与r ( w ) 相比，主要有以下两点不同： 1 、( w ) 并不显式依赖于未知的联合分布函数，( x ，y ) ； 2 、理论上，( w ) 可以关于w 最小化。 用对参数w 求经验风险kw ) 的最小值代替求期望风险胄( w ) 的最小值，就是所谓 的经验风险最小化( e r d 原则。传统的各种基于数据的分类器设计方法实际上都是在 e r m 原则下提出的。 根据大数定理，当训练样本数聆趋于无穷时，经验风险k ( w ) 将在概率意义上趋近 于期望风险r ( w ) 。但是，仅由此还不能得出使经验风险r ( i ) 最小的w 同时也会使r ( w ) 最小这一结论。其次，即使我们有办法使这些条件在样本数无穷大时得到保证，我们也 无法认定在这些前提下达到经验风险最小化方法在样本数有限时仍能得到好的效果。我 们需要考虑在什么条件下，e r m 原则满足一致性，即经验风险r e m p ( w ) 的最小值依概率 收敛于实际风险r ( w 1 的最小可能值： 。i n ，f ( w ) ：孵r ( i ) ( 2 2 4 ) 其中为权空间。这里所谓的一致性可以理解为：当样本趋于无穷时，使经验风险最小 化的w e 。所对应的期望风险也差不多是最小。下面的定理回答了这一问题。 定理2 1 ( e r m 原则一致性的充要条件) 【3 刀；对于有界损失函数，经验风险最小化学 习一致的充要条件为经验风险在如下的意义上一致地收敛于实际风险： 。l i r a p s u ，p r ( w ) 一( w ) ) 0 寸o ( 2 捌 定理2 1 在理论上奠定了经验风险最小化的可行性，但在实际问题中样本数目厅不 可能无穷大，因此还需要研究收敛的速度问题。 2 2 2 函数集的v c 维及泛化能力 统计学习理论【”1 在研究收敛速度问题的时候，定义了一个重要的概念“v c 维”。模 式识别方法中v c 维的直观定义是：如果存在一个包含h 个样本的样本集能够被一个函 数集中的函数按所有可能的2 6 种形式分为两类，则称该函数集能够把样本数为h 的样本 9 中国民航大学硕士学位论文 集打散( s h a t t e r i n g ) 。指示函数集的v c 维就是用这个函数集中的函数所能够打散的最大样 本集的样本数目。如果对于任意数目的样本都有函数能将其打散，则函数集的v c 维为 无穷大。v c 维作为统计学习理论中的一个核心概念，它反映了一个函数集的容量 ( c a p a c i t y ) ，表明了学习机器的最大学习能力。一般而言，v c 维越大则学习机器越复杂， 函数集的容量越大。但目前尚未有关于计算任意函数集v c 维的理论，这仍然是统计学 习理论中有待研究的一个问题。 2 2 3 一致收敛的速度 统计学习理论系统地研究了对于各种类型的函数集，实际风险和经验风险及函数集 容量之间的关系，即推广性的界【”】，阐明了经验风险在什么条件下以及以多快的速度一 致收敛到实际风险。其中，对于两类分类问题有如下的结论( 以至少l - r 的概率成立) ： r ( w ) 0 3 7 时，这个界肯定是松弛的；当v c 维无穷大时，这 个界不再成立( 如使用k n n 算法时) 。因此，寻找更紧的上界也是一个待解决的问题。 2 2 4 结构风险最小化 e r m 原则是从处理大样本数问题出发的，其合理性也可以通过对式2 2 6 的分析来 验证。当i h 较大时，不等式右边的第二项就变得较小，于是实际风险就较接近经验风 险的取值。然而如果i h 较小，那么一个小的足。( w ) 并不能保证小的实际风险值。在 这种情况下，要最小化实际风险就必须对不等式右边的两项同时最小化。但是需要注意 的是，不等式右边的第一项取决于函数集中的一个特定的函数，而第二项则取决于整个 函数集的v c 维。因此要对风险的界最小化，我们必须使v c 维成为一个可以控制的变 量。结构风险最小化原则旨在针对经验风险和置信范围这两项最小化风险泛函。 l o 中国民航大学硕士学位论文 从上面的讨论可以看出，经验风险最小化原则在样本数目有限时是不合理的，因为 我们需要同时最小化经验风险和置信范围。有了式2 2 6 的理论依据，我们就可以用另 一种策略，即结构风险最小化【3 8 1 来解决这个问题。 首先把函数集s = f ( x ，w ) ，w q 分解为一个函数子集序列 s c 是c c 最c c s 是各个子集能够按照v c 维的大小排列，即 魂s 这样在同一个子集中置信范围就相同；然后在每一个子集中寻找最小经验风险，通 常它随着自己复杂度的增加而减小。选择最小经验风险与置信范围之和最小的子集，就 可以达到期望风险的最小，这个子集中使经验风险最小的函数就是要求的最优函数。这 种思想称作结构风险最小化。在这个原则下，一个分类器的设计过程包括以下两方面任 务： l 、选择一个适当的函数子集( 使之对问题来说有最优的分类能力) ； 2 、从这个子集中选择一个判别函数( 使经验风险最小) 。 s r m 原则定义了在对给定数据逼近的精度和通近函数的复杂性之间的一种折衷。 随着子集序号行增加，经验风险的最小值减小，但置信界却增加；s r m 原则把两者都考 虑在内，子集墨的选择使得在这个子集中，最小化经验风险会得到实际风险的最好的界。 2 3 支持向量机 支持向量机( s v m ) 是统计学习理论的v c 维理论和结构风险最小化原理的具体实 现。s v m 方法是从线性可分情况下的最优分类面提出的。在二维两类线性可分情况下， 对于把两类正确分开的分类线而言，两类样本中离它最近的点到它的距离之和称作两类 的分类间隔。所谓最优分类线就是要求分类线不但能将两类无误地分开( 保证经验风险 最小) ，而且要使两类的分类间隔最大。推广到高维空间，最优分类线就成为最优分类 面。 2 3 1 支持向量机的原理 支持向量机是从线性可分情况下的最优分类面提出的。假定训练数据 ，咒 ，f = 1 ，2 ，疗，薯r , y j - 1 ，1 ) 可以被一个超平面( w x ) + 6 = o 没有错误地分开。用如下方程描述与样本间隔为a 的分类超平面： 1 1 中国民航大学硕士学位论文 ( w 工) + 6 = o ，l i 叫l = l y = 1 ，若( w 工) + 6 2 a y = - i ，若( w x ) + 6 0 ，i = l ，2 ，栉 目标函数是严格凸函数，约束条件是凹函数。式2 3 2 是一个严格凸规划， 理论中凸二次规划的解法，把它转化为w o l f e 对偶问题来求解： 构造l a g r a n g e 函数： 工( w ，训= i l l w 卜喜q 咒( ( 峨) + 6 ) 嘻q 吼o ，i = 1 ，2 ， 其中口是l a g r a n g e 乘子。根据最优点满足的k 盯条件有： 斋三w , a , b ) 喜= 。 未三, a , b ) = 善nq 片= 。 由方程组2 3 4 可得到： ( 2 3 2 ) 按照最优化 ( 2 3 3 ) ( 2 3 4 ) 中国民航大学硕士学位论文 w = 口，咒x h 口，m = 0 i = 1 将式2 3 5 ，2 3 6 代入式2 3 3 函数中， w o l f e 对偶问题是： ( 2 3 5 ) ( 2 3 6 ) 消去的系数为零。这样原优化问题，式2 3 2 的 m a x ( 口) = q 一去口，哆”乃( 墨_ ) j = l - i i = 1 n q 一= o 珥0i = l ，2 ，疗 其解是原优化问题的整体最优解。可根据一定的优化算法解出玩。注意到只有支持向量 所对应的l a g r a n g e 乘子才不为0 ，参数6 可由j | ；= 汀条件求出： b = 乃一w x i ) 这样就可以得到所求的分类判别函数： 巾) = s 醐w 叫镏n 倭训) + a )l ，lj 利用w o l f e 对偶原理，使样本仅以向量点积的形式出现。正是这一重要特点，使支 持向量机能推广到非线性情况。由于w o l f e 对偶问题的这种性质，现在对支持向量机所 作研究一般都从w o l f e 对偶问题开始，而不将其最初的数学提法作为优化目标。 2 3 3 线性不可分情形 在线性不可分的情况下如图2 3 所示： x 图2 3 线性不可分情况 1 4 中国民航大学硕士学位论文 可以在优化问题2 3 3 的条件项中增加一个松弛项o 来作为对分类误差的描述，即将 约束条件变为： 只 ( w 薯) + 6 一1 + 六o i = l ，2 ，h 同时目标函数变为： 小，f ) ：扣 1 2 + c f 窆缶1 二 ，= l 即折衷考虑最少错分样本和最大分类间隔，就得到广义最优分类面。其中c 0 ，称为 惩罚系数，是一个常数，它控制对错分样本惩罚的程度。广义最优分类面的对偶问题与 线性可分情况下几乎完全相同。利用w o l f e 对偶原理模仿线性可分情况的推导过程可以 得到线性不可分优化问题的对偶问题为： m a x w ( a ) = 杰q 一丢杰q q 乃乃( 葺_ ) s j a y , = o 0 s 珥c ，f = l ，2 ，胛 唯一的区别在于对口。加了一个上限限制c 。这种广义最优分类面对于非线性支持向量机 同样适用，使支持向量机可以普遍适用于各种模式识别问题。 由于不可分问题的存在，破坏了支持向量机直观的几何意义，给它的算法实现带来 了一定的难度。 2 3 4 特征空间与核函数 前面的方法针对的是输入空间存在线性判别面的情况，对分类面是非线性函数的情 况，按照广义线性判别函数的思路，要解决一个非线性问题，可以设法将它通过非线性 变换转化为另一个空间中的线性问题，在这个变换空间求最优或广义最优分类面。但是 这种方法带来了两个问题：一是概念上的问题；怎样在如此高维的空间中找到一个推广 性好的分类超平面；二是技术上的问题：如何处理高维空间中的计算问题。前面我们把 寻找最优超平面最终归结为其w o l f e 对偶问题，一个很重要的方面就是找到了一个克服 “维数灾难”问题的绝好方法：如果数学上可以找到一个函数k ：( r “，r “) 斗r ，使得 ， 置( ，) 就等于葺，在高维特征空间中的映射之内积，即足( t ，x j ) = ( 中( ) ，中( ) ) ， 其中k ( ，z ，) 称为核函数。那么用核函数k ( 葺，x ，) 代替w o l f e 对偶问题中o ( 薯) 和中( ) 的内积即可，计算量将会大大减少。统计学习理论指出，根据h i l b e r t s c h m i d t 原理，只 中国民航大学硕士学位论文 要一种运算满足m e r c e r 条件： 对于任意的对称函数k ( ，- ) ，它是某个特征空间中的内积运算的充分必要条件是，对于 任意的妒( 茗) 彳。且p 2 ( 石) o 那么，它就可以作为这里的内积使用，即k ( 薯，一) 为核函数。 按照这种方式，二次规划的w o l f e 对偶问题将成为： 月1 m a x 形( 口) = q 一寺q q 乃 k ( _ ) j j q 咒= o ( 2 3 7 ) 必0f = 1 ，2 ，行 而训练完成后的决策函数也相应地变为： r、 ，( x ) = s g n a , y j k ( x j x ) + b ( 2 3 8 ) h e 5 ”j 其中s v 为支持向量。 由于变换空间的维数可能很高，所以在这个空间中的线性判别函数的v c 维也很大， 这样就不具有良好的泛化能力。因此，核函数的选择对支持向量机得到的判别函数的推 广性起着至关重要的作用。 定理l 在d 维空间中，设所有的一个样本都在一个超球范围内( 这可以通过样本 归一化等方法实现) ，即样本集为 j = 而，而，毛) ，k d l r 其中d 为包含所有样本在内的最小超球的中心。则满足条件州| 2 c 的规范化超平 面形成的分类面 ( x ，w ，6 ) = s g n ( w x ) + 6 ) 的v c 维满足下面的界 h 一 m i n ( 眈 ，d ) + 1 定理2 【3 s 1 如果一组训练样本能够被一个最优分类面或广义最优分类面分开，则对 于测试样本分类错误率的期望的上界是训练样本中平均的支持向量占总训练样本数的 比例，即 1 6 中国民航大学硕士学位论文 帆叫) 豁 根据定理1 和定理2 ，只要我们在高维空间中能够构造一个具有较小 e r 2 c 值的 分类面，就可以有较小的v c 维，从而得到较好的泛化能力。同时，支持向量机的推广 性也是与变换空间的维数无关的，只要能够适当地选择一种内积定义( 核函数) ，构造一 个支持向量数相对较少的最优或广义最优分类面，则就可以得到较好的泛化能力。 下面是一些经常采用的核函数： 1 、线性核函数：k ( 葺，) = 薯 2 、多项式核函数：k ( 为，x s ) = ( _ ) + 1 r 3 、觚s i 托核函数：地刚= e x p 一学 4 、s 形核函数：k ( 薯，x s ) = t a n h ( v ( x , _ ) + c ) 此外，k ( 墨j ，) = c o s h ( x + y - a 焉- b 忑) + 丽c = o s h 石( x - y - b + 一a ) 【2 3 矧也是一种核函数，称为 纠核函数。如图2 4 所示，该函数一阶导数连续，在x = j ，处，不存在二阶导数。 图2 4 酬函数图像 中国民航大学硕士学位论文 x 图2 5 明函数分类图像 图2 5 为采用上述明函数作为核函数，对手写体数字进行分类的结果。表2 1 为采 用不同核函数的分类结果( 训练样本2 0 0 个，测试样本2 0 0 个) 。 表2 1 不同核函数分类结果 核函数类型核函数的参数分类间隔支持向量错误率 高斯函数 仃= l0 7 9 1 4 1 5 5 多项式函数 q = 3 0 4 23 4l o 删函数 a = o ，b = l 0 1 7 4 2 7 从表2 1 中可以看出，三种核函数的错误率逐渐降低，即叫核函数描