（概率论与数理统计专业论文）基于闭凸包收缩的多分类方法.pdf

摘要 支持向量机是由b e l l 实验室的v a p n i k 等人提出的种针对分类和回归问题的新型机器学习 方法，是借助于最优化方法解决机器学习问题的新j ：具支持向量机方法基于统计学习理论与结 构风险最小化原理，具有良好的推广性和较高的准确率它集成了最优分类超平面、核技巧、凸二 次规划等多项技术，能有效地解决“过学习”、“维数灾难”和局部极小点等问题由于出色的学 习性能，支持向量机已经成为当前机器学习界的一个研究热点，并在很多领域得到了广泛的应用， 包括模式识别、同归估计等方面由于支持向量机方法最初是针对二类别的分类问题提出的，如 何将二类别分类方法扩展到多类别分类是支持向量机研究的一个重要内容 本文主要做了以下几个方面的：r ：作 1 介绍了机器学习、统计学习理论以及支持向量机的发展和研究现状讨论了支持向量机的 理论和算法，包括核函数理论等总结了目前常用的基于支持向量机的多分类方法，包括一对多方 法、一对一方法、决策二义树方法对比讨论了各种方法的优缺点 2 在平分最近点法和闭凸包收缩原理的基础上，提出了一种基于闭凸包收缩原理推厂“的多类 分类方法，该方法在一定程度上能克服传统方法的一些不足 3 利用核方法的思想针对原始空间中非线性可分的多分类问题，基于上述闭凸包收缩原理构 造了特征空间上的线性可分多分类算法并通过仿真试验验证了该方法的有效性 关键词：支持向量机，闭凸包，多分类，核方法 a b s t r a c t s u p p o r tv e c t o rm a c h i n ei san o v e lm a c h i n el e a r n i n gm e t h o dp r o p o s e db yv a p n i ka n d h i sg r o u pa tb e l ll a b o r a t o r yf o rc l a s s i f i c a t i o na n dr e g r e s s i o np r o b l e m s i ti san e wt o o lt o s o l v ep r o b l e m so fm a c h i n el e a n i n gb a s e do no p t i m i z a t i o nt e c h n i q u e s u p p o r tv e c t o rm a - c h i n eb a s e do ns t a t i s t i c a ll e a r n i n gt h e o r ya n ds 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 eh a sg o o d g e n e r a l i z a t i o na n db e t t e ra c c u r a c y i tc h a r a c t e r i z e db yt h eu s i n go fo p t i m a lc l a s s i f i c a t i o n h y p e r p l a n e ，t e c h n i q u eo fk e r n e l sa n dc o n v e xq u a d r a t i cp r o g r a m m i n gc a ns o l v es o m ep r o b - l e m ss u c ha so v e r - l e a r n i n g ，d i m e n s i o nd i s a s t e ra n dl o c a lm i n i m i z a t i o ne f f e c t i v e l y s u p p o r t v e c t o rm a c h i n eh a sb e c o m er a t h e rp o p u l a rf o ri t se x c e l l e n tl e a r n i n gp e r f o r m a n c ei nm a c h i n e l e a r n i n gd o m a i n ，a n di sw i d e l ya p p l i e di nav a r i e t yo fr e g i o n ss u c ha sp 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 ne s t i m a t i o na n ds oo n t r a d i t i o n a ls u p p o r tv e c t o rm a c h i n ei sd e v e l o p e df o rb i - n a r yc l a s s i f i c a t i o np r o b l e m s h o wt oe x t e n di tf o rm u l t i - c l a s sc l a s s i f i c a t i o ni sas i g n i f i c a n t p u r p o s e t h em a i nw o r ko ft h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： f i r s t l y ，m a c h i n el e a r n i n g ，s t a t i s t i c a ll e a n i n gt h e o r y , t h ed e v e l o p m e n ta n dr e s e a r c ha c t u - a l i t yo fs u p p o r tv e c t o rm a c h i n ea r ei n t r o d u c e d t h et h e o r ya n da l g o r i t h mo fs u p p o r tv e c t o r m a c h i n ea r es u m m a r i z e d a n dt h et h e o r yo fk e r n e lf u n c t i o n ，p a r a m e t e r ss e l e c t i o na n do t h e r h o ts p o ti s s u e sa r ed i s c u s s e ds i m u l t a n e o u s l y c o m m o nm u l t i - c l a s sc l a s s i f i c a t i o nm e t h o d s i n c l u d i n g o n e a g a i n s tr e s t ，o n ea g a i n s to n e ，b i n a r yt r e ea r es u m m a r i z e d t h ea d v a n t a g ea n d d i s a d v a n t a g eo f t h e s em e t h o d sa r e c o m p a r e d s e c o n d l y ，o nt h eb a s i so ft h eb i s e c t i n g n e a r e s t - p o i n tm e t h o da n dt h et h e o r yo fc o n t r a c - t i o no ft h ec l o s e dc o n v e xh u l l ，t h em u l t i - c l a s sc l a s s i f i c a t i o nm e t h o d sa r ep r e s e n t e db a s e do n s p r e a d i n gt h et h e o r yo fc o n t r a c t i o no ft h ec l o s e dc o n v e xh u l l a n ds o m es h o r t c o m i n g so f t r a d i t i o n a lm e t h o d sa r eo v e r c a m e t h i r d l y , n o n l i n e a rs e p a r a b l em u l t i c l a s sp r o b l e mi no r i g i n a ls p a c ec a nb es o l v e du s i n g t h ei d e ao fk e r n e lm e t h o d ，a n dt h ea l g o r i t h mo fl i n e a rs e p a r a b l em u l t i c l a s sa l ec o n s t r u c t e d i nf e a t u r es p a c eb a s e do nt h et h e o r yo fc o n t r a c t i o no ft h ec l o s e dc o n v e xh u l l t h ee f f i c i e n c y o ft h en e wm u l t i c l a s sm e t h o di sp r o v e db yr e s u l t so fe x p e r i m e n t k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e ，c l o s e dc o n v e xh u l l ，m u l t i - c l a s sc l a s s i f i c a t i o n ，k e r - n e lm e t h o d 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特，i , i n 以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书面使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名：力历痹 时间： 矿尸年朋衫日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩日j 或扫掐等复制手段保 存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的 全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 锄垮 孰主力 时间： 矿护年厂月，罗日 时间：g 陟fo 年，月夕pb 1 1 课题研究的背景 第一章引言 2 0 世纪9 0 年代以来，计算机技术和信息技术的迅猛发展宣告了信息时代的到来，这个时代的 重要特征就是人们有了更多的机会和手段接触到大量数据海量数据时刻充斥着我们的生活，它 们将在生产和生活中发挥巨大作用因此人们投入了大量资源去收集、存储和处理数据而实际 问题中由于数据量太大，很难对其进行高效管理，或者由于数据结构太复杂，很难对其进行有效分 析，所以这些海量数据只有- d , 部分在发挥作用，大量濑在的有价值信息仍没有被挖撼出来，这就 出现了“数据爆炸，信息匾乏”的现象 对大型、复杂、信息丰富的数据集的理解实际上是政府、企业和科研领域的共同需要在政 府机构中，很多政策、法律、法规的制订都要有数据信息作为依据：在商务领域，公司和顾客的数 据都被认为是一种战略资产；在科研领域，研究者们既从数据中寻找规律义在用数据检验规律这 就要求对数据有深刻地理解，传统的数据库技术和数据分析方法己难以满足他们的要求如何从 海量数据中快速挖掘出有用知识，己成为信息时代一个十分紧迫而富有挑战的研究课题数据挖掘 技术( d a t am i n i n g ，d m ) 1 l 就是在这样的背景下应运而生的 基于数据的机器学习( m a c h i n el e a r n i n g ，m l ) 是数据挖撅技术中的重要内容，它研究从观测 数据出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测现有机器学习方法 共同的重要理论基础之一是统计学传统统计学研究的是样本数目趋于无穷大时的渐近理论，即当 样本趋于无穷多时的统计性质但在实际问题中，样本数目往往是有限的，通常的方法仍以样本无 穷多为假设进行算法推导和建模，因此一些理论上很优秀的学习方法在实际中的表现可能难以令 人满意比如，在普通的神经网络学习中，当样本数有限时，本来很好的学习算法却表现出很差的 推广能力，这种现象被称为过学习现象 为了解决这类问题，许多学者进行了坚持不懈的研究工作二十世纪六七十年代，v a p n i k 等人 开始建立一种研究有限样本情形下统计规律及学习方法性质的理论，即统计学习理论( s t a t i s t i c a l l e a r n i n gt h e o r y , s l t ) 2 ，3 1 ，它为有限样本的机器学习问题建立了一个良好的理论框架，较好地解决 了小样本、非线性、高维数和局部极小点等实际问题随着其理论的不断发展和成熟，也由丁神经 网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视 直到1 9 9 5 年，v a p n i k 和他的合作者们明确提出一种新的通用学习方法支持向量机( s u p p o r t v e c t o rm a c h i n e ，s v m ) 4 】后，该理论才受到广泛的重视并应用到不同的领域它基于v c 维理论和 结构风险最小化原理( s t r u c t u a lr i s km i n i m i z a t i o n ，s r m ) 训练学习机器，在很大程度上克服了传统 机器学习中的维数灾难以及局部极小等问题【2 】同时，根据有限的样本信息在模型的复杂性( 即对 特定训练样本的学习精度，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 ) 分类问题源于图像识别，疾病诊断和语音识别等许多实际问题从大规模数据库获取知识的 过程也涉及剑分类问题分类的目标是通过分析样本数据集来构造一个分类模型利用该模型能 够把数据库中的数据映射到某一类别，然后再利用数据预测实际的模式识别问题大多是多分类 问题如动物的分类，文本的分类，环境的分类等，能将这些分类问题很好的解决对人们的研究生物 物种形成的规律，各类疾病的有效治疗有着很人的作 j ，对人类的生存和发展带来的好处是不可估 量的 有很多种方式来表述模式分类器，其中用的最多的是一种判别函数肌( z ) ，i = 1 ，的形 式，如果对于所有的j i ，有a i ( x ) g a z ) ，则此分类器将这个特征向量z 判为第i 类多分类问 题的难点就是如何构造判别函数使各类能够正确的分开。对于异常值的识别，不可分区域如何划分 的问题，以及多分类问题的效率和识别精度问题等目前主要的多类分类方法有一次性分类方法， 对一，一对多，d a g s v m 等方法但是基于的思想是不同的，有基于s v i v l 、s v d d 、还有本文提 到的基于闭凸包收缩的多类分类方法，该方法易于理解，实施方便对于解决多类分类问题的效率 和识别精度有很大的帮助 1 2 支持向量机的发展历史与研究现状 1 2 1 支持向量机的发展历史 早在上世纪六十年代，v a p n i k 就开始了统计学习理论的研究，于上世纪六十至七十年代建立 了统计学习理论的基本理论框架 19 71 年，v a p n i k 和c h e r v o n e n k i s a l 提出v c 维理论 1 9 8 2 年，v a p n i k 提出结构风险最小化原理 19 9 2 年，b o s e r , g u y o n 和v a p n i k 5 提出最优边界分类器 1 9 9 5 年v a p n i k 4 等人提出支持向量机概念 1 9 9 7 年，v a p n i k ，g o l o w i c h 和s m o l a 介绍了基于支持向量机方法的回归算法 1 。2 1 支持向量机的研究现状 由于s v m 坚实的理论基础及其在很多领域表现出的良好性能，国内外正广泛开展对s v m 的 研究目前对s v m 的研究主要包括： 支持向量机的变形：为了使支持向量机在解决某些实际问题时具有更优良的特性，学者们对 二次规划的目标函数进行适当修改，从而构造出一些具有新的性质的支持向量机，如妒支持向量 机( v - s v m ) 2 t l 。最小二乘支持向量机( l e a s t - s q u a r es v m ，l s - - s v m ) 2 2 1 ，加权支持向量机( w e i g h t e d s v m ，w s v m ) 2 z 和模糊支持向量机( f u z z ys u p p o r tv e c t o rm a c h i n e ，f s v m ) 2 4 “2 6 】； 训练算法的改进：针对s v m 训练速度慢和时间空间复杂度大的问题，目前常见的支持向量 机训练算法有：b o s e r 等人在1 9 9 2 年提出的选块算法( c h u n k i n ga l g o r i t h m ) 5 1 ；o s u n a 在1 9 9 7 年提 出的分解算法【1 8 ，1 9 】：p l a t t 在1 9 9 8 年提出的序贯最小优化( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ，s m o ) 算法【2 0 】： 利用s v m 解决多类分类问题：经典的线性分类算法，起初都是针对两分类问题而提出的， 目前大多都是通过各种方法将两类分类机转化为多类分类机，这也是目前支持向量机研究的主要 内容之一，目前，对于多类分类问题，s v m 的解决途径有两种：一种是通过构造多个s v m 二值 分类器并将它们组合起来实现多类分类，例如o n e a g a i n s t o n e ( o a o ) 1 3 5 , 4 0 l 、o n e a g a i n s t a i i ( o a a ) a 7 3 0 1 、d a g s v m 3 6 ，4 1 1 虽然这三种方法是当前最常用且性能较优的，但o a o 和o a a 2 方法的泛化误著是无界的，再者，o a o 所需构造的子分类器的数量关于类别数k 成超线性增长， 共k ( k i ) 2 个，且在测试阶段，必须计算所有子分类判别函数，o a o 方法还有一个最明显的缺点 就是，每个子分类器必须都要非常仔细地调整，如果某个子分类器不规范化，则整个分类系统将趋 于过学习d a g s v m 方法解决了不可分区域问题，而且不一定要计算所有的子分类判决函数，但各 个子分类器在有向无环图中的位置也会对分类系统产生较大的影响另种是直接在一个优化公 式中同时考虑所有子分类器的参数优化 2 0 i 严格的讲，其思想类似于o a a 方法，只不过是把k 个 二值s v m 优化问题放在个最优化公式中同时优化，所以它也存在o a a 方法相同的缺点另外， 这种思想尽管看起来简洁，但在最优化问题求解过程中的变量远远多于第1 种，训练速度不及第1 种。且在分类精度上也不占优当训练样本数非常人时，这一问题更加突出由于s v m 是针对两分 类问题提出的，因此存在一个如何将其推广到多分类上的问题目前对于多类问题，s v m 的算法主 要有：“一对多”多分类方法【2 ，2 7 i ，“一对一”多分类方法【2 7 ，2 8 】，二义树多分类方法【2 9 ，3 0 】和一次 性求解方法1 3 0 i 1 2 11 2 3 支持向量机的应用 支持向量机出色的学习性能，使该技术已经成为机器学习界的研究热点，并在很多领域中得 到了成功的应用国内外学者的积极研究极大地推进了支持向量机在各领域应用的快速发展 如：手写汉字识别【6 ，7 j 、人脸识别和人脸检测【8 l 、网络入侵检测【9 】、文本分类 x o l 、语音识别 【l l 】、信号处理【1 2 】、图像分类与识别【1 3 】、三维地形处理【14 】、医疗诊断1 1 5 1 等众多研究领域 1 3 本文研究内容和文章安排 1 3 1 本文研究内容 s v m 方法拥有完备的数学理论基础，是一种在高维空间表示复杂的函数依赖关系的高效通用 手段和其他同类方法相比，s v m 具有全局优化、适应性强、理论完备、泛化性能好等优点自 2 0 世纪9 0 年代初对s v m 的研究取得突破性进展后，s v m 已经成为目前研究的热点但是s v m 支持向量模式分类方法最初是针对二类别的分类而提出的，如何将其有效地推广到多类别分类仍 然是当前支持向量机研究的一个重要内容 、 1 3 2 本文的主要工作安排 本文主要工作和具体内容安排如下： 第一章介绍了支持向量机的发展历史和研究现状，以及本文的主要工作 第二章主要介绍了机器学习与统计学习理论 第三章研究了支持向量机多类分类方法 第四章本章首先介绍了基于凸闭包收缩的最大边缘分类器，该分类器可将近似线性不可分 问题转化为线性可分问题从而避免映射到特征空间而对于非线性可分问题可以通过核思想的利 用转化为特征空间中的线性可分问题并利用闭凸包收缩原理和已有的多分类方法将其推广到多 分类问题并通过数值验证这也是本文的主要工作 3 。j ：鬯j 、- 川- ：。f j ? 论上 鸹。j i高 第五章综述了本文的j r 作，并对今后的j ：作做了展望 4 与：j 、。? 州! i f i f 夸上 筢 t y j 【：jj j ? 定1 7 ? j ，- j 论m 述 第二章机器学习与统计学习理论概述 2 1 机器学习的基本问题 s v m 是2 0 世纪9 0 年代中期，v a p n i k 等人在统计学习理论、v c 维理论、结构风险最小化理 论、核函数理论的基础上研究提出来的一种最新的机器学习算法，它在很多领域都表现出优丁二现 有学习算法的性能从分类的角度来讲，s v m 是一种广义的线性分类器，它是在r o s s e n b l a t t 线性 感知机【3 2 】的基础上，通过引入结构风险最小化原理、核函数理论、最优化理论演变而成的 为了对支持向量机有一个较深层次的理论认识，以及本文将要讨论的支持向量机奠定理论基 础，以下主要参考文献【1 6 】，对机器学习和统计学习理论做一个简述 2 1 1 机器学习的发展历史 机器学习问题的研究历史可以分为四个阶段【2 1 第一阶段：第一个学习机器的创立一r o s e n b l a t t 的感知器( 2 0 世纪6 0 年代) e r o s e n b l a t t 提 出了第一个学习机器的模型，称之为感知器 a 2 1 这标志着人们对学习过程进行数学研究的真正开 始这个阶段的研究工作导致了模式识别这个新学科的诞生，同时还形成了机器学习的一种重要 方法一判别函数法 第二阶段：学习理论基础的创立( 2 0 世纪6 0 年代一7 0 年代) 在这段时间内理论分析学派 完成了模式识别学习理论和经验风险最小化归纳推理的分析 第三阶段：神经网络的创立( 2 0 世纪8 0 年代) 1 9 8 6 年，研究者提出了同时构造感知器所有 神经元的向量系数的方法，即后向传播的方法这一方法的思想是很简单的，在修改的模型中，新 的神经元的合成是一个连续函数，利用计算神经元的系统梯度，人们可以应用任何基于梯度的方法 来构造对期望函数的逼近后向传播技术的提出是感知器的一次飞跃，这时的感知器也被称为神经 网络神经网络在很多实际应用中也取得了很好的效果然而，所得到的理论成果并没有对一般的 学习理论带来多大的贡献在神经网络学习中。并没有发现新的有意义的现象 第四阶段：统计学习理论( 2 0 世纪9 0 年代) 由于神经网络等现有的机器学习方法的共同理 论基础之一是传统统计学，传统统计学研究的是样本数目趋于无限大时的渐进理论。但在实际问题 中，样本数往往是有限的，与传统统计学相比，统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y 或s l t ) 是 一种专门研究小样本情况下机器学习规律的理论该理论针对小样本统计问题建立了一套新的理 论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息 的条件下得到最优结果v a p n i k 等人从六、七十年代开始致力于统计学习理论( 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 ) 的研究，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习 方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视 2 1 1 机器学习问题概述 学习问题的目的是根据给定的训练样本求输入输出量之间的依赖关系的估计，使它能够对未 知的或无法预测的输出量做出尽可能准确的预测，即遵循某一未知的联合概率分布f ( z ，可) ，( z 和 5 j ：幔j 、；j “rf 。；二f i 仑乏鸹t ； l w 。1 j j ? j j 铳：卜：j 川! i 分_ 生述 ! ，) 之间的确定性关系可以看作是特例) ，学习问题就是就是根据1 1 个独立同分布观测样本 ( x l ，耖1 ) ，( x 2 ，耽) ，( z 。，y n ) ( 2 1 ) 在一组函数，( z ，u ) 中求一个最优的函数( x ，蜘) 对输入输出变量之间的依赖关系进行估计，使期 望风险 r ( u ) = 工( ，( z ，u ) ) d f ( z ，耖) ( 2 2 ) 最小，其中，( z ，u ) 称作预测函数集，u 为函数的广义参数，( z ，u ) 可以表示任何函数集： l ( y ，( x ，u ) ) 为由于，( z ，u ) 对y 进行预测的损失，不同类型的学习问题有不同形式的损失函 数预测函数也称作学 - - 1 函数学习模型或者学习机器由上可知，学习问题的基本模型是： 图2 1 机器学习问题的基本模型图 输出y 预测输出y 在模型中，输出变量y 是训练系统根据输入变量z 得到的，预测变量y 是机器学习后得到的学 习的目标就是使预测变量y 尽可能的接近输出变量y 学习问题的形式化表述涉及面很广，它包括了很多特殊的问题最基本的机器学习问题有三 类：模式识别( 分类) 、函数逼近( 回归估计) 和概率密度估计 1 模式识别问题 模式识别即分类问题，系统的输出为类别标号在两类情况下，令训练样本中输出可只取 两种值y = + l ，- t ，并令，( z ，u ) ，u a 为指示函数集，考虑损失函数：当y = ， ，u ) 时， l ( y ，( 2 ，u ) ) = 1 ：当y ，仕，u ) 时，l ( y ， ，u ) ) = 一1 对上述损失函数，式( 2 1 1 ) 的泛函确定 了训练器和指示函数( x ，u ) 所给出的值不同的概率通常把指示函数给出的值与训练器输出不 同的情况f l q 做分类误差因此，对模式识别问题来说，学习问题就是在概率测度f ( z ，) 未知，但训 练样本集已知的情况下，寻找使分类误差的概率最小的函数 2 回归函数估计问题 同归函数估计问题即函数逼近问题，训练器的输出剪为实数值，并令( x ，u ) ，u a 为实函数 集合回归函数就是在损失函数( 妙，忙，u ) ) = ( y 一，陋，u ) ) 2 下使风险泛函最小的函数这样，回 归估计的问题就是在概率测度f ( 2 ，甜) 未知，但训练样本集已知的情况下，寻找使得风险泛函最小 的密度函数 3 概率密度估计问题 概率密度估计问题就是从密度函数集p ( z ，u ) ，u a 中估计密度函数的问题考虑损失函数 三( 可，( z ，u ) ) = 一l o g p ( x ，u ) ，待求的密度函数就是在损失函数下使风险泛函最小化因此从训练 6 样本集估计密度函数的问题就是，在相应的概率测度f ( 2 ) 未知，但给出了独立同分布数据的情况 下，使风险泛函最小化 基于数据的机器学习问题主要研究如何在已有观测数据的基础上去找到某些规律，并能够利 用这些规律对未知数据已经无法进行观测的数据进行预测，就其实现方法而言，大致可以分为三 种。第一种是经典的参数统计估计方法：第二种是经验非线性方法，例如入工神经网络；第三种即 是后面要介绍的统计学习理论 统计学习理论是专门研究小样本情况下机器学习问题的理论统计学习理论所提出的结构风 险最小化归纳原理包括了学习过程的一致性、边界的理论和结构风险最小化原理等部分，结构风 险最小化学习过程克服了经验风险最小化的缺点，在实际问题上获得了更为良好的效果以下就该 理论的主要内容进行介绍 2 2 统计学习理论的基本内容 统计学习理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则 不仅考虑了对渐近性能的要求而且追求在现有有限信息的条件下得到最优结果在这些条件下 关于统计学习方法推广性界的结论在这些界的基础上建立的小样本归纳推理规则以及实现新的 准则的实现方法( 算法) 2 1 1 学习一致性条件 所谓学习一致性是指当训练样本数趋于无穷大时，经验风险的最优值能收敛到真实风险的最 优值对于有界的损失函数。学习过程一致性充分必要条件是经验风险在以卜意义上一致收敛于真 实风险： 1 i mp s u p ( r ( w ) 一r 。m p ( u ) ) ) = o ，讫 0 t 。o 。 u a 其中p 表示概率，经验风险和期望风险都是预测函数的函数，通过求使经验风险最小化的函数来 逼近能够使期望风险最小化的函数统计学习理论定义了一些指标来衡量函数的性能，其中最重 要的是v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 2 1 1v c 维 为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性 能的指标，其中最重要的是v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 分类( 模式识别) 方法中v c 维的直观定义是：对一个指示函数集，如果存在z 个样本能够被函数集中的函数按所有可能的2 种形式分开，则称函数集能够把z 个样本打散；函数集的v c 维就是它能打散的最大样本数目z 若 对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大有界实函数的v c 维可以 通过用一定的闭值将它转化成指示函数来定义 学习的目标就是使期望风险函数最小r ( o j ) 最小，但因为 ，( 2 ，u ) ) 和f ( ylz ) 未知，因此一 7 般由经验风险函数r e m p ) 代替风险函数冗( u ) ， 见神) = 詈妻地州刊) ( 2 3 ) 在早期的机器学习中，人们总是把注意力集中在如何使冗。m p ( u ) 更小，但很快发现，一味追求 训练误差小并不是总能达到好的预测效果人们将学习机对未来输出进行正确预测的能力称作推 广性某些情况下，当训练误差过小反而会导致推广能力的下降，这就是所谓的”过学习”问题例 如函数集 ，( z ，u ) = s i i l ( u z ) ，u r ) ，对于任意的一组训练样本( 霉，耖) ，z r ，y 【0 ，l 】总存 在一个u 使经验损失为零但这个”最优函数”不能正确代表原来的函数模型出现这种现象的原 网是 l j 一个复杂的模型去拟合有限的样本，结果丧失了推广能力。这就是有限样本下学习机复杂 度和推广性之间的矛盾针对有限样本下学习机这一矛盾，v a p n i k 和c h e r v o n e n k i s 提出了度量函 数类的丰富性和适应性的参数v c 维，函数集的v c 维越大，函数的学习能力越强，相应的推j “性 却不一定好针对两分类问题，v a p n i k 提出了下列不等式为v c 维的分析提供了依据1 3 5 , 4 0 p r ( u ) s 皿唧( u ) + q ( 去) ) 1 叶 ( 2 4 ) q ( 去) = 其中叩( 0 ，1 】，h 为指示函数集 ，( x ，u ) ，u a ) 的v c 维 由式( 2 4 ) 可知，样本数据和函数集v c 维h 对实际风险r ( u ) 的影响可分三种情况； ( 1 ) 样本数目z 同定 此时，如果函数集的v c 维很大，那么对样本的分类能力很高，这时r 。m 口将很小，甚至为零， 而q ( 圭) 将很大，即冗。m p ) 的置信区间很大，实际的风险r ( u ) 不会小，即对新样本的分类能力很 低相反，当h 的值很小时，经验风险将很大，这时r ) 也不会小 因此。v c 维过大或过小都不能使学习机推，“性能高，必须设计一种学习器，在样本数目一定 的情况下，使其v c 维有适当的大小，以保证r ) 值达到最小 ( 2 ) v c 维h 固定 此时，相当于学习机器是给定的，而且进一步假设它对给定训练样本的正确分类能力高，即经 验风险磁m p ) 随着样本数目z 的增大始终保持很小，甚至为零。那么，当f 增大时，q ( 去) 减 小，从而实际风险r ) 小的可能性变大，即学 - - j 机器的推广能力提高：当f 减小时，q ( 丢) 变大，从 而实际风险r ( q ) 小的可能性变小，即推广能力降低所以，一般情况下，训练样本的增多能提高学 习机器的性能，直观上这是因为训练样本为机器提供的信息多了 0 ， 若轨= 1 ， i ( u t 戤+ 的 1 时，1 一矗 0 ，样本娩可能被错分，所以 & ( 3 1 0 ) 是被错分样本数的一个上界如图3 2 所示，图中两条虚线的方程为u t z + b = - t - 1 ，中间的实线 图3 2 非线性可分情形示意图 就是分界线u t z + 6 = 0 虽然每类有两个点落在两虚线之间，但它们没有越过分界线，即满足 0 。t 霉+ b l 或一l u t 茁+ b 0 ，因而相应的0 & 1 因此式e 的值大 于错分样本数4 ，即式( 3 1 0 ) 是s v m 中被错分样本点的一个上界 3 1 4 非线性支持向量机 上一节我们讨论了最简单的线性支持向量机，即在原空间直接建立一个超平面作为分界面， 显然这只有在给定样本集线性或几乎线性可分时才能得到较好的结果而实际上许多分类问题很 复杂，用简单的超平面根本无法达到分类的目的，必须以复杂的超曲面作为分界面在这一节将要 1 3 讨论的1 线性支持向量机就是通过一个邗线性映射将低维空间中的竹线性分类问题转化为高维 h i l b e r t 空间( 特征空间) 中的线性分类问题在这个高维的空间用前面的方法建立一个分类超平面， 从而在原空间建立一个分类超曲面 首先引入一个非线性映射，圣r d 一衄把数据从原空间r d 映射到更高维的特征空间 使得 数据在上是线性或几乎线性可分，如图3 3 所示 图3 3通过一个映射把原始宅间上的非线性可分问题转化为特征空间上的线性可分问题 例3 1 ：设原空间r 2 中有两类数据点以圆周( x l 1 ) 2 + ( z 2 2 ) 2 = 9 为分界面，引入映射 垂r 2 _ = 舻 圣c z ，= 圣( ：) = ( 蓁i ) ：垒( 兰) ， 则在r 2 中的圆周分界面变为中的超平面：一2 z l 一4 2 2 + z 3 + z 4 = 4 原空间r d 上的样本集 ( 霸，肌) ，i = l ，2 ，) 映射到特征空间h 上的新样本集 ( 西( 舰) ，执) ，i = 1 ，2 ， ，对该新样本集利用线性s v m 在h 上建立一个超平面，我们不 需要重新推导，而只要把上一节的推导公式中出现的z 或x i 全部用圣( 2 ) 或圣( 戤) 代替即可所 以非线性s v m 在上建立了如下超平面，亦即在原空间掣上建立一个超平面 其中 u r 圣( z ) + b = 0 ， 1 4 zi e i 玑 q 汹 = u fm a x 羹啦一三薹薹口t 玑蜘西c z t ，t 圣c q ， s l 0 q i c ，i = l ，2 ，n ， ( 3 1 1 ) 分类判决函数 ，( z ) = r 圣( 茁) + 6 = q t 犰圣( z t ) t 圣( z ) + b ( 3 1 2 ) = 1 从上面的公式中看出西( z ) 总是以内积的形式圣( z ) t v ( y ) 出现，所以在计算时可以把它们 作整体处理，即引进核函数惫( 茁，y ) = 圣( z ) r 圣( 可) ，这样在整个计算过程中，只需在原空间上计算 后( z ，y ) 而根本不用在特征空间上进行任何计算实际上我们也不必去考虑映射圣是如何构造的， 而只要找一个核函数奄( z ，爹) 使得它可以写成同一个函数的内积形式 核函数定义【叫：核是一个函数k ，这个函数对于所有的z ，可x ，满足 靶( 刃，可) = ( 圣( z ) ，圣( 矽) ) 二元函数k 即被称为核函数由于在输入空间中，衡量两个特征向量之间内在联系的标准为内积 运算，因此，在特征空间，也可以将内积运算的这种作用转嫁到特征空间中来，即也可以用内积运算 来计算特征空间中两个映像之间的距离或者相似度量但是由于圣( 2 ) 的复杂性，在特征空间直接 计算两个映像之间的内积内积是行不通的，核函数的构造试图将计算特征空间中两个映像之间的 内积转化为计算核函数七的函数值，这样就可以使得计算特征空间中的内积只与输入空间中的变 量有关，而与特征空间的维数无关，大大减少了计算复杂性 3 1 5m e r c e r 定理及m e r c e r 核 m e r c e r 定理通常用来有效的构造一个特征空间，同时m e r c e r 定理给出了一个连续实值对称 函数为核函数的充要条件 设输入集合为r d 中的紧集x ，其中xcr d ，并且设七仕，z ) 是xxx 上的连续对称函数， 即七( 茁，z ) = 后( z 7 ，z ) ，v x ，z x 定理3 1 【3 3 】 若对称核函数k ( x ，y ) 满足 是( 2 ，寥) z ( 2 ) z ) d z d 影20 ， 其中名( z ) 为任意满足 z 2 ( z ) 血锄 1 5 o i | 弘 q 谢 的函数，则k ( x ，y ) 可以写成内积形式 下面列出几种常用的核函数， ( 1 ) p 阶多项式核函数： k ( x ，y ) = ( z r y ) p 或 k ( x ，y ) = ( x t y + 1 ) p ( 2 ) 径向基( r b f ) 核函数： k ( x ，y ) = e x p ( 一i | z 一耖0 2 7 2 ) ( 3 ) s i g m o i d 核函数： k ( x ，y ) = t a n h ( x r y 一秒) 核方法是支持向量机解决非线性分类问题的核心内容，采用适当的核函数就可以实现某一非 线性变换后的线性分类，而计算复杂度并没有增加，这一特点为算法可能导致的”维数灾难“问题 提供了解决方法：在构造判别函数时，不是对输入空间的样本作非线性变换，而后再在特征空间中 求解；而是先在输入空间比较向量( 例如求点积或是某种距离) ，然后再对结果作非线性变换，这样 大的工作量将在输入空间而不是在高维特征空间中完成 3 2 支持向量机的训练算法 由于s v m 方法较好的理论基础和它在一些领域的应用中表现出来的优秀的推广性能近年来， 许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆续提了出来尽管s v m 算法的性能在许多实际问题的应用中得到了验证，但是算法在计算上存在着一些问题，包括训练算 法速度慢、算法复杂而难以实现以及检测阶段运算量大等等 传统利用标准二次型优化技术解决对偶问题的方法可能是i j i l 练算法慢的主要原因：首先， s v m 方法需要计算和存储核函数矩阵，当样本点数目较大时，需要很大的内存，例如，当样本点数 目等于6 0 0 0 时( 这在实际应用中很常见，二阶矩阵的元数个数为3 6 亿，一般计算机的内存根本不 够；其次，s v m 在二次型寻优过程中要进行大量的矩阵运算，而且对大规模的矩阵进行数值计算不 稳定，计算速度也慢，很难达到实际应用中的一些要求 s v m 方法的训练运算速度是限制它的应用的主要方面，为了很好的解决s v m 的训练问题， 已经发展了好几种算法来克服遇到的困难，从而能更好的对s v m 进行训练 3 2 1 块算法 块算法【5 l 是最早提出的优化算法，其思路是：删除核函数矩阵中对应于l a g r a n g e 乘子为0 的 行和列，不会对最终结果产生影响对于给定的训练样本数据集，如果支持向量已知，寻优算法就可 以丢弃非支持向量，只需对支持向量计算l a g r a n g e 乘子即可但在训练过程结束之前，支持向量未 知，因此，块算法的目标就是通过某种迭代方式，逐步丢弃非支持向量 块算法实现方法是： 1 6 给定训练样本集s ，并初始化所有的l