《粗糙空间上结构风险最小化原则》由会员分享，可在线阅读，更多相关《粗糙空间上结构风险最小化原则（40页珍藏版）》请在金锄头文库上搜索。
1、河北大学 硕士学位论文 粗糙空间上结构风险最小化原则 姓名：赵春雷 申请学位级别：硕士 专业：应用数学 指导教师：哈明虎；田大增 2011-05 摘 要 I 摘 要 统计学习理论是处理小样本学习问题的重要理论方法。然而，该理论是建立在概率 空间上基于实随机样本的， 它难以讨论和处理现实世界中客观存在的涉及粗糙空间上粗 糙样本的小样本统计学习问题。结构风险最小化原则是统计学习理论的核心内容之一， 是构建支持向量机的重要基础。基于此，本文研究了粗糙空间上结构风险最小化原则。 首先，给出了粗糙空间上粗糙变量退火熵、生长函数和 VC 维的定义，并证明了它们的 一些性质；其次，构建了粗糙空间上基于 VC
2、 维的风险泛函的界；再次，给出了粗糙空 间上结构风险最小化原则， 证明了该原则的一致性， 同时推导出了收敛速度的界； 最后， 给出了粗糙空间上结构风险最小化原则的直接实现。 关键词 粗糙空间 VC 维 风险泛函的界 结构风险最小化原则 直接实现 Abstract II Abstract Statistical Learning Theory is important regarded as a sound framework that handles a variety of learning problems in presence of small size data samples. H
3、owever, Statistical Learning Theory is built on probability space and based on real random samples, so it can hardly handle statistical learning problems built on rough space and based on rough samples, which can be encountered in real world scenarios. Structural risk minimization principle is one o
4、f the kernels content of Statistical Learning Theory. The principle is the theoretical fundamentals of establishing the support vector machine. Based on above, the structural risk minimization principle based on rough samples is explored in the paper. Firstly, the concepts of annealed entropy, growt
5、h function and VC dimension as well as their properties on rough space are given. Secondly, the constructive and distribution-independent bounds with VC dimension on rough space are presented. Thirdly, the structural risk minimization principle on rough space is proposed. The consistency of this pri
6、nciple is proven, and asymptotic bounds on the rate of convergence is derived. Finally, the structural risk minimization principles direct implementation on rough space is given. Keywords Rough space VC dimension Bounds on the risk functional The structural risk minimization principle Direct impleme
7、ntation 第 1 章 绪 论 1 第 1 章 绪 论 1.1 粗糙空间上结构风险最小化原则的提出及意义 统计学习理论（Statistical Learning Theory, SLT）是在 20 世纪 60 年代由Vapnik 等 1-3提出的，90 年代中期建立的一种利用经验小样本数据进行机器学习的一般理论。由 于其理论体系的完备性和实际应用的广泛性， 统计学习理论备受机器学习及相关领域科 研和工程技术人员的青睐4。统计学习理论实际上是从给定数据集中估计函数依赖关系 的方法，后来发展了一种能够解决维数灾难、局部极小点、过拟合等实际问题比较通用 的算法支持向量机5（Support Vec
8、tor Machine, SVM） 。这些方法，是在统计学习理 论的基础上建立起来的，主要包括以下四方面重点内容2 ： （1） 关于统计推断一致性的充分必要条件的一系列概念； （2） 在这些概念的基础上的反映学习机器推广能力的界； （3） 在这些界的基础上的针对小样本数的归纳推理原则； （4） 实现这种新的推理的方法。 统计学习理论是各部分密切联系的一个不可分割的整体，简化它或将其中一部分 与其他部分分割开来的都会影响理论和实际应用。从学习理论的数学部分考虑，学习机 器可以推广仅仅是因为它们采用了有限容量的结构元素，所以，利用小样本集机器不能 解决绝大多数的可能的形式化问题1。要想取得成功，学
9、习机器必须使用函数集上的结 构，而这样的结构要适合于我们所研究的问题，它在对学习现象的理解和对实际应用来 说都是非常重要的1，在这方面国内外学者已经取得了一些成果4-19。 结构风险最小化原则是以一致收敛速度的界为主要理论基础的，而一致收敛速度 的界是训练误差、学习机器所实现的函数集的VC维和观测样本数的函数，因此为了最 小化训练错误，我们必须从更广的函数集中选取函数，而不是从小VC维的窄函数集中 选取函数1。换句话说就是，结构风险是经验风险和置信区间这两项的和20，并且它是 期望风险的一个上界，由于我们最小化期望风险很困难，所以可以考虑最小化期望风险 上界的结构风险。 由一致收敛速度的界，
10、我们知道置信区间是训练样本个数的递减函数， 且当训练点足够多时置信区间趋向于 0。这显示了当训练点很多时置信区间的值不大， 可以用经验风险取代期望风险。 但是当训练点较少时， 则可能必须考虑置信区间的作用。 同时我们知道置信区间也依赖于VC维，它是VC维的递增函数，经验风险与之相反，所 河北大学理学硕士学位论文 2 以要使结构风险达到最小，应该兼顾经验风险和置信区间两方面的影响。 基于概率空间上的统计学习理论在处理小样本问题上具有很强的优势， 它是建立在 概率空间上基于实随机样本21-23的， 故它在处理现实生活中存在的非概率空间上的学习 问题和概率空间上基于其他样本的学习问题。 因此在这些方
11、面的研究引起国内外许多学 者的关注，如：哈明虎，李颜9等推导出了非概率空间Sugeno测度空间上的统计学习理 论的关键定理；哈明虎, 田景峰, 张植明 10-11讨论了概率空间上基于非随机样本的结构 风险最小化原则， 其中包括复随机样本和双重随机样本等； 哈明虎， 王超， 张植明等4在 其著作“不确定统计学习理论”中构建了处理广义不确定测度空间上基于广义不确定样 本机器学习问题的统计学习理论（简称为不确定统计学习理论） ；刘杨讨论了粗糙空间 上基于粗糙样本的统计学习理论的关键定理和学习过程一致收敛速度的界， 本文在她的 基础上结合信赖性理论24-28的相关知识，给出了粗糙空间上退火熵，生长函数
12、，VC维 的概念及其相关的性质，以此为基础构建了粗糙空间上基于VC维的风险泛函的界，进 一步构建了粗糙空间上结构风险最小化原则并给出了它的一个直接实现。 1.2 本文的主要内容 本文研究了粗糙空间上结构风险最小化原则，主要内容如下： 1. 第 2 章是简单介绍了一下粗糙变量的相关知识， 给出了凸规划问题及对偶问题的 定义和相关定理。 2. 第 3 章定义了粗糙空间上退火熵、生长函数、VC 维，并推导出了基于 VC 维的 风险泛函的界。 3. 第 4 章给出了粗糙空间上结构风险最小化原则， 推导出了该原则的一致性及收敛 速率的渐近界。 4. 第 5 章在第 4 章的基础上构建了粗糙空间上结构风险
13、最小化原则的直接实现。 5. 第 6 章给出了本文的主要结论， 总结了不足和缺点， 并且提出了未来的研究方向。 第 2 章 预备知识 第 2 章 预备知识 这一章主要给出了粗糙空间上的基本知识，讨论了信赖性测度的一些性质，给出了 粗糙空间上期望的概念及相关性质，同时还给出了凸规划问题的概念及相关性质。 2.1 粗糙变量基本知识 首先我们给出粗糙空间的定义并进一步讨论它的一些性质。 为了描述粗糙变量，有必要给出下面 4 条公理28。设为一个非空集合，A为一 由的子集构成的代数，为A中的一个元素，为定义在上的一个实值集函数， 并满足如下四条公理： A 公理一： ； 公理三：对所有的AA， 0A；
14、公理四：对任意不相交事件序列 (1,2,) i Ai =? ,有. 11 = = = i i i i AA 事实上， 满足四个公理的集函数显然是一个测度， 而三元组( , ) A是一个测度空间。 定义 2.1定义 2.128 设为一个非空集合，为一由A的子集构成的代数，为A中的 一个元素， 为定义在上的满足如上 4 条公理的一个实值集函数，则称四元组A ( , , ) A为一个粗糙空间。 定义 2.2定义 2.228 设( , , ) A为一个粗糙空间，是A中的一个事件，则称 事件A的上信赖性定义为： = A ATr, 事件A的下信赖性定义为： = A ATr, 事件A的信赖性定义为：)( 2
15、 1 ATrATrATr+=. 定理 2.1定理 2.128 设( , , ) A是一个粗糙空间，则信赖性Tr是A上的一个测度，且满 足： (a) 1;Tr = 3 河北大学理学硕士学位论文 (b) 0;Tr= (c) 是单调增的，即当TrAB时， ;Tr ATr B (d) Tr是自对偶的，即有A A 1. c Tr ATr A+= 定义 2.3定义 2.328 设( , , ) A为一个粗糙空间，是从A到实数集R的函数， 若对R的 任意集BorelB，有 ( )B A. 则称为粗糙空间( , , ) A上的粗糙变量。更进一步，我们称 ( ), ( ) = 分别为粗糙变量的下近似和上近似。 定义定义 2.428 假设为粗糙变量，为的信赖性分布。 若存在函数:对 所有的 )0,R + (),x +满足 ( )( ) x xy dy =， 则称为粗糙变量的信赖性密度函数。 定义定义 2.528 设 12 , n ?为粗糙变量，如果对于R的任意集Borel 12 , n B B ? B ，有 , 1 ,1,2, n iiii i TrBinTrB = = ? 那么称 12 , n ?为相互独立的粗糙变量。 定义 2.6定义 2.627 设 12 , n
