（计算机应用技术专业论文）基于支撑向量机的手写英文字符识别.pdf

摘要 摘要 手写字符识别是o c r 的一个分支，它的研究对象是：如何利用电子计算机 自动辨认手写的英文字符和阿拉伯数字。在探索手写字符识别的方法上采用了统 计学习理论，利用支撑向量机s v m 作为基本的识别工具。 统计学习理论是一种研究基于样本的机器学习理论。v v a p n i k 等人从六、七 十年代开始致力于此方面的研究，到九十年的中期，其理论的不断发展和成熟， 已基本形成一套比较完整的理论体系。在这一理论基础上发展了一种新的通用学 习方法一支撑向量机s v m 。它是种普遍适用的方法，已经广泛的用于模式识别、 回归估计、函数逼近、密度估计等方面。独立分量分析i c a 最初是由c o m o n 等 人于1 9 9 4 年提出的，它解决了盲源分离等问题，应用于模式识别、图像、医学等 领域。本文在系统研究s v m 和i c a 的基础上提出了以下新的观点： 其一是采用了引入后验概率的修正s v m 方法，它在原分类超平面的基础上 不断修正分类超平面，提高分类正确率，从而避免了寻找最优二次规划的麻烦， 同时将大规模训练样本集化为小规模训练样本集： 其二是应用独立分量分析i c a 对需要进行识别的字符图像预处理，提取字符 特征，降低输入数据的维数，从而可以为下步的s v m 识别过程提供好的数据 集，用以提高识别率和识别速度。 结合以上两种新方法，使得识别率和识别速度有明显的提高。i c a 方法的引 入对于识别过程无论在速度上还是在正确率上都有很大的提高，其中的根本原因 在于对输入数据维数的压缩；修正s v m 方法是对原有s v m 方法的一个改进，借 助于特征压缩后的数据集，识别效率有了很大的改善。 关键字：统计学习理论模式识别支撑向量机独立分量分析后验概率理论 摘要 a b s 仃a c t h a n d w r i t t e nc h a r a c t e rr e c o g n i t i o nr e s e a r c hi sab r a n c ho ft h ea r e ao f o p t i c a i c h a r a c t e rr e c o g n i t i o n ( o c r ) ，w h i c hd e a l sw i t ht h er e c o g n i t i o no f h a n d w r i t t e n e n g l i s h c h a r a c t e ro rd i g i t su s i n gc o m p u t e r s u p p o r tv e c t o rm a c h i n e ( s v m ) i su s e da st h e i m p l e m e n t a t i o nb a s i s ，w h i c hi sa t o o lo f s t a t i s t i c a ll e a r n i n g t h e o r y ( s l t ) s l ti sam a c h i n el e a r n i n gt h e o r yb a s e do ns a m p l e s jw h i c hw a ss t a r t e d b yp j v a p n i ki nt h e l9 7 0 sa n dm a t u r e dt of o r mac o m p l e t et h e o r e t i c a la r c h i t e c t u r ei nt h e m i d d l eo f1 9 9 0 s s v m ，d e v e l o p e df r o mt h a tt h e o r e t i c a l a r c h i t e c t u r e ，i s ah i g h l y a d a p t i v em e t h o d ，w h i c hi sa p p l i e di nt h ea r e a so fp a t t e r nr e c o g n i t i o n ，r e g r e s s i o n e s t i m a t i o n ，f u n c t i o na p p r o x i m a t i o na n dd e n s i t ye s t i m a t i o n i n d e p e n d e n tc o m p o n e n t a n a l y s i sw a sf i r s tp r o p o s e db yc o m o n i n1 9 9 4t os o l v et h ep r o b l e mo fb l i n ds o u r c e s e p a r a t i o n ，w h i c hi s n o ww i d e l yu s e di nt h ea r e ao fp a f t e mr e c o g n i t i o n ，i m a g e p r o c e s s i n ga n dm e d i c a ls c i e n c e ，s o m e n e wi d e a sa r ep r o p o s e di nt h i st h e s i sb a s e do n s v ma n d i c a ： f i r s t l y , am o d i f i e ds v m m e t h o db a s e do np o s t e r i o r ip r o b a b i f i t yt h e o r yi sg i v e n ， w h i c hm a k e st h ec l a s s i f i c a t i o ns u p e rp l a n ec o r r e c t e df r o mt h eo r i g i n a lo n e ab e t t e r c l a s s i f i c a t i o nr e s u l ti so b t a i n e dw i t h o u tf i n d i n gt h eb e s tq u a d r i co p t i m i z a t i o na l g o r i t h m a n dl a r g es c a l et r a i n i n gd a t a s e t sa r er e d u c e dt os m a l ls c a l et r a i n i n gd a t a s e t sa tt h es a m e t i m e s e c o n d l y , i c a i sa p p l i e dt ot h ep r e p r o e e s s i n gp e r i o do ft h er e c o g n i t i o nc h a r a c t e r i m a g e sf o rp u r p o s eo ff e a t u r ee x t r a c t i o na n dd i m e n s i o nr e d u c t i o n af i n e l yt r i m m e d i n p u td a t a s e t st os v m i sf o r m e dt og e tah i g h e rr e c o g n i t i o nr a t ea n d s p e e d ， t h ec o m b i n a t i o no fs v ma n di c ai sh i g h l ye f f e c t i v ei nt h er e c o g n i t i o np r o c e s s t h ed i m e n s i o nr e d u c t i o no fi c ai st h ef u n d a m e n t a lf a c t o ri nt h er e c o g n i t i o nr a t ea n d s p e e di m p r o v e m e n ta n dt h em o d i f i e ds v m m e t h o dg i v e sa na m a z i n gr e s u l ti nt h i s a r e a k e y w o r d ：s t a t i s t i c a ll e a r n i n gt h e o r y m a c h i n e i n d e p e n d e n tc o m p o n e n ta n a l y s i s p a t t e r n r e c o g n i t i o ns u p p o r t v e c t o r p o s t e r i o r ip r o b a b i l i t y t h e o r y 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究t 作及取得的研究 成果。尽我所知，除了文一 1 特别加以标注和致谢，i - 所罗列的内容以外，论文l i t 不 包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使川过的材料。与我一同t 作的同志对本研究所做 的佰何页献均已在论文巾做了明确的说明并表示了谢意。 ， 申请学位论文与资料若有不实之处，本人承拙切相关责任。 本人签名：塞遣壁 日期： 垫竖6 丝 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使川学位论文的规定。即：研究牛 在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使j f j 论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借测论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本 签名囊是辞本人签名： 坠望兰：i 导师签名：墨盥 日期： 日期： 兰! 丝! ：丝 竺丝兰 第一章绪论 第一章绪论 1 1 研究背景 手写字符识别( h a n d w r i t t e nc h a r a c t e rr e c o g n i t i o n ) 是光学字符识别技术 ( 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 ) 的一个分支，它研究的对象是：如何 利用电子计算机自动辨认人手写在纸张上的英文字符和阿拉伯数字。 手写字符模式识别可分为联机手写字符识别和脱机手写字符识别两种，它们 有本质上的区别，识别方法也有所不同。 符，是一种特殊形式的二维图形或图象， 脱机手写字符识别的识别对象是手写字 经扫描输入计算机：联机手写字符识别 的识别对象虽然也是手写字符，但通过特殊书写板和笔把构成字符的笔划按照书 写顺序依次送入计算机，因而事实上已经把一个二维图形分解为一维的笔划序列。 在整个o c r 领域中，最为困难的就是脱机手写字符的识别。到目前为止，尽 管人们在脱机手写英文、汉字识别的研究中已取得很多可喜成就，但距实用还有 一定距离。伴随着新的理论以及研究方法的出现，为这方面的研究提供强有力的 支持。 ：。 在理论和方法的探索中，实验室以模式识别理论和方法为主要着眼点，借鉴 思维科学、系统科学和心理学等领域的研究成果，经历了一个从无到有的艰难历 程，逐步形成了较为系统的模式识别理论与方法，得到了国内外广泛重视与研究。 7 0 年代初，受当时日本实施模式信息处理计划的影响，注意到模式识别本身 的重要性，尤其是模式识别用以解决人与计算机能方便地交换信息，研制“人机 接口”的诱人前景，中科院自动化所一批科技工作者开展了手写字符模式识别的 研究，率先投身于模式识别领域的研究工作。：在这一阶段，解释了模式识别的意 义，确定了研究内容，对模式识别方法做了细致的分析和研究。1 9 7 4 年研究成功 手写数字识别系统，并应用于信函自动分拣系统中。 8 0 年代初，自动化所与模式识别的主要奠基人k s f u 教授合作。开展了模 式识别理论研究工作。他们分析了传统的统计模式识别和句法模式识别方法各自 的弱点，统计方法不能描述复杂模式的结构以及模式与子模式之间的关系，句法 方法在处理具有噪声的模式及利用数字的语义信息方面又往往无能为力。为克服 它们的弱点，创建性地利用了属性文法作为联系桥梁，引入语义信息，用带属性 的文法对模式进行描述与分析，把统计模式识别和句法模式识别有机地结合起来。 一个带属性的文法包括语法和语义两个部分，语义与语法两者之间存在一种折衷 关系，即如果语义部分复杂一些，就可以简化语法部分，反之亦然。这样，不仅 基j ：支撑向耸机的手写英文字符识别 突破了统计模式u 别方法和句法模式识别方法各自的局限性，而且也将两者作为 两种极端情况结合起来。工作中首次定量地论述了属性文法中语法和语义的内在 联系，既考虑到模式的语法结构，又注重模式的语义信息，建立了一种新9 的模 式识别方法一语义句法模式识别方法。这种方法简单、合理，从某种意义上讲， 更符合人的思维实际，受到国内外广泛地兴趣、重视和研究，c o m b j n in g s t a t i s t i c a a n ds t er i cr u r a lm e t h o d s ) ， s u r v e y p i c t u r ep r o c e s s in g ：1 9 8 0 和 s u r v e y p i c t u r ep r o c e s s i n g ：1 9 8 2 ) ) 等文将语义句法方法作为典型的代表性 方法做了详细的分析、比较和充分的肯定。值得指出的是，每一种文法对应着一 种用以识别的自动机，语义句法方法中有限状态属性文法的引入大大简化了句法 部分使复杂语言结构的描述变得简洁、有效。 8 0 年代初期，在多次有启发性的讨论中，建立了”将语义句法方法的思想引入 人工智能的知识表达中”的设想。为此，经过大量的工作，进一步把关系属性等引 入句法模型，从统一的观点出发，把模式识别中的统计方法、句法方法，人工神 经网络论及专家系统等方法结合起来，揭示了模式描述与知识表达间的一致性， 完成了句法模式识别的奠基人k s ，f u 教授去世后，他的友人们对句法模式识别可 能做出的贡献。之后，人工神经网络研究复苏，深感基于符号描述的局限性后， 把人工神经网络与传统的人工智能中符号处理两者有机的结合起来。改进并增强 了人工神经网络的联想记忆能力，作为一种用于知识表达的模型引入体系之中， 成为关系属性的一种描述方法，形成了描述从知识结构分析到知识表达的”综合各 种模型的知识系统”这一概念。 1 9 9 2 年，在对原有工作和人工智能发展史回顾与总结的基础上，把工作上升 到智能系统一级。将模式识别作为一种重要的智能现象进行了深入的分析和反思， 试图寻找指导工作进行方向的方法论，也就是研究智能现象的方法论。此时，系 统科学中，著名科学家钱学森与于景元、戴汝为合作，针对开放的复杂巨系统提 出了从定性到定量的综合集成方法论。经过长时间的思考，结合工作中的深切体 会，形成了智能系统的综合集成理论，引起了国内外学者的兴趣与关注。美国 h a r v a r d 大学的y c h o 教授专门组织了研讨小组，对智能系统的综合集成理论进 行了广泛而深入的研究和热烈的讨论。值得指出的是，这一理论中一个十分重要 的观点就是人将作为智能系统中的成员加以集成，这就是建立人机结合的智能系 统。围绕这一理论的建立，引出了针对手写汉字识别的基于人工神经网络的特征 选取方法模拟形象思维的子结构检测器方法以及对模式识别中有效的”反向传 播”模型的缺点加以克服，提出竞争学习算法等成果。 在智能系统综合集成理论的基础上，系统而深入地总结和分析了模式识别的 各个环节及其关系，提出了集成型模式识别方法。每一种识别方法都有各自的优 势和局限性，其识别精度和适用范围也有一定限度。基于不同特征抽取和匹配方 第一章绪论 法的分类器或多或少具有互补性。对多个分类器的识别结果进行集成可以弥补各 个分类器的不足，提高总体性能。根据组成系统分类器机理的不同，采用了不同 的集成机制，包括基于传统方法的串行集成方法和基于人工神经网络的并行集成 方法。在网络集成方法的研究中，建立了反馈集成网络理论，从而使模式识别不 再局限于简单的映射，而提高到一种闭环非线性动力学系统行为，这更符合人脑 模式识别的实际，引起了国内外热切地关注。 集成型模式识别方法是一种承上启下的模式识别方法，强调开放的系统观和 人一机结合的重要性，是综合集成方法论在模式识别中的体现，已成为模式识别领 域的主要发展趋势之一。 进入9 0 年代，v a p n i k 提出统计学习理论后，$ v m 理论才得到了广泛的重视。 统计学习理论较好地解决了线性不可分的问题，并正式奠定了s v m 的理论基础。 s v m 的出现为基于模式识别的字符识别领域提供了新的工具，并成功的应用于模式 识别和函数拟合等领域，其表现优于己知的一些神经网络方法。 手写字符识别技术应用于邮政编码、统计报表、财务报表、银行票据等方面， 可以实现信息的自动录入，无疑会促进工作效率。因此，手写字符的识别研究有 着重大的现实意义，一旦研究成功并投入应用，将产生巨大的社会和经济效益。 1 2 本文的主要工作 本论文在探索手写字符识别的方法上采用了统计学习理论，利用支撑向量机 s v m 作为基本的识别工具。研究的主要内容包括四部分：s v m 基础理论的研习；引 入后验概率的修正s v m ；i c a 及其在特征提取方面的研究：引入后验概率的修正s v m 与i c a 结合实现手写字符识别。本论文的章节安排如下： 第二章给出了s l t 的基础理论。统计学习理论是一种研究基于样本的机器学 习理论。v v a p n i k 等人从六、七十年代开始致力于此方面的研究，到九十年的中 期，其理论的不断发展和成熟，已基本形成一套比较完整的理论体系。在这一理 论基础上发展了一种新的通用学习方法一支撑向量机s v m 。它是一种普遍适用的方 法，已经广泛的用于模式识别、回归估计、函数逼近、密度估计等方面。 第三章讲述了s v m 及其引入后验概率的修正s v m 方法。目前，研究引入后验 概率修正s v m 较少大多都是沿用v a p n i k 的思想、方法，把精力用在解二次规划 的数学技巧上，或者直接用v a p n i k 的计算方法应用到某一领域得出一些应甩结果。 引入后验概率的修正s v m 方法在原分类超平面的基础上不断修正分类超平面，提 高分类f 确率，从而避免了寻找最优二次规划的麻烦，同时将大规模训练样本集 化为小规模训练样本集。 第四章探讨了独立分量分析i c a 及其在图像特征提取方面的应用。独立分量 基丁1 支撑向量机的手写英文字符识别 分析最初是由c o m o n 等人于1 9 9 4 年提出的，它解决了盲源分离等问题，应用于模 式识剐、图像、医学等领域，1 c a 从多变量信号罩找到一个线性的j l 二丌i 交的坐标系， 其坐标轴的方向 4 | 原始信号的2 阶及其高阶统汁特性决定，最终能够使各变缝之 州的独立性最大。应用独立分量分析i c a 对需要进行识别的字符图像预处理。i c a 方法将一幅图像看作是由一系列基图像经过线性组合而成，而这些基图像之间相 互不相关因此就可以利用其组合系数作为图像的特征代表原有的字符图像输入 s v m 进行识别。利用i c a 这一特点可以提取字符特征，降低输入数据的维数，从而 可以为下一步的s v m 识别过程提供好的数据集，用以提高识别率和识别速度。 第五章将引入后验概率的修j 下s v m 方法与i c a 结合应用于手写字符识别，采 用的字符库是n i s t 的手写英文字符和u s p s 的手写数字字符。首先将归一化的字 符数据通过i c a 提取特征，把数据维数从4 0 0 维降到5 0 维，保留了9 5 以上的能 量；然后将特征数据输入到引入后验概率的修正s v m 中进行训练和识别。采用这 种方法相对于采用原始数据和常规的s v m 训练识别，其识别结果和速度有显著的 提高。 第二章统计学习理论 第二章统计学习理论 基于数据的机器学习是现代智能技术中的重要方面研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。包括模式 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。 传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基 于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学 习方法实际中表现却可能不尽人意。 与传统统计学相比。统计学习理论( s t a t i s t i c a ll e a r n i n g t h e o r y ) 或( s l t ) 是 - z o o 专门研究小样本情况下机器学习规律的理论。v v a p n i k 等人从六、七十年代丌 始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，也由于 神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广 泛的重视。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习 问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多 原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) 。同时， 在这一理论基础上发展了一种新的通用学习方法一支持向量机( s u p p o r t v e c t o r m a c h i n e ) 或( s v m ) ，它已初步表现出很多优于已有方法的性能。一些学者认为 s l t 和s v m 正在成为继神经网络研究之后新的研究热点，并将有力地推动机器学习 理论和技术的发展 2 1 学习的表示 讨论一下在统计学习理论框架内定义的从样本中学习的情况。有两个变量集 合石x 矗。和y e y r ，他们以概率关系相互关联。我们之所以说它们之间的 关系是依概率的，是因为通常x 中的一个元素并不能唯一的确定为y 中的一个元 素，而更合适的应该是y 上的一个概率分布。可以通过假设一个定义在集合x y 上的概率分布p ( x ，y ) 来将其公式化。此概率分布p ( x ，y ) 未知，在很一般的情况下， 可将其写为：p ( x ，y ) = p ( x ) p ( y l x ) ，其中p ( y t x ) 是对给定的x 下，y 的条件概率，p ( x ) 是x 的边缘概率。提供给我们是有这种概率关系的样本，这就是被称为训练样本 的一个数据集合d ，= 戤，y ，) x y ，根据p ( x ，) ，) 对x x y 采样f 次得到。学习 问题存在于，对给定数据集d ，给出一估计量，即一个函数f ：x 斗y ，它可以用 柬埘给定的x x 中的任意值，预测一个y 值。 基丁支撑向姑机的手写英文字符识别 在统计学习理论中，解决学习问题中的标准方法在于定义一个风险函数，用来 度量与一个估计量相联系的平均误差量，然后在允许的误差值中，寻找有最低风 险的估计量。当利用f ( x ) 来预测y 时，用v ( y ，( x ) ) 来作为测度误差的损失函数， 那么，平均误差也就是所谓的期望误差风险： ， 厂 5 j 、，y ( y ，( x ) ) 尸( z ，y ) a x d y ( 2 1 ) 假设在一大”类函数f 上定义期望风险，并用，0 表示在f 中使期望风险最小的 函数： = a r g m i n i f ( 2 2 ) 函数兀是理想的估计量，通常称为目标函数。 2 1 1 经验风险最小化学习原则 不幸的是目标函数在实际中并不能找到，因为定义期望风险的概率分布 p ( x ，y ) 未知，仅仅可以得到它的一个样本集，即数据集d ，。为了克服这一缺陷， 需要一个归纳原则，借助它，可以从已有的有限数目的训练数据中进行“学习”。 由v a p n i k 提出的统计学习理论建立在所谓的经验风险最小化( e r m ) 归纳原则基 础上。e r m 方法包括：用数据集d ，建立一个期望风险的随机近似值，通常称为经 验风险，定义为： 1 i ，。 厂；f = 2 v ( y i ，f ( x i ) ) ( 2 3 ) i = l 核一t 5 问题是在f 中，经验风险的最小值的期望风险是否与厶的期望风险接近。问 题并不是能否必然的找到 ，而是在解的期望风险很接近厶的期望风险时，能否 “仿造” 。从形式上来说，该问题就是要找到在什么条件下，e r m 方法以概率 ( 所有状态都是依概率存在的，因为在数据上，以p ( x ，y ) 开始的) 满足： j i m ，。， 石；， = i m ， z 】= ， 】 ( 2 - 4 ) 式中，我们用f 表示f 内经验风险( 2 3 ) 的最小值。 可以看到，在概率中，为了使式( 2 4 ) 中的极限存在，或者更确切地晓，为 了使经验风险最小化原则具有非平凡一致性，下面的一致性大数定理( 它可解释 为在f 内经验风险依概率一致性收敛于期望风险) 是一个充分必要条件： f1 ；i n 2 p s u p ( 1 f 卜l ，i f ) s = 0 v e 0( 2 - 5 ) 第二章统计学习理论 直观地，若f 非常“大”，那么，总能找到f f ，其经验风险为0 。然而这并不 能保证_ 的期望风险也接近0 ，或接近儿 。 典型地，讨论了双边依概率一致性收敛： f l i m j p s u p l i f 卜i f ；1 ps _ 0 v s 0 ( 2 - 6 ) 【，e 7j 显然上式包括了式( 2 5 ) 。集中讨论强双边的情况并指出，若要得到单边一致性收 敛，只要对这一理论进行一些极小的技术上的改变即可。我们不讨论有关一致性、 非平凡一致性、双边和单边一致性收敛等之间关系的技术问题，从现在开始，集 中讨沦双边依概率一致性收敛，简单的将其称为一致性收敛。 e r m 的一致性收敛理论已由v a p n i k a n d c h e r v o n e n k i s 等人进行了相应研究。 2 1 2 用于密度估计的一致性收敛 g l i v e n k o c a n t i l l i 和k o l m o g o r o v 等人己研究7 为解决密度估计i 司题所考虑的 假设空间这一特定情况下的一致性收敛。 设x 是一个一维随机变量( 结果可以推广到多维) ，考虑这样一个问题：根据 f ( x ) 获得一组随机的、相互独立的样本z ，x ，_ ，从该样本集来估计x 的概率 分御函数： f = 瞅 s = 鳃p 誓璺，i f 。) 一c ，( a ；f ) i 占 ( z 7 ) 其结果变为：在特定假设空阳j 和这罩构造的损失函数下，对每个s 0 ，( 2 - 7 ) 式 的极限均为0 ，即一致收敛成立。特别的，有下述定理成立： 定理2 1 1 ( g 1 i v e n k o c a n t e l l i ，1 9 9 3 ) 极限 舰尸( 誓墨广( 小c 扣i = 。 成立。 定理2 1 2 ( k o i m o g o r o v s m i y f i o v 分匆) 经验分布函数与真实分布函数的收敛率 服从如下规律： 脚尸( 以。s u p 。 f ) 一，( 口；叫 占) = 一z 喜( 一广1 e - 2 ， 引理2 1 2 ( k o l m o g o r o v ，1 9 3 3 ) 概率函数 p ( 撕州s 。u p 。，l m 卜( 叫3 1 s u p l f 。, ( x ；，) 一f ( j ) j = s u p l f 0 p ( y ；1 ) - f 。( y ) i 冈此，对任意连续分却函数，概率函数p s u p k 。( 口；，) 一广( 口) j 0 ，_ ” f 2 收敛性的快速逼近率的一个充分条件是： l i m 里竺! 堡坠o v 0 ，_ + 。 f 它是否也是一个必要条件还有待解决。 3 对分布独立的( 即对任意p ( x ，y ) ) 快速收敛率的一个充分条件是： 第一二章统计学习理论 l i m 里掣：o , v 0 f - + m ， 对指示函数，这也是一个必要条件。 根据统汁学习理论，这三个量是在设计和分析学习机器时应该考虑的：v c 熵， 为了一种依赖于数据概率分布v ( x ，y ) 的分析而定义的退火v c 熵以及为了一种分布 独立性分析而定义的生长函数。尽管读者应记住分布依赖性结论在将来可能很重 要，但是我们仅考虑分布独立的结论。 不幸的是：在实际中，函数集的生长函数很难计算。因此统计学习理论r j 的 通用方法是运用生长函数的一个上界，它通过另一个重要的量v c 维给出，这足另 一个函数集的复杂度，即容量的( 较松的) 衡量方法。我们集中于讨论这一量， 但是有一点很重要，那就是读者应记住v c 维在某种意义上是对数据复杂度一种 “弱”的度量，因此它通常导致生长函数松的上界：总之理论上来看，直接使用 生长函数是较好的情况。我们现在讨论v c 维和其在学习中的应用。 首先在指示函数情况下来定义v c 维，其后再将其推广到实值函数。 定义2 1 5 指示函数集合：和驴( 工) l 厂f ) 的v c 维是向量x i , x 2 ，x h 的最大数目 h ，这些向量能够用该集合的函数以所有2 种可能的方式将其分为两类。 如果，对v n ，总能找到n 个点x l ，x 知x 。，以所有2 6 种可能的方式对其分类，那 么我们况，集合的v c 维是无穷大的。 这个量重要的特性是，尽管我们提到v c 维仅对生长函数提供了个上界，但 在指示函数情况下，v c 维的有限性是一致性收敛独立于基本分布v ( x ，y ) 的一个充 分必要条件。 定义2 1 6 设a s v ( y ，缸) ) 丑，f f ，且a ，b m 。集合杪( y ，o ) ) ，厂f ) 的v c 维被定义为指示函数集汐。厂( y ，( z ) ) 一口l 口( 爿，占) 的v c 维。 有时我们称妒b ，( x ) x f 的v c 维为f 内v 的v c 维。很容易看出：在 y 一l ，+ l 和v ( y ，厂( x ) ) = o ( - y f ( x ) ) 作损失函数时，用定义2 1 6 计算f 内v 的 v c 维等于用2 1 ，5 计算指示函数集 口( r ( x ) ) ，f f 的v c 维。在实值函数情况下， v c 维的有限性仅仅是一致性收敛的充分条件。在本章最后，我们将讨论一种提供 必要条件的性能度量方法。 v a p n i k 和c h e r v o n e k i s 工作的个重要成果是：假设空间中经验风险与期望风 险之间的一致性偏差与v c 维有关。如下面定理所示： 基r 支撑向昔机的手写英丈字符识别 定理2 1 3 ( v a p n i ka n dc h e r b o n e n k i s ，1 9 7 1 ) 设a v ( y ，厂( x ) ) b ，f f ，f 是一个 有界函数集，h 是f 内v 的v c 维。那么，下列不等式对f 中的所有元素f 至少以 概率1 一h 同时成立： h 型_ 】n 俜胁型- l n f 旦 】( b l a ) t 半 ， ， 0 ，e r m 方法在f 内是依概率一致 性收敛的，( 或者说有s 一一致性收敛) 如果： r、 脚p 例- i f ；1 - i 州 5 2 0 ( 2 “) 注意到，若对v 0 ，式( 2 1 4 ) 都成立，那么我们有一致性收敛( 式( 2 6 ) ) 。可 以看到( 【v a p n i k ，1 9 9 8 1 的变化) 一概率- 致性收敛暗含： ，惦j ( ，比】+ 2 6 ( 2 1 5 ) 从概率角度，和前面一样，z 是经验风险的最小值，o 是f 内期望风险的最小值。 有关旷维的基本理论如下： 定理2 1 4 ( a l o n e t a 1 ，1 9 9 3 ) 设a s v ( y ，( j ) ) s b ，f f ，f 是有界函数集。对 v o ，若f 内v 的维对某个常量岱去，r = 甜是有限的，那么e r m 方法依 概率占一收敛。 定理2 1 5 ( a l o n e ta 1 ，1 9 9 3 ) 设a v ( y ，厂( 工) ) b ，厂f ，f 是有界函数集。e r m 方法是一致性收敛得当且仅当：在f 内v 的一维对v r 0 是有限的。因此，对 v r 0 ，r 维的有限性是e r m 方法对实值函数来说，分布独立一致性收敛的一个 竺 兰! ：壅堡塑墼塑堕至! 茎塞兰堕堡型 充分必要条件。 定理2 i 6 ( a l o n e t a l ，1 9 9 3 ) 设a 矿( ) ，厂( x ) ) b 、f ，f 足有界函数檠。刈 1 - v 。2 o 和所有7 亏我们有：如果对，= 伽( a 磊1 ) ， ，是在f 内v 的维，且 r d 女 7 h ，是有限的，那么： 尸l 。s 卜u ，p l i 。，驴；，卜，驴】 占f g ( 占，一，) ， 。：。， 其中，g 是 ，的一个增函数，s 和，的减函数，且有g 一0 ，当，斗m 时。 从这一定理我f l ；! t t l 容易看到。对v 占 0 和所有，乓： p ，j ，阮】+ 2 e 1 - 2 9 ( 6 ，h ，l ( 2 1 7 ) 其中，) 和前面一样，是f 内的期望风险最小值。要记住的一个重要发现是：定 理2 1 6 需要f 内损失函数v 的维。在分类情况下，这就意味着，如果要得到期 望错分的界，我们必须利用损失函数曰卜( 工) ) 的一维。 2 2 结构风险最小化学习原则 s r m 的方法是定义一个假设空问的重叠序列日。c ：c j v 刚) ，n ( ，) 是，的非 增整函数。其中，每个假设空间h 。有v c 维，且是有限的并比前面所有集合的v c 维 都大。如果吩是空间e 的v c 维，那么h i 亡h 2c 州) 例如：片，可以是i 阶多项 式集合，或是有i 个节点的样条集，或是一些更为复杂的非线性参数。对结构的每 个元素h ，学习问题的解是： 丸= a r g r a m i n l 。m ( 2 - 1 8 ) 由于我们定义结构的方式，很显然，f 越大，z ，的经验误差越小( 因为我们有大 的“灵活性”来适应我们的训练样本) ，但( 2 1 2 ) 式右边的v c 维部分则越大。用这 样一个越来越复杂的假设空间的重叠序列，s t t m 学习方法包括选择空间日。因 为只有这样，式( 2 12 ) 的右边才是最小化的。可以看到， v a p n i k ，1 9 8 2 解f ( f l 不等式( 2 一1 2 ) 和( 2 - 1 3 ) 至少以概率( 1 一_ ) “z 1 一月( o q 成立。其中，用h 。代 第二章统计学习理论 替 ，用h ，中期望风险的最小值4 2 替f o ，用五1 f ) ，代替z 。 恰当的选择n ( 1 ) ，n j 以看到，当，专o o ，n ( t ) 一o 。时，浚方法解的期望风险依概率 逼近1 二h = u ：，中期望风险的最小值，即阮 而且，若目标函数兀属。一h 的闭，那么，式( 2 - 4 ) 依概率成立。( 见 v a p r d k ，1 9 9 8 1 ) 然而在实际中，是有限的( “小”) ，因此疗( ，) 小意味着h = u ：日是一个小空 f n j 所以，瞻】可能比目标函数兀的期望误差更大，因为f o 可能不在h 中运用 近似理论的结果，阮】与，阮】之间的距离称近似误差并且是有界的 2 2 1 使用_ 维的结构风险最小化 旷维理论证明r 下面要描述的“推广”的s r m 方法的f 确性需要记住的是， 这罩描述的方法只具有理论意义，且只用作r n 和s v m 的理论动机。应该清楚，以 上所有的定义和分析对任何假设空间h 仍成立，其中用h 中的期望风险最小值来 代替 z 是h 内经验风险最小值，h 是h 内损失函数v 的v c 维 设，是训练数据的个数，对一固定s o ，z 砉，r 。去占，像前面一样，考虑一 假设空间的重叠序列h ， h ： h 州一，其中每个假设空间h ，的一维是有限的且 比前面所有集合的维都大例如，若h ；是空间。的一维，那么 h ，h ：h 训) 对结构的每个元素，认为学习问题的解都是： z ，= a r g 罢i n i , , , p l f ； ( 2 - 1 9 ) 由于此处定义结构的方式，从而有：i 越大，z ，的经验误差越小( 因为这样有 更大灵活性”来适应我们的训练数据) 但不等式( 2 1 6 ) 的右边越大，使用这样一 种越来越复杂的假设空间的重叠序列，推广的s r m 学习技巧包括找到结构元素 h 。( f 对此，经验误差与( 2 1 6 ) 式右边部分的折衷是最优解一种实用的想法是： 为每个h i 在数字上找到有效的s ，使得( 2 1 6 ) 式的解对所有，都相同，然后选择 z ，使经验风险与占，的和最小化a 丝j 支撑向苗机的手写英文字符识别 推测：当f - ，选择合适的n ( t ，s ) ，使得随着，斗o o ，有n ( 1 ，) - 9 0 0 ，该方 法解的期望风险依概率收敛到一个小于2 , - ，远离h = 【j ：1 日内最小期望风险的 值。注意到，刘固定的，描述了一种s r m 方法。若对每一r 0 ，h 的旷维是 有限的，那么我们1 j 以更进一步改善推广的s r m 方法，使得随着，斗。，有占一0 。 假设，若目标函数兀属于h 的闭，那么，当2 哼c o ，选择合适的占，n ( 1 ，s ) 和r * ( 7 ，s ) ， s r m 方法的解可以被证明依概率满足公式( 2 4 ) 。找到s n ( 1 ，) 和n ( ，s ) 的恰 当形式是一个期待解决的问题( 这主要是一个技术问题) 。而且，因为在“标准” s r m 情况下，实际中，是有限的，因此h = l