第八章统计学习理论简介IntroductionofStatisticalLearningTheory§1机器学习问题和方法§2学习过程的一致性条件§3函数集的学习性能与VC维§4推广性的界§5结构风险最小化－支持向量机客观世界中存在着无法准确认识，但可进行观测的事物。“统计”是面对数据而又缺乏理论模型时最有效的、也是唯一的分析手段。传统的统计学所研究的是渐进理论，是在样本数目趋于无穷大时,其性能才有理论上的保证。上世纪90年代中才成熟的统计学习理论，是在基于经验风险的有关研究基础上发展起来的，专门针对小样本的统计理论。统计学习理论为研究有限样本情况下的模式识别、函数拟合和概率密度估计等三种类型的机器学习问题提供了理论框架，同时也为模式识别发展了一种新的分类方法——支持向量机。§1机器学习问题和方法2.风险最小化－机器学习问题表示已知变量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)为联合分布函数。三类机器学习问题的损失函数⑴模式识别：输出y就是类别。两类输出y={0,1},这时预测函数称为指示函数。损失函数定义：⑵函数拟合：y(连续变量)是x的函数，损失函数⑶概率密度估计：估计的概密为p(x,w)，损失函数3.经验风险最小化(EmpiricRiskMinimization，ERM)从期望风险最小化到经验风险最小化并没有可靠的理论依据。Remp(w)和R(w)都是w的函数，概率论中的大数定理只说明样本无限多时Remp(w)在概率意义上趋近于R(w)，并不说二者的w最小点为同一个点。而且客观上样本是有限的。有限样本情况下学习精度和推广性之间往往有矛盾，采用复杂的学习机器可使误差更小，但推广性差。统计学习理论对使用经验风险最小化原则的前提，对解决机器学习问题中的期望风险最小化理论依据进行了研究。§2学习过程的一致性条件换句话讲，如果经验风险最小化方法能提供一个函数序列{f(x,w)}，使得Remp(w)和R(w)都收敛于最小可能的风险值R(w0)，则这个经验风险最小化学习过程是一致的。这两个条件说明①式保证了所达到的风险收敛于最好的可能值。②式保证了可以在经验风险的取值基础上估计最小可能的实际风险。存在一种可能，预测函数集中有某个特殊的函数满足上述条件。为此定义了非平凡一致性概念，即预测函数集中的所有子集都满足条件。2.学习理论关键定理：经验风险最小化一致性的充分和必要条件是经验风险在函数集上，如下式收敛于期望风险其中P概率。这样把一致性问题转化为一致收敛问题。它有赖于预测函数集和样本概率分布。Remp(w)和R(w)都是预测函数的函数(泛函)。目的是通过求经验风险最小化的预测函数来逼近能使期望风险最小化的函数。关键定理没有给出学习方法，即预测函数集是否能满足一致性的条件。为此定义了一些指标来衡量函数集的性能，最重要的是VC维。§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熵，作为衡量函数集分类能力的指标，是函数集的一个特性。⑵生长函数(growthfunction)G(n)函数集的生长函数G(n)定义为最大随机熵G(n)反映了函数集把n个样本分成两类的最大可能的分法数。二分法的最大数为2n。G(n)≤nln2。如果G(n)＝2n成立，就称为具有n个样本的集合被指示函数打散(shattered)了。退火的VC熵，定义VC熵、退火的VC熵与生长函数三者之间的关系2.生长函数的性质与VC维(VapnikChervonenkisdimension)由VC维的创立者在1968年发现了下面的规律：函数集的生长函数或者与样本数成正比，即①G(n)=nln2,或者以样本数的某个对数函数为上界,即VC维对于一个指示函数集，表示函数能打散的最大样本数。若其生长函数是线性的，VC维为无穷大；若以h的对数函数为上界，则VC维等于