（计算数学专业论文）基于数据的学习：埃尔米特算法与黎曼流形上的法向量估计.pdf

摘要 摘要 在本文中，我们主要研究学习理论中关于回归，流形学习和数据分析的一 些算法。我们将详细地讨论这些算法的设计，并从逼近论的观点讨论其渐近性 质。 论文的第一部分，在再生核h i l b e r t 空间中最小二乘回归正则化算法的框架 下，我们研究了基于梯度样本数据的学习问题。在表示定理的帮助下，算法的 求解归结为求解个线性方程组，系数矩阵中涉及核函数值的g r a m i a n 矩阵以及 核函数偏导数值的h e s s i a n 矩阵。额外的关于梯度的样本值可以提高算法的学习 性能。通过运用采样算子分析样本误差和s o b o l e v 空间中的积分算子分析逼近误 差，我们给出该算法的误差分析。 法向量估计是处理点云数据以及计算机图形学中曲面重构的重要研究课题。 在论文的第二部分，我们考虑欧式空间中余维为1 的子流形上的法向量估计问 题。由于流形是未知的，我们要利用在流形上随机采样得到的样本点来估计法 向量。我们提出了一种由核函数构造的学习算法，它实际上是无监督形式的梯 度学习。算法的求解归结为求解一个线性代数的特征向量问题。在真实的法向 量和采样分布满足一定的条件时，我们得到了关于该算法的误差估计。 在论文的最后一部分，我们主要讨论样本依赖假设空间中的正则化回归问 题。对于给定的一组样本数据，样本依赖假设空间中的函数定义为由核函数和 样本数据产生的一族基函数的线性组合，因此空间中的函数完全取决于其线 性组合的系数。这种核函数构造的假设空间其依赖样本的特质给学习算法带 来很大的灵活性和自适应性。在这种空问里讨论的正则化算法与传统的再生 核h i l b e r t 空间中的算法有本质的不同：我们所考虑的核函数不是对称的，从而 不具有半正定性，正则化子作为作用在该空间中函数上的泛函，被取为其相应 的组合系数的汐范数的p 次幂。这种不同增加了误差分析的困难。 具体来说，我们主要在本文中研究了两种情况：p = 1 和p = 2 。当p = 1 时， 笆1 正则化子经常会使解向量具有稀疏性，从而极大提高算法运行的效率。 当p = 2 时，相应的算法是线性的并且可以通过一个线性方程组来求解。这两种 算法都已经被一些文献研究过。在本文中，我们利用关于垆经验覆盖数的中心 极限定理得到了学习算法目前为止最好的收敛阶。因为我们的目的是给出一种 容量相关的分析方法，对于在误差分析中出现的由非对称核函数构造的函数空 间，我们给出了其中的单位闭球关于俨经验覆盖数的性质，这在我们的分析中 起了十分关键的作用。 i 摘要 关键词：埃尔米特学习法向量估计流形学习 样本依赖假设空间系数正 则化算法 a b s t r a c t ab s t r a c t i nt h i st h e s i s ，w ei n v e s t i g a t es o m ea l g o r i t h m si nl e a r n i n gt h e o r yf o rp u r p o s eo f r e g r e s s i o n ，m a n i f o l dl e a r n i n ga n dd a t aa n a l y s i s t h e i rd e s i g na n da s y m p t o t i cp e r f o r - m a n e ew i l lb ed i s c u s s e di nd e t a i lf r o mt h ev i e wp o i n to fa p p r o x i m a t i o nt h e o r y i nt h ef i r s tp a r t ，t h ep r o b l e mo fl e a m i n gf r o md a t ai n v o l v i n gf u n c t i o nv a l u e sa n d g r a d i e n t si ss t u d i e di naf r a m e w o r k o fl e a s t s q u a r er e g u l a r i z e dr e g r e s s i o ni nr 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 t h ea l g o r i t h mi si m p l e m e n t e db yal i n e a rs y s t e mw i t ht h e c o e f f i c i e n tm a t r i xi n v o l v i n gb o t hb l o c km a t r i c e sf o rg e n e r a t i n gg r a p hl a p l a c i a n sa n d h e s s i a n s 。t h ea d d i t i o n a ld a t af o rf u n c t i o ng r a d i e n t si m p r o v el e a r n i n gp e r f o r m a n c eo f t h ea l g o r i t h m e r r o ra n a l y s i si sd o n eb ym e a n so fs a m p l i n go p e r a t o r sf o rt h es a m p l e e r r o ra n d i n t e g r a lo p e r a t o r si ns o b o l e vs p a c e sf o rt h ea p p r o x i m a t i o n e r r o r n o r m a le s t i m a t i o ni sa ni m p o r t a n tt o p i cf o rp r o c e s s i n gp o i n tc l o u dd a t aa n ds u r - f a c er e c o n s t r u c t i o ni nc o m p u t e rg r a p h i c s i nt h es e c o n dp a r to ft h et h e s i s ，w ec o n s i d e r t h ep r o b l e mo fe s t i m a t i n gn o r m a l sf o ra ( u n k n o w n ) s u b m a n i f o l do fae u c l i d e a ns p a c e o fc o d i m e n s i o n1f r o mr a n d o mp o i n t so nt h em a n i f o l d w ep r o p o s eak e r n e lb a s e d l e a r n i n ga l g o r i t h mi na nu n s u p e r v i s e df o r mo fg r a d i e n tl e a r n i n g t h ea l g o r i t h m c a nb e i m p l e m e n t e db ys o l v i n ga l i n e a ra l g e b r ap r o b l e m e r r o ra n a l y s i si sc o n d u c t e du n d e r c o n d i t i o n so nt h et r u en o r m a l so ft h em a n i f o l da n dt h es a m p l i n gd i s t r i b u t i o n i nt h el a s tp a r to ft h i st h e s i s ，w ec o n s i d e rt h er e g r e s s i o np r o b l e mb yl e a r n i n gw i t h a r e g u l a r i z a t i o ns c h e m ei na d a t ad e p e n d e n th y p o t h e s i ss p a c e f o rag i v e ns e to fs a n l - p i e s ，f u n c t i o n si nt h i sh y p o t h e s i ss p a c ea r ed e f i n e dt ob el i n e a rc o m b i n a t i o n so fb a s i s f u n c t i o n sg e n e r a t e db yak e r n e lf u n c t i o na n ds a m p l ed a t a ，t h u sa r ee n t i r e l yd e t e r m i n e d b yt h ec o m b i n a t i o nc o e f f i c i e n t s t h ed a t ad e p e n d e n c en a t u r eo ft h e k e r n e l b a s e dh y - p o t h e s i ss p a c ep r o v i d e sf l e x i b i l i t ya n da d a p t i v i t yf o rt h el e a r n i n ga l g o r i t h m s t h er e g u - l a r i z a t i o ns c h e m ei se s s e n t i a l l yd i f f e r e n tf r o mt h es t a n d a r do n ei nar e p r o d u c i n gk e r n e l h i l b e r ts p a c e ：t h ek e r n e lf u n c t i o ni sn o tn e c e s s a r i l ys y m m e t r i co rp o s i t i v es e m i d e f i n i t e a n dt h er e g u l a r i z e r , a saf u n c t i o n a la c t i n go nt h ef u n c t i o n si ns u c hk i n d so fh y p o t h e s i s s p a c e s ，i st a k e n t ob et h ep - t hp o w e ro ft h eg p - n o r mo ft h ec o r r e s p o n d i n gc o m b i n a t i o n c o e f f i c i e n t s t h ed i f f e r e n c e sl e a dt oa d d i t i o n a ld i f f i c u l t yi nt h ee r r o ra n a l y s i s t ob em o r es p e c i f i c w em a i n l ys t u d yt w oc a s e si nt h i st h e s i s ：p = 1a n dp = 2 w h e np = 1 ，t h eg l - r e g u l a r i z e ro f t e nl e a d st os p a r s i t yo ft h es o l u t i o nv e c t o rw h i c h c a ng r e a t l yi m p r o v et h ee f f i c i e n c yo fc o m p u t a t i o n s w h e np = 2 ，t h ec o r r e s p o n d i n g h i a b s t r a c t a l g o r i t h mi sl i n e a ra n di se a s yt oi m p l e m e n tb ys o l v i n gal i n e a rs y s t e m b o t ha l g o r i t h m s h a v eb e e ns t u d i e di nt h el i t e r a t u r e 。i nt h i st h e s i s ，w ea p p l yc o n c e n t r a t i o nt e c h n i q u e s w i t h 俨一e m p i r i c a lc o v e r i n gn u m b e r st og e tt h eb e s tl e a r n i n gr a t ef o rt h et h el e a r n i n g a l g o r i t h m s s i n c eo u ra i mi sac a p a c i t yd e p e n d e n ta n a l y s i s ，w ea l s os h o wt h a tt h e f u n c t i o ns p a c e si n v o l v e di nt h ee r r o ra n a l y s i si n d u c e db yt h en o n - s y m m e t r i ck e r n e l f u n c t i o nh a v en i c eb e h a v i o r si nt e r m so ft h e 俨一e m p i r i c a lc o v e r i n gn u m b e r so fi t su n i t b a l l k e y w o r d s ：h e r m i t el e a r n i n g ，n o r m a le s t i m a t i o n ，m a n i f o l dl e a r n i n g ，s a m p l ed e p e n d e n t h y p o t h e s i ss p a c e ，c o e f f i c i e n t sr e g u l a r i z a t i o ns c h e m e i v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名： 歹| 年j 月g 日 第1 章引言 第1 章引言 随着科学与信息技术的迅猛发展，现代生活和工作的各个方面都涉及到数 据的采集与处理。我们的社会投入了大量的人力，物力和财力，为了科学，医 学，工程和商业的目的而收集各种各样类型的数据。如何处理及利用这些数据 在现代科学与工程的各个领域中起着十分重要的作用。 随着计算机广泛应用于解决科学与现实生活中的问题，机器学习( m a c h i n e l e a r n i n g ) 作为- - 1 7 全新的学科得以迅速发展。概括地说，机器学习就是基于经验 数据设计有效的算法从而使计算机具有某种学习的能力。或者说，机器学习的 主要任务是利用计算机来做数据分析并且从数据样本中找出规律性的东西。它 在以数据挖掘和信息检索为目的的很多领域都有着十分重要的应用。作为机器 学习的一个分支，学习理论( 1 e a r n i n gt h e o r y ) 主要是为学习算法和数据分析方法 提供理论支持。它开始于上世纪五十年代后期对模式识别问题的分析，上世纪 六十年代到九十年代又在统计学的框架下得到发展和研究。现在，学习理论已 经发展成为一门涉及统计学，逼近论，调和分析，计算机科学以及优化论等多 学科的研究领域。 一般来说，我们利用对其属性的观测值来描述客观事物。例如，我们可以 利用性别，身高，体重来描述一个人。另外，很多时候，我们会对客观事物所 处的某种状态或者它所呈现的某种现象特别感兴趣，例如人的健康状况。在现 实生活中，从单个观测实体采集到的数据往往可以被分成两部分，第一部分反 映被观测对象的属性细节，第二部分反映被观测对象所处的某种状态。当然， 并不是所有数据都包括这两部分，有些数据可能只含有第一部分。在数学建模 中，我们把与一个观测实体有关的数据表示为( z ，y ) ，其中z 称之为输, k ( i n p u t ) ， 它是由客观事物的n 个观测值构成的一个r n 空间中的向量，y 碾称之为x 的标 注( 1 a b e l ) ，用来量化客观事物所处的状态。 在学习理论中，针对不同类型的数据，我们主要考虑两类学习问题。一个 是监督学习( s u p e r v i s e dl e a r n i n g ) 用来学习的样本数据都包含输入和相应的标 注，学习算法给出一种方法用来预测新输入样本的标注。另一个是无监督学 习( u n s u p e r v i s e dl e a r n i n g ) ：给出的样本数据都不包含标注，学习算法用来找寻数 据的组合方式或者给出数据本身的某种性质。 本文中，我们同时对监督学习算法和无监督学习算法进行了研究，并且对 于算法的性能给出了详尽的数学分析。首先，我们简单回顾下统计学习理论的 发展。 第1 章引言 1 1经典的统计学习理论 随着计算机性能的提高，对现实生活中的问题进行多维数据分析成为可能。 伴随着第一代高性能计算机的产生，经典的学习理论开始发展于上世纪六十年 代。 学习理论中依赖估计问题( d e p e n d e n c ye s t i m a t i o n ) 描述为：如果一组数 据 z 。，犰) 罂，是由某种函数依赖关系所决定的，如何找出这种依赖关系；或 者说，如果存在函数广：r n - - + 瓞使得玑厂( 甄) ，如何确定广。传统的统计数 据分析例如参数推断( p a r a m e t r i ci n f e r e n c e ) 是在一个预先定义好的集合中来寻找 这种函数依赖。这个集合是由有限个已知的相对简单的函数( 例如多项式) 的线 性组合生成并且要包含目标函数，+ ，或者其中的函数可以用来很好地逼近目标 函数广。因此在这种给定集合里进行依赖估计等价于用所给数据估计其线性组 合的参数。显然要给出这样的集合需要目标函数一些先验的性质。 如今我们需要处理的数据与以前大不相同。在很多时候，我们可以从单 个实体上采集到曲线，谱甚至是图像，因此z 是一个几千维甚至上百万维的向 量。例如，我们要利用卫星图像数据来精确复原整个地球表面( 误差在一米以 内) ，此时z 就应该有几百万维。参数统计推断的方法是不能用来处理这种高维 数据的，主要是因为，假设礼元目标函数，+ c s ，在个多项式预先定义的函 数集中寻找厂+ 的逼近，只能保证精度是o ( n 叫肛) 。如果，+ 只是l i p s c h i t z 连续， 也就是s = 1 ，且所需的误差精度为e 0 ，则n = 0 ( e 哪) ，当礼很大的时候， 随着精度的增加迅速增大。因此，在处理现实生活中的高维问题时，当我们 需要考虑的变量有成百上千维，定义一个合理且相对较小的函数集合来逼近 目标函数是不可能的。这就是r i c h a r db e l l m a n 在【6 】中所提到的维度诅咒( c u r s eo f d i m e n s i o n a l i t y ) ，即维度的增加将导致计算资源以指数级增长。 既然传统的统计分析方法在处理现代数据时有局限性，作为一种全新的方 法，统计学习理论的出现可以帮助研究者针对数据特别是高维数据进行归纳推 断。从统计学的观点来看，它是一种非参数推断，即人们不需要知道关于潜在 的统计规律或者要逼近的函数的任何先验信息，我们仅是从已给样本中找出一 种方法给出推断。具体来说，学习理论的主要目的是为研究推断问题提供理论 支持，所谓推断问题就是通过创建模型从数据中获取信息，做出预测或选择， 而统计学习理论是在统计的框架下研究推断问题，即假设数据是随机的，按照 某种统计规律产生。下面我们以监督学习为例来给出统计学习理论的数学模 型。 2 第1 章引言 1 2 监督学习的数学框架 假设x 是欧式空间r n 的一个紧集，y 是酞上的一个闭子集。因为采样是随 机的( 或者在采样的过程中允许误差) ，我们假设p 是定义在z ：= x y 上的一 个b o r e l 联合概率分布。我们需要一个损失函数妒：rr - r + 来衡量任一函 数f ：x - y 的预测能力。实际上，妒( ，( z ) ，y ) 给出的是把厂作为模型对z 进行 预测的误差。这是一个局部误差，把所有关于( z ，秒) x y 的局部误差在整 个z 上做关于分布p 的平均，于是我们得到关于函数厂的泛化误差( g e n e r a l i z a t i o n e r r o r ) ： ， 秽( ，) = 妒( ，( 。) ，y ) d p jz 我们想要确定的目标函数因此定义为 2 a r g ，蛩夥( n 因为p 是未知的，我们不能从上述表达式直接计算臂。我们能利用的是一组 样本z = ( z t ，玑) ) 2 1 ，假设这些样本都是由j 9 独立选取的。学 - - - - j 算法就是由 样本z 构造丘来逼近譬。这个过程在一个给定的称之为假设空间( h y p o t h e s i s s p a c e ) 的函数集中进行a 因为i n f ，w 秽( ，) 给出了咒中函数的最小泛化误差，我 们利用额外泛化误差( e x c e s sg e n e r a l i z a t i o ne r r o r ) 夥( 厶) 一怨夥( ，) 来衡量算法的性能。学习算法要具有相容性【2 6 】。 定义l 1 一个学习算法称之为与假设空间咒和损失函数矽相容，如果础( 厂z ) 在概 率意义下收敛至l j i n f i 7 - 毋( ，) ，也就是说对于任意e 0 ， 钉l i mp r o b f ( f , ) 一删i n f 础( f ) e _ 0 1 3 经验风险最小化 经典的统计学习理论中一个重要的思想是发展于上世纪六十年代末期的 经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ) 原贝l j l 7 2 1 。由于样本由p 独立选取，对 于一个固定的函数，由大数定理，当样本个数趋于无穷，经验误差( e m p i r i c a l e r r o r ) 础( ，) = 磊i - 妒( ，( 兢) ，玑) 3 第1 章引言 在概率的意义下收敛到泛化误差础( ，) 。因此经验风险最小化原则建议，与其最 小化泛化误差来寻找目标函数，人们可以通过最小化经验误差来找寻一个替代 的函数。在所有可能的函数中找寻使经验误差最小化的函数是不明智的。事实 上，如果单点集在p 的测度下是零，我们总是可以构造一个函数使其经验误差最 小而泛化误差可以任意大。 因此，为了防止这种过拟合( o v e rf i t t i n g ) 现象，一个简单的方法是在一个适 当选取的丸中最小化经验误差。则经验风险最小化算法定义为 盘= a r g m 俐i n 掣( ，) ( 1 1 ) 令 戌= a r g m 倒i n 秽( n 如果损失函数函数妒是凸的并且假设空间“是紧致的函数空间，函数谨是完善 定义的。显然，如果秽属于咒，则黟( 硝) = 夥( ) 。随之而来的一个重要问 题是该算法的相容性。下面关于额外泛化误差的分解是i 扫c u c k e r 和z h o u 1 s l 提出 的： ( 兹) 秽( 谨) = 夥( 舷) 一础( 兹) ) + 础( 锄) 一础( 戌) ) + 础( 硝) 一秽( 戌) ) 矽( 兹) 一掣( 兹) ) + 础( 戌) 一秽( 硝) 2 s u pl 础( ，) 一彰( 删( 1 2 ) ，咒 这个分解说明经验风险最小化算法的相容性是由咒中一致概率意义下的收敛 所决定的。这种关于函数集的一致大数定律在经验过程( e m p i r i c a lp r o c e s s ) 领域 被d u d l e y ，g i n 6 ，z i n n ，v a p n i k t ”】广泛地研究。 定义1 2 我们说由定义在距离空间x 上的实值函数构成的集合饨是一致g l i v e n k o c a n t e l l i ( u g c ) 的，如果对任意的e 0 ， 。三芊b s u pz。p，王”rob。 e ) = 。， 这里，p 是定义在x 上任一b o r e l 概率分布，样本z 1 ，z 2 ，z m 由芦独立选取。 函数集合的u g c 性质可以被该集合的k 一维刻画。其他的一些涉及集合容 量的量例如覆盖数( c o v 谢n gn u m b e r ) ，熵数( e n t r o p yn u m b e r ) ，v c 维等都可以用 来描述这一性质。下面的定理在【l 】给出。 4 第1 章引言 定理1 1 假设丸是由从x 到 0 ，1 】的函数构成的集合，则爿是粥c 的当且仅当对 任意的7 0 ，咒的k 一维是有限的。 因此为了得到好的学习效果，假设空间的容量控制对于经验风险最小化算 法是至关重要的。 1 4 正则化 当目标函数。，+ 属于孔时，经验风险最小化算法有着良好的表现。但是 这种情形是很少发生的。因此我们要尽可能扩大假设空间同时还要避免过 拟合的发生。另外，直接最小化经验误差经常导致数值计算的不稳定。正则 化( r e g u l a r i z a t i o n ) 作为一种可行的避免这种问题的方法首先被t i k h o n o v 幂l ：i a r s e n i n f 7 0 】用 来解决反问题，然后被p o g g i o 和g i r o s i i 3 4 】成功地应用到学习理论上，在统计中相 应的方法被称为收缩估计( s h r i n k a g ee s t i m a t o r ) t 4 2 1 。 取一个尽可能大的函数集合作为假设空间咒，这个集合很可能在连续函数 空间中是稠密的。令q ：孔- r + 是定义在假设空间咒上的泛函，该泛函称为正 则化子( r e g u l a r i z e r ) 用来衡量税中任一函数的复杂程度。贝l j t i k h o n o v 正则化算法 定义为 珐= a r g 嘶 础( ，) - 4 - 入q ( ，) ) ( 1 3 ) 这里，a 0 称为正则化参数用来平衡拟合程度与拟合所用函数的复杂程度。如 果咒是b a n a c h 空间或者h i l b e r t 空间，正则化子一般取与空间范数有关的形式。 参数入的选择是影响算法性能的关键，并因此形成了模式选择( m o d e ls e l e c t i o n ) 中 的一个重要的研究课题u 9 1 。在实际应用中，确定最佳的入通常是十分困难的， 很多时候要利用额外的数据通过交叉验证来完成这项工作。 为了研究正则化算法( 1 3 ) 的收敛性，我们定义 群：= 戏咒= a r g r a 艇i “n 黟( ，) 一夥( 黟) + 入q ( ，) ) 我们将带有惩罚项的额外泛化误差髟( 磋 ) 一夥( ) + a q ( 磋a ) 分解为 秽( 壁a ) 一掣( 壁a ) ) + 掣( 式) 一秽( 式) ) + 彩( 群) 一夥( ) + 入q ( 群) ) + ( 掣( 职) + a q ( 幺) ) 一( 硭( 式) + a q ( 戌) ) ) 由璧入的定义可知，最后一项小于或者等于零，因此泛化误差秽( 拦a ) 一 夥( 瑶) 以 秽( 职) 一硭( 璐) ) + 露( 戌) 一秽( 臂) ) + 彩( 群) 一秽( ) + a q ( 霞) ) 气 第1 章 引言 为上界。前两项涉及到样本z 被称为样本误差( s a m p l ee r r o r s ) ，我们希望可以随着 样本个数m 的增大趋于零；而最后一项称为逼近误差( a p p r o x i m a t i o ne r r o r ) 用来衡 量假设空间咒的逼近能力，我们期望这一项可以随着a 趋于零而趋近于零。因此 为了给出正则化算法的误差分析，我们转而分别估计样本误差和逼近误差。误 差分解是对许多学习算法进行分析的标准过程，在以下各章中，我们将会用到 各种误差分解方式。 在学习理论中，我们通常选择再生核h i l b e r t 空间作为假设空间而正则化子 取为空间范数的平方。 1 5 再生核h i l b e r t 空间 再生核h i l b e r t 空间最早应用于逼近论中【7 7 1 ，然后被g i r o s i 和p o g g i o 弓l , k 学习 理论。再生核h i l b e r t 空间( r k h s ) 是o a m e r c e r 核生成的。 定义1 3 令x 是一个距离空间，函数k ：xxx 称为m e r c e r 核，如果它是 连续的，对称的并且是半正定的( 即对于任何有限点集x = x l ，z 2 ，幻) cx ， g r a m i a n 矩阵k 【x 】= ( k ( z i ，) ) i l ，j ：1 是半正定的) 。 设k 是m e r c e r 核，对于集合 虬：= k ( z ，) ：z x ) 的线性包中的函数，= ：l 七玫。和夕= 罂，屈定义内积 ( ，夕) k = e k b z k ( 犰) 1 s 七n 1 0 。如果矩阵k 【x 1 是严格正定的，利 用径向基函数进行多元插值是唯一可解的【3 2 1 。尽管如此，如果西不是紧支撑的， 作为一种数值方法，当插值节点增多时，用径向基函数进行插值会变得越来越 不稳定( 这主要是因为矩阵k x 】的条件数会变得很大) 。在实际的应用中，人们 可以利用具有紧支撑的正定的径向基函数来产生相应的平移不变核。 例1 3 ( 吴核f 7 8 1 ) 令 ( z ) = ( 1 一z 2 ) 5 _ c e 。是一个2 次的截断多项式，那么卷 积咖= 五幸五是一个分段4 z + 1 次多项式函数。定义也忌( 7 ) = d 七咖( 2 7 ) ， 则丸蠡( 7 ) 是一个4 z 一2 庇+ 1 次截断多项式并且它的支撑是( 0 ，1 1 。其对应 的平移不变核k ( z ，y ) = 机，( 忪一v i i ) 是铲k + 1 上的严格正定核，b p k x l 对 于1 1 2 k + 1 上任意两两互不相同的数据集x 都是严格正定的。 例1 4 ( w e n d l a n d 核【8 0 1 ) 取t ，n ，令札r ) = ( 1 一r ) ：。对于任意d n ，取e = ld 2 l + k + 1 。定义 血，凫( r ) - = 岛，七，讥慨一n ( r ) ， 其中岛o = 1 并且对于0 歹岛+ 1 ，其系数满足下列递归关系： 嘶= 萎。两际蒜裂爿掣酾 如此得到的函数九k 伊七在【o ，l 】上是紧支撑的并且对应的平移不变核 在r d 上是严格正定的。 如果具有紧支撑，矩阵k f x l 因此是稀疏的，从而可以获得较为稳定并且高效的 插值算法，由于得到的插值函数在某点的取值只与该点附件的数据点有关，从 而为函数赋值带来很大方便。关于利用径向基函数对散乱点进行插值的更加详 尽的讨论可以查看f 7 9 】以及其中所列举的文献。更多关于再生核h i l b e r t 空间的例 子和性质可以在 6 0 1 中找到。 给定m e r c e r 核k ，在咒k 中以其范数的平方作为正则化子的t i k h o n o v 正则化 算法描述为 盛，k2a r g 倒r e _ i n k 础( j f ) + 删咐 ( 1 5 ) 第1 章引言 下面的定理【7 7 1 是由咒k 空间的再生性质推导出来的，揭示了在利用核函数设计 的学习算法中，为何取r k h s 作为假设空间的原因。 定理1 2 优化问题r j 习的解磋a ，k 属于由托l 一，恐。张成的有限雏空间丸k 1 6 积分算子和特征映射 b o r e l 概率测度j d 可以分解为在x 上的边缘测度( m a r g i n a ld i s t r i b u t i o n ) p x 以 及对于z x 的条件测) 变( c o n d i t i o n a ld i s t r i b u t i o n ) p ( y i x ) 。令己；x 表示关于测 度触的平方可积空间，即对于空间中的任何函数厂：x _ r ，都有l l 川羔& ：= 厶l f ( x ) 1 2 d p x 0 ，算子l k ：l 致_ l k 定义为 l ( 九) = 5 2 吼饥， q ) 七俨 k - - ik - - i 下面的定理称为m e r c e r 定理告诉我f i m e r c e r 核有一个致的展开式。我们 说p x 是非退化的( n o n d e g e n e r a t e ) ，如果对于任何非空开集u x 都有p x ( u ) o 。 定理1 4 ( m e r c e r 定理，聊) 若p x 是x 上的非退化的b d 纠测度，并且k ：x x _ r 舭比p 撤。令a 七是算子l 耳的第尼个正的特征值且其对应的连续的正交特征函 数是妣。则对于所有的z ，y x ，都有 k ( z ，秒) = 入七机( z ) 机( 可) ， k 三l r 第1 章引言 对于任意z ，y x ，该收敛是绝对收敛并且在x x 是一致的。 事实上，当肌是非退化的， v g 砂k ，九 o ) 构成觎k 中一组标准正交基。 当d i m t - l k = 。，算子l k 有无限可数多个正的特征值入，则 耻 ，= 妻抓蚶慨，窭 = 1 ee 2k=1) lj 当d i m t - l k = 仇 o ) - 在l k 中的闭包到咒k 的 等距同构。即对于每个，九k 都可以表示为，= l 蚤夕，其中夕l 2 p x ( x ) 并 目- i l f l l k = l ；，。 我们可以利用 佤机) 来构迮t & x f u 特征空间( 其实是粤2 中的某个子集) 的特 征映射( f e a t u r em a p ) ： 西：z _ 垂( z ) = ( 瓜七( z ) ) 凫l z 2 对于任意的z ，y x ，我们有 ( 圣( z ) ，西( 可) ) 卢= k ( z ，y ) 以及 l l 圣( 。) 一圣( 可) l l 务= k ( x ，z ) 一2 k ( x ，秒) + k ( v ，y ) ， 从而我们可以不借助特征映射的具体形式，或者说我们并不用知道数据点在 特征映射下的像，仅通过核函数就能定量地描述像之问的几何关系。因为这样 构造的映射有很大的灵活性，很多时候都不一定是线性的，因此我们在特征空 间中找到的关于数据的像之间的关系具有普遍性。这种方法称为核技巧( k e r n e l t r i c k ) ，在学习理论中有着广泛的应用。 1 7 指数型概率不等式 对于固定的厂：x r ，考虑z 上的随机变量( 名) = 砂( ，( z ) ，可) ，其中z = ( z ，可) z 。则 彩( 肛秽( ，) 2 熹一e ( f ) 9 第1 章引言 在对学 - 3 算法进行误差分析时，我们经常要考察这一项的收敛速度。一些常 用的概率不等式可以对此项进行估计，例如c h e b y s h e v 不等式。设是概率空 n z _ k 的随机变量，其均值e ( f ) = 弘并且方差为盯2 ( ) = 口，则对于任意 0 ， c h e b y s h e v 不等式断言 黝职弘h 嘉 这个不等式提供了一个关于弱收敛大数定理的简单形式，因为它表明当m - - + o o ，示1 銎1 ( 乞) 以概率1 收敛到p 。对于任意o 6 1 ，在上述不等式中 令6 = 差，我们得到在1 6 的置信度下成立 l 去妻淞h l 层 7 ， 在统计学的文献中，大多数的误差分析的上界都是以上述形式给出的，即依赖 于 。通过应用指数型概率不等式，学习理论中一个典型的上界以1 6 的置信度 可取为p ( 丝笋) 。枷，其中o 0 取决于f 的方差。与( 1 7 ) 作比较，除了收 敛速度有所提高( 可以达到；+ 口) ，另一主要的提高在于误差界只依赖l o g ( 2 a ) 。 常用的指数型不等式包括h o e f f d i n g 不等式，b e n n e t t 不等式以及b e m s t e i n 不等式。 关于详尽的讨论可以查阅【1 8 】和 7 1 。这里，我们只给出取值在h i l b e r t 空间中向量 值随机变量的b e n n e t t 不等式，它可由【5 7 】推导出来的。 引理1 5 假设“是所胁p 形空间并且 & ) 凳1 是m 个独立的取值在咒上的随机变量。 假设对于每个t ，都有慷l l m 0 引理1 6 假设孔是剧场p 空间，是( x ，p ) 中取值在咒上的随机变量，并且l m 几乎处处成立记c r 2 ( ) = e ( 1 2 ) ，且样本 既) 罂l 是由p 独立选取的 则对于0 6 0 ，使得对于任意，饨几乎处处成立l ，( z ) 一可l m ，则对于所有的e 0 ， 渤kl 础( 沪秽i e ) z 一( 咒，南) e x p ( 一旦3 0 0 m 2 ) 1 9 论文概述 在本文中，我们主要从逼近论的观点来研究学习理论中的一些算法。我们 将在接下来的几章中讨论这些算法的设计和渐近性质。 在第二章中，我们回顾学习理论中的一些主要研究课题，包括回归分析， 分类问题，聚类问题，变量选择，特征选择以及流形学习。 第三章中，利用再生核h i l b e r t 空间，在最小二乘正则化回归的框架下，我 们考虑了基于函数值与梯度值的学习问题，即抽样数据中既包括函数值的信息 又包括梯度值的信息。算法的求解涉及到一个线性方程组，其系数矩阵既包含 原来的g r a m i a n 矩阵又包含涉及到梯度的h e s s i a n s 矩阵。与传统的学习算法相比， 额外的函数梯度数据可以提高其学习性能。通过运用抽样算子分析样本误差以 及利用定义在s o b o l e v 空间上的积分算子分析逼近误差，我们得到了关于算法的 误差分析。 作为分析点云数据和进行曲面重构的一种必要的预处理手段，法向量估计 是计算机图形学中的一个十分重要的研究课题。在第四章中，我们假设样本点 随机分布在欧式空间中余维为1 的未知子流形上，针对这样的数据考虑其法向量 估计问题。我们提出了一种以核函数为基础的学习算法，它实际上是一种无监 督形式的梯度学习。算法的实现归结