（模式识别与智能系统专业论文）基于支持向量机的图像分割与边缘检测.pdf

l u li i ii l lli ii lr li ii ii 17 5 4 7 6 7 南京邮电大学 硕士学位论文摘要 学科、专业：工学模式识别与智能系统 研究方向：智能信息处理 作者：盟级研究生韭建民 指导教师：李雷 题目：基于支持向量机的图像分割与边缘检测 英文题目：i m a g es e g m e n t a t i o na n de d g ed e t e c t i o nb a s e do nt h e s u p p o r tv e c t o rm a c h i n e 主题词：图像分割，确定聚类，边缘检测，支持向量机 k e y w o r d s ：i m a g es e g m e n t a t i o n ，c l u s t e r i n g ，e d g ed e t e c t i o n ，s u p p o r tv e c t o r m a c h i n e r l i 南京邮电大学硕士研究生学位论文摘要 摘要 图像图形是人类相互交流和认识客观世界的主要媒体。科学研究表明，视觉系统帮助 人类从外界获得7 5 以上的信息。而图像图形带给我们的正是视觉世界中的所有信息。因 此，图像图形技术的应用必然涉及到人类生活和社会发展的各个方面。 图像分割是一种重要的图像分析技术，是从图像处理进行到图像分析的关键步骤，也 是进一步图像理解的基础。在图像分割前，对图像的加工主要处于图像处理的层次，图像 分割后图像的分析才成为可能。边缘检测是图像分割的一种算法，在图像识别、图像分割 以及图像压缩等领域都有较为广泛的应用，它还经常被应用到计算机视觉和模式识别等较 高层次的图像处理中。 本文围绕图像分割及边缘检测算法而展开，本文的创新工作主要有以下两点： 1 首先利用系统聚类的思想，提出了一种新的基于确定聚类的s v m 分割算法，提高 了分割的性能，并与传统的基于阈值的分割算法进行了比较。 2 在边缘检测时，本文提出一种新的基于聚类的特征选取方法，用来选取支持向量 机的训练向量，从而改善了支持向量机的训练方法，缩短了训练时间，取得了较好的边缘 检测效果，同时与经典的边缘检测算子做了比较。 关键词：图像分割，确定聚类，边缘检测，支持向量机 b r o u g h tt ou sa l lt h ei n f o r m a t i o ni nt h ev i s u a lw o r l d s ot h ea p p l i c a t i o no fi m a g ep r o c e s s i n g i n e v i t a b l yi n v o l v e di ne v e r ya s p e c to fh u m a nl i f ea n d w o r k t h ei m a g es e g m e n t a t i o ni sa l li m p o r t a n ti m a g ea n a l y s i st e c h n o l o g y , w h i c hi sak e ys t e pi n t h ep r o c e s sf r o mt h ei m a g ep r o c e s s i n gt oi m a g ea n a l y s i s b e f o r et h es e g m e n t a t i o n , a l lt h e p r o c e s s i n g i s m a i n l yi n t h el e v e l o fi m a g ep r o c e s s i n g a f t e rs e g m e n t a t i o n , i m a g ea n a l y s i s b e c o m e sp o s s i b l e e d g ed e t e c t i o ni sa na l g o r i t h mf o ri m a g es e g m e n t a t i o n i ti sw i d e l yu s e di n m a n yf i e l d ss u c ha si m a g er e c o g n i t i o n ，i m a g es e g m e n t a t i o na n di m a g ec o m p r e s s i o na n d s oo n i t i sa l s of r e q u e n t l ya p p l i e di nt h eh i g h e rl e v e lp r o c e s so fi m a g e ，f o re x a m p l e ，c o m p u t e rv i s i o na n d p a r e r nr e c o g n i t i o n t h i sp a p e rd e a l sw i t ht h ei m a g es e g m e n t a t i o na n de d g ed e t e c t i o n f i r s tu s et h ei d e ao f s y s t e mc l u s t e r i n g ，a n dp r o p o s ean e ws e g m e n t a t i o na l g o r i t h mb a s e do nt h es y s t e mc l u s t e r i n g s v m i nt h ee n d ，c o m p a r ei tw i t ht h et r a d i t i o n a lt h r e s h o l d - b a s e da l g o r i t h m d u r i n gt h ee d g e d e t e c t i o n , an e wf e a t u r es e l e c t i o na p p r o a c hb a s e do nt h ec l u s t e r i n gi sp r o p o s e d i ti su s e dt o s e l e c tt h et r a i n i n gv e c t o r t h u st h a ti m p r o v e st h et r a i n i n gp r o c e s s ，s h o r t e nt h et r a i n i n gt i m ea n d a c h i e v eg o o dr e s u l t si nt h ee d g ed e t e c t i o n a tl a s tt h e r ei sac o n t r a s tb e t w e e nt h ec l a s s i ce d g e d e t e c t o ra n dt h em e t h o di nt h i sp a p e r k e y w o r d s ：i m a g es e g m e n t a t i o n ，c l u s t e r i n g ，e d g ed e t e c t i o n ，s u p p o r tv e c t o rm a c h i n e i i 、 南京邮电大学硕士研究生学位论文 目录 目录 摘要i a b s t r a c l ：i i 目录i i i 第一章绪论1 1 1 研究背景1 1 2 研究现状2 1 2 1 图像分割的研究现状2 1 2 2 边缘检测的研究现状3 1 2 3 支持向量机的研究现状4 1 3 本文的内容安排5 第二章机器学习与统计理论6 2 1 引言6 2 2 机器学习的基本方法7 2 2 1 学习问题的一般表示7 2 2 2 经验风险最小化原则7 2 3 统计学习理论的基本思想8 2 3 1 学习过程一致性条件9 2 3 2 函数集的v c 维9 2 3 3 泛化误差的边界9 2 3 4 结构风险最小化原理1 0 第三章支持向量机理论1 2 3 1 引言1 2 3 2 支持向量机分类1 2 3 2 1 线性情况1 3 3 2 2 非线性情况1 6 3 3 支持向量机回归1 7 l 南京邮电大学硕士研究生学位论文 目录 3 3 1 线性回归1 7 3 3 2 损失函数1 9 3 3 3 非线性回归2 0 第四章图像的分割处理2 l 4 1 引言2 l 4 2 经典图像分割方法i 2 1 4 2 1 基于区域生成的分割方法2 1 4 2 2 特征空间聚类2 3 4 3 基于确定聚类s v m 的图像分割2 6 4 3 1 确定聚类s v m 算法：2 6 4 3 2 图像的特征提取：2 6 4 3 3s 模型选择：j 2 7 4 3 4 结果及分析：2 7 第五章图像边缘检测2 9 5 1 引言2 9 5 2 基本的边缘检测方法2 9 5 2 1 基于微分的边缘检测方法2 9 5 2 2l o g 算子( m a r r h i l d r e t h 算子) 3 2 5 2 3c a n n y 边缘检测算法3 3 5 2 4 曲面拟合法3 6 5 3 基于支持向量机的边缘检测3 7 5 3 1 算法思想3 7 5 3 2 算法过程3 7 5 3 2 样本特征提取3 7 5 3 3 支持向量机的训练及检测方法：3 8 5 4 实验结果及分析3 9 第六章总结与展望4 1 6 1 全文总结4 1 6 2 展望4 1 南京邮电大学硕士研究生学位论文目录 致谢4 2 参考文献4 3 攻读学位期间发表的论文4 7 v 数字电子技术的迅猛发展为数字图像处理提供了先进的技术手段，基于计算机的图像 处理学也就成为研究图像信息的- - i - j 崭新学科。近年来，数字图像处理技术得到更大的重 视和长足的发展，出现了许多相关的新理论和新设备，并已在科学研究、工业生产、医疗 卫生、教育、娱乐、管理和通信等方面得到了广泛的应用，并发挥着重要的作用。 图像处理所包含的内容非常丰富，包括图像的采集、编码、存储和传输，图像的变换、 增强、恢复和重建，图像的分割，特征的提取和测量，序列图像的校正，图像数据库的建 立、索引、查询和抽取，图像模型的建立，图像知识的利用和匹配，图像和场景的解释和 理解，以及基于它们的推理、判断、决策和行为规则等。根据抽象程度的不同，图像处理 可分为三个层次：狭义图像处理、图像分析和图像理解。如图1 1 所示，图像处理学是既相 互联系又相互区别的狭义图像处理、图像分析和图像理解三者的有机结合。狭义图像处理 侧重研究图像之间的变换，主要指对图像进行各种操作以改善图像的视觉效果，或对图像 进行压缩编码以减少所需的存储空间或传输时间、传输通路的要求，实质上是一个从图像 到图像的处理过程。图像分析主要是对图像中感兴趣的目标进行检测和测量，从而建立对 图像的描述，是一个从图像到数值或符号的处理过程。图像理解则是在图像分析的基础上， 进一步研究图像各目标的性质和它们之间的相互联系，并得出对图像内容的理解以及对原 来客观场景的解释，从而指导和规划行动。图像分析主要以观察者为中心研究客观世界， 图像理解是以客观世界为中心，借助知识和经验等来把握整个客观世界。 南京邮电大学硕士研究生学位论文第一章绪论 抽 象 程 度 高 语 义 低 高层 中层 低层 小 大 数 据 量 图1 1 图像处理三层次示意图 狭义图像处理、图像分析和图像理解是处在三个抽象程度和数据量各有特点的不同层 次上。狭义图像处理是比较低级的操作，主要在图像像素级上进行处理；图像分析则进入 了中层，经分割和特征提取，把原来以像素构成的图像转变成比较简洁的非图像形式的描 述；图像理解是高层操作，是从描述中抽象出来符号来进行运算，其处理过程和方法与人 类的思维推理有许多类似之处。 图像处理技术是随着计算机技术的发展而开拓出来的一个新的计算机应用领域，涉及 的领域包括数学，物理学，生物学以及生理学等基础学科，又在电子技术，计算机科学， 信息理论，医学，控制理论以及系统工程等应用学科新成就的促进下迅速发展。目前图像 处理仍然是一门年轻的，充满活力的交叉学科，并随着计算机技术，认知科学，神经网络 技术以及数学理论的新成果。如数学形态学，小波分析，分形理论的发展，以及其他相关 领域的最新成就而飞速发展着。 1 2 研究现状 1 2 1 图像分割的研究现状 图像分割是一种重要的图像分析技术。在图像的研究和应用中，人们往往仅对图像中 的某些部分感兴趣。这些部分常被称为目标或背景( 其它部分称为背景) ，它们一般对应 图像中特定的，具有独特性质的区域【3 1 。为了辨识和分析图像中的目标，需要将它们从图 2 操作对象 号 标 素 符 目 像 南京邮电大学硕士研究生学位论文 第一章绪论 像中分离提取出来，在此基础之上才有可能对目标进行测量和对图像进行利用。图像分割 就是指把图像分成各具特性的区域并提取出感兴趣的目标的技术和过程。 图像分割算法研究多年来一直受人们的高度重视，当人观察景物时，在视觉系统中对 景物进行分割的过程是必不可少的。这个过程非常有效，以至于人所看到的并不是一个复 杂的景物，而只不过一种物体的集合体。但是，使用数字处理，必须设法分离图像中的物 体，把图像分裂成像素集合，每个集合代表一个的物体的图像。尽管数字图像分割的任务 在人类视觉感受中很难找到对照，但在数字图像分析中它却不是一个轻而易举的任务。至 今已提出了许多种方法，从分割操作策略上讲，可以分为基于区域生成的分割方法，基于 边界检测的分割方法和区域生成与边界检测的混合方法。所谓基于区域的生成方法，就是 直接找出特征相近的像点，从而生成区域；基于边界检测的方法是，首先检测出图像特征 不一致性所在点，并将它们连成边界，这些边界就将图像分成许多区域；第三类方法是根 据特征同一性准则，特征相近的像点形成区域，不一致之处的点连成边界。从方法上讲， 可以直接根据灰度大小进行分割，也可以根据灰度分布进行分割，还可以根据图像模型进 行分割。虽然有许多分割方法，但至今没有找到对任何图像都特别有效的图像分割算法， 就是说任何一种分割算法都有它的局限性和针对性。因此，要使图像分割效果好，应充分 利用对象知识，所采用的分割方法应和对象特点相“匹配”。实践表明，一个提高图像分割 效果的途径是将一些分割算法组合起来形成一个系统，根据图像的特点，分层次有针对性 地使用不同的分割算法。 1 2 2 边缘检测的研究现状 边缘是图像最基本的特征，边缘检测在计算机视觉、图像分析等应用中起着重要的作 用，是图像分析与识别的重要环节，这是因为图像的边缘包含了用于识别的有用信息，所 以边缘检测是图像分析和模式识别的主要特征提取手段。 所谓边缘是指其周围像素灰度发生阶跃变化或屋顶状变化的那些像素的集合，它存在 于目标与背景、目标与目标、区域与区域，基元与基元之间。因此它是图像分割所依赖的 重要的特征，也是纹理特征的重要信息源和形状特征的基础；而图像的纹理形状特征的提取 又常常依赖于图象分割。图像的边缘提取也是图像匹配的基础，因为它是位置的标志，对 灰度的变化不敏感，它可作为匹配的特征点。图像的其他特征都是由边缘和区域这些基本 特征推导出来的。 图像的大部分主要信息都存在于图像的边缘中，主要表现为图像局部特征的不连续 南京邮电大学硕士研究生学位论文第一章绪论 性，是图像中灰度变化比较剧烈的地方，也即我们通常所说的信号发生奇异变化的地方。 奇异信号沿边缘走向的灰度变化剧烈，通常我们将边缘划分为阶跃状和屋顶状两种类型。 阶跃边缘中两边的灰度值有明显的变化；而屋顶状边缘位于灰度增加与减少的交界处。在 数学上可利用灰度的导数来刻画边缘点的变化，对阶跃边缘、屋顶状边缘分别求其一阶、 二阶导数。 对于阶跃性边缘，二阶方向导数在边缘处呈零交叉；对于屋顶状边缘，二阶方向导数 在边缘处取极值。边缘反应了局部区域内特征的差别，它表示为图像信息的某种不连续( 如 灰度突变，纹理以及彩色的变化) 。著名的“马赫带效应”指出：人的视觉对物体光度变化的 部分有特殊的增强效应，即在不同光强度区的边缘周围引起“过量调整”。物体边缘特征是 与图像中灰度发生跳变的部分相对应的。因此，基于灰度不连续性特征检测的方法成为图 像边缘提取的主要方法之一。在众多视觉模块计算中，通常把边缘检测作为视觉计算的第 一步，高层次计算机视觉处理能否成功极大地依赖于边缘检测算了的优越性能。 由于边缘是图像的最基本特征，它有能勾画出区域的形状、能被局部定义以及能传递 大部分图像信息等诸多优点，所以边缘信息的提取无论是对人类还是对机器视觉来说都是 一个最重要而经典的课题。边缘检测的定义有很多种，其中最常用的一种定义为：边缘检 测是根据引起图像灰度变化的物理过程来描述图像中灰度变化的过程。 长期以来，人们一直在研究各种能较好实现边缘检测的方法t d - a l 。但由于以下原因：图 像本身的复杂性；有效边缘与噪声均为高频信号，容易混淆：光照阴影及物体表面纹理等 因素在图像中均表现为边缘：对于不同的使用者来说所关心的边缘信息各不相同等因素的 影响，使得边缘提取迄今为止仍然是一个难题。 1 2 3 支持向量机的研究现状 支持向量机是统计学家v a p n i k 根据统计学习理论提出的一种新的学习方法，近年来受 到国际学术界的重视，得到了广泛的应用。支持向量机理论的最大特点是根据结构风险最 小化准则，有效地避免了学习方法中的过学习，维数灾难，局部极小等传统分类中存在的 问题，在小样本条件下仍然具有良好的泛化能力，现已成为训练多层感知器，r b f 神经网 络和多项式神经网络的替代性方法，因此受到了广泛关注。 支持向量机的基本思想是基于m e r c e r 核展开定理，可以通过非线性映射，把样本空间 映射到一个高维乃至无穷维的特征空间，使在特征空间中可以应用线性学习机的方法解决 样本空间中的高度非线性分类和回归问题。支持向量机方法巧妙的解决了这两个难题；由 4 南京邮电大学硕士研究生学位论文 第一苹绪论 于应用了核函数的展开定理，所以根本不需要知道非线性映射的显示表达式：由于在高维 特征空间中应用线性学习机的方法，所以与线性模型相比几乎不增加计算的复杂性，这在 某种程度上避免了“维数灾难”。 从优化目标函数可以看到，s v m 方法的复杂度与特征维数无关，但受训练样本集规模 以的制约。当样本点数目很大时，存储该核函数矩阵需要大量的内存。同时，s v m 在二次 型寻优过程中要进行大量的矩阵运算，使得算法收敛速度慢。因此，s v m 训练需要从提高 训练算法收敛速度以及如何处理大规模样本集的训练问题等两方面进行改进，目前已经提 出了许多解决方法和改进算法。 1 3 本文的内容安排 本文的主要研究内容是图像的分割和边缘检测，首先阐述了课题的研究背景、意义以 及该研究领域的发展现状，介绍了一些具有代表意义的经典的图像分割和边缘检测方法， 并且对这些经典方法的检测结果进行了相关的分析比较。接下来本文着重介绍了基于支持 向量机的图像分割和边缘检测方法，并进行仿真实验，取得了良好的效果。 整篇文章的具体内容做如下安排： 第一章，阐述了课题的研究背景和发展现状。 第二章，介绍了机器学习的基本方法和统计学习的基本思想，以及学习过程中的经验 风险和结构风险模型。 第三章，介绍了支持向量机的基本理论，支持向量分类和支持向量回归两种情况。 第四章，首先介绍了图像分割算法中经典的基于区域生成的并行区域分割技术以及 特征聚类方法，同时在此基础上提出了一种新的基于确定聚类支持向量的图 像分割方法，进行了仿真实验，并与传统阈值分割方法进行了比较。 第五章，对图像分割中的基于边界的分割算法进行了介绍，重点介绍了并行边界分割 技术即图像的边缘检测，并对那些经典的检测算法进行了分析比较，最后提 出了一种新的基于支持向量机的边缘检测算法，该算法采用了特征聚类的思 想来提取训练向量，改进了支持向量机的训练过程，缩短了训练时间，并取 得了良好的效果。最后，与经典的边缘检测算子进行了比较。 第六章，对全文进行了总结和展望。 5 南京邮电大学硕士研究生学位论文 第二章机器学习与统计理论 第二章机器学习与统计理论 本章首先描述了支持向量机背后的基本思想，介绍了机器学习的基本方法及其存在的 缺点，从而引出统计学习理论的基本思想，在此基础之上，讨论了简单的线性情况下的最 优超平面的构造，然后进一步将其推广到非线性情况。其次，介绍了支持向量机的线性和 非线性回归理论，最后对基于不同核函数的支持向量机方法与相对应的神经网络方法进行 了比较。 2 1 引言 人的智慧中一个很重要的方面是从实例中学习知识的能力，即通过对已知事实的分析 总结出规律，预测无法直接观测的事实。在这种学习中，重要的是举一反三的能力，即利 用学习得到的规律，不但可以较好地解释已知事实，而且能够对未来或无法观测的现象做 出正确的预测和判断，这叫做推广能力。在机器智能的研究中，希望用机器来模拟人的这 种能力，这就是机器学习理论的出发点。机器学习的目的是，设计某种方法，通过对已知 数据的学习，找到数据内在的相互依赖关系，从而对未知数据进行预测或对其性能进行判 断。传统的学习理论主要是基于经验风险最小化原则( e m ) 的。所谓经验风险，是指在 训练集上的风险，通常用平均平方误差表示。理论表明，当训练数据趋于无穷多时，经验 风险收敛于实际风险。因此经验风险最小化原则隐含地使用了训练样本无穷多的假设条 件。但是在现实问题中，可用的训练样本数目总是有限的。虽然人们知道这一点，但传统 上仍然基于经验风险最小化原则来推导各种算法。在实际应用中，这些算法遇到了很多困 难，如小样本问题，高维问题，学习机器结构问题和局部极值问题等。 统计学习理论从控制学习机器复杂度的思想出发，提出了结构风险最小化原则。该原 则使得学习机器在可容许的经验风险范围内，总是采用具有最低复杂度的函数集。支持向 量机是在统计学习理论基础上发展出的一种性能优良的学习机器。其基本的思想是，在线 性情况下，在原空间寻找两类样本的最优分类超平面，而在非线性情况下，首先将原始模 式空间映射到高维的特征空间，并在该特征空间中寻找最优分类超平面。支持向量机利用 一些具有特殊性质的核函数，将特征空间中的内积运算转化为低维空间中的非线性运算， 从而巧妙地避免了高维空间中的计算问题。 6 南京邮电大学硕士研究生学位论文 第二章机器学习与统计理论 2 2 机器学习的基本方法 2 2 1 学习问题的一般表示 机器学习的基本模型如图2 1 所示，其中，系统( s ) 是我们研究的对象，它在给定一 定输入x 下得到一定的输出y ，l m 为所求的学习机器，输出为y 。机器学习的目的是根据 给定的训练样本求出系统输入输出之间依赖关系的估计，使它能够对未知样本的输出做出 尽可能准确的预测。 图2 1 机器学习问题的基本模型 输出y 学习问题可以一般的表示为变：ly 与工之间存在未知依赖关系，即遵循某一未知联合概率 密度r ( x ，y ) 。机器学习问题就是根据玎个独立同分布观测样本 ( x a ，m ) ，( 而，儿) ，( 毛，以) ( 2 1 ) 在一组函数 厂( x ，w ) ) 中，求一个最优的函数f c x ，w o ) ，对依赖关系进行估计，使期望风险 尺( w ) = i 三( ) ，f c x ，w ) ) d f ( x ，y ) ( 2 - 2 ) 最小。其中， 厂( 毛叻) 称作预测函数集，w q ，为函数的广义参数。 f ( x ， 可以表示 任何函数集。l ( y ，f ( x ，w ) ) 表示由于用f ( x ，w ) 对y 进行而造成的损失，称为损失函数。 因此，机器学习问题也可以表示为。从一组独立同分布的观测样本出发，过最小化风 险泛函r ( w ) ，确定学习机器的广义参数w 的过程。 2 2 2 经验风险最小化原则 学习的目的就是为了使式( 2 2 ) 所示的期望风险最小化。为达此目的，必须依赖于联 合概率f ( x ，力。但在实际的机器学习问题中，这一条件是未知的，只能利用已知训练样本 7 南京邮电大学硕士研究生学位论文第二章机器学习与统计理论 ( 2 一1 ) 的信息，因此期望风险无法直接计算和进行最小化。 为此，一般根据概率论中的大数定理，即采用算术平均来代替式( 2 2 ) 中的数学期望， 于是定义 ( w ) = 去三( 乃，厂( 而，川) ( 2 3 ) ，i l = l 来逼近期望风险，称之为经验风险。所谓的经验风险最小化原则( e m p i r i c a l 硒s k m i n i m i z a t i o n , e r m ) ，就是指用对参数w 求经验风险( w ) 的最小值代替求期望风险r ( 叻 的最小值。经验风险最小化原则是目前绝大多数模式识别方法的基础。 事实上，从期望风险最小化到经验风险最小化并没有可靠的理论依据，只是人们直观 上认为合理的做法。首先，概率论中的大数定理只说明了( 在一定的条件下) 当样本趋于 无穷多时( w ) 将在概率意义上趋于r ( 川，并没有保证使( 最小的与使r ( w ) 最 j x 的w * 是同一个点，更不能保证( w ) 能够趋于r ( 矿) 。而且，即使我们有办法使这些 条件在样本数无穷大时得到保证，我们也无法认定在这些前提下得到的经验风险最小化方 法再样本数有限时仍能得到好的结果。 2 3 统计学习理论的基本思想 任何学习机器都可以看成是一组函数集合，机器学习问题就是从函数集合中选择合适 的逼近函数并参数化的过程。所谓学习机器的容量也就是它所对应的函数集的容量，或者 叫复杂度。容量或复杂度代表了函数集实现从输入到输出的映射的能力，对学习机器来说， 叫做学习能力。容量越大，机器的学习能力就越强。在模式识别问题中，学习能力强的机 器能够得到更加复杂的分类面，然而，越复杂的分类面，就越依赖于训练数据分布的细节， 这种对训练数据的过于细致的依赖，往往会导致学习机器的泛化能力不强。统计学习理论 用v c 维来描述学习机器的容量，并从控制学习机器容量的思想出发，结合经验风险和训 练样本数目，导出了期望风险在不同情况下的一组风险上界1 4 3 - s 4 1 。这些界具有如下特点： 1 、这些界是通用的，与具体数据的分布无关； 2 、在小样本情况下同样成立： 在实际的训练过程中，可以通过最小化风险上界，实现对学习机器的优化， 因此所得到的学习机器的复杂度受到很好地控制，即使在小样本情况下也同样具有比 较高的泛化。 8 南京邮电大学硕士研究生学位论文第二章机器学习与统计理论 2 3 1 学习过程一致性条件 学习过程的一致性是指当训练样本数趋于无穷大时，经验风险的最优值能够收敛到真 实风险的最优值。只有满足一致性条最小化原则下得到的最优结果当样本数无穷大时趋近 于使期望风险最小化的最优结果。对于有界的损失函数，经验风险最小化学习一致的充分 必要条件是经验风险在如下意义上一致地收敛于期望风险：件，才能保证在经验风险 l i i 粤尸is u p ( r ( w ) 一8 唧( 叻) 一gl=0(24) 其中，s 0 ，p 表示概率。 式( 2 4 ) 将学习一致性问题转化为一致收敛问题。显然，我们感兴趣的是学习方法，即 预测函数集是否能满足一致性的条件。虽然式( 2 4 ) 给出了经验风险最小化原则成立的充分 必要条件，但它并没有给出什么样的学习方法能够满足这一条件。为此，统计学习理论定 义了一些指标来衡量函数集的性能，其中最重要的是v c 维。 2 3 2 函数集的v c 维 为了描述函数集的容量，v a p n i k 和c h e r v o n e n l d s 提出了v c 维概念【5 2 】。模式识别方法 中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本的样本集能够被函数集中 的函数按所有可能的2 6 种形式分为两类，则称函数集能够把样本数为h 的样本集打散 ( s h a t t e r i n g ) 。函数集的v c 维就是它能打散的最大样本数目h 。若一个函数集能将任意数目 的样本集打散，则该函数集的v c 维为无穷大。 v c 维反映了函数集的学习能力，v c 维越大，则学习机器越复杂( 容量越大) ，学习能 力就越强。v c 维是统计学习理论中的一个核心概念，它是目前为止对函数集学习性能的 最好描述指标。但遗憾的是，目前尚没有通用的关于任意函数集v c 维计算的理论，只确 定了一些特殊的函数集的v c 维。如在n 维实数空间中，线性分类器和线性实函数的v c 维是n + 1 ，而对一些比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集选择有关外， 还受学习算法等的影响，因此其确定将更加困难。但是，在实际应用统计学习理论中，可 以通过变通的办法巧妙地避开直接求v c 维的问题。 2 3 3 泛化误差的边界 统计学习理论从v c 维的概念出发，推导出了关于经验风险和实际风险之间关系的重 要结论，称作泛化误差的边界。这些界是分析学习机器性能和发展新的学习算法的重要基 9 南京邮电大学硕士研究生学位论文第二章机器学习与统计理论 础。统计学 - - - j 理论中给出了如下的估计真实风险的不等式，对于任意a f ( f 是抽象参数 集合) ，以至少l 一刁的概率满足以下不等式【5 0 l ， 脚，c 们+ 甲( 尝) 泣5 ， 鼽甲( 鲁) = ( 2 6 ) ( 忉表示经验风险；甲( 尝) 称为置信风险；n 是样本个数：参数h 称为一个函数集 合的v c 维。当h r 较大时，置信风险较大，此时用经验风险近似期望风险就会出现较大 的误差。如果样本数较多，使得h 较小，则置信风险就会较小，经验风险最小化的最优 解就会接近真正的最优解。 对于一个特定的学习问题，当样本数固定时，如果学习机器的v c 维越高( 复杂度越 高) ，则置信风险越大，导致真实风险与经验风险之间可能的差就越大。因此，在设计分 类器时，不但要使经验风险尽可能小，而且要控制其v c 维也尽可能小，从而缩小置信风 险，使期望风险最小。 2 3 4 结构风险最小化原理 “结构风险最小化原理”的基本想法是：如果我们要求风险最小，就需要使得不等式中 两项相互权衡，共同趋于极小；另外，在获得的学习模型经验风险最小的同时，希望学习 模型的泛化能力尽可能大，这样就需要h 值尽可能小，即置信风险最小。 由于有式( 2 5 ) 的理论依据，统计学 - - - j 理论提供了一种在小样本情况下，使( 叻极 小化的同时，控制v c 维( 模型复杂性) 的方法，即对于给定的有限样本，选择最佳模型 复杂性的方法，该方法描述如下： 首先把函数集s = f ( x ，w ) ，w q 分解为一个函数子集序列，使其具有一种嵌套结构 墨c 最c c 最c c s( 2 7 ) 其中& = f ( x ，w ) ，w eq ) 为函数集的子集( 元素) ，其v c 维数吃为有限。在此结构中， 嵌套子集按其复杂性( 即v c 维数大小) 的顺序排列： 1 0 南京邮电大学硕士研究生学位论文第二章机器学习与统计理论 a s s 魂 ( 2 8 ) 这样，在同一个子集中，置信范围是相同的。在每个子集中寻找最小经验风险，通常 它随着子集复杂度的增加而减小。选择最小经验风险与置信范围之和最小的子集，就可以 达到期望风险的最小，这个子集中使经验风险最小的函数就是要求的最优函数。这种思想 称作结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o n ，简称s r m ) 。 图2 1 给出了结构风险最小化的示意图 风险 根据这一分析，我们得到两种运用结构风险最小化原理构造的学习机器的思想： ( 1 ) 给定一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在每个子集 中求取最小经验风险，然后选择经验风险与置信风险之和最小的子集。当子集数目较大时， 此方法较费时，甚至不可行。 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的经验风 险( 例如，使得训练误差为0 ) 。然后，在这些子集中选择适当的子集使置信风险最小，则 相应的函数子集中使得经验风险最小的函数就是所求解的最优函数。 可见，利用结构风险最小化原理的思想，就可以完美解决传统机器学习中的过学习问 题。支持向量机通过最大化分类边界以最小化v c 维，也即在保证经验风险最小的基础上 最小化置信风险，从而达到最小化结构风险的目的，因此支持向量机方法实际上就是结构 风险最小化思想的具体实现。 南京邮电大学硕士研究生学位论文 第三章支持向量机理论 3 1 引言 第三章支持向量机理论 给予数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻 找规律，利用这些规律对未来数据或无法观测的数据进行预测。包括模式识别、神经网络 等在内，现有机器学习方法共同的重要理论基础之一是统计学。传统统计学研究是样本数 目区域无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数 往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意【4 9 】。 与传统统计学相比，统计学习理论( s l t ：s t a t i s t i c a ll e a r n i n gt h e o r y ) 是一种专门研究 小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新理论体系， 在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的 条件下得到最优结果。v a p n i k 等人从二十世纪六、七十年代开始致力于此方面研究，到二 十世纪九十年代中期，随着其它理论的不断发展和成熟，也由于神经网络等学习方法在理 论上缺乏实质性进展，统计学习理论开始受到越来越广发的重视。 支持向量机( s v m ：s u p p o r tv e c t o rm a c h i n e ) 是统计学习理论中最年轻的内容，也是 最实用的部分。其核心内容是在1 9 9 2 年到1 9 9 5 年间提出的 5 3 - 5 5 】，目前仍处在不断发展阶 段。其方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础上的，根据有限 的样本信息模型的复杂性( 即对特定训练样本的学习精度，a c c u r a c y ) 和学习能力( 即无 错误地识别任意样本的能力) 之间寻求最佳折衷，以期获得最好的推广能力( g e n e r a l i z a t i o n a b i l i t y ) 。 支持向量机分类算法具有4 个显著特点：( 1 ) 利用大间隔的思想降低分类器的v c 维， 实现结构风险最小化原则，控制分类器的推广能力；( 2 ) 利用m e r c e r 核实现先行算法的非 法线性化；( 3 ) 稀疏性，即少量样本( 支持向量) 的系数不为零，就推广性而言，较少的 支持向量数在统计意义上对应好的推广能力，从计算角度看，支持向量减少了核形式判别 式的计算量；( 4 ) 算法设计成凸二次规划问题，避免了多解性1 5 刚。 3 2 支持向量机分类 假定大小为，的训练样本集 ( 焉，儿) ，i = 1 ，2 ，) ，由二类别组成，如果薯r ”属于第1 1 2 南京邮电大学硕士研究生学位论文第三章支持向量机理论 类，则标记为正咒= l ，如果属于第2 类，则标记为负( 只= - 1 ) 。学习的目的是构造一个决 策函数，将测试数据尽可能正确地分类。针对训练样本集为线性或非线性两种情