所有函数(包括使经验风险最小的函数)，经验风险R、(w)和实际风险R(w).pdfVIP

第四章 统计学习理论概述 大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其 VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n+l。对于一些比较复杂的学习机器 (如神经网络)，其VC维除了与函数集 (神经网结构)有关外，还受学习算法等的影响，其确定更加困难。对于给定的学习函数集，如何计算其VC维是当前统计学习理论中有待研究的一个问题。 统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。对于二值分类问题，结论是:对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险R、(w)和实际风险R(w)之间以至少1一粉的概率满足如下关系。，_八，。，_、.1}人(ln(Zn/h)+1)一h(。/4)} ，月。、八、叼 孟几e即气即，宁钊1— } 、，一，7 钊 n l 其中h是函数集的VC维，n是样本数。 这一结论从理论上说明了学习机器的实际风险是由两部分组成的:一是经验风险 (训练误差)，另一部分称作置信范围，它和学习机器的VC维及训练样本数有关。可以简单地表示为 R(w)‘RemP(w)+。(h/n) (4一10) 它表明，在有限训练样本下，学习机器的VC维越高 (复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。 这里给出的推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当vC维较高时更是如此。当 h/n0.37 时这个界肯定是松弛的5。而当VC维无穷大时，这个界限就不再成立。而且，这种界只在对同一类学习函数进行比较时有效。可以指导从函数集中选择最优的函数，而在不同函数集之间比较却不一定成立。 4.23结构风险最小化 如前所述，经验风险最小化原则在样本有限时是不合理的，需要同时最小化经验风险和置信范围。其实，在传统方法中，选择学习模型和算法的过程就 — 31一 基于认七b文本挖掘的SVM网页文本分类研究 是调整置信范围的过程，如果模型比较适合现有的训练样本 (相当于h/n值适当)，则可以取得比较好的效果。但因为缺乏理论指导，这种选择只能依赖先验知识和经验，造成了如神经网络等方法对使用者“技巧”的过分依赖。 统计学习理论提出了一种新的策略，即把函数集构造为一个函数子集序列，使各个子集按照VC维的大小 (亦即。的大小)排列。设函数f(x，w)的集合5具有一定的结构，这一结构是由一系列嵌套的函数子集又一{f(x，w)}w。叽}组成的，它们满足slc=又c?凡.，.，且vC维依次递减，即人‘气‘?‘气 。结构风险最小化实现了在对给定数据逼近的精度和逼近函数的复杂性之间的一种折衷。随着子集序号n的增加，经验风险的最小值减小，但决定置信范围的项却增加。结构风险最小化原则通过选择子集凡，在子集间折衷考虑经验风险和置信范围，使得在所选择的子集中，最小化经验风险会取得实际风险的最好的界，这种思想称作结构风险最小化 (structUral形skMinim咖tion)，即SRM准则。 实现 SRM 原则可以有两种思路，一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至是无穷时甚至根本不可行。此外还有第二种思路，即设计函数集的某种结构使每个子集中都能取得最小的经验风险 (如使训练误差为0)，然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法就是这种思想的具体实现。 注 释: ，cher沁”sky从MulierELearmn g加moat:concePts，仆eo叮andMethods.N丫Jo比 Vi】eySons，1997.2边肇棋，张学工著‘模式识别.第二版.清华大学出版社2。。0:284一304.3v、p愈.Stl刀cn址eofstaisticalle朴 gthe。毕hiA石alnm ennan，editor，co卿u切tionaland Probabalis石cR已滔曲mg.V百ley，Chichester，19%4Vap‘kvlad五n五N著胀学工译，统计学习理论的本质一清华大学出版社.20乡.SBulkejcJ.Atuito五donsup