1、交叉驗(yàn)證簡(jiǎn)介： 交叉驗(yàn)證是一種沒(méi)有任何前提假定直接估計(jì)泛化誤差 的模型選擇的方法，由于沒(méi)有任何假定，可以應(yīng)用于各種 模型中，因此，具有應(yīng)用的普遍性，又由于其操作的簡(jiǎn)便 性，被人們認(rèn)為是一種行之有效的模型選擇方法。 交叉驗(yàn)證的產(chǎn)生是一個(gè)曲折的過(guò)程，首先人們發(fā)現(xiàn)同 一數(shù)據(jù)集既進(jìn)行模型訓(xùn)練又進(jìn)行泛化誤差的估計(jì)會(huì)產(chǎn)生一 個(gè)較差的結(jié)果，也就是我們常說(shuō)的訓(xùn)練誤差估計(jì)的樂(lè)觀性， 為了克服這個(gè)問(wèn)題，人們提出了交叉驗(yàn)證的方法，它的基 本思想是將數(shù)據(jù)分為兩部分，一部分?jǐn)?shù)據(jù)用來(lái)進(jìn)行模型的 訓(xùn)練，通常我們叫做訓(xùn)練集，另一部分?jǐn)?shù)據(jù)用來(lái)測(cè)試訓(xùn)練 生成模型的誤差，我們叫做測(cè)試集，這樣的泛化誤差的估 計(jì)可以更接近真實(shí)的泛化誤

2、差. 在數(shù)據(jù)足夠的情況下，我們可以很好估計(jì)出真實(shí)的泛化誤 差。但是在實(shí)際應(yīng)用中，往往只有有限的數(shù)據(jù)可用，我們必須 對(duì)數(shù)據(jù)進(jìn)行重用，對(duì)數(shù)據(jù)進(jìn)行多次切分來(lái)得到好的估計(jì)。自從 交叉驗(yàn)證提出以后，人們提出不同的數(shù)據(jù)切分方式，因此產(chǎn)生 了多種形式的交叉驗(yàn)證方法，下面我們對(duì)常用的交叉驗(yàn)證方法 做一個(gè)簡(jiǎn)單的介紹。 Hold-out：最早由Devroye和Wagner提出，主要思想是將數(shù)據(jù)集 進(jìn)行一次切分，一部分用來(lái)做訓(xùn)練模型，另一部分用來(lái)測(cè)試， 這是最簡(jiǎn)單的一種方法，也是交叉驗(yàn)證的雛形。下面我們用數(shù) 學(xué)語(yǔ)言進(jìn)行描述，通常設(shè) 為集合Dn=1,2,n的非空子集， 為其補(bǔ)集，我們用 作為訓(xùn)練集來(lái)進(jìn)行模 型訓(xùn)練，I

3、v作為測(cè)試集來(lái)進(jìn)行泛化誤差的估計(jì)，這種方法通常只 對(duì)數(shù)據(jù)進(jìn)行一次隨機(jī)切分，訓(xùn)練生成的模型用A(Dn)表示，最后 泛化誤差的估計(jì)為： 其中， 為訓(xùn)練樣本，nv為測(cè)試樣本個(gè)數(shù)，L為損失函 數(shù)。 其實(shí)嚴(yán)格意義來(lái)說(shuō)Hold-Out方法并不能算是CV,因?yàn)檫@種方法沒(méi) 有達(dá)到交叉的思想,由于是隨機(jī)的將原始數(shù)據(jù)分組,所以最后驗(yàn)證 集分類準(zhǔn)確率的高低與原始數(shù)據(jù)的分組有很大的關(guān)系,所以這種 方法得到的結(jié)果其實(shí)并不具有說(shuō)服性. I InII cv ,.,2 , 1)( I v Ii in v HO DAL n R);( 1 v Ii in D )( 留一交叉驗(yàn)證：其基本思想是每次從個(gè)數(shù)為N樣本集中取出一個(gè) 樣本作

4、為驗(yàn)證集，剩下N-1個(gè)樣本作為訓(xùn)練集，重復(fù)進(jìn)行N次，依 次取遍所有N個(gè)數(shù)據(jù)作為驗(yàn)證集，最后將平均的N個(gè)數(shù)據(jù)的結(jié)果作 為泛化誤差的估計(jì)。用數(shù)學(xué)語(yǔ)言描述為;設(shè)有樣本量N的數(shù)據(jù)集DN， 第j次取出樣本記為 ，DN（-j）表示除去樣本 后剩下的數(shù)據(jù)，最 后的泛化誤差估計(jì)定義為： 其中，L為損失函數(shù)。 留一交叉驗(yàn)證有兩個(gè)明顯的優(yōu)點(diǎn)： a.每一回合中幾乎所有的樣本皆用于訓(xùn)練模型,因此最接近原始 樣本的分布,這樣評(píng)估所得的結(jié)果比較可靠； b.實(shí)驗(yàn)過(guò)程中沒(méi)有隨機(jī)因素會(huì)影響實(shí)驗(yàn)數(shù)據(jù),確保實(shí)驗(yàn)過(guò)程是可 以被復(fù)制的。 其缺點(diǎn)是：重復(fù)次數(shù)相對(duì)來(lái)說(shuō)較大，在計(jì)算上比較耗時(shí)，所以在 計(jì)算復(fù)雜度上沒(méi)有什么優(yōu)勢(shì)。 j j N

5、j j j NNLOO DAL N DAR 1 )( );( 1 );( k折交叉驗(yàn)證（kCV）：這種方法首先是把數(shù)據(jù)集平分為k份，每 次從k份數(shù)據(jù)集中拿出一份數(shù)據(jù)集作為驗(yàn)證集，剩下的k-1份數(shù)據(jù) 集作為訓(xùn)練集，重復(fù)進(jìn)行k次，最后平均k次結(jié)果作為最后泛化誤 差的估計(jì)。用數(shù)學(xué)語(yǔ)言描述為： 設(shè)有一樣本量為n的數(shù)據(jù)集Dn，A1,Ak為數(shù)據(jù)集Dn的子集，且對(duì) 于任意子集Aj都有M（Ai）n/k， M（Ai）為子集中樣本的個(gè)數(shù)， 最后的泛化誤差估計(jì)為： 其中L為損失函數(shù)， 為除去子集Aj后剩下的樣本，s為訓(xùn)練得到 的模型。在kn的情況下，k折交叉驗(yàn)證比留一交叉驗(yàn)證要簡(jiǎn)單的 多，因此，k折交叉驗(yàn)證在實(shí)際應(yīng)

6、用中是一種人們普遍使用的模型 選擇方法。 在利用交叉驗(yàn)證進(jìn)行模型選擇時(shí)，一般選擇使得泛化誤差估計(jì)最 小的模型。 k jAi j j N j kCV j Ds L AMk R 1 )( ) );( )( 1 ( 1 )(j N D 用布利岡影響函數(shù)（BIF）對(duì)核方法 的交叉驗(yàn)證的有效近似 本文結(jié)構(gòu) 第一部分：背景介紹； 第二部分：介紹一些基本事實(shí)； 第三部分：引進(jìn)布利岡影響函數(shù)（BIF），并給出一個(gè)新方法 近似交叉驗(yàn)證誤差； 第四部分：介紹一個(gè)計(jì)算BIF和高階BIF的方法； 第五部分：如何利用這些BIF去近似交叉驗(yàn)證估計(jì)； 第六部分：實(shí)證分析我們所提出的近似交叉驗(yàn)證這個(gè)標(biāo)準(zhǔn)的性 能； 第七部分：

7、結(jié)論 摘要摘要 模型的選擇是近代核方法的研究與應(yīng)用的關(guān)鍵問(wèn)題。 交叉驗(yàn)證是被普遍采用且廣泛接受的一個(gè)模型選擇的 標(biāo)準(zhǔn)。然而，交叉驗(yàn)證要求對(duì)考慮的算法進(jìn)行多次訓(xùn) 練，這是密集的計(jì)算。這一篇文章，介紹一個(gè)新的方 法用于近似交叉驗(yàn)證，基于布利岡影響函數(shù)，其只要 求解一次算法。BIF 測(cè)量一個(gè)無(wú)窮小的污染的初始分 布的影響。我們首先建立BIF與交叉驗(yàn)證的聯(lián)系。BIF 與泰勒展開式的一次項(xiàng)有關(guān)，從而我們計(jì)算BIF和更高 階的BIF，并應(yīng)用這些理論成果去近似交叉驗(yàn)證的誤差。 試驗(yàn)結(jié)果證明，我們的近似交叉驗(yàn)證這個(gè)標(biāo)準(zhǔn)是充分 且有效的。 核方法的基本原理是：在非線性可分的情況下，使用一個(gè)非線性 變換 將輸入模

8、式空間R中的數(shù)據(jù)映射到高維特征空間F中， 即 ,在F中基于新的分類函數(shù)，達(dá)到線性可分的目的。不必 明確知道非線性變換的具體表達(dá)式，只要用核函數(shù) 代替內(nèi)積運(yùn)算即可，如下圖所示。 )(x FR ),(),(yxyxK 通常情況下，變換函數(shù) 比核函數(shù) 更為復(fù)雜， 也就是說(shuō)簡(jiǎn)單的核函數(shù)往 往對(duì)應(yīng)著“復(fù)雜”的映射。 因此，核函數(shù)的引入可以 大大降低非線性變換的計(jì) 算。常用的核方法有支撐 向量機(jī)，核聚類等。 )(x )(K 一、引言一、引言 核方法，例如支撐向量機(jī)（SVM），最小二乘支撐向量機(jī) （LSSVM）和支撐向量回歸（SVR）已在數(shù)據(jù)挖掘和機(jī)器 學(xué)習(xí)領(lǐng)域被廣泛地應(yīng)用。這些核方法的性能很大程度上依 賴

9、于一些超參數(shù)（例如核參數(shù)，正則化參數(shù)）的選擇，因 此模型選擇的問(wèn)題成為核方法的重要問(wèn)題。與此相聯(lián)系的 是學(xué)習(xí)算法的外推能力的評(píng)價(jià)問(wèn)題。事實(shí)上，我們通常選 擇使得泛化誤差最小的超參數(shù)為最理想的超參數(shù)。顯然， 泛化誤差不能被直接計(jì)算，由于產(chǎn)生數(shù)據(jù)的概率分布是未 知的，因此，有必要依靠其值的估計(jì)。這一誤差可以通過(guò) 在那些沒(méi)有用于學(xué)習(xí)的樣本上做測(cè)試或者通過(guò)理論分析的 約束來(lái)估計(jì)。 為了建立泛化誤差的上界，我們已有一些測(cè)量方法：例如， VC維，拉德馬赫復(fù)雜度(Rademacher complexity)，最大差異， 常規(guī)風(fēng)險(xiǎn)，半徑邊緣限制(radius-margin bound)，壓縮系數(shù)和 特征值攝動(dòng)

10、(eigenvalues perturbation)。 已經(jīng)有許多有趣的嘗試運(yùn)用上述約束或者其他的技術(shù)選擇超 參數(shù)，然而選擇超參數(shù)最普遍使用且廣泛接受的方法仍然是k 折交叉驗(yàn)證(KCV)和留一法交叉驗(yàn)證(LOO)。然而， KCV和 LOO要求解我們所用算法數(shù)次，這要求密集的計(jì)算。出于效 率的目的，一些人給出了對(duì)于特定算法的LOO標(biāo)準(zhǔn)的近似： 例如廣義交叉驗(yàn)證(GCV)，影響函數(shù)，廣義近似交叉驗(yàn)證 (GACV)和跨度約束(span bound)。 在這一篇文章，我們將介紹一個(gè)新方法，基于布利岡影響 函數(shù)(BIF)，近似k折交叉驗(yàn)證。我們知道，對(duì)核方法的k折交叉 驗(yàn)證的誤差的近似的有效策略還從未被

11、提出。我們建立概念BIF 和概念KCV之間的聯(lián)系，并提出一個(gè)新方法計(jì)算連續(xù)分布的BIF 和高階BIF。此外，我們?cè)跇颖痉植忌瞎烙?jì)這些BIF并利用這些 BIF得到KCV的近似。我們的方法只要求解一次算法，這可以極 大地提高效率。實(shí)驗(yàn)結(jié)果表明我們的BIF標(biāo)準(zhǔn)是一個(gè)選擇模型的 不錯(cuò)的標(biāo)準(zhǔn)。 1.1相關(guān)工作 近年來(lái)，一些研究人員研究著核方法的穩(wěn)健性。在穩(wěn)健統(tǒng)計(jì) 這一領(lǐng)域，影響函數(shù)被引入用于分析離群值對(duì)于算法的影響。 這一影響函數(shù)的定義針對(duì)在特定的地方添加一個(gè)小的概率質(zhì) 量而輕微受擾的連續(xù)分布。已有一些人證明了支撐向量機(jī) (SVMs)對(duì)于分類和回歸在對(duì)損失函數(shù)做一些假設(shè)的情況下具 有有界的影響函數(shù)。De

12、bruyne提出了一個(gè)方法通過(guò)影響函數(shù) 估計(jì)LOO。Christmann和Messem推廣了影響函數(shù)的概念，并 從布利岡導(dǎo)數(shù)引進(jìn)了一個(gè)新的概念稱為布利岡影響函數(shù)。布 利岡影響函數(shù)測(cè)量一個(gè)無(wú)窮小污染的初始分布的影響。此外， 他們證明了支撐向量機(jī)在對(duì)損失函數(shù)做一些弱假設(shè)的情況下 的BIF有界。 對(duì)于核方法，例如SVM,LSSVM和SVR，決策函數(shù)（decision fuction）的形式為 以上工作關(guān)于核方法的穩(wěn)健統(tǒng)計(jì)均忽略偏差b。然而，有時(shí)偏差 b在核方法的性能里扮演著很重要的角色。在這里，我們考慮偏 差b ，并且給出一個(gè)理論的結(jié)果計(jì)算連續(xù)分布的BIF。這一結(jié)果 通過(guò)一個(gè)更簡(jiǎn)單的證明推廣了Chr

13、istmann和Messem的結(jié)論。 Debruyne提出一個(gè)方法計(jì)算高階IF，并利用這些結(jié)果去近似 LOO。我們推廣IF的結(jié)果為BIF，并利用這些BIF的結(jié)果近似交 叉驗(yàn)證的誤差。 bxxKxf i i i ),()( 二、準(zhǔn)備工作 設(shè) 為大小為n的獨(dú)立同分布樣本集，取自一個(gè)固定 且未知在Z=XY（ )上的概率測(cè)度P。對(duì)于回歸， ； 對(duì)于分類， 。設(shè) 為一個(gè)核函數(shù)，即K是 對(duì)稱的且對(duì)任何有限點(diǎn)集 ，核矩陣 是半正定的。與核K相聯(lián)系的再生核希爾伯特空間（RKHS）H 定義為函數(shù)集 線性生成空間的完備化，其 上的內(nèi)積表示為 ，滿足 。 算子 定義為： 其中， 是一個(gè)損失函數(shù)， 是正則化參數(shù)（re

14、gularization parameter）。 n iii yxS 1 ),( d RX RY 1, 1YRXXK: Xxxx n ,., 21 m ji ji xxKK 1, ),( XxxKx: ) ,()( K ,),()(),(xxKxx K pkpkkk bfPbf , : 2 , , )(minarg K p RbHf pkpk fbxfyVEbf )(V 當(dāng)我們使用樣本分布Pn時(shí)，我們有 . 最小二乘支撐向量機(jī)（LSSVM）, -不敏感支撐向量回歸（ -SVR）和二次 -不敏感支撐向量回歸（二次 -SVR）僅僅是 損失函數(shù)的選擇上有所不同。對(duì)于LSSVM，V(r)=r2，對(duì)于

15、-SVR, ,而對(duì)于二次 -SVR， 。 除非特殊說(shuō)明，我們分別記 和 為fP和bP。 2 1 , , )( 1 minarg K i n i i RbHf pkpk fbxfyV n bf nn 0 ,max)(rrV 2 0 ,max)(rrV pk f , pk b , 三、快速近似交叉驗(yàn)證的方法 在這一節(jié)，我們介紹布利岡影響函數(shù)（BIF）和高階的BIF，并 展現(xiàn)如何利用這些BIF去近似k折交叉驗(yàn)證(KCV). 3.1布利岡影響函數(shù) 定義定義1 1：設(shè)P為一個(gè)分布,T為一個(gè)算子T:PT(P).T在P處的QP方 向上的布利岡影響函數(shù)定義為： BIF測(cè)量初始分布P在T(P)上Q方向的無(wú)窮小污

16、染的影響。 記 .我們可以看到BIF是 在 處的一階 導(dǎo)數(shù)。 )()1( lim),;( 0 PTQPT PTQBIF QPP Q )1 ( , )( ,Q PT 0 高階的BIF可以類似的定義： 定義定義2 2：設(shè)P為一個(gè)分布,T為一個(gè)算子T:PT(P).則T在P處的Q方 向上的k階布利岡影響函數(shù)定義為： 如果所有階數(shù)的BIF都存在，則可得到如下的泰勒展開式： （1） 0, | )(),;( Q k k PTPTQBIF ),;( ! )()( 1 , PTQBIF i PTPT i i i Q 3.2利用BIF近似KCV 假設(shè)樣本 被分成k個(gè)互不相交的部分 .令 為 樣本S去掉觀測(cè)Si的經(jīng)

17、驗(yàn)分布，即對(duì)于 ，我們有 否則為0。其中M為Si的大小。 對(duì)于k折交叉驗(yàn)證， 需要對(duì)每一個(gè)i進(jìn)行計(jì)算。這意味著 考慮的算法需要被計(jì)算k次，這是高強(qiáng)度的計(jì)算。 如果T的各階BIF能被計(jì)算，我們可以提供一個(gè)快速的計(jì)算方 法。 首先注意到， n iii yxS 1 ),( k ii S 1 i S n P Mn P i S n 1 i SSx )( i S n PT in S n s Mn M P Mn M P i )(1 ( 其中 對(duì)應(yīng)于樣本Si的樣本分布，即對(duì)于 ， ，否 則為0.因此，令Q= ， ， 式（1）給出 （2） 等式的右邊現(xiàn)在只依賴于樣本 和 .給出 ，則k折交叉驗(yàn)證誤差可以寫為 其

18、中 為損失函數(shù)。其只要求解一次算法。 i s M xsi 1 )( i Sx i s KKn S nQ bfTPPPP Mn M i , , ! ),;( )( , 1 j PbfsBIF Mn M bfbf nKKij j j PP PPnn i S n i S n n P i s),;( ,nKKij PbfsBIF ) ! ),;( )( ,( 1 , 1 1 p PbfsBIF Mn M bfyl n CVk nKKip p p PP k iSx j nn ij ) , ( l 注意到-M/(n-M)=-1/(k-1)，對(duì)于一些較大的p， 很小。 因此，我們采用低階的泰勒展開式的近似式

19、去近似k折交叉驗(yàn)證： 注注1 1：經(jīng)過(guò)試驗(yàn)，我們發(fā)現(xiàn)當(dāng)泰勒展開的階數(shù) 時(shí)，近似交 叉驗(yàn)證誤差的值與原始值幾乎相同。 !) 1( ) 1( pk p p ) ! ),;( )( ,( 1 , 1 1 p PbfsBIF Mn M bfyl n CVk nKKip p r p PP k iSx j nn ij 3r 四、BIF的計(jì)算 在這一節(jié)，我們首先提出一種新方法計(jì)算連續(xù)分布P的BIF和高階 BIF，然后在特殊樣本分布Pn上估計(jì)這些BIF。 4.1連續(xù)分布BIF的計(jì)算 由 的k階BIF的定義（k=1,2,),容易驗(yàn)證 令VP=V(y-fP(x)-bP),在P的一階BIF將由下面的定理給出。 KK

20、 bf , 00, |),;( , QQ P k P k KKk bfPbfQBIF 定理定理1 1：設(shè)H為一個(gè)定義在X上的有界連續(xù)核函數(shù)K的再生核希爾 伯特空間（RKHS）.此外，設(shè)P為 上的一個(gè)分布，則 在分布Q P方向上的BIF為 其中算子L:(H,R) (H,R) 定義為： 注注2 2：不含偏差項(xiàng)（即 ）的決策函數(shù)的一階BIF已經(jīng)在 （Christmann ( ),;( ),(),;( )(),;(2) 1( |,| , , , , 1 0 1 0 1 , PKKkQ PKKkP PKKkQ PKKkP P k P k VPbfQBIFE VPbfQBIFE xVPbfQBIFE xV

21、PbfQBIFELk bf QQ 2 0 ,max)(rrV 定理定理2 2的證明的證明：首先證明對(duì)所有的 有下式成立： (8)式兩邊對(duì) 求導(dǎo)可得： Nk2 )()(2 )()()()(2 )()()1 (2 22 2222 222 xVbxfE xVbxfExVbxfE xVbxfEf Q QP P 因此，對(duì)于k=2，方程（12）成立。 對(duì)（12）兩邊求導(dǎo)， 從而（12）式對(duì)k+1成立。 令 ，我們有： 0 （10）式兩邊對(duì) 求導(dǎo)，令 ，可得： 0 與上面的證明相類似，容易驗(yàn)證： 因此，我們有： 4.2 BIF在樣本分布上的計(jì)算 這一節(jié)，我們將估計(jì)樣本分布Pn上的BIF，從而得到 4.2.1

22、 最小二乘支撐向量機(jī)（LSSVM） 首先考慮取損失函數(shù)V(r）=r2.定理1中Pn上的算子L，映射任何 的（f，b） (H,R) 到 記 ，核矩陣 。 注意到 , (;,) jikkn BIFsfbP 111 222 ( , )2() ()(),()2 nnn jjjj jjj b L f bff xxxf xb nnn 1 ( (),.,() ,1(1,.,1) TT n ff xf x ,1 ( ,) n ij i j KK x x 1 11 ( , )() 1 2 1 1 1 ( , )() n n L f b x IKK f nn b L f b x n 這意味著 是有限樣本版本的Pn

23、上的算子L。 記 根據(jù)定理1，我們可以得到 11 1 2: 2 1 1 1 n n IKK nn L n , 0100 |()|,.,()| sss iii T PPPn kkk ffxfx , , 0 1 0 1 | 1 |1 sn i si i PiP n T PS fKS gf M L bg M 其中， 當(dāng) 時(shí)， ；否則為0. ,Si表示 n n矩陣，當(dāng) 時(shí)， ，否則為0. 是矩陣對(duì)應(yīng)元素的乘 積。 根據(jù)定理2，我們可以看到高階的BIF可以類似的計(jì)算。 其中， 。若 ，則 ，否則為0. 12,1, (,.,) ,( ),(,.,) , nniii TT niiPiPSSS n gg gg

24、gyfxbggg ji xS , i Sjj gg 1 (),.,() nnn T PPPn ffxfx ki xS , 1 i j k S , , 0 1 1 0, 1 11 | (1) 11 |11 si si i Pkik k n TT Pkk S k fKbKS b nM kL bbb nM ,1, (;,)( ),.,(;,)( ) , T kkikknkikknn bBIFS fbP xBIFS fbP x , ,00 (;,)()()|()| ss ii kikknjPjPj kk BIFSfbPxfxbx , ,1, , (,.,) iii T k Sk Sk S n bbb

25、ji xS , i k Sjk j bb 對(duì)于k折交叉驗(yàn)證，定義BIFMLSSVMt為k n矩陣，且 根據(jù)等式（2），截掉等式某些項(xiàng)，我們有 （3） 4.2.2 二次 -不敏感支撐向量機(jī) 由于二次 -不敏感支撐向量機(jī)，其損失函數(shù)為 因此， ， 。 , (;,)() t i jtikknj BIFMLSSVMBIFsfbPx , 1 1 ()()() ! SS ii nn nn r jPjPs i j PP s fxbfxbBIFMLSSVM s 2 0, ( ) () , r V r rr 0, ( ) 2(), r V r rr 0, ( ) 2, r Vr r 注意到 處的導(dǎo)數(shù)不存在，但實(shí)

26、際上， 的概率為0，所 以我們忽略這一概率。 類似于最小平方損失，很容易驗(yàn)證： 這是有限樣本版本的Pn上的算子L。其中B表示第i列為 的矩陣， ， 根據(jù)定理1，我們有 rr 1 21 : 1 1 n n TT IKBKB n L vv n ( ) nn iPiP Vyfxb 1 ( ,.,)T n vvv( ) nn iiPiP vVyfxb , , 0 1 0 1 | 1 |1 sn i si i PiP n T PS fKSf M L b M 其中， 若 ，則 ，否則為0. 根據(jù)定理2，高階形式可以如下計(jì)算： 其中， 。若 ，則 ，否則為0.對(duì)于k折交叉驗(yàn)證，令BIFMSVRt為k n矩

27、陣，且 根據(jù)等式（2），我們有 （4） 1,1, (,.,)( ),., nniii niiPiPSSS n Vyfxb ji xS, i Sjj , , 0 1 1 0 1 11 | (1) 11 | si si i Pkik k n TT PkSk k fKB bKB S b nM kS bv bvb nM 1 ( ,.,) ,() nn T niiPiP vvvvVyfxb ji xS , i Sjj vv , (;,)() t i jtikknj BIFMSVRBIFsfbPx , 1 11 ()()() () 1! SS ii nn nn r s jPjPs i j PP s fxb

28、fxbBIFMSVR ks 五、近似KCV標(biāo)準(zhǔn) 傳統(tǒng)的k折交叉驗(yàn)證誤差根據(jù)下式給出： 其中， 是一個(gè)恰當(dāng)?shù)膿p失函數(shù)。我們所研究的是用對(duì)于 LSSVM用式（3）中的近似式，對(duì)于二次 -SVR用式（4）中的近 似式代替k折交叉驗(yàn)證的式子。 LSSVM的近似k折交叉驗(yàn)證誤差的t次BIF標(biāo)準(zhǔn)定義為： 對(duì)于二次 -SVR， 1 1 (,() SS ii nn ji k ij PP ixS kCVl yfxb n (, )l , 11 111 (,()() ) 1! nn ji s kt t kjK PjK Ps i j ixSs BIFl yfxbBIFMLSSVM nks , 11 111 (,()(

29、) ) 1! nn ji s kt t kjK PjK Ps i j ixSs BIFl yfxbBIFMSVR nks 5.1時(shí)間復(fù)雜度分析 計(jì)算 和 ，我們需要O(n3)去計(jì)算Ln的逆，和O(kn2+tn2) 去計(jì)算BIF矩陣，其中n是訓(xùn)練集的大小，k是交叉驗(yàn)證的折數(shù)，t 是泰勒展開的次數(shù)。因此， 和 所有的時(shí)間復(fù)雜度都是 O(n3+kn2+tn2). 對(duì)于傳統(tǒng)的k折交叉驗(yàn)證方法，考慮的算法需要計(jì)算k次，因此對(duì) 于LSSVM和二次 ，時(shí)間復(fù)雜度均為O(kn3). t k BIF t k BIF t k BIF t k BIF SVR 六、實(shí)驗(yàn) 在這一節(jié)，我們將實(shí)證分析我們提出的的近似k折疊

30、交叉驗(yàn)證標(biāo)準(zhǔn) （BIF-kCV）的性能。 我們?cè)谌∽訪IBSVM上的20個(gè)數(shù)據(jù)集上做估計(jì)：10個(gè)數(shù)據(jù)集用于分 類，10個(gè)數(shù)據(jù)集用于回歸，見Table 1. 我們用 作為我們的備 選核。我們實(shí)驗(yàn)中考慮的學(xué)習(xí)算法是LSSVM。對(duì)于每個(gè)數(shù)據(jù)集， 我們跑所有方法10次，訓(xùn)練樣本和測(cè)試樣本隨機(jī)分離（樣本的50% 數(shù)據(jù)作為訓(xùn)練樣本，50%作為測(cè)試樣本）。 精確度：精確度：我們將比較BIF-kCV和傳統(tǒng)的k折交叉驗(yàn)證（kCV），有 效的留一法交叉驗(yàn)證（ELOO）和最新提出的特征值攝動(dòng)標(biāo)準(zhǔn)。 在第一次實(shí)驗(yàn)中，設(shè)泰勒展開式的次數(shù)為t=3.分類的平均測(cè)試誤差 和回歸的測(cè)試均方誤差在Table1中給出。對(duì)于每一個(gè)訓(xùn)練集，我們 通過(guò)在訓(xùn)練集上的每個(gè)標(biāo)準(zhǔn)選擇核參數(shù) 和正則化參數(shù) ，并所選 參數(shù)在測(cè)試集上計(jì)算測(cè)試誤差。 2 2 2 ( ,)exp(/ 2 ),2 ,7, 6,.,7,8 i K x xxxi Table1.在分類數(shù)據(jù)集上的平均測(cè)試誤差，泰勒展開式的次數(shù)為t=3. Table1.在回歸數(shù)據(jù)集上的平均測(cè)試誤差，泰勒展開式的次數(shù)為t=3. Table1中的結(jié)果可總結(jié)為： (a)在所有的數(shù)據(jù)集上，BIF-kCV給出與kCV幾乎一樣的測(cè)試誤差， k=5,10,20.breast,diabetes,australian,fourclass,ger