（基础数学专业论文）再生核与一般核背景下学习理论问题的研究.pdf

再生核与一般核背景下学习理论问题的研究 摘要 本文一方面研究了学习理论中以再生核h i l b e n 空闻为背景的最小二乘估计子的上界估 计问题另一方面当假设窄问与样本有关时对基于正则化系数的学习理论首先估计了以再 生核h i l b e r t 空间为背景的一般假设双么a ) 的界，然后引入了一种新的更为普遍的方法给出 了以一般核为背景的一般假设砟，1 ) 的界从结构上将本文分为三章 第一章为绪论 第二章研究了学习理论中以再生核h i l b e n 空间为背景的最小二乘估计子的上界及相关 问题 第三章当假设空间与样本有关时，对基于正则化系数的学习理论首先估计了以再生核 h i l b e r t 空间为背景的一般假没尹( z ，1 ) 的界，继而引入了一种新的更为普遍的算法并给出了 以一般核为背景的一般假设乒) ( z ，t ) 的界 关键词学习理论；监督学习理论；最小二乘估计子；算法；误差分解；再生核空间；覆 盖数；熵数 t h el e a r n i n gt h e o r yb a s e do nt h er e p r o d u c i n gk e r n e la n d g e n e r a lk e r n e l a b s t r a c t o nh a n d ，t h i sp a p e re s t i m a t et h eu p p e rb o u n do ft h el e a s ts q u a r e se s t i m a t o rw i t ht h er e p r o d u c i n gk e m e lh i l b c r ts p a c ei nl e a m i n gt h e o 巧o nt h eo t h e rh a n d ，w h e nt h eh y p o t h e s i ss p a c e d e p e n do nt h es a m p l e ，t ot h el e a m i n gt h e o u o fc o e f l i c i e n tb a s e dr e g u l a r i z a t i o nw i t ht h er e p r o d u c i n gk e m e l ，w e 五r s te s t i m a t et l eb o u n do ft h eg e n e 豫lh y p o t h e s i s 尹( z ， ) i nt h er e p r o d u c i n gk e m e l h ) e r ts p a c e ，t h e nw ep r o p o s ean e w1 e a m i n ga l g o t h mt oe s t i m a t et h eb o u n do f 尹( ：，1 ) w h e n t h er e p r o d u c i n gk e m e lb e c o m e sag e n e r a lk e m e l t h i sp a p e ri sd i v i d e di n t ot h r e ec h 印t e r s i nt h ef i r s tc h a p t e r w eg i v et h ep r e f a c e i nt h es e c o n dc h a p t e r ，w ee s t i m a t et h eu p p e rb o u n do ft h el e a s ts q u a r e se s t i m a t o rw i t ht h e r e p r o d u c i n gk e m e lh i l b e r ts p a c ei ni e a m i n gt h e o 巧 i nt h et h i r dc h a p t e r ，丘r s tw ee s t i m a t et h eb o u n do ft h eg e n e f a lh y p o t h e s i s 双z ，t ) i nt h er 印r 0 - d u c i n gk e t t l e lh i l b 鲥s p a c e ，t h e nw ep r o p o s ean e wl e a m i n ga l g o r i t h mt 0e s t i m a t et h eb o u n d0 f 尹( z ，t ) w h e nt h er e p r o d u c i n gk e m e l b e c o m e sag e n e r a lk e m e i k e yw o r d ss u p e r v i s e dl e a m i n gt h e o w ；t h el e a s ts q u a r e se s t i m a t o r ；a l g o r i t h m ；啪rd e c o m p o s i t i o n ；t h er e p r o d u c i n gk e m e lh i l b e r ts p a c e ；c o v e r i n gn u m b e r ；t l l ee n t r o p yn u m b e r s 原创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得丕望竖垫盘茎或其它教育机构 的学位或汪书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 即： 论文作者签名趣修同期：刃加年么月7 r 研究生学位论文使用授权说明 ( 必须装订在提交学校图j 转馆的印刷本) 本人完拿了解天津师范大学关于收集、保存、使用研究生学位论文的规定， 按照学校要求向图书馆提交学位论文的印刷本和电子版本； 图书馆有权保存学位论文的印刷本和电子版，并通过校园网向本校渎者 提供全文与阅览服务。 图书馆可以采用数字化或其它手段保存论文； 因某种特殊原因需要延迟发布学位论文，按学位论文保密规定处理，保 密论文在解密后遵守此规定。 论鬻签三纛了月，咋裳叩同期：，埘年石月 h l 第一章绪论 学习理论作为函数逼近理论和概率统计理论等诸多研究方向的交叉学科，近年来受到了 广泛关注，成为函数逼近理论研究的热点问题本文对由c u c k e r 和s m a l e 提出的监督学习中 的一些问题进行了进一步研究下面简单介绍本文的内容 没 xc 础，yc r 。 x 与y 都是b o r e l 集，并且设p 是定义在 z = x y 的b o r e l 子集类上的概率测度对厂：x 一l 定义误差； 6 ( 厂) ：r 执x ) 一力：咖：厂叭x ) 一y ) 2 咖卅x ) 纸， j zj z 其中时l x ) 足指y 上( 相对于石) 的条件概率测度；m 为x 上的边界概率测度，即当sc 彳时， m 岱) = 以s y ) ， 这里仅考虑有界集合y ，故存在一个正则条件概率测度p ( i 功 定义刀( x ) 为j ，的相对于测度p ( l 工) 的条件期望即 删= 廊 函数厶( j ) 在数理统计学中被称为p 的回归函数 监督学习，或源自样本的学习，是指以已获得的输入数据而和对应的输出数据儿，f = l ，历为基础，建立一个能够很好地表达输入量工x 与对应输出量y 】，之闻关系的函 数其目的足以已给数据z ：= ( ( x i ，少i ) ，( ，) ) 为基础，找到一个估计子正，使其能够很 好地逼近概率测度p 的回归函数( 或其投影) 在许多情况下建立正的方法是提供一个几乎最优估计子其基本思路是：首先选择一 个恰当的假设空问爿，然后构造 正爿2a 唱爨骝6 = ( n ( 1 ) 作为经验最优最小二乘估计子其中： 6 二( n 一壶h 被称为厂的经验( 风险) 误差 目前在学习理论中( 【l 】【4 5 】) 中的惯用方法是，先选择一个函数类h 得到正m 再考虑其 对五在上的2 ( 纵) 投影厶：= 坼h 的逼近性质( 1 】，【2 】，【3 】，【5 】) ，这种情形被称为投影学 习问题研究中需要用到集合的熵数、覆盖数以及再生核空问的概念，我们分别给出其定义 对b a n a c h 空间8 的一个紧子集 ，其熵数定义如下： 磊c ，功：= i n f 占：瑚，五”。c 固+ s u c 剀) ， 其中叭b ) 是b a n a c h 空间口的闭单位球 以( ，s ，b ) 表示覆盖数，即利用球心在0 ，半径为s 的球体覆盖0 所需要的球体的最小 个数由定义知： ( 0 ，岛( 0 ，口) 。b ) 2 ” x 上的m e r c e r 核是一个连续且对称函数 k ：xxx _ r ， 而且这个函数是半正定的，即对任意的有限集合h ，娩，瓢jc 彳，以k ，x ，) 为对应元素 的矩阵k 嗍是半正定的 以k 为核的再生核h i l b e r t 空间7 奴( 见【6 】) 被定义为函数集合 魁五) ：工的元素的 线性组合张成的闭包，内积为 纸2 足， 满足 = f u c 、，飞x x ，f 吼k ， 其中巧( ) = 足( 以) ，同时再生核h i l b e n 空间元素的范数记为i i k 本文第二章就何是再生核h i l b e r t 空闻中满足邑( h l ( j d x ) ) d 胛。的有界闭凸集情形 做了一些研究，得到 定理1 设w 是再生核h i l b e r t 空间的有界闭凸集，同时v 厂纠，厂相对于概率测度，满 足i 以) 一y i m 口总，那么对v o ，有 矿 z ：姒w ) 一文庸) o ，a ( o ，l 】，有： 矿 z 翻一鼽二口( 卸+ 洲e x p ( 一番) ， 矿 z = 翻一勖二一口( 翻+ 训e x p ( 一番) ( 5 ) 利用分析的方法证明了 引理( 2 2 5 ) 对于定理l 中所给的何，p 设口( o ，1 ) ，s 0 ，且厂吖使得 错 0 ， 6 2 6 二u + s 一溉) + 2 ( 6 l 知) 一& ( 角) ) 的概率至少为 p ( 斜，s ) ：= l 一( 硝，南，c ( ) e x p ( 一意象) 综合以上各引理和定理证明了定理l ，从而得到了再生核h i l b e n 空间下的最小二乘估计 子的上界估计 相对于算法( 1 ) 在学习理论中得到六硝的更为普遍的方法为f 见【1 2 】f l3 1 【1 4 【15 】 【1 6 】，【1 7 】) ： 五纠2 口曙卿 邑+ l q l ， ( 2 ) 这里 & = 去，批，厂( 研) ) 是个经验风险函数，如果八x ) 是用来预测实际输出量y 的，则渺，厂( z ) ) ：尺2 凡是一个损 失度量函数a 是个非负正则化参数而 q ：纠r 是一个补偿泛函，通常满足 q ( 0 ) = o 当l = o 时，方法( 2 ) 就变成了经典的经验风险最小化( e r d 假设空间钟与补偿泛函q 的选择对于算法的性能是至关重要的【1 8 】，【1 9 】取假设空问 为研= ，补偿泛函q = i 们受，得到了了再生核h i l b e r t 空阎上的正则化算法 正= 口馏勰 6 z + 州哟- ( 3 ) 另外一部分文献选择的假设空间与补偿泛函仅仅依赖于样本的大小，w = 7 k 。，q = ”l l ， 相应的算法( 2 ) 就变成了 正= 口，苫恶咖 6 ：) + ，t | i ，1 i ( 4 ) j t 几点婀 如( 【2 0 】， 2 l 】，【2 2 】) 中取高斯核如( 工y ) = e x p 警 其中的参数满足伊= 町。，假设空问为 爿= 纸，埘，补偿泛函为q = l 们嚏，肼 4 本文第三章的主要目的足研究学习算法( 3 ) ，假设空间爿却足依赖于样本二的，而不仅 仅依赖于样本大小历也就是说，此时的假设空间为 硝= 牡， 而且补偿泛函也是与样本z 有关的 q = q ， 此时学习算法( 2 ) 就变成了如下形式 z = 口曙咖 & + g ( d ( 5 ) 一般地，对渺，厂( 石) ) ，称 期= e 妙，八枷= 上炒，八j ) 冲 为期望风险，且称 兵= a r gm i n 价 为目标函数，其中最小值是取遍了所有的可测函数获得的 泛化误差6 旺) 一6 ) 是衡量算法( 3 ) ，( 4 ) ，( 5 ) 中的正逼近疗效果的关键量，许多文章 如( 1 2 】，【1 3 】，【1 4 】，【1 5 】，【1 6 】，【1 7 】) 都对其作了研究对于算法( 3 ) 的情况，令 五，倒2 口厂g 爨瓣 6 十 q l ， 纠 那么础) 一6 昕) 有分解式 6 旺) 一6 圻) = 6 伍) 一矗旺) + i ( e 旺) + a q 旺) ) 一( 6 ：( 厶w ) + a q ( 厶州) ) + 芒毫己，= 1 w 一6 ( w ) + ( 厶w ) 一6 ( - 疗) + l q ( 以w ) 一l q 旺) ) 因为上是补偿经验风险的最小化子，所以有第二项 l ( ：u ) + a q 旺) ) 一( 6 ：w ) + l q u i w ) ) is0 ( 6 ) 而其它各项也都有成熟的估计方法而对于算法( 5 ) 的情况，相应的( 6 ) 式不再成立，出现了 本质的困难我们对( 5 ) 引用一种新的误差分解方法，为此先给出定义 定义1 称x 上的一个函数类。足对于算法( 5 ) 的一般性假设，如果 uu 凡 相应于的补偿泛函为翁与和骗相关的最小化子为 此时6 幔) 一6 忻) 有分解式： ，2n 曙魄 6 u ) + a q t l u ) ， ( 7 ) 6 旺) 一双序) = 旺) 一& 强) + ( t 旺) + l q 幔) ) 一( 二( 五) + l q o 蛹饥， ) + & ) 一双 ) + ) 一双矿) + l m 巩) l q ：( ) 在分解式中除第二项外均容易估计( 见正文) ，而估计第二项的关键是适当选择( 梳，) 对于 核为k 的再生核h i l b e r t 空间，如果给出样本，x ：， ，则没与样本有关的段没空问为 = 五：删= 喜皑啉一c 川卜 _ i， 此时( 5 ) 式化为 z = 口，g 觑：f 8 ：) + q ) ( 9 ) 此时q = 翟ls 位f ) ，对任意的厂= 竺，a t 办t 鲰：这里s ：尺_ 只+ 是偶函数且在 【o ，+ o o ) 上单调不减- 取= ，= 喇们喷，y ，7 o ，且设= 私为了避免混 淆，将( 3 ) 的解记为厶，即 厶。孵勰 矗+ p 轧 令 五= 一魄 鲫+ 例沁 在上述假没下讨论误差分解中的第二项，我们得到 定理3 2 1 设z z ”假定对于某些庸 0 ，几乎处处有m ，o ) 府如果存在两个非负 常量c l = c 1 0 ，朋) 和c 2 = c 2 缸，用) 使得 q ( 岛) = s ( 叫5c 一奠吗) + q 蚓缸 ，= l 并且，7 满足叩鲁，也就是“若苦) ，那么 ( 酋旺) + l q l ) ) 一( 妨丘) + f 1 1 | i ；) c j 庸 6 以上基于正则化系数的学习算法中的再生核k 可以用一搬核来代替假设k ：x x j r 是连续的，可以考虑b a n a c h 空间是由所有如下形式函数，构成的 厂( x ) = 嘶k ( ，x ) x ， ，= 1 范数规定为 i i 门i = i n f i 口，l ：八石) = a ，k ( x ；，x ) ，x 佶l ，= i ， 很容易验证罗泛能够嵌入到c ( ，并且 们i 。必i i 门i ，v - 厂于k ， 这里贡= 胍，另外对于v z ，有倒比及因此对于给出样本娩， ，我们假 设与样本有关的假设空间由( 8 ) 式给出，且给出算法： z 一舰m + 五静p ， 再定义 = 斥，骗= 嗍 那么相应的 五= 口r g 碰 6 + a 删l 另外我们假设损失函数，杪，八x ) ) 具有局部l i p s c h i t z 性，即对于y 8 o ，存在( 8 ) ，使得 i 桫， ( x ) ) 一时，烈工) ) l ( 8 ) l 厂( x ) 一烈x ) 1 对于慨x 以及v ，g 满足i 【1 i ，心i b 很明显( 8 ) 是递增的，并且这里假设( 占) 足右 连续 定义给定一个点集 x l ，砭， 置如果对于每一个工z 存在着某一个1 f 肌 使得 ( ，( x ，丑) s ， 那么这个点集，娩，x 。 就被称作是一稠密的 定理3 2 如果，娩， 在x 中足一稠密的，那么当l p = “s n ， 这里仅考虑有界集合y ，故存在一个正则条件概率测度p ( l 工) 定义五( x ) 为 的相对于测度p ( - 协) 的条件期望即 删= 上廊 2 函数五( 工) 在数理统计学中被称为p 的回归函数 引理( 2 1 1 ) ：如果五( x ) 工2 ( 瓜) ，那么五使得误差双介达到最小 证明：对町2 帆) ， 嘲= 如炉”2 和 ：r 0 i x ) 一后( x ) + 石( 曲一y ) z 和 z = 上( ，i x ) 一z ，( 工) ) ! 和( x ) + j ! ：上( 乃( x ) 一j ，) 2 “p d i 工咖( j ) + 2 j ：上( 厂( x ) 一z ( x ) ) ( ( 工) 一少) 咖- i z ) p ( j ) = 毋似) 一崩州2 和( 卅，( 伽) 刊锄吣) 在第四个等式中，第二项恒不为负；而当厂( x ) = 后( x ) 时， 上( 八二) 一( x ) ) 2 p ( x ) = 。 因此有对任意的厶( 一) 毛2 ( j ) 。) ，有 6 ( f ，) 双厂) 结论得证 因此在误差的意义下，回归函数后能够最好的描述输入量x x 与输出量y y 之 间的关系而现在的任务是在给定的数据z = ( ( 石l ，y i ) ，( ，乃，) ) 的基础上，找到一个估计 子正能够以很大的概率逼近厶( 或它的投影) 这其巾要假设( x ， ) f = l ，2 。，m 按慨率测 度p 独立同分布 3 按照如下在逼近论中已形成的标准且在学习理论中( 【l 】 4 】【5 ) 已使用过的力法，首 先选择一个函数类( 在【2 】巾被称为假设空问爿) ，再考虑对在上的2 p a ) 投影 向：= 坼) 的逼近研究( 【1 【2 】，【3 】， 5 】) 这种情形被称为投影学习问题 4 本研究中还需用到熵数及相应覆盖数的定义对b a n a c h 空间8 的一个紧子集o ，其 熵数定义如下： 。c 。，口，：= i n f s ： 忻，刀。c 固l 6 + s u c b ，) ， 其中矾占) 是b a n a c h 空间b 的闭单位球 以j v ( o ，s ，b ) 表示覆盖数，即球心在0 ，半径为s 的能够覆盖住o 的所需球体的最小个 数。由定义知： ( o ，6 ，( 0 ，口) ，占) s2 ” 5 在许多情况下建立z 的方法是提供一个几乎最优估计子首先，选择一个恰当的假设 空间爿( 可能与。有关) 接着构造正纠作为经验最优( 最小二乘) 估计子： 正w ：= a 唱爨骋爱 其中： 6 ：= 二f ( ，u 卜y f ) 2 “i = 被称为门拘经验( 风险) 误差于足很自然的通过耻) 一6 ( 石) 来描述逼近的性能，其值为： 引理( 2 1 2 ) ：对任意的：轨) ， 6 ( 门一双彳，) = 1 1 厂一厶吃j ) 证明： 6 一6 圻) = f ( i 工) 一和y 和州x ) 一f 坼，( x ) 一y ) 2 咖和 卜) j zj z 1 0 ： i ) 一，( 工) ) ( i z ) + ，( ) 一砂) ( 1 p 砌，抄l 工) ：厂( i j ) 一力( j ) ) ( ( 彳) + 力( x ) 一2 ( j ) ) z p x = p 一胁) ) 2 咖 结论证毕 6 以下是学习理论中要用到的经典的b e m s t e i n 不等式：如果f 是z 上的一个随机变量， 那么记 ( f ) ：= 易( 亭) ：= ff 咖 j z ，( f ) ：= f ( f e ( 手) ) 2 和 t ，z 对每一个随机变量f ，有以下概率形式的b e m s t e i n 不等式：如果 那么对任意的 o 有 敝z ) 一e ( f ) l 朋口。p 。也。p i 去喜鬏z ，一c 手，l s ) 2 e x p ( 一蔫) ， 其中z ：= ( z l ，z 。) ，下面是对应的单边不等式 触。p 矧咽北s 卜p ( 一蒜禹) ， 尸，。阮。 刍喜鼠：，一c f ，s s e x p ( 一三i 蠢) ， 且本文对函数类形作如下假设 5 ，( 肜b ) d 聆一， 形cd 矾占) 7 下面介绍一些再生核h i l b e n 空间的相关知识 x 上的m e r c e r 核足一个连续，对称函数 k ：x x 叫尺 而且这个函数是半正定的，即对任意的有限集合t 2 瓢jcx ，以k ( 五，_ ) 为对应元素 的矩阵k 【棚是半正定的 以k 为核的再生核h i l b e n 空问【6 】7 k 就被定义为函数集合 k ( x ，) ：工加的元素的 线性组合张成的闭包内积为 讯= x ， 满足 = ，i x ) ，v j f x 吖k ， c ( 表示连续函数空间，范数为 ， 同时再生核h i l b e n 空问的范数记为 1 1 忆 设 必= s u p 而， x e x 那么由再生核性质知 刀i 。9 r | | 1 l k ，v 厂7 k 因此讯ca 加，且的任一有界闭集万同时是c ( 的有界集 2 2 主要结论及证明 相对于之前定义的上钟，这里给出厶的定义： a ：2a r g 嘞6 定理l 若纠是再生核h i l b c n 空问的有界闭凸集，同时v 爿满足叭x ) 一卅m 口息 相对于概率测度p 那么对v s o ，有 矿 z ：幔，爿) 一s 嗍) k l | i 五k k ( x ，石) 一2 k ( x ，y ) + k ，y ) 】；，( 牢) 丽由k ( l 少) 的连续性知，对v 占 0 ，粥 0 ，只要k 一川 6 就有 l k ( r ，曲一k ( x ，力i o ，当l x 一叫6 时，有 l 五( j ) 磊o ) i 差， 下面设x = 【口，6 ( 其它情况证明类似) ，取正整数m 使得等 6 ，把闭区问k 6 】进行肌 等分分点记为 口= i x i j f 2 时，对v j ，6 】有某j f ，6 】使 i x 一i i 岍一 忆， 因此肠足惟一的此外( 1 ) 式给出了 | 一 吃咿一删乞一j 忻崩吃= 双厂) 双角) 1 4 定理得证 为了下面证明的方便给出以下记号： 6 ( 爿) ：= 双a ) 一6 ( 后) = l 【砌一彳，略 ：= 6 一6 魄) ； 锄：= 6 ：一6 ：晚) ； ，( 介：= ，c f 三) ：= l 厂( x ) 一) ，) 2 一( 局l ，( x ) 一j ，) 2 ，z = ( 石。力， 同时对一般的 ，我们也记 芒靖= b ( ，z ) ) ， 锄：= 去u 孔，玎厶一 引理( 2 2 3 ) 对于定理l 中所给的爿，有 o r 2 ：= ，( ，) 4 铆 证明： ，( ，) se ( u ) 2 ) = e u i x ) 一崩( x ) ) 2 0 r ( x ) + 厶( 曲一z y ) 2 4 e ( ( 厂i 工) 一詹( 工) ) 2 ) = 4 l 扩一崩眩 4 严啊( ) 从而结论得证 引理( 2 2 4 ) 对于定理1 中所给的爿，以及v 硝对任意的s o ，口( o ，l 】，有： ：= 翻一翻：姒翻( ，) + 训e x p ( 一等) ， 一z ：翻一翻) 川( 翻( 力+ s ) e x p ( 一案) 证明：记口：= 6 坩u ) 那么口o 以上两个不等式的证明是相同的，故在这里仅证明第 一个不等式对，( 力使用单边b e m s l e i n 不等式得： 肚：翻( n 一卸朋独t 胚唧( 一驴等篆) ， 接下来就需要证明： 2 ( ( 厂2 + l 尹a ( 口+ 占) 3 ) 一5 解 l “+ s s 使用引理( 2 2 3 ) 得，一方面： 2 d o r 2 + 严口( 口+ s ) 3 ) s 严d 9 口+ 2 s 3 ) 另一方面： 5 m 2 ( + s ) 2 严s ( 1 0 口+ 5 s ) 比较以上两式就可以得到所要证明的不等式 引理( 2 2 5 ) 对于定理l 中所给的爿，j d 设口( o ，1 ) ，s 0 ，且甜使得 翻( 门一卸： 石丽瓦一锄 那么对于任意的g 纠，只要i l 厂一翻i “舯s 口s 4 m 就有： 鱼望二鱼三塑 2 口： 6 爿( g ) + s 一 证明：记 口：= 白，口：= 翻 ) ，6 ：= 卸j ，6 ，：= 卸二 那么条件中的假设i i 厂一翻i a 船4 m 意味着： 陋一口7 i 口s 2 ，眵一6 7 i 口2 ， 由( 2 ) 和( 4 ) 式得( 口0 ) ： 口( 1 一口) l 一p ( 一署) 现在取任意的z 人和g 舛设乃使得 憎一石0 c 的雌4 m ， 那么由引理( 2 2 5 ) 可以得到 6 w 悖) 一w 。留) ， 瓦西i - “虬 反过来再一次运用( 7 ) 式，从而定理得证 定理3 假设w ，p 满足定理l 中的条件，那么对任意的甜，s o 6 2 6 ：十一姒) + 2 ( 8 0 白) 一6 ：l 助) )( 8 ) 的概率至少为 删：= l 一( w ，南，c ) e x p ( 一赤) 证明：对于定理2 ，当盯= 时，得 的概率至少为p ( 啊，s ) ，将以下两式 断 2 翻= + s 翻( - n ：= 6 一5 厶) ；翻：( 力：= & 一6 ：( 庸) ， 带入上式，得到( 8 ) ，从而结论得证 推论l 在定理3 的假设条件下，有 & l 砌) 一：u 洲) s 2 1 7 ( 9 ) 的概率至少为p ( 啊，s ) 关于推论l 的证明读者可以参考文献【7 】 接下来的任务就足对于定理l 的证观 证明：首先取= z 。w ，那么由其定义可以知道 将厂= 啊代入到( 9 ) 式中得 6 恍旺州) ：= 6 ：旺纠) 一& ( 觑) o ， 翻w ) = 6 幔纠) 一6 魄) 2 芒啊：旺珂) + = 2 & 旺w ) 一2 疋魄) + s 进而得到( 8 ) 式接下来运用定理3 得6 u w ) 一6 嘞) s 的概率至少为 t 一( 何，南，c ) e x p ( 一盎) 即 f ：6 ( 纠一6 嗍) 曲l l 一( w ，南，c ) e x p ( 一蒜) 从而定理l 得证 1 8 第三章与样本相关情况下基于正则化系数的学习理论 3 1 预备知识及介绍 在学习理论中，一种使用非常广泛的方法是正则化，也称为经验风险最小化( 【9 】，【l o 】，【l l 】) 这种方法，给定一个输入度量空间x 和一个输出度量空间yc 尺，还有一个样本z = ( 工i ，巾 墨。 ( x x 秽，这些样本独立且按集合z = x y 上的未知概率测度p 同分布从x 到y 的函数集 合甜( 称为假没空闻) 中寻找一个函数工使得 正= 口馏凳骋 & + a q l ， ( 1 ) 这里 龟= 去秘删 足一个经验风险函数，如果八工) 是用来预测实际输出量y 的，则妙，厂( x ) ) ：尺2 _ 凡是一个损 失度量函数l 是一个非负正则化参数而 q ：爿_ 足+ 是个补偿泛函，通常满足 q ( 0 ) = o 当五= o 时，方法( i ) 就变成了经典的经验风险最小化( 丘r 加 许多以( 1 ) 为背景的学习算法，使用的是具体的损失函数，假设空间和补偿泛函，如正则 化网络f l l 】，支持向量机 1 2 】损失函数的选择通常依赖于具体的学习问题，如回归问题的最 小二乘方损失 u 以工) ) = 杪一八x ) ) 2 ， 和支持向量机中的 b ，八x ) ) = ( 1 一j 以x ) ) + 许多文章都对算法( 1 ) 的泛化性感兴趣，而本部分的一个目的就是给泛化误差 6 幔) 昕) 一个界，其中 鲫= 炒，八圳；上炒，八枷和 1 9 称为期望风险且 = n r gm i n 烈n 被称为目标函数，其中最小值是取遍了所有的可测函数获得的对于泛化误差界这个问题 在诸多文献中已经引起了足够的重视，其中损失函数，假设空间和补充泛函具体可见文献 ( 【1 3 】， 1 4 】，【1 5 】，【1 6 】， 1 7 】， 1 8 】) 而这其中最重要的情况是与m e r c e r 核相关的再生核h i l b e r t 空间 6 】与一般核的正则化问题 假设空间h 与补偿泛函q 的选择对于算法的性能是至关重要的选择假设空间爿的经 典方法是首先要了解样本分布p 的一些先验知识这种情况下假设空间啊与样本无关典型 的例子是在线性回归中的线性函数集合，如下例： 设k 是集合x 上的一个再生核，假设空问取为 何= ， 补偿泛函取为 q = l 们良。 那么算法( 1 ) 就变成了再生核h i i b e n 空间的正则化算法( 【1 9 】，【2 0 】) 正= 口r g 髋f z + 五l 啡l ( 2 ) 另外一种方法更多的是关注假设空间对数据的拟合很大一部分文献中选择假设空间与 补偿泛函仅仅是根据样本的大小 爿= ，q = ， 相应的算法( 1 ) 就变成了 z = 口曙册 & + a ( 3 ) 一个典型的椤l l 子是根据样本大小确定核的参数，如高斯核( 【2 1 ， 2 2 】，2 3 】) 帅加e x p 一譬) 其中的参数满足 矿5 “， 假设空间为 纠= 。， 补偿泛函为 q = 己 已知文献中几乎所有关于算法( 1 ) 的误差分析结果都集中于( 3 ) ，其中样本要么与样本无 关，要么仅与样本大小研有关通常误差界的获得足通过平衡样本( 估计) 误差与逼近误差，这 其中就需要根据样本的大小珊选择合适的参数即使假设空间依赖于样本大小，误差分析依 然首先要固定一个参数化了的假设空间，接着使参数最优化以上论文研究中的假设空间足 仅仅依赖于样本大小聊的 而奉部分的主要目的是研究学习算法( 1 ) ，假设空问爿却足依赖于样本z 的，而不仅仅 农赖于样本大小m 也就足说，此时的假设空间为 甜= 他， 而且补偿泛函也是与样本z 有关的 q = q ， 此时学习算法( 1 ) 就变成了如下形式 石= 口，g 珊 & + 五q ( 4 ) 对于这种形式学习算法的具体例子如下： 设xc 彤，格( 五力= e x p 一譬) ，其中o 矿 o ，能够给出 ( 龟( ) + l q u ) ) 一( 6 ：坼) + p g ，( 肋) ( 1 1 ) 2 4 的界，那么误差分解( 1 0 ) 就可以给出令人满意的误差界这里为了给出上的补偿泛函虢， 必须要紧密联系咒上的补偿泛函q 3 2 主要结论及证明 一再生核h i l b e r t 空间下基于正则化系数的学习理论 在给定半正定核k ：x 一尺的情况下，可以生成一个再生核h i l b e n 空问，这个时候 如果给出样本 j f l ，娩， ，那么可以直接给出与样本有关的假设空间 ：= 厶：胁，= 姜撇h 娟一叫 ， f _ l ， 当假设空间为巩j 时，基于正则化参数的学习算法就是 正= 丘= 口r g 晨熟 6 ：魄) + q 魄) ) ( 1 3 ) 此时q = 墨ls ( 口f ) ，对任意的= 翟lo f f 7 k ：这里s ：尺_ 凡足偶函数且在 【o ，+ o o ) 上单调不减对于这种与样本有关的算法，可直接令 = 讯， 补偿泛函可以选为 b = ，7 儿门i 之，v 7 k ，7 7 o ， 很明显 uu ， 所以7 而是一个一般假设 接下来为了使误差分解( 1 0 ) 有意义，需要首先对假设误差尹( z ， ) 进行估计，为此需要将 式( 1 3 ) 和式( 2 ) 相联系 设= 私为了避免混淆，将( 2 ) 的解记为己，即 巴= 口，g 嬲 & ( 厂) + 川i 州毛 ( 1 4 ) 给出厶的目的就是为了建立正与j ，：1 = 石之间的联系 石= “厂g 舰 6 ( 厂) + 川慨 之前的文献( 【1 9 】，【2 0 】) 已经得到了：当r = ( r l ，t 。) r ”时i 岛= 丘因此将f 与巴 进行比较就有可能了另外五是不受数据限制的巴! 奠下的结果给出了令人满意的假设误差 界 2 5 命题3 2 1 设= 假定对于某些肪 o ，几乎处处有心t ，o ) 廊如果存在两个非负 常量c i = c l ，m ) 和c 2 = q 姐，加) 使得 q 吗) = s ( c ，) 冬c i & 嵋。) + q | | 巴。眩， ( 1 5 ) f = l 并且，7 满足，72 惫，也就是m 芒苦) ，那么 ( 6 = 幔) + a q ( ) ) 一( 疋坼) + 川帆幢) i c l 府 证明：由厶：可得 龟) + l q 旺) 盆l 乙) + t q u 乙) ， 由条件( 1 5 ) 式以及对_ 7 的假设得： 但是 并且 所以 & l 已) + a q l 厶) ( 1 + a c l ) 6 二l 厶) + a c 2 i i 厶0 乏 = ( 1 + 码) 俺呜) + 高l 略l l ；) ( 1 + l c i ) ( 邑u 乙) + p i d 毛女) 邑l 厶) + l 乙i 唼s6 2 ( o ) + o 庸， 最( 己) + i i z o i l 乏6 ：坼) + p i 帆0 乏， ( 岔( 正) + a q ( - ) ) 一( 6 ：( ) + | i ；) s ( e 旺) 十l q ) ) 一( 毒l 二) + p l i 。i i ；) l c l m 则结论证得 从命题2 1 来看，当( 1 5 ) 式成立时，尹( z ，a ) c l 肘，因而对于算法( 1 3 ) 的误差分解的关 键是式( 1 5 ) 那种形式的不等式成立，另外为了保证假设误差的界l f i 肘有效，可以选择适当 的川以使得当m _ o o 时，i c t _ o 从已有的文献来看在大多数情况下，这是可以做到的 二一般核下基于正则化系数的学习理论 以上系数基于正则化系数的学习算法中的再生核k 可以用般核来代替，这样当能够获 得关于数据的先验知识或者希攀按某种形式：拟合数据时，这种般核的方法就会很有用 也设这个一般核为k 2 6 当使用一般核k 的时候，一个h i i b e r t 空问可能就不足以估计一个逼近误差但是可以利 用关于核k 的一个b a n a c h 空间 假设k ：x x - r 屉连