（概率论与数理统计专业论文）基于核的正则化学习算法.pdf

摘要 摘要 学习理论是机器学习算法的数学基础它在许多科学技术领域中都有着重 要的应用在这篇论文中，我们主要考虑基于核的正则化学习算法像支持向量 机这样采用凸损失函数和再生核希尔伯特空间的t i k l l o n o v 正则化方法已在文献 中有较多的研究；而本文中我们将引入一些非标准的框架，并对新框架下的算法 作深入的分析 首先，我们将讨论带有z 1 正则项的回归算法这一算法的假设空间是依赖 于数据样本的，并且可以使用非对称的核函数样本相关的假设空间将为误差分 析带来一项额外的假设误差，这一点与通常情况下样本无关的假设空间有本质 的区别在对正则化误差、样本误差和假设误差分别进行估计之后，我们得到了 误差的完整估计，这一误差与核函数的性质、输入空间、边缘分布密度、以及回 归问题的回归函数有关在选定合适的正则化参数之后，我们获得了学习算法的 学习率在核函数为欧氏空间上的高阶光滑函数时，z 1 正则化算法的学习率还可 以进一步改进 其次，我们分析了从非一致概率测度中抽样的二分类问题这里的主要目标 是要对分类器的额外分类误差给出令人满意的估计，而我们的结果表明非一致 抽样与独立同分布抽样的情形是类似的同时，通过一个关于多分类器误差分析 的比较定理，我们还可以对多分类问题作出误差估计 最后，我们考虑了z 1 正则化方法带来的稀疏性，这一问题最近引起了研究 人员的广泛注意这里，我们在理论和应用方面都给出了一些讨论，以供将来进 一步研究 关键词：学习理论核方法正则化 a b s t r a c t l e 锄i n gm e o 口i sm em a m e m a t i c a lf o u n d a t i o nf o rm a m n e 1 e a r n i n ga l g o n m m s w h i c hh a v ei m p o r t a n ta p p l i c 撕o n si nm 觚ya r e a so fs c i e n c ea n dt e c h n o l o g y 1 nm l s m e s i s ，w em a i n l yc o n s i d e rl e a m i n ga l g o r i m m si m ，o l v m gk e m e lb a s e dr e g u l a n z a t l o n s c h e r n e s w h i l ea l g o r i t h m sl i k es u p p o r t v e c t o rm a c h i n eg i v e nb yt i k h o n o vr e g u l 小 i z a t i o ns c h e m e sa s s o c i a t e dw i 也c o n v e x1 0 s sf u n c t i o n sa n dr e p r o d u c i n g k e m e lh 1 l b e n s p a c e sh a v e b e e ne x t e n s i v e l ys t u d i e di nm e 1 i t e r a t u f e ，w ei 眦o d u c es o m en o n 。s t 狃d a r d s e t t i n g sa n dp r o v i d ei n s i 曲t f h la i l a l y s i sf o r m e m f i r s y w es t u d yar e g r e s s i o na l g o r i t h mw i m z 1r e g u l a r i z e rs t a t e dmah y p o m e s i ss p a c e 吼i n e df r o md a t ao rs 锄p l e sb yan o n s y i i l i 】t r i ck e m e lt h e d a t ad e p e n _ d e n tn a t u r eo ft h ea l g o r i m ml e a d st oa ne x t r ae r r o rt e 肌c a l l e dh y p o 血e s i se r r o r w h l c h i se s s e n t i a l l ，d i f ! f 色r e l l tf r o mr e g u l a r i z a t i o ns c h e m e sw i t hd a t ai n d e p e n d e n t h y p o t h e s l s s p a c e s b yd e a l l n gw i mr e g u l a i i z a t i o ne 玎0 r s 锄p l e e r r o ra n dh y p o m e s l se r r o r ，w ee s t i m a t em et o t a le r r o ri nt e 册so fp r o p e n i e so fm ek e m e l ，m ei n p u ts p a c e ，t h em a r g m a l d i s t r i b u t i o n ，a n dm er e g r e s s i o n 缸l c t i o no ft h er e g r e s s i o np r o b l e m - l e a r n l n g 联此s a r e d e r i v e db yc h o o s i n gs u i t a b l ev a l u e so fm er e g u l a r i z a t i o np a r a m e t e r a ni m p r o v e d e r r o r d e c o n l p o s i t i o na p p r o a c hi su s e di n0 u rd a t ad e p e n d e n t s e t t i n g s e c o n d l v w ec o n s i d e rt h eb i n a r yc l a s s i f i c 撕o np r o b l e mb y l e a r 【l i n gf r o ms 锄p l e s d r a w nn o man o n i d e n t i c a ls e q u e n c eo fp r o b a b i l i t ym e a s u r e s o u rm a l ng o a 王1 st 0 p r o v i d es a t i s f a c t 0 巧e s t i m a t e sf o rm ee x c e s sm i s c l a s s i 丘c a t i o n e r r o ro fm ep r o d u c e d c l a s s m e r s s i m i l a rr e s u l t sc a nb eo b t a j n e df o rm u l t i c l a s sc l a s s i f l c a t i o nb e c a u s ew e g i v eac o m p a r i s o nt h e o r yf o re n d ra n a l y s i so fm u l t i - c l a s sc l a s s i f i e r s f i n a l l y w ec o n s i d e rt h es p a r s i t yi s s u ef o rz 1r e g u l a r i z a t i o ns c h e m e s i h l s t o p l c h a sa t t r a c t e dal o to fa t t e n t i o nr e c e n n ya n dw eg i v es o m e d i s c u s s i o nf o rf u r t l l e rs t u d y o nb o t ht h e o r e t i c a la n dp r a c t i c a la s p e c t s k e y w o r d s ：l e a r n i n gm e o r y ，k e m e lm e t h o d s ，r e g u l a r i z a t i o n 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：辎 1 。夕年罗月7 日 第l 章绪论 第1 章绪论 机器学习是与统计学、计算机科学、逼近论以及计算生物学等学科有密切联 系的一个研究领域它是数据挖掘和信息检索等方法的基础，在很多科学技术中 都有重要的应用对学习算法的数学分析则是机器学习的理论基础，这形成了数 学科学的一个新兴领域一学习理论 机器学习研究中大量文献所关注的是其中一个名为监督式学习的分支，即 从一组训练样本中学习出函数或特征训练样本包含了输入对象和对应的输出 对象，而学习过程是为了得到一个预测函数，能够为新的输入对象预测相应的输 出根据输出对象的不同类型，监督式学习又可以分为回归和分类两种回归问 题中输出的是连续值，而分类问题中输出的是离散值 在这篇论文中我们主要研究基于核的正则化监督式学习算法基于核的学 习算法始于v a p n i k 等人在支持向量机方面的工作【7 4 ，但本文中的讨论将与他 们的框架不同 正则化在学习中扮演着重要的角色，它引入了一个额外的惩罚项来得到偏 差方差平衡，可以防止过拟合的发生这一思想在很多数学领域中都有所体现， 我们将在下文中作简单的回顾 1 1 各领域中经典的正则化方法 在本节中，我们将回顾一些经典的正则化方法它们主要来自对各种病态问 题的研究，将为我们在学习理论方面的研究提供一些启示 1 1 1 岭回归 在统计学中常考虑如下的线性回归模型 ) ，= 卢x + ， ( 1 一1 ) 其中石r n 是输入变量，) ，r 是输出变量，卢瞅是回归系数，而是误差项 给定大小为m 的独立同分布( i i d ) 样本_ ，y f ) 翟1 ) 后，回归分析的目标是要估 计卢，使得最小二乘误差 如( 卢) 。袁荟( j b 妒y f ) 2 达到最小令x = o i ，) ，y = ”) 则卢的最佳估计由 飚= ( x r x ) 一1 x r y ( 1 - 2 ) 1 第1 章绪论 给出 假设抽样误差是不相关的随机变量，它们期望为o ，方差相等高斯一马尔 可夫定理 5 8 】告诉我们，在所有卢的无偏估计中，卢+ 的方差最小 因为x 各列中可能存在相关性，矩阵x r x 可能是病态的，甚至是不可逆的 这就导致了岭回归的引入【3 8 】与飚不同，岭回归中卢的估计是由 麟f = ( x r x + 九i ) 一1 x r y ( 1 3 ) 给出的，其中i 是恒等矩阵，而九 o 是一个岭参数卢；f 可以最小化 1 ，竹 铱f ( j b ) = 圭( | b 旎一m ) 2 + a l i p 幢， ( 1 4 ) f = l 其中”i l p 代表着汐范数舔f 不是别的，正是铅( 卢) 和一个正则项的和 艨f 虽然是j b 的有偏估计，它的方差总是比卢f 要小当输入矩阵的多元共线 性较强时，( 1 3 ) 给出的预测结果一般要比( 1 2 ) 更好选择合适的参数九，会得 到一个偏差方差平衡，并能给出j b 的最佳估计和模型的最佳预测效果 岭回归为我们后文中更一般的框架提供了一个较简单的例子，因此后文中 我们将经常回到岭回归上来而偏差方差平衡的思想也是我们对学习算法进行 误差分析的基础统计学中更多应用正则化思想的例子可以在【4 中找到 1 1 2 病态问题的t i k i l o n o v 正则化 在线性代数、积分方程、傅立叶分析、最优化理论等很多数学领域中，都存 在所谓的反问题它们可以抽象成如下的形式 考虑方程 a z = “，( 1 5 ) 其中a 是从度量空间( z ，如) 到另一个度量空间( u ，妇) 的一个连续映射在反问 题中，需要找出a 的逆，即对给定的“丁u ，找出幻z 使得a z r = “r 特别 的，假设仅给出某个“6 使得力( ，“r ) 6 ，我们希望可以找到某种意义下一个 与“6 对应的逼近解z 6 ，使得6 一o 时有z 6 一z 丁 这里我们并不要求“6 在a 的值域中a l 在“6 不一定有定义，即使有 定义也不一定连续因此，这样一个反问题是病态问题，我们不能简单的 令邵= a l h 艿对病态问题的研究是要在a 一1 无定义或不连续时，仍能从“6 以 某种稳定的方式得到z 占 为了使( 1 5 ) 稳定化，t i k h o n o v 引入了一个正则化算子 7 2 】首先我们称q ： z _ r + 是一个稳定化泛函，如果z r 在q 的定义域中，且集合f z z ：q ( z ) d ) 关于任意的d o 都是z 的一个紧子集这样，对历= z z ：咖( a z ，“6 ) 6 ) ， 2 第l 章绪论 正则化算子尺( ，6 ) 由厉中能最小化q ( z ) 的那个元素z 给出在一定的条件 下，这一最小化过程等价于选择合适的z 6 ，使得泛函 q ( z ，“6 ) = d 2 ( a z ，“6 ) + 无q ( z ) ( 1 - 6 ) 达到最小取z 6 = r ( “6 ，6 ) ，则在“6 一“r 时，有z 6 _ z 7 1 2 正则化学习 1 2 1 正则化学习的框架 令度量空间( x ，d ) 为监督式学习的输入空间，y 为输出空间在回归问题 中，y = r 是连续的，而在分类问题中，y 是一个离散集特别地，如果y 仅含两 个元素，则是一个二分类问题，不失一般性可令y = 一1 ，1 ) 学习的目标是要给出一个函数厂，可以对某个x x 给相应的预测) ，y 在 回归中，预测由厂 ) 的值直接给出在二分类中，预测值由s 卯( ，) ( 功给出，其中 昭，z ( ) 是如下的符号函数 r 啪= 1 玎忿跳 i 一1 ，i f f cx ，( f ，j ) 元素为 k ，即) 的忌七矩阵k ( x ) 是半正定的 对任意x x ，定义函数疋：x 一酞为疋( ) = k ( ，x ) 定理1 1 ：存在一个x 上函数的希尔伯特空间( 磁，( ，) 缘) 满足如下条件： ( i ) 对任意z x ，有墨兹， ( i i ) 集合 忍：x x ) 张成的线性空间在缘中稠密， ( i i i ) 对所有的厂璐和工x ，有 厂g ) = ( 疋，厂) 缘 ( 1 l o ) 4 第l 章绪论 定义1 2 ：上述定理中给出的空间璐被称作再生核希尔伯特空间，而性质( i i i ) 被称作再生性 对满足 厂2 荟磁，g 。善岛q 的厂，g 璐，它们在繇中的内积为 ( ，g ) 璐=啦岛k ，弓) 1 f ，l ，l _ ，m 下文中为了简化，我们用( ，- ) k 来代替( ，) 缘，用i k 来代替1 1 0 缘 下面我们给出一些缘空间的例子，它们相应的m e r c e r 核定义在上 例1 3 ( 多项式核) ：取某个s n ，令k ，) = + 1 ) 5 则焰是一个m e r c e r 核，且拖等价于觥上阶数不超过s 的多项式空间 例1 4 ( 高斯核) ：对任意o o 和xcr ，高斯核岛 ，) = p 一气矿是一个 防一，j 。 m e r c e r 核磊岛还是一个全能核( u i l i v e r s a lk e m e l ) 4 8 】，也就是说相应的空间 在c ) 空间中是稠密的 再生核希尔伯特空间更多的性质和例子可以在 6 2 】中找到这里，我们仅给 出一条定理来说明为什么再生核希尔伯特空间在基于核的学习算法中起着重要 的作用 定理1 2 ( 【7 5 】) ：在( 1 9 ) 中取假设空间为某个m e r c e r 核髟对应的缘，且q ( ，) = i l 厂| l 乏记璐，z 为甄张成的一个缘的有限维子空间，而p ：缘_ 缘，z 是个正交投影若厂璐是( 1 9 ) 的一个解，则p ( ，) 缘，z 也是( 1 9 ) 的一 个解 定理1 2 之所以成立是因为璐的再生性它表明优化问题( 1 - 9 ) 可以在一 个有限维空间中求解 1 2 3 支持向量机 支持向量机( s v m ) 【7 4 】是再生核希尔伯特空间中学习算法的典型代表，与 其他分类算法相比，它有着最佳的预测能力【1 3 ，4 4 】 要衡量二类分类器够：x l ，的预测能力，一个更直观的标准是误分类误差 纫( 够) = p r o b ：z c 扛) ) ， 5 第1 章绪论 如果够是由某个实值函数，给出的够= 蹭，l ( ，) ，只有在y 厂o ) o 时它才能 给出一个正确的预测因此我们的损失函数可选作y ( 厂( x ) ，y ) = 妒( 玎) ，其中 妒= 如是如下的误分类损失 批) ： 0 讧忿优 i1 ，m o 定理1 3 ( 【2 3 】) ：采用误分类损失矿( 厂( 工) ，) ，) = 如( ) ) ，则有 留( 昭n ( 厂) ) = 矽( ，) 且个目标函数是( 1 - 8 ) 所定义的昂 定义1 3 ：我们称能最小化误分类误差历( ，) 的五= 昭，l ( 届) 为贝叶斯分类器 如果( 1 9 ) 中的损失函数取加，则该优化问题不是凸的，当样本量较大时没 有有效的算法来求解为此，我们采用另外的h i n g e 损失 啪) ： 0 讧忿1 【1 _ f ，i f k 1 使用某个再生核希尔伯特空间缘作为假设空间，h i n g e 损失作为损失函数，则 正则化算法( 1 9 ) 可写作 向= 鹕惑滗刷m 眇幢) ， m 而根据定理1 2 ，它的解为 五，九= 啦k ， 其中o c r m 。 算法( 1 1 1 ) 被称作支持向量机它是一个凸优化问题，有很多计算工具可 用，快速的计算方法可以在【1 8 】和【3 2 】中找到注意我们还可以考虑其它损失函 数，包括最小二乘损失【7 0 】和l o g i s t i c 损失 9 6 】 有大量的文献 6 ，6 8 ，8 0 ，8 3 ，9 0 】关注用五九逼近五的误差误差的上界一般 由误差分解技巧给出，它把误差分为两个部分正则化误差的部分由逼近论和泛 函分析的知识可以得到，而样本误差的部分则依赖于各种概率不等式选定合适 的正则化参数后，我们可以对这两项误差取一个平衡，这和统计学中偏差方差 平衡的思想是一致的在一定的假设条件下，样本量m 增长时这一逼近阶可以 达到d ( 1 坜) 第1 章绪论 类似的手段还可以用来处理回归问题取最小二乘损失y ( ，) ，) = ( 厂) 一 y f ) 2 ，则支持向量回归算法【6 6 】为 r1m、 五，a2 嘴舞魏 壶丕扩k ) 一m ) 2 十训州未 ( 1 - 1 2 ) 岭回归是( 1 1 2 ) 的特例，它的核函数为线性核k ( 工，) = z 一在( 1 - 1 2 ) 中，我们 把线性回归推广到了一般的非线性回归 通过再生核希尔伯特空间把线性多项式空间推广到非线性函数空间这一想 法在机器学习和统计学的其他领域中也有体现，包括特征选择【4 9 ，5 0 】，主成份 分析【6 0 】，独立成分分析【3 】，以及典则相关分析【3 4 】等【3 9 】是一篇关于各种基 于核的算法的综述 1 2 4 在数据相关假设空间中学习 在一些应用中 8 1 】，我们并不能根据某些先验知识来选择澎，而是让 澎= 缆，q = q z 依赖于样本z 这样( 1 9 ) 就有如下数据相关的形式 五，九2 蝣艘1 最( ，) + a 鹞( 埘 ( 1 - 1 3 ) ( 1 1 3 ) 的一个例子是核函数学习算法 1 4 ，4 6 ，4 7 】m e r c e r 核k 是通过某种 算法由z 得到的，假设空间也是如此例如，我们可以选择高斯核的参数仃为 砚= 鹕q 磐2 q 畏嚷 磊( 厂) + 九i j 州乞) ， 这里有o 四 ( 1 1 4 ) 关于( 1 1 4 ) 的误差分析可在【7 8 】中找到 另一个例子是基于系数的正则化方法令核函数k ：x x r 为某个连续 函数，但不一定是m e r c e r 核对任意的1 p m 兹= 啦如：啦r ( 1 - 1 5 ) if = lj 且 q ( ，) = p 于是( 1 9 ) 变成了数据相关的形式( 1 1 3 ) 而五九由 朋 五，九= 睨，f 如 i = l ( 1 1 6 ) 7 第1 章绪论 给出，其中 = 鹕赫 磊( 茎嘶磁卜酗p ) m 如果我们选择k 为线性m e r c e r 核且令p = 2 ，则岭回归也可以写成这种形 式另外的例子包括l a s s 0 回归和线性规划s v m 4 2 ，9 7 】 岭回归和l a s s o 回归的误差分析是统计学中的一个经典课题【7 9 】把线性 规划s v m 与经典的s v m 关联起来，对它作了误差分析除此之外，基于系数的 正则化学习算法很少有文献关注 我们的主要兴趣在于l a s s o 和其他z 1 正则方法，在下一章中会有进一步 的讨论 1 3 本文主要贡献 在这篇学位论文中，我们主要研究正则化回归算法一些非标准的框架这些 在文献中很少有人关注，但在实际应用中非常重要 首先我们考虑的是基于系数的z 1 正则化方法，亦即在( 1 1 7 ) 取p = 1 这样 一个方法可以放松核函数在对称性和正定性方面的限制，并且可以带来稀疏性 在 8 l 】对这一学习算法有所研究，但并不完整在第二章和第三章中我们将对这 一算法的学习率作彻底的分析同时在第五章我们将从理论和应用两方面对稀 疏性作一些讨论以供进一步研究 另一方面，当前很多文献都是假定样本z 独立同分布的抽自j d ，但这在实际 中并不总是成立我们将在第四章中分析非一致抽样时的分类算法在这一章中 我们还通过定义一个分离函数对多类分类算法进行了误差分析 8 第2 章一般度量空间上的1 正则化学习 第2 章一般度量空间上的z 1 正则化学习 2 1 正则化因子因为它带来的稀疏性而引人注目，这里所谓稀疏性是指在最 后的解中大部分系数为o 本章中我们首先回顾文献中用过的笆1 正则化方法，并 说明稀疏性是如何产生的接下来我们将介绍在一般度量空间上基于核的笆i 正 则化学习算法，并对误差进行估计获得它的学习率，以确保该算法收敛到我们的 学习目标 本章中只考虑回归问题，而分类问题可以用类似的方法来分析本章的核心 内容主要来自【8 5 】 2 1 粤1 正则化的稀疏性 对z 1 正则化因子的研究始于线性回归的l a s s o 方法【7 l 】，在那里我们可以 观察到在选择合适的正则化参数后，回归系数是稀疏的这样的稀疏性受到了广 泛的关注，因为它可以用来进行变量选择但稀疏性产生的真正原因直到压缩感 知理论建立 1 0 ，2 4 】起来之后才明确 2 1 1 l a s s 0 回归 线性回归模型( 1 。1 ) 的l a s s o 方法与岭回归方法的不同之处只是在于把护 正则项替换成粤1 的正则项也就是说，它通过最小化 也( 胪去薹( 肌咄) 2 刊胁， ( 2 - 1 ) 来估计卢，估计值为 肱2 a r g 船鼠( 卢) ( 2 - 2 ) 计算眦较快的方法是最小角回归 2 6 ，2 8 ，3 7 】 经验的观察表明，对于适当选择过的九，卢己的大部分分量会是o ，也就是说 卢己是稀疏的这样的稀疏性在统计学中非常重要，因为它给出了变量选择的一 种自适应的方法【8 ，3 1 】最近一些关于l a s s o 的分析【5 ，4 3 ，9 1 1 表明，如果模型 ( 1 1 ) 中真实的系数j b 是稀疏的，那么估计得到的系数舷有很大的可能也是稀 疏的这些分析依赖于我们在下一小节中将要讨论的压缩感知理论 9 第2 章一般度量空间上的z 1 正则化学习 更广义的l a s s o 可以按如下方式定义令 ，屈为某个空间彬的一个 生成集我们求解优化问题 t 矗xk 矿2 a r g 怨善( 善哟乃) 一) ，t ) 2 + 九善f 哟i 并通过篙l 口；乃 ) 来预测) ，如果这个生成集由某个核函数产生，那么这个方 法与取p = 1 的基于系数的正则化学习方法( 1 1 7 ) 一致这也就是我们在本章和 第三章中将要研究的学习算法注意口+ 仍保持有肱的稀疏性 2 1 2 压缩感知理论 压缩感知，也叫做压缩抽样，是信号处理中近年来新兴的一种理论，而它同 时也吸引了应用数学领域研究人员的广泛注意 令厂为取值在r n 中的向量值函数，它可以通过一个正交系￥= ，】 表示为 n 儿) = 嗣( f ) ， l = 1 其中x 是厂的系数序列，魂= ( 厂，) 是各个分量也可以把厂记作眠用恻i o 表示x 中非零分量的个数如果l o s ，则称，是s 稀疏的， 对厂的感知机制由正交系西= 【妒l i 九】给出，各观测值为 了j = u ，舟。 我们希望通过测量所有的 ，j 1 ，1 ) 来恢复，但因为种种原因，我们仅仅 有一部分满足_ m 的) ，i ，其中集合mc 1 ，1 ) 的基数m o ，使得对任意的o 6 o 成立，则x 在1 一n 一6 的置信度下可以通过矿精确的重构 令尺为m ，l 矩阵，它选出了m 中的那些观测值令a = 尺中甲则( 2 3 ) 又 可写作 艘l ，“y = 做 ( 2 4 ) 另一方面，x 最稀疏的表示是 船俐o ，“y 2 做 ( 2 5 ) 虽然( 2 5 ) 是一个n p 难问题，但有大量的矩阵a 使得( 2 5 ) 与( 2 4 ) 有完全相同 的解【2 5 】例如， 定理2 2 ( 2 9 】) ：设( 2 5 ) 的解端满足 蚓。 o 和q o ， 成立 ( x ，r ) c 玎( 吴) q ， v 0 o 和o f ，使得对于x 中任意开球b ( 石，尺) = _ “x ：d ( “，甸 尺) ，x 上的概率测度触可使得 p x ( b ( x ，r ) ) g 尺f坛x ，o o ，昂取自算子i k l 5 的值域中 在本章中我们总是假设i ) ，l m 几乎处处成立现在我们陈述这一节的主要 结论 定理2 4 ：假设x 满足指数为叼 o 的条件( 2 9 ) ，核函数k 满足( a ，j b ) 阶( 其 中o a ，j b o 的k 条件，且对于某个 o o ，令九= m 记 一 南捌卜掣，三一掣，詈一掣，封 那么对任意的o 3 ( 1 + 7 7 ) ，九= m e 其中 9 箭珊 注2 2 ：限制了p x 的支集后，条件( 2 9 ) 在f 0 ，五九由( 2 8 ) 给出我们有 i | 五，九一昂i l 夕( z ，九) + 汐( z ，九) + 9 ( 九) ( 2 - 1 5 ) 证明：通过简单的计算可以发现 夕( z ，j ；l ) + 汐( z ，九) 十9 ( j l ) = 椤( 五，a ) 一矽( 而) + 尢q z ( 五，九) 而q z ( 五，九) o 因此由恒等式夕( 兀，九) 一矽( 昂) = l i 五，九一昂i i 可知( 2 - 1 5 ) 成 2 4 估计正则化误差 因为并没有假定k 是对称的，对正则化误差的估计需要采取与正定的核函 数 6 4 ，7 7 】不同的方法 引理2 1 ：设砖是k 磙的正特征值，而饥是l 2 x 中相应的标准化特征函数 则 ；砖i c 2 且i l 氟l | 袁k 证明：定义核函数霞：x x _ r 为 霞( “，1 ，) = k ( “，工) k ( 工) d p x ( 石) 容易验证霞是一个m e r c e r 核，并有i i 霞i i c 伍x ) k 2 ，且k = k 砭 根据m e r c e r 定理( 参见【2 0 】) 可知 ；砖= ；砰上做 ) 2 d 咫o ) = 上霞 ，工) d 触 ) p 七七 一一 注意到 饥= 壶k 砭暾寻壶k 做= 毒上上k ( ，x ) k ( v ，工) 做( v ) d 触( v ) d p x ) 于是妣可以写作 做= 上 壶上k ( u x ) 暾( y ) d 似( v ) ) 疋d 触( n 第2 章一般度量空间上的1 正则化学习 这是函数族忍 x ) 的一个线性组合，相应的系数为氏k ( u 曲锹( ，) d p x ( 1 ，) 因 此由范数”f l 的定义可知 | l 奴i | 上l 去上k ( u 神暾( v ) d 触( v ) 卜似( 刁= 壶上l 砭饥( 力i d p x ( n 再根据许瓦兹不等式，有 l l 暾l l 去l | 砭删嚷= 去瓦砭砸= 麦 这就得到了我们所需的上界 口 上面的第一个不等式可以很容易地从对称核霞所定义的积分算子珞的迹 得到，但第二个不等式则不能因为范数1 1 i l 与”| l 霞并不一致 现在可以给出正则化误差9 ) 的上界如下 命题2 2 ：如果昂= l k l 5 9 关于某个o o ，( 2 1 6 ) 其中c 12 奄x + 删 证明：去掉那些特征值为。的特征向量后，我们有g = 缸 o 鲰绌于是恬i l ：& = 缸 o 口； o 鲰雒锹 如果o o 使得触满足k 条件，而“ 丝l 是独立的抽 自似的一组样本，且存在某个 o 使得“) 墨1 是一稠密的，那么对任意的 o 6 1 ， 1 0 9 僻，会) 一等眺l o g 要 ( 2 - 1 9 ) 在1 一孚的置信度下成立 证明：我们用一组半径为金的球 b j ，= l ，= 僻，今) ) 来覆盖x 由厶条 件的定义可知，p x ( 毋) g ( 金) f 关于每个歹都成立这样，事件协 銎l n 毋= o 发生的概率最多为( 1 一g ( 金) f ) m 而饥) 翟1 n 毋= o 对至少一个j 1 ，m ) 成立的概率最多为 ( 1 一g ( 扪m 唧 娟( 钔 因此，在1 一e x p o 的k 条件，存在o s 2 使 得而在l k i 。的值域中，且k 满足( 2 1 1 ) ，那么对任意的o 6 1 ， 卿矧九帮+ 九爱? ( 盟宅竽业) 譬 ( 2 2 3 ) 在1 一耋的置信度下成立，其中c 2 是与九、，l 和6 都无关的常数 第2 章一般度量空间上的1 正则化学习 证明：要利用引理2 3 采获得1 岌设误差的上界，需要找剑一个h 邑膨满足( 2 一l ” 式的为此，我们考虑如下的定义在( o ，) 上的严格单调下降函数 砸) = 。g ( x ，兰) 一等 令 a = 2 ( 1 + ( 詈) 5 + c 旁砖) ， 并取 树( 咝掣) 专 利用( 2 9 ) 给出的覆盖数的上界可得 知( ) 。g ( c 町( 暑) 町) + 罟。g ( 菇葛匹7 万) 一冬( 1 0 9 ( 2 6 ) + l o g ( m + 1 ) ) 根据a 的定义可知五2 ，萼( ) f ，且a 叼q 2 t 7 砖于是 郴旧。g 簪+ 铷m 一抛。g 胁+ 1 ) 乩g 吾一孙c m 删 9 9 孚 即满足( 2 1 9 ) 这个不等式再由引理2 2 ，在至少1 一要的置信度下，伪) 翟1 是 稠密的从引理2 3 可推出f 2 2 3 、式给出的e 界，其中常数 命题2 3 证毕 q = 2 ( c k + c 1 m ) a a 彳 口 口 2 6 估计样本误差 令 舅( z ，九) = 磊( ) 一岛( 昂) ) 一 多( 厶) 一彦( 昂) ) ， ( 2 - 2 4 ) 而 彤( z ，九) = 汐( 矗九) 一乡( 昂) ) 一 磊，九) 一岛( 昂) ) ， ( 2 2 5 ) 则( z ，a ) = 舅( z ，a ) + 兄( z ，九) 我们下面将分别给出这两部分样本误差的上 界 2 0 第2 章一般度量空间上的1 正则化学习 定义考( z ) = 考 ，) ，) = ( 一) ，) 2 一g ) 一) ，) 2 ，这是z 上的一个随机变量， 并有舅( z ，九) = 刍距l 专( z i ) 一e 专如下的单边伯恩斯坦不等式是概率论中的标准 结果 引理2 4 ( 伯恩斯坦不等式) ：设 o ，都有 p r o b ) e x p 一高) c 2 2 6 ， l f 怯的上界由( 2 - 1 8 ) 和( 2 1 3 )