06-统计学习理论.pdf
1第六章 统计学习理论?6.0 引言?6.1 一致性与一致收敛?6.2 Vapnik-Chervonenkis(VC)理论?6.3 结构风险最小化(Structural Risk Minimization)6.0 引言6.0 引言?过拟合问题与Ockhams razor:?Williams of Ockham/Occam(1285-1347?);?Ockhams razor:“entities should not be multiplied beyond necessity”.6.0 引言?模式识别中的学习问题：?训练数据集(X,Y),(,),(),(2211nnyxyxyxL,dix,2,1KyiL随机变量的独立同分布样本。的类别标识，Xix随机变量的独立同分布样本。Y6.0 引言?学习函数集：?损失函数：:),(xf参数参数空间).,(,(xfyL6.0 引言?例：最小平方误差线性分类器。?训练数据：?学习函数集：?损失函数：.,=ddbwbw.1,1+iy.),(bxwxfT+=.)(),(),(,(22bxwyxfyxfyLT=,dix26.0 引言?学习：从学习函数集中挑一个“最优”的。?什么是“最优最优”？?统计推断：期望风险最小化(RM)?期望风险=),(),(,(),()(yxdFxfyLfRRYX,的分布函数。6.0 引言?经验过程：经验风险最小化(ERM)?经验风险.),(,(1),()(1=niiiempempxfyLnfRR6.0 引言?基于最小错误率的Bayes决策).|()()|()()|(),()(xePExdPxePdxxpxePdxxePeP=6.0 引言?在解决一个给定的问题时，要尽量避免把解决一个更为一般的问题作为中间步骤。6.0 引言?经验过程的例子：?最小平方误差：?最小错误：.),(1)(12=niiiempxfynR.),(1)(1=niiiempxfynR6.0 引言?关于经验风险最小化(Empirical Risk Minimization)的问题：?一致性(consistency)；?泛化能力(generalization ability)收敛速度；?泛化能力的控制：结构风险最小化。36.1 一致性与一致收敛6.1一致性与一致收敛?渐进性质一致性：?ERM估计与RM估计：.),(,(1minarg)(minarg)(1=niiiempRxfyLnRnemp.),(),(,(minarg)(minarg=yxdFxfyLRR6.1一致性与一致收敛?一致性；?解收敛：?风险值收敛：.0)()(nRRRnRemp.0)()(nRRempRnRempPP6.1一致性与一致收敛?非平凡一致性：（后简称一致性）?对函数集定义子集?如果对任意非空都有,),(),(,(:),()(=cyxdFxfyLxfc:),(xf),(),(cc)(inf)(inf)()(RRcnempc 6.1 一致性与一致收敛?一致性的充要条件一致一致收敛。?一致收敛：?Key Theorem(theorem about equivalence):ERM原则一致性的充分必要条件是一致收敛。0)()(supPrnempRR06.1 一致性与一致收敛?经验风险和期望风险n经验风险期望风险46.1 一致性与一致收敛?经验风险和期望风险都是学习函数集的函数（泛函）。?学习的目的：通过求使经验风险最小化的学习函数来逼近使期望风险最小化的函数。?注意：ERM原则一致性的充分必要条件取决于学习函数集中最差函数的性能。6.1 一致性与一致收敛?损失函数为示性函数的分析：?例：),sgn(),(bxwxfT+=).,(1).,(0),(,(xfyxfyxfyL令.2,1,),(nizZyxzi=记).,(,(),(xfyLzQ=6.1 一致性与一致收敛?随机熵：函数集对样本集所有不同分类数目定义为：),(21nzzzNL.2),(21nnzzzNL必有：),(ln)()(21nzzzNEZHEnHL=?示性函数集的熵:),(ln)(21nzzzNZHL=)(ZH6.1 一致性与一致收敛?一致收敛的充要条件：.0)(lim=nnHn6.1 一致性与一致收敛?完全不可证伪性?部分不可证伪性2ln)(lim=nnHn.0)(lim=CnnHn6.2 VC理论56.2 VC理论?函数集的熵与分布函数有关：?与分布无关的熵：生长函数(Growth function).).(),(ln),(ln)(2121zdFzzzNzzzNEnHnnLL=).,(supln()(21,21nzzzzzzNnGnLL=依赖具体问题。普遍适用。6.2 VC理论?函数集的熵与生长函数的关系：?与分布函数无关的一致收敛：).()(nGnH.0)(lim=nnGn6.2 VC理论?Growth function的结构：+=hnhnhhnnnG)ln1(2ln)(nh)(nG2lnn)1(ln+hnhh:VC维6.2 VC理论?VC维：?定义：最大的正整数，使得存在，可以被任意地分成两类。.2),(21hhzzzN=Lhhzzz,21L),(zL.2),(1121+6.2 VC理论?ERM原则是针对大样本数问题的。当较小时，实际风险接近经验风险的取值。但是，当较大时，小的经验风险并不能保证小的实际风险。这是ERM原则的缺点，也是过学习问题所在。nh/nh/6.3 结构风险最小化6.3 结构风险最小化?对风险上界最小化：?同时考虑经验风险和VC维(trade off)；?结构化的学习函数集：.1)()(nnRnRempempRempR+经验风险VC维.21LLk.:),(iixfS=.21LLkSSS.UiiSS=6.3 结构风险最小化?例：多项式。:nSn阶多项式。.21LLkSSS86.3 结构风险最小化风险上界经验风险S1SnS*h*h1hnhSn的VC维“最优”学习函数集。SRM是一致相合的。6.3 结构风险最小化?SRM原则给出了在给定数据逼近的精度和逼近函数的复杂性之间的一种折中。习题习题?1.证明：维空间被个超平面分割，最多能分出的区域个数为：?提示：用两次归纳法，分别对维数和超平面的个数做归纳。hhn=hiinChnN1),(?参考文献参考文献1 Vladimir N.Vapnik,Statistical Learning Theory,John Wiley&Sons,Inc.1998.2 Vladimir N.Vapnik,The Nature of Statistical Learning,Springer-Verlag,New York,NY,1995(中译本统计学习理论的本质，张学工译，清华大学出版社，2000年9月)3 Vladimir N.Vapnik,An overview of Statistical Learning Theory,IEEE Trans.Neural Networks,10(5),988-999,1999.
