（计算机软件与理论专业论文）基于支持向量机的手写体字符识别.pdf

摘要 光学字符识别( o c r ) 是指将纸上的文字转化为计算机所能处理的形式( 如 a s c i i 码) 的过程。手写体字符识别是光学字符识别的一个分支，手写体字符识 别在邮政信件分拣、银行票据的自动处理、手机和掌上电脑的输入等领域有着巨 大的作用。由于手写体字符的随意性，使其识别难度大于印刷体字符。而诞生于 上世纪九十年代的支持向量机是一种基于小样本的新的统计学习方法，在许多方 面( 包括字符识别) ，都取得了优秀的效果。但是，传统的支持向量机训练算法 在时间复杂度上面的表现不尽如人意，如果训练样本的数量过大，消耗的训练时 间和存储空间会急剧增大。针对这种情况，本文提出一种改进算法，即尽量选择 那些有可能成为支持向量的训练样本来具有针对性地加以训练，从而可以减少时 问与空间的消耗。 本文主要做了以下工作： l 由于核函数的存在，使得训练样本之间的距离在由输入空间到特征空间的 映射之中产生了变化。为此，本文分析了训练样本之间的距离在输入空间与特征 空间的联系。 2 本文针对不同的核函数，探讨并证明y n 练样本在输入空间和特征空问的 两个空间的距离之间的联系，并在此基础之上，提出一种基于k n n ( kn e a r e s t n e i g h b o r s ) 属性的训练样本选择方法，通过减少参加训练的样本数来减少训练所 需要的时间。本文探讨了算法所选择的样本数。由于选择的样本数要小于原训练 样本集而包含的支持向量却与原样本集相当，从而在减少训练时间的同时保持了 分类正确率。 3 在i i n i s t 和u c i 的数据库上对本算法与s m o 算法进行了对比实验，得到的 结果是在辩识正确率基本不变的情况下，消耗的时间大量减少 关键词：支持向量机；核函数；字符识别 b s t r c t o p t i c a le h a r a e t e a r e c o g n i t i o n ( 0 1 1 1 e a i l 5r e a d i n gt e x tf r o mp a p e ra n d t r a n s l a t i n gt h ei n 城g 锚i n t oaf o r mt h a tt h ec o m p u t e r 啪m a n i p u l a t e ( f o re x a m p l e , i n t o a s c i ic o d e s ) n a n d p r i a td l a l l l c t 廿r e e o g a i t i o ni sab r a n e l ao fo c ra n dp l a y s 缸 i m p o r t a n tr o l ei nm a n yf i e l d ss u e l a 勰p o s to f f i c es y s t o m 。b a n ks y s t e ma n dt h ei n p u to f c e l l sa n dp d a b t x ? a l u s eo fi t sd u m g e 埴b i l i t y , h a n d p r i n tc h t l l * a c t e ti sn l o t od i f f i c u l tt o b er e e o l 卿z e at h a nm a c h i n ep r i n tc h a n l c t e f $ v m ( s u p p o r tv e c t o rm a c h i n e ) w h i c h w a sb o mi nl a s tc e n t u r y9 0 sd o e sag o o dj o bi nm a n yf i e l d si n c l u d i n gc h a i l l c t 盱 r e e o g n i t i o d b u t ( r a i n i n gas v m n e e d sal o to ft i m ea n dm e m o r ye s p e c i a l l yw h e nt h e d a t a b a s eo ft r a i n i n gp a t t e r n si sl a r g e t h i sp a p e rp r o p o s e san e wa l g o r i t h m ：s e l e c t t h o s ep a t t e r n st h 雠呲m o s tl i k d yt ob et h es - a p p o r tv e c t o ra n di r a i no i lt h e ma n dt h e n w ec 孤s g v eal o to f t i m e i nt l a i sp a p e ro u tm a i n w o r ki sa sf o l l o w s 1 t h er e l a t i o n s h i po fd i s t l m c l ，o fn a i n i n gl m t e m sb e t w t 地l li n p u ts p a c ea n d f e a t u r os p a c eh a sc h a n g e db e c a u s eo ft h ek o m e lf u n c t i o n s ow ca n a l y z et h e r e l a t i o n s h i po f d i s t a n c eb e t w e e nt w os p a c e s 2 b a s e do nt h ea n a l y s i so fr o l a t i o m l a i po fd i s t a n c eb c t w o c nt h et w os p a c e s ，t h i s p a p e rp r o p o s e sat r a i n i n gp a t t e r ns e l e c t i o na l g o r i t h mw i t ht h ep r o p e r t yo fk n n ( k n e a r e s tn e i g h b o r s ) t h i sp a p e ra n a l y z e sh o wm a n yp a t t e r n sw i l lb es e l e c t e d al o to f t i m ew i l lb es a v e db 搬i nt h ep r o p o s e da l g o r i t h mj t t s tas m a l lp a r to fi r a i n i n g p a t t e r n sw i l lb es e l o e t e dw h i l em o s to f t l a es u p p o r tv e c t o r sa l s ow i l lb os e l e c t e d 3 t h ee x p e r i m o n t sd o n e0 1 3 t h ed a t a b l l o f m n i s ta n di j c is h o wt h a tt h et i m e e o m u m p t i o no fl r a i n $ v mo ns e l e c t e dp a t t e r md e c r e a s ea l o tw h i l et h eo i t o i r a t eo f t h er e c o g n i t i o ni sn e a r l yt h es a l r l l ea sw el r a i n $ v mo l d a l lt h ep a t t e r n su s i n gs m o a l g o r i t h m k e y w o r d s ：s u p p o r tv e c t o rl d a i n e ) k e r n e ll f r n e t i o l l ) c l a a r a e t e r r e e o g n l t i o n 第一章绪论 1 1 研究背景及意义 第一章绪论 手写字符识别的目的是利用电子计算机自动辨认人手写在纸张上的字符，从而 实现办公自动化来提高人们的工作效率的技术。它是光学字符识别o c r ( o r c d e a l c h a r a c t e rr e c o g n i t i o n ) 的一个分支。手写体字符识别可分为两大类：联机手写体字符 识别和脱机手写字符识别。联机手写体字符识别是经过各种输入设备 如手写板、 触摸屏等) ，将字符的轮廓及其笔划顺序按顺序送入计算机中。而脱机手写体字符 是没有笔划顺序这一重要特征的，输入到计算机中的只是2 维的图像。而且相对于印 刷体字符，手写体字符由于不同的人的丽不同，造成即使是同一字符，不同的人书 写也会因字体，习惯不同而大不一样。因此，相对于其他的字符识别技术，脱机的 手写体字符识别的难度更大 而随着信息社会的加速到来，越来越多的数据要输入计算机系统。大量的书籍、 杂志、报刊、文章、通知等等需要电子化，变成可供查询的数据库内容，这需要字 符的自动识别；邮件自动分拣机、税务机关和车辆登记所采用的自动识别管理系统 也离不开字符识别技术。个人数字助理p d a ( p e r s o n a ld i g i t a la s s i s t a n t ) 和许多手机， 其主要的输入方式也是手写输入，因此，字符识别具有广泛的意义。 欧美国家，对o c r 技术的研究最早可以追溯到上世纪2 0 年代，1 9 2 9 年t a u s h e k 就在德国获得了一项有关o c r 的专利。1 9 5 8 年c r i m s a l d e 等人首次利用计算机进 行光学字符识别，他们用飞点扫描器对输入模式进行扫描，并将之与存储在计算机 中的模式进行比较，并作出判断。经过多年的不断改进和完善，并伴随着计算机技 术的飞速发展，o c r 技术现在已经广泛应用于各个领域，使大量的文档资料能快速、 方便、省时省力和及时地自动输入计算机，实现信息处理的电子化。 在我国最早的手写体字符识别系统可以追溯到7 0 年代初，中科院自动化所的 科技工作者胡启恒院士等人于1 9 7 4 年开始研制手写体数字识别系统并成功的应用 于邮局的信件自动分拣系统之中。8 0 年代开始，清华大学自动化学院，北京大学等 高校开始系统的对字符识别技术进行研究并取得成果。 最早的字符识别是；f ! 用模板匹配算法实现的，后来，人们用几何矩，特征变换。 直方图，f i s h e r 线性判别，非线性判别函数以及人工神经网络，支持向量机等算法 进行字符识别。1 9 8 6 年r u m e l h a r t 和m c c l e l l a n d 合著的p a r a l l e ld i s t r i b u t e d p r o c e s s i n g ：e x p l o r a t i o ni nt h e m i c r o s t r u c t u r e so f c o g n i t i o n 两卷书出版，对神经网络的 迸展起了极大的推动作用。尤其是r u m e l h a r t 提出了多层网络b a c k - p r o p a g a t i o n 法 青岛大学硕士学位论文 或称e n o rp r o p a g 越o n 法，这就是后来著名的b p 算法。受到许多学者的重视，在 包括字符识别的许多领域中取得了相当不错的效果。进入9 0 年代。v a l m i k 提出统 计学习理论后，s v m 理论才得到了广泛的重视。统计学习理论较好地解决了线性 不可分的问题，并正式莫定了s v m 的理论基础。$ v m 的出现为基于模式识别的字 符识别领域提供了新的工具，并成功的应用于模式识别和函数拟合等领域，其表现 优于己知的一些神经网络方法。但是，s v m 的训练时问会i 菀p 昔训练样本数的增大 而急剧增加从而限制了其在许多应用中的表现，因此，需要对其加以改进。 1 2 本文的所做工作及内容安排 本文首先对字符识别过程进行了详细地介绍，并对结构特征和统计特征加以对 比。然后本文对支持向量机的原理与常见的支持向量机的类型作了介绍。本文的创 新之处在 l 对训练样本在输入空间与特征空间中的距离关系作了推导，即针对不同的核 函数，训练样本之间的距离在输入空间和特征空间变化的规律不同。 2 根据训练样本在输入空间和特征空问这两个空问的距离关系提出了一种基 于k n n ( k n e a r e s t n e i g h b o r s ) 属性的支持向量机的训练样本选择算法，即尽量选 择那些有希望成为支持向量的训练样本本文详细的介绍了该算法的思想并对其理 论复杂性加以细致地分析，并将该算法应用到字符识别中，取得了良好的效果 本文主要内容如下； 第一章阐明了本文的研究背景，介绍了字符识别的历史和研究现状，并概述了 本文的主要研究工作 第二章对字符识别的过程加以介绍，特别是对统计特征和结构特征加以介绍， 目的是为了使读者对支持向量机所采用的统计特征有更好的了解。 第三章介绍了支持向量机的理论基础以及经典的支持向量机的改进算法。 第四章提出了一种新的算法，即利用训练样本的心咐属性对训练样本加以选 择，由于拨函数的存在，使得训练样本的州可能发生变化，为此，对训练样本 在输入空间与特征空间的距离关系进行了讨论。对样本选择算法的思想及步骤进行 了详细地描述 第五章对该算法从理论上加以分析，指出算法的有穷性及算法选择的训练样本 数 第六章将该算法应用到字符识别当中，在m n z s t 和u c i 的数据库上进行对比 试验并取得了良好的效果。 第七章总结全文，对本算法的不足及以后值得进一步研究的方向做了展望。 2 第二章字符识别技术 第二章宇符识别技术 通常，字符识别过程可分为三个主要部分：l 预处理。2 特征提取。3 分类器 分类。预处理是为了保证特征提取的正确性，而特征提取则是最后分类的基础。下 面，我们分别加以介绍。 2 1 预处理 预处理的主要目的是去除噪声，压缩冗余信息，为特征提取做好准备。预处理 是字符识别过程中的重要一环，它可以消除原始图像中一些与类别无关的因素( 如 尺寸和位置的归一化) 。由于一般都在预处理后的图像上提取特征，因此如果这个 步骤结果不理想，往往会给后面的特征提取阶段带来无法纠正的错误。预处理主要 包括二值化，去噪、锐化、分割、逼近、细化、归一化等过程1 1 】1 2 【”1 4 。下面我们 分别加以介绍 ( 1 ) 二值化 二值化指的是将灰度图像转化为黑臼两个等级的过程。在扫描过程中，图像每 一像素点的灰度值定义为光照下以该点为中心的区域上的平均光照亮度。二值化过 程可看作是对原扫描图像的映射交换过程，当像素灰度值小于一定阈值时，被映射 成黑点。二值化的最终目的应为：原图像中反映图像结构的灰度值差别经映射后被 保留，而不反映图像结构的灰度值抖动被消除，从而最终得到的只是构成字符图像 的关键信息。 ( 2 ) 去噪 二值化后，影晌文本图像质量的噪声源大体分为三种：文稿原件本身带有的 污损、墨点。文本的背景色造成图像二值化产生的干扰。扫描设备本身产生的 光电子噪声和热噪声。其中可以通过设计有效的白适应二值化算法来加以克服： 可以通过分析并建立噪声模型，使用图像复原的方法减小噪声的影响；中提到 的干扰是不可避免的。因此设计去除干扰和平滑算法的一般要求是：尽量去除噪声 点和噪声块，而不影响字符图像的完整性；消除字符边缘的毛刺，但不影响字符图 像的拓扑结构。 ( 3 ) 字符分割 字符分割的目的是便于对单个字符进行迸一步的单独处理。因为一般字符图像 均能满足相邻文字行、列间至少有一行或一列全为背景像素这一条件。因此，分割 是比较容易实现的。 3 青岛大学硕士学位论文 ( 4 ) 细化 细化不仅仅是压缩冗余信息的需要，同时还是对模式进行结构分析的需要。另 外，输入所产生的噪声往往集中在字符笔划的边缘上，通过细化可以消除这些噪声 并保持原始图像重要的几何和拓扑特征字符细化的基本要求如下：要保留原有笔 划的连续性，不能由于细化造成笔划断开；要细化为单线，即笔划宽度只有一个像 素；细化后的骨架应尽量是原来笔划的中心线；要保持文字原有特征，既不要增加， 也不要丢失；速度快细化的算法很多，但大多数细化算法都是从字符的边界开始逐 层移去黑点，称之为脱壳算法。文献例对细化算法有详细的描述。 ( 5 ) 逼近 由于手写体的字符行中每个字符的书写位置有高有低这样在进行字符分割后。 得到的单个字符会位于一个较大的矩形框中。如果不做行逼近处理，以后提取特征 时会使提取的特征不稳定，所阻有必要对分割后的字符进行行逼近处理。 ( 6 ) 归一化 归一化是指将不同大小的字符圈像映射到固定大小的字符点阵中来满足识别的 需要。归一化是预处理中非常重要的一环，由于原始图像在大小方面存在着很大的 差异，必须进行归一化处理，使其具有相同的大小。以利于特征提取和识别的进行 此外。常见的预处理手段还包括倾斜字符的校正等措旌。预处理是字符识别过 程中的基础环节。关系着以后特征提取以及分类的准确性 当比较两个被识别的模式时，二者之间必须找出可作比较之处。当认为两个模 式属同一类别时，二者必须在某一特性空间内合乎一定的度量准则，这样的特性空 间也可以说是特征空间，特征提取也因此成为模式识别中最本质的问题之一【”。特 征提取的效果直接关系着最终的识别效果。 d t m j v e f 和l 矗m 盯【7 1 定义特征提取为：“从原始数据中提取可以用于分类的相关 信息，使得新的模式表达可 ；乏减少类内的差异，同时增大类闻的差异。”这同时也 是衡量一个特征提取方法优劣的准则对特征提取而言，如何提取出相对于位移、 大小、旋转、变形等具有不变性的特征是模式识别研究的重要目标之一。虽然众多 研究者为此付出大量工作，但目前还没有找到一种普遍适用的特征，能够刻画模式 的共有和特有本质特性，可用这种特性来判定同一类别模式的共同归属和不同类别 模式的不同归属。鉴于人所具有的模式识别能力，早期研究者从直觉上觉得至少对 4 第二章字符识别技术 于某一具体应用而言，这样的特征是存在的。他们为此提出不少的不变量分析方法 删m ，不过由于计算机性能上的制约，使得很难在当时给这些算法一个很好的评价。 现在模式识别所用的特征提取方法也困实际问题不同而异。根据文字识剐的方法， 其所用的特征可分为结构特征和统计特征两大类，下面将分别进行讨论。 2 2 1 结构特征 结构特征是文字结构的一种模型化的直接反映在字符识别中常用的结构特征 基元有：特征点、笔段、笔划等字符的构成以它们为基础。结构特征的优点是在 字符识别中，由于结构特征和人们的日常思维相近，很容易为人们所接受，因而一 直是研究的重点之一。结构特征提取的缺点是，在实际应用中抗干扰能力差，因为 在实际得到的文本图像中存在着各种干扰，如倾斜、扭曲、断裂、粘连、纸张上的 污点、对比度差等等，而且手写体字符由于人与人不同的书写习惯以及书写认真程 度的不同，会造成同一字符也会相差很大。这些因素直接影响到结构基元的提取， 假如结构基元不能准确地得到，后面的推理过程就成了无源之水。常见的结构特征 如下。 ( 1 ) 点特征 点特征是一种重要的结构特征，它是指笔划的端点，叉点( 多个笔划相交的点) 。 拐点( 有明显书写方向变化的点) 等。其中，端点反映了字符中笔划的起点和终点 信息。叉点可分为三叉点和四叉点。三叉点是指该点周围有3 条线与之相连，四节点 是指该点周围有4 条线与之相连。在字符细化后是很容易得到点特征的。某点p ( x y ) 的交点数由下式计算： c ：委窆” 1 - 1 2 一( 1 ) 其中a ( i = 1 , 2 ，8 ) 为点p 的8 个相邻点的像素值，p t o j r p 9 = p l 。 1 c = - i 时，该点为端点； 2 c = - 3 时，该点为三节点； 3 c = 4 时，该点为四节点： 通过计算字符局部区域内的点特征，可以得到字符的局部点特征。局部点特征 在对相似的字符进行细分类时非常行效。相对来说，拐点的提取比叉点提取复杂， 最经典的方法是多边形近似法。即先提取笔划的两端点，然后根据每一点到两端点 所连直线的距离大小来确定该点是否为拐点。此外，也可以根据该点邻域的书写方 5 青岛大学硕士学位论文 向变化率来对拐点位置进行简单的判断 ( 2 ) 尖角特征 所渭尖角特征就是指诸如“a ”、“v ”、“m ”、“w ”等字符点阵中出现的 尖角。使用该特征可以将上述字符与其它字符区别开来该特征的提取是由看其临 域的点阵的左右( 或上下) 两部分的点阵的最大和最小值的匹配程度得到。 ( 3 ) 浮动模板特征 浮动模板特征主要用于对相似模式的细分。所谓浮动模板实际上就是一系列具 有特定位置关系的像素集合使用浮动模板时，将模板按所要检测的方向顺着图像 边缘移动，通过模板是否能与图像边缘重合来取值。 ( 4 ) 笔划及笔段特征 基于细化图像的笔划提取一般都是从笔划的端点或叉点等特征点开始，沿某一 方向跟踪直至遇上另一特征点为止。跟踪所得的结果为一个子笔段由于每次只沿 一个方向跟踪，因而跟踪过程比较简单但是因为细化方法本身的局限性，使所提 取的特征点不可避免地存在成为错误。如把一个四又点分成两个三叉点等，相应地 造成笔划段断裂，因而需根据笔段连续性等先验知识对跟踪的结果进行合并。 2 2 2 统计特征 上文已经说过，结构特征的抗干扰能力较差，而统计特征与之相比，在抗干扰 方面有较大的优势。相对结构特征而言，统计决策论发展较早，理论也较成熟其 要点是提取待识别模式的一组统计特征，然后按照一定准则所确定的抉馕函数进行 分类判断字符的统计模式识别是将字符点阵看作一个整体，其所用的特征是从这 个整体上经过大量的统计而得到的。统计特征的特点是抗干扰性强，匹配与分类的 算法简中，易于实现。不足之处在于细分能力较弱，区分相似字的能力差一些常 见的统计模式特征在特征提取的级别上可分为像素级特征、局部特征和全局特征 ( 1 ) 外围特征 字符的轮廓包含了丰富的特征，即使在字符内部笔划粘连的情况下。轮廓部分 的信息也还是比较完整的。这种特征非常适合于作为粗分类的特征，但细分的能力 不强。 g ) 宽度特征 宽度特征分为全局宽度特征和局部宽度特征。我们从字符的点阵的左右两个方 向分别扫描字符，将每一行分别碰到的非背景像素记为u x ) 和r 取) ，则字符的宽度为 w ( x 产r ( x 卜i 积) ，通过判断字符宽度小于某个阈值的行数所占总行书的比例来对该特 征加以取值。局部宽度特征是看宽度小于某一阈值的行所占某一部分的比例。 6 第二章字符识别技术 ( 3 ) 跳交特征 跳变特征是指字符的边缘发生不连续变化所表现出来的一种特征通过对相邻 两行( 或者两列) 进行比较，若变化大于某一阈值，则发生跳变。跳变特征可分为 左右跳变特征。 ( 4 ) 交截特征 交截特征是指某一行背景像素与目标像素交替出现的次数。交截特征可分为横 向交截特征和纵向交截特征。 ( 5 ) 交换特征 变换特征是指对图像进行某种变换，如k - l ( k a h u n e nl o e v o 变换，f o u r i c r 变换， w a v e l e t ( 小波) 变换等对字符点阵迸行变换。由于手写体字符的变化较大，因此不 是很适用。 ( 6 ) 几何矩特征 m , k hu 提出利用矩不变量作为特征的想法，引起了研究矩的热潮。研究人员又 确定了数十个移不交、比例不变的矩。如h u 矩i l “，z e r l l i k o q 矩等。人们都希望找到 稳定可靠的、对各种干扰适应能力很强的特征，在几何矩方面的研究正反映了这一 愿望。以上所涉及到的几何矩均在线性变换下保持不变。但在实际环境中，很难保 证线性变换这一前提条件。 国比划密度特征 笔划密度的描述有许多种，这里采用如下定义：字符图像某一特定范围的笔划 密度是在该范围内，以固定扫描次数沿水平、垂直或对角线方向扫描时的穿透次数。 这种特征描述了印刷体文字的各部分笔划的疏密程度，提供了比较完整的信息。在 图像质量可以保证的情况下。这种特征相当稳定。适合于脱机手写体字符的识别。 此外，还有特征点特征，微结构特征，差笔划特征等其他统计特征。 2 2 3 融合 统计模式识别方法将重点放在模式信息处理的数学规范上，以数值特征向量的 方式表达模式。便于找到合适的模式学习和匹配算法。但难于描述模式内部复杂的 几何及拓扑结构特性。结构模式识别方法则以形式语言为基础，侧重于句法结构分 析，但文法复杂。结构模式识别与统计模式识别各有优缺点，随着人们对于两种方 法认识的深入，这两种方法正在逐渐融合，网格化特征就是这种融合的产物。字符 图像被均匀地或非均匀地划分为若干区域称之为“网格”。在每一个网格内寻找 各种特征，如笔划点与背景点的比例，交叉点、笔划端点的个数，细化后的笔划度、 7 青岛大学硕士学位论文 网格部分的笔划密度等等，特征的统计以网格为单位。 2 3 分类 识别系统中采用的分类器有多种，但根据分界面的形状可分为线性分类器和非 线性分类器。在特征空间中分界面为超平面的分类器为线性分类器，否则为非线性 分类器。对统计模版匹配方法而言，常用的距离分类器、n 分类器、s o f m 分类 器等都可称为线性分类器。而如b p 网络分类器、r b f 网络分类器等则是非线性分类 器本文采用的支持向量机是非线性分类器。 8 第三章支持向量机( s t y ) 第三章支持向量机( s v g ) 支持向量机( s u p p o r tv e c t o rm a c h i n e ) 是由| p i i i k 及其合作者发明，在1 9 9 2 年计算 学理论的会议上介绍进入机器学习的领域的【”】0 2 0 3 。之后，支持向量机受到了广 泛的关注。在上世纪末及本世纪初得到了全面深入的发展，现在已经成为机器学习 领域的标准工具之一。支持向量机集成了机器习领域的若干标准，如最大同隔超平 面，m e r c e r t 燕，凸二次规划，松弛变量等技术。支持向量机在若干领域获得了目前 为止最好的性能在美国的科学杂志上，支持向量机被认为“是机器学习领域中的 一个令人瞩目的发展方向”。 支持向量机方法是建立在统计学习理论的v c ( v cd i m e n s i o n ) 维理论和结构风 险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最 佳折衷的一种算法。所谓支持向量，是一些特殊的训练样本，这些样本所组成的向 量决定着模式的分类，“支持”着分类平面，因此叫做支持向量。而支持向量机是 一种算法，是利用训练样本来建立分类平面。 3 1 支持向量机的理论基础： 3 i i 机器学习理论 长期以来，机器学习理论是哲学界和科技界都在研究的目标之一，所谓机器学 习通常是指从已知的数据样本出发来寻找某种规律，再利用寻找到的这些规律对未 来数据或无法观测的数据进行预测，模拟机器学习的历史可以分为4 个阶段，它 们分别以下面四个重要事件为标志： ( 1 ) 第一个学习机器的创立( 2 0 世纪6 0 年代) 2 0 世纪6 0 年代初，er o s c n b l a t t 提出了第一个学习机器的模型，称作感知器， 标志着人们对学习过程进行数学研究的真正开始。 ( 2 ) 学习理论基础的创立( 2 0 世纪6 0 一7 0 年代) 2 0 世纪6 0 年代末。m m i n s k y 和s f a p e r t 在感知器【1 4 j 一书中指出感知器 的缺陷并表示出对该方面研究的悲观态度，从而使得对感知器的研究陷入停滞状 态。然而，这段时间里统计学习的发展却是成果累累。v v a p n i k 等人确立了经验风 险最小化原则的理论【n 1 ：a n t t k h o n o v 等提出解决不适定问题的正则化理论；e p a r z e n 等提出密度估计的非参数方法。 9 青岛大学硕士学位论文 ( 3 ) 神经网络的创立( 2 0 世纪8 0 年代) 2 0 世纪8 0 年代初，h o p f i e l d 网络i l s 】以及多层感知罂的反向传播算法l ”1 的提出， 掀起了神经网络研究的热潮。这一阶段诞生了一系列重要的神经网络模型。比如t k o h o n e 的自组织映射网络f s e l f - o r g a n i c sm a p ，简称s o m ) 1 1 7 l ，ge 1 - i m t o n 的 b o l t z m m m 机【嘲以及d s b r o o m h e a d 和d l o w e 的径向基函数( r b f ) 神经网络【。 ( 4 ) 神经网络替代方法新的学习方法的创立( 2 0 世纪9 0 年代至今) 这一阶段，人们把更多的注意力放在了对神经网络的替代算法的研究上，统计 学习理论中的较高深的部分现在开始吸引更多的学者2 0 世纪9 0 年代初，随着建 立在结构风险最小化原则基础上的支持向量机的诞生，在此基础上延伸出7 一种基 于核的学习方法。 目前机器学习的常用的实现方法大致可以分为三种： ( 1 ) 参数统计估计方法 参数统计估计方法以传统统计学理论为基础，要求参数相关形式己知，训练样 本用来估计参数值。但是参数统计估计方法有较大的局限性：需要大量的已知样本 及其分布形式。只有在已知样本数趋向无穷大时经典的参数估计方法在性能才有理 论上的保证。因此在实际问题中，对有限样本数，很多方法都难以取得理想的效果 ( 2 ) 经验非线性方法 经验非线性方法的代表是人工神经网络，该方法利用已知样本建立非线性模型， 克服了传统参数估计方法的困难。但是由于缺乏一种统一的数学理论，应用中许多 因素需要凭经验确定，如阿络节点数、初始权值、学习步长的选择，同时还存在着 局部极小点，过学习，欠学习等问题。 ( 3 ) 统计学习理论( s t a i s t i c a ll c a l n i 赡t h c o 巧) v a i i 【等人早在2 0 世纪6 0 年代就开始研究有限样本情况下的机器学习i ；习题，但 是由于当时研究尚不十分完善，在解决模式识别问题中往往趋于保守，而且数学上 又比较艰涩，而直到年代以前并没有提出能够将其理论付诸实现的较好的方法。 加之当时正处在其他学习方法飞速发展的时期，因此这些研究一直没有得到充分的 重视直到9 0 年代中，有限样本情况下的机器学习理论研究逐渐成熟起来，形成了 一个较完整的理论体系即统计学习理论。与传统统计学相比，统计学习理论是一种 专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一 套新的理论体系。在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而 且追求在现有有限信息的条件下得到最优结果统计学习理论的一个核心概：叁是v c 维概念，它是描述函数集或学习机器的复杂性或者说是学习能力的一个重要指标。 1 0 第三章支持向量机( s v i ) 支持向量机在解决小样本、非线性及高维模式识别问题中表现出了许多特有的优势， 并且能够推广应用到函数拟合、密度估计等其他机器学习问题中。支持向量机的出 现将推动机器学习理论和技术有重大的发展相对于以前的机器学习方法，支持向 量机有3 个较明显的优势： ( 1 ) 支持向量机是专门针对有限训练样本情况的，其目的是得到在现有信息下的最 优解而不仅仅是样本数趋于无穷大时的最优解，在实际的应用当中，样本数几乎不 可能趋于无穷。 ( 2 ) 支持向量计算法最终将转化成为一个二次型最优化问题，从理论上说，得到的 将是全局最优点，而在神经网络中，人们不得不面对令人头痛的局部极值。 ( 3 ) 支持向量机算法利用核将实际问题通过非线性变换转换到高维的特征空间中， 在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保 证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维 数无关，从而避免了“维数灾难”。 既然支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，那么我们首先介绍一下这些概念。 3 1 2 统计学习理论与结构风险最小原理 3 1 1 1 结构风险最小原理 目前在机器学习研究领域影响较大的是h s i m o n 的观点1 2 0 1 ：学习是系统中的 任何改进，这种改进使得系统在重复同样的工作或进行类似的工作时，能完成得更 好。学习的基本模型就是基于这一观点建立起来的 图3 1 学习的基本模垂 给定机器学习算法a 以及相应的控制数，a 可以通过修改可调参数构造出不同的 分类函数( 对于分类问题) 或拟合函数( 对于拟合问题) ： ，如，它们组成一个有限 1 l 青岛大学硕士学位论文 或无限的集合h = ，如，称它为a 的假设函数集合。 对于分类问题，训练样本集上乙由n 个样本( x 。，弘) ( i = l 2 ，n ) 组成，其中 x 。e x ，乃e o l ，采用4 对分类算法进行训练获得分类方程上( 见，) ：x 呻 叫) ， 定义其上的o - i 损失函数为： z ( 工( 乜，x ) ，朔) 爿工( 见，x ，) 一只l 3 一( 1 ) 则算法在以上的经验风险( 训练错误率或训练偏差) 可表示为： ( 见) = m - 宅t ( l ( d ，x ，) ，咒) “e 域) 3 - ( 2 ) 算法在皿上的实际风险( 实际错误率或实际偏差) 为： 置( 域) = i “d l ，x ，) ，乃川融，奶) 3 一( 3 ) 并 其中，佤，* ) 是( x ，乃) 的概率分布函数。对于分类问题y = 0 , i ) ，对于拟台问题 y r 。 人们通常认为随着训练样本数的增加，算法的经验风险不断地接近于它的实际 风险，即： 8 。( 见) 哼置( 见) 刀啼c o 3 - ( 4 ) 但是这根本没有可靠的理论依据，只是直观上合理的想当然做法。我们希望找到3 - ( 4 ) 成立的条件。这样随着训练样本数的不断增加，我们可以不断地逼近算法的实际性 能。然而，仅仅使式3 删成立并不具有多大的实际意义，因为在实际问题中训练样 本数总是有限的，此时算法的经验风险与实际风险问的差剔仍然无法衡量。在这种 情况下，盲目地追求经验风险最小化，即尽可能地降低同一算法在特定训练样本集 合上的经验风险，或者选择该训练样本集合上经验风险小的算法是危险的。比如， 在早期神经网络研究中，人们总是把注意力集中在如何使更小，但很快便发现， 一味追求训练误差小并不是总能达到好的预测效果。某些情况下，当训练误差过小 反而会导致推广能力的下降，这就是几乎所有神经网络研究者都曾遇到的所谓过学 习c 0 v 玎m 陆g ) 问题从理论上看，模式识别中也存在同样的问题，但因为通常使用 的分类器模型都是相对比较简单( 比如线性分类器) ，因此过学习问题并不像神经网 络中那样突出。尽管如此。经验风险最小化作为解决模式识别等机器学习问题基本 1 2 第三章支持向量机( s v m ) 的思想仍统治了这一领域的几乎所有研究，人们多年来一直将大部分注意力集中到 如何更好地求取最小经验风险上。与此相反，统计学习理论则对用经验风险最小化 原则解决期望风险最小化问题的前提是什么? 当这些前提不成立时经验风险最小化 方法的性能如何? 以及是否可以找到更合理的原则等基本问题进行了深人的研究。事 实上，关于学习机器复杂性和推广能力，有以下的结论 ( 1 ) 经验风险最小并不一定意味着期望风险最小； 国学习机器的复杂性不但与所研究的系统有关而且要和有限的学习样本相适 应。 3 1 1 2 统计学习理论的核心内容 依据算法的经验风险以及算法本身的构造推测它的实际风险是我们评估算法 泛化能力的可行方法，统计学习理论就是以此目的建立的。它的基本体系早在2 0 世纪7 0 年代就已建立。然而，由于它的研究结果大部分只表现出理论研究价值， 所以在很长时间里没有象人工智能以及人工神经网络那样受到广泛关注。直到2 0 世纪9 0 年代v a p n i k 根据这一理论发明了支持向量机并用它成功地解决了一些实际 阀题( 例如：手写邮政编码的识别) 才使得这一理论更多地被人了解。 统计学习理论将算法的训练过程看作算法向训练样本学习的过程。围绕这一过 程该理论分成从理论向实践渐进的四个部分： ( 1 ) 学习过程一致性的理论。一个基于经验风险最小化原则的学习过程满足怎样的 条件，它的经验风险与实际风险趋向一致。 国学习过程收敛速度的理论。如果学习过程的经验风险与实际风险趋向一致，那 么它们之间的接近速度随着训练样本数的增加是如何变化的。哪些因素控制着它们 接近的速度。 ( 3 ) 控制学习过程泛化能力的理论。采用前两部分的结论改进学习过程。 ( 4 ) 构造学习算法的理论。采用前三部分的结论，在分类和拟合问题中构造现实的 学习算法。 统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它 从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险 与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。 3 1 1 3v c 维 假设函数集合的v c 维是这一理论中一个重要的概念。它出现在该理论几乎所 有的结论中。 定义；对于分类算法，其假设函数集合h 的v c 维是指能够被h “打散”的样 本集合可能具有的最大样本数( 或称作样本集合的最大基数) ，记作v c - d i m ( n ) 。 1 3 青岛大学硬士学位论文 样本集合 而，屯，v o o p ) 被h “打散”是指对该集合中的样本任意赋予类别标记0 或l 使之成为 ( 而，1 ) ，如，o ) ，