（概率论与数理统计专业论文）高效预测的核学习方法.pdf

摘要 以学习理论解决数据分析问题，是近期统计学研究的趋势之一。问题 规模与复杂性曰增的现实，需要更具效率的学习方法。本篇博士学位论文 在统计学习理论的框架下，应用核方法，提出几种新的学习思路，建立起 二套简洁、高效的回归学习机，并成功地用于预测实践。与标准学习方法 比较，新的设计思路，更具效率，能以低的计算代价取得满意的学习效果。 论文围绕学习性能的改进与学习效率的提高两个主题分四个方面展 开。文章首先考虑样本集上信息分布纵横两向上的不均匀性，构造了几种 简洁的动态参数，并引入多元尺度因子，构造多元核。在统一的框架下考 虑参数的改进、优化与特征提取，所得学习机m o - s v r 简明、高效，改进 孝 了原标准学习机的学习性能，为学习机的优化设计提供了一条新思路，其 性能为试验所肯定。 减少学习问题规模是提高学习效率的一种直接途径。文章接下来应用 局部风险最小化原则，导出了局部学习机的一般形式，并分析其理论收敛 界。承m o - s v r 的优化思想，利用快速计算的留一误差，由模式搜索p s 算法实现参数的自动优化，构造出具体的优化局部学习机。为高效学习特 别是大规模的学习问题提供了一条精简的设计思路，其有效性为试验所肯 定。随之，文章从另一个角度提出直接简化d s 策略，以极低的计算代价 将当前先逼近后优化分步走的稀疏思路合二为一，直接在原问题空间上简 化。具体开发了c h o l e s k y 分解算法与共轭梯度算法，保证d s 策略整体上 的高效、简洁。d s 具有一定的创新性，在大规模学习问题中更具有直接 的实践意义，试验肯定了算法性能与理论分析。 i 提高学习效率的另一途径是改变学习方式。论文最后推广当前在线学 习，得到更丰富的学习率下降模式，并在此启示下提出约束随机元方法 _ - l s m d 。l s m d 既有s m d 的自适应调节能力，同时算法的稳定性能又有理论 保证。论文还比较了在线学习的隐式更新与显式更新，导出了隐式更新的 更紧的收敛界。将隐式更新技术与s m d 结合的自适应算法a i l k 具有内在 的稳定性，是一种极具挖掘潜力的学习方法。自适应在线方法为高效学习 开辟了新思路，利用在线学习方式高效率的同时保证了满意的学习性能， 其理论分析与算法性能得到实验的充分肯定。 以学习理论解决数据分析问题必将给统计学带来新的活力，本论文在 此方面做了有益的尝试。所得成果应用并不局限于预测，其构造思路与相 关理论技术亦可推广到其他非核方法的学习领域。论文所做工作丰富了数 据分析处理的理论方法，对统计实践具有一定的指导意义。 关键词：统计学习理论，核方法，m o - s v r ，局部学习，d s ，在线自 适应学习 i i a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m y , s c i e n c ea n dt e c h n o l o g y , t h et a s ko f s t a t i s t i c sb e c o m e sm o r ec o m p l e x ，a n dt h es i z eo ft h ed a t es e ti n v o l v e di so n t h ei n c r e a s e t oc o p ew i t ht h e s ec h a l l e n g e s ，i nt h i sd i s s e r t a t i o n ，w ed e v e l o p s e v e r a lf a s tk e m e lm a c h i n e s ，w h i c ha r es u c c e s s f u l l yu s e di nt i m es e r i e s f o r e c a s t i n g c o m p a r e dw i t he x i s t i n gm e t h o d s ，t h er e s u l t i n gm e t h o d sc a n o b t a i ng o o dp e r f o r m a n c ea tl o wc o m p u t i n gc o s t f o re a c hm a c h i n e ，w em a k ea c l e a rt h e o r e t i c a la n a l y s i sa n dc a r r yo u tas e r i e so fe x p e r i m e n t st oe v a l u a t ei t s p e r f o r m a n c e i m p r o v i n gt h ep e r f o r m a n c ea n de f f i c i e n c yo fl e a m i n gi st h et o p i co f t h i s d i s s e r t a t i o n i np r a c t i c e ，t h ei n f o r m a t i o ni so f t e nd i s t r i b u t e du n e v e n l yo v e r d a t es e t s c o n s i d e r i n gt h i s ，i nc h a p t e r3 ，w ed e v e l o pa no p t i m i z e ds v r ， n a m e l ym o s v r ，w h i c hp e r f o r m sp a r a m e t e r sm o d i f y i n g ，p a r a m e t e r s o p t i m i z i n ga n df e a t u r e ss e l e c t i n gi na nu n i f i e df r a m e w o r k a l lt h ep a r a m e t e r s i n v o l v e da r eo p t i m i z e dw i t hg a ，a n dj u s tb a s e do nt h eo p t i m i z e dm u l t i p l e k e r n e l ，f e a t u r es e l e c t i o ni sc a r r i e do u tt or e d u c et h er e d u n d a n ti n f o r m a t i o n e x p e r i m e n t a lr e s u l t sa s s e s st h ef e a s i b i l i t yo fo u ra p p r o a c ha n dd e m o n s t r a t e t h a to u rm e t h o di sap r o m i s i n ga l t e r n a t i v ef o rt i m es e r i e sf o r e c a s t i n g r e d u c i n gt h es i z eo ft r a i n i n gs e ti sad i r e c tw a y t oi m p r o v et h ee f f i c i e n c y o fl e a r n i n g s oi nf o l l o w i n gt w oc h a p t e r s ，w ed i s c u s st w ow a y sr e s p e c t i v e l yt o r e d u c et h es i z eo fl e a r n i n g f i s t ，w ec o n s i d e rl o c a ll e a r n i n ga n dp r e s e n ti ti n c h a p t e r4 w ep r e s e n tag e n e r a lf o r mf o rl o c a lk e m e lm a c h i n e sa n dd e r i v e da i i i t h e o r e t i c a lb o u n d b a s e do nl e a v e o n e o u te r r o r so rb o u n d s ，p a t t e r ns e a r c h m e t h o di su s e df o rm o d e ls e l e c t i n g i n t e n s i v ee x p e r i m e n t so nar e a lw o r l d e l e c t r i c i t yl o a df o r e c a s t i n gh a v eb e e nc a r r i e do u ta n dt h er e s u l t sd e m o n s t r a t e t h ef e a s i b i l i t yo fo u rm e t h o d so fo b t a i n i n ga ni m p r o v e d g e n e r a l i z a t i o n p e r f o r m a n c ea tar e d u c e dc o m p u t a t i o nc o s t i nc h a p t e r5 ，w ec o n s i d e ra n o t h e r w a yt or e d u c et h es i z eo fl e a r n i n g ，n a m e l yi m p o s i n gt h es p a r s i t yo fk e r n e l r e g r e s s i o nm a c h i n e s d i f f e r e n tt oe x i s t i n gm e t h o d s ，o u rm e t h o dd sc o m b i n e s t w os t e p s ，n a m e l ya p p r o x i m a t i o na n dl e a r n i n g ，a n ds i m p l i f i e st h e l e a r n i n g p r o b l e md i r e c t l yi nt h ep r i m a ls p a c e t h em a i na d v a n t a g eo fo u tm e t h o dl i e si n i t sa b i l i t yt of o r mv e r yg o o da p p r o x i m a t i o n sf o rk e r n e lr e g r e s s i o nm a c h i n e s w i t hac l e a rc o n t r o lo nt h ec o m p u t a t i o n c o m p l e x i t y a sw e l la st h et r a i n i n gt i m e t w oa l g o r i t h m s ，n a m e l yc fa n dc ga r e d e v e l o p e dt or e a l i z et h ei d e a e x p e r i m e n t so nt w or e a lt i m es e r i e sa n db e n c h m a r ks u n s p o ta s s e s st h e f e a s i b i l i t yo f o u rm e t h o d a sa n o t h e rp o p u l a rw a y , k e r n e lb a s e do n l i n ea l g o r i t h m s ，w h i c hf o r m u l a t e t h el e a r n i n gp r o b l e ma sas t o c h a s t i cg r a d i e n td e s c e n ti nr k h s ，a r ep r e s e n ti n t h el a s tc h a p t e r e x i s t i n ga l g o r i t h m sa r ee x t e n d e da n dt h er e s u l t i n ga l g o r i t h m s p r o v i d em o r ep a t t e r n sf o rl e a r n i n gr a t ed e s c e n t i n s p i r e db yt h i s ，w ed e v e l o pa n e ww a yl s m dt oa d a p tl e a r n i n gr a t e sa u t o m a t i c a l l y , w h i c hu s e ss t o c h a s t i c m e t a - d e s c e n ta l g o r i t h mw i t h i nal i m i t e dr a n g et ok e e pt h ea l g o r i t h ms t a b l e i l ka l g o r i t h ma d o p t i n gi m p l i c i tu p d a t ei sa l s od i s c u s s e dh e r ea n dt h er e s u l t s s h o wt h a t ，c o m b i n i n gs m dw i t hi l ki sa n o t h e rp r o m i s i n gw a yf o ro n l i n e l e a r n i n g ，w h i c hp o s s e st h ei n h e r e n ts t a b i l i t ya n da d a p t i v ea b i l i t ya sw e l l w e d e m o n s t r a t et h e o r e t i c a l l yt h es u p e r i o r i t yo fi m p l i c i t u p d a t e o v e re x p l i c i t u p d a t e f o ro n l i n el e a r n i n ga n dd e r i v es o m et h e o r e t i cr e s u l t sa b o u tt h e c o n v e r g e n c eo ft h ea l g o r i t h m si n v o l v e di nt h i sc h a p t e r e x p e r i m e n t so nar e a l t i m es e r i e sa n dt w ob e n c h m a r k sc o r r o b o r a t et h et h e o r e t i c a lr e s u l t s ，a n ds h o w t h a to u ra l g o r i t h m so u t p e r f o r mm o r ep r i m i t i v em e t h o d s b a s e do np r e v i o u sw o r k ，w ep r e s e n ts u c c e s s f u l l ys e v e r a lk e r n e lm e t h o d s f o rr e g r e s s i o nm a c h i n e s c l e a r l y , t h er e s u l t i n ga l g o r i t h m sa r en o tl i m i tt ou s e i nt i m es e r i e sf o r e c a s t i n g t h e yc a nb eu s e di no t h e rc a s e s ，a n dt h ei d e ac a n a l s ob ee x t e n d e dt on o n - k e r n e ll e a r n i n gm e t h o d s l e a r n i n gf o r md a t ap r o m p t s t h e d e v e l o p m e n to fs t a t i s t i c s ，a n di nt u r n ，t h ed e v e l o p m e n to fs t a t i s t i c s p r o v i d e sm o r et h e o r e t i cs u p p o r tf o rl e a r n i n g w eb e l i e v e , i ns o m es e n s e ，t w o t h i n g sa r eo n ea n do u rw o r kw i l lc o n t r i b u t es o m e t h i n gt oi t k e yw o r d s ：s t a t i s t i c a ll e a r n i n gt h e o r y , k e r n e lm a c h i n e s ，m o - s v r ， d s ，l o c a ll e a m i n g ，a d a p t i v eo n l i n el e a r n i n g v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在论文中作了明确的说明。 作者签名：伽 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位 论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用 复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所 将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 作者签鸫超a 导师签名继日期舻工月立日 博 ：学位论文绪论 第1 章绪论 随时代的发展与社会的进步，数据的分析与处理在各研究与应用领域，地位日显 重要，其本身的理论与技术亦不断发展。在反思传统参数统计学的基础上，v a p n i k 等人结合计算理论、机器学习等领域的学术思想，创立了统计学习理论，并在其理论 框架之下开发出支持向量机等功能强大的数据处理工具。本文将在统计学习理论的框 架下应用核方法，构造一套高效率的预测学习机器。 1 1 问题背景与意义 随经济技术的迅速发展，统计领域不断受到来自科学界与产业界的挑战。早期， 这些问题通常来自农业与工业试验，规模相对较小。现今，随计算机与信息时代的到 来，统计问题的规模与复杂性都急剧增加。像具有代表性的三大类数据：经济金融数 据，生物数据与网络信息数据，都呈现出新的特点。主要表现在数据的规模、关系的 复杂性与数据缺失及污染几个方面。具体而言，数据规模剧增，表现在数据量与维度 上。经典统计经常面对的往往是几十到数百样本， 而当下数据量动辄成千、上万，甚至是十万以上的海量。无疑，处理技术的“效 率”成为关键问题。更具有挑战性的是数据的维度也随之飙升，带来所谓的“维度灾 难”汹1 魄1 眠1 。我们所面对的不再只是一元、几元的问题，几十维，上百维的问题在 宏观经济建模、生物数据分析以及图像处理、文本分析等方面屡见不鲜。维度问题不 容回避。同时，数据所蕴含的内在关系越来越复杂，“线性一工具已明显不足，非线 性特征必须纳入我们的研究之中。最后，由于测量、观察以及实际条件等方面的限制， 我们获取的数据难免缺失或受到污染，从而要求我们探索更具“稳健性 的处理方法。 数据的新特点提出了新要求，也必然带来学科发展的新机遇，像数据挖掘就是此 种背景下的新兴学科哺1 。众所周知，无论在理论上还是在应用中，预测问题一直都是 统计学科与计算学科关注的重要领域瑚溉峨啪i 0 4 , i 0 5 。如何顺应时代的发展，探索一套 稳健、高效，涵盖非线性，能处理高维问题的预测建模方法就成为本文的研究重点。 与常见统计方法不同，本文将从统计学习理论的角度处理预测问题。 统计学习理论基本体系由v a p n i k 建立于2 0 世纪7 0 年代n 瞄1 。在这一理论框架 下，于2 0 世纪9 0 年代产生了支持向量机( s v m ) 这一新的学习工具n0 蔬施嘲。由于其 理论体系完备，实际表现优良，统计学习理论成为了当下的研究热点，并推动了数据 分析技术的迅速发展。很多学习问题在统计学习框架下被重新考虑。 统计学习理论主要研究从数据到分布的归纳机理问题。由于我们观测到的只是有 限样本集合，如何从有限的样本集合得到分布意义下的某种求解目标的最优，就成为 博i ：学位论文 绪论 统计学习研究的主要内容。可见，统计学习理论主要解决基于有限观测( 样本) 的目 标函数和基于分布的目标函数之间的关系。一个直接的想法便是先利用有限观测所得 样本估计分布，再由估计所得分布进行推断。这种先归纳后演绎思路常为经典统计所 采用。与之不同，在有限信息下完成推理，统计学习理论则遵循一个更为简洁原则， 即如果你对所求问题只拥有有限信息，那么你应试图直接求解问题，而不是以求解一 个更一般的问题作为中问问题n 0 4 1 。可能的情况是，所得信息足以直接求解问题，但不 足以解决一个更一般的问题。 统计学习理论与传统统计学的主要区别还在于其推理理论依据不同。传统统计学 的推理主要依据大数定理，从而必然会对所得样本提出较高要求并导致结论的渐近 性。显然，必需样本量的增加还会带来计算方面的问题。统计学习理论则是以学习领 域的p a c 框架( p r o b a b l ya p p r o x i m a t e l yc o r r e c t ) 的形式给出学习机( 模型) 关于 泛化性能( 推广能力) 的界n 帆州1 ，从而认识学习精度和样本量之间的关系。统计学习 理论第一次强调了“小样本统计学修问题。在很多问题上，通过考虑样本数量，学习 理论可以得到比传统统计技术更好的解。新框架下的统计推断规则，不但要求满足渐 进性质，还要保证有限信息下的最好结果。 支持向量机是在建立在统计学习理论基础上的一个准则性的学习系统。它先将输 入向量按预定的某一非线性变换映射到高维特征空间，在该特征空间中构造线性函数 的假设空间，再在构造的假设空间中寻找最优假设。显然选择何种变换进而确定特征 空间是关键的一环，直接决定需要学习的目标函数的复杂程度( 表现形式) 并进而决 定学习任务的难度以及学习机的泛化能力。m i n s k y 与p a p e r t 在2 0 世纪6 0 年代就 指出线性学习机计算能力有限瞄1 。现实世界的复杂性要求我们构造比线性函数更富有 表达能力的假设空间。也就是说，目标函数通常难以由给定属性( 输入数据) 的简单 线性函数组合而产生，我们应该探求数据更为抽象的特征。多层阈值线性函数就是解 决这一问题的途径之一，由此导向了多层神经网络和学习系统的后向传播算法1 。 核表示方式则为之提供了另一种有效解决途径，隐式地将数据非线性地映射到高 维空间h j 辅鹅1 。由于正定核具有诸多优良特征，而正定核又对应一个再生希尔伯特空 间( r k h s ) n 乙剐町，因此许多学习任务往往都在r k h s 中考虑。支持向量机的一个重要 特征就是在一定程度上逼近理论的问题与学习理论的问题相互独立。因此，我们可用 一种通用而相对独立的方式研究核表示方式，并在不同的学习理论中使用它。核方法 另一个优势在于其学习算法与理论同具体应用领域的特性在很大程度上分开，而这些 具体特性可通过核函数的设计与选择加以体现。 在支持向量机迅速发展的同时，其他使用核方法的理论与算法也成为研究活跃的 领域。正则化网络( r n ) “引1 、高斯过程( g p ) 随船剐1 2 1 就是其中的典型代表。由于 核方法的相对对立性，同时核方法能涵盖非线性特征、克服维数灾难，以核方法为主 线研究预测问题将具有相当的理论与实践意义，也存在研究的空间。 2 博t 学位论文 绪论 学习效率是我们面对的另一问题。一方面我们处理的数据规模加大，另一方面应 用中对学习速度要求也越来越高。比如金融市场的股指预测嗽9 7 1 ，电力市场上的负荷 预测j 刳，预测速度直接关乎交易的成败。其他学习任务上亦是如此。像图像处理m 1 学习效率直接影响图像质量与流畅性；像自动驾驶，学习效率直接决定反应速度并影 响设备成本；像网络文本信息处理h ，学习效率也左右了网络运行质量、信息处理与 传输效率，等等。显然，学习效率问题的提出不只是为了理论上的完美，更直接服务 于实践。 那么如何在保证学习精度的f ；i f 提下降低计算成本，提高计算速度? 一个直接的想 法就是减少工作集的规模，也就是说减少学习所用的样本，只选取所得样本中的一部 分用于学习。我们主要考虑局部方法与稀疏简化方法。局部学习就是在兴趣点( 待学 习的点，比如需要预测的点) 邻域内考虑学习 5 , 7 , 3 4 , 4 2 , 6 1 。显然，如果我们在整个输入 空间上考虑学习，函数的复杂性必然会更高，因为我们要保证学习所得函数能在整个 输入空间上给出一个合理的精度。而在兴趣点邻域内考虑学习，我们可用相对简单的 函数逼近学习目标，也就是用过局部地逼近学习目标，就可以达到较高的学习精度。 当然这又涉及如何将输入空间合理划分以得到好的局部学习精度问题，解决的办法是 最小化局部风险。与局部方法不同，稀疏方法仍然在整个输入空间上考虑学习问题， 但不是利用整个样本集，而是按某一准则选取一部分样本为代表进行学习 啪m 舢，4 4 她瓴1 1 3 。学习所得模型在整个输入空间上应具有合理的学习精度并具有强的泛 化能力。 提高学习效率的另一个途径则是改变学习模式。通常，我们进行学习，都是在获 取样本集( 所能得到的全部样本) 之后再行讨论，与此对应的是批量学习( b a t c h l e a r n i n g ) 。由于信息充足，批量学习往往能给出一个高精度的学习结果，但计算成 本往往也比较高。在线学习( o n l i n el e a r n i n g ) 考虑的则是另一种情况，即一边获 取样本一边进行学习 2 1 , 5 6 , 5 7 , , 5 8 , 5 9 , 6 2 , 9 0 , 1 1 5 。从某种意义上讲，这是一种更搿自然 的学习 模式。在线学习并不等到获取全部样本之后才开始，而是充分利用当前所得信息直接 进行学习。每获得一个新样本就对以前的学习结果进行一次修正、更新，而不是从头 再来学习一次，因此在线学习往往具有更高的学习效率。 当然，如何在保证甚或是提高学习精度的前提下提高学习效率，并不局限于上述 思路，具体方法也需要我们进一步研究。从而，在统计学习理论的框架下，应用核方 法讨论高效率预测的学习建模问题自然地成为我们的研究任务。更多的技术细节与文 献评述将在后面的章节中逐一展开。 1 2 本文工作及结构 本文在统计学习理论的框架下，应用核方法建立一套高效率的预测学习机，并用 3 博： ：学位论文 绪论 以解决实际问题。所得理论结果与算法性能都在详尽的试验中得到确证与检验。论文 的主体部分首先讨论学习机性能的改进与优化，并构造相应学习机。接下来将就减少 工作集规模的两种方法展开研究，构造局部学习机与稀疏学习机。最后我们讨论在线 学习模式，构造稳健、高效的自适应在线学习机。每种学习机自成一章，第二章则就 作者的理解，对统计学习理论与核方法的理论主线做必要回顾。全文共计6 章，相关 定理证明在附录1 中给出，引用定理的证明则可在参考文献中找到。 论文涉及的基本概念、基本技术与必需的理论结果都在第二章给出，是我们研究 的起点。我们首先从经验风险最小化出发，再到不定方程，最后导出结构风险最小化， 介绍统计学习理论基本框架与思路。进一步，我们讨论核与再生希尔伯特空间，利用 正则化方法导出核方法的一般模式。最后部分则对常见的三种核学习机，即支持向量 机s v m 、正则化网络r n 与高斯过程g p 一一做了介绍。第三章考虑样本集上信息分布 纵横两向上的不均匀性，构造了几种简洁的动态参数，并引入多元尺度因子，构造多 元核。在统一的框架下考虑参数的改进、优化与特征提取，所得学习机m o - s v r 简明、 高效，为学习机的优化设计提供了一条新思路。结合其他学习技术，该学习机的性能 在四个不同规模的数据集上得到了检验与肯定。其思想在后述几个学习机上也得到了 应用。文中的主体成果已经在相关国际杂志上发表。 接下来的两章考虑如何减少工作集，提高学习效率。第四章应用局部风险最小化 原则，导出了局部学习机的一般形式，并分析其理论收敛界。承m o - s v r 的优化思想， 利用快速计算的留一( 1 e a v e o n e o u t ) 误差或其误差界，由p s 算法实现参数的自动 优化，构造出具体的优化局部学习机。为高效学习特别是大规模的学习问题提供了一 条精简的设计思路，通过一系列的试验，学习机的有效性在一个真实的电力负荷时间 序列上得到了肯定。文中的主体成果已经在相关国际会议上发表。 第五章从另一个角度实现工作集的减少，即采用稀疏技术构造简化的核回归机。 当前文献的主要思路是首先用一低阶矩阵或基函数逼近g r a m 矩阵k ，再求解近似后的 学习机。而求解近似学习机的常见方法是先转化原问题为对偶问题然后再行优化求 解。我们的思路更为直接，规模递增地选择一列基函数逼近待学习的目标函数，使得 该目标函数直接最小化风险泛函。通过光滑化损失函数或直接选用类似二次损失函数 的光滑的损失函数，我们具体开发了c h o l e s k y 分解( c f ) 与共轭梯度技术( c g ) ，高 效率地学习。由于我们一方面简化了基函数，计算复杂性由o ( t 3 ) 下降为o ( t d 2 ) ，这里， 表示样本规模而d ，表示基函数规模；另一方面我们采用c f ( c g ) 技术直接求解学 习机，又降低了复杂性常数。d s 策略具有一定的创新意义，在大规模学习问题上更具 直接的实践意义，试验结果肯定了算法性能与理论分析。部分成果已经在相关国际会 议上发表。 论文最后一章研究在线高效学习模式。如何利用在线学习模式的高效率优势的同 时提高在线学习的精度是本章的研究任务。我们讨论了显式更新( e x p l i c i tu p d a t e ) 4 博上学位论文 绪论 与隐式更新( i m p l i c i t u p d a t e ) 两种学习方法，并从理论与实证两个方面论证了隐 式更新的优势。进一步，我们推广当前在线学习，得到更丰富的学习率下降模式，并 在此启示下提出约束随机元方法( l i m i t e ds t o c h a s t i c m e t a d e s c e n t ，简记为l s m d ) ， l s m d 既有s m d 的自适应调节能力，同时算法的稳定性能又有理论保证。最后我们结合 隐式更新与s m d 两者的优势，得到的自适应算法a i l k 具有内在的稳定性，是一种极 具挖掘潜力的学习方法。自适应在线方法为高效学习开辟了新思路，其理论分析与算 法性能得到详尽实验的充分肯定。部分前期成果即将( 2 0 0 8 年6 月) 在i e e e 世界计 算智能会议上发表。 实践的需求一直是科学发展的动力之一，考虑到数据呈现出的新特点以及社会对 高效、稳健预测模型的迫切需求，本博士学位论文在前人工作的基础上，提出几种新 的学习思路，构造相应的回归学习机并用于预测实践。其良好性能将在实际问题中得 到进一步检验。显然，所得成果的应用不局限于预测，其构造思路与相关理论技术亦 可应用到其他非核方法的学习领域。以学习理论解决数据分析问题必将给统计学带来 新的活力，而统计学的发展也必然为学习理论提供更多的理论支持。我们在此方面做 了新的尝试，所做工作也将会对两者的发展起到一定的积极促进作用。 博卜学位论文 学习理论中的核方法 第2 章学习理论中的核方法 为从数据中找到一种函数依赖关系，传统参数统计学往往将备选函数集定义为与 参数呈线性关系的只含少数自由变量的函数的集合，对数据所隐含的统计分布规律也 有很强的假定，比如说正念律，其推理依据是大数定律，所得结论都是渐进性的。现 实中的情况往往与此背离。如前所述，数据中的依赖关系也许有很强的非线性特征， 隐含的统计成分也不一定能用经典的统计分布函数来描述。更为重要的是，我们的统 计推断必须在有限信息下完成。对渐近性的结论而言，我们并不知道拥有多少的样本 量才能充分保证结论的可靠性。同时在实际中，问题规模的可计算性、计算效率也都 是必须考虑的问题，“维数灾难 便是其中突出的问题之一。因此，如何完成有限信 息下的统计推理( 小样本理论) 自然地成为现代统计学家关注的问题。正是在反思传 统参数统计学的基础上，v a p n i k 等人基于g 1 i v e n k o 、c a n t e l l i 与k o l m o g o r o v 开创的 立足于经验分布的统计推理体系( 非参数体系) ，结合计算领域的思想成果，创立了 统计学习理论，而此框架下的核方法则能巧妙地处理高维、非线性问题。 2 1 统计学习理论 本文中的学习问题是指依据有限观测( 经验数据或者说样本信息) 来寻找待求的 函数依赖关系的问题，即从实例中学习，对应于机器学习中的有指导的学习。 设我们已经观察到一个实例序列，即，个样本数据对， d = ( ，只) 2 。( z ，y ) 7 ， ( 2 1 1 ) 其中，薯z 为刀维输入向量，zcr ”为输入空间，y 酞为输出( 目标) 变量， y 为目标空间。我们的工作就是在给定观测d 的基础上，构造一个对未知的目标算子 s ：疋_ y 的适当一个逼近。具体而言，我们逼近什么? 对此的两种不同回答导出处理 学习问题的两种不同思路。 第一种思路是我们模仿目标算子，即构造一个模仿算子墨：疋一步，使得 鬼( y ，y ) 最小。这里，y 表示目标空间的预测空间，既，( ，) 表示定义在度量空间q 上的距离。 第二种思路则更强一些，辨识目标算子，即构造一个逼近算子s ：石专3 ，使得 风。( s ，是) 最小。需要进一步说明的是，此处“构造一个算子一的具体含义是，通过学 习机实现某一固定的函数集f ( x ，口) ，a a ，其中人是参数集( a 不同则表示对应的函数 不同，a 可以为标量，向量或抽象元素) ，而学习的过程就是就是从该给定函数集 厂“口) ，口人中选取一个适当函数的过程，也就是确定参数a 的值。此处的“函数 在 6 博士学位论文 学习理论中的核方法 学习理论文献中又常称为一个“假设，函数集f ( x ，口) ，a 人则相应地称为“假设空间 或“假设集，记为歹。 两种逼近思路存在本质的差别。第一种给出最佳预测结果即可，方法上有一套非 渐近理论。第二种则更为困难一些。不仅要给出好的预测结果，还要构造对目标算子 的一个好的逼近算子。通俗地讲，就是不仅能够进行预测而且还要能够解释内在机理。 该思路涉及不适定问题，方法上只有渐近性的理论。我们先分别讨论两种方法然后再 在此基础上导出另一种新的归纳原则。 2 1 1 经验风险最小化 遵循上述第一种思路中，以最小4 9 p 的函数歹。我们首先实现度量晚，( y ，夕) ，定义损失函数来评价预测准确程度。这 里的预测是通过选择某个函数而推断出的结果。 定义2 1 1 ( 损失函数) 设工疋= 科，输出y y ，引进3 元组 l ( x ，y ，a ) ) x x y y ，若映射l ：x x y x y r + 使得对任意的工疋= i t ”，y y ， 都有l ( x ，y ，y ) = 0 ，则称为一个损失函数 对预测而言，我们构造回归学习机，常采用的损失函数有二次损失函数，e 一不 敏感损失函数和h u b e r 损失函数等，其具体形式分别为 l ( x , y ，( x ，口) ) = 二( y 一厂( x ，口) ) 2 ， ( 2 1 2 ) l ( x ，只f ( x ，口) ) ： y f ( x ，口) l 。， ( 2 1 3 ) l ( x , y ，f ( x ，口) ) 爿y - f ( x ，口) h , e ( 2 1 4 ) 其中，我们记 l y 一厂c z ，口，t = | y 一厂。三口，i 一，：；二公耋兰；：三： c 2 t 5 ， l y f ( x ，a ) l 片。= 荔1 ij ，一似 口) i ，l y 一厂( 硎。 ( 2 1 6 ) i ) ，一厂( x ，口) l 一詈， i 夕一厂( x ，口) i c 损失函数是对某一点预测效果的评价，为从整体上评价所选函数的品质，我们引 入观测的概率分布，定义期望风险为其一个品质准则。 定义2 1 2 ( 风险泛函) i 殳f ( x ，少) 为x x y 上的概率分布，l 为给定的损失函数， 则称数学期望 r ( 口) = f l ( x ，y ，f ( x ，a ) ) d f ( x ，y ) ( 2 1 7 ) 7 博：学位论文学习理论中的核方法 为风险泛函。 确定待求函数f ( x ，口) ，也就是确定参数a a 对应值，我们通过最小化泛函( 2 1 7 ) 来实现。换言之，我们的学习目标就是在概率测度f ( x ，y ) 未知、所有可用信息都包含 在训练集( 2 1 1 ) 式中的情况下，寻找最优函数厂( 五a o ) ，使它在函数类f ( x ，口) ，口人 中最小化风险泛函r ( 口) 。 由于定义风险泛函的概率分布f “y ) 未知，我们不能直接最小化风险泛函。那最 小化什么? 对此的回答确定了解决学习问题的归纳原则。我们首先介绍经验风险最小 化原贝i j n j 峙】。 定义2 1 3 ( 经验风险泛函) 设给定训练集d = ( x ，咒) 谁。( z ，y ) 7 ，其中 五, - ycr ”，咒y r ，并且给定损失函数。所谓经验风险泛函是指 1， ( 口) = ( 毛，咒，厂( 丐，a ) ) ( 2 1 8 ) 定义2 1 4 ( 经验风险最小化归纳原则) 设任意给定训练集d ，并且给定损失函 数所谓经验风险最小化归纳原则是指用最小化经验风险泛函( 2 1 8 ) 式的函数 l ( x , y ，厂“口，) ) 近似最小化风险泛函( 2 1 7 ) 式的函数( x ，j ，f ( x ，口0 ) ) ，简称e m r 原则。 现在的问题是在什么条件下，l ( x ，y ，f ( x ，q ) ) 能够为l ( x ，y ，f ( x ，) ) 提供一个良好地 逼近? 换言之，也就是在什么条件下e m r 原则的学习过程是一致的。关键定理给出了 e m r 原则一致性的充分必要条件。 定义2 1 5 ( 一致性) 设d = ( ，舅) ) ：= 。是按概率分布f ( x ，y ) 得到的独立同分布的 样本集，z ( x ，y ，f ( x ，q ) ) 是最小化经验风险泛函( 2 1 8 ) 的函数若下面两个序列依 概率收敛于同一极限，即 r ( a t ) 寺i 矾n f r ( 口) ， ( q ) 寺骤只( 口) ， 则称e m r 原则对函数集l ( x ，y ，f ( x ，口”，口a 和概率分布f ( x ，j ，) 是一致的。 定理2 1 1 ( 关键定理1 ) 设函数集( x ，y ，f ( x ，口”，口人满足条件 彳p ( x ，y ，厂( x ，口) ) 扭( 工，y ) b , ae 人， ( 2 1 9 ) 那么，e r m 原则一致性收敛的充分妊要条件是：经验风险泛函( 口) 在函数集 l ( x , y , f ( x ，口) ) ，口a 上在如下意义下一致收敛于实际风险r ( 口) ： ! i m p s 1 l p r ( 口) 一墨唧( 口) 占) = o ，v 占 0 卜o d e 一致性是一个渐近概念，我们需要表述有限观测条件下学习的可靠性， 引入描述函数集丰富程度的“容量概念汹t 州1 。 为此我们 定义