（模式识别与智能系统专业论文）核函数的性质、方法及其在障碍检测中的应用.pdf

里堕型堂丝查叁主竺壅生! 塞堂生笙苎 摘要 近几年来，基于统计学习理论的支持向量机的研究逐渐成为机器学习领域中一 个重要的方向。核函数方法正是在支持向量机的研究中提出并逐步得到发展的一种 构造非线性变换的方法。由于核函数的好坏直接影响着支持向量机的性能，因此有 关核函数的研究也就成为大家关注的焦点，成为支持向量机研究中需要解决的核心 问题之一。 本文内容分为理论研究和实践应用两个部分。 在理论部分，主要分析研究了核函数的性质、核函数的选择、核函数的构造等 三个方面。 支持向量机引入核函数的目的是为了解决线性不可分样本的分类问题。然而并 不是所有的核函数都能使线性不可分的样本变得线性可分。本文给出了核函数使样 本线性可分的充要条件，并进一步给出了一个具有可操作性的充分条件。在此基础 上不仅证明了高斯核函数能够通过选择半径参数实现对任意给定样本的线性划分， 还给出了一种通用的核函数改造方法。用该方法改造后的核函数能够将训练样本线 性分丌。 给定训练样本后，选择什么样的核函数将直接影响所构造的支持向量机的性能。 本文分别针对模式分类和函数逼近两类问题，给出了对核函数参数进行选择的简便 方法。 本文在核函数的构造方法上进行了初步探索，给出了一种基于离散数据插值的 核函数构造方法。 在实践应用部分，本文利用核函数方法，改造了现有的单类判别方法，荠结合 双日视觉技术中的重投影方法，实现了单、双目信息的有效融合，研制了一个自然 场景下的障碍检测实验演示系统。 关键词：统计学习，支持向量机，核函数，模式识别，障碍检测，讨算机视觉 第1 页 国防科学技术火学研究生院学位论文 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 s ( s v m s ) ，b a s e do nt h e s t a t i s t i c a ll e a r n i n gt h e o r y ( s t l ) ， h a v eb e c o m et h ei m p o r t a n tf i e l do fm a c h i n el e a r n i n gr e c e n t l y k e r n e l ，w h i c hi sp r o p o s e d a n dd e v e l o p e di nt h es t u d yo fs v m s ，i san e ww a yo fc o n s t r u c t i n gn o n l i n e a rm a p g o o d k e r n e l sm e a ng o o ds v m s ，s ot h es t u d yo fk e r n e lf u n c t i o n si so n eo ft h ef o c u s e si nt h e r e s e a r c ho ns v m s t h e r ea r et w o p a r t si nt h et h e s i s ：t h et h e o r e t i c a lp a r ta n d t h ea p p l i e dp a r t i nt h et h e o r e t i c a lp a r t ，t h et h e s i sf o c u s e so nt h ef o l l o w i n gt h r e ei s s u e s ： t h es e p a r a b i l i t yo fk e r n e l s k e r n e l sa r ei n t r o d u c e di n t os v m sf o rc l a s s i f y i n gt h e n o n l i n e a rs e p a r a t e dd a t a ，b u tn o ta l lo fk e r n e l sc a nd oi t t h i st h e s i sp r e s e n t sas u f f i c i e n t a n dn e c e s s a r yc o n d i t i o nt oj u d g ei fak e r n e lc a nd oi t a n o t h e ro p e r a t i o n a ls u f f i c i e n t c o n d i t i o ni sa l s op r e s e n t e d b a s e do i lt h i ss u f f i c i e n tc o n d i t i o n ，ag a u s s i a nk e r n e li sp r o v e d t ob es e p a r a b l ef o ra n yg i v e nd a t aw i t has u i t a b l er a d i u sp a r a m e t e rc h o s e n f u r t h e r m o r e a g e n e r a lm e t h o d t oc o n s t r u c ts e p a r a b l ek e r n e l sf o rt h eg i v e nd a t ai sp r e s e n t e d t h es e l e c t i o no fk e r n e l s t h ep r o p e r t i e so fs v m sw i l lb ed e c i d e db yk e r n e l si f t h et r a i nd a t aa r e g i v e n t h i s t h e s i s p r e s e n t s t w o s i m p l em e t h o d st o s e l e c tk e r n e l s p a r a m e t e r s f o rc l a s s i f i c a t i o np r o b l e m sa n d r e g r e s s i o np r o b l e m sr e s p e c t i v e l y t h ec o n s t r u c t i o no fk e r n e l s t h et h e s i sp r e s e n t san e wm e t h o dt oc o n s t r u c ta k e r n e lb a s e do ni n t e r p o l a t i o no fs c a t t e r e dd a t a ，t h ec o n s t r u c t e dk e r n e lh a st h ea d v a n t a g e o fm o r e g e n e r a l i z a t i o na n dl e s ss u b j e c t i v i t y i nt h ea p p l i e dp a r t ，k e r n e lm e t h o di su s e dt o i m p r o v et h em e t h o do fc l a s s i f i c a t i o n w i t ho n ec l a s s t r a i n i n g d a t a t h e i m p r o v e dm e t h o d i sc o m b i n e dw i t h g r o u n dp l a n e t r a n s f o r m a t i o nm e t h o d s ot h a ti n f o r m a t i o nf r o mm o n o c u l a rv i s i o na n ds t e r ov i s i o nc a nb e f u s e de f f e c t i v e l y b a s e do nt h i s ，ad e m o s y s t e mo fo b s t a c l ed e t e c t i n gi no u t d o o rs c e n e si s d e v e l o p e d k e yw o r d s 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 u p p o r t v e c t o r m a c h i n e ，k e r n e l ，p a t t e r n r e c o g n i t i o n ，o b s t a c l ed e t e c t i o n ，c o m p u t e r v i s i o n 第1 i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 趑鱼塾塑性厦：友洼丛基奎睦堡拴型主鲍应用 v- j ， 学位论文作者签名：叁! 堑日期：2 o 口j 年乡月2 - 0 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：趑鱼数曲性厦：直洼区基垄睦堡拴型史的廑旦 学位论文作者签名 作者指导教师签名 关c 寿 驾! ! 坐 日期：加d ；年弓月如日 日期：弘”罗年，月上一日 国防科学技术火学研究生院学位论文 第一章绪论：核函数方法的研究背景 统计学习理论与支持向量机介绍 核函数的定义和使用，并非源自机器学习问题本身。但是核函数作为一种方法 提出，则与统计学习理论( s t a t i s t i c a ll e a r n i n g ，s l ) 和以此为基础的支持向量机 ( s u p p o n v e c t o rm a c h i n e s ，s v m s ) 的研究与发展密不可分。核函数的许多性质f 是 在支持向量机的研究中被不断发现并得以推广应用。现在，核函数方法在特征变换 的表示和构造，非线性问题的线性化方面正起着越来越重要的作用。 本章简要介绍了核函数方法的研究背景：统计学习理论和支持向量机。重点介 绍了统计学习和支持向量机的核心思想以及研究的主要内容。最后介绍了论文的研 究内容、组织结构和主要贡献。 1 1 统计学习理论概要 人的智慧中一个很重要的方面是从实例学习的能力，通过对已知事实的分析总 结出规律，预测不能直接观测的事实。在这种学习中，重要的是能够举一反三，即 利用学习得到的规律，不但可以较好地解释已知的事例，而且能够对未来的现象做 出正确的预测和判断。这就是我们所说的学习的推广n e 7 3 ( 泛化能力) 。 在人工智能研究中，我们希望机器也能具有上面所况的推广能力。它决定了机 器学习能否真正走向实用。在这方面，统计学起着基础性的作用。但是传统的统计 学所研究的主要是渐进理沦，即当样本趋向于无穷多时的统计性质。在现实的问题 中，我们所面对的样本数目通常是有限的，有时还十分有限。但人们推导各种学习 算法时，仍以样本数无穷多为假设，以为( 希望) 这样得到的算法在样本较少时也能有 较好的f 至少是可接受的) 表现。但事实并非如此神经网络中的过学习现象可以说 就是一个典型的代表。 统计学习理论虽说也是利用统计学的方法，但是它的许多结论都是结合有限样 本情况下学习系统的特性分析做出的，因而它已经成为研究有限样本情况下机器学 习问题的主要工具。统计学习理论目前已经取得的一些基本理论成果包括：经验风 险最小化准则( e x p e r i e n c er i s km i n i m i z a t i o n ，e r m ) f 学习一致性的条件；在这些 条件f ，经验川硷o j 实际风险之间的关系，即推广性的界；在这些界的基础_ i i 建立 的小样本p 纳推理准则，支持向量机是其中的主要代表：实现该准则的实际：疗法， h f j 支持向量机中的备科，镎法。本节主要介绍前两个方面的内容。这些介绍夫部分墩 材自文献【1 1 。 第l 页 蓬麓辩学技术犬学骚究生筏学谯论交 1 , 1 1 统计学习瑷论中学习波题的裘零 机器学习的目的，是根据给焱的枷缘撵本，储计系统输入输融之浏的一种依赖 关系，特别楚鼹毅的输入，能够镦遣尽硪能准确懿预测。在统计学习中，挺竣入变 鸶x 和输溺交量y 钓依赖蔻系看作是某一未知的联合概攀f ( x ，岁) ( x 和y 之间的确 定性关系可以嚣 苫蹙萁特铡) ，予魁瓿器学习翘题，裁是投掇雎个独立慰分毒麓鼹溅 礴本 瓴，y ；) ，( x 2 ，y ：) ，( 茂，y 。)( 1 1 ) 在一组函数集 ，( 算，瑾) 。苣 中求个最优的函数f ( x ，a 。) 对依赖关系进千亍估计，缆得 期颦撼险 r ( c o * 弘 对y 避霞联溅露逡或瓣损失拣度量爨数。不弱类 型的损失液量，对应蕾不嗣豹学习阀题。统计学习所研究，主薅楚下面三类简颓： 穰式分类、交数潺遥窝摄搴密度估计。 模式分类( 两类判潮) 令输密交萋j ，只取嚣嵇蕊：岁= 0 鸯，并令f ( x ，掰x 拱a 为撩示函数集合( 瓣只 餐0 葶珏t 两静取落的函数) 。损失函数可以定义为： 妁，f ( x , a 沪 ：黑篙 。， 这撑学习目题裁成了在酸枣测度f ( x ，y ) 未知，孛羹爨所绘谢练撵本，寻找分类错 误概率最小的涵数。 函数逼近 令输 蟊变量y 为实数往，并令f ( x ，搿) ，搿a 为实函数集合e 损失函数可以定义 为： l ( y ，f ( x ，髓) ) * ( y f ( x ，许) ) 2( 1 4 ) 戏者 l ( y ，f ( x ，联) ) = l y f ( x ，搿) ( 1 5 ) 等多种形式。采弼不丽的形式，可以得粼不疑意义下豹娥谯潼近。不过支持崮璧枫 求解函数逼远闷题对采厨的损失溺数有搿予以上酾任藩一种。县俸采臻俺秘度餐， 其实与我们对误麓的估计鄹认识水平有癣甥联系。 密发信诗( f i s h e r 。w a l d 表示) 此时学习的斟灼楚根摄训缘样本确定x 的概率窿发。考虑扶密艘函数熊 p ( x ，群) ，搿a 串佑诗密袋螽数。镄失函数可以定义为： l ( p ( x ，d ) ) = 一l o g p ( x ，靠)( 1 6 ) 第2 页 国防科学技术人学研究生院学位论文 1 1 2e r m 原则与举习过稷的一致性条件 为了在来麓静分勺遵数g ( x ，y ) + f 最夺纯( 1 2 ) 中豁风陵泛溺，遥常我们鄂粟稻f 面的归纳原则：用训练样本( 1 1 ) 定义经验风险 ，乙，( 群。) = 三( y ，( 簟，口。) ) ( i 7 ) n 篇 爆使经验域险最小款函数寒遥远使( 1 。2 ) 中定义豹实际飚除最小的f ( x ，岛) 。这一 原则就是我们熟称的经验风险最小化归纳原则，简称e r m 原则。 e r m 原则在学习过程中超羞j 繁重要的 乍鼹。魄如函数逼近润题中，如果采弱 f 1 4 ) 所定义的风险函数，那么经验风险就变为平方训练误差，最4 - - 乘法就成为e r m 原则的直接作用结果；在密度估计中，采用( 1 。6 ) 式定义的损失函数，e r m 准则就会 等价予最大似然估计 1 j 。 然而，经验风险毕竟不等同于实际风险。因此我们不能根据经验风险爨小化必 然推出实际飙险最小。神经翻络中的过学习现象就缎能说明这个问题。统计学习理 论首先要解决的问题就是：对于一个使经验风险最小的学习过程，它在什么时候能 够墩得小静实际诫险，就是e r m 学习过程静致性条件。更f ”格的致槛羽定义如 卜： 定义1 1 设f ( x ，g 。( 撵) ) 怒对”个独立阐分奄诩练样本( 1 1 ) ，健经验撤陵泛豳( 1 7 ) 最小化的函数1 。如果下面两个序列依概率收敛于同个极限，即： l i m r ( c z8 ( 牲) ) 2 一i n f r )( 1 8 ) l i m r e m p ( 瞍( n ) ) 止一碴r 缸) ( 1 9 ) 则e r m 原则( 或方法) 对函数集f ( x ，口) ，口a 和概率分布f ( x ，y ) 是一致的。 i 。1 3统嚣攀习理论豹三个攫程碡 有了e r m 原! i ! 【l 致性的概念，按踵而柬的问题是：什么时候e r m 原则具有一 致性? 什么时候经验风陵能够快速鲍收敛到实际飙险：在什么情况下，这种快速的 收敛速度能够不依赖于问题本身，即与概率测度无关。对这三个问题的回答，就是 。f 面孝簪要介缁的统计学习理论中三个器程碑。 定义1 2 ( v c 熵) 设a l ( x ，y ，d ) b ，口a 是一个有界损失函数的集台。浚函数 集帚吲练洋率集f l l 可以聿句造下西酌h 维向鬣集合： q ( 甜) ；( l ( x i ，y i ，口) ，。，l ( x y 儿，口) ) ，删a( 1 1 0 ) 配n 。( ； ，y ；) ，( 戈。y 。) ) 是离篷集合q ) ，甜a 在c 度量( 或0 度篮) 卜j 最 小s 网格的元素数目。当f 充分小时，它是穹s 无关的量。目p “0 1 ) 最小蚀始验风险髓一1 、的函数所对应的参数t 它j 佯奎的个数n 竹关t 所以这啦皑n ；成t l 娈鼢的肜，。 第3 页 国防科学技术火学研究生院学位论文 n “( s ；( z 1 ，y 1 ) ，一，( x 。，y 。) ) 一“( ( 工l ，y 1 ) ，( x 。_ ) 。) ) 僵它是关予谢练谨本( 1 i ) 艇一个黢毒莛交慧。我们鼹 “( 盯) = e i n n “( “，y 1 ) ，瓴，y 。) )( 1 1 1 ) 为函数集a l ( x ，y ，口) s b ，g a 在数量必挣载样本上懿v c 嫡。 定义1 3 ( 退火的v c 熵) 嚣纛( 嚣) = i n e n “( ( 茗t ，y 1 ) ，( 苁，y 。势 s ；# 一1 其中c 0 ，为某个常数。 3 当l i r a o a ( n _ _ 2 。o 时，采用e r m 原则的学习过程所得到的经验风险能够不依 月_ 2 疗 赖于概率测凄麴快速兹收敛到实际娥除。 1 1 4容量控制与结构风险最小化( s r m ) 原则 上面所述的三个缩论意嘛着：函数集结构越简单，函数集容量越小，小的经验 风险就越能保证小的实际风险。那是不是选择的函数集越简单越好，或者笼缆地晓， 函数袋的容量越少越好昵? 事实并菲如此。太简单的函数集可能使我们无法得到较 小的经验风险。那就更谈不上取得较小的实际风险了。所以这里有个容量控制的 阔题。但是怒不是控翻好函数集豹容鬟，藏躲决了搿有 1 蠢瑟滗? 其实瞧不楚。为了 进一1 步说明经验风险、实际风险和函数集容爨三者恻的关系，这罩还需要引入v c 缝( v a p n i k c h e r v o n e n k i s d i m e n s i o n ) 静概念。 事实上，v c 维与我们6 u 面介绍的生长函数之间有重要的联系。它是由v a p n i k 鞫c h e r v o n e n k i s 奁1 9 6 8 年发现滤。 定理1 i t l 任何生长函数，它或糟满足等式 第4 页 国防科学技术人学研究生院学位论文 g “( ，1 ) ；n l n 2 ， 或者受下蕊的不等式约柬： g “( n ) s 向( 1 n + ” ，z 蒸中h 楚一令整数，谩缮当n = h 时，有 g “( ) 一h i n 2 ， g “( 矗+ 1 ) 矗+ 1 ) l n 2 定义1 5 如果指示函数槊的生长函数是线性的，则该函数集的v c 维是涎穷大： 如巢，主长函数以参数为h 的对数函数为界，捌该指示溺数集的v c 维是有限的且等于 h 。 在模式识翁中，v c 维豹囊蕊定义是：对一个摇冢函数集，如栗存在h 个样本能 够被函数集中的函数按所有可能的2 “种形式分丌，则称函数集能够把h 个样本打散； 函数集鼢v c 维就凳它麓打敬靛最大群本数强h 。若对任意数蟊的祥本都有酗数能褥 它们打散，则函数集的v c 维是无穷大。有界实函数的v c 维可以通过用一定的闽值 貉它转仡戏臻示函数束定义。 v c 维也是一个袭征函数集容量的参数。它与经验风险r ) 和实际风险r ) 之阁斡关系楚：对指示番数榘中嚣掰育函数( 包括矮经验蝇轮最小弱豳数) ，经验诫浚 尺。 ) 和实际风险擞 ) 之间以至少1 一叩( 0 吁 0 胰j r 成 k ( x ，y ) = y 吼( 工) ( y ) c 即( z ，y ) 描述了某个特征空1 1 = j j 中的一个内积) 的充分必要条件是：对使缁 第9 页 国骑辩学技术入学辑究生麓学谴论文 阽2 ( x ) d x 。c 的所有函数g 0 ，条件 俨晦y ) g ( x ) g ( y ) d x d y ，。( 1 3 0 ) 成立。 这里的条件3 0 ) 就是我们熟称的m e r c e r 条件。 引入核融数后，求鳃特征空闽中的聚佐( 广义) 超平嚣的数学援划形式栽变为 了： m a x w ( 搿卜m 。a x 静一言磊t z i y y j k ( 伪( 1 3 1 ) 0 s a is c ，i = 毛- - - , n 满足约束条件： 妻y ，a 。：o 最后得到的非线性决策函数变为： ，( 工) = s g n ( ( 咒搿一k ( x i ，x ) ) - b 8 ) ( 1 3 2 ) 可以麓到：引入核函数后，求解算法并没有产生实质性的变化。与线性可分时 阏蘧熬求鼹确篦，唯一翡变 乞羲是建楚籍到自量淘羧( 置x ，或慧并茗：) 懿圭龟方，全 部都用k ( x l ，x ，)k ( x ，x ，) 柬代替。 支持向量机的最后实观形式非常类似一个三层6 h 向神经网络( 如1 3 图所示) 。 1 2 3 核函数方法 输m ( 决麓舰 l i 】j ) 户酗班( 较值毗一晖咒 丛干s 个上特：；j ：x i ，x 2 ，鼻。 的1 i 线一h 娈换( 内私! ) 燃1 3 芷持| 趣机示意鳖( 披c lc l 】) 绘定禁令孩蘧热女( 并，工) ，裁定义了一个翱应瓣h i l b e r 空秘，熏投影竣h i l b e r 空 1 、日j ( r e p r o d u c i n g k e r n e l h i l b e r ts p a c e ，r k h s ) 。该空问中的基本元素是一些连续函数。 第l o 页 幽防科譬：技术人学研究生院学位论文 这数连续函数具有如下形式： 珏 ，积) ：鳓) 一艺口。露z ) ( i 3 3 ) l箭l 可以证明，( 1 3 3 ) 所定义雏函数空闯是一个h i l b e r t 空闼。其实它也没鸯传么特 别之处，与我们平时常用的l ，空间相比，它是由些更加光滑的函数构成的。在这 个空恒j 中，骶个元素( 函数) 的内积定义鳃下： c ，g = a 。声产( 一，工，) ( 1 3 4 ) f 蘑滔重投影( r e p r o d u c i n g ) ，是指该空闻中熬内积鬃有如下性质： i = f ( x ) i i = k ( x ，x ) 酶瑟我翻提到逑，由一个较鏊数可以浮窭某令穗应毂 线瞧变巍。准绥逢澄， 同一个核函数可以对应很多非线性变换，下面的变换是其中之一： 辔：x 呻婚，磅 f 1 3 5 ) 该变换是将输入空蚓中的个元索映入到核函数导出的r k h s 中的一个元索( 连续 函数) 。予麓根据r k h s 的藿投影性质，有： = = k ( x ，y )( 1 3 5 ) 如果要简单地叙述核函数方法( k e r n e lt r i c k ) 的实质，那就是：核函数方法通过 定义籍薤变换磊撵本在特矮空越中瓣内获束实瑷一耱籍，疰变换。宅关心熬是结莱， 而不是实现结果所聚用的具体的方式。 支持囱量撬遥过雩l 入核函数，有效鼹熬决了模式分类中麴线陵不可分阏篷。舔 核函数经过这几年研究和发展，其应用领域也早已不仅限于支持向量机这。单一领 域。事实上，它正逐步成为一耪爨要的，毒孥 线性闯题线性化麴蕊逶方法。比始 s c h b l k o p f 【4 9 】将核晒数方法用于主成分分析( p c a ) ，提出了基于核的主成分分析方法 f k p c a ) ，扶纛垮溅零鼹予线性毒鞋关分掭的p c a 方法扩建到了嚣线性褶关分褥翁镶 域。f r b a c h 等人将核函数方法用于独立元分析( i c a ) ，使得原本用于分解独立信t 。：i l 线性迭加的i c a 方法电可以用于独立信号滟 线性 昆迭( 疆l 】) 。总之，以翦鼹决线睦 问题时的许多技术手段，都可以尝试通过棱函数方法扩展到非线性领域。 2 4 支持自量撬及核蚕数纂秀突的国志锋j 筵震 支持向量机的核心内容基本是在1 9 9 2 年1 9 9 5 年削形成啦。从那以辰，关j 二 支持向量机方面翡文章h 雨后眷笋，渐渐成为霍际 二机器学习领域耨静骈究热点。 我阁虽然早在八十年代术就注意到统计学习理论的些基础性的成果【“，1 _ ! 并没饪 藉l l 页 国防科学技术人学研究生院学位论文 引起怒够重视。国内研究支持向量机的文章激早也到了1 9 9 9 年p 1 。但是这几年笈璇 很快。特别是v v a p n i k 的名罄( ( t h e n a t u r eo fs t a t i s t i c a ll e a r n i n g ) ) 中文版的出版，更 是有力推动了国内这方面的研究。下面我们分别就鏊础理论、算法以及具体应硐三 方面介绍支持向量机的研究逝况。 1 支持向量机蘩础理论研究 核函数对支持向凝机的性能有重露的影口向。所以支持向缀机理论研究主要以核 函数方面的研究为主，包括模黧选择阻及核鹚数的构造。其中模型选择又包括核函 数类型的选择、核函数参数的选择以及支持向量机中的参数( c 值，参见( 1 2 6 ) 式) 匏确定。丽这方面的研究的核心是辩支持向羹视性能的有效评估。关于这方面的研 究情况，我们在第三帮中有专门的介绍。 孩函数托枣驽造跑孩函数豹选择可链会更有意义些。但是构造出一个好的核函 数却很难。目f i i f 核函数的构造方面的成果主隳集中在具有某种特性的，但是是普适 静孩黼数酶秘造上。其中最魏塑酶代表就是s c h 6 | k o p f 等入给出的其有平移和小角 度旋转不变性的核函数的构造方法【5 】。该方法被成功运用到手写体数字识别中，使 褥雳这种接涵数实臻的s v m 分类器超过了一个由专家设计，结合了各静先验翔_ i = 的，复杂的5 层神经网络的汉别水平，从而成为目6 “最好的分类器。此外，针对离 敖数撵麴模式分类蠢遂，j a a k k o l a 霸h a u s s l e r 设计了较豫为f i s h e r 孩函数憝褥遣方 法( 5 3 1 ， 5 4 1 ) 。它是从离散序列的概率模型出发构造的一种描述两个离散序列相似程 凄憝核函数。凌在蓦予f i s h e r 核函数隧及辕应懿改遂壁毂t o p ( t a n g e t i tv e c t o r so f p o s t e r i o r l o g 。o d d s 的缩写) 核函数( k t s u d a ，5 5 1 ) 已成功用于文本分类、语音t 别、d n a 序列以及蛋自餍分类簿各项碜究中，芳取褥了一系列爨色的成果。 支持向量机面世以来，它的优电性质和某些应用领域的优异表现的确让人侧目。 于是一韶分学者就歼始在理谂上深入戮瓠支持囊量搬的钱势：如果溴支砖离羹镌好， 那它到底好在什么地方? 这些研究为我们进一步深入理解支持向量机，了解支持向 量尊l 嗨其它方法之问的联系，起到了积极的作用。比如y il i n 在f 3 3 l 中指出：对于 模式分类问题，支持向量机彳i 是去试图估计样本的密度分市p ( x ) ，而是通过核函数 1 翁方法实褒了怼决蓑滋数s i g n p ( x ) - 皇浆遥远。瑟恁嚣疑时也可以番作是b a y e s 鬃 z 优估计的一个近似。 在讨论支持向萋税与其它方法瀚联系上，核函数起着关键性酶份掰。有狠多成 熟的技术和方法，其实都可阻通过设计相应的核函数i 啊用支持向量机来实现。比如 f | 撺 f 弱 我磁密：当竣函数采震变雾发函数来送行定义时，支持向餐税方法簿 a 手 克力n ( k r i g i n g ) 方法2 ；当核函数用样本问的协方差函数来定义时，s v m 方法等价： 裹赣过程( 一耪蜀予蘧数逗逐靛方法) ；当核函数为t a n h 丞数时，支持稳黧辊又可 第i 2 页 国防科学技术人学研究生院学位论文 以用束实现一个两层神经网络( 【1 ) 。可见，很多看似不同的方法，其实都可以通过 核函数而被纳入到支持向量机的统一框架中。这为我们研究支持向量机的本质，分 析支持向量机的优越性，提供了基础。 2 支持向量机算法研究 支持向量机的算法研究概括起来，六个字：“更小”、“更快”、“更广”。 所谓“更小9 9 是指构造支持向量机所需的内存更小；或者反过来说，利用有限 的内存，处理尽可能多的样本。f 如前面我们介绍中提到的，训练一个支持向量机 本质上是要求解一个二次规划( q p ) 问题。解二次规划问题当然有许多经典的解法， 如积极方集法、对偶方法、内点法等。但是当面临大规模的数据样本( 或称海量数 据) 时，由于内存的限制，太多的训练样本可能导致训练算法根本就无法进行。例 如，当样本点数目超过4 0 0 0 时，存储核函数矩阵需要多达1 2 8 兆内存。为了能有效 处理大量的训练样本，1 9 9 5 年c o r t e s 和v a p n i k 首先提出了分解( c h u n k i n g ) 算法f 8 】。 该算法的主要特点是可将一个大型的二次规划问题分解为一系列较小规模的二次规 划问题。1 9 9 7 年，o s u n a 等人证明【9 | 【”j ：如果每步至少加入一个不满足k u h n t u c k e r 条件的样本，则利用一系列的q p 子问题就可以保证实现收敛。c h u n k i n g 算法就满 足该定理，因此可保证收敛。但是当训练集的支持向量个数非常大时，c h u n k i n g 算 法仍然无法保证能将矩阵完全放入到内存中。1 9 9 8 年，p l a t t 提出了序贯最小优化 ( 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 ) 的s v m 训练算法f “t 。该算法的特点是将 一个大型q p 问题分解为一系列仅是有两个l a g r a n g e 乘子的q p 问题，从而使得原 问题可以通过分析的方法加以解决，避免了在内循环中使用数值算法进行q p 最优 化时所导致的不稳定及耗时问题。 所谓“更快”，顾名思义，就是研究支持向量机的各种新的快速训练算法。以 s m o 为代表的算法是通过将一个大规模的问题分解成若干小规模的子问题实现对 大样本问题的处理。但是子问题的舰模和迭代的次数是一对矛盾，将工作样本集的 规模减少，一个直接的后果就是迭代次数的增加。所以这些算法实际上是将求解子 问题的耗费转嫁到迭代上，然后在迭代上寻求快速算法。在对s m o 作进步的研究 之后，1 9 9 9 年p l a t t 指出，通过核优化方法可以大大提高s m o 的性能【1 2 j 。另一方面， s s k e e r t h i 等通过对算法的分析，在【1 3 1 中提出了重大改进，即在判别最优条件时用 两个闽值代替一个阈值，从而使算法更加合理，速度也更快。这一点在f 1 4 1 中得到了 进一步的理论分析和实际大型测试数据库的证明。这罩需要特别提一下国内的研究 情况。1 9 9 9 年，我因学者张铃和张钹提出采用球面投影函数作为非线性映射，完成 样本点的分类问题m 1 。这jv a p n i k 的思想在本质上是相同的。不同的是，v a p n i k 将分类问题变换为二次舰划的最优解问题，而张铃和张钹则是借助球面覆盛的算法 实现样本的分类。虽然该方法的适用范围不如s v m 广( 至今尚未见到该方法在函数 变异函数f 克，j 恪方法均怂地赝统汁学中的生舞挫术干n 方法，主要用r 函数h 归。 第1 3 页 国防科学技术人学研究生院学位论文 逼近或者密度估计方面的推广) ，但仅对模式分类而言，这种方法在计算量方面却有 很大的优势。张文生等人在此基础上给出的计算支持向量的领域算法，在处理海量 数据的求解方面看来是有效的【l ”。其实他们的方法本质上得到的是一个近似最优超 平面。从这个角度，也不难理解它的速度为什么会远快于经典的s v m 求解算法了。 中科院何清等人提出的用于快速分类的s v m 直接算法，基本上也是这个思想【”1 。 所谓“更广”，是指通过对算法的修改或改进，使支持向量机的应用范围更加广 泛。这些修改主要包括如下三个方面： 一是对目标函数进行适当修改，从而构造出一些具有新的性质的支持向量机， 这些新的支持向量机在解决某些问题时可能具有一些更优良的特性。比如s c h 6 1 k o p f 通过在目标函数中添加了一项关于支持向量个数的约束，得到了一个新的s v m 分类 器v s v m l ”】。它的主要优点是：使用一个参数v 来来直接控制支持向量的个数；相 比经典s v m ，目标函数中少了c ，避免了数值计算的麻烦。j a k s u y k e n s 提出的最 小二乘支持向量机l s s v m 。主要是将优化目标中松弛变量的一次惩罚项改为了二 次。约束条件也变为只有等式约束。这使得支持向量的求解可以通过最小二乘法实 现 1 9 1 。o l v i 等人【2 ( ) l 通过在原目标函数中添加一项b 2 ，使对偶问题多了一项，而少 了一项等式约束。问题转化为边界约束条件下的二次规划问题，适合迭代求解。同 时应用矩阵分解技术，每次只需更新l a g r a n g e 乘子的一个分量，因此无需将每个样 本载入内存，并且提高了收敛速度。传统的支持向量只能用于两类判别。j w e s t o n 通过定义新的目标函数，将多类判别通过解优化问题一次得以实现【“】。计算量过大 是这个方法的致命弱点。还有y il i n 等人在 4 6 1 中还深入分析了非标准情况下，即 训练样本来自不同的分布，误判代价与具体类别有关等情形下支持向量机的修l f 算 法。 另一方面的算法改进是将本来需要一次载入所有训练样本的离线算法改进为序 贯法和在线算法。所谓序贯法，是考虑训练样本序贯加入，同时考虑其对支持向量 的影响。这方面的一个突出应用就是实现机器的主动式学习( a c t i v el e a r n i n g ) 。当 样本序贯进入时，每个样本提供的信息量是不一样的。主动式学爿算法不是被动接 收每个训练样本，而是主动在训练样本中依次挑出有价值的训练样本。这种方法在 文本分类m 2 】和图像搜索【2 3 】中得到了运用。 与序贯方法不同，在线训练算法中对于训练样本的总的个数是未知的。浚算法 的重点在于样本逐个录入时s v m 的实时训练。从学习理论的角度看，递推算法可以 使统计学习具有知识扩充的能力：即已知样本集k ，且对k 已进行过学习，观新增 加样本s ，如何在已学习的基础上进行适当的调整，使惆整后的网络适应1 二样本集 k + s 。从应用角度看，在线训练可以使s v m 用于系统的在线辨u 和实l i , l 控制。不 过这方面的研究成果还不是很多。目前的在线训练算法主要由g e r tc a u w e n b e r g h s 、 s s k e e r t h i 等人给出了 2 3 , 2 4 1 。需要特别指出的是，国内学者张铃在此方面也取得了 第1 4 页 国防科学技术入学错究生院学侮论文 可枣成果。链在 2 5 哮l 绘出弱挚缝形迭饯算法不仅键s v m 矮蚤了知淡扩充麓力，嬲 且其求解过程有