今天内容模型选择课件.ppt

1、今天内容：模型选择nOccams razorn测试误差/训练误差n训练误差的乐观性估计nMallows Cp 统计量nAICnBIC/MDLnSRMn直接估计测试误差n交叉验证nBootstrap“模型”n我们说的“模型”有时指的是模型类别 ，例如所有2个高斯的混合模型和所有3个高斯的混合模型。n有时也指在一个类别的模型中的一员，如参数 的值为特定值。也就是说，模型的类别是固定的，而考虑的是不同的参数值。n在实际应用中，我们通常同时考虑上述两种情况，也就是说：n参数 的选择统计决策理论部分已经讨论，在此主要讨论不同函数族的选择 F,MFOccams razor William of Occha

2、m(12851348)from wikipediaOccams razor:Entia non sunt multiplicanda praeter necessitatem Or：Entities should not be multiplied unnecessarily the explanation of any phenomenon should make as few assumptions as possible,eliminating,or shaving off,those that make no difference in the observable predictio

3、ns of the explanatory hypothesis or theory.Occams razorn例：树后面有多少个盒子？模型选择n训练数据n既包含输入输出之间的规律n也包含噪声n模型匹配时会匹配上述两种情况n如果模型太复杂，会将噪声也包含在模型中n所以，好的模型n足够对输入输出之间的规律建模n不够对噪声建模（假设噪声较弱）一个回归的例子n 2YX20,1,0,0.3XUniformN样本数n=10用M阶多项式拟合：1Mjjjyw x一个回归的例子（2）0阶多项式拟合一个回归的例子（3）1阶多项式拟合一个回归的例子（4）3阶多项式拟合一个回归的例子（5）9阶多项式拟合一个回归的例

4、子（6）n 过拟合：211inRMSiiEyyn一个回归的例子（7）n 回归系数：一个回归的例子（8）9阶多项式拟合，训练样本数n=15一个回归的例子（9）9阶多项式拟合，训练样本数n=100一个回归的例子（10）岭回归：最小化 22101ppnridgeiijjjijjRSSyX ww一个回归的例子（11）岭回归一个回归的例子（12）岭回归一个回归的例子（13）n岭回归系数目标n模型选择：估计不同模型的性能，选出最好的模型n模型评估：已经选定最终的模型，估计它在新数据上的预测误差（泛化误差）n提升模型的性能：模型平均nBaggingnBoostn教材第8章模型选择和模型评估n当样本足够多时，

5、可以将数据分成三份n训练集：估计模型的参数n校验集：估计模型的预测误差n测试集：计算最终选定的模型的泛化误差n但通常没有足够多样本，而且也很难说明多少足够数据是足够的n依赖于基础数据的信噪比和模型的复杂程度模型选择目标：选择使测试误差最小的模型M，称为模型选择。训练误差与测试误差n测试误差，亦称泛化误差(generalization error)，是在与训练数据同分布的独立测试样本上的风险（平均损失）：n亦称期望风险n训练误差是在训练样本上的平均损失：n亦称经验风险11,ntriiiRML Y Y Mn,R ML Y Y M E训练误差与测试误差n目标是选择测试误差最小的模型n但测试误差很难计

6、算/估计n用训练误差估计n但训练误差是测试误差的欠估计n在选择合适复杂性的模型时，存在偏差-方差的平衡trR MRMop M训练误差的乐观性训练误差与测试误差n经验风险/训练误差是否是期望风险/测试误差的一个好的估计？n随样本集容量n渐进成立n在小样本条件下，并不是一个好的估计n训练误差是测试误差的欠估计（有偏估计）trR MRMop M训练误差的乐观性训练误差的乐观性n通常我们有n因此，为了选择模型，我们可以n对 进行估计，或n以某种方式估计R(M)欠拟合程度+复杂性惩罚 trR MRMop Mop M训练误差的乐观性n估计预测误差的方法n估计乐观性，然后与训练误差 相加nAIC/BIC/M

7、DL等（模型与参数为线性关系时）nSRMn直接估计测试误差 n交叉验证/bootstrapn对任意损失函数、非线性自适应拟合技术都适用trRMR M估计乐观性n通过各种技巧（通常是渐近性）估计乐观性Mallows Cp 统计量n 统计量：22ptrpCMRMn2 MSE噪声方差的估计，通过一个低偏差模型的估计p基的数目n训练样本数目使用所有特征的模型pCMAIC：Akaike Information Criterionn当采用log似然作为损失函数，测试误差为n其中 为MLE，模型为 ，似然函数为n则训练误差为n其中 为在训练集上的log似然。2R Ml M E1loglog|,niiil M

8、L Mf YMX122log|,ntrtriiiRMlMf Y MX 1log|,niiif YMX,M FtrlMi为测试集上数据索引AIC：Akaike Information Criterionn当 时，n其中n这导出R(M)的一个估计：AICn其中 为从一个低偏差（复杂的）估计的MSE获得。n 22trR MlMp 22222trtrnpAIC MlMpRMn 222112ntriiilMyfx（高斯模型时，对数似然与平方误差损失一致）211ntriiiRMyfxn2trnRMBIC：Bayesian Information Criterionn类似AIC，可用于极大化对数似然实现的拟

9、合中n其中n所以 ()2logtrBIC MlMn p 22112ntriiilMyfx2trnRM同AIC22()logtrnpBIC MRMnnBIC:Motivationn用贝叶斯方法选择模型回顾贝叶斯方法n为书写简单，记训练数据为n假设已知模型 的 的形式，参数 的贝叶斯估计为（见参数估计部分）n定义模型参数的先验分布：n和模型似然：n当有数据Z到达后，参数的分布（后验分布）变得更确定F()()()()(|,)|(|,)|,(|)(|,)|ffffffffdqqqqqqqq=ZZZZZMMMMMMMMv11,.,nnX YX YZ()|fqM(|,)fqZM(|)fM|Z(|,)fZM

10、M贝叶斯方法与模型选择n给定一些列侯选模型 ，并且模型参数为n某个给定的模型的后验概率为：n 表示模型的先验n 表示证据（参数估计中的归一化因子）n为了比较两个模型，可以比较后验比：n如果比值 1，则选择第1个模型。111222(|)()(|)(|)()(|)ffffffZZZZMMMMMM()mf M(|)mf Z M,1mmM M(|)()(|)mmmfffZZMMMm贝叶斯方法与模型选择n n其中先验比 n可以根据美学原理或经验确定：如简单的模型先验更高n但先验比不是必须的，即使假设模型的先验是均匀的，即先验比为常数，贝叶斯规则也倾向于选择能解释数据的最简单模型：Occam剃刀原理。nB

11、ayes因子 表示数据Z对后验比值的贡献（证据）n根据证据对模型排序12()()ffMM 12(|)(|)fBFfZZZMM111222(|)()(|)(|)()(|)ffffffZZZZMMMMMM例：Occam剃刀原理n简单模型 只对有限范围内做预测 n复杂模型 （如有更多自由参数）能对更宽范围做预测n但对区域 中的数据，的预测不如 强Z2(|)f Z M1(|)f Z M2M1M2MC11M证据n证据（evidence）n通常会在最可能的参数 附近有一个很强的峰。n以一维参数为例：利用Laplace方法近似，即用被积函数 乘以其宽度(|)(|,)(|)mmmmmmfffdZZMMMm|(

12、|)(|,)(|)mmmmmZbest fit likelihoodOccam factorfffZZMMM (|,)(|)mmmmffZMM|ZOccam因子（参数为多维情况）n n其中1 2 (|)(|,)(|)det2mmmmmbest fit likelihoodOccam factorfffZZAMMM log(|,)mmfAZ M BIC：Bayesian Information Criterionn当模型为线性模型时用Laplace近似 n其中 为极大似然估计，为模型中自由参数的数目n当损失函数取 ，导出贝叶斯信息准则：log(|)log(|,)log12mmmmdffnOZZM

13、M2log(|,)mmf ZMf(|)mf Z Mmmd22()logtrnpBIC MRMnnBICnAIC不是一致的，而BIC是一致的。也就是说，选择最小BIC的模型等价于选择最大后验概率的模型（在渐近意义下）。事实上，模型的后验概率为n不仅可以估计最好的模型，而且可以评估所考虑模型的相关指标。n但：假设候选模型包含正确的模型n“Essentially,all models are wrong,but some are useful”G.Box(1987)12121|mlBICmBICMlefeZM最小描述长度MDLn最小描述长度MDL（minimum description length

14、）采用与BIC完全相同的选择准则，但它源自数据压缩/最优编码nBIC与MDL都只适用于似然损失。Rissanen,J.1978.Modeling by shortest data description.Automatica,14,465-471.MDLn可译变长编码：越频繁的信息码长越短n平均信息长度越短n消息的长度 与事件zi的概率 之间的关系为：n为了传递具有概率密度为 的随机变量zi，需要大约 位n平均信息长度()22,()logil ziiizl zz PP2log()izP 2l(g)oiiilzzz PPE il z熵：消息长度的下界 izP izPMDLn假设我们有以为参数的模

15、型M，和包含输入输出数据Z=(X,y)，则传递输出的消息长度为：n选择最小长度的模型等价于选择最大后验概率的模型，同BIClog(,)log()yMMX 长度PP传递模型参数所需的平均消息长度用于传递模型与目标差别所需要的平均消息长度AIC vs.BICnAIC：n选择使 最小的模型，也是使 最大的模型，其中 为log似然函数，表示模型中有效参数的数目n极大似然，同时模型复杂度极小nBIC:n用贝叶斯方法选择模型n选择最大后验概率的模型22222trtrnpAIC MlMpRMn l Md Ml M22l Md Md Mp n22()2loglogtrtrnpBIC MlMn pRMnn AI

16、C vs.BICn均使用模型参数数目来度量复杂度n对复杂度的惩罚参数的选择不同nBIC：渐近相容n样本容量n时，选择正确模型的概率1n有限样本情况下，当取高斯噪声时，n ，BIC中因子2被logn代替，对复杂性施加更严厉的惩罚，倾向于选择简单模型，AIC倾向于选择复杂模型22()logtrnpBIC MRMnn222trnpAIC MRMnBIC MAIC M有效参数数目nAIC/BIC中参数的数目可以扩展到使用正则化拟合的模型n对线性拟合n其中 为 的矩阵，只依赖于输入向量 ，与 无关n则有效参数的数目为n如对岭回归n则有效参数数目为 ySySnnixiy dtraceSS 2121pjTT

17、jjddftracedX X XIX1ridgeTTyXX X XIX yVC维(Vapnik-Chernovenkis Dimension)n之前的乐观性估计都适用于简单模型和基于似然函数的。VC理论给出了模型复杂性更一般的度量n函数类 的VC维n可被函数集成员打散（shatter）的点的最大数目n打散n不管怎样改变每个点的位置和标记，某个类别的函数中的一员都能完全分开这些点，则称为这些点能被该类别的函数打散。:0,1DFRVC维2D线性函数的VC维为3，等于参数的个数正弦函数的VC维：无穷，但参数只有一个：频率sin()xVC维n如线性函数能打散2D平面上任意3点，因此线性函数的VC维是3

18、。通常D维线性函数的VC维是D+1，也就是自由参数的数目。n一个非线性的函数族的VC维可能无穷大，因为通过选择合适的参数，任何点的集合都能被该类的函数打散。n实值函数类 的VC维定义指示函数类 的VC维，其中在 f 的值域上取值。:DFRR:0IfxFVC维n函数集的VC维不一定等于自由参数的个数n可为等于、大于或小于n尚无一般方法对任意函数集计算VC维，只有一些函数集合的VC维可计算n线性函数n多项式n三角函数等VC维与风险的界n对两类分类问题，假设函数类的VC维为h，则对该函数类中的每个模型，至少有 的概率满足n其中n对回归问题n对回归问题，建议 n对分类问题，没有建议，但 对应最坏的情况

19、trtr4112RMR MRM21log1log(4)hc n hcntr31RMR Mc1231ccc124,2cc1VC维与风险的界n n如果h有限的话，模型族的复杂性可以随n增加而增加 n当h 较小时，R(M)和 Rtr 之间的差异小n所以正则化回归（如岭回归）比一般最小二乘的推广型更好trtr4112RMR MRM21log1log(4)hc n hcnVC维与风险的界n n称为置信范围，随n增大而减小，随h增加而增加，与AIC中的项 d/n一致n训练误差有时亦称经验风险，测试误差亦称期望风险n对于特定的问题，样本数目n一般是固定的，VC维越大，测试误差与训练误差之间的差就越大。因此我

20、们在选择模型时，不但要使训练误差最小化，还要使模型的复杂性也即VC维尽量小，从而使测试误差最小。trR MRMh n结构风险最小化原则(Structural Risk Minimization,SRM)n这个上界是对函数类中的全部成员（参数不同）给出可能的上界，而AIC描述的是类中某个特定成员(MLE)的乐观性估计。n结构风险最小化原则选择具有最小上界的函数类别。n注意：VC理论并没有给出测试误差的真正估计，只是测试误差的上界，所给出的界往往是松的结构风险最小化n设计模型的目标：n同时最小化经验风险和置信范围n如何同时最小化结构风险最小化原则n把函数集S分解为一个函数子集序列（子集结构）：S1

21、 S2 Sk S，使得各子集能够按照VC维的大小排列：h1 h2 hk，n同一个子集中的置信范围就相同结构风险最小化n根据函数类的性质，将它划分为一系列嵌套的子集n如多项式的阶数增加；岭回归的减小；神经元网络的隐含节点数据增加n学习问题：n选择一个适当的函数子集（根据推广性）n并在该子集中选择最好的函数（根据经验风险）两种构造性方法n一种方法：找到合适的模型类别，然后再这个类别的模型中找到使训练误差最小的函数，即保持置信范围固定（通过选择合适的模型类别）并最小化经验风险n如人工神经网络n先确定网络的结构，然后再学习网络的系数n另一种方法：保持经验风险固定（如为0），最小化置信范围n如SVM直接

22、估计测试误差n重采样技术：直接估计测试误差R(M)n交叉验证nbootstrap交叉验证n最简单、最常用的估计预测误差的方法n思想：直接估计样本外误差 n 应用到来自X与Y的联合分布的独立的测试集n在 -折交叉验证中，数据被分成大致相等的 份。对第 份，用其余 份数据用于拟合模型，并在第 份数据上计算拟合好的模型的预测误差(,()R ME L Yf X)(XfKk1KkKK-折交叉验证n数据被分成大致相等的K份n第k=1,K份数据作为校验集，其余K-1份数据用于训练模型，并在第k份数据上计算训练好的模型的预测误差n例5-折交叉验证第1折：第2折：第3折：第4折：第5折：交叉验证n交叉验证对预测

23、误差的估计为n其中 为去掉第k份数据后训练的模型。n 对测试误差提供了一个估计，通过最小化 确定调整参数：n最后被选中的模型为用所有数据拟合的模型()11()(,(,).nk iiiiCVL yfxn),(xf)(CV)(CVargmin()CV()(,)k iifx学习曲线由于训练集减小，会引起偏差交叉验证：K的值?n如果 称为留一交叉验证(leave-one-out cross-validation，LOOCV)。这是近似无偏的，但由于n个训练集彼此之间很相似，可能会有较高的方差。并且计算代价也很高（计算n次）。n另一方面，当 CV为低方差但偏差较大。n在给定训练集合大小时，如果学习曲线比

24、较陡，则5-折、10-折CV会对真正的预测误差过估计。n通常取K=10,Kn,5KBootstrapnBootstrap是一个很通用的工具，用来估计测试误差和置信区间n参见第二部分：统计推断n用来估计预测误差：从训练集n中进行bootstrap采样，得到bootstrap样本,1,.,iiZx yin*,1,.,1,.,biiZxyinbBBootstrap测试误差估计nbootstrap来估计检测误差：n但同时从训练集和校验集中采样，当二者有重叠时，就引入了偏差。一种方法是leave-one-out bootstrap:n其中 为不包含观测i的样本b的索引的集合。这解决了过拟合问题，但样本的

25、减少带来了类似CV中的偏差问题。n为了处理样本偏少的问题，采用“.632”估计子：*111,.|inloobootibiiib CRL yfxnC*111 1,.BnbootibibiRL yfxB niC.6320.3680.632.trloobootRRRBootstrap测试误差估计n“.632”估计子在“轻拟合”时表现很好，但在过拟合时会有问题，因此又引入“.632+”估计子：n 无信息误差率 ：如果输入和类别标号是独立的，则 为预测规则的误差率n 过拟合率：n“.632+”估计子：.6320.6321,10.368trloobootRw RwRwR2111,nniiiiL yfxnl

26、ooboottrtrRRRRCase study：前列腺癌数据 n考虑模型族：岭回归n模型复杂度参数：n有效参数数目：n采用下述技术做模型选择nAICnBICnCVnBootstrap1TTySyX X XIX y 2121pjTTjjddftracedX X XIXAIC22trpAIC MRMnBIC2logtrpBIC MRMnnSRMtrlog1log(4),1hn hRMR Mn10-折交叉验证n最佳模型为：*41.7532,4.0366dfBootstrapn0.632：Bootstrapn0.632+：最小测试误差到底应该选择哪个模型？n模型越简单，越不用做工作。更复杂的模型需要

27、更正确的模型选择，采用重采样技术n线性回归：AIC/BICn非参数：采用交叉验证和bootstrapn通常更准确需要更多计算总结：模型选择n模型：n模型的类别n每个类别的模型的参数n模型选择n选择测试误差最小的模型n假设测试数据与训练数据的某种一致性（如IID）n模型必须与数据有一定的拟合精度n但模型过复杂时，数据拟合程度很好，但会出现过拟合，测试误差也会很大n模型选择是在数据拟合精度与模型复杂性之间的折中,MF下节课内容n模型组合 更高的性能？nBaggingnBoostingn附：AIC推导0Yf kYfkFkk()()()12,pFFkFkFk=K()12,kpfYkkkkqK0Yf0Y

28、f0Yf()*f Yq附：AIC推导nKL损失/log似然损失：表示函数f与g之间的距离，其中g为真正的分布，为当前模型 ,log|g yL g fg y dyfyf loglog|g yg y dxfyg y dy loglog|YYg yfyEEEE对 而言是常数C|fx2log|Yfy E E熵定义为：logH Yg yg y dy KL散度也表示用f去近似g，信息的损失量n模型选择：给定f，和数据 ，选择损失最小的模型参数作为参数估计，即参数 的估计为其MLEn所以损失函数为：n模型选择的目标是选择风险（损失的期望）最小的模型n风险为期望KL损失：n等价于最大化期望log似然,2log

29、|nYL g ffxY E EnY极大似然等价于最小KL散度，参见MLE的性质部分,2log|nnnYYYL g ffyY EEEEEElog|nnYYfyYEEEElog似然1,nnYYYn n其中 为当样本数 时的MLE（最小化KL损失的参数的值）log|nnYYfyYEEEE 1*log|YfyYtr JIE E2*log|,1,YijfyIi jp E E*log|log|TYfyfyJE E*n ，为Fisher信息n当 时，n其中p为参数的维数（特征的维数）n如果f为一个较好的模型（在g附近），则fg 11*JIJItr JIpI 1*tr JIpn n所以最小风险的模型n等价于n 其中第一项的估计为n所以AIC为：min2log|nnYYfyYEEEE min2log|2yfyypE E log|2log|2nnYYYfyYfyYp EEEEEE 1log|log|nYiifyYfyYE E 2212log|22nitrinpAIC MfyYpRMn 1,.nYYY