统计学习理论简介 28页

第八章统计学习理论简介IntroductionofStatisticalLearningTheory\n§1机器学习问题和方法§2学习过程的一致性条件§3函数集的学习性能与VC维§4推广性的界§5结构风险最小化－支持向量机\n客观世界中存在着无法准确认识，但可进行观测的事物。“统计”是面对数据而又缺乏理论模型时最有效的、也是唯一的分析手段。传统的统计学所研究的是渐进理论，是在样本数目趋于无穷大时,其性能才有理论上的保证。上世纪90年代中才成熟的统计学习理论，是在基于经验风险的有关研究基础上发展起来的，专门针对小样本的统计理论。统计学习理论为研究有限样本情况下的模式识别、函数拟合和概率密度估计等三种类型的机器学习问题提供了理论框架，同时也为模式识别发展了一种新的分类方法——支持向量机。\n§1机器学习问题和方法1.机器学习问题机器学习是现代智能技术中重要的一个方面，研究从观测样本出发去分析对象，去预测未来。机器学习的基本模型：G从F(x)中抽取的x；S是研究对象；LM是所求的学习机。系统(S)学习机{f(x,w)}(LM）输入x输出y预测输出产生器(G)输出y与x之间存在一种固定的、但形式未知的联合概率分布函数F(y,x)。学习机中有函数集{f(x,w)}，可估计输入与输出之间依赖关系，其中w为广义参数。\n2.风险最小化－机器学习问题表示已知变量y与输入x之间存在一定的未知依赖关系，即联合概率分布F(x,y)。(作为一种特例，若x和y之间有确定性关系，即系统辨识)。机器学习就是根据独立同分布的n个观测样本：(x1,y1),(x2,y2),···,(xn,yn)在一组函数{f(x,w)}中求一个最优函数f(x,w0)，使预测的期望风险R(w)最小化。L(y,{f(x,w)})为损失函数，由于对y进行预测而造成的损失；w为函数的广义参数，故{f(x,w)}可表示任何函数集；F(x,y)为联合分布函数。\n三类机器学习问题的损失函数⑴模式识别：输出y就是类别。两类输出y={0,1},这时预测函数称为指示函数。损失函数定义：⑵函数拟合：y(连续变量)是x的函数，损失函数⑶概率密度估计：估计的概密为p(x,w)，损失函数要使期望风险R(w)最小化，依赖概率分布F(x,y)。但在机器学习中，只有样本信息，无法直接计算期望风险及其最小化。\n3.经验风险最小化(EmpiricRiskMinimization，ERM)根据概率论中的大数定理，用算术平均代替数学期望，定义了经验风险来逼近定义的期望风险。用训练样本(xi,yi,i=1~n)(即经验数据)定义,故称为经验风险。求经验风险Remp(w)的最小值代替求期望风险R(w)的最小值，就是所谓的ERM原则。模式识别中前面各章的分类器设计(除SVM)；函数拟合中的最小二乘法；概率密度估计中的极大似然法都是在ERM原则下得到的。\n从期望风险最小化到经验风险最小化并没有可靠的理论依据。Remp(w)和R(w)都是w的函数，概率论中的大数定理只说明样本无限多时Remp(w)在概率意义上趋近于R(w)，并不说二者的w最小点为同一个点。而且客观上样本是有限的。有限样本情况下学习精度和推广性之间往往有矛盾，采用复杂的学习机器可使误差更小，但推广性差。统计学习理论对使用经验风险最小化原则的前提，对解决机器学习问题中的期望风险最小化理论依据进行了研究。\n§2学习过程的一致性条件一致性(consistency)是指当样本趋于无穷时，Remp(w)的最优值收敛到R(w)的最优值。1.学习过程的一致性最优预测函数f(x,w*)→最小的L(y,f(x,w*|n))→最小值Remp(w*|n)。R(w*|n)为在L(y,f(x,w*|n))下的真实(期望)风险值。如果下面两式成立时称这个学习过程是一致的：\n换句话讲，如果经验风险最小化方法能提供一个函数序列{f(x,w)}，使得Remp(w)和R(w)都收敛于最小可能的风险值R(w0)，则这个经验风险最小化学习过程是一致的。这两个条件说明①式保证了所达到的风险收敛于最好的可能值。②式保证了可以在经验风险的取值基础上估计最小可能的实际风险。存在一种可能，预测函数集中有某个特殊的函数满足上述条件。为此定义了非平凡一致性概念，即预测函数集中的所有子集都满足条件。\n2.学习理论关键定理：经验风险最小化一致性的充分和必要条件是经验风险在函数集上，如下式收敛于期望风险其中P概率。这样把一致性问题转化为一致收敛问题。它有赖于预测函数集和样本概率分布。Remp(w)和R(w)都是预测函数的函数(泛函)。目的是通过求经验风险最小化的预测函数来逼近能使期望风险最小化的函数。关键定理没有给出学习方法，即预测函数集是否能满足一致性的条件。为此定义了一些指标来衡量函数集的性能，最重要的是VC维。\n§3函数集的学习性能与VC维1.指示函数集的熵和生长函数⑴指示函数集的熵有n个训练样本Zn={zi(xi,yi)，i=1,2,···,n}。定义N(Zn)为函数集中的函数能对样本分类的数目。随机熵：定义指示函数集能实现分类组合数的自然对数，称为函数集在样本上的随机熵H(Zn)=lnN(Zn)指示函数集的熵：n个样本的随机熵的期望值H(n)=E(lnN(Zn))也称VC熵，作为衡量函数集分类能力的指标，是函数集的一个特性。\n⑵生长函数(growthfunction)G(n)函数集的生长函数G(n)定义为最大随机熵G(n)反映了函数集把n个样本分成两类的最大可能的分法数。二分法的最大数为2n。G(n)≤nln2。如果G(n)＝2n成立，就称为具有n个样本的集合被指示函数打散(shattered)了。退火的VC熵，定义VC熵、退火的VC熵与生长函数三者之间的关系\n2.生长函数的性质与VC维(VapnikChervonenkisdimension)由VC维的创立者在1968年发现了下面的规律：函数集的生长函数或者与样本数成正比，即①G(n)=nln2,或者以样本数的某个对数函数为上界,即VC维对于一个指示函数集，表示函数能打散的最大样本数。若其生长函数是线性的，VC维为无穷大；若以h的对数函数为上界，则VC维等于h。\n线性分类器一章中已述d维空间中的N个样本，线性可分的数目为当n=d+1时，此两式结果相同。若d=2：n=3，D=8种线性二分的情况；n=4,D=16，其中14种是线性可分的；n=5,D=32，其中22种是线性可分的。随着样本数目增多，可能的二分法总数增加。但并不是线性关系，而是如图实线所示。也就是生长函数G(n)的性质。当n>d+1\nVC维的直观定义：假设存在一个有h个样本的样本集能被一个函数集中的函数按照所有可能的2h种形式分为两类,则此函数集能够把样本数为h的样本集打散。也就是说，如果存在h个样本的样本集能够被函数集打散，而不存在有h+1个样本能被打散，则函数集的VC维就是h。指示函数集的VC维就是用这个函数集中的函数能够打散的最大的样本数目表示。学习过程一致的充要条件是函数集的VC维有限。VC维h＝d+1=2+1=3指示函数为线性函数\n根据VC维的定义，d维空间中的线性分类器中①二值符号函数的VC维是h=d+1；②实值线性函数的VC维也是h=d+1。VC维反映了函数集的学习能力。VC维越大，则学习机器越复杂。目前，对一些特殊的函数集的VC维可准确知道，而对一些复杂的学习机器(如神经网络)，其VC维除了与函数集的选择有关外，还受算法的影响，确定困难。\n1.推广性统计学习理论指出：经验风险最小化原则下的学习机器的实际风险由两部分组成：①训练样本的经验风险Remp(w)；②称为置信范围F(h/n)，不但受置信水平1-h影响，而且是函数集的VC维h和样本数n的函数。为此重写为上式强调随着n/h的增加，F(n/h)单调减少。§4推广性的界\n经验风险与期望风险之间差距的上界F(n/h)，反映了根据经验风险最小化原则得到的学习机器的推广能力，称为推广性的界。当n/h较小时(如小于20，h固定，样本数n少)，置信范围(或称为VC信任)F较大，用经验风险近似真实风险的误差大，用经验风险最小化取得的最优解推广性差。另一方面样本数n固定，若VC维越高(复杂性越高)，则置信范围越大，误差越大。注意：函数的VC维是指示函数的性质，用样本数数目来表示，不是需要训练样本的数量。为了推广性，训练样本的数量n要多得多。\n2.复杂性VC维越高置信范围越大，复杂性高，误差大。因此在设计分类器时，要使VC维尽量小，就是不用过于复杂的分类器或神经网络。选择模型的过程就是优化置信范围的过程。例如选了线性分类器，就确定了学习机器的VC维。虽然很多问题不是线性的，但当样本数有限时往往用线性分类器(VC维低)可得到好的结果。同样，在神经网络中首先根据问题和样本选择不同神经网络的结构(隐层数对应于VC维)，再进行经验风险最小化。\n有时训练误差过小反而导致推广能力下降，这就是神经网络中的“过学习”问题。这是因为学习样本少，或学习机器设计不合理。也就是说，采用复杂的学习机器容易使学习误差更小，但丧失推广性。因此有限样本情况下，①经验风险最小并不一定意味期望风险最小，可通过函数最小化使经验风险收敛于期望风险。函数的重要性质就是VC维。②学习机器的复杂性不但与系统有关，而且与有限的样本有关。即存在学习精度和推广性之间存在矛盾。因此在模式识别中，为了推广性人们趋于用线性或分段线性等较简单的分类器。\n§5结构风险最小化StructureRiskMinimization,SRM1.结构风险最小化其理论依据也是把函数集S={f(x,w),w∈Ω}分解为一个函数子集序列：各子集按VC维的大小排列h1≤h2≤···≤hk≤···这样在同一个子集中置信范围相同。再在每一个子集中寻找最小经验风险Remp，通常它随函数集复杂度的增加而减少。\n选择经验风险与置信范围之和最小的子集，就达到期望风险最小。在这个子集中使经验风险最小的函数就是所求的最优函数。这就称为结构风险最小化原则。在SRM原则下设计分类器步骤：第一步模型选择，选择一个适当的函数子集，使之对问题有最优的分类能力，即确定了F(n/h)；第二步从子集中选择一个判别函数，再进行参数估计，使经验风险最小，得到最优函数。这也称为有序风险最小化原则。\n2.支持向量机SVR－实现了有序风险最小化思想⑴SVM的最优分类线不但能将两类分开，使经验风险最小(为0)；而且要使两类的分类空隙最大实际上就是推广性的界中的置信范围最小。样本集为\n⑵SVM的推广性非线性支持向量机是在比原特征空间维数高的空间进行分类。若变换的维数过高，在此空间的线性判别函数的VC维(h=d+1)可能会很大。最优和广义最优分类面的推广能力的定理：如果一组训练样本能被一个最优分类面分开，则对测试样本分类错误率的期望上界是训练样本中平均的支持向量数占总训练样本数的比例，即因此推广性与维数无关，只要选择一种内积定义，构造支持向量数相对少的最优分类面。\n⑶SVM的主要优点：①针对有限样本的，其目标是得到现有信息下的最优解。②算法最终转化为一个二次优化(对偶)问题。理论上可得到全局最优解。③算法通过非线性变换到高维特征空间，在此空间构建核函数实现原空间的非线性判别函数，使学习机器有较好的推广能力；同时解决了维数问题，其算法复杂度与维数无关。在SVM方法中，只要定义不同的内积函数就可实现多项式逼近、Bayes分类器、RBF方法、MLP等现有的学习算法。\n⑷经典的SVM算法为两类分类算法，在多类问题中解决方法：①构造多个两类SVM的组合，主要有一对多组合模式、一对一组合模式和SVM决策树。②构造多个分类器组合。SVM的主要思想是通过选择的线性与非线性映射将输入向量映射到高维特征空间中，利用优化理论构造最优决策函数，并利用核函数代替高维空间的点积运算，从而避免了复杂的计算。\n作业：1.请你用自己的语言总结指示函数、生长函数G、VC维h、训练样本数n，它们之间的区别与联系，以及与经验风险最小和期望风险最小的联系。2.什么是结构风险最小化？与VC维的关系，结合推广性进行分析。