（基础数学专业论文）统计学习中回归与正则化谱聚类算法的研究.pdf

， u s 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明 作者签名：蝴 签字日期：么么：笸! z 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入 等有关数据库进行检索，可以采用影印，缩印或扫描 等复制手段保存，汇编学位论文本人提交的电子文档的内容和纸质论文的内 容相一致 保密的学位论文在解密后也遵守此规定 哼么开 口保密l 年) 作者签名：涩丝幻 导师签名 签字日期：么1 2 ：压：2签字日期_ 竺! ! ：! ：1 7 lj1ij 摘要 摘要 在本文中，我们主要研究了统计学习中的回归和谱聚类算法。主要贡献可 分为以下三个部分。 首先，研究回归问题。在样本无界的背景下，我们考虑了最小二乘正则化 学习算法。这部分的工作主要是利用积分算子方法，得到了很好的学习算法 收敛阶。主要结果依赖两个重要假设，一个是关于无界输出样本的矩假设，另 一个是与边缘分布相关的函数空间假设。在适当的条件下，所得结果是与样 本有界情况下是一致的。 其次，我们研究了谱聚类算法。类似的理论研究近几年已经有很多。我们 的创新之处在于：我们在一个依赖样本的有限维假设空间内考虑，这样很自 然的能够引入统计上著名的l a s s o 思想，即施加正则化项一三1 罚。由核函数张 成的样本依赖假设空间能够为学习过程提供很好的灵活性。可是同时也带来 了技术处理和理论分析上的困难。主要困难在于假设空间不仅依赖样本，而 且还有两个约束条件，以前所有的处理技巧都不能直接拿来应用。本文从逼 近论角度研究，通过合理的假设克服了上述困难。这里主要利用的是局部多 项式再生公式和构造化的处理手段。谱聚类算法的一致性主要取决于以下几 个条件：输入空间的结构，未知的分布，核函数以及目标函数的光滑性。 最后我们以逼近论的角度去研究学习理论中的回归问题。根据一些逼 近论中的正定算子，设计了一系列非优化的学习器。这样的学习器是由一般 的核函数经过放缩变换，然后作用于样本点产生的。他们与经典的逼近算子 的区别主要在于：传统的逼近算子依赖于确定的节点或节点满足很好的形状， 而学习器的样本是随机的。在回归的背景下我们研究了这样学习器的有效性， 并且给出了他们的泛化能力。泛化能力主要依赖于回归函数的光滑性，随机 样本的方差以及核函数中心与规则节点的距离。误差分析由样本误差和逼近 误差两部分组成。我们详尽的阐述了两个典型的例子，一个是核函数由连续 型伯恩斯坦基构成的，另一个是关于杰克森算子的。获得了相应的具体的学 习阶。 关键词：再生核希尔伯特空间b e r n s t e i n 多项式谱聚类函数空问复杂度 i 摘要 正则化算法。 a b s t ra c t a b s t r a c t i nt h i st h e s i sw ei n v e s t i g a t es e v e r a la l g o r i t h m si ns t a t i s t i c a ll e a r n i n gt h e o r y ，a n d o u rc o n t r i b u t i o n sc o n s i s to ft h ef o l l o w i n gt h r e ep a r t s f i r s tw ef o c u so nt h el e a s ts q u a r er e g u l a r i z e dr e g r e s s i o nl e a r n i n ga l g o r i t h mi na s e t t i n go fu n b o u n d e ds a m p l i n g o u rt a s ki s t oe s t a b l i s hl e a r n i n gr a t e sb ym e a n so f i n t e g r a lo p e r a t o r s b yi m p o s i n gam o m e n th y p o t h e s i so nt h eu n b o u n d e ds a m p l i n g o u t p u t sa n daf u n c t i o ns p a c ec o n d i t i o na s s o c i a t e dw i t ht h em a r g i n a ld i s t r i b u t i o n ，w e d e r i v el e a r n i n gr a t e sw h i c ha r ec o n s i s t e n tw i t ht h o s ei nt h eb o u n d e ds a m p l i n gs e t t i n g t h e nw ec o n s i d e rt h es p e c t r a lc l u s t e r i n ga l g o r i t h m sb yl e a r n i n gw i t har e g u l a r i z a t i o ns c h e m ei nas a m p l ed a t ah y p o t h e s i ss p a c ea n d1 1 - r e g u l a r i z e r t h ed a t ad e p e n d e n t s p a c es p a n n e db ym e a n so ft h e k e r n e lf u n c t i o np r o v i d e sg r e a tf l e x i b i l i t yf o rl e a r n i n g t h em a i nd i f f i c u l t yi ns t u d y i n gs p e c t r a lc l u s t e r i n gi no u rs e t t i n gi st h a tt h eh y p o t h e s i s s p a c en o to n l yd e p e n d so n as a m p l e ，b u t a l s od e p e n d so ns o m ec o n s t r a i n e dc o n d i t i o n s t h et e c h n i c a ld i f t i c u l d yi ss o l v e db yal o c a lp o l y n o m i a lr e p r o d u c t i o nf o r m u l aa n da c o n s t r l l c t i o nm e t h o d t h ec o n s i s t e n c yo fs p e c t r a lc l u s t e r i n ga l g o r i t h m si s s t a t e di n t e r m so fp r o p e r t i e so ft h ed a t as p a c e t h eu n d e r l y i n gm e a s u r e ，t h ek e r n e la sw e l la st h e r e g u l a r i t yo f a t a r g e tf u n c t i o n f i n a l l y ，w et a k eal e a r n i n gt h e o r yv i e w p o i n t t os t u d ya f a m i l yo fl e a r n i n gs c h e m e s f o rr e g r e s s i o nr e l a t e dt op o s i t i v el i n e a ro p e r a t o r si na p p r o x i m a t i o nt h e o r y s u c ha l e a r n i n gs c h e m e i sg e n e r a t e df r o mar a n d o ms a m p l eb yak e r n e lf u n c u o np a r a m e t e r i z e db y as c a l i n gp a r a m e t e r t h ee s s e n t i a ld i f f e r e n c eb e t w e e nt h i sa l g o r i t h ma n d t h ec l a s s i 。 c a la p p r o x i m a d o ns c h e m e si st h er a n d o m n e s so ft h es a m p l i n gp o i n t s ，w h i c hb r e a k s t h ec o n d i t i o nf o rg o o dd i s t r i b u t i o no fs a m p l i n gp o i n t so f t e nr e q u i r e di na p p r o x i m a t i o n t h e o r y w ei n v e s t i g a t ee f f i c i e n c yo ft h el e a r n i n ga l g o r i t h mi n a r e g r e s s i o ns e t t i n ga n d p r e s e n tl e a r n i n g r a t e ss t a t e di nt e r m so ft h es m o o t h n e s so ft h er e g r e s s i o nf u n c t i o n ，s i z e s o fv a r i a n c e s ，a n dd i s t a n c e so fk e r n e lc e n t e r sf r o mr e g u l a rg r i d s t h ee r r o ra n a l y s i si s c o n d u c t e db ye s t i m a t i n gt h es a m p l ee n o ra n da p p r o x i m a t i o ne n 0 r t w oe x a m p l e sw i t h k e m e lf u n c d o n sr e l a t e dt oc o n t i n u o u sb e r n s t e i nb a s e sa n dj a c k s o n k e r n e l sa r es t u d i e d a b s t r a c t _ _ 一 i nd e t a i la n dc o n c r e t el e a r n i n gr a t e sa r eo b t a i n e d k e y w o r d 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 ，b e r n s t e i np o l y n o m i a l ，s p e c t r a lc l u s - t e r i n g ，c o m p l e x i t yo f f u n c t i o ns p a c e s ，r e g u l a r i z e da l g o r i t h m s i v 目录 目录 摘要i a b s t r a c t i 目录v 第1 章学习理论的基本框架1 1 1 学习理论的主要问题1 1 2 核方法介绍2 1 2 1 再生核希尔伯特空间的基本理论2 1 2 2 标准的基于核的监督学习算法 4 1 2 3 正则化谱聚类算法6 1 3 在样本依赖假设空间的学习8 1 4 容量依赖与容量独立9 1 5 无界情形下的学习1 0 1 6 含噪音抽样的逼近算子l1 1 7 本论文的概括1 2 第2 章无界输出样本的回归问题1 3 2 1 基于核函数的学习算法框架1 3 2 2 有关r h k s 的性质和假设1 4 2 3 主要结果1 6 2 4 基于积分算子的误差分析1 7 2 4 1 样本误差估计1 7 2 5 在“k 的学习阶2 2 2 5 1 在l ；x 的学习阶2 3 第3 章带2 1 正则化的谱聚类一致性2 7 3 1 谱聚类框架2 7 3 1 1 正则化谱聚类算法2 8 3 1 2 误差分解与逼近误差估计2 9 v 目录 3 2 假设误差估计3 1 3 3 样本误差估计3 7 3 4 整体误差和学习阶4 2 第4 章以逼近论角度研究学习理论4 5 4 1 背景和学习算法4 5 4 2 两个典型例子4 6 4 - 3 一般情形4 8 4 4 误差分析4 8 4 4 1 样本误差估计4 8 4 4 2 逼近误差估计5 0 4 5 关于b e r n s t e i n 基的例子5 2 4 6j a c k s o n 核情形5 5 参考文献5 9 致谢6 7 在读期间发表的学术论文与取得的研究成果6 9 v i 第l 章学习理论的基本框架 第1 章学习理论的基本框架 机器学习在计算机科学，金融，工业等诸多领域发挥着重要作用。它的基 本原理在于：通过收集的数据，找到数据间的函数关系，借以用来预测未来趋 势或提取有效的信息。统计学习就是为许多常用的机器学习算法提供理论支 持的，进而形成了一门的新的数学分支一学习理论。 一般情况下，我们容易得到一个输出量值( 如股票的价格) ，我们希望根 据一些该股票的特征( 如股票对应公司的表现和经济数据) 来预测未来的股 票价格。也就是说，样本包括一些输入和与之相对应的输出。用这些可观察到 的数据来建立预测模型，用它来预测我们事前无法看得见的事物。上述的描 述称之为“监督学习一，这样称谓主要是因为用输出变量来指导学习过程。监 督学习依据输出变量形式的不同可以分为回归和分类。回归问题下，输出值 是连续型的，而分类的输出值是离散的。在现实世界里，并不是每个输入都有 与之对应的输出存在。有些情况下，输入值很容易获得，可输出值却得不到， 在这种情况下研究事物内在的不变性，划分归类或建立分类器，机器学习上 称之为“无监督学习”。聚类就是属于“无监督学习”的一种非常流行的算法。 在我毕业论文中，首要研究了最小二乘正则化学习算法和谱聚类算法。在 适当的框架内为指定的一些算法提供了理论分析。然后从经典的逼近论角度 去研究学习理论的回归问题，为学习理论的研究提供了一个新的视角。接下 来我们首先回顾一些学习理论的标准框架。 1 1学习理论的主要问题 学习理论研究的问题可以如下描述。在可度量空间z 定义一个概率分 布p ，考虑函数集合q ( z ，口) ，其中o l a 我的目标是使得下列的风险泛函最小o ， r ( 口) = q ( z ，q ) d p ( z ) ，q a ， ( 1 1 ) - ， 这里概率测度p 是未知的，但是已知样本z l ，z 2 ，z m 是从p 中独立抽取的。学 习理论的任务就是利用样本信息，通过建立数学模型来发现事物内在的规律， 从而达到预测，增加认识或进行决策的最终目的。在学习理论中，核方法其中 1 第1 章学习理论的基本框架 非常重要的角色，尤其是支持向量机，高斯过程，主成份分析，谱聚类等分析 工具的出现，核方法引起了工程界和学术界的广泛关注。 1 2 核方法介绍 核方法最初是用来模式分析的。它兴起于二十世纪九十年代，尤其 是v a p n i k 提出了影响深远的支持向量机【6 6 1 。 核方法可以这样简单描述：首先把原始数据映射到一个高维的特征空间， 每一个坐标对应一个数据的特征，这样把数据变成了一系列欧式空间的点。 核方法的成功归因于核函数的应用，它能够使问题在特征空问得以解决，同 时不需要计算数据在特征空间的坐标，只需要计算两两数据在特征空间的内 积就可以了。核方法在数据挖掘，图学习，文本挖掘以及图像处理等诸多领域 都有广泛应用。 1 2 1再生核希尔伯特空间的基本理论 在过去十多年间，利用正定核估计和学习成为了机器学习中相当流行的 方法。这些方法定义在一个有摩塞核产生的再生核希尔伯特空间，它有很强 的数学理论基础。 定义1 1 令x 是一个度量空问。我们称一个核k ：x x _ r 是对称的， 兰i t f ( z ，y ) = k ( y ，z ) 对于任意z ，y x 。如果给定任意多个点【z 1 ，x 2 ，x k c x 和对于所有的 c 1 ，c 2 ，) cr ，乞c 勺k ( 航，x j ) 0 恒成立，我们称这个 核是半正定的。如果这个核同时满足连续，对称和正定这些条件，那么它被称 为“摩塞核一。 任意半正定核都能诱导一个再生核希尔伯特空间，表示为7 l f k 。首先由线 性组合a i k ( x ) 张成有限维内积空间，其中定义内积为： m ( q t g ( x ) ，岛( 协，) ) h k = a i l 3 j k ( x i ，协) 然后把这个有限维空间完备化就构成了再生核希尔伯特空间。 在下文中，我们用( ) k ，i l i l k 分别来表示再生核希尔伯特空间的内积和范 数，来代替比较繁琐的( ) “耳和”l i h 。 2 第1 章学习理论的基本框架 咒的再生性可以由点泛函的r i e s z 定理来描述： f ( z ) = ( ，f g ，v x x ，7 - g ( 1 2 ) 假设 k ：= s u p 钔丽 0 ，l k ：三2 p ( x ) _ 三三( x ) 是很好定义的，表示为： 坛( 似z ) = a ；( ，e 七) e 七，v ，l 三( x ) k = l 表示r = i ：九 o ) ，那么 0 i ：i r ) 形成咒k 一组正交基并且，l 名2 9 7 - k 和l ：之间的同构映射，特别地 i l f l l 现= i i 三z 2 f l l k 我们称p 是非退化的，如果对于任意非空开集u x ，p ( u ) 0 。下列的 摩塞定理来自参考文献【1 4 】。 3 第1 章学习理论的基本框架 定理1 2 令弘是一个定义在x y _ _ 的b o r e l 非退化测度，以及k ：x x r 是 摩塞核令入k 是l k 的第七个正的特征值，和机为相对应的第七个连续特征函 数对于任意的z ，t x ，k 可以表示为： k ( x ，艺) = 入知九( z ) 机( z ) k l 对于每个z ，y x ，上述收敛是绝对和一致的。 1 2 2 标准的基于核的监督学习算法 在机器学习术语中，监督学习可以描述为：令x 是一个紧的度量空间 和ycr 。假定z x 和y y 是取自一个定义在x y 上的联合概率测 度p 的随机变量。这里z 称之为输入变量，y 是输出变量。定义一个损失函 数矽= 妒( ，( z ) ，y ) 来衡量预测的精度。全局误差是通过一个叫做“泛函误差一 的概念来描述的： ( ，) = 砂( ，( z ) ，) 咖( z ) ， jz 拥有最好学习能力的目标函数定义为： 靠= a r g r a i n ( f ) ， ( 1 4 ) 这里的最小化取自从x 到y 的所有可测函数。既然p 是未知的，我们无法直接 得到目标函数詹。可行的办法是通过样本z = ( 魏，鼽) ) 罂1 的信息构造一个学 习器，z 。当样本量很大的时候，希望厶能够很好的逼近澎。一个很自然的想法 是把泛i t i i 吴差离散化，即根据损失函数咖和样本z z m 来定义“经验误差 ： g ( ，) = 三m 矧甄) ，犰) ( 1 5 ) 由概率论的大数定理，期望留极小化函数能够逼近力，上述方法叫做“经验风 险极小化一( e r m ) 原则。可是解决e r m 算法是个不适定问题，以及可能发生 过度拟合，特别是当假设函数空间的复杂度很高的情况下。为解决不适定问 题，t i k h o n o v 6 4 l 提出了正则化的思想。这种思想在样条理论，机器学习中都有 广泛的应用。包括支持向量机在内的许多机器学习算法都可以看作为正则化 算法的一个特例。 4 第1 章学习理论的基本框架 有了以上准备，我们现在可以清楚的给出一个基于经验误差和正则化项 的正则化监督学习算法。给定从x 到y 的函数集合形，被称为“假设空间”， 我们建立如下优化问题 厶，a2 a r g 晃耍g ( ，) - - i - ) f f 2 ( f ) ， ( 1 6 ) 这里q ：彤_ r + 是一个惩罚泛函，通常满足q ( o ) = 常数入被称为正则 化参数，作用是平衡“经验误差和惩罚力度的。它往往依赖于样本容量， 即入= 入( m ) 满足l i m m 。入( m ) = 0 。 当考虑上述优化问题在一个再生核希尔伯特空问氕k 里，以及惩罚泛函 是f 2 ( f ) = l i f l l 炙- ，问题就转化为： 厶，卜m - g 倒m i n kg ( f ) + a l l f l l 琵 ( 1 7 ) 现在通过适当地选取一些损失函数，我们列出一些经典的机器学习算法。 正则化最小二乘( r l s ) 对应的损失函数：咖( ，( z ) ，y ) = ( f ( x ) 一y ) 2 ； 支持向量机分类对应h i n g e 损失函数：( ，( z ) ，y ) = m a 。x 0 ，1 一，( z ) 可 ； 支持向量机回归对应的是s 不敏感损失函数：妒( ，( z ) ，y ) = m a x 0 ，i f ( x ) 一 y 卜e ) 依据经典表示定理，优化问题( 1 7 ) 的解存在并且能在有限维空间内得到，即 为此，在何k 的优化问题就简化成了在有限维空间内求系数q ；( i - l ，m ) ，同时 又能保持选取集合足够大，包括非线性函数等。例如，考虑最小二乘时，对应 的算法( 1 7 ) 有闭形式的解，可以通过解决一个线性系统求得( 见e g 【1 4 1 ) 。对于 一般的凸的损失函数，经常无法通过原始问题直接得到解。代替的是转化为 其对偶问题。 定义对偶函数砂：r r 为： 妒( ”，b ) = s u p v u 一( “，6 ) ，u ，b r u e r ( 1 8 ) 5 z 甄 k乜 m 试 l l c 厶 第1 章学习理论的基本框架 原始问题与它的对偶关系已很好的理解( 见e g 【7 9 】) ： ，i n h f k 耋( ，) + 入0 ，i i 琵) = q s u 酞p 。 r ( q ) ) ， 其中 脚) - _ 善卅啦撒) 一志垂啦刚砒一r m 并且两个优化问题的解都存在，如果 鑫= a r g 理鞣 r ( 血) ) ， q r m 那么 ，z 厂赤萋砬k ( 酬 1 2 3 正则化谱聚类算法 谱聚类是一种重要的数据分析技术，已经广泛应用到许多领域，如机器 学习，数据挖掘，模式识别以及生物信息等。聚类是属于无监督学习的一种方 法。给定样本点，目的是根据数据问的距离或类似性概念把整体数据分成若 干组。 谱聚类是一种应用很广的聚类算法，它的起源可以追溯到d o n a t h 和h o f f m a n 1 6 】 以及f i e d l e r 蚴。最近它的理论研究引起了广泛关注。谱聚类最要有两个类型： 非标准化谱聚类和标准化谱聚类。就最简单的形式而言，根据样本点在仿射 图的相似性来建立一个图l a p l a c i a n 矩阵，用该矩阵的第二大特征值对应的特 征向量作为划分数据的依据。 同监督学习一样，我们假定数据空问x 是紧的度量空间，p 是定义在x 上的概率测度。给定独立从p 中抽取的m 个数据样本点x = z 0 翟1 ，数据点 两两类似由一个核函数来定义：k j = k ( x i ，巧) 。数据类似矩阵可以表示 为：致= ( q j ) i j ：1 ，- ，m ，幕i i u d 表示一对角矩阵，其元素也：= 銎1k j 。本论 文重点研究的“非标准图l a p l a c i a n 弦定义为三： 三= d 一致 。标准图l a p l a c i a n 一定义为： l ：= d 一1 2 l d 一1 2 = ，一d 一1 2 k x v 一1 2 6 第1 苹学习理论的基本框架 l ”：= d l = i d k x “非标准图l a p l a c i a n 弦的许多性质i 扫m o h a r 4 5 】证明所得，而c h u n g 1 2 】详细 陈述了关于“标准图l a p l a c i a n 一的一些性质。这样我只列举一些为我们所用的 重要的性质： -m v t l v = 石1 k ，歹( 忱一v j ) 2 ， 对于任意向量口= ( u 1 ，v m ) t r m 。i , j = l 这等式说明了三是半正定矩阵。同时也很容易证明0 是l 的最小特征值，而对 应的特征向量是l = ( 1 ，1 ) t 。类似的性质对于l a n dl ”也成立。 一致性是统计学中研究随机数据需要考虑的重要性质。在有限点集合的 特殊背景下，早起有一些关于谱聚类的一致性结果。直到最近，v o nl u x b u r g 等 人【3 6 】才深入的讨论了谱聚类的极限行为，建立了有限样本与潜在分布的收敛 结果。他们证明了，标准化谱聚类在适当的条件下就能够收敛，但非标准谱聚 类需要附加一些苛刻的条件才可以。 并不是很显然的就能看出这些谱聚类的运行机制。谱聚类的根源思想在 于谱图理论。如下观点可以解释谱聚类如何起作用的：图切割，随机游走以及 扰动理论。详细的阐述可以查阅y o nl u x b u r g 的文章1 3 7 。本文只考虑非标准化 谱聚类的最简单形式，它可以由图逼近切割观点推导出来【3 7 1 ，从而导致下面 宽泛的优化问题 1 m v = a r g 罂器赤( 讹一u j ) 2 k j s u b j e c tt 。m i _ _ u t d 乱= 1 ，u t d l = o ( 1 9 ) 依据r a y l e i g h - r i t z 定理【矧，该优化问题的解就是三的第二最小特征值对应的特 征向量记为v 。x 的划分- - i 哇t v 得到，e g c = x iiv i o ) a n d - 0 = 兢iv i ，( 1 11)i=1 i = 1 4 = 厂l ；l t 城( 旎) = o ，去厂( 鼢) 玩( 戤) = 1 ， ( 1 l ， 这里段= 磊1 墨1 ；。表示定理依然成立，目标函数有形式： a 一= 虬；， 其中矿= ( q 荨，碥) 是由下列优化算法决定的 q x = 哪躲嘉q t k x l k x q + ，y q t 致qs t - - 嘉a t k , , d k , , q = l ，o c t k x d l = 0 1 3 在样本依赖假设空间的学习 假设空间形和惩罚函数q 的选择直接决定于算法( 1 6 ) 的性能表现。一个 传统的方法是基于先验信息而不是样本点来选择假设空间。一个典型的例子 是：在线性回归模型中，选择线性函数空问作为假设空间。另外一种方法是选 择一个基于样本的假设空间，此类的研究已经有很多，如自适应模型选择，学 习核函数和系数化正则算法等。在这种情况下，假设空间依赖于样本信息z ， 即形= 缆，惩罚项也依赖于样本：q = q z 这样学习算法( 1 6 ) 呈现如下形 式： 厶= a r g 艘g ( ，) + a 咒( n ( 1 1 2 ) 误差分解是研究算法( 1 1 2 ) 的强有力方法，把泛化误差分为样本误差，假设误 差和逼近误差( 或正则误差) 。在分析过程中，我们需要定义一个与样本无关 的全体假设空间和适当的逼近误差。 定义1 2 我们称定义在x 的函数空间镅是与( 1 1 2 ) 算法相关的全体假设空间， 如果g r e e nu z z 。兹编。与镅和惩罚泛函q o ：镅- 瓞+ 对应的逼近误差 定义为 玩( 入) 2 篾敝，) 一( 移) + 入q 。( m 入 o 我们引入一个正则函数为： ，镯2 感烈，) + 入( 朋入 0 r 第l 章学习理论的基本框架 这样就形成了误差分解如下： ( 厶) 一咖( 彤) + a 盹( 厶) = p ( 厶) 一g ( 厶) + g ( ，确) 一( ，确) ) ( 1 1 3 ) + ( g ( ，z ) + a q z ( ，z ) 一( g ( ，确) + a q o ( ，溺) ) ) + 9 0 ( a ) 定义样本误差为： s ( z ，a ) ：= 妒( 厶) 一g ( 厶) + 露( ，确) 一( ，确) ) ， 用符号咒( z ，a ) 表示假设误差： n ( z ，a ) ：= g ( 厶) + a q z ( 厶) 一( g ( ，确) + a q o ( ，确) ) 值得注意的是厶与a ，确可能在不同的空间，即缆与瑙。这就是在样本依赖 假设空间分析假设误差的本质困难。最近，在样本空间的学习引起了广泛关 注【7 3 7 4 , 7 6 1 。特别地，在u 3 中，作者发现了线性规划支持向量机与传统的支持向 量机有着紧密的联系。 1 4 容量依赖与容量独立 在学习理论中，为研究样本误差，通常我们需要考虑一系列随机变量， 如算法( 1 6 ) 中的，z ，a 和( 1 1 2 ) 中的厶。这就要求我们要估计相应假设空问的 容量。在此背景下，引入了许多概念来刻画函数空间的复杂度，常用的有： 熵【鲫，v c 维数【1 8 , 6 7 , 6 8 ，k 维数【3 ，2 0 】，r a d e m a c h e r 复杂度【6 5 】以及各种形式的覆 盖数【8 2 1 。就我们所知，覆盖数研究的最深入，也得到了较理想的估计。关于复 杂度的研究不是本文的重点，我们只考虑用覆盖数来衡量函数空间的复杂度。 定义1 3 令( 彩，d ) 是一个伪度量空间，s 是彩一个子集。对于e 0 ，s 的覆盖 数( s ；e ；d ) 定义为以为半径的球体覆盖s 的最小球体个数。即 r z 、 a f ( s ；e ；d ) = m i n z 斟：scu b ( 彤，) 对于某一个 s t ) 名lc 彩 ， l j = 1 j 其中曰( 彤，) = s 彩，d ( s i ，s ) ) 是彩一个球体。 令厂为定义在z 上的实函数集合，用三o 。度量来定义厂的一致覆盖 数( 歹，) 。现在我们给出一个关于一致收敛的概率不等式。一种概率不 等式研究研究的很成熟，具体可以参看文献【2 ，3 1 。 o 第1 章学习理论的基本框架 命题1 3 令厂为定义在从z 到【o ，引上的实函数集合那么 p 砌 溜阿一去娄，c 圳 w c 厂，詈) 唧 在学 - j 理论空问内，也存在独立于容量的研究误差分析的方法，如稳定 性分析【9 1 ，剔除一样本分析【7 9 】以及最近出现的弹性网格正则化m 】。粗略的说， 容量对立方法对应与容量依赖的“最坏的 情形。简单有效的方法可以通过积 分算法来实现。一般情况下，容量独立方法严格依赖于算法的结构，如线性， 拟线性或二次型规划。但不管怎样，在对误差分析精度不是太高的情况下，容 量独立是一种非常简单有效的方法。相关讨论请参考文献f 5 5 1 。 1 5 无界情形下的学习 在回归问题下，我们定义一个输入空间x 和一个输出空间y 。令x 是一个 可度量空间，y = r 。令p 表示定义在xxy 上的b o r e l 概率测度。我们假定样 本集z = ( x i ，y i ) 罂1 独立的抽取自p ，回归函数定义为： ，- l ( x ) = ly d p ( 可 z ) ，z x ， ( 1 1 4 ) l ，y 其中j d ( i x ) 是由p 诱导的条件分布。回归学习的目的是基于样本构造一个学习 器厶，使得厶能很好的预测厶。 在机器学习中研究最为广泛是当属正则化最小二乘算法： 一 m 五，卜a r g ，m 啡i n - - m 1f = ( i ( x , ) 一犰) 2 + , x l l f l l ；r ( 1 1 5 ) 对于算法( 1 1 5 ) 的误差分析，已经有许多学习理论方面的工作，见【1 1 , 4 1 , 5 5 5 9 7 5 ，鲫。 研究最多的标准假设是输出样本是有界的，即对于某一正数m ，川m 。也就 是说条件分布j d ( i x ) 的支撑集包含在卜m ，m 】中。可是，这种假设与许多现实 数据相背离，在参考文献【1 l ，7 0 】中抛弃了这一假设。这里我给出一个有关样本 的一般假设。 矩假设：假设存在常数m 0 和c 0 使得 l y l 2 d p ( i z ) c g , ! m 2 v2 z n ， vz x ( 1 1 6 ) ，y 下面我举出两个常见的例子以结束本节的讨论。 1 n 第1 章学习理论的基本框架 例1 令b 0 和b o 0 。如果对于每个z x ，l 厶( z ) l b 和条件分 布j d ( i z ) 是一个正态分布，并且方差满足b o ，那么( 2 2 ) 结论是满足的， 取m = m a x 以玩，召) a n dc = 4 。 例2 如果对于每个z x ，条件分布p ( i x ) 有指数型密度函数婴掣定 义在 o ，o o 】以及等于0 在( 一。o ，o ) ，其中0 0 ，有 i 1 2 d p ( i z ) c g ! m 2 v 2 z n ，v x x ，( 2 2 ) ，y 本章的第一个任务是，当厶属于咒时，在咒k 的度量中得到f | 丘，a l i i , , 的误 差精度。第二个任务是为误差分析i i 厶，入一l i i l ；x 提供一个容量依赖的分析方 法。值得提出的是我们的分析主要通过积分算法技术实现的。 2 2 有关r h k s 的性质和假设 要研究学习理论的收敛阶，首先需要对回归函数厶一定的光滑性假 设，这里采用的是：厶在l k 的值域里，对于某一正数r 0 。事实上，如 果r 1 2 ，l 女的图像包含于h k 中。因此l 厶l ；x 表明厶在l k 的值域里， 是度量回归函数光滑性的。另外，我们引入一个刻画函数空间的假设：假设存 在c 1 l 和s ( 0 ，1 使得 l i f l l q i l f l l 女。l i ，l | 磊： v ，冗k ( 2 3 ) 对于c l = k 和s = 1 ，假设条件( 2 3 ) 是恒成立的。但是一般比较感兴趣的 是s 1 ，和p ( 1 2 q ) l 。那么但功成立，其中s = 呈学 和q 是一个依赖于弘g ，c o ，c o ，d 1 和i i k ( z ，z ) l i o 。的常数 注意到当口= 0 时，即相应的特征函数是一致有界的，那么我们的结果是 与f 4 l 】的引理5 1 是一致的。可是这并不能作为( 4 1 l 的推广，既然我们要