（应用数学专业论文）黎曼流形上的学习理论—在线分类和多核算法.pdf

黎曼流形上的学习理论一在线分类和多核算法 摘要 随着现代科学技术的发展，人们每天都要面对大量数据。如何去理解和处理这 些数据并有效地加以利用成了当今科学技术的一个重要研究课题。 机器学习是计算机得以广泛应用后逐渐发展起来的- - f - 学科，它是研究如何利 用已有的经验数据设计一些算法使计算机具有一些学习功能即从经验数据中学习 出一些规律。学习理论是其中的一个分支，它的目标是给机器学习中的一些算法提 供理论支持并由此设计一些更有效的算法。本文主要分析两类算法一在线分类算 法和多核算法。特别地，本文的分析适用于流形学习( 即所给的数据或所研究的函 数关系分布在一个低维流形上) ，欧氏空间的情形只是其中的一个特例。 首先，我们研究了一类更符合实际操作的全在线分类算法。它是一种可以表达 为再生核希尔伯特空间中泛函极小化问题的在线算法，其包含的损失函数满足凸 性。该算法的一个重要特征是正则化参数随着时间的变化而变化，因此跟以前正则 化参数固定的半在线算法有很大不同。对于该算法的误差分析，我们先用一个新方 法来估计由正贝0 化参数变化而产生的漂移误差，然后在再生核希尔伯特空间中估计 样本误差的强收敛阶。最后，对应于几个特殊的损失函数，我们结合关于额外分类 误差和额外泛化误差的比较定理以及关于正则化误差的衰减性假设得到该算法对应 的额外误差估计。特别地，我们给出了对应于叮范数的支持向量损失函数( q 1 ) 的全在线支持向量机的收敛阶。损失函数是凸的这一假设在我们的分析中起着十分 重要的作用。我们的结果对在线算法给出了坚实的理论基础，是除最小二乘回归算 法外第一个完整的全在线分类算法的理论分析。它不仅为更广的学习算法提出了理 论问题，而且对设计更有用的算法提供了数学上的理论指导。 从2 0 0 0 年开始，流形学习逐步成了学习理论中的一个热门话题。它的核心思 想是假设数据及函数关系分布在一个嵌入到n 维欧氏空间的d 维子流形上，一般 地，d 比n 小很多。但已有文献的大多数研究是实验性的，即通过大量数据的算法 应用说明流形结构对算法的影响。一般是用数值结果说明实际数据及所学函数关系 中有很强的流形结构，这些结构可以大大提高算法的收敛性和降低算法复杂性。但 到现在为止，只有个位数的文章有较严格的数学分析。因此如何在数学上严格证明 流形结构对学习算法的本质影响成了一个公认的，困难丽又意义重大的研究课题。 本文，我们给出了定义在连通紧致c 一黎曼流形上高斯函数的逼近和学习能力。当 被逼函数属于l i p ( s ) 时，方差为盯的高斯函数卷积被逼函数有d ( 矿) 的一致逼近 阶；而当被逼函数属于s o b o l e v 空间明( x ) 时，方差为a 的高斯函数卷积被逼函 数在l p ( x ) 意义下有d ( 矿) 的收敛阶。其中，紧黎曼流形中的一致凸邻域在得到相 应逼近阶过程中起着十分关键的作用。利用这些结果，我们得出了学习理论中一些 多核算法的收敛阶( 包括回归和分类) ，这些收敛阶比欧氏空间情形下( 即输入空间 只是作为欧氏空间的子集，不利用流形的特殊结构) 给出的收敛阶好很多，从而有 力地说明了多核算法在实际应用中的有效性。另外，通过比较逼近阶，我们说明了 单核算法和多核算法的本质区别。我们的数学分析严格地说明了黎曼流形的维数对 多核高斯学习算法的本质影响，是少见的理论分析之一，有着重大的理论及应用前 景。 关键词：学习理论，再生核希尔伯特空间，分类算法，回归算法，在线学习，高斯 核，逼近，黎曼流形 中图分类号：0 2 9 ，0 1 7 4 4 1 ，0 2 3 5 l e a r n i n go nr i e m a n n i a nm a n i f o l d ：o n l i n e c l a s s i f i c a t i o na n dm u i t i - k e r n e l a l g o r i t h m s a b s t r a c t w i t ht h ed e v e l o p m e n to fm o d e r ns c i e n c ea n dt e c h n o l o g y , w ea r ec o n f r o n t e dw i t ha m a s so fd a t ae v e r yd a y h o wt ou n d e r s t a n da n dd e a lw i t ht h e s ed a t aa n dt h e nm a k eu s e o ft h e m b e c o m ea ni m p o r t a n tr e s e a r c ht o p i ci nm o d e r ns c i e n c ea n dt e c h n o l o g y m a c h i n el e a r n i n gi sas u b j e c td e v e l o p i n gr a p i d l ys i n c ec o m p u t e r sa r ew i d e l yu s e d i t s m a i no b j e c ti 8t ou s et h ee m p i r i c a ld a t at od e s i g ns o m ee f f e c t i v ea l g o r i t h i n sa n de n a b l e c o m p u t e r st oh a v el e a r n i n ga b i l i t y , t h a ti s ，w ew a n tc o m p u t e r st ol e a r ns o m el a w sf r o m e m p i r i c a ld a t a l e a r n i n gt h e o r yi sab r a n c ho fm a c h i n el e a r n i n ga n df o c u s e so ns e a r c h i n g f o rt h e o r e t i c a lf o u n d a t i o n sf o rm a c h i n el e a r n i n ga l g o r i t h m sa n dt h e nd e s i g n i n gs o m em o r e e f f e c t i v ea l g o r i t h m s i nt h i st h e s i sw ef o c u so nt w ok i n d so fa l g o r i t h m s - - o n l i n ec l a s s i f i c a - t i o na l g o r i t h m sa n dm u l t i - k e r n e la l g o r i t h m s i np a r t i c u l a r o u ra n a l y s i si 8a d a p t a b l et o m a n i f o l dl e a r n i n g ( i e s t u d yo ff u n c t i o nr e l a t i o n so rs t r u c t u r e so nd a t al y i n gi nm a n i f o l d s e m b e d d e di nh t l g ed i m e n s i o n a le u c l i d e a ns p a c e s ) a n dt h ee u c l i d e a ns p a c es e t t i n gi so n l y as p e c i a lc a 8 e f i r s t l y , w ec o n s i d e rf u l l yo n l i n el e a r n i n ga l g o r i t h m sf o rc l a s s i f i c a t i o ng e n e r a t e df r o m t i k h o n o vr e g n l a r i z a t i o ns c h e m e sa s s o c i a t e dw i t hg e n e r a lc o n v e xl o s sf u n c t i o n sa n dr e - p r o d u c i n gk e r n e lh i l b e r ts p a c e s f o rs u c haf u l l yo n l i n ea l g o r i t h m ，t h er e g n l a r i z a t i o n p a r a m e t e ri ne a c hl e a r n i n gs t e pc h a n g e sa n di ti sm o r ef e a s i b l ei np r a c t i c e b u tt h i sr a i s e s a ne s s e n t i a ld i f f e r e n c ef r o mt h ep a r t i a l l yo n l i n ea l g o r i t h mw h i c hu s e saf i x e dr e g u l a r i z a t i o n p a r a m e t e r w ef i r s tp r e s e n tan o v e la p p r o a c ht ot h ed r i f te r r o ri n c u r r e db yt h ec h a n g e o ft h er e g n l a r i z a t i o np a r a m e t e r t h e nw ee s t i m a t et h ee r r o ro ft h el e a r n i n gp r o c e s sf o r t h es t r o n ga p p r o x i m a t i o ni nt h er e p r o d u c i n gk e r n e lh i l b e r ts p a c e f i n a l l y , l e a r n i n gr a t e s a r ed e r i v e df r o md e c a y so ft h er e g u k u i z a t i o ne r r o r t h ec o n v e x i t yo ft h el o s sf u n c t i o n p l a y sa ni m p o r t a n tr o l e i no u ra n a l y s i s c o n c r e t el e a r n i n gr a t e sa r eg i v e nf o rt h eh i n g e l o s sa n dt h es u p p o r tv e c t o rm a c h i n eq - n o r ml o s s o u rr e s u l t sg i v eas o l i dt h e o r e t i c a lb a s i s f o ro n l i n ea l g o r i t h ma n di ti st h ef r s tc o m p l e t et h e o r e t i c a la n a l y s i so i lf u l l yo n l i n ec l a s s i - f i c a t i o na l g o r i t h m sb e s i d e st h el e a s t - s q u a r er e g r e s s i o na l g o r i t h m i tn o to n l yr a j b e s8 0 m e i i i t h e o r e t i c a lp r o b l e m so nl e a r n i n gt h e o r y , b u ta l s op r o v i d e st h e o r e t i c a lg u i d e l i n et od e s i g n m o r ee f f e c t i v ea l g o r i t h n m m a n i f o l dl e a r n i n gh a sb e e nah o tt o p i ci nl e a r n i n gt h e o r ys i n c e2 0 0 0 i t sk e yp o i n t i st oa s s u m et h a tf u n c t i o nr e l a t i o n so rs t r u c t u r e so fd a t al i eo nm a n i f o l d se m b e d d e di n h u g ed i m e n s i o n a le u c l i d e a ns p a c e s i ng e n e r a l ，t h ed i m e n s i o no ft h em a n i f o l di sm u c hl e s s t h a nt h a to ft h eu n d e r l y i n ge u c l i d e a ns p a c e t h e r ea r eh u n d r e d so fp a p e r so nm a n i f o l d l e a r n i n g ，b u tm o s to ft h e ma r ec u t - a n d - t r y , t h a ti s ，t h e yw a n tt oe x p l a i nh o wm a n i f o l d s t r u c t u r em a k e se f f e c t so na l g o r i t h m sb ye x p e r i m e n t st h r o u g hd a t a b u tt h er e a ls c i e n t i f i c g o a ls h o u l db et h ed e s i r et os h o wt h a tt h em a n i f o l ds t r u c t u r ec a l lg r e a t l yi m p r o v et h e l e a r n i n gr a t e sa n dd e d u c et h ec o m p l e x i t yo ft h ea l g o r i t h m u n t i ln o wt h e r ea r en o tm o r e t h a nt e np a p e r st h a th a v es t r i c tm a t h e m a t i b a la n a l y s i st a r g e t i n gt h i sg o a l h o wt og i v e as o l i dm a t h e m a t i c a la n a l y s i so nt h ei n f l u e n c eo ft h em a n i f o l ds t r u c t u r eo na l g o r i t h m s b e c o m e sa no p e n ，d i f f i c u l ta n dv a l u a b l er e s e a r c ht o p i c i nt h i st h e s i sw es t u d yt h ea p p r o x i m a t i o na n dl e a r n i n gb yg a u s s i a n so ff u n c t i o n s d e f i n e do nad - d i m e n s i o n a lc o n n e c t e dc o m p a c tc r i e m a n n i a ns u b m a n i f o l do f pw h i c h i si s o m e t r i c a l l yi m b e d d e d w es h o wt h a tt h ec o n v o l u t i o nw i t ht h eg a u s s i a nk e r n e lw i t h v a r i a n c e 口p r o v i d e st h eu n i f o r ma p p r o x i m a t i o no r d e ro fd ( 矿) w h e nt h ea p p r o x i m a t e d f u n c t i o ni sl i p s c h i t zs ( 0 ，1 】a n dt h a to f0 ( 盯2 ) u n d e r 妒) n o r mw h e nt h ea p p r e x - i m a t e df u n c t i o ni si nt h es o b o l e vs p a c e 研僻) t h eu n i f o r mn o r m a ln e i g h b o r h o o d so f ac o m p a c tr i e m a n n i a nm a n i f o l dp l a yac e n t r a lr o l e i nd e r i v i n gt h ea p p r o x i m a t i o no r d e r t h i sa p p r o x i m a t i o nr e s u l ti su s e dt oi n v e s t i g a t et h er e g r e s s i o na n dc l a s s i f i c a t i o nl e a r n i n g a l g o r i t h m sg e n e r a t e db yt h em u l t i - k e r n e lr e g u l a r i z a t i o ns c h e m ea s s o c i a t e dw i t hg a u s s i a n k e r u e l sw i t hf l e x i b l ev a r i a n c e s 、) l ，h e nt h em a n i f o l dd i m e n s i o ndi ss m a l l e rt h a nt h ed i m e n - s i o nno f t h eu n d e r l y i n ge u c l i d e a ns p a c e ，o u rl e a r n i n gr a t ei sm u c hb e t t e rc o m p a r e dw i t h t h o s ei nt h el i t e r a t u r e b yc o m p a r i n ga p p r o x i m a t i o no r d e r s ，w ea l s os h o wt h ee s s e n t i a l d i f f e r e n c eb e t w e e na p p r o x i m a t i o ns c h e m e sw i t hf i e x i b l ev a r i a n c e sa n dt h o s ew i t has i n g l e v a r i a n c e i tv e r i f i e st h ee f f i c i e n c yo ft h em u l t i - k e r n e la l g o r i t h m si np r a c t i c e o u rm a t h e - m a t i c a la n a l y s i si so n eo fv e r yf e wt h e o r e t i c a lr e s u l t si nm a n i f o l dl e a r n i n ga n ds h o w st h e e s s e n t i a le f f e c to ft h ed i m e n s i o no ft h em a n i f o l do nm u l t i - k e r n e la l g o r i t h m s i to w e si t s o w ng r e a tt h e o r e t i c a la n da p p l i c a b l ef o r e g r o u n d 1 v k e y w o r d s ：l e a r n i n gt h e o r y , e r r o ra n a l y s i s ，r e p r o d u c i n gk e r n e lh i l b e r ts p a c e s ，c l a s s i - f i c a t i o na l g o r i t h m ，r e g r e s s i o na l g o r i t h m ，o n l i n el e a r n i n g ，g a u s s i a nk e r n e l s ，a p p r o x i m a - t i o n ，r i e m a n n i a nm a n i f o l d s c h i n e s el i b r a r yc l a s s i f i c a t i o n ：0 2 9 ，0 1 7 4 4 1 ，0 2 3 5 v 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他人或其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 作者签名：! 土焦丝日期：绷：i ：垒 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件允许论文被查阅和借阋：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 作者签名：进撞丝导师签名翘：趔丛 第一章绪论 1 1 监督性学习介绍 随着计算机科学的日新月异和应用范围的不断拓展，人们每天都得面对大量无 法直接理解的数据。如何利用计算机来帮助我们理解和处理数据信息成了当今科学 技术的一个重要研究课题。 机器学习是计算机得以广泛应用后逐渐发展起来的- - 1 7 学科，它研究如何利用 已有的经验数据设计一些算法使计算机具有学习功能即从经验数据中学习出规律 性的东西，同时随着经验数据的增多，学习的性能会越来越好。由于不同领域会产 生不同类型的数据，因此它是一个多领域的交叉学科，涵盖应用数学、计算数学、统 计学、计算机科学、神经生物学、基因科学、认知科学、信息论等。 本文研究的问题都属于监督性学习，它主要是从一组给定的样本点 ( 轨) 揍。 中学习回归函数或分类器。若一个算法的目标是学习回归函数，我们称此算法为回 归算法，若是分类器，则称该算法为分类算法 1 ，3 7 ，6 9 】 1 1 1 回归问题 关于回归问题的研究可以追溯到用于线性回归的最小二乘法。下面我们举一个 例子来说明什么是回归问题并引出学习理论中回归问题的数学模型。 例1 1 用数据拟合的方法来学习一个物理规律假设一个物理规律可以用一个函数 ，：r 班来表示，并且该函数有特殊的形式允( 茁) = 墨1 毗如( 。) ，这里也( z ) ， = 1 ，是事先给定的一组函数，它可以是多项式组，三角函数组等等，而桃，i = 1 是需要从经验数据中去学习的参数另外我们知道一组经验数据 ( ，玑) ，圣1 如果测量是精确的，则经验数据应满足，慨) = 玑， = 1 r 一般说来，数据讹是 有误差的，因此我们可以最小化 t n ( 儿 ) 一们) 2 ，这里厶( 彳) = 姚也( 。) t = l ；l 来学习参数撕， 1 ，这里，t 此算法就是典型的最小二乘回归算法，它最早可以追溯到高斯和l e g e n d r e ，利 用数值线性代数的知识，该算法可以快速有效地得到解答。 1 第一章绪论 许多实际问题如金融工程、生物工程等的输入数据戤也是随机的，它也可以 根据一个概率分布产生。另外，给定的函数空间也不定有参数表示形式。 在学习理论中，我们通常假设数据 涵，雏) 圣l 是根据定义在z = x y 上 一个波莱尔联合概率分布p 独立选取的。其中x 是一个紧度量空间( 在很多情况 下，x 是欧氏空