您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 用布利冈影响函数对核方法的交叉验证的有效近似.
交叉验证简介:交叉验证是一种没有任何前提假定直接估计泛化误差的模型选择的方法,由于没有任何假定,可以应用于各种模型中,因此,具有应用的普遍性,又由于其操作的简便性,被人们认为是一种行之有效的模型选择方法。交叉验证的产生是一个曲折的过程,首先人们发现同一数据集既进行模型训练又进行泛化误差的估计会产生一个较差的结果,也就是我们常说的训练误差估计的乐观性,为了克服这个问题,人们提出了交叉验证的方法,它的基本思想是将数据分为两部分,一部分数据用来进行模型的训练,通常我们叫做训练集,另一部分数据用来测试训练生成模型的误差,我们叫做测试集,这样的泛化误差的估计可以更接近真实的泛化误差.在数据足够的情况下,我们可以很好估计出真实的泛化误差。但是在实际应用中,往往只有有限的数据可用,我们必须对数据进行重用,对数据进行多次切分来得到好的估计。自从交叉验证提出以后,人们提出不同的数据切分方式,因此产生了多种形式的交叉验证方法,下面我们对常用的交叉验证方法做一个简单的介绍。Hold-out:最早由Devroye和Wagner提出,主要思想是将数据集进行一次切分,一部分用来做训练模型,另一部分用来测试,这是最简单的一种方法,也是交叉验证的雏形。下面我们用数学语言进行描述,通常设为集合Dn={1,2,…,n}的非空子集,为其补集,我们用作为训练集来进行模型训练,Iv作为测试集来进行泛化误差的估计,这种方法通常只对数据进行一次随机切分,训练生成的模型用A(Dn)表示,最后泛化误差的估计为:其中,为训练样本,nv为测试样本个数,L为损失函数。其实严格意义来说Hold-Out方法并不能算是CV,因为这种方法没有达到交叉的思想,由于是随机的将原始数据分组,所以最后验证集分类准确率的高低与原始数据的分组有很大的关系,所以这种方法得到的结果其实并不具有说服性.IInIIcv\},...,2,1{)(IvIiinvHODALnR));((1vIiinD)(留一交叉验证:其基本思想是每次从个数为N样本集中取出一个样本作为验证集,剩下N-1个样本作为训练集,重复进行N次,依次取遍所有N个数据作为验证集,最后将平均的N个数据的结果作为泛化误差的估计。用数学语言描述为;设有样本量N的数据集DN,第j次取出样本记为,DN(-j)表示除去样本后剩下的数据,最后的泛化误差估计定义为:其中,L为损失函数。留一交叉验证有两个明显的优点:a.每一回合中几乎所有的样本皆用于训练模型,因此最接近原始样本的分布,这样评估所得的结果比较可靠;b.实验过程中没有随机因素会影响实验数据,确保实验过程是可以被复制的。其缺点是:重复次数相对来说较大,在计算上比较耗时,所以在计算复杂度上没有什么优势。jjNjjjNNLOODALNDAR1)());((1);(k折交叉验证(kCV):这种方法首先是把数据集平分为k份,每次从k份数据集中拿出一份数据集作为验证集,剩下的k-1份数据集作为训练集,重复进行k次,最后平均k次结果作为最后泛化误差的估计。用数学语言描述为:设有一样本量为n的数据集Dn,A1,…,Ak为数据集Dn的子集,且对于任意子集Aj都有M(Ai)≈n/k,M(Ai)为子集中样本的个数,最后的泛化误差估计为:其中L为损失函数,为除去子集Aj后剩下的样本,s为训练得到的模型。在kn的情况下,k折交叉验证比留一交叉验证要简单的多,因此,k折交叉验证在实际应用中是一种人们普遍使用的模型选择方法。在利用交叉验证进行模型选择时,一般选择使得泛化误差估计最小的模型。kjAijjNjkCVjDsLAMkR1)()));(()(1(1)(jND用布利冈影响函数(BIF)对核方法的交叉验证的有效近似本文结构第一部分:背景介绍;第二部分:介绍一些基本事实;第三部分:引进布利冈影响函数(BIF),并给出一个新方法近似交叉验证误差;第四部分:介绍一个计算BIF和高阶BIF的方法;第五部分:如何利用这些BIF去近似交叉验证估计;第六部分:实证分析我们所提出的近似交叉验证这个标准的性能;第七部分:结论摘要模型的选择是近代核方法的研究与应用的关键问题。交叉验证是被普遍采用且广泛接受的一个模型选择的标准。然而,交叉验证要求对考虑的算法进行多次训练,这是密集的计算。这一篇文章,介绍一个新的方法用于近似交叉验证,基于布利冈影响函数,其只要求解一次算法。BIF测量一个无穷小的污染的初始分布的影响。我们首先建立BIF与交叉验证的联系。BIF与泰勒展开式的一次项有关,从而我们计算BIF和更高阶的BIF,并应用这些理论成果去近似交叉验证的误差。试验结果证明,我们的近似交叉验证这个标准是充分且有效的。核方法的基本原理是:在非线性可分的情况下,使用一个非线性变换将输入模式空间R中的数据映射到高维特征空间F中,即,在F中基于新的分类函数,达到线性可分的目的。不必明确知道非线性变换的具体表达式,只要用核函数代替内积运算即可,如下图所示。)(xFR),(),(yxyxK通常情况下,变换函数比核函数更为复杂,也就是说简单的核函数往往对应着“复杂”的映射。因此,核函数的引入可以大大降低非线性变换的计算。常用的核方法有支撑向量机,核聚类等。)(x)(K一、引言核方法,例如支撑向量机(SVM),最小二乘支撑向量机(LSSVM)和支撑向量回归(SVR)已在数据挖掘和机器学习领域被广泛地应用。这些核方法的性能很大程度上依赖于一些超参数(例如核参数,正则化参数)的选择,因此模型选择的问题成为核方法的重要问题。与此相联系的是学习算法的外推能力的评价问题。事实上,我们通常选择使得泛化误差最小的超参数为最理想的超参数。显然,泛化误差不能被直接计算,由于产生数据的概率分布是未知的,因此,有必要依靠其值的估计。这一误差可以通过在那些没有用于学习的样本上做测试或者通过理论分析的约束来估计。为了建立泛化误差的上界,我们已有一些测量方法:例如,VC维,拉德马赫复杂度(Rademachercomplexity),最大差异,常规风险,半径边缘限制(radius-marginbound),压缩系数和特征值摄动(eigenvaluesperturbation)。已经有许多有趣的尝试运用上述约束或者其他的技术选择超参数,然而选择超参数最普遍使用且广泛接受的方法仍然是k折交叉验证(KCV)和留一法交叉验证(LOO)。然而,KCV和LOO要求解我们所用算法数次,这要求密集的计算。出于效率的目的,一些人给出了对于特定算法的LOO标准的近似:例如广义交叉验证(GCV),影响函数,广义近似交叉验证(GACV)和跨度约束(spanbound)。在这一篇文章,我们将介绍一个新方法,基于布利冈影响函数(BIF),近似k折交叉验证。我们知道,对核方法的k折交叉验证的误差的近似的有效策略还从未被提出。我们建立概念BIF和概念KCV之间的联系,并提出一个新方法计算连续分布的BIF和高阶BIF。此外,我们在样本分布上估计这些BIF并利用这些BIF得到KCV的近似。我们的方法只要求解一次算法,这可以极大地提高效率。实验结果表明我们的BIF标准是一个选择模型的不错的标准。1.1相关工作近年来,一些研究人员研究着核方法的稳健性。在稳健统计这一领域,影响函数被引入用于分析离群值对于算法的影响。这一影响函数的定义针对在特定的地方添加一个小的概率质量而轻微受扰的连续分布。已有一些人证明了支撑向量机(SVMs)对于分类和回归在对损失函数做一些假设的情况下具有有界的影响函数。Debruyne提出了一个方法通过影响函数估计LOO。Christmann和Messem推广了影响函数的概念,并从布利冈导数引进了一个新的概念称为布利冈影响函数。布利冈影响函数测量一个无穷小污染的初始分布的影响。此外,他们证明了支撑向量机在对损失函数做一些弱假设的情况下的BIF有界。对于核方法,例如SVM,LSSVM和SVR,决策函数(decisionfuction)的形式为以上工作关于核方法的稳健统计均忽略偏差b。然而,有时偏差b在核方法的性能里扮演着很重要的角色。在这里,我们考虑偏差b,并且给出一个理论的结果计算连续分布的BIF。这一结果通过一个更简单的证明推广了Christmann和Messem的结论。Debruyne提出一个方法计算高阶IF,并利用这些结果去近似LOO。我们推广IF的结果为BIF,并利用这些BIF的结果近似交叉验证的误差。bxxKxfiii),()(二、准备工作设为大小为n的独立同分布样本集,取自一个固定且未知在Z=X×Y()上的概率测度P。对于回归,;对于分类,。设为一个核函数,即K是对称的且对任何有限点集,核矩阵是半正定的。与核K相联系的再生核希尔伯特空间(RKHS)H定义为函数集线性生成空间的完备化,其上的内积表示为,满足。算子定义为:其中,是一个损失函数,是正则化参数(regularizationparameter)。niiiyxS1),(dRXRY1,1YRXXK:Xxxxn,...,,21mjijixxKK1,),(XxxKx:),()(K,),()(),(xxKxxKpkpkkkbfPbf,,,,,,:2,,,,,))((minargKpRbHfpkpkfbxfyVEbf)(V当我们使用样本分布Pn时,我们有.最小二乘支撑向量机(LSSVM),-不敏感支撑向量回归(-SVR)和二次-不敏感支撑向量回归(二次-SVR)仅仅是损失函数的选择上有所不同。对于LSSVM,V(r)=r2,对于-SVR,,而对于二次-SVR,。除非特殊说明,我们分别记和为fP和bP。21,,,,,))((1minargKiniiRbHfpkpkfbxfyVnbfnn0,max)(rrV20,max)(rrVpkf,,pkb,,三、快速近似交叉验证的方法在这一节,我们介绍布利冈影响函数(BIF)和高阶的BIF,并展现如何利用这些BIF去近似k折交叉验证(KCV).3.1布利冈影响函数定义1:设P为一个分布,T为一个算子T:P→T(P).T在P处的Q≠P方向上的布利冈影响函数定义为:BIF测量初始分布P在T(P)上Q方向的无穷小污染的影响。记.我们可以看到BIF是在处的一阶导数。)())1((lim),;(0PTQPTPTQBIFQPPQ)1(,)(,QPT0高阶的BIF可以类似的定义:定义2:设P为一个分布,T为一个算子T:P→T(P).则T在P处的Q方向上的k阶布利冈影响函数定义为:如果所有阶数的BIF都存在,则可得到如下的泰勒展开式:(1)0,|)(),;(QkkPTPTQBIF),;(!)()(1,PTQBIFiPTPTiiiQ3.2利用BIF近似KCV假设样本被分成k个互不相交的部分.令为样本S去掉观测Si的经验分布,即对于,我们有否则为0。其中M为Si的大小。对于k折交叉验证,需要对每一个i进行计算。这意味着考虑的算法需要被计算k次,这是高强度的计算。如果T的各阶BIF能被计算,我们可以提供一个快速的计算方法。首先注意到,niiiyxS1),(kiiS1iSnPMnPiSn1iSSx\)(iSnPTinSnsMnMPMnMPi))(1(其中对应于样本Si的样本分布,即对于,,否则为0.因此,令Q=,,式(1)给出(2)等式的右边现在只依赖于样本和.给出,则k折交叉验证误差可以写为其中为损失函数。其只要求解一次算法。isMxsi1)(iSxisKKnSnQbfTPPPPMnMi,,,,,,!),;()(,,1jPbfsBIFMnMbfbfnKKijjjPPPPnniSniSnnPis)
本文标题:用布利冈影响函数对核方法的交叉验证的有效近似.
链接地址:https://www.777doc.com/doc-2203112 .html