（计算机应用技术专业论文）不同核条件下的支持向量机算法研究及验证.pdf

摘要 摘要 支持向量机是在统计学习理论基础上发展起来的一种新的机器学习方法，具有理论 完备、适应性强、全局优化、训练时间短、泛化性能好等优点，自提出以来，一直受到 人们的关注，已经被广泛应用到模式识别和回归等问题中，其中人脸识别是模式识别问 题中一个非常典型的应用。人脸识别同其他基于生物特征的鉴别方法相比，具有友好， 采样方便，使用者无心理负担等优点，加上现代图像通讯的迫切要求，对人脸识别技术 的研究有着重要的意义。本文主要工作内容如下： 1 ) 支持向量机是目前比较流行的模式识别方法，在解决小样本、非线性及高维模式 识别问题中表现出许多特有的优势。在传统支持向量机中，样本间的相似程度是用内积 来表达和评估的。本文通过对核函数及其参数选择的研究，提出了一种使用距离来衡量 样本间相似性的核方法，该距离选用欧几里德距离。在o r l 、y a l e 、e s s e x 三种不同的 人脸库上的实验结果均表明，基于此核函数的支持向量机算法与其他常用的核函数相比 较，在识别时间并没有增加的情况下，识别率得到了提高。 2 ) 针对人脸类别增多识别率下降较明显的问题，本文引入一种条件正定核。该核函 数不满足m e r c e r 核条件，但是可以用于核方法学习。本文从理论上证明了该核函数比 基于点积的核函数更加有效，同时通过人脸识别实验，进一步说明基于该核函数的支持 向量机算法的可行性和有效性，识别率高于其它核函数。 3 ) 鉴于使用原始人脸图像进行实验所需时间较长，效率较低，论文采用多种不同的 图像处理方法对人脸图像降维，通过实验选取降维效果最好的方法对人脸库中的图片进 行降维处理。对降维后的人脸库进行实验，实验结果进一步验证了本文所引入的两种新 的核函数的有效性。 最后对本文的工作进行了小结，并对后续的研究提出了目标与希望。 关键词：支持向量机；人脸识别；核函数；m e r c e r 核 a b s t r a c t 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 e ，d e v e l o p e do nt h eb a s i so fs t a t i s t i c a ll e a r n i n gt h e o r y , i san e w m a c h i n e l e a r n i n g m e t h o dw i t ht h e a d v a n t a g e o fp e r f e c tt h e o r y , a d a p t a b i l i t y , g l o b a l o p t i m i z a t i o n ，s h o r tt r a i n i n gt i m ea n dg o o dg e n e r a l i z a t i o np e r f o r m a n c e s i n c eb e e np r o p o s e d ， i th a sb e e np a i dm u c ha t t e n t i o na n dh a sb e e nw i d e l ya p p l i e dt ot h ep r o b l e m so fp a t t e m r e c o g n i t i o na n dr e g r e s s i o n ，o fw h i c hf a c er e c o g n i t i o ni so n et y p i c a la p p l i c a t i o n c o m p a r i n gt o o t h e rb i o m e t r i c - b a s e di d e n t i f i c a t i o nm e t h o d s ，i th a sm a n ya d v a n t a g e s ，s u c ha sf r i e n d l y , e a s y s a m p l i n g ，w i t h o u tp s y c h o l o g i c a lb u r d e n , a n ds oo n w h a ti sm o r e ，t h em o d e mi m a g e c o m m u n i c a t i o nr e q u i r e m e n ti sv e r yu r g e n c y ，i ti sv e r yi m p o r t a n tt os t u d yt h ef a c er e c o g n i t i o n t e c h n o l o g y i nt h i sp a p e r ，t h em a i nw o r ki n c l u d e s ： f i r s t l y , s u p p o r tv e c t o rm a c h i n e si s o n ep o p u l a rp a r e mr e c o g n i t i o nm e t h o d i th a sa n u m b e ro fu n i q u ea d v a n t a g e si ns o l v i n gt h es m a l ls a m p l e s ，n o n l i n e a ra n dh i g hd i m e n s i o n a l p a t t e mr e c o g n i t i o np r o b l e m s i nt 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 e s ，i n n e r - p r o d u c ti su s e dt o e v a l u a t et h es i m u l a t i o nb e t w e e ns a m p l e s a f t e rt h ek e r n e lf u n c t i o na n di t sp a r a m e t e ro fs v m a r es t u d i e d ，an e wk e r n e lf u n c t i o nb a s e do ne u c l i d e a nd i s t a n c ei sp r o p o s e d t h ee x c r e m e n t a l r e s u l t so no r l ，y a l e ，e s s e xf a c ed a t a b a s e ss h o wt h a tt h i sk e r n e lf u n c t i o n sc a nc o m p l e t ef a c e r e c o g n i t i o nb e t t e r c o m p a r i n gt oo t h e rk e r n e l s ，i th a sh i g h e rr e c o g n i z i n ga c c u r a c ya n dt h e r e c o g n i z et i m ed o e s n ti n c r e a s e s e c o n d l y , f o ras v mc l a s s i f i e r , k e r n e lf u n c t i o ni st h ek e yf a c t o r ak e r n e lf u n c t i o ni s i n t r o d u c e di nt h i sp a p e r , k n o w na sc o n d i t i o n a l l yp o s i t i v ed e f i n i t ek e r n e l ，w h i c hd o e sn o t s a t i s f yt h em e r c e rc o n d i t i o nb u tc a nb eu s e di nt h es t u d yo fk e r n e lm e t h o d s t h i sk e r n e l f u n c t i o ni sp r o v e nm o r ee f f e c t i v et h a na n yo t h e rk e r n e lf u n c t i o nb a s e do ni n n e r - p r o d u c tb y t h e o r ya n de x p e r i m e n ta t t h es a m et i m e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h i sk e r n e l f u n c t i o nh a sb e t t e rr e s u l t st h a nt h et r a d i t i o n a lk e r n e lf u n c t i o n si nt h ea s p e c to ff a c e r e c o g n i t i o n t h i r d l y , u n d e rt h ef a c tt h a tt h ei d e n t i f yt i m ei sq u i t el o n ga n dt h ee f f i c i e n c yi sq u i t el o w , s e v e r a ld i f f e r e n ti m a g ep r o c e s s i n gm e t h o d si ss e l e c t e dt op r o c e s st h ei m a g e so ft h e s et h r e e f a c ed a t a b a s e s t h ee x p e r i m e n t a lr e s u l t sp r o v et h ee f f e c t i v e n e s so ft h et w on e wk e r n e l f u n c t i o n sa g a i n ，t h e s ei m a g ep r o c e s sm e t h o d sa r ec o m p a r e da tt h es a m et i m e a tl a s t ，t h ew h o l ew o r ko ft h i sp a p e ri ss u m m a r i z e d ，a n dat a r g e ta n dh o p et ot h ef u t u r e r e s e a r c hi sg i v e n k e y w o r d s ：s u p p o r tv e c t o rm a c h i n e s ；f a c er e c o g n i t i o n ；k e r n e lf u n c t i o n ；m e r c e rk e m e l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文申作了明确的说明并表示谢意。 签名： 封鳌 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索j 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 塞! ! 麴。 聪诬日 第一章绪论 第一章绪论 1 1 课题的背景及其意义 支持向量机( s v m ) 是在统计学习理论的基础上发展起来的新一代学习算法，它不 仅克服了维数灾难和局部极小问题，还在处理非线性问题时显示了突出的优越性：第一， 它不同于神经网络等传统方法，以训练误差作为优化问题的约束条件，而以置信范围值 最小化作为优化目标。因此，s v m 的泛化能力要明显优越于神经网络等传统学习方法。 其次，s v m 的求解中最终得到的最优化问题都是凸二次规划，因此，s v m 的解是唯一 的、也是全局最优的，避免了局部最小化问题。第三，在支持向量机中，通过引入核函 数，而无需知道样本信息从原始空间映射到特征空间这一具体的过程。就能够把高维特 征空间中的点积运算转化为低维输入空间的核函数运算，避免了在高维空间中直接计算 的难题，从而很好地解决了“维数灾难 问题。 对于s v m 来说，决定其分类性能的关键因素是它的核函数，选择了一个特定的核函 数也就选择了它从样本空间到特征空间的特定映射。不同的核函数有不同的特点，由它 们构成的s v m 的性能也有所差别。当选择一种核函数后，也就选定了一种学习模型， 而一个学习模型性能的好坏是由学习能力和推广能力即对未知样本的预测能力两方面 决定的。 然而，目前在s v m 的学习中，对s v m 的核函数及其参数的选择仍没有形成一个 统一的模式。s v m 算法参数选择还只能是凭借经验、实验对比、大范围搜索或者利用 交叉验证功能进行寻优。而现有的核函数各自都有优缺点，因此作者希望能够找到一种 综合性能较好的核函数。 1 2 课题研究现状 近年来，以v a p n i k 的支持向量机为代表的统计学习理论专门研究小样本情况下的机 器学习规律，它采用结构风险最小化准则，在最小化经验风险的同时最小化推广误差的 上界，并采用凸二次规划技术使所求问题的解具有全局最优性。s v m 不仅能保证在小 样本条件下仍具有较好的推广性，而且基本消除了“维数灾难 、“过学习 和“欠学习 等传统机器学习方法难以解决的问题，在复杂系统的建模、优化、分类与预测等方面显 示出强大的优势。这些优势使得s v m 理论成为当前学术界研究的热点问题，受到普遍 关注和重视。但是，s v m 在应用中存在着两个突出的问题，即s v m 核函数的选择和 s v m 用于多类问题的学习算法设计。此外，在实际应用中很难获得高质量、大规模的 数据样本，数据样本中或包含不完整数据、或样本数很少、或蕴含模式多样性的情况。 如何充分利用有限数据样本和不完整数据样本中包含的有限信息，构造高精度的s v m 分类器是一个有待深入研究的问题。 江南大学硕士学位论文 1 3 本文的研究内容及结构安排 1 3 1 研究内容 支持向量机以其结构风险最小化等优势而被广泛应用到模式识别、回归【2 】【3 】等领域 中。在模式识别领域，语音识别、虹膜识别、指纹识别等，都已用于商业应用。而人脸 的机器自动识别是一种直接、友好、方便、容易被人民接受的非侵犯性识别方法，具有 非常广泛的应用范围，在许多领域都有着广阔的应用前景。 支持向量机最初是用来解决二类分类问题的，但在实际应用中大多是多类分类问 题，因此一对一、一对多、决策树等策略相继被提出来，用以解决多类分类问题。另外， 在现实分类问题中，大多数情况下样本都是非线性可分的，而解决非线性问题支持向量 机最核心的部分就是核函数。鉴于支持向量机本身的特点，针对人脸识别这类小样本、 多类分类问题，为提高人脸识别的识别率、减少识别时间，本文在以下几个方面对支持 向量机及其人脸识别应用进行了研究和探索： 第一，在传统支持向量机中，样本间的相似程度是用内积来评估的。本文通过对核 函数及其参数选择的研究，提出了一种使用距离来衡量样本间相似性的核方法，该距离 选用欧几里德距离。在o r l 、y a l e 、e s s e x 三种不同的人脸库上的实验结果均表明，基 于此核函数的支持向量机算法与其他常用的核函数相比较，在识别时问并没有增加的情 况下，识别率得到了提高。 第二，针对人脸类别增多识别率下降较明显的问题，本文引入一种条件正定核，该 核函数不满足m e r c e r 核条件，但是可以用于核方法学习。本文从理论上证明了该核函 数比基于点积的核函数更加有效，同时通过人脸识别实验，进一步说明了基于该核函数 的支持向量机算法的可行性和有效性，识别率高于其它核函数。 第三，由于使用原始图片识别周期较长，而且原始图片中也有很多不必要的信息， 因此，分别对图片进行直接降维、d c t 变换、p c a 特征提取和小波变换四种方法进行 处理，通过实验选取降维效果最好的方法对人脸库中的图片进行降维处理。对降维后的 人脸库进行实验，实验结果进一步验证了本文所引入的两种新的核函数的有效性。 1 3 2 论文的结构安排 论文共分六章。第一章为绪论，对课题提出的背景、意义，课题研究状况以及主要 研究内容作了一个综合阐述；第二章为理论知识的介绍，主要介绍了支持向量机方法和 人脸识别的相关理论知识；第三章对支持向量机核函数进行分析，提出了一种基于欧几 里德距离的核函数，通过实验将其同常用的核函数进行比较，得出该核函数在处理人脸 识别问题上同其他核函数相比具有一定的优势；第四章在已有核函数类别增多时下降明 显的基础上引入了另一种基于距离的核函数条件正定核，通过实验证明了该核函数的 有效性和鲁棒性；第五章首先介绍了关于图像处理方面的相关理论知识，对几种不同的 图像降维方法进行比较，选出一种较好的降维方法对人脸库中的图片进行处理，对降维 处理后的人脸图像用基于不同核函数的支持向量机算法进行识别实验，进一步验证本文 算法的有效性；第六章对全文的研究工作进行总结，对未来的研究工作进行展望。 2 第二章理论知识介绍 第二章理论知识介绍 2 1 统计学习理论 模式分类是模式识别中的一项重要内容，也是处理其他许多问题的核心1 4 j 。传统的 模式分类方法如b a y e s i a n 方法、f i s h e r 判断等，主要基于统计分析理论，他们一般需要 事先知道样本的先验分布，并要求有足够多的样本数据，这些要求在实际应用中往往难 以达到，因此分类效果往往不够理想。近年来被广泛应用的人工神经网络方法在发展过 程中也遇到了困难，如结构不容易确定、容易陷入局部极小等固有的缺陷，从而限制了 其实际应用。在神经网络的实际应用中还会出现过学习问题，这是因为在传统学习方 法中采用的经验风险最小化准贝u ( e r m ) 虽然可以使训练误差最小化，但并不能最小化学 习过程的泛化误差。为此，v a p n i k 提出了统计学习理论( s 【5 】，它基于结构风险最小化 准贝o ( s r m ) ，在最小化样本点误差的同时，缩小模型泛化误差的上界，即最小化模型的 结构风险，从而提高模型的泛化能力，通俗地说就是通过对推广误差( 风险) 上界的最小 化达到最大的泛化能力。在这些理论的基础上，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 ) 学习算法。它的基本思想是在样本空间或特征空间，构造出最优 超平面，使得超平面与不同类样本集之间的距离最大，从而达到最大的泛化能力。支持 向量机不仅克服了维数灾难和局部极小问题，并在处理非线性问题时显示了突出的优越 性。它不同于神经网络等传统方法以训练误差最小化作为优化目标，而是以训练误差作 为优化问题的约束条件，以置信范围值最小化作为优化目标，因此，s v m 的泛化能力 要明显优越于神经网络等传统学习方法。另外，s v m 的求解中最终得到的最优化问题 都是凸二次规划，因此，s v m 的解是唯一的、也是全局最优的，避免了局部最小化问 题。鉴于支持向量机种种优点，近年来，s v m 得到了广泛的重视，已经成功应用于多 个领域。 2 1 1 机器学习的基本问题 统计学在解决机器学习问题中起着基础性的作用【6 】【7 】。但是，传统统计学主要是在 样本数目趋于无穷多的前提下进行研究的，是一种渐进性理论，所提出的各种方法只有 在样本数趋于无穷大时其性能才有理论上的保证。现有的学习方法，如贝叶斯决策理论、 人工神经网络等也是基于此假设。但是在现实的问题中，样本数目通常是有限的，虽然 人们已经意识到这一点，但传统上仍以样本数目无穷多为假设来推导各种算法，希望这 样得到的算法在样本较少时也能有较好的表现。结果一些理论上很优秀的学习方法在实 际中的表现却不尽人意。 与传统统计学相比，统计学习理论( s l t ) 【8 】【9 】【1 0 1 是一门专门研究小样本情况下机器学 习规律的理论。它建立在一套坚实的理论基础之上，为解决有限样本学习问题提供了一 个统一的框架。它可以将很多现有的方法纳入其中，而且可以帮助解决许多原来都难以 解决的问题，如神经网络结构选择问题，局部极小点问题等。在这个理论基础之上同时 3 江南大学硕士学位论文 也发展了一种新的模式识别方法一支持向量机。 1 问题的表示 机器学习的目的是根据给定的训练样本求出对系统输入输出之间依赖关系的估计， 使它能够对未知样本的输出做出尽可能准确的预测。通过定义风险函数( 也称期望风险) 对学习效果进行评估【l 】。假设变量x 和y 遵循某一未知的联合概率p ( x ，y ) ，l 为给定的损 失函数，再求出一个最优的决策函数刷，f ：x ( xcr ”) 专y = 一1 ，l ，那么假设俐 的期望风险即为 r e f 2j r 。y 三( z ，y ，f ( x ) ) d p ( x ，j ，) ， ( 2 1 ) 从期望风险的定义可以看出，决策函数删的期望风险依赖于概率分布和损失函数。 期望风险的大小可以理解为，当用假设删进行预测时，“平均 的损失程度，或“平均 犯错误的程度。对于不同类型的学习问题有不同形式的损失函数。 机器学习有三类基本的问题：模式识别、回归函数估计、概率密度估计。对模式识 别问题，令训练器的输出y 只取两种值，尸 0 ，1 ) ，预测函数即指示函数，损失函数可以 定义为： 坳讹咖 苗主矧， 亿2 ， 使风险最小就是贝叶斯决策中错误率最小。 对回归函数估计而言，y 是连续变量( 这里假设为单值函数) ，损失函数可定义为 z ( y ，f ( x ，川) = ( y f ( x ，w ) ) 2 ， ( 2 3 ) 即采用最小平方误差准则。 对概率密度估计问题，学习的目的是根据训练样本确定x 的概率密度，设估计的密 度函数为p ( x ，w ) ，损失函数可以定义为 l ( p ( x ，们) = - l o g p ( x ，w ) ( 2 4 ) 2 经验风险最小化 学习的目的就是使期望风险最小，而期望风险是依赖于概率分布p 阮纠的，但实际 的分类问题中，概率分布是未知的，只能利用已失n 1 ) j l 练样本的信息，因此期望风险无法 直接计算和进行最小化。为此，在实际应用中，一般根据大数定律即采用算术平均来代 替，使经验风险 1 上 r 唧【门= 亏c ( 而，y ，( 而) ) ( 2 5 ) 达到最小值来代替求期望风险的最小值即为经验风险最小化( e r m ) 准则。事实上， 用e r m 准则代替期望风险最小化并没有经过充分的理论证明，只是直观上合理的想当 然做法，经验风险最小化准则的思想在多年的机器学习方法研究中占据了主导地位。但 e r m 的思想是建立在样本数目m 趋于无穷大的情况，当实际问题中的样本数目是很有 限的个数时，e r m 准则得到的结果却不一定能使得真实风险也较小。起初很多注意力 都集中在使r 。( w ) 更小上，但很快就意识到，训练误差小并不一定导致较好的预测效 4 第二章理论知识介绍 果，某些情况下，训练误差过小反而导致了推广能力的下降，这就是过学习问题。由此 得知，在有限样本的情况下，经验风险最小并不一定意味着期望风险最小，学习机器的 复杂性不但与所研究的系统有关，而且还要同有限数目的样本相适应。 2 1 2 统计学习理论的核心内容 统计学习理论就是研究小样本统计估计和预测的理论，主要内容包括四个方面【5 】： 1 经验风险最小化准则下统计学习一致性的条件； 2 在这些条件下关于统计学习方法推广性的界的结论； 3 在这些界的基础上建立的小样本归纳推理准则； 4 实现新的准则的实际算法。 ( 一) 函数集的v c 维 v c 维被认为是数学和计算机科学中非常重要的定量化概念，它可用来刻画分类系 统的性能。模式识别中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能 够被函数集中的函数按所有可能的2 h 种形式分开，则称函数集能够把h 个样本打散，函 数集的v c 维就是它能打散的最大样本数目h ；若对任意数目的样本都有函数能将它们 打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的阈值将它转 化成指示函数来定义。v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂， 所以v c 维又是学习机器复杂程度的一种衡量。 v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂( 容量越大) 。遗憾的 是，目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些特殊的函数集知道 其v c 维。比如在i 维实数空间中线性分类器和线性实函数的v c 维是刀+ 1 ，对于一些 比较复杂的学习机器( 如神经网络) ，其v c 维除了与函数集( 神经网络结构) 有关外，还受 学习算法等的影响，其确定更加困难对于给定的学习函数集，如何计算其v c 维是当前 统计学习理论中有待研究的一个问题。 ( - - ) 推广性的界 推广性的界【1 1 1 即经验风险和实际风险之间的关系。当假设集，的v c 维有限时，经 验风险最小化归纳原则是有效的。然而通常考虑的问题中样本点个数是有限的，此时仅 仅用经验风险来近似期望风险是行不通的。v a p n i k 等人经过研究，就两分类问题提出如 下结论：对指示函数集( 指示函数即只有0 或l 两种取值的函数) 中的所有函数，经验风险 和实际风险之间以一定的概率满足如下关系： 反1 f 可 r f 】r 甜妒 厂】+ 1 f 号( 办( 1 n - 7 + 1 ) + i n 习 yl 仃 o ， ( 2 6 ) 其中，h 是函数集的v c 维，z 是样本数。v c 维是衡量学习机器复杂程度的一个指 标，v c 维越大，则学习机器越复杂，其定义为：学习机器能够正确划分的任意二值标 识的最大点集样本数，它表征了学习机器的最大学习能力。 由上式右边可见，学习机器的实际风险由两部分组成：一是经验风险即训练误差， 另一部分称为置信范围( c o n f i d e n c ei n t e r v a l ) 。经验风险依赖于厂的选择，而置信区间则 江南大学硕士学位论文 是f 的v c 维日的增函数。在有限训练样本下，机器学习的v c 维越高( 复杂性越高) 则 置信范围就越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现 过学习现象的原因。比如说，对于1 0 0 个训练样本，可以通过设计一个包含1 0 0 个隐层 节点的神经网络将其实现，此时网络的训练误差为最小( 为0 ) 。但是同时网络的复杂度 太高，即v c 维h 太大，因此导致置信范围将会很大，这时虽然经验风险为0 ，但由上 式可知，最终得到的期望风险仍然很大，以至网络的泛化能力很差。机器学习过程不但 要使经验风险最小，还要使v c 维尽量小以缩小置信范围，才能取得较小的实际风险， 即具有较好的推广性。 值得注意的是推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当 v c 维较高时更是如此。而且，这种界只在对同一类学习函数进行比较时有效，在从函 数集选择函数时有指导作用，在不同的函数集之间比较却不一定成立。 ( 三) 结构风险最小化 从上面的论述得知，e r m 准则在样本有限时是不合理的，会产生过学习现象。为 解决此问题，就需要在保证分类精度( h p 减小经验风险) 的同时，降低学习机器的v c 维， 从而使得学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化原则的 基本思想。它的具体思路是构造一组嵌套的函数子集，使其v c 维由内向外依次增加， 然后在该嵌套子集中寻找能使经验风险和置信范围之和最小的子集，从而使得实际风险 上界达至最小化。显然，利用结构风险最小化原则的思想，就可以完美解决神经网络中 的过学习问题。支持向量机方法实际上就是这种思想的具体实现。 实现s r m 原则可以有两种思路，一是在每个子集中求最小经验风险，然后选择使 最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚 至无穷时不可行? 因此有第二种思路，即设计函数集的某种结构使每个子集中都能取得 最小的经验风险( 如使训练误差为0 ) ，然后只需选择适当的子集使置信范围最小，则这 个子集中使经验风险最小的函数就是最优函数。 2 2 支持向量机分类方法 训练样本集假定为，肋) ，i = l ，2 ，n ，其中x ，r 为输入值，y ， 1 , - 1 ) 为对应 的目标值，刀为样本数。学习的目的是构造，酣，使之与目标值之间的距离最小，同时 函数的v c 维最小，这样，对于未知样本，可以最优地估计出对应的目标值。 2 2 1 线性情况 s v m 的基本思想是寻找一个最优分类超平面将两类样本分开，同时兼顾分类间隔的 最大化和误差的最小化。可以用下图来说明。图l 中，星形和圆圈分别代表两类样本。 l o 为分类线，l l ，l 2 分别为过各类中离分类线最近的样本且平行于分类线的直线，它们 之间的距离为分类间隔。 6 第二章理论知识介绍 图2 l两类线性可分情况 f i g 2 - 1l i n e a rc o n d i t i o no f t w oc l a s s e s 最优分类线是指能将两类样本正确的分开，而且使得分类间隔最大的那条分类线。 与此相应的分划直线的表达式为 ( w x ) + 6 = 0 。 ( 2 7 ) 此时相应的两条极端直线的距离为击。假设给定的样本数据集 1 1 w l t = ( z 。，y 。) ，( ，儿) ) ( x xy ) ”为线性时，极大化间隔的思想导致求解下列对变量w 和b 的最优化问题 m i n 钏wi | 2 ， s t ：y f ( w 为+ 6 ) 1 ，f = 1 , 2 ，以。 ( 2 8 ) 在n 维空间中，满足条件m l a 的正则超平面构成的指示函数集( x ，鹕6 ) 的v c 维满足 h m i n ( a 2 ，2 】，忉+ l ，( 2 9 ) 其中，为包络训练样本数据的最小球半径，因此，式( 2 8 ) 的最优化问题中，最小化去忪0 2 意味着最小化v c 维，同时训练误差作为最优化问题的约束条件。上述最优分类线的推 导过程可以自然扩展到多维情况下最有超平面的推导过程。这时l o ，l l ，l 2 变为超平面， 超平面l l ，l 2 上的样本点被称为支持向量( s v ) ，这些点唯一地确定了一个最优的分类面 l o 。 为求解上述优化问题，i ji n l a g r a n g e 乘子口把上述最优分类面问题转化为其w o l f ) 对偶 问题【1 】 m a x i m i z e ：仅i 一9 e e o t f a j y t y j b i 毒x j ) ， i = 1。i = lj = l s t 善y 以= ” 。 ( 2 1 0 ) a f 0 ，f = , - - n 这是一个不等式约束下的二次函数寻优问题，存在唯一解。根据k a r u s h - k u h n - t u c k e r 最优化条件，此最优化问题的解需满足 q ( w 而) + b ) - 1 ) = 0 ，f = 1 ，甩。 ( 2 1 1 ) 7 江南大学硕士学位论文 由上式可以看出，多数样本对应的a ，将为零，取值不为零的仅对应于使上式等号成 立的样本即支持向量，他们通常占相当小的比例。 此时，支持向量机的决策函数为： 厂( x ) = s g n ( w x + 6 ) 。( 2 1 2 ) 当训练集线性不可分时，任何分划超平面都必有错分，如图2 所示的情形： ( 1 ) 图2 - 2两类线性不可分情况 f i g 2 - 2n o n - l i n e a rc o n d i t i o no ft w oc l a s s e s 此时不能再要求所有的训练点满足约束条件y ，( w + 6 ) 1 ，f = 1 , 2 ，”。为此，当 约束条件不可实现时，引入松弛变量量，这样式最优化问题为： m i n 去0 叫1 2 + c 窆参， i = l s t ：y l ( w t + 6 ) 1 ，f = 1 , 2 ，n 。( 2 1 3 ) 其中c o 为惩罚系数，c 越大表示对超出e 管道数据点的惩罚越大。采用拉格朗 日乘子法求解这个具有线性不等式约束的二次规划问题，即 三阮历= 劲叫1 2 + 畦磊一q ( t ) + 6 ) + 磊一1 ) 一层考。 ( 2 1 4 ) i = 1 其中归心，呸，厂，脚孱一缘y 是拉格朗日乘子。此优化问题的k k t 条件为： ， v 。l ( x ，口，) = 0jw = 口j y f 而 f = l ， v 6 l ( x ，口) = 0 专口f = 0 ， i = 1 ( 2 1 5 ) ( 2 1 6 ) v f 三( x ，5 ) = 0 专c 一5 f 一屏= 0 ， ( 2 1 7 ) 将式( 2 1 5 ) ，( 2 1 6 ) ，( 2 1 7 ) 代入式( 2 1 4 ) ，得到对偶最优化问题 m 。i n寺a j y , y j ( x i x ) - 够， 一 i = ij = 1i = i l s 川t 5 f y i = 0 ，0 够c ，= i ，2 ，玎。 ( 2 1 8 ) i = i 根据最优化的充要条件( k k t 条件) 知，在最优点，拉格朗日乘子与约束的乘积为0 ， 因此，最优化得到的口，中，支持向量( s u p p o r tv e c t o r ，s v ) a ，称为支持值。由式( 2 1 5 ) 知，非支持向量( 口，= 0 ) 对w 没有贡献，只有支持向量对w 有贡献，即对估计函数f ( x ) 8 第二章理论知识介绍 有贡献。在支持向量中，对于标准支持向量，如果o o ， ( 2 2 0 ) 可以构造出分划超平面( w x ) + 6 = 0 ，由此求得决策函数为 厂(x)=sgn(wx)+6)。(221) 2 2 2 非线性情况 对于训练集为非线性情况，通过某一非线性函数( x ) 将训练集数据x 映射到一个高 维特征空间，使得样本点在这个高维特征空间中是线性可分的，并在这个维数可能为无 穷大的线性空间中构造决策函数。在上面的对偶问题中可以看到，不论是寻求最优目标 函数还是分类函数都只涉及到样本向量之间的内积运算。假设存在一个函数 x ( x ，x ，) = ( 一) 西 ，) ，这样，高维空间中的内积运算就可以用原空间中的函数实现 了。估计函数俐为如下形式： 厂( 功= w ( x ) + b ， ( 2 2 2 ) 其中w 的维数为特征空间维数( 可能为无穷维) 。最优化问题为 m 时i n x + c 善当 s t 弘一w ( 薯) 一b 磊 磊0 ，i = 1 , 2 ，。( 2 2 3 ) 类似线性情况，得到对偶最优化问题 m i n 去口j y t y ，k ( 一，x j ) - 芝a , i = ij = l i = 1 s t ：口f y j = 0 ， 0 口 c ，i = l ，2 ，n 。 ( 2 2 4 ) 决策函数为 ( x ) = s 印( 口，y ，x ( x ，一) + 6 ) ， ( 2 2 5 ) 其中b 按如下计算 b = 乃一y 1 k ( x j , x j ) 。 ( 2 2 6 ) 由式( 2 2 5 ) 和式( 2 2 6 ) 知，尽管通过非线性函数将样本数据映射到具有高维甚至无穷 维特征空间，但在计算决策函数时并不需要显式计算该非线性函数，而只需计算核函数 【1 2 】【1 3 】【1 4 】【1 5 】【1 6 】【1 7 】【1 8 】，从而避免高维特征空间引起的维数灾难问题。核函数的选择必须满 9 江南大学硕士学位论文 足m e r c e r 条件，目前常见的核函数有：线性函数x ( x ，x ，) = g x ，此种情况下得到 的支持向量机是样本空间种的超平面。多项式函数k ( x ，x ，) = ( ( t ，x ，) + 1 ) d ，此时得到 的支持向量机是一个g 阶多项式分类器。高斯核函数k ( x ，x ，) = e x p ( 一i i x ，- - x | | o 2 ) ， 此时的支持向量机是一个径向基函数分类器，它与传统径向基函数( r b f ) 方法的基本 区别是，这里每一个基函数的中心对应于一个支持向量，它们以及输出权值都是由算法 自动确定的。s 形核函数k ( x ，一) = t a n h ( v ( x ) + c ) ，这时支持向量机实现的是包含一 个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在困扰神经网络 方法的局部极小点问题。 2 2 3 支持向量机方法优点 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理基础上 的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好 的推广能力( g e n e r a l i z a t i o na b i l i t y ) 。 支持向量机方法的几个主要优点有： ( 1 ) 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本 数趋于无穷大时的最优值； ( 2 ) 算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点， 解决了在神经网络方法中无法避免的局部极值问题； ( 3 ) 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) 然后通过在 高维空间中构造线性判别函数来实现原空间中的非线性判别函数，它不但可以训练出有 较好推广能力的机器，而且巧妙地解决了维数问题，其算法复杂度与样本维数无关。 ( 4 ) 最优化计算得到的中，多数满足= o 。也就是说在样本数据中非支持向量占多数， 因此，只需少量样本( 支持向量) 就可构成分类决策函数，使得有用的样本数据大大压缩。 解的稀疏性是s v m 的重要特征之一，使得s v m 在实际问题求解中具有很强的实用性。 2 3 支持向量机研究现状 支持向量机算法一经提出，就得到国内外学者的高度关注。虽然支持向量机发展时 间很短，但是由于它的产生是基于统计学习理论的，因此具有坚实的理论基础【l 。近几 年涌现出的大量理论研究成果，更为其应用研究奠定了坚实基础。如j o h nc p l a t t ( 1 9 9 8 ) 针对求解二次规划问题的计算量和计算复杂度提出了序列最小最优化算法【1 9 1 。a n t h o n y e t a 1 ( 1 9 9 9 ) 等人给除了关于硬邻域支持向量机学习误差的严格理论界限， s h a w e t a y l o r ( 2 0 0 0 ) 和c r i s t i a n i n i ( 2 0 0 0 ) 也给出了类似的关于软邻域支持向量机和回归情 况下的误差界限；w e s t o ne ta 1 ( 1 9 9 8 ) 和v a p n i k ( 1 9 9 5 ，1 9 9 8 ) 等研究了支持向量机的泛化性 能及其在多值分类和回归问题的扩展问题；s m o l a ( 1 9 9 8 ) 和s c h o e l k o p f ( 1 9 9 9 ) 提出了支持 向量机一般意义下的损失函数数字描述：脊回归是由t i k h o n o v 提出的一种具有特殊形 式的正则化网络，g i r o s i ( 1 9 9 0 ) 、p o g g i o ( 1 9 7 5 ) 等将其应用到正则化网络的学习中， s m o l ae t a 1 ( 1 9 9 9 ) 研究了状态空间中脊回归的应用，g i r o s i ( 1 9 9 0 ) 、s m o l a ( 1 9 9 8 ) 、 1 0 第二章理论知识介绍 s c h o e l k o p f ( 1 9 9 9 ) 等讨论了正则化网络和支持向量机的关系。随着支持向量机理论上 深入的研究，出现了许多变种支持向量机，如s m o l ae ta 1 ( 1 9 9 9 ) 提出的用于分类和回 归的v 支持向量机。另外，一些学者还扩展了支持向量机概念，如m a n g a s a r i a n ( 1 9 9 7 ) 等人的通用支持向量机( g e n e r a l i s e ds v m s ) 。 用数值算法进行q p 最优化所导致的不稳定及耗时问题。为了是解决某些问题时可 能具有一些更优良的特性，s c h o l k o p f 通过在目标函数中添加一项关于支持向量个数的 约束，得到了一个新的s v m 分类器v - s v m 1 6 1 。它的主要优点是：使用一个参数f 来直 接控制支持向量的个数，相对于经典s v m ，目标函数中少了c ，避免了数值计算的麻 烦。j a k s u y k e n s 提出的最小二乘支持向量机l s v m ，主要是将优化目标中松弛变量的 一次惩罚项改成了二次，约束条件也变为只有等式约束，这使得支持向量机的求解可以 通过最小二乘法实现【2 0 】。 除了各种算法的出现，关于核函数的研究是支持向量机理论研究的另一个热点，主 要集中在核函数的构造和模型选择上面。核函数的构造可能比核函数的选择更有意义一 些，但是构造一个好的核函数却很难。目前核函数构造的成果主要集中