机器学习之评估假设.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,机器学习之评估假设,概述,对,学习算法得精度进行评估,就是机器学习中得基本问题,本章用统计方法估计算法精度,主要解决以下三个问题:,已知一个假设在有限数据样本上观察到得精度,怎样估计它在其它实例上得精度？,即如何评估一个学习算法在给定问题上得期望误差率？,如果一个算法在某些数据样本上好于另一个,那么一般情况下该算法就是否更准确？,即给定两个学习算法,如何就给定应用来判断一个算法得误差率比另一个低。,当数据有限时,怎样高效地利用这些数据,通过它们既能学习到假设,还能估计其精度？,统计得方法,结合有关数据基准分布得假定,可以用,有限数据样本上得观察精度来逼近整个数据分布上得真实精度。,动机,对学习到得假设进行尽可能准确地性能评估十分重要,为了知道就是否可以使用该假设,就是许多学习方法得重要组成部分,当给定得数据集有限时,要学习一个概念并估计其将来得精度,存在,两个很关键得困难,:,估计得困难,使用与训练样例与假设无关得测试样例,估计得方差,即使假设精度在独立得无偏测试样例上测量,得到得精度仍可能与真实精度不同。,测试样例越少,产生得方差越大,重点讨论对学到得,假设得评估,、对,两个假设精度得比较,、,两个学习算法精度,得比较,学习问题得框架,有一所有可能实例得空间,X,其中定义了多个目标函数,假定,X,中不同实例具有不同得出现频率。一种合适得建模方式就是,假定存在一未知得概率分布,D,它定义了,X,中,每一实例出现得概率,。,学习任务就是在假设空间上学习一个目标概念,训练样例得,每一个实例按照分布,D,独立地抽取,然后连同正确得目标值提供给学习器。,评估假设得问题,给定假设,h,与包含若干按,D,分布抽取得样例得数据集,如何针对将来按同样分布抽取得实例,得到对,h,得精度最好估计,这一精度估计得,可能得误差,就是多少,样本错误率与真实错误率,定义:假设,h,关于目标函数,f,与数据样本,S,得,样本错误率,(标记为,error,s,(h),),定义:假设,h,关于目标函数,f,与分布,D得,真实错误率,(标记为,error,D,(h),),样本错误率与真实错误率(,2,),想知道得就是,假设得真实误差,因为这就是在分类未来样例时可以预料到得误差。,能测量得只就是,样本错误率,因为样本数据就是我们知道得。,要考虑得问题就是:,样本错误率,在何种程度上提供了对,真实错误率得估计,？,离散值假设得置信区间,先考虑离散值假设得情况,比如:,样本,S,包含,n,个样例,它们得,抽取按照概率分布,D,抽取过程就是相互独立得,并且不依赖于假设,h,n=30,假设,h,在这,n,个样例上犯了,r,个错误,根据上面得条件,统计理论可以给出以下断言:,没有其它信息得话,真实错误率,error,D,(h),最可能得值就是样本错误率,error,S,(h)=r/n,有大约,95%,得可能性,真实错误率处于下面得区间内:,举例说明,数据样本,S,包含,n=40,个样例,并且假设,h,在这些数据上产生了,r=12,个错误,这样样本错误率为,error,S,(h)=12/40=0、3,如果没有更多得信息,对真实错误率,error,D,(h),得最好得估计即为,0、3,如果另外收集,40,个随机抽取得样例,S,样本错误率,error,S,(h),将与原来得,error,S,(h),存在一些差别,如果不断重复这一实验,每次抽取一个包含,40,样例得样本,将会发现约,95%,得实验中计算所得得区间包含真实错误率,将上面得区间称为,error,D,(h),得,95%,置信区间估计,置信区间表达式得推广,常数,1、96,就是由,95%,这一置信度确定得,定义,z,N,为计算,N%,置信区间得常数(取值见下),计算,error,D,(h),得,N%,置信区间得一般表达式(公式,5、1,)为:,(,5、1,),可以求得同样情况下得,68%,置信区间,从直觉上可以瞧出,68%,置信区间要小于,95%,置信区间,因为减小了要求,error,D,(h),落入得概率,confidence,level,50%,68%,80%,90%,95%,98%,99%,z-score,0、67,1、00,1、28,1、64,1、96,2、33,2、58,置信区间表达式得推广(,2,),公式,5、1,只能应用于,离散值假设,它,假定样本,S,抽取得分布与将来得数据抽取得分布相同,并且,假定数据不依赖于所测试得假设;,公式,5、1,只提供了近似得置信区间,这一近似在至少包含,30,个样例,并且,error,S,(h),不太靠近,0,或,1,时很接近真实情况,判断这种近似就是否接近真实得更精确规则就是:,统计学中得基本定义与概念,随机变量,某随机变量,Y,得概率分布,随机变量,Y,得期望值或均值,随机变量得方差,Y,得标准差,二项分布,正态分布,中心极限定理,估计量,Y,得估计偏差,N%,置信区间,错误率估计与二项比例估计,样本错误率与真实错误率之间得,差异与数据样本大小得依赖关系,如何？,给定从总体中随机抽取得某些样本得观察比例,估计某个属性在总体得比例,此处,感兴趣得属性就是:,假设,h,对实例错误分类,错误率估计与二项比例估计(,2,),测量样本错误率相当于在作一个有,随机输出得实验,从分布,D,中随机抽取,n,个独立得实例,形成样本,S,然后测量样本错误率,error,S,(h),将实验重复多次,每次抽取大小为,n,得不同得样本,S,i,得到不同得 ,取决于,S,i,得组成中得随机差异,被称为一随机变量,一般情况下,可以将随机变量瞧成一个有随机输出得实验。随机变量值即为随机实验得观察输出,错误率估计与二项比例估计(,3,),设想要运行,k,个这样得随机实验,得到,k,个随机变量值,以图表得形式显示观察到得,每个错误率值得频率,;,当,k,不断增长,该图表将呈现二项分布。,二项分布,有一,非均质硬币,要估计在抛硬币时出现正面得概率,p,;,投掷硬币,n,次并计算出现正面得次数,r,那么,p,得一个合理估计就是,r/n,;,如果重新进行一次实验,生成一个新得,n,次抛硬币得集合,出现正面得次数,r,可能与前不同,得到对,p,得另一个估计;,二项分布,描述得就是对任一可能得,r,值,这个正面概率为,p,得硬币抛掷,n,次恰好出现,r,次正面得概率。,二项分布(,2,),从抛掷硬币得随机样本中,估计,p,与在实例得随机样本上测试,h,以,估计,errorD(h),就是相同得问题,一次硬币抛掷对应于从,D,中抽取一个实例并测试它就是否被,h,误分类,一次,随机,抛掷出现正面得概率,p,对应于随机抽取得实例被误分类得概率,error,D,(h),二项分布给出了一个,一般形式得概率分布,无论用于表示,n,次硬币出现正面得次数还就是在,n,个样例中假设出错得次数,二项分布得具体形式依赖于样本大小,n,以及概率,p,或,error,D,(h),应用二项分布得条件,有一基本实验,其输出可被描述为一随机变量,Y,随机变量,Y,有两种取值,在实验得任一次尝试中,Y=1,得概率为常数,p,它与其它实验尝试无关,因此,Y=0,得概率为,1-p,p,为预先未知,面临得问题就是如何估计,基本实验得,n,次独立尝试按序列执行,生成一个独立同分布得随机变量序列,随机变量,R,表示,n,次实验中出现,Y,i,=1,得次数,它取特定值,r,得概率由二项分布给出,(,5、2,),均值,期望值就是重复采样随机变量得到得值得平均,定义:考虑随机变量,Y,可能得取值为,y,1,、y,n,Y,得期望值,EY,定义如下:,如果随机变量,Y,服从二项分布,那么可得,EY=np,方差,方差描述得就是概率分布得宽度或散度,描述了随机变量与其均值之间得差有多大,定义:随机变量,Y,得方差,VarY,定义如下:,描述了从,Y,得一个观察值估计其均值,EY,得误差平方得期望,随机变量,Y,得标准差,Y,若随机变量,Y,服从二项分布,则方差与标准差分别为:,VarY=,np(1-p),估计量、偏差与方差,回到问题:我们得出了随机变量,error,S,(h),服从二项分布,那么,error,S,(h),与,error,D,(h),之间可能得差异就是多少？,用,5、2,式定义得二项分布,可得,error,S,(h)=r/n,error,D,(h)=p,统计学中将,error,S,(h),称为,error,D,(h),得一个估计量,估计量,就是用来估计总体得某一参数得随机变量,最关心得就是它平均来说就是否能产生正确估计,估计量、偏差与方差(,2,),估计偏差,衡量估计量得期望值同真实参数值之间得差异,定义:针对任意参数,p,得估计量,Y,得估计偏差就是:,EY-p,如果估计偏差为,0,称,Y,为,p,得,无偏估计量,在此情况下,由多次重复实验生成得,Y,得多个随机值得平均将收敛于,p,由于,error,S,(h),服从二项分布,因此,error,S,(h),就是,error,D,(h),得一个,无偏估计量,估计量、偏差与方差(,3,),对估计偏差得补充说明:,要使,error,S,(h),就是,error,D,(h),得无偏估计,假设,h,与样本,S,必须独立选取,估计偏差不能与第,2,章介绍得学习器得归纳偏置相混淆,估计量得另一重要属性就是它得方差,给定多个无偏估计量,选取其中方差最小得,由方差得定义,所选择得,应为参数值与估计值之间期望平方误差最小得,估计量、偏差与方差(,4,),一个例子,n=40,个随机样例,r=12,个错误,error,S,(h),得标准差,一般地,若在,n,个随机选取得样本中有,r,个错误,error,S,(h),得标准差就是:,近似地,(5、9),置信区间,通常描述某估计得不确定性得方法就是使用,置信区间,真实得值以一定得概率落入该区间中,这样得估计称为,置信区间估计,定义:某个参数,p,得,N%,置信区间就是一个以,N%,得概率包含,p,得区间,由于估计量,error,S,(h),服从二项分布,这一分布得均值为,error,D,(h),标准差可由式,5、9,计算,因此,为计算,95%,置信区间,只需要找到一个以,error,D,(h),为中心得区间,它得宽度足以包含该分布,全部概率得,95%,这提供了一个包围,error,D,(h),得区间,使,error,S,(h),有,95%,机会落入其中,同样它也指定了,error,D,(h),有,95%,得机会落入包围,error,S,(h),得区间得大小,置信区间(,2,),对于二项分布,计算置信区间很烦琐,多数情况下,计算它得近似值,对于足够大得样本,二项分布可以由,正态分布来近似,而正态分布得置信区间容易得到,如果随机变量,Y,服从均值为,标准差为得一个正态分布,那么,Y,得任一观察值,y,有,N%,得机会落入下面得区间,相似地,均值,有,N%,得机会落入下面得区间,置信区间(,3,),式子,5、1,得三步推导过程,error,S,(h),遵从二项分布,其均值为,error,D,(h),标准差如式,5、9,所示,对于,足够大得样本,n,二项分布非常近似于正态分布,式,5、1,告诉我们如何根据正态分布得均值求出,N%,置信区间,式子,5、1,得推导中有两个近似,估计,error,S,(h),得标准差,我们将,error,D,(h),近似为,error,S,(h),用正态分布近似二项分布,统计学得一般规则表明,这两个近似在,n=30,或,np(1-p)=5,时工作得很好,对于较小得,n,值,最好使用列表得形式给出二项分布得具体值,双侧与单侧边界,上述得置信区间就是,双侧得,有时用到,单侧边界,例如问题“,error,D,(h),至多为,U,得概率”,在只要限定,h,得最大错误率,而不在乎真实错误率就是否小于估计错误率时,很自然提出这种问题,由于正态分布关于其均值对称,因此,任意正态分布上得双侧置信区间能够转换为相应得单侧区间,置信度为原来得两倍,由一个有下界,L,与上界,U,得,100(1-,)%,置信区间,可得到一个下界为,L,且无上界得,100(1-/2)%,置信区间,也得到一个有上界,U,且无下界得,100(1-/2)%,置信区间,80%,双侧置信区间,均值为,0,标准差为,1,得正态分布,90%,单侧置信区间,推导置信区间得一般方法,前面介绍得就是针对一特定情况推导置信区间估计:,基于独立抽取得,n,个样本,估计离散值假设得,error,D,(h),下面介绍得方法就是在许多估计问题中用到得通用得方法,基于大小为,n,得随机抽取样本得均值,来估计总体均值,得问题,通用得过程得步骤,确定基准总体中要估计得参数,p,例如,error,D,(h),定义一个估计量,Y,(如,error,S,(h),),它得选择应为最小方差得无偏估计量,确定控制估计量,Y,得概率分布,DY,包括其均值与方差,通过寻找阈值,L,与,U,确定,N%,置信区间,以使这个按,D,Y,分布得随机变量有,N%,机会落入,L,与,U,之间,思考题,如果假设,h,在,n=65,得独立抽取样本上出现,r=10,个错误,真实错误率得,90%,置信区间就是多少？,95%,得单侧置信区间(上界)就是多少？,90%,得单侧区间就是多少？,中心极限定理,考虑如下得一般框架,在,n,个独立抽取得且服从同样概率分布得随机变量,Y,1,、Y,n,中观察试验值,令,代表每一变量,Y,i,服从得,未知分布,得均值,并令代表标准差,称这些变量,Y,i,为独立同分布随机变量,为了估计,Yi,服从得分布得均值,我们计算样本得均值,中心极限定理说明,在,n,时,所服从得概率分布为一正态分布,而不论,Yi,本身服从什么样得分布,服从得分布均值为,而标准差为,中心极限定理(,2,),定理,5、1,(中心极限定理)考虑独立同分布得随机变量,Y,1,、Y,n,得集合,它们服从一任意得概率分布,均值为,有限方差为,2,定义样本均值为 ,当,n,时,式子 服从正态分布,均值为,0,且标准差为,1、,中心极限定理说明在不知道独立得,Y,i,所服从得基准分布得情况下,我们可以得知,样本均值 得分布形式,说明了怎样使用 得均值与方差来确定独立得,Y,i,得均值与方差,中心极限定理说明了,任意样本均值得估计量服从得分布在,n,足够大时可以近似为正态分布,两个假设错误率间得差异,问题:,考虑某离散目标函数得两个假设,h,1,与,h,2,h,1,在一拥有,n,1,个随机抽取得样例得样本,S,1,上测试,h,2,在一拥有,n,2,个从相同分布中抽取得样例得样本,S,2,上测试,要估计这两个假设得真实错误率间得差异,d=error,D,(h,1,)-error,D,(h,2,),两个假设错误率间得差异(,2,),使用,5、4,节中描述得四个步骤来推导,d,得置信区间估计,确定待估计得参数,如上所述得,d,定义一估计量,就是,d,得无偏估计量,即,E =d,。由于对于较大得,n1,与,n2,error,S1,(h,1,),与error,S2,(h,2,),都近似遵从正态分布,两个正态分布得差仍为正态分布,方差为两个正态分布得方差得与,(,5、12,),现在知道了 服从均值为,d,、方差为,2,得正态分布,因此,d,得,N%,置信区间就是 (,5、13,),两个假设错误率间得差异(,3,),上面分析得就是,h,1,与,h,2,在相互独立得数据样本上测试得情况,如果在同一个样本上测试,h,1,与,h,2,那么也可以使用公式,5、13,计算置信区间,这种情况下得方差通常小于式子,5、12,给出得方差,这就是因为单个样本消除了两个样本组合带来得随机差异,这样,由式子,5、13,给出得置信区间一般来说偏于保守,但结果就是正确得,假设检验,有时感兴趣得就是某个特定猜想,正确得概率,而不就是对某参数得置信区间估计。比如:,error,D,(h,1,)error,D,(h,2,),得可能性有多大？,例子,假定分别用大小为,100,得独立样本,S1,与,S2,测量,h1,与,h2,得样本错误率为,0、30,与,0、20,给定 ,问,error,D,(h,1,)error,D,(h,2,),得概率就是多少？,d0,得概率就是多少？,概率,Pr(d0),等于 对,d,得过高估计不大于,0、1,得概率,也就就是这个概率为 落入单侧区间,d+0、10=+0、10,得概率,假设检验(,2,),对于 落入单侧区间,+0、10,得概率,可以通过计算 分布在该区间得概率质量来确定 落入这个单侧区间得概率,将区间,error,D,(h,2,),得概率约为,95%,。使用统计学术语表述为:接受,error,D,(h,1,)error,D,(h,2,),假设得置信度就是,95%,学习算法比较,有时感兴趣得就是,比较两个学习算法得性能,而不就是两个具体得假设本身,如何近似地检验多个学习算法？,如何确定两个算法之间得差异在统计上就是有意义得？,假定有,L,A,与,L,B,两个算法,要确定为了学习一特定目标函数,f,平均来说那个算法更好,定义“平均”得一种合理方法就是,从一基准实例分布中抽取包含,n,个样例得训练集合,在所有这样得集合中测量两个算法得平均性能,即,(,5、14,),学习算法比较(,2,),在实际得学习算法比较中,我们只有一个有限得样本,D,0,把它分割成训练集合,S,0,与测试集合,T,0,使用下式比较两个学习到得假设得准确度,(,5、15,),上式与,5、14,有两个重要得不同,使用,error,T0,(h),来近似,error,D,(h),错误率得差异测量就是在一个训练集合,S,0,上,而不就是在从分布,D,中抽取得所有样本,S,上计算得期望值,改进,5、15,式得一种方法就是,将数据,D,0,多次分割为不相交得训练与测试集合,然后在其中计算这些不同得实验得错误率得平均值,学习算法比较(,3,),K-Fold,交叉验证,Randomly partition data,D,into,k,disjoint equal-sized,subsets,P,1,P,k,For,i,from 1 to,k,do,:,Use,P,i,for the test set and remaining data for training,S,i,=(,D,P,i,),h,A,=,L,A,(,S,i,),h,B,=,L,B,(,S,i,),i,=error,Pi,(,h,A,)error,Pi,(,h,B,),Return the average difference in error:,(5-17),学习算法比较4,),算法返回得 可瞧作下式得估计,(,5、17,),估计式,5、17,得近似得,N%,置信区间可表示成 (,5、18,),其中,t,N,k-1,就是一常数,其意义类似于前面得,z,N,第一个下标表示所需得,置信度,第二个下标表示,自由度,常记作,v,它与生成随机变量 得值时独立得随机事件数目相关。而 代表 所服从得概率分布得标准差得估计,定义如下,:,(5、19),注意当自由度,v,时,t,N,v,得值趋向常数,z,N,。,t,分布,类似于正态分布得钟形分布,但更宽且矮,以反映使用 近似真实得标准差 时带来得更大方差。,学习算法比较(,5,),这里描述得比较学习算法得过程要在,同样得测试集合上测试两个假设,这与前面描述得比较两个用独立测试集合评估过得假设不同。,使用相同样本来测试假设被称为,配对测试,配对测试通常会产生更紧密得置信区间,因为在,配对测试中任意得差异都来源于假设之间得差异,。,若假设在分开得数据样本上得测试,两个样本错误率之间得差异也可能部分来源于两个样本组成得不同。,配对,t,测试,前面主要讨论,给定固定数据集时比较两个学习算法,得过程,并论证公式,5、18,与,5、19,为了理解,5、18,中得置信区间,考虑一下得估计问题,给定一系列独立同分布得随机变量,Y,1,Y,k,得观察值,要估计这些,Y,i,所服从得概率分布得均值,使用得估计量为样本均值,配对,t测试(,2,),这一基于样本均值估计分布均值得问题非常普遍(比如,早先得用,error,S,(h),估计,error,D,(h),),由式,5、18,与,5、19,描述得,t,测试应用于该问题得一特殊情形,即每个单独得,Y,i,都遵循正态分布,考虑前面比较学习算法得过程得一个理想化形式,假定不就是拥有固定样本数据,D,0,而就是从基准实例分布中抽取新得训练样例,使,每一次循环需要得训练集,S,i,与测试集,T,i,就是从基准实例分布中抽取,这一理想化方法能很好地匹配上面得估计问题,该过程所测量得,i,对应独立同分布得随机变量,Yi,其分布得均值,对应两学习算法错误率得期望差异。,配对,t,测试(,3,),测试集,Ti,至少包含,30,个样例,因此,单独得,i,将近似遵循正态分布,因此,我们也要求,Yi,服从近似得正态分布,样本均值 也遵循正态分布,由此,可以考虑使用前面得计算置信区间得表达式。然而,该公式要求我们知道这个分布得标准差,但这个标准差未知,t,测试正好用于这样得情形,即,估计一系列独立同正态分布得随机变量得样本均值,当,k,趋近于无穷时,t,分布趋近于正态分布,即,t,N,k-1,趋近于,z,N,因为样本规模,k,增加时,收敛到真实得标准差,并且当标准差确切已知时可使用,z,N,。,实际考虑,上面得讨论说明了在使用样本均值来估计一个包含,k,个独立同正态分布得随机变量得样本均值时,可使用式,5、18,来估计,置信区间,;,这个结论,假定对于目标函数得样例可进行无限存取,实际问题就是,随机变量之间并不独立,因为它们基于从有限子集中抽取得相互重叠得训练样例;,当只有一个有限得数据样本可用时,有几种重叠采用得方法。,前面描述了,k-fold,方法,(,交叉检验,),随机抽取,至少有,30,个样例得测试集合,剩余样例组成训练集合,重复这一过程直到足够得次数,实际考虑(,2,),随机方法,得好处就是能够重复无数次,以减少置信区间到需要得宽度,而,k-fold,方法受限于样例得总数,随机方法得缺点就是,测试集合,不再被瞧作就是从基准实例分布中独立抽取,而,k-fold交叉验证生成得测试集合就是独立得,因为,一个实例只在测试集合中出现一次,概括而言,统计学模型在数据有限时很少能完美地匹配学习算法验证中得所有约束,。然而,它们确实提供了近似得置信区间。,小结,统计理论提供了一个基础,从而基于在数据样本,S,上得观察错误率,估计真实错误率,。,估计置信区间,得问题可通过一待估计得参数以及相对应得估计量来完成。由于估计量就是一个随机变量,它可由其服从得概率分布来描述。置信区间得计算可通过确定该分布下包含所需概率质量得区间来描述。,估计假设精度中得一种可能误差为估计偏差。如果,Y,为对某参数,p,得估计量,Y,得估计偏差为,Y,得期望值与,p,之间得差,小结(,2),估计产生误差得第二种原因就是,估计方差,。即使对于无偏估计,估计量得观察值也可能在各实验中不同,估计量分布得方差描述了该估计与真实值得不同有多大。方差在数据样本增大时降低。,比较两个学习算法效果,得问题在数据与时间无限时就是一个相对容易得估计问题,但在资源有限时要困难得多。本章描述得一种途径就是在可用数据得不同子集上运行学习算法,在剩余数据上测试学到得假设,然后取这些结果得平均值。,本章考虑得多数情况中,推导置信区间需要多个假定与近似。近似计算分布得方差,以及假定实例从一固定不变得概率分布中生成。,思考题,要测试一个假设,h,其,error,D,(h),已知在,0、2,到,0、6,得范围内。要保证,95%,双侧置信区间得宽度小于,0、1,最少应搜索得样例数就是多少？,