注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

行走的馒头

Stay Hungry, Stay Foolish

 
 
 

日志

 
 

五、Model Selection and Model Assessment  

2012-09-02 11:38:57|  分类: 统计学习初探索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

先简单介绍一下model selection和model assessment。通常,我们的模型会存在一个tuning parameter ,也叫做模型复杂度参数,这个参数控制着我们模型的复杂程度。注意这里的模型我们假定使用某一种类模型,比如在使用线性回归时,可以是选择使用feature的个数P,选择使用的feature越多,模型就越复杂;也可以是基变换的阶数,阶数越大,我们也认为模型越复杂;当然也可以同时是他们的结合。在同一类模型中,对于不同的,我们都可以通过learning过程得到一个模型,不妨把这个模型叫做这一类模型中的子模型,然后我们可以通过一些标准来比较这些子模型的优劣。Model selection要做的就是找出在某种标准下表现最好的那个子模型。这些标准就是下面会提到的各种误差标准,而有些误差标准比较难于直接求解,我们可以使用其他的误差和方法去估计这种标准,像下面会描述的AIC、BIC以及cross validation和bootstrap都属于此类。而model assessment就是在我们已经通过model selection选取最佳的那个子模型后,我们评估这个子模型的泛化能力。一个学习方法或者说模型的泛化能力是指这种方法在独立测试集上面的预测表现。

如果数据量非常可观,通常可以把数据划分成三个数据集。其中训练数据集用来对每个对应下的子模型进行学习,得到估计的参数值,而在验证数据集下用某种标准来筛选最佳的那个子模型,最后在测试数据集上面我们来评估这个最佳子模型的表现。在实际中很难说应该怎样去划分这个数据集,通常的作法是50%的数据放入训练集,而验证集和测试集各25%。

 

损失函数及误差

子模型之间要进行比较,让我们先来看看常用的一些标准。这些标准牵涉到损失函数、训练误差、测试误差等等。

对于regression模型,典型的损失函数有

假定我们的训练数据集记为。测试误差(test error),也叫做泛化误差(generalization error),是指在独立测试集上的误差

这里因为训练集T是固定的,所以误差只针对这个训练集训练出来的参数。这里求期望是针对X,Y的联合概率分布。

期望测试误差(expected test error),也叫做期望预测误差(expected prediction

error),可表示如下

注意这里的期望平滑了所有的随机项,包括XY的联合分布和使用随机选择的训练数据集产生的

    训练误差(Training error)对应于训练集中所有样本点损失的平均,可表示如下

训练误差在machine learning中也叫做empirical risk或者empirical error

 

    很多时候,我们的目标是最小化test error,而test error往往也比较难求,training error却容易求解,但是不幸的是,用training error往往并不能很好的去估计test error。因为随着模型变得越来越复杂,training error往往会逐渐减小,当模型足够复杂的时候,train error甚至可以降为0,但这时往往是overfit的,其test error一般都会比较大。后面会介绍一些方法用training error和模型复杂度参数来估计test error,以及他们之间的界限关系。

 

    对于classfication,情况也是类似的,只是损失函数的形式有点不同而已。模型给出样本属于第k类的概率为,给出的分类结果为。常见的损失函数有

    

    如果因变量具有Gauss, Poisson, gamma, exponential, log-normal等形式的分布,log-likelihood经常被用来作为损失函数。我们假定因变量的密度函数为,那么损失函数就可以表示为

,这里使用-2是为了使得当Y服从高斯分布时,就像linear regression所讨论,能够对应squared-error loss     

 

 

The Bias–Variance Decomposition

首先我们假定因变量和自变量的关系可以表示如下

对于regression拟合出来的,其在处的expected test error可表示为

式子中的第一项是随机误差,表示因变量的值偏离其真实值的程度,除非,否则是不可避免的。第二项是bias的平方和,表示我们的估计值和真实值偏差的期望,注意这里的期望是针对选用不同的训练集拟合的值。第三项是模型本身的variance

 

下面是一个误差示意图。横轴对应于模型复杂度,这里共使用了100个训练数据集,浅蓝色的每条线表示每个训练集对应的training error,深蓝色的线表示expected train error。浅红色的线表示每个训练集对应的test error,深红色的线表示expected test error。我们可以看出training errorexpected train error对于模型复杂度总是递减的,而test errorexpected test error则有一个波动的过程。另外,模型复杂度很低的时候,对应着较大的bias和较小的variance,随着复杂度增加,bias变小,variance变大。

 

    linear regression中,拟合的模型可以表示为,所以在样本点处的test error可以表示为

其中, 

 

    这里我们可以把对应的对应的分解的更细一点。记为最佳的参数估计,则其可以表示为

注意上式中的期望是针对自变量X。可以看到,表示的是使用最佳子模型估计的参数。这时那么bias-variance 分解中可表示为

这里第一项是model本身bias平方和的期望。Model本身的bias是指最佳子模型能够达到的误差。第二项是指在模型复杂度为的时候,我们在各种训练集上找到的最佳估计对应的拟合值的期望与最佳model拟合值的差距,这里的差距反映了在当前模型复杂度的performance和最佳的performance的距离。可以证明,在普通的最小二乘中, estimation bias等于0,在有约束的条件下,比如ridge regression中,estimation bias会变大,相应的variance会变小。而对于model bias ,则能够通过基变换增加自变量X的阶数来减小。

 

 

Cp、AIC及BIC

    下面可以看到, AIC以及BIC都是通过使用一个训练集的training error来估计in-sample error的,而后面提到的cross validationbootstrap则使用多个训练集的training error来估计test error或者expected test error

Optimism of the Training Error Rate

    Test error 可以被认为是一种extra-sample error,因为测试集相对于原来的训练集是独立的。相应的,我们可以定义in-sample error

我们定义in-sample errortraining error之差optimism

op通常都大于0,因为在每个样本点只针对已经出现的,容易overfit,使得其变得较小。而在中,在每个样本处平滑了没有出现的Y值的情况。

因为在训练集中所有样本X的取值是固定的,我们对op求关于因变量Y的期望

对于squared error, 0-1 error以及其他一些损失函数,我们可以得到

因此,我们可以得到如下的式子

如果我们的模型为对应着d个参数的linear regression或基扩展后的linear regression,则

那么,的关系可表示为

 5.1

针对特定的训练集,可以看做是 的一种估计。我们估计时,可以通过op相加来得到。下面提到的 , AIC, BIC等方法都属于此类。虽然可能离我们的目标 或者可能差的比较多,因为在独立测试数据集上数据的分布可能跟训练集不太一样,然而在做model selection的时候其仍然是一个不错的选择。另一方面,像cross validationbootstrap等方法都可以直接估计或者

 

Estimates of In-Sample Prediction Error

    估计的一个通用的式子可表示为。下面是三种从不同角度对 的估计。

 

如果使用式子(5.1)中的关系,并假设损失函数为squared error,我们可以得到的估计可表示为如下的形式

其中是对noise variance的一个估计,常常采用某种low-bias modelmean-squared error去估计。

 

AIC Akaike information criterion

如果损失函数为log-likelihood损失函数,当时,根据(5.1)可以得到

比如在在logistic regression中,AIC可以表示为

我们通常使用AIC来做model selection,我们通常选择使AIC最小的那个子模型。我们用表示对应下子模型中的训练误差和模型的参数个数。这时AIC可表示为

下面的示意图中,横轴表的基变换的个数对应于,黄色的线表示train error,蓝色的线表示test error,而绿色的则表示AIC

 

The Bayesian Approach and BIC

如果损失函数为log-likelihood损失函数,除了AIC,我们也可以使用BIC,其可以表示为

 5.2

对于高斯模型来说,假设随机误差已知,第一项 等价于,所以BIC也可以表示为

可以看出来,相比于AICBIC对复杂的模型惩罚的更加重一点,因此在采用BICmodel selection的时候更加倾向于选择较简单的子模型。

    虽然BIC的样子和AIC长得很像,但是他们的出发点确实很不一样的,让我们来看看。假设现在我们有M个子模型,每个子模型对应有参数,每个子模型中参数的先验概率为对应于训练数据集。那么给定训练数据集的后验概率就可以表示为

要比较两个子模型的优劣,我们可以比较它们的后验概率

其中叫做贝叶斯因子(bayes factor)。在通常情况下,我们可以假定都是相同的,那么我们可以只估计。一种叫做laplace approximation的方法给出的估计如下

这里是子模型下的最大似然估计,表示参数个数。如果我们定义损失函数为

,那么可以看到上面的式子跟(5.2)定义的BIC的形式是相同的。因此,我么可以看到,BIC选择的是具有最大后验概率的那个子模型。

    在实际应用中,使用AIC还是BIC等并没有明确的界限。一般的,当时,AIC倾向于选择复杂度很高的子模型,而BIC倾向于选出正确的那个子模型。而当样本量很小的时候,BIC倾向于选择非常简单的子模型。

 

 

误差分析及VC维

Error Bound

先来看看一些误差分析中要用到的一些引理。

  1. 如果 k个不同的事件,它们之间可能相互独立,也可能不会,anyway,都满足下面的式子

  2. Hoeffding不等式。如果 m个独立同分布的随机变量,并且它们都满足Bernoulli分布,,定义为这些随机变量的均值。那么,对于任何固定的 ,满足下面的式子

    ,这个式子也叫做Chernoff Bound

对于二分类问题,如果我们使用0-1损失函数,对于任何一个子模型 ,我们定义随机变量 ,在每一个样本i处我们定义 ,因为我们的样本中的样本点是独立同分布的,因此 是同分布的。因此我们的training error可以表示为

 。从前面Test error 的定义中看到,其是随机变量 期望。根据 是同分布的,以及前面的Hoeffding不等式,我们可以得到下面的式子

令事件 表示 ,那么我们有 ,因此我们有

因此,把上面的式子稍微变换一下就得到

 ,对于每个子模型 ,我们容易根据上面的式子容易得到下面的结论, 至少以 的概率成立。

 为最佳的子模型,假设这里选择最佳模型的标准为使得 最小。我们有下面的结论

至少以 的概率成立。

 

Vapnik–Chervonenkis Dimension

VC维的理论描绘了怎么去估计一个子模型的复杂度,提供了误差分析中界限方面的理论。我们来简单看看。

    前面我们描绘的子模型的复杂度往往跟其参数的个数有关,但是事实总是这样子的么?让我们来看看下面的情况。假设我们的模型为判别函数,如果为一个向量,并且一个子模型对应判别函数可表示为,我们可以说这个子模型的模型复杂度为p+1,其中p为自变量X的维度。但是如果  是一个实数,我们知道这是一个非常扭曲的函数,但是这儿只有一个参数,但是我们可以说这个子模型比前面的的复杂度会低么?显然结论是否定的。

    给定一个样本集 ,并且这些样本是二分类的,如果我们的子模型能够正确的分类这个样本集所有可能的label的情况,那么我们说这个子模型能够shatter这个样本集。并且这个子模型的VC维就是他所能shatter的最大的样本中样本点的数目。

    举个例子,如果我们的特征空间为 ,并且我们的子模型为 ,对于样本中只有三个样本点的情况,我们看到子模型能够shatter这个样本集,如下图

    当样本有四个样本点是,容易看出不能够shatter样本了,所以 能够shatter的最大样本的样本点的数目为3,所以我们说VC维是3

    我们可以用VC维来进行误差分析,把模型复杂度带入到上面的误差分析中,如果用VC 来刻画模型复杂度,那么可以得到下面的结论

 至少以 的概率成立

其中

其中 可认为是误差的一个上界。在Vapnik的最小结构风险(structural risk minimizationSRM的方法中,我们要选的就是误差上界最小的那个子模型。在实际应用中,SRM往往并不那么可行,因为首先VC维一般都非常难求,而且这里的误差上界往往都非常宽松。而AICBIC等标准往往更加实用一点。

 

 

    Cross-Validation

Cross Validation是对test error或者expected test error的一种估计。如果我们把所有数据平均的分成K个部分,我们把第k个部分作为验证集,其余K-1个部分作为训练集。下面是一个k=3,K=5的示意图。然后,我们把 时分别计算的test error求平均。

令映射表示把样本映射到划分数据集的哪一个部分。表示用除k各部分外的数据拟合出来的模型,用cross valildation估计的test error可表示为

如果K=N,这时叫做leave-one-out cross validation。如果我们的每个子模型对应于一个模型复杂度参数 cross validation这时可以表示为

然后我们就可以找出最小的那个 所对应的那个子模型最为我们的最佳子模型。

让我们来看看K-fold cross validation 的效果,当 的时候,我们可以看到这时进行K次拟合时所用的训练数据集都相差很大,相当于对expected test error进行估计。这时我们的估计variance就会比较小,而bias可能会较大。当KN很接近时,比如leave-one-out cross validation中,进行K次拟合时所用的训练数据集其实几乎没差别,这时就相当于对test error进行估计了。这时的我们的估计具有较低的bias和较高的variance,因为我们每次相当于在使用几乎同一个数据集。而且这时K很大,计算的时间开销也很大。在实际使用中,常取K=5或者K=10

下面是一个训练数据集大小和误差的示意图

可以看到,当训练数据集的大小超过100,时,拟合出来的模型的效果并没有太大的改进。如果我们的数据集大小为200,这时我们做5-fold或者10-foldcross validation,在每个训练集上的效果跟使用全部数据集的效果并没有太大的差距,这时使用cross validation就不会有太大的bias。然而,如果我们的数据集的大小为50,那么我们可以看到使用5-fold或者10-foldcross validation就会对误差估计过高。这时就会产生较大的bias。在实际中,我们可以画出这样的曲线,然后看看去什么样的K比较合适。

 

Bootstrap Methods

Bootstrap同cross validation类似,也是估计test error的一种方法。我们的训练数据集为 ,Bootstrap的想法是我们每次从训练集中随机可重复的选取N个样本点,然后这种抽样重复B次,我们就产生了B个bootstrap数据集。下面是bootstrap的一个示意图, 表示对bootstrap数据集的的一些操作,比如计算预测值和误差等等。

我们用来表示用第bbootstrap数据集训练出来的模型在第i个样本点处的拟合值,那么用bootstrap方法来估计test error可表示为

可以看到,这个估计的泛化能力可能不是很好,因为我们在计算误差的时候所有的样本点跟训练模型时的样本点有很大的重合,容易产生overfitting。而在cross validation中则避免了这样的情况,因为其把训练集和测试集是分开了的。因此,对上面的式子稍作改进,我们得到所谓对test errorleave-one-out估计

其中 表示不包括样本点i的那些bootstrap训练集。

 

 

    


  评论这张
 
阅读(2651)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017