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

今天内容：模型选择,Occams razor测试误差/训练误差训练误差的乐观性估计Mallows Cp 统计量AICBIC/MDLSRM直接估计测试误差交叉验证Bootstrap,“模型”,我们说的“模型”有时指的是模型类别，例如所有2个高斯的混合模型和所有3个高斯的混合模型。有时也指在一个类别的模型中的一员，如参数 的值为特定值。也就是说，模型的类别是固定的，而考虑的是不同的参数值。在实际应用中，我们通常同时考虑上述两种情况，也就是说：参数 的选择统计决策理论部分已经讨论，在此主要讨论不同函数族的选择,Occams razor,William of Occham(12851348),from wikipedia,Occams 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 predictions of the explanatory hypothesis or theory.,Occams razor,例：树后面有多少个盒子？,模型选择,训练数据既包含输入输出之间的规律也包含噪声模型匹配时会匹配上述两种情况如果模型太复杂，会将噪声也包含在模型中所以，好的模型足够对输入输出之间的规律建模不够对噪声建模（假设噪声较弱）,一个回归的例子,样本数n=10用M阶多项式拟合：,一个回归的例子（2）,0阶多项式拟合,一个回归的例子（3）,1阶多项式拟合,一个回归的例子（4）,3阶多项式拟合,一个回归的例子（5）,9阶多项式拟合,一个回归的例子（6）,过拟合：,一个回归的例子（7）,回归系数：,一个回归的例子（8）,9阶多项式拟合，训练样本数n=15,一个回归的例子（9）,9阶多项式拟合，训练样本数n=100,一个回归的例子（10）,岭回归：最小化,一个回归的例子（11）,岭回归,一个回归的例子（12）,岭回归,一个回归的例子（13）,岭回归系数,目标,模型选择：估计不同模型的性能，选出最好的模型模型评估：已经选定最终的模型，估计它在新数据上的预测误差（泛化误差）提升模型的性能：模型平均BaggingBoost,教材第8章,模型选择和模型评估,当样本足够多时，可以将数据分成三份训练集：估计模型的参数校验集：估计模型的预测误差测试集：计算最终选定的模型的泛化误差但通常没有足够多样本，而且也很难说明多少足够数据是足够的依赖于基础数据的信噪比和模型的复杂程度,模型选择,目标：选择使测试误差最小的模型M，称为模型选择。,训练误差与测试误差,测试误差，亦称泛化误差(generalization error)，是在与训练数据同分布的独立测试样本上的风险（平均损失）：亦称期望风险训练误差是在训练样本上的平均损失：亦称经验风险,训练误差与测试误差,目标是选择测试误差最小的模型但测试误差很难计算/估计用训练误差估计但训练误差是测试误差的欠估计在选择合适复杂性的模型时，存在偏差-方差的平衡,训练误差的乐观性,训练误差与测试误差,经验风险/训练误差是否是期望风险/测试误差的一个好的估计？随样本集容量n渐进成立在小样本条件下，并不是一个好的估计训练误差是测试误差的欠估计（有偏估计）,训练误差的乐观性,训练误差的乐观性,通常我们有因此，为了选择模型，我们可以对 进行估计，或以某种方式估计R(M),欠拟合程度+复杂性惩罚,训练误差的乐观性,估计预测误差的方法估计乐观性，然后与训练误差 相加AIC/BIC/MDL等（模型与参数为线性关系时）SRM直接估计测试误差 交叉验证/bootstrap对任意损失函数、非线性自适应拟合技术都适用,估计乐观性,通过各种技巧（通常是渐近性）估计乐观性,Mallows Cp 统计量,统计量：,使用所有特征的模型,AIC：Akaike Information Criterion,当采用log似然作为损失函数，测试误差为其中 为MLE，模型为，似然函数为则训练误差为其中 为在训练集上的log似然。,i为测试集上数据索引,AIC：Akaike Information Criterion,当 时，其中这导出R(M)的一个估计：AIC其中 为从一个低偏差（复杂的）估计的MSE获得。,（高斯模型时，对数似然与平方误差损失一致）,BIC：Bayesian Information Criterion,类似AIC，可用于极大化对数似然实现的拟合中其中所以,同AIC,BIC:Motivation,用贝叶斯方法选择模型,回顾贝叶斯方法,为书写简单，记训练数据为假设已知模型 的 的形式，参数 的贝叶斯估计为（见参数估计部分）定义模型参数的先验分布：和模型似然：当有数据Z到达后，参数的分布（后验分布）变得更确定,贝叶斯方法与模型选择,给定一些列侯选模型，并且模型参数为某个给定的模型的后验概率为：表示模型的先验 表示证据（参数估计中的归一化因子）为了比较两个模型，可以比较后验比：如果比值 1，则选择第1个模型。,贝叶斯方法与模型选择,其中先验比 可以根据美学原理或经验确定：如简单的模型先验更高但先验比不是必须的，即使假设模型的先验是均匀的，即先验比为常数，贝叶斯规则也倾向于选择能解释数据的最简单模型：Occam剃刀原理。Bayes因子 表示数据Z对后验比值的贡献（证据）根据证据对模型排序,例：Occam剃刀原理,简单模型 只对有限范围内做预测 复杂模型（如有更多自由参数）能对更宽范围做预测但对区域 中的数据，的预测不如 强,证据,证据（evidence）通常会在最可能的参数 附近有一个很强的峰。以一维参数为例：利用Laplace方法近似，即用被积函数 乘以其宽度,Occam因子（参数为多维情况）,其中,BIC：Bayesian Information Criterion,当模型为线性模型时用Laplace近似 其中 为极大似然估计，为模型中自由参数的数目当损失函数取，导出贝叶斯信息准则：,BIC,AIC不是一致的，而BIC是一致的。也就是说，选择最小BIC的模型等价于选择最大后验概率的模型（在渐近意义下）。事实上，模型的后验概率为不仅可以估计最好的模型，而且可以评估所考虑模型的相关指标。但：假设候选模型包含正确的模型“Essentially,all models are wrong,but some are useful”G.Box(1987),最小描述长度MDL,最小描述长度MDL（minimum description length）采用与BIC完全相同的选择准则，但它源自数据压缩/最优编码BIC与MDL都只适用于似然损失。,Rissanen,J.1978.Modeling by shortest data description.Automatica,14,465-471.,MDL,可译变长编码：越频繁的信息码长越短平均信息长度越短消息的长度 与事件zi的概率 之间的关系为：为了传递具有概率密度为 的随机变量zi，需要大约 位平均信息长度,熵：消息长度的下界,MDL,假设我们有以为参数的模型M，和包含输入输出数据Z=(X,y)，则传递输出的消息长度为：选择最小长度的模型等价于选择最大后验概率的模型，同BIC,传递模型参数所需的平均消息长度,用于传递模型与目标差别所需要的平均消息长度,AIC vs.BIC,AIC：选择使 最小的模型，也是使 最大的模型，其中 为log似然函数，表示模型中有效参数的数目极大似然，同时模型复杂度极小BIC:用贝叶斯方法选择模型选择最大后验概率的模型,AIC vs.BIC,均使用模型参数数目来度量复杂度对复杂度的惩罚参数的选择不同BIC：渐近相容样本容量n时，选择正确模型的概率1有限样本情况下，当取高斯噪声时，BIC中因子2被logn代替，对复杂性施加更严厉的惩罚，倾向于选择简单模型，AIC倾向于选择复杂模型,有效参数数目,AIC/BIC中参数的数目可以扩展到使用正则化拟合的模型对线性拟合其中 为 的矩阵，只依赖于输入向量，与 无关则有效参数的数目为如对岭回归则有效参数数目为,VC维(Vapnik-Chernovenkis Dimension),之前的乐观性估计都适用于简单模型和基于似然函数的。VC理论给出了模型复杂性更一般的度量函数类 的VC维可被函数集成员打散（shatter）的点的最大数目打散不管怎样改变每个点的位置和标记，某个类别的函数中的一员都能完全分开这些点，则称为这些点能被该类别的函数打散。,VC维,2D线性函数的VC维为3，等于参数的个数,正弦函数的VC维：无穷，但参数只有一个：频率,VC维,如线性函数能打散2D平面上任意3点，因此线性函数的VC维是3。通常D维线性函数的VC维是D+1，也就是自由参数的数目。一个非线性的函数族的VC维可能无穷大，因为通过选择合适的参数，任何点的集合都能被该类的函数打散。实值函数类 的VC维定义指示函数类 的VC维，其中在 f 的值域上取值。,VC维,函数集的VC维不一定等于自由参数的个数可为等于、大于或小于尚无一般方法对任意函数集计算VC维，只有一些函数集合的VC维可计算线性函数多项式三角函数等,VC维与风险的界,对两类分类问题，假设函数类的VC维为h，则对该函数类中的每个模型，至少有 的概率满足其中对回归问题对回归问题，建议 对分类问题，没有建议，但 对应最坏的情况,VC维与风险的界,如果h有限的话，模型族的复杂性可以随n增加而增加 当h 较小时，R(M)和 Rtr 之间的差异小所以正则化回归（如岭回归）比一般最小二乘的推广型更好,VC维与风险的界,称为置信范围，随n增大而减小，随h增加而增加，与AIC中的项 d/n一致训练误差有时亦称经验风险，测试误差亦称期望风险对于特定的问题，样本数目n一般是固定的，VC维越大，测试误差与训练误差之间的差就越大。因此我们在选择模型时，不但要使训练误差最小化，还要使模型的复杂性也即VC维尽量小，从而使测试误差最小。,结构风险最小化原则(Structural Risk Minimization,SRM),这个上界是对函数类中的全部成员（参数不同）给出可能的上界，而AIC描述的是类中某个特定成员(MLE)的乐观性估计。结构风险最小化原则选择具有最小上界的函数类别。注意：VC理论并没有给出测试误差的真正估计，只是测试误差的上界，所给出的界往往是松的,结构风险最小化,设计模型的目标：同时最小化经验风险和置信范围如何同时最小化结构风险最小化原则把函数集S分解为一个函数子集序列（子集结构）：S1 S2 Sk S，使得各子集能够按照VC维的大小排列：h1 h2 hk，同一个子集中的置信范围就相同,结构风险最小化,根据函数类的性质，将它划分为一系列嵌套的子集如多项式的阶数增加；岭回归的减小；神经元网络的隐含节点数据增加学习问题：选择一个适当的函数子集（根据推广性）并在该子集中选择最好的函数（根据经验风险）,两种构造性方法,一种方法：找到合适的模型类别，然后再这个类别的模型中找到使训练误差最小的函数，即保持置信范围固定（通过选择合适的模型类别）并最小化经验风险如人工神经网络先确定网络的结构，然后再学习网络的系数另一种方法：保持经验风险固定（如为0），最小化置信范围如SVM,直接估计测试误差,重采样技术：直接估计测试误差R(M)交叉验证bootstrap,交叉验证,最简单、最常用的估计预测误差的方法思想：直接估计样本外误差 应用到来自X与Y的联合分布的独立的测试集在-折交叉验证中，数据被分成大致相等的 份。对第 份，用其余 份数据用于拟合模型，并在第 份数据上计算拟合好的模型的预测误差,K-折交叉验证,数据被分成大致相等的K份第k=1,K份数据作为校验集，其余K-1份数据用于训练模型，并在第k份数据上计算训练好的模型的预测误差例5-折交叉验证,第1折：,第2折：,第3折：,第4折：,第5折：,交叉验证,交叉验证对预测误差的估计为其中 为去掉第k份数据后训练的模型。对测试误差提供了一个估计，通过最小化 确定调整参数：最后被选中的模型为用所有数据拟合的模型,学习曲线,由于训练集减小，会引起偏差,交叉验证：K的值?,如果 称为留一交叉验证(leave-one-out cross-validation，LOOCV)。这是近似无偏的，但由于n个训练集彼此之间很相似，可能会有较高的方差。并且计算代价也很高（计算n次）。另一方面，当 CV为低方差但偏差较大。在给定训练集合大小时，如果学习曲线比较陡，则5-折、10-折CV会对真正的预测误差过估计。通常取K=10,Bootstrap,Bootstrap是一个很通用的工具，用来估计测试误差和置信区间参见第二部分：统计推断用来估计预测误差：从训练集中进行bootstrap采样，得到bootstrap样本,Bootstrap测试误差估计,bootstrap来估计检测误差：但同时从训练集和校验集中采样，当二者有重叠时，就引入了偏差。一种方法是leave-one-out bootstrap:其中 为不包含观测i的样本b的索引的集合。这解决了过拟合问题，但样本的减少带来了类似CV中的偏差问题。为了处理样本偏少的问题，采用“.632”估计子：,Bootstrap测试误差估计,“.632”估计子在“轻拟合”时表现很好，但在过拟合时会有问题，因此又引入“.632+”估计子：无信息误差率：如果输入和类别标号是独立的，则 为预测规则的误差率 过拟合率：“.632+”估计子：,Case study：前列腺癌数据,考虑模型族：岭回归模型复杂度参数：有效参数数目：采用下述技术做模型选择AICBICCVBootstrap,AIC,BIC,SRM,10-折交叉验证,最佳模型为：,Bootstrap,0.632：,Bootstrap,0.632+：,最小测试误差,到底应该选择哪个模型？,模型越简单，越不用做工作。更复杂的模型需要更正确的模型选择，采用重采样技术线性回归：AIC/BIC非参数：采用交叉验证和bootstrap通常更准确需要更多计算,总结：模型选择,模型：模型的类别每个类别的模型的参数模型选择选择测试误差最小的模型假设测试数据与训练数据的某种一致性（如IID）模型必须与数据有一定的拟合精度但模型过复杂时，数据拟合程度很好，但会出现过拟合，测试误差也会很大模型选择是在数据拟合精度与模型复杂性之间的折中,下节课内容,模型组合 更高的性能？BaggingBoosting,附：AIC推导,数据Y是根据某个未知参数的分布 产生的令 表示k维参数族分布，我们的目标是在这一类分布族中搜索与 最佳匹配的模型为了确定哪个模型与 最相近，我们需要一个度量测量真正模型 与近似模型 之间的差异,附：AIC推导,KL损失/log似然损失：表示函数f与g之间的距离，其中g为真正的分布，为当前模型,对 而言是常数C,熵定义为：,KL散度也表示用f去近似g，信息的损失量,模型选择：给定f，和数据，选择损失最小的模型参数作为参数估计，即参数 的估计为其MLE所以损失函数为：模型选择的目标是选择风险（损失的期望）最小的模型风险为期望KL损失：等价于最大化期望log似然,极大似然等价于最小KL散度，参见MLE的性质部分,log似然,其中 为当样本数 时的MLE（最小化KL损失的参数的值）,，为Fisher信息,当 时，其中p为参数的维数（特征的维数）如果f为一个较好的模型（在g附近），则,所以最小风险的模型等价于 其中第一项的估计为所以AIC为：,83,