（应用数学专业论文）关于模型选择问题的子空间信息准则.pdf

摘要 近年来，模型选择问题引起人们很大的兴趣在监督学习中，模型选择的好 坏直接影响学习算法的推广能力如果所选择的模型过于复杂，就会出现过学 习( o v e r f i t t i n g ) 现象；相反，如果模型过于简单，则会出现欠学习( u n d e r f i t t i n g ) 现象 对于小规模样本集( 实际问题总是小规模样本集的问题) ，监督学习的目 标是在给定的函数集中挑选一个最优的逼近函数，从而最小化推广误差对 此，v a p n i k 在文献| 5 3 】中提出了选择这样函数集的原则，即结构风险最小化 ( s r m ) 原则该原则为给定函数集提供一个容许结构，然后在整个给定的结 构元素上找到最小化保证风险的函数 上世纪下半叶，人们从各种观点出发，提出了很多模型选择原则其中以 a k a i k e 等人提出的两种模型选择原则较为流行。a k a i k e 信息准则( a i c ) 1 7 和b a y e s i a n 信息准则( b i c ) 1 s 后来，从泛函分析的角度出发，s u g i y a r n a 和o g a w a 又提出了一种新的模型选择准则，即子空间信息准则( s i c ) 27 s i c 所考虑的训练样本是基于f o ，1 1 上样本点的一个均匀分布，零均值和 不同方差值的正态分布噪声得到的它用所选取的函数与真实函数之间的均 方差来估计性能 s i c 的优势在于它是推广误差的一种无偏估计，实验证明 依s i c 思想选择的模型得到的学习算法具有很好的推广能力 本文分五个部分讨论了模型选择的子空间信息准则问题 第一部分，主要介绍了学习问题及本文的研究背景 第二部分，首先介绍模型的概念，接着回顾一些经典的模型选择原则， 主要介绍的有三个t 结构风险最小化原则( s r m ) ，a k a i k e 信息准则( a i c ) 和 b a y e s i a n 信息准则( b i c ) 第三部分，讨论本文的主要内容，即解决模型选择问题的子空间信息准则 f s i c ) 在介绍s i c 的定义以后，把该方法推广到无限维的假设空间上；并且 还对s i c 进行扰动分析，最后对s i c 的一些不足之处进行改善，从而提高该 方法的精度 1 1 1 第四部分，我们将s i c 应用到学习问题的一些重要模型中，这其中包括 在再生核h i l b e r t 空间上，应用s i c 选择逼近函数中模型参数在找到相关的 无偏学习算子后，证明了用于选择模型的s i c 是关于学习结果的推广误差的 一种无偏估计，同时说明学习算法有较好的推广熊力进一步探讨了s i c 的 应用前景 第五部分，我们对s i c 和解决模型选择问题的其他方法进行了比较，同 时对本文所介绍的子空间信息准则( s i c ) 的前景进行估计和分析 关键词 模型选择；推广能力i 子空间信息准则；无偏估计；学习矩阵 a b s t r a c t i nr e c e n ty e a r s ，m a n yp e o p l ea r ei n t e r e s t e dg r e a t l yi nt h em o d e ls e l e c t i o n p r o b l e m s i ns u p e r v i s e dl e a r n i n g ，t h eq u a l i t yo fm o d e ls e l e c t i o ni n f l u e n c e s d i r e c t l yg e n e r a l i z a t i o nc a p a b i l i t yo fl e a r n i n ga l g o r i t h m i ft h em o d e li s t o o c o m p l e x ，i tm a ya p p e a rt h ep h e n o m e n o no f o v e r f i t t i n g ；o nt h ec o n t r a r y , i f t h em o d e li st o os i m p l e ，i tm a ya p p e a rt h ep h e n o m e n o no f u n d e r f i t t i n g r e g a r d i n gs m a l ls c a l es a m p l es e t s ( p r a c t i c a lp r o b l e m sa r ea l w a y ss m a l l s c a l es a m p l es e tp r o b l e m s ) ，t h eg o a lo fs u p e r v i s e d e a r n i n gi st oo b t a i na no p - t i m u ma p p r o x i m a t e df u n c t i o nf r o mt h eg i v e nf u n c t i o ns e t ，t h u si tc a r lm i n i m i z e g e n e r a l i z a t i o ne r r o r r e g a r d i n gm o d e ls e l e c t i o n ，v a p n i kp r o p o s e das e l e c t i o n p r i n c i p l ef o rs u c hf u n c t i o ns e ti nt h el i t e r a t u r e 5 3 1 ，n a m e dt h es t r u c t u r e 砸s k m i n i m i z ep r i n c i p l e ( s r m ) t h ep r i n c i p l ep r o v i d et h ef u n c t i o ns e tw i t ha na d m i t t e ds t r u c t u r e ，t h e ni ne n t i r eg i v e ns t r u c t u r a le l e m e n t s ，w ec a nf i n dt h e f u n c t i o no ft h em i n i m u mg u a r a n t e e dr i s k i nt h ee n do ft h ep a s tc e n t u r y , t h ep e o p l eh a v ep r o p o s e dm a n ys e l e c t i o n p r i n c i p l e sf r o mv a r i o u sv i e w p o i n t s t w ok i n d so fm o d e ls e l e c t i o np r i n c i p l e s w h i c hw e r ep r o p o s e db ya 诅i k ea n dh i sc o m p a n i o n sw o r em o r ep o p u l a r ，a k a i k e i n f o r m a t i o nc r i t e r i o n ( a i c ) 1 1 7 】a n db a y e s i a ni n f o r m a t i o nc r i t e r i o n ( m c ) i l s l a f t e r w a r d s ，e m b a r k e df r o mt h ea n g l eo ff u n c t i o n a la n a l y s i s ，s u g i y a m aa n d o g a w aa l s op r o p o s e dak i n do fn e wm o d e l s e l e c t i o nc r i t e r i o n ，n a m e ds u b s p a c e i n f o r m a t i o nc r i t e r i o n ( s i c ) 2 7 ， s i cc o n s i d e r st h et r a i n i n gs a m p l e w h i c hi sd r a w nf r o ms a m p l ep o i n t s 讷t hn o r m a ld i s t r i b u t i o nn o i s e so fu n i f o r md i s t r i b u t i o n ，z e $ oa v e r a g ev a i u e a n dd i f f e r e n tv a r i a n c ev a l u e si n 0 ，1 i te s t i m a t e sp e r f o r m a n c eb yt h em e a n s q u a r e sv a r i a n c eb e t w e e nt h eo b t a i n e df u n c t i o na n dt h er e a lf u n c t i o n t h e s u p e r i o r i t yo fs i cl i e si nt h a ti t i sa nu n b i a s e de s t i m a t i o no fg e n e r a l i z a t i o n e r r o r ，t h ee x p e r i m e n t sh a v ep r o v e dt h eo b t a i n e dl e a r n i n ga l g o r i t h m sa c c o r d i n g t ot h et h o u g h to fs i ch a v eb e t t e rg e n e r a l i z a t i o nc a p a b i l i w t h em a i nc o n t e n ti sa r r a n g e da sf o l l o w i n g ： i nt h ef i r s tp a r t ，w ew i l lm a i n l yi n t r o d u c et h el e a r i n gp r o b l e m sa n dt h e b a c k g r o u n d i nt h es e c o n dp a r t ，w ew i l lf i r s t l yi n t r o d u c et h ec o n c e p t i o no fm o d e l ，t h e n r e v i e ws o m ec l a s s i c sm o d e ls e l e c t i o np r i n c i p l e s ，m a j r a yi n t r o d u c et h r e ek i n d s ： s t r u c t u r er i s km i n i m i z ep r i n c i p l e ( s a m ) ，a k a i k ei n f o r m a t i o nc r i t e r i o n ( a i c ) a n db a y e s i a ni n f o r m a t i o nc r i t e r i o n ( b i c ) i nt h et h i r dp a r t ，i ti st h ek e yc o n t e n to ft h ea r t i c l e ，n a m e ds u b s p a c e i n f o r m a t i o nc r i t e r i o n ( s i c ) f o rm o d e ls e l e c t i o np r o b l e m s a f t e rt h ed e f i n i t i o n ，w ec a 2 1p r o m o t et h em e t h o dt oi n f i n i t ed i m e n s i o nh y p o t h e s i ss p a c e s ；t h e n w ec a r r yo nt h ep e r t u r b a t i o na n a l y s i s ，o f s i cf i n a l l ym e n ds o m ed e f i c i e n c i e s o fs i c ，t h u se n h a n c ep r e c i s i o no fs i c i nt h ef o u r t hp a r t ，w ea p p l ys i ct os o m ei m p o r t a n tm o d e l si nl e a r n i n g p r o b l e m s i 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 ，w ed i s c u s st h em o d e lp a r a m e - t e r ss o l e c t i o nf o rt h ea p p r o x i m a t i o nh m c t i o nb ys i c a f t e rf i n d i n gc o r r e l a t i v e u n b i a s e dl e a r n i n go p e r a t o r s ，w ep r o v et h es i ci sa nu n b i a s e de s t i m _ a t eo fg e n - e r a l i z a t i o ne r r o ro fl e a r n i n gr e s u l t ，m e a n w h i l ei tc a np r o v et h a tl e a r n i n gr e s u l t h a sb e t t e rg e n e r a l i z a t i o nc a p a b i l i t y f u r t h e rw ed i s c u s sa p p l i c a t i o np r o s p e c t o fs i c i nt h ef i f t hp a r t ，w ec o m p a r es i cw i t ho t h e rm e t h o d sf o rm o d e ls e l e c t i o n p r o b l e m s ，m e a n w h i l ee s t i m a t ea n da n a l y s et h ea p p l i c a t i o np r o s p e c to fs i c k e yw o r d s m o d e ls e l e c t i o n ；g e n e r a l i z a t i o nc a p a b i l i t y ；s u b s p a c ei n f o r m a t i o nc r i t e r i o n ； u n b i a s e de s t i m a t e ；l e m m i n gm a t r i x 、r 1 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他 个人或集体已经发表或撰写过的作品或成果对本文的研究做出重要贡献的 个人和集体，均巳在文中以明确方式标明本声明的法律后果由本人承担。 论文储肄黜器 签名日期。弘口年月3 日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即；按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容( 保密论文在解密后遵守此规定) 敝储繇黜嚣 签名日期；枷1 年6 月孓日 】l 导师硌籼i 嘎 签名日期，乙“年占月f 日 第一章引言 人们对机器智能的研究中，希望能够用机器( 计算机) 来模拟人类的学习 能力，这就是所谓的基于数据的学习问题，或简单地称为机器学习问题，这一 问题的研究目的是设计某种方法，利用学习得到的规律，较好地解释已知的实 例，并且能够具有对未来现象或无法观测的现象作出正确预测和判断的推广 能力 人们对学习问题的研究过程中。从6 0 年代r o s e n b l a t t 的感知器模型，到 7 0 年代学习理论基础的创立，直到8 0 年代神经网络的出现，统计学一直在解 决机器学习问题中起着基础性作用然而，传统的统计学所研究的主要是基 于大样本的渐近理论，在实际问题中，面对的样本通常是有限的，使得针对大 样本的各种算法，条件往往难以实现，并且这些针对大样本的算法在样本较少 时未必有较好的表现，当问题处在高维时尤其如此其中，近年来常谈论的神 经网络过学习问题就是一个典型代表t 当样本有限时，本来很不错的一个学习 机器可能表现出很差的推广能力 人们对于解决此类问题的努力一直在进行v n v a p n i k 等人早在2 0 世 纪6 0 年代就开始研究有限样本情况下的机器学习问题，并于7 0 年代末建立 了有限样本的学习同题的基本体系，直刭9 0 年代形成了一个较完善的理论体 系一统计学习理论( s l t ) 5 3 1 ，它针对小样本统计问题建立了一套新的体系 而同时，神经网络等较新兴的机器学习方法的研究则遇到一些重要的困难，比 如如何确定网络结构的问题，过学习与欠学习问题，局部极小点问题等等。在 这种情况下，试图从更本质上研究学习问题的统计学习理论逐步得到重视， 无论是在学习理论中，还是在理论应用统计学中，都形成了一个前沿的研究方 向 1 1 机嚣学习问题简介 基于数据的机器学习的目的是，设计某种算法，使之能够通过对已知数据 的学习，找到数据内在的相互依赖关系，从而对未知的数据进行预测和判断 1 1 1 1 机器学习问题的表示 机器学习问题的基本模型包括三个部分：样本生成器( g e n e r a t o r ) 依照某 一未知概率分布随机产生数据，输入到我们研究的对象监督器( s u p e r v i s o r ) 中得到个输出y ，同时学习机器( l e a r n i n gm a c h i n e ) 对输入z 响应输出，( z ) 机器学习问题可以形式化的表示为t 已知输入空间z 与输出空间y 之间 存在一定的未知依赖关系，即存在一个未知的联合概率测度p ( x ，y ) 机器学 习就是根据包含m 个独立同分布的观测样本的集合 s = ( z 1 ，y 1 ) ，( ，玑) ，( z 。，肌。) )( 1 1 1 ) 在个函数集( 或称假设空间) 州中寻找一个最优的函数，使它的期望风险( e x - p e c t e dr j s k l r ( f ) = c ( ”，( ) ) d p ( 。，y )( 1 1 2 ) 最小，其中c 表示在给定输入茁下，监督器的响应y 与学习机器给出的响应 f ( x ) 之间的损失不同类型的学习问题往往具有不同形式的损失函数 在这一体系中假设空间h 是一个泛函空间，在爿中需要定义一个收敛 准则，即h 必须赋予拓扑结构一般说来，学习问题是一个不适定问题，通 常将问题转化为下述最小化问题t 磐恃若c ( y l , m i ) ) 叫) ) _ 其中泛函q ( ，) 表示了，光滑性的先验信息，参数a 0 是在，对样本的拟 合度与，的光滑性之间进行调节的参数，通常称为正则化参数 而当写出损失函数时，我们已暗示了函数，在任何一点是已知的进 一步，如果我们能够使用学习机器对任一给定的输入z 作预测，那么，( 占) 必 须对所有。z 都存在。即我们需要的是点点有定义的函数集，同时要求评 价函数是线性的，连续的。使得假设空间具有再生性在赋予函数集这些性质 后就会产生许多有意义的结果在学习机器领域最有用的结论是一个核函数 k 的存在性，一个具有再生性的二元函数 v f h ，3 m n ，( 口i ) k l ，。，s ，( z ) a i k ( x ，) 2 因实际的原因，可能有不同的表示，主要依赖于核的选择如果函数 集是一个h i l b e r t 空间。那么，它成为一个再生核希尔伯特空间( r k h s ) 尽 管h i l b e r t 结构对于学习问题的假设空间不是必须的，但再生核希尔伯特空间 及其相应的再生核因具有良好的性质，在学习领域中被广泛应用 1 1 2 机器学习的基本问题 机器学习问题中最基本的三个问题是模式识别，回归估计和概率密度函 数估计 在模式识别( 即分类) 问题中，对于两类情形，输出空间为y = 一1 ，1 ) ， 假设空间7 - 1 ：= ( s 弘( ，) ：，州为实值函数) 考虑的损失函数为 铀川圳= 忙嚣吖。 对于这个损失函数。( 1 1 2 ) 式的风险泛函确定了训练集s 和学习机器响应 的函数所给的答案不同的概率我们把该函数所给的答案与训练器输出的值 不同的情况叫做分类错误这样，模式识别问题就成了在概率测度p ( x ，y ) 未 知，但训练样本集( 1 1 1 ) 已知的情况下，寻找使分类错误最小的函数 在回归估计问题中，y r ，州为实值函数集合考虑的损失函数为 l ( y ，( z ) ) = ( y 一，( 。) ) 2 我们知道，在该损失函数下，使( i i 2 ) 式最小的函数为 ，o ( 。) = y d v ( y x ) ， 其中p ( y l x ) 为条件概率测度，通常称该函数为回归函数这样，回归估计问 题就成了在概率测度未知，但训练样本集已知的情况下，寻找回归函数的逼近 问题 在密度函数估计中，考虑在概率测度p ( x ) 未知，而给出独立同分布样本 情况下，利用损失函数 x l ，o m c ( p ( z ) ) = 一l n p ( x ) 3 使期望风险( 1 1 2 ) 式达到最小( 其中p ( z ) 为密度函数集) 1 1 3 机器学习问题的归纳原则 学习问题可以看作是基于经验数据进行函数估计的问题 散数据基础上寻找待求函数依赖关系的问题 学习机器观察n 个数据( 训练集) ( 茁1 ，掣1 ) ，- 一，( 。m ，! f 仇) ， 或者说是在离 ( 1 1 3 ) 该训练集包含了输入向量z 和训练器的响应值y 它是根据一个联合概率分 布p ( x ，y ) = p ( x ) p ( y z ) 而随机独立抽取的在这个过程中，学习机器构造一 个规则，这个规则根据产生器产生的具体向量值瓤来预测训练器的响应值y i 学习的目的就是要对任何输入构造一个与训练器响应合适的逼近 当选择一个具有想要的性质的函数时，我们应该考虑的个模型为。在所 有可能的函数中，要寻找一个以最好的可能方式满足给定的性质评判标准的 函数 令。= ( g ，”) ，学习问题可以作如下的一般表示：设有定义在空间z = z y 上的概率分布p ( z ) ，考虑函数集合，( 。) ，“，学习的目标是最小化 风险泛函 ， r ( c ，) = c ( z ) d p ( z ) ，( 1 1 4 ) j 其中c ( 2 ) ：= c ( 口，( z ) ) ，概率分布p ( z ) 未知，但给定了一定的独立同分布样 本 我们已经知道，不同的学习问题可以看作是待定损失函数下的风险泛函 最小化问题但怎样才能最小化风险泛函呢? 由于定义风险的概率分布p 未 知，我们不能直接最小化风险泛函经典的解决学习问题的归纳原则是经验风 险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ，e r m ) 归纳原则 为了在未知的分布函数p ( z ) 下最小化( 1 1 4 ) 式的风险泛函，有一种做 法是， 4 ( 1 ) 把风险泛函r ( l ，) 替换为所谓的经验风险泛函 ( 甜) = 击喜地，( 硼， ( 1 1 5 ) ( 2 ) 用使经验风险( 1 1 5 ) 式最小的函数，逼近使风险( 1 1 4 ) 式最小的函 数 ，我们把这一原则称作经验风险最小化归纳原则 一个归纳原则，如果对任何给定的观测数据，学习机器都依照这一原则 来选择逼近。则我们说这一归纳原则定义了一个学习过程在学习理论中， e r m 原则扮演了一个具有决定性的角色 e r m 原则是非常一般性的解决一些特殊的学习问题的很多传统方法。 比如在回归估计问题中的最小二乘法，概率密度估计的最大似然法等，都是 e r m 原则的具体实现 1 1 4 学习机器的推广性能 一个好的学习机器要求在能较好地解释已知实例的同时，还能对未来的 现象作出比较可靠的疆测和判断，我们把这种能力称为学习机器的推广性能 ( 亦称推广性) 推广性问题是学习的核心问题，同时也是关于自然科学和哲学 的核心问题现代对这一问题的研究始于2 0 世纪前期，a n k a l m o g o r a v 在 1 9 3 3 年提出了概率论和统计学的公理体系，在这一体系下有两种不同的推理 的数学模型t 演绎模型( 概率的理论) 和归纳模型( 统计的理论) 从那时起人 们才把统计学看成是一种推理的数学模型，其主要问题是给定观测( 数据) 寻 求推广( 感兴趣的函数) 2 0 世纪7 0 年代人们发现，对于归纳推理来说，有且 仅有两种因素影响学习机器的推广性，它们分别是r 1 经验风险t 它说明了被选中的函数在多大程度上刻画了观测在早期神经 网络研究中。人们总是把注意力集中在如何使经验风险更小，但是后来发现一 味追求小的训练误差并不是总能达到好的预测效果在某些情况下，训练误差 小反而导致推广性能的下降，这就是几乎所有的神经网络研究者都遇到过的 所谓过学习( o v e r f i t t i n g ) 问题之所以出现过学习现象，一是因为学习样本不 充分；二是学习算法设计不合理，假设空间过于复杂 2 ，假设空间的容量( 或称复杂性) ：它描述了被选择函数集的多样性如果函数 5 集足够“大”，那么我们选中的函数可以充分好地适应观测样本( 即经验风险 可以充分小) 但是它对新样本预测的真实风险可能很大，即所谓的过学习 我们把函数集适应不同数据的能力称为它的容量 为了保证学习机器有较好的推广性能，我们必须在控制经验风险的同时， 选择一个容量较小的函数集，这就是我们通常所说的模型选择问题这一点在 小样本的学习上尤为突出，针对小样本的学习机器执行结构风险最小化( s r m l 原则，s r m 原则要求在经验损失和假设空间的容量两者之间折衷，这样在一 定程度上克服了传统的e r m 原则的缺陷 1 2 研究环境 我们研究的具体环境是，设爿是由未知但给定的分布p ( z ) 所决定的点所 构成的输入空间 乱) ，y 是由条件分布p ( y 恸决定的，它是目标算子在输入 空间彤上的输出空间三= 磊 = ( 如，玑) 是样本空间，样本空间z 上的 分布p 是未知的，它是由分布p ( z ) 和p ( 圳z ) 导出的特别地，当y = 一1 ，1 ) 时，所研究对象就为分类f 司题，分类问题在数据挖掘，手写体和语音的识男n ， 视觉和语言学习等中有重要的应用 我们记m 个样本的训练样本集s 为 s = z l ，z 2 ，) = t ( ，9 1 ) ，( x 2 ，珈) ，一，0 。，) ) 若v u z ，记，”为 s 芦= z z ，五一i ，缸，五十1 ， ， 即伊u 表示把训练样本集s 的第1 个分量魂用u 替换，所以s t “z 记分为 = ( z l ，五“五+ 1 ，) ， 即表示把调练样本集s 的第i 个分量盈去掉，所以s t 刀“一 我们记s p m 为训练样本集s 是根据分布函数p 从z ”上随机独立抽 取的，类似记z p 为样本i 是根据分布函数p 从z 上随机独立抽取的 6 一个学习算法矗就是从训练样本集s 到假设空间( 或函数空间) 何上的 一个映射设学习算法，s 在训练样本集s 上的输出函数居为彤到ycr 上的实值可测函数 学习算法厶的性能一般是用学习算法的真实误差( 或真实风险) 来度量， 即用学习算法，s 在一个任意的新样本z 0 一p ) 上产生损失的期望来度量 我们用i ( s ) 表示学习算法南的真实误差( 或真实风险) 若用c ( f s ，z ) 表示学习算法括在样本z 产生的损失，损失( f s ，z ) 不仅 是样本z 的函数，而且是训练样本集s 的函数，并且满足条件： 0 ( f s ，z ) m 在一些特殊情况下，如分类情况下，我们取m = 1 特别地，当损失为二次损 失函数时，我们有 c ( i s ，z ) = ( s ( 茁) 一g ) 2 于是有 i ( f s ) = e z ( i s ，。) 真实误差i ( 如) 是一个学习算法，s 性能的最主要的度量一般，当训练 样本集s 的样本的数目增大时，若i ( ，s ) 超过最优误差值的概率趋于o 时， 我们就认为这个学习算法是好的在一些特定的情况下，这个最优误差值可以 是贝叶斯误差 因为样本空间z 上的分布函数p 是未知的，故我们不能直接界定真实误 差i ( 如) ，为了便于分析真实误差i ( 五) ，一般把真实误差i ( 南) 分解成两个部 分：一部分是经验误差( 或经验风险) ：经验误差是学习算法，s 在训练样本集 s 上性能的度量，记为i s ( i s ) 一 m i s ( i s ) = 去c ( ，s , z d ； 另一部分是推广误差g e n ( s ) ：推广误差是经验误差i s ( 厶) 与真实误差i ( s ) 的 差，即 g e n ( s ) = i ( s ) 一i s ( 如) 7 对这两部分有一个均衡：因为当考虑的假设空间? - 越复杂时，经验误差i s ( 矗) 会越小，而推广误差g e n ( s ) 却会越大因此，机器学习理论研究的一个主要 目的就是如何去处理假设空间咒简单性和复杂性的平衡问题 8 第二章模型选择 2 1 模型的定义 基于大小为m 的训练样本集，考虑逼近目标函数的监督学习问题 设学习目标函数，( z ) dcr ，r 是l 维e u c l i d 空间训练样本由 样本点蜀和相对应的样本值轨构成； ( 轨，y i ) 1y i = ，( 甄) + g m ：l ，z t 口，玑e ( 2 1 1 ) 其中c 为复数集，i 是由均值为零，方差为一的正态分布得到的加性噪声 设日是艟决定学习结果的因素组成的集合例如，基函数的类型和数目， 正则化参数和正则化项等等我们把p 称为模型 设五是由模型口得到的学习结果，并假设，1 五h ，咒为h i l b e r t 空 间，那么模型选择问题可以如下表示t 定义2 1 1 ( 模型选择) 从所给的模型集合中，找到一个模型使它能够最小化 推广误差 最i i 五一1 1 2 ， 其中e e 表示对噪声的一致平均，0 表示范数 2 2 经典的模型选择原则 随着机器学习理论的不断完善，模型选择问题越来越受到青睐在实际算 法中，模型选择的好坏直接影响学习结果的推广性能 上世纪，人们从各种观点出发，提出了很多模型选择原则如有限预测误 差( f p e ) ，广义交叉检验( c c v ) ，s h i b a t a 模型选择子( s m s ) ，最小描述长度 ( m d l ) 原则，a k a i k e 信息准则( a i c ) ，b a y e s 信息准则( b i c ) 等等，其中以 a i c 和b i c 较为流行，并且得到了广泛地应用和研究 本章如下篇幅，就着重介绍三种经典的模型选择方法 9 2 2 1 结构风险最小化原则( s r m ) 对于小样本集，经验风险最小化原则( e r m ) 的目标是不惜任何代价来最 小化经验风险与此相比，结构风险最小化原则则是寻找经验数据的数量利 用选自给定函数集所得到的对经验数据逼近的品质，以及刻画函数集的容量 值之间的最优关系 s r m 原则可以找到一个函数，它对于固定数量的数据 可以达到保证风险的最小值 我们将结构s 施加到函数l ( z ，a ) ，n a 的集合s 上，使其具有一个结 构s 考虑函数嵌套子集的集合： & c 岛c 岛c - c 晶 其中& = c ( z ，n ) ，口他) 和s = u k & + 定义容许结构为满足下列性质的结构一 1 结构s 的任何元素鼠都具有有限的v c 维h k ( h t 冬b 2 结构s 的任何元素鼠包含 ( i ) 一个完全有界函数集0 ( ：，d ) 反，n 也，( b 1 s b 2 s 或者 ( i i ) 一个非负函数集c ( z ，口) ，a a ，且满足不等式 s 。u 。a p 帮s 靠。( n s 您) 3 集合s 在集合s 中按照度量l 1 ( p ) 是处处稠密的，其中p = p ( z ) 是 抽取样本所依据的分布函数 对于给定的观测集合z l ，z 2 ，钿，s r m 方法选择达到最小保证风险的 结构元素s k s r m 的思想是为给定函数集提供一个容许结构，然后在整个给 定的结构元素上找到最小化保证风险的函数它强调了选择具有适当容量的 结构元素的重要性，描述了容量控制的一般模型+ 另一方面，v a p n j k 在文献 f 5 4 1 中证明了s r m 原则是一致的，在实践中有非常广泛的应用 2 2 2a k a i k e 信息准则( a i c ) 上世纪下半叶，人们从各种观点出发，提出了许多模型选择准则特别是 】0 在七十年代，a k a i k e 等人从信息统计的角度出发，提出的a k a i k e 信息准则 ( a i c ) 被广泛研究与应用 a i c 的基本特点是在某些假设条件下，给出了期望对数似然的一种渐进 无偏估计它是一种在多个可能非嵌套模型中选择的准则，a i c 的应用非常广 泛，尤其在与认知心理学有关的领域例如在结构等价模型( j s r e s k o g ，s o r b o m ， 1 9 9 6 ) 和时频分析( m c q u a r r i ea n dt s a i ，1 9 9 8 ) 中，a i c 可以作为一种模型适 当测度，还可以应用于因子分析，回归和l a t e n tc l a s s 分析等等 a i c 模型选择的目标是，当与真实模型有关的概率分布可以用与估计模 型有关的概率分布来逼近时，来估计信息损失，而真实模型和估计模型之间的 差可以用k u l l b a c k - l e i b l e r 信息数来度量，所以首先我们从k u l l b a c k - l e i b l e r 距离开始介绍 设y 是训练数据，是期望数据，m 是给定的模型口的真实分布与 参数值的最大似然估计的预测分布之间的k u l l b a c k - l e i b l e r 距离如下表示： i =砌) 1 0 9 p且(ylo(y),m) d 雪 0 其中p 是似然，口是模型中所有参数的集合 不难看出，距离越小，预测分布越好若假设数据是由一个分布抽取出来 的，可以在整个训练数据集上对j 进行平均： e ； j 】= 易( 们【j 】= p ( 可) d v p ( 雪) l o gp(yio虻(y),m)d口 a ! m i k e 给出了马 卅的一种逼近： c 。n 8 t 一1 。g ( 工( 口1 可) + 七) ：c 。n s t + 垒孚， ( 2 2 1 ) 如此最小化a i c 等价于最小化( 平均) k u u b a c k - l e i b l e r 距离 a i c 以最小化期望信息损失的标准选择模型( 例如能最小化期望k u l l b a c k - l e i b l e r 距离的模型) ，可以渐进地等价于能最小化a i c 值的模型尬 由( 2 2 1 ) 可得a i c 的表达式为 a i c = 一2 1 0 9 l + 2 k ， ( 2 2 2 ) 其中三对于模型尬的最大似然，可以由调整自由参数的个数来决定 ( 2 2 2 ) 式说明了a i c 通过最大似然和自由参数来衡量所选模型的好坏，另一 方面，a i c 是建立在渐进逼近的方法之上的，所以仅对于充分大的样本集才 适用对于有限的样本集，可以进行如下修正r a i c 。= - 2 l o g l + 2 k 4 一裂葛如k 4 0 ) 尽管a i c 有着广泛的应用，但是a i c 忽略了估计参数的随机采样性，当 参数的似然值不能很好地集中在最大值周围时，它的模型选择效果会很差同 时a i c 不是一致的即当样本集很大时，a i c 模型选择方法有很大的局限性 2 2 3b a y e s 信息准则( b i c ) 近年来，b a y e s 信息准则( b i c ) 成为模型选择中一种很流行的准则，它 克服了a i c 的诸多缺点，但是在实际应用中，它们却能解决不同的问题 b i c 是以一种罚最大似然模型选择准则，被广泛应用在统计文献中对 于大样本集学习，b i c 要求样本独立同分布，而且假设所有模型的先验概率 相等于是它可以应用于任何规则的统计模型，例如最大似然估计器( m l e ) 依范数渐进于真实值的均方情形，方差矩阵等于期望f i s h e r 信息矩阵的逆等 情形另一方面，b i c 还可以用于比较不同参数和不同参数数目的模型如 今人们把它应用于语音和人工智能等瓴域也有很好的前景 给定数据集z = 。l ，茁2 ，。) c 剌，模型集合m = 尬，蝎， 靠) 模型选择问题就是从集合m 中挑选出最适合的模型满足z 的分布 b a y e s 信息准则是一种模型选择准则，它关于她的b i c 值可以如下定义- m c ( 磊) = 一2 l o g p ( z l 舰) + k l o g m 其中p ( z l 尬) 是在模型坛中z 的最大似然，k 是模型m 中独立参数的数 目b i c 选择模型的标准是找到的模型能最小化b i c 值 a i c 和b i c 的表达式非常相似，但是它们是从不同的框架中演变而来 的，由a i c 的表达式可以得到： e i a i c ：l e 一，( 2 2 3 ) 1 2 由b i c 的表达式可以类似得到， e - 啪= l ( 厕一。 由( 2 2 3 ) 式可以看出a i c 中的似然是用e x p ( 一k ) 来修正，而b i c 中的 似然是由( 何) “来修正如果样本集大小= 7 3 8 9 ( 非常小) 时，a i c 与 b i c 相等另一方面，当一o 。时，b i c 是一致的，这克服了a i c 的一个 比较大的局限 a i c 和b i c 都能解决实际中的很多问题，所以很难判定它们之间究竟孰 优孰劣，但是在实际算法中，b i c 所假设的真实模型的维数要比a i c 低得 多 1 3 第三章子空间信息准则( s i c ) 3 1 介绍 二十一世纪初，s u g i y a m a 和o g a w a 从泛函分析的角度出发，提出了一 种新的模型选择准则，即子空间信息准则( s i c ) 它在一些假设条件下，给出 了推广误差的一种无偏估计，是无偏风险估计的一种推广 s i c 所考虑的训练样本是基于 0 ，1 上样本点的一个均匀分布。零均值 和不同方差值的正态分布噪声得到的它假设学习目标函数属于一个特定的 h i l b e r t 泛函空间，定义学习结果和目标函数之间的差的平方h i l b e r t 泛数为 推广误差，即是用所选取函数与真实函数之间的均方差来估计性能 s i c 的 优势在于它是推广误差的一种无偏估计，实验证明依s i c 思想选择的模型得 到的学习结果具有很好的推广能力 s i c 和a i c 有很多的不同其一是推广测度不同，在a i c 中把对全体训 练样本的平均推广误差视为推广测度，面s i c 是有选择的对部分训练样本平 均，从这一点来说s i c 比a i c 精确性更好；其二是逼近方法不同，a i c 采用 渐进逼近方法，并给出了推广误差的一种渐进无偏估计，而s i c 考虑噪声特 性给出了推广误差的一种精确无偏估计；其三对模型的限制程度不同，a i c 只对嵌入式模型的选择有效，而s i c 则对模型没有任何限制 s i c 从提出到今，已经取得了长足的发展，人们从许多方面对它进行了补 充，s i c 的应用也越来越广泛在第四部分中我们将就最小均方学习，正 则化学习和参数模蛩选择几个方面进行探讨 3 2s i c 的定义 监督学习的目标是从由样本点和相对应的样本值组成的训练样本中，寻 找一种潜在的规则如果规则成功获得。那么适当的输出样本值就可以估计出 未知输入样本点，这种能力称之为推广能力s i c 在