劉焱青， 王　鈺， 李濟(jì)洪*

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 山西 太原　030006； 2.山西大學(xué) 計(jì)算中心， 山西 太原　030006)

?

基于組塊3×2交叉驗(yàn)證t檢驗(yàn)的模型選擇算法

劉焱青1， 王鈺2， 李濟(jì)洪2*

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 山西 太原030006； 2.山西大學(xué) 計(jì)算中心， 山西 太原030006)

摘要：傳統(tǒng)的模型選擇問(wèn)題中,往往以所關(guān)心的性能指標(biāo)的大小來(lái)評(píng)價(jià)模型.然而,許多情形下模型性能指標(biāo)之間的差異在統(tǒng)計(jì)意義下是不顯著的,是由隨機(jī)誤差導(dǎo)致的.為此,基于組塊3×2交叉驗(yàn)證指標(biāo)差異的顯著性t檢驗(yàn)給出了一種新的模型選擇算法.模擬實(shí)驗(yàn)結(jié)果表明,在統(tǒng)計(jì)意義的最小化即平方損失(回歸)和0-1(分類)損失最小化下,該方法常常被選擇到較為簡(jiǎn)單的模型.

關(guān)鍵詞：模型選擇; 組塊3×2交叉驗(yàn)證; t檢驗(yàn); 測(cè)試誤差; 模型復(fù)雜度

0引言

統(tǒng)計(jì)機(jī)器學(xué)習(xí)的主要目的是依據(jù)訓(xùn)練數(shù)據(jù)建立預(yù)測(cè)模型, 用以描述給定數(shù)據(jù)的統(tǒng)計(jì)規(guī)律, 并通過(guò)此模型對(duì)新數(shù)據(jù)進(jìn)行預(yù)測(cè)和問(wèn)題求解. 其中, 模型的建立和選擇是關(guān)鍵. 所謂模型選擇指的是根據(jù)某種評(píng)價(jià)準(zhǔn)則, 在所有候選模型中選出使得該評(píng)價(jià)準(zhǔn)則最優(yōu)的模型.典型地,訓(xùn)練誤差的評(píng)價(jià)準(zhǔn)則是很自然的選擇, 然而,它是泛化誤差的過(guò)分樂(lè)觀估計(jì),常常導(dǎo)致較差的預(yù)測(cè)誤差.因此,在評(píng)價(jià)準(zhǔn)則中必須權(quán)衡模型的復(fù)雜度與訓(xùn)練數(shù)據(jù)的擬合優(yōu)度,如在進(jìn)行神經(jīng)網(wǎng)絡(luò)中隱節(jié)點(diǎn)數(shù)目和多項(xiàng)式擬合中多項(xiàng)式次數(shù)的選擇時(shí)，不能僅僅考慮訓(xùn)練數(shù)據(jù)中訓(xùn)練誤差最小化,還需要考慮模型的復(fù)雜度(隱節(jié)點(diǎn)數(shù)目和多項(xiàng)式次數(shù)).現(xiàn)實(shí)中,許多這樣的模型選擇方法也已經(jīng)被提出,如在傳統(tǒng)回歸分析中常用的AIC(Akaike Information Criterion),BIC(Bayesian Information Criterion),最小描述長(zhǎng)度(MDL)以及結(jié)構(gòu)風(fēng)險(xiǎn)最小化(SRM)的解析估計(jì)樣本內(nèi)預(yù)測(cè)誤差的方法[1-4].

近年來(lái), 研究者們提出多種直接估計(jì)樣本外誤差(預(yù)測(cè)誤差)的方法，如文獻(xiàn)[5,6]的自助法(Bootstrap)，文獻(xiàn)[7,8]的交叉驗(yàn)證(CV)法等.特別地,像文獻(xiàn)[1]中指出的那樣,交叉驗(yàn)證是預(yù)測(cè)誤差估計(jì)中最簡(jiǎn)單、最廣泛使用的方法,同時(shí)也得到了很多學(xué)者的廣泛關(guān)注.實(shí)際應(yīng)用中交叉驗(yàn)證也有多種形式,包括標(biāo)準(zhǔn)K折交叉驗(yàn)證,RLT(Repeated Learning Testing)交叉驗(yàn)證,MC(Monte-Carlo)交叉驗(yàn)證,5×2交叉驗(yàn)證方法等(如文獻(xiàn)[9-12]).但面對(duì)折數(shù)的選擇、計(jì)算復(fù)雜度和數(shù)據(jù)集切分等問(wèn)題,這些交叉驗(yàn)證方法都存在著令人不滿意的地方,文獻(xiàn)[13]在綜合分析已有交叉驗(yàn)證研究成果的基礎(chǔ)上提出組塊3×2交叉驗(yàn)證,并在自然語(yǔ)言處理的實(shí)際應(yīng)用中驗(yàn)證了此方法優(yōu)于常用的K折交叉驗(yàn)證.文獻(xiàn)[14]也通過(guò)實(shí)驗(yàn)驗(yàn)證了此方法應(yīng)用于算法性能對(duì)照檢驗(yàn)中的優(yōu)良性質(zhì),為此本文考慮把它應(yīng)用于模型選擇.

同時(shí)我們注意到,無(wú)論是上面提到的哪種模型選擇方法都存在這樣的一個(gè)問(wèn)題,在某種評(píng)價(jià)準(zhǔn)則下,一個(gè)具有較高復(fù)雜度的模型是最優(yōu)的,而一個(gè)較簡(jiǎn)單模型是次優(yōu)的,但實(shí)際上它們之間的差異可能是隨機(jī)誤差造成的,在統(tǒng)計(jì)上不顯著,此時(shí)選擇簡(jiǎn)單模型可能更合適.為此,本文把統(tǒng)計(jì)顯著性檢驗(yàn)應(yīng)用于模型選擇,給出了基于組塊3×2交叉驗(yàn)證t檢驗(yàn)的模型選擇算法,并通過(guò)基于回歸和分類的模擬實(shí)驗(yàn)進(jìn)行了驗(yàn)證.

1基于組塊3×2交叉驗(yàn)證t檢驗(yàn)的模型選擇算法

1.1組塊3×2交叉驗(yàn)證

所謂組塊3×2交叉驗(yàn)證指的是首先將數(shù)據(jù)集D隨機(jī)地劃分為4等份(P1,P2,P3,P4),然后任取兩份訓(xùn)練,兩份測(cè)試進(jìn)行2折交叉驗(yàn)證,其中D={z1,z2,…,zn},zi∈Z是從某個(gè)未知分布P中獨(dú)立抽樣得到,zi=(xi,yi),xi為輸入向量,yi為輸出變量.具體如表1所示.

表1　組塊3×2交叉驗(yàn)證

傳統(tǒng)的基于交叉驗(yàn)證的模型選擇就是要選擇使得下式達(dá)到最小的模型A：

1.2基于組塊3×2交叉驗(yàn)證t檢驗(yàn)的模型選擇算法

具體地,假定有m個(gè)備選模型A1,A2,…,Am,復(fù)雜度依次為h1,h2,…,hm,且不妨假設(shè)隨著備選模型中下標(biāo)增加, 模型的復(fù)雜度也相應(yīng)增加(即h1≤h2≤…≤hm).記Cm為m維計(jì)數(shù)數(shù)組,用來(lái)統(tǒng)計(jì)重復(fù)實(shí)驗(yàn)中各備選模型A1,A2,…,Am作為最優(yōu)模型的次數(shù).

基于組塊3×2交叉驗(yàn)證t檢驗(yàn)的模型選擇算法1.計(jì)數(shù)初值置為0,即cp=0(p=1,2,…,m);2.forp=1,2,…,(m-1) forq=(p+1),…,m a.計(jì)算用于模型Ap和Aq之間差異對(duì)照的檢驗(yàn)統(tǒng)計(jì)量(見(jiàn)文獻(xiàn)[14]) tpq=^μ3×2(Ap,Aq)16∑3i=1∑3k=1(^μ(i)k(Ap,Aq)-^μ3×2(Ap,Aq))2

其中^μ(i)k(Ap,Aq)=2n∑zj∈T(i)k(L(Ap(D(i)k),zj)-L(Aq(D(i)k),zj) b.iftpq>t1-α(5),且^μ3×2(Ap)>^μ3×2(Aq),則選擇復(fù)雜度為hq的模型Aq,即cq=cq+1; else復(fù)雜度為hp的模型Ap和復(fù)雜度為hq的模型Aq沒(méi)有顯著差異,選擇具有較低復(fù)雜度hp的模型Ap,即cp=cp+1;3.挑選出備選模型被選到的次數(shù)最多的模型Ak作為最優(yōu)模型,其中k=argmaxpc(p)(p=1,2,…,m);如果它們中次數(shù)有相同的,則選擇復(fù)雜度較低的模型作為最優(yōu)模型.

2模擬實(shí)驗(yàn)

本節(jié)中我們分別在多項(xiàng)式回歸和分類情形下對(duì)傳統(tǒng)的模型選擇方法(AIC,BIC,5折交叉驗(yàn)證, 組塊3×2交叉驗(yàn)證)和本文提出的組塊3×2交叉驗(yàn)證t檢驗(yàn)方法進(jìn)行了對(duì)照.首先描述了實(shí)驗(yàn)的設(shè)置,接著給出了實(shí)驗(yàn)對(duì)照結(jié)果.

2.1實(shí)驗(yàn)設(shè)置

2.1.1回歸

2.1.2分類

在多項(xiàng)式分類中，xt(t=1,…,N)由[-1,1]上的均勻分布生成，rt(t=1,…,N)通過(guò)比較后驗(yàn)概率

的大小得到, 其中C0表示0類,C1表示1類.若P(C0|x)>P(C1|x),則rt取值為0,否則為1.類條件密度P(x|Ci),i=0,1通過(guò)

P(x|C0)=0.5N(-0.58,0.17)+0.5N(0.32,0.13)

P(x|C1)=0.6N(-0.10,0.15)+0.4N(0.65,0.09)

2.2實(shí)驗(yàn)結(jié)果和分析

這一小節(jié)中, 我們給出了五個(gè)模型選擇方法(AIC,BIC,5折交叉驗(yàn)證(5CV),組塊3×2交叉驗(yàn)證(32CV), 組塊3×2交叉驗(yàn)證t檢驗(yàn)(32CVt))的實(shí)驗(yàn)對(duì)照.考慮兩個(gè)評(píng)價(jià)準(zhǔn)則:最優(yōu)模型的復(fù)雜度和測(cè)試集上最優(yōu)模型的測(cè)試誤差.為了使得對(duì)照更有效,相同的訓(xùn)練和測(cè)試樣本用于所有的模型選擇方法.通過(guò)1 000次重復(fù)實(shí)驗(yàn)來(lái)進(jìn)行模型的選擇.

2.2.1回歸結(jié)果

圖1～2給出了五種方法在兩種樣本量下1 000次重復(fù)實(shí)驗(yàn)中各階多項(xiàng)式作為最優(yōu)模型的次數(shù).對(duì)中樣本來(lái)說(shuō),AIC,BIC,5折交叉驗(yàn)證和組塊3×2交叉驗(yàn)證方法選擇5階多項(xiàng)式作為最優(yōu)模型,而本文給出的組塊3×2交叉驗(yàn)證t檢驗(yàn)方法選擇4階多項(xiàng)式作為最優(yōu)模型.大樣本下,AIC,BIC,組塊3×2交叉驗(yàn)證方法選擇6階多項(xiàng)式作為最優(yōu)模型,5折交叉驗(yàn)證選擇7階多項(xiàng)式作為最優(yōu)模型,而本文方法選擇的是5階多項(xiàng)式.前四種方法在中樣本下結(jié)果一致,在大樣本下5折交叉驗(yàn)證選擇更復(fù)雜的模型,而基于t檢驗(yàn)的方法選擇更簡(jiǎn)單的模型,因?yàn)槿绻粋€(gè)簡(jiǎn)單模型不是比復(fù)雜模型統(tǒng)計(jì)意義下顯著差的話,則傾向于選擇簡(jiǎn)單模型.

圖1　回歸情形中樣本的模型選擇方法對(duì)照

圖2　回歸情形大樣本的模型選擇方法對(duì)照

用于模型選擇方法對(duì)照的第二個(gè)準(zhǔn)則是測(cè)試集上的測(cè)試誤差,如表2所示.中樣本下,AIC,BIC,5折交叉驗(yàn)證和組塊3×2交叉驗(yàn)證四種方法具有相似的錯(cuò)誤率和標(biāo)準(zhǔn)差(四種方法的錯(cuò)誤率在后面的小數(shù)位上是有差異的),都比本文方法得出的要小,但是它們之間的差異是不顯著的.隨著樣本量從中樣本變?yōu)榇髽颖?我們方法的錯(cuò)誤率雖然還是最大的,但五種方法的結(jié)果變得更加相似.

表2　最優(yōu)模型在測(cè)試集上的誤差及其標(biāo)準(zhǔn)差

2.2.2分類結(jié)果

圖3～4給出了分類情形五種方法在兩種樣本量下1 000次重復(fù)實(shí)驗(yàn)中各階多項(xiàng)式作為最優(yōu)模型的次數(shù).中樣本中,AIC,BIC,5折交叉驗(yàn)證和本文方法選擇了3階多項(xiàng)式作為最優(yōu)模型,而組塊3×2交叉驗(yàn)證選擇的是5階多項(xiàng)式.然而,5折和組塊3×2交叉驗(yàn)證選擇的波動(dòng)比較大,比如組塊3×2交叉驗(yàn)證選擇的3,4,5,6,7階多項(xiàng)式的次數(shù)均在150次左右.AIC,BIC和本文方法在1 000次重復(fù)中有950次以上選的是3階多項(xiàng)式, 波動(dòng)很小.

在大樣本下,AIC方法選擇的是5階多項(xiàng)式,BIC和本文方法選擇的是3階多項(xiàng)式,這是因?yàn)锽IC比AIC懲罰復(fù)雜模型更多,尤其是在大樣本量下要遠(yuǎn)大于2.而5折和組塊3×2交叉驗(yàn)證選擇的是更復(fù)雜的6階多項(xiàng)式來(lái)作為最優(yōu)模型,且它們波動(dòng)同樣比較大.

圖3　分類情形中樣本的模型選擇方法對(duì)照

圖4　分類情形大樣本的模型選擇方法對(duì)照

表3給出了分類情形下兩種測(cè)試樣本集上五種方法的測(cè)試錯(cuò)誤率和標(biāo)準(zhǔn)差.和回歸情形類似,雖然本文提出的方法有較大的錯(cuò)誤率,但是它和AIC,BIC,組塊3×2交叉驗(yàn)證方法的差異是不顯著的.5折交叉驗(yàn)證具有出奇高的錯(cuò)誤率,這是因?yàn)殡m然5折交叉驗(yàn)證中選的最優(yōu)模型是6階多項(xiàng)式,但實(shí)際上在1 000次重復(fù)中選到3～8階多項(xiàng)式的次數(shù)都非常接近,所以也很容易犯錯(cuò).

表3　最優(yōu)模型在測(cè)試集上的

綜上所述,組塊3×2交叉驗(yàn)證t檢驗(yàn)方法與其它方法相比較,測(cè)試誤差的差異在統(tǒng)計(jì)意義下不顯著,且該方法選擇更簡(jiǎn)單的模型,這種選擇更符合實(shí)際應(yīng)用.

3結(jié)論

本文主要分析了組塊3×2交叉驗(yàn)證t檢驗(yàn)方法在回歸和分類的模型選擇任務(wù)中的性能,從選擇的最優(yōu)模型復(fù)雜度和測(cè)試集上最優(yōu)模型的測(cè)試誤差等兩方面分析,本文所述方法具有較好的性能.

然而,在其它應(yīng)用領(lǐng)域如密度估計(jì)和高維度的生物數(shù)據(jù)問(wèn)題中,組塊3×2交叉驗(yàn)證t檢驗(yàn)方法是否也具有優(yōu)良的性能? 另外,能否構(gòu)造出組塊m×2交叉驗(yàn)證方法和組塊m×2交叉驗(yàn)證t檢驗(yàn)方法,并將其用于分類和回歸的模型選擇任務(wù)? 上述這些問(wèn)題，還值得我們?cè)诮窈筮M(jìn)一步去研究.

參考文獻(xiàn)

[1] Wasseman L.Bayesian model selection and model averaging[J].Journal of Mathematical Psychology,2000,44:92-107.

[2] Hastie T,Tibshrani R,Friedman J.The elements of statistical learning:data mining,inference,and prediction[M].2nd edition.New York:Springer,2009.

[3] Spiegelhalter D J,Bes N G,Carlin B P,et al.Bayesian measures of model complexity and fit[J].Statistical Methodology,2002,64(4):583-639.

[4] Kadane J B,Lazar N A.Methods and criteria for model selection[J].Journal of the American Statistical Association,2004,99(465):279-290.

[5] Fronmont M.Model selection by bootstrap penalization for classification[J].Journal of Machine Learning,2007,66(2-3):165-207.

[6] Breiman L.The little bootstrap and other methods for dimensionality selection in regression:X-fixed prediction error[J].Journal of the American Statistical Association,1992,87:738-754.

[7] 李根,鄒國(guó)華,張新雨.高維模型選擇方法綜述[J].數(shù)理統(tǒng)計(jì)與管理,2012,31(4):640-658.

[8] Houwelingen H C,Sauerbrei W.Cross-validation,shrinkage and variable selection in liner regression revisited[J].Open Journal of Statistics,2013,3:79-102.

[9] Bengio Y,Grandvalet Y.No unbiased estimator of variance of K-fold cross validation[J].Journal of Machine Learning,2004,5:1 089-1 105.

[10] Arlot S,Celisse A.A survey of cross-validation procedures for model selection[J].Statistics Surveys,2010,4:40-79.

[11] Nadeau C,Bengio Y.Inference for the generalization error[J].Machine Learning,2003,52(3):239-281.

[12] Yildiz O T.Omnivariate rule induction using a novel pairwise statistical test[J].IEEE Transactions on Knowledge and Data Engineering,2013,25:2 105-2 118.

[13] 李濟(jì)洪,王瑞波,王蔚林,等.漢語(yǔ)框架語(yǔ)義角色的自動(dòng)標(biāo)注研究[J].軟件學(xué)報(bào),2010,30(4):597-611.

[14] Wang Yu,Wang Ruibo,Jia Huichen.Blocked 3×2 cross-validated t-test for comparing supervised classification learning algorithms[J].Neural Computation,2014,26(1):208-235.

[15] Yilidiz O T.Tuning model complexity using cross-validation for supervised learning[D].Turkey:Bagazici University,2005.

Model selection algorithm based on blocked 3×2 cross-validatedt-test

LIU Yan-qing1， WANG Yu2， LI Ji-hong2*

(1.College of Mathematical Sciences, Shanxi University, Taiyuan 030006, China ；2.Computer Center, Shanxi University, Taiyuan 030006, China)

Abstract:In traditional model selection problem,the evaluation of the model is always based on the performance indexes. However,in many cases,the difference of the performance indexes of the models may not be statistically significant,which may result from random error.Therefore,a new model selection algorithm is proposed based on blocked 3×2 cross-validated significance t-test for the difference of the indexes.Experiment results show that the algorithm always select the simple models based on the minimization of square loss (regression) or 0-1 loss (classification).

Key words:model selection； blocked 3×2 cross-validation； t-test； test error； model complexity

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1000-5811(2015)01-0179-05

通訊作者:李濟(jì)洪(1964-), 男, 山西長(zhǎng)治人, 教授, 博士生導(dǎo)師，研究方向:統(tǒng)計(jì)機(jī)器學(xué)習(xí)及統(tǒng)計(jì)自然語(yǔ)言處理,lijh@sxu.edu.cn

作者簡(jiǎn)介:劉焱青(1988-), 女, 山西忻州人, 在讀碩士研究生, 研究方向: 統(tǒng)計(jì)機(jī)器學(xué)習(xí)

基金項(xiàng)目：山西省科技廳科技基礎(chǔ)條件平臺(tái)建設(shè)項(xiàng)目(20130910030101)