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

南京邮电大学硕士研究生孚位论文 一 摘要 摘要 图像作为一种有效的信息载体，是人类获取和交换信息的主要来源。人类感 知的外界信息8 0 以上是通过视觉得到的。因此，图像处理的应用领域必然涉及 到人类生活和工作的方方面面。 图像增强是对图像的低层次处理，处于图像处理的预处理阶段。它是图像处 理的一个重要环节，在整个图像处理过程中起着承前启后的重要作用，对图像高 层次处理的成败至关重要。边缘检测在图像识别、图像分割以及图像压缩等领域 都有较为广泛的应用，它还经常被应用到计算机视觉和模式识别等较高层次的图 像处理中。 本文围绕图像增强和边缘检测而展开。利用支持向量回归特性把图像和支持 向量机联系起来，形成s v r 图像。在s v r 域下把传统的图像增强方法应用到s v r 图像中取得了较好的效果。本文改进了用于边缘检测的支持向量机的训练方法， 缩短了训练时间，边缘检测效果良好。并对不同信噪比环境下，选用不同的核函 数对边缘检测性能的影响进行了比较。 关键词：图像增强，边缘检测，支持向量机，c a n n y 算子 南京邮电大学硕士研究生学位论文a b s t r a c t a b s t r a c t a so n ee f f e c t i v ei n f o r m a t i o nm e d i a ，i m a g ei st h em a i ns o u r c et h a tp e o p l eg e ta n d e x c h a n g ei n f o r m a t i o n 8 0 o ft h eo u t s i d ei n f o r m a t i o np e o p l ep e r c e i v ei sg o t t e n v i s u a l l y 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 gi 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 f h u m a nl i f ea n dw o r k t h ei m a g ee n h a n c e m e n ti st h el o wl e v e lp r o c e s s i n go fi m a g e ，w h i c hi sa tt h e p r e - p r o c e s s i n gs t a g e i ti sa ni m p o r t a n tp a r to fi m a g ep r o c e s s i n g ，a n di tp l a y sac r u c i a l a n dt r a n s i t i o n a lr o l ed u r i n gt h ew h o l ep r o c e s s ，a n di td e t e r m i n e st h er e s u l t so ft h e h i g h e rl e v e lp r o c e s s i n g e d g ed e t e c t i o ni sw i d e l yu s e di nm a n yf i e l d ss u c ha si m a g e r 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 ds oo n ，i ti sa l s o f 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 n a n dm o d e lr e c o g n i t i o n t h i sp a p e rd e a l sw i t l lt h ei m a g ee n h a n c e m e n ta n de d g ed e t e c t i o n t h ei m a g e a n dt h es u p p o r tv e c t o rm a c h i n ea r ec o n t a c t e dw i t ht h ec h a r a c t e r i s t i c so fs u p p o r t v e c t o rr e g r e s s i o n , s o 雒t of o r mt h ei m a g es v r i nt h i sp a p e r , t h et r a d i t i o n a lm e t h o d s o fi m a g ee n h a n c e m e n ta p p l i e dt os v r i m a g e sa n da c h i e v e dg o o dr e s u l t s t h i sp a p e r i m p r o v e st h et r a i n i n gm e t h o do fs u p p o r tv e c t o rm a c h i n ew h i c hi su s e dt od e t e c te d g e ， s h o r t e n st h et r a i n i n gt i m ea n dt h ed e t e c te f f e c ti sg o o d b e s i d e st h a t ，t h ea u t h o r c o m p a r e sa n dc o n t r a s t st h ee f f e c t sd i f f e r e n tk e r n e lf u n c t i o n sh a v eo nt h ep e r f o r m a n c e o f e d g ed e t e c t i o nu n d e r d i f f e r e n ts n rc i r c u m s t a n c e s k e y w o r d s ：i m a g ee n h a n c e m e n t , 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 , c a n n y o p e r a t o r i i 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 日期：净4 鱼当 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名： 南京邮电大学硕士研究生学位论文 一 第一章绪论 第一章绪论 1 1 图像处理与分析 图像是用各种观测系统以不同形式和手段观测客观世界而获得的，可以直接 或间接作用于人眼并产生视知觉的实体【l 】。图像可根据其形式或产生方法有多种 分类方式：从人眼的视觉特点上可将图像分为可见图像和不可见图像：按波段多 少图像可分为单波段、多波段和超波段图像：按图像空间坐标和明暗程度的连续 性可分为模拟图像和数字图像【2 】。一幅图像可定义为一个二维函数或三维函数， 当空间坐标和幅度值为有限、离散的数值时称该图像为数字图像。数字图像是由 有限的元素组成的，每个元素的坐标代表场景点的位置，而元素的值代表场景点 的某个特征量，这些元素称为图像元素。 对图像进行的一系列的操作以达到预期目的的技术称为图像处理。图像处理 分为模拟图像处理和数字图像处理两种方式。数字图像处理，简称为图像处理， 指利用计算机来处理数字图像，从而获得某种预期结果的技术。 由于数字电子技术的迅猛发展给数字图像处理提供了先进的技术手段，基于 计算机的图像处理学也就成为研究图像信息的- i - 崭新学科。近年来，数字图像 处理技术得到更大的重视和长足的发展，出现了许多相关的新理论和新设备，并 已在科学研究、工业生产、医疗卫生、教育、娱乐、管理和通信等方面得到了广 泛的应用，并发挥着重要的作用。 图像处理所包含的内容非常丰富，包括图像的采集、编码、存储和传输，图 像的变换、增强、恢复和重建，图像的分割，特征的提取和测量，序列图像的校 正，图像数据库的建立、索引、查询和抽取，图像模型的建立，图像知识的利用 和匹配，图像和场景的解释和理解，以及基于它们的推理、判断、决策和行为规 则等。根据抽象程度的不同，图像处理可分为三个层次：狭义图像处理、图像分 析和图像理解。如图1 1 所示。图像处理学是既相互联系又相互区别的狭义图像 处理、图像分析和图像理解三者的有机结合。狭义图像处理侧重研究图像之间的 变换，主要指对图像进行各种操作以改善图像的视觉效果，或对图像进行压缩编 码以减少所需的存储空间或传输时间、传输通路的要求，实质上是一个从图像到 图像的处理过程。图像分析主要是对图像中感兴趣的目标进行检测和测量，从而 建立对图像的描述，是一个从图像到数值或符号的处理过程。图像理解则是在图 像分析的基础上，进一步研究图像各目标的性质和它们之间的相互联系，并得出 堕室些皇查兰堡主堡窒生堂垡丝兰笙二童丝笙 对图像内容的理解以及对原来客观场景的解释，从而指导和规划行动。图像分析 主要以观察者为中心研究客观世界，图像理解是以客观世界为中心，借助知识和 经验等来把握整个客观世界。 抽 象 程 度 高 语 义 低 高层 中层 低层 小 大 数 据 量 图1 1 图像处理三层次示意图 狭义图像处理、图像分析和图像理解是处在三个抽象程度和数据量各有特点 的不同层次上。狭义图像处理是比较低级的操作，主要在图像像素级上进行处理； 图像分析则进入了中层，经分割和特征提取，把原来以像素构成的图像转变成比 较简洁的非图像形式的描述；图像理解是高层操作，是从描述中抽象出来符号来 进行运算，其处理过程和方法与人类的思维推理有许多类似之处。 图像处理学是- f l 关于图像处理的综合性边缘学科，从它的研究方法来看， 它与数学、物理学、生物学、生理学、心理学、电子学、计算机科学等许多学科 相互借鉴、相互联系，虽然各有侧重但又互为补充。另外，以上各个学科都得到 了人工智能、神经网络、遗传算法、模糊逻辑等新理论、新工具、新技术的支持， 并因此得到不断的进展。从它的研究范围来看，它与模式识别、计算机视觉、计 算机图形学等多个专业又互相交叉，既有区别又有联系，i 从它的应用范围来看， 它与生物医学、材料、遥感、通信、交通管理、军事侦察、文档处理和工业自动 化等许多领域也是不可分割的。随着信息技术的发展，数字图像处理将在社会生 活中的更多领域得到更为广泛的应用。 2 操作对象 号 标 素 符 目 像 南京邮电大学硕士研究生学位论文第章绪论 1 2 图像增强的研究与发展现状 图像在采集过程中不可避免的会受到传感器灵敏度、噪声干扰以及模数转换 时量化问题等各种因素的影响，从而导致图像无法达到令人满意的视觉效果。为 了实现人眼观察或者机器自动分析、识别的目的，对原始图像所做的改善行为， 就被称作图像增强。图像增强包涵了非常广泛的内容，凡是改变原始图像的结构 关系以取得更好的判断和应用效果的所有处理手段，都可以归结为图像增强处 理。其目的就是为了改善图像的质量和视觉效果，或将图像转换成更适合于人眼 观察或机器分析、识别的形式，以便从中获取更加有用的信息。 常用的图像增强处理方式包括灰度变换、直方图修正、图像锐化、噪声去除、 几何畸变校正、频域滤波和彩色增强等。由于图像增强与感兴趣的物体特性、观 察者的习惯和处理目的密切相关，尽管处理方式多种多样，但它带有很强的针对 性。因此，图像增强算法的应用也是有针对性的，并不存在一种通用的、适应各 种应用场合的增强算法。于是，为了使各种不同特定目的的图像质量得到改善， 产生了多种图像增强算法。这些算法根据处理空间的不同分为基于空间域的图像 增强算法和基于变换域的图像增强算法。基于空间域的图像增强算法又可以分为 变换增强算法、滤波增强算法以及空域彩色增强算法；基于变换域的图像增强算 法可以分为平滑增强算法、锐化增强算法以及频域彩色增强算法。 尽管各种图像增强技术已取得了长足的发展，形成了许多成熟、经典的处理 方法，但新的增强技术依然在日新月异地发展完善，不断推陈出新( 如小波变换， k l 变换等) 。 1 3 图像边缘检测的研究与发展现状 边缘是图像最基本的特征，边缘检测在计算机视觉、图像分析等应用中起着 重要的作用，是图像分析与识别的重要环节，这是因为图像的边缘包含了用于识 别的有用信息，所以边缘检测是图像分析和模式识别的主要特征提取手段。 所谓边缘是指其周围像素灰度发生阶跃变化或屋顶状变化的那些像素的集 合，它存在于目标与背景、目标与目标、区域与区域、基元与基元之间。因此它 是图像分割所依赖的重要特征，也是纹理特征的重要信息源和形状特征的基础： 而图像的纹理形状特征的提取又常常依赖于图像分割。图像的边缘提取也是图像 匹配的基础，因为它是位置的标志，对灰度的变化不敏感，它可作为匹配的特征 点。图像的其他特征都是由边缘和区域这些基本特征推导出来的。 3 南京邮电大学硕士研究生学位论文 第一章绪论 图像的主要信息都存在于图像的边缘中，主要表现为图像局部特征的不连续 性，是图像中灰度变化比较剧烈的地方，即我们通常所说的信号发生奇异变化的 地方。奇异信号沿边缘走向的灰度变化剧烈，通常我们将边缘划分为阶跃状和屋 顶状两种类型：阶跃边缘中两边的灰度值有明显的变化：而屋顶状边缘位于灰度 增加与减少的交界处。在数学上可利用灰度的导数来刻画边缘点的变化，对阶跃 边缘、屋顶状边缘分别求其一阶、二阶导数。 对于阶跃性边缘，二阶方向导数在边缘处呈零交叉；对于屋顶状边缘，二阶 方向导数在边缘处取极值。边缘反应了局部区域内特征的差别，它表示为图像信 息的某种不连续( 如灰度突变，纹理以及彩色的变化) 。著名的“马赫带效应”指 出：人的视觉对物体光度变化的部分有特殊的增强效应，即在不同光强度区的边 缘周围引起“过量调整”。物体边缘特征是与图像中灰度发生跳变的部分相对应 的。因此，基于灰度不连续性特征检测的方法成为图像边缘提取的主要方法之一。 在众多视觉模块计算中，通常把边缘检测作为视觉计算的第一步，高层次计算机 视觉处理能否成功极大地依赖于边缘检测算子的性能。 由于实际处理的图像一般都是含噪图像，所以在提取边缘的同时还需要考虑 所用方法抗噪性能如何，是否能够消除噪声干扰带来的伪边缘。因此，边缘检测 方法的优劣直接影响着图像特征提取及其他后续处理，是图像预处理中的关键。 由于边缘是图像的最基本特征，它能勾画出区域的形状、能被局部定义以及 能传递大部分图像信息等诸多优点，所以边缘信息的提取无论是对人类还是对机 器视觉来说都是一个最重要、最经典的课题。边缘检测的定义有很多种，其中最 常用的一种定义为：边缘检测是根据引起图像灰度变化的物理过程来描述图像中 灰度变化的过程。 长期以来，人们一直在研究各种能较好实现边缘检测的方法口嘲。但由于以 下原因：图像本身的复杂性：有效边缘与噪声均为高频信号，容易混淆：光照阴影 及物体表面纹理等因素在图像中均表现为边缘：对于不同的使用者来说所关心的 边缘信息各不相同等因素的影响，使得边缘提取迄今为止仍然是一个难题。 已有的边缘检测方法可分为以下几类h 1 ： 1 、经典算子法 经典的边缘检测方法是以原始图像为基础，对图像的各个像素考察它的某个 领域内灰度阶跃变化，利用边缘邻近一阶或二阶方向导数变化规律检测边缘。由 4 南京邮电大学硕士研究生学位论又 第一章绪罐 于边缘点往往对应于一阶微分值大的点，早期学者们提出的都是基于梯度的边缘 检测算子：r o b e r t s 边缘检测算子伯1 、s o b e l 边缘检测算子门1 、p r e w i t t 边缘检测 算子n0 i l l 、k i r s c h 边缘检测算子n 2 1 等。这些算子都是现在应用比较广泛的方法， 它们运算量小，操作简单。但基于梯度的边缘检测算子在边缘附近区域产生的响 应较宽，所以利用上述算子得到的边缘还需后续的细化处理，从而使得边缘定位 精度不高。一阶微分的局部最大值对应着二阶微分的过零点，即图像边缘点一阶 微分的峰值处同为二阶微分的零交叉点，基于此，人们提出了二阶微分算子法一 拉普拉斯边缘检测算子n 村，它在灰度阶跃边缘的两侧均有响应。其值一边为正， 一边为负，而对斜坡形边缘响应为零，即值为零，并且在此零值点的两侧也有一 正一负两个峰值。不论是阶跃边缘还是斜坡边缘，这一正一负两峰值的大小及走 向，反映了边缘的强弱及走向。它对灰度突变更加敏感，因此使得噪声对图像的 影响变大。 2 、最优算子法 最优算子是在经典边缘检测算子的基础上发展得来的，这类方法是根据信噪 比求得检测边缘的最优滤波器。 为提高传统算子的抗噪性能，d m a r r 提出可先对图像进行高斯平滑，再使 用旋转不变的拉普拉斯算子提取二阶导数的过零点来得到图像的边缘。此过程与 人类视觉观察边缘的途径很相似，简称l o g ( l a p l a c i a no fg a u s s i a n ) 算子。 数学上已经证明n 钔，l o g 算子是按照二阶导数零交叉点检测阶跃型边缘的最佳算 子。 j o h nf c a n n y 把边缘检测问题转换为检测单位函数极大值问题，根据边缘 检测的有效性和定位的可靠性，研究了最优边缘检测器所需的特性，给出了评价 边缘检测性能优劣的三个指标：信噪比、定位性能、对单一边缘仅有唯一响应， 即单个边缘产生多个响应的概率要低，并且虚假边缘响应应得到最大抑制。这就 是著名的c a n n y 算子酊。c a n n y 首次将上述三个指标用数学的形式表达出来，然 后采用最优化数值方法，得到了对应给定边缘类型的最佳边缘检测模板。在二维 情况下，c a n n y 算子的方向性质使边缘检测和定位性能比l o g 算子要好，具有更 好的抗噪性能，而且能产生边缘梯度方向和强度两个信息，为后续处理提供了方 便。但也存在不足之处，为了得到较好的结果通常需要使用较大的滤波尺度，导 致一些细节丢失。 南京邮电大学硕士研究生学侄_ 论文第 一绪论 3 、曲面拟合法 曲面拟合法就是把图像看作曲面，首先对图像进行某种形式的拟合，再在拟 合曲面上根据拟合参数求得边缘。其基本思想是用一个平滑的曲面与待测点周围 邻域内像素点的灰度值进行拟合，然后计算此曲面的一阶或二阶导数。h u e c k e l n 吼川提出了首先用二维分段线性函数对原始图像作最佳拟合，然后用参数估计的 方法进一步检测边缘，他还引进了正交基作近似简化运算。对于阶跃型边缘， h a r a l i c k n 们提出用离散正交多项式对原始图像每一像素的某邻域作曲面最佳拟 合，求得系数估计，然后在拟合曲面上求二阶方向导数的零交叉点，最终提取阶 跃型边缘点。h a r a l i c k 的算法精度有较大提高，但由于正交多项式基构造过程复 杂，灵活性差，不易表达复杂边界的形状，应用受到了限制。 4 、多尺度方法 早期边缘检测的主要目标是为了处理好单一尺度上的检测和定位之间的矛 盾，而忽略了在实际图像中存在的多种干扰边缘，往往影响到边缘的正确检测和 定位。r o s e n f e l d 等n 耵首先提出要把多个尺寸的算子检测到的边缘加以组合，m a r r 等人口1 倡导同时使用多个尺度不同的算子，并提出了一些启发性的组合规则。这 一思想后来经w i t k i n 等发展成了尺度空间滤波理论，说明了不同尺度上的零 交叉的因果性。多尺度信号处理不仅可以辨识出信号中的重要特征，而且能以不 同细节程度来构造信号的描述，非常适用于高层次的视觉处理。 小波变换是近年得到广泛应用的数学工具乜旧1 。与傅立叶变换和窗口傅里叶 变换相比，小波变换是时间和频率的局部变换，因而能有效地从信号中提取信息， 它通过伸缩和平移等运算功能对函数或信号进行多尺度细化分析，解决了傅立叶 变换不能解决的很多困难问题，因而被誉为“数学显微镜。作为多尺度通道分 析工具，小波变换为信号在不同尺度上的分析和表征提供了一个精确和统一的框 架2 朝。 基于小波变换的各种图像边缘检测方法在国内外已有很多n 卜3 引。其中，文献 2 5 采用b 样条小波检测边缘：文献 2 6 采用以零点为对称点的对称二进制小波 来检测屋顶状边缘，用以零点为反对称点的二进制小波来检测阶跃型边缘：文献 2 7 采用h a a r 小波进行边缘检测：文献 2 8 采用双h a a r 小波来检测边缘：文献 2 9 采用了多进制小波检测边缘：正交小波口也被用来提取多尺度边缘。 6 南京邮电大学硕士研字生学位论文第一章绪论 5 、基于自适应平滑滤波的方法b 3 洲1 基于自适应平滑滤波的边缘检测方法的基本思想是利用一个通用算子对信 号进行平滑，该算子能使其本身与信号的局部结构相适应。利维( l e v ) 等人提出 的一种加权模板，其系数是根据窗口的中心点及其邻近点的灰度平均值来确定。 还有一种方法是选择具有与中心点灰度值最接近的邻近点，并利用这些邻近点灰 度值的平均值取代中心点值。一种更复杂的方法是根据每一点的邻域的局部统计 性质来确定模板的系数。吉曼( g e m a n ) 提出利用模拟退火( s i m u l a t e dn e a l i n g ) 进行边缘检测的方法就属于自适应边缘检测方法。 6 、松弛迭代法汹蚓 有学者从边界增强的角度出发提出了松弛迭代的方法。这种方法分为二步， 图像的平滑、边缘的获取、松弛迭代。它使用边缘点的位置、梯度矢量曲率等信 息来初始化松弛网络像素的标记，根据边界曲线上的点的信息在局部具有一致性 和相关性，而噪声点的信息是随机的、无规律的特点，进行邻域点的信息的相互 作用，增强有规律的边缘信息同时削弱无规律的噪声，通过不断的迭代对标记进 行重复修正和某些约束，最后使得迭代收敛于真实的边缘。 7 、数学形态学在边缘检测中的应用 数学形态学m 1 是一种非线性滤波方法，它可以用来解决抑制噪声、特征提取、 边缘检测等图像处理问题汹删。数学形态学中二值图像的形态变换是一种针对集 合的处理过程m 1 ，其基本运算是腐蚀和膨胀。这种算法简单，适用于并行处理， 且易于硬件实现，适于对二值图像进行边缘提取h 。灰度数学形态学是二值数学 形态学对灰度图像的自然扩展。s o i l l e h 2 3 将灰度形态学的梯度与阂值相结合用于 边缘检测，可较好的检测出被噪声污染图像中的边缘。 上面介绍的几种方法都是目前研究较多的边缘检测方法，此外还有采用神经 网络进行边缘检测的方法h 孔枷、统计学方法h 习等。支持向量机在边缘检测方面的 应用研究也成为一个新的研究热点。 1 - 4 本文的内容安排 本文的主要研究内容是图像增强和图像边缘检测，首先阐述了课题的研究背 景、意义以及该研究领域的发展现状，介绍了一些具有代表意义的经典的图像增 强和边缘检测方法，并且对这些经典方法的检测结果进行了相关的分析比较。接 下来本文着重阐述了基于支持向量机的图像增强和边缘检测方法，并进行仿真实 7 南京邮电大学硕士研究生学位论文第一章绪论 验，取得了理想的效果。 整篇文章的具体内容做如下安排： 第一章，阐述了课题的研究背景和发展现状。 第二章，介绍了机器学习的基本方法和统计学习的基本思想，以及学习过程 中的经验风险和结构风险模型。 第三章，介绍了支持向量机的基本理论，支持向量分类和支持向量回归两种 情况。 第四章，首先介绍了经典的图像增强处理方法，接着提出了新的基于支持向 量回归的图像增强方法，并经行仿真，与经典方法经行比较，新方法增强效果较 好，并很好的保持了图像原有的灰度分布，更有利于图像的后续处理。 第五章，对现有的经典的边缘检测算法进行了介绍，并对这些经典检测方法 进行了分析比较，提出了新的基于支持向量机的边缘检测算法，该算法改进了支 持向量机的训练过程，缩短了训练时间，并能取得良好效果。最后，在不同信噪 比条件下，选择不同的核函数进行了仿真，比较了不同核函数对边缘检测性能的 影响。 第六章，对全文进行了总结和展望。 南京邮电夭学硕士研究生学位论文第_ 三荦机器学习与统计理论 第二章机器学习与统计理论 2 1 引言 人的智慧中一个很重要的方面是从实例中学习知识的能力，即通过对已知事 实的分析总结出规律，预测无法直接观测的事实。在这种学习中，重要的是举一 反三的能力，即利用学习得到的规律，不但可以较好地解释已知事实，而且能够 对未来或无法观测的现象做出正确的预测和判断，这叫做推广能力。在机器智能 的研究中，希望用机器来模拟人的这种能力，这就是机器学习理论的出发点。机 器学习的目的是，设计某种方法，通过对已知数据的学习，找到数据内在的相互 依赖关系，从而对未知数据进行预测或对其性能进行判断。传统的学习理论主要 是基于经验风险最小化原则( e m r ) 的。所谓经验风险，是指在训练集上的风 险，通常用均方误差表示。理论表明，当训练数据趋于无穷多时，经验风险收敛 于实际风险。因此经验风险最小化原则隐含地使用了训练样本无穷多的假设条 件。但是在现实问题中，可用的训练样本数目总是有限的。虽然人们知道这一点， 但传统上仍然基于经验风险最小化原则来推导各种算法。在实际应用中，这些算 法遇到了很多困难，如小样本问题，高维问题，学习机器结构问题和局部极值问 题等。 统计学习理论从控制学习机器复杂度的思想出发，提出了结构风险最小化原 则。该原则使得学习机器在可容许的经验风险范围内，总是采用具有最低复杂度 的函数集。支持向量机是在统计学习理论基础上发展出的一种性能优良的学习机 器。其基本的思想是，在线性情况下，在原空间寻找两类样本的最优分类超平面， 而在非线性情况下，首先将原始模式空间映射到高维的特征空间，并在该特征空 间中寻找最优分类超平面。支持向量机利用一些具有特殊性质的核函数，将特征 空间中的内积运算转化为低维空间中的非线性运算，从而巧妙地避免了高维空间 中的计算问题。 2 2 机器学习的基本方法 2 2 1 学习问题的一般表示 机器学习的目的是根据给定的训练样本，估计系统输入与输出之间依赖关 系，使之能够尽可能准确地预测系统的未来输出【4 6 1 。机器学习的基本模型，可 以用图2 1 表示。图2 1 中，系统是研究的对象，它在给定的输入x 下得到输出y 。 9 南京：邮电大学硕士研究生学位论文第二章机器学习与统计理论 在训练过程中，输入与输出组成训练样本( x ，j ，) ，提供给学习机器。在测试过程中， 训练后的学习机器对于输入戈给出预测输出少。 图2 1 机器学习问题的基本模型 输出y 预测输出j ， 假定对于所研究的系统，已知变量y 与输入x 之间存在一定的未知依赖关 系，即存在一个未知的联合概率f ( x ，y ) ，对该系统的输入输出进行观测，得到 如下独立同分布的观测样本 ( 毛，m ) ，( 而，奶) ，( 矗，此) ， ( 2 1 ) 假定学习机器具有广义参数w ( 所有参数的集合) ，对于输入工，学习机器 的预测输出y 可以表示为y = f ( x ，w ) ，则该学习机器的预测输出的期望风险可以 表示为 r ( w ) = 弘( j ，厂( x ，w ) 炒( z ，j ，) ( 2 2 ) 其中，w q 为函数的广义参数，l ( y ，s ( x ，w ) ) 为损失函数，表示在输入x 下，用学习机器的预测输出对系统的实际输出y 进行估计而造成的损失。 因此，机器学习问题也可以表示为，从一组独立同分布的观测样本出发，经 过最小化风险泛函r ( w ) ，确定学习机器的广义参数w 的过程。 2 2 2 经验风险最小化原则 要使式( 2 2 ) 定义的期望风险最小化，必须依赖关于联合概率f ( x ，少) 的信 息，但是，在实际的机器学习问题中，我们只能利用已知样本( 2 1 ) 的信息，因 此期望风险无法直接计算和最小化。根据概率论中大数定律的思想，人们自然想 到用算术平均代替式( 2 2 ) 的数学期望，于是定义了 1 0 南京邮电大学硕士研究生学位论文 一 第二章机器学习与统计理论 ( w ) 2 吉善( 只，胞，w ) ) ( 2 3 ) 来逼近式( 2 2 ) 定义的期望风险。由于w ) 是用已知的训练样本( 即经验 数据) 定义的，因此称作经验风险。用对参数w 求经验风险( w ) 的最小值代 替求期望风险r ( w ) 的最小值，就是所谓的经验风险最小化( e m p i r i c a lr i s k m i n i m i z a t i o n 简称e p , m ) 原则。 仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可 以发现，从期望风险到经验风险最小化并没有可靠的理论依据，只是直观上合理 的想当然做法。 首先，( w ) 和r ( w ) 都是函数，概率论中的大数定律只说明( 在一定条 件下) 当样本趋向于无穷多时，( w ) 将在概率意义上趋近于r ( w ) ，并不保 证( w ) 和r ( w ) 在同一个点上取得最小值。 其次，没有理论保证在样本数无穷大条件下得到的学习机器，在样本数有限 的情况下仍能具有好的效果。 多年来，经验风险最小化原则作为解决模式识别等机器学习问题的基本思 想，几乎统治了这个领域内的所有研究。大部分的研究者们把注意力集中在如何 更好地逼近最小化经验风险的最优解。 2 3 统计学习理论的基本思想 4 7 - 5 1 】 任何学习机器都可以看成是一组函数集合，机器学习问题就是从函数集合中 选择合适的逼近函数并参数化的过程。所谓学习机器的容量也就是它所对应的函 数集的容量，或者叫复杂度。容量或复杂度代表了函数集实现从输入到输出的映 射的能力，对学习机器来说，叫做学习能力。容量越大，机器的学习能力就越强。 在模式识别问题中，学习能力强的机器能够得到更加复杂的分类面，然而，越复 杂的分类面，就越依赖于训练数据分布的细节，这种对训练数据的过于细致的依 赖，往往会导致学习机器的泛化能力不强。统计学习理论用v c 维来描述学习机 器的容量，并从控制学习机器容量的思想出发，结合经验风险和训练样本数目， 导出了期望风险在不同情况下的一组风险上界。这些界具有如下特点： 1 、这些界是通用的，与具体数据的分布无关； 堕室堂皇奎堂堡主堕窒生堂垡丝壅至三至型! 堡兰翌皇竺生堡丝 2 、在小样本情况下同样成立； 在实际的训练过程中，可以通过最小化风险上界，实现对学习机器的优化， 因此所得到的学习机器的复杂度受到很好地控制，即使在小样本情况下也同样具 有比较高的泛化能力。 2 3 1 学习过程一致性条件 学习过程的一致性是指当训练样本数趋于无穷大时，经验风险的最优值能够 收敛到真实风险的最优值。只有满足一致性条件，才能保证在经验风险最小化原 则下得到的最优结果当样本数无穷大时趋近于使期望风险最小化的最优结果。对 于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验风险在如下 意义上一致地收敛于期望风险： l i m p ls u p ( r ( w ) - ( w ) ) 一占i = 0 ( 2 4 ) 打 l 。 一 其中，占 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 k i s 提出了v c 维概念硒副。模式 识别方法中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 维。如在l q 维实数空间中， 线性分类器和线性实函数的v c 维是n + l ，而对一些比较复杂的学习机器( 如神经 1 2 堕塞坚皇奎堂堕主里塞竺堂垡笙壅笙三童垫堡堂翌兰堕生堡堡 网络) ，其v c 维除了与函数集选择有关外，还受学习算法等的影响，因此其确定 将更加困难。但是，在实际应用统计学习理论中，可以通过变通的办法巧妙地避 开直接求v c 维的问题。 2 3 3 泛化误差的边界 统计学习理论从v c 维的概念出发，推导出了关于经验风险和实际风险之间 关系的重要结论，称作泛化误差的边界。这些界是分析学习机器性能和发展新的 学习算法的重要基础。统计学习理论中给出了如下的估计真实风险的不等式，对 于任意a r ( r 是抽象参数集合) ，以至少l 一，7 的概率满足以下不等式咖1 ， 脚) ( w ) + 甲 ( 2 5 ) 其中，甲： l 以 ( 2 6 ) ( 们表示经验风险；y ( 尝) 称为置信风险；n 是样本个数；参数h 称为一 个函数集合的v c 维。当h r 较大时，置信风险较大，此时用经验风险近似期望 风险就会出现较大的误差。如果样本数较多，使得i 较小，则置信风险就会较 小，经验风险最小化的最优解就会接近真正的最优解。 对于一个特定的学习问题，当样本数固定时，如果学习机器的v c 维越高( 复 杂度越高) ，则置信风险越大，导致真实风险与经验风险之间可能的差就越大。 因此，在设计分类器时，不但要使经验风险尽可能小，而且要控制其v c 维也尽 可能小，从而缩小置信风险，使期望风险最小。 2 3 4 结构风险最小化原理 “结构风险最小化原理”的基本思想是：如果我们要求风险最小，就需要使 得不等式中两项相互权衡，共同趋于极小：另外，在获得的学习模型经验风险最 小的同时，希望学习模型的泛化能力尽可能大，这样就需要h 值尽可能小，即置 信风险最小。 由于有式( 2 5 ) 的理论依据，统计学习理论提供了一种在小样本情况下， 使( w ) 极小化的同时，控制v c 维( 模型复杂性) 的方法，即对于给定的有限 1 3 南京邮电大学硕士研究生学位论文一 第二章 机器学习与统计理论 样本，选择最佳模型复杂性的方法，该方法描述如下： 首先把函数集s = f ( x ，们，w eq 分解为一个函数子集序列，使其具有一种 嵌套结构 sc 岛c 7 c 7 瓯c c s ( 2 7 ) 其中墨= f ( x ，w ) ，w q 为函数集的子集( 元素) ，其v c 维数魂为有限。在 此结构中，嵌套子集按其复杂性( 即v c 维数大小) 的顺序排列： ( 2 8 ) 这样，在同一个子集中，置信范围是相同的。在每个子集中寻找最小经验风 险，通常它随着子集复杂度的增加而减小。选择最小经验风险与置信范围之和最 小的子集，就可以达到期望风险的最小，这个子集中使经验风险最小的函数就是 要求的最优函数。这种思想称作结构风险最小化原则( s t r u c t u r a lr i s k m i n i m i z a t i o n ，简称s r m ) 。 图2 2 给出了结构风险最小化的示意图。 风险 想： 围 风险 h 图2 2 结构风险最小化的示意图 根据这一分析，我们得到两种运用结构风险最小化原理构造的学习机器的思 1 4 塑室塑皇奎堂堡主塑塞竺堂垡笙奎苎三童垫壁兰望皇堑过堡垒 ( 1 ) 给定一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在 每个子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的子集。 当子集数目较大时，此方法较费时，甚至不可行。 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小 的经验风险( 例如，使得训练误差为o ) 。然后，在这些子集中选择适当的子集 使置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求解的最 优函数。 可见，利用结构风险最小化原理的思想，就可以完美解决传统机器学习中的 过学习问题。支持向量机通过最大化分类边界以最小化v c 维，也即在保证经验 风险最小的基础上最小化置信风险，从而达到最小化结构风险的目的，因此支持 向量机方法实际上就是结构风险最小化思想的具体实现。 南京邮电大学硕士研究生学位论文一第三章支持向量机理论 第三章支持向量机理论 3 1 引言 给予数据的机器学习是现代智能技术中的重要方面，研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。包括模式 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。 传统统计学研究是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于 此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习 方法实际中表现却可能不尽人意【4 9 l 。 与传统统计学相比，统计学习理论( 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 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 1 ，目前 仍处在不断发展阶段。其方法是建立在统计学习理论的v c 维理论和结构风险最 小原理基础上的，根据有限的样本信息模型的复杂性( 即对特定训练样本的学习 精度，a c c u r a c y ) 和学习能力( 即无错误地识别任意样本的能力) 之间寻求最佳 折衷，以期获得最好的推广能力( g e n e r a l i z a t i o na b i l i t y ) 。 支持向量机分类算法具有四个显著特点：( 1 ) 利用大间隔的思想降低分类 器的v c 维，实现结构风险最小化原则，控制分类器的推广能力：( 2 ) 利用m e r c e r 核实现先行算法的非法线性化：( 3 ) 稀疏性，即少量样本( 支持向量) 的系数不 为零，就推广性而言，较少的支持向量数在统计意义上对应好的推广能力，从计 算角度看，支持向量减少了核形式判别式的计算量；( 4 ) 算法设计成凸二次规 划问题，避免了多解性【5 6 】。 1 6 南京邮电大学硕士研究生学位论文 第三章支持向量机理论 3 2 支持向量机分类 假定大小为，的训练样本集 ( 薯， ) ，i - - 1 ，2 ，) ，由二类别组成，如果r “ 属于第1 类，则标记为正只- - i ，如果属于第2 类，则标记为负( 只= - i ) 。学习 的目的是构造一个决策函数，将测试数据尽可能正确地分类。针对训练样本集为 线性或非线性两种情况分别讨论【5 7 l 。 3 2 1 线性情况 如果存在分类超平面 国x - i - b = 0 ( 3 1 ) 使得 三：三+ 4 - b 6 三1 - 1 ，y 只e 三- 11 ，i ：。，2 ， c 3 2 ， 国毛 ， = ，= l ， 则称训练集是线性可分的，其中t o x 表示向量彩月”与x r “的内积。式 ( 3 1 ) 和式( 3 2 ) 中的国尺”，b r 1 都进行了规范化，使每类样本集中与分类 超平面距离最近的数据点满足式( 3 2 ) 的等式要求。对于式( 3 2 ) ，可以写成如 下形式 y j ( 缈薯+ 6 ) 1 ， i = 1 ，2 ， ( 3 3 ) 由统计学习理论可知，如果训练样本集被超平面没有错误地分开，并且距超 平面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面，如图 3 1 所示，由此得到的决策函数 厂( z ) = s g i l ( 缈- x + b ) ( 3 4 ) 其推广能力最优，其中s g n ( ) 为符号函数。最优超平面的求解需要最大化 2 1 1 缈u ，即最小化丢忪1 1 2 ，为如下的二次规划问题 r a 脚i ，。n2 1 - 。i 删i i ( 3 5 ) s j 咒( 缈x + 6 ) 1 ， i = 1 ，2 ，7 南京邮电大学硕士研究生学位论文第三磬支持向量机理论 最优超 w - x