基于均衡7×2交叉驗(yàn)證的模型選擇方法

杜偉杰 王瑞波 李濟(jì)洪

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

0 引言

模型選擇是統(tǒng)計(jì)機(jī)器學(xué)習(xí)中的重要研究領(lǐng)域.模型選擇的主要目標(biāo)就是選擇到真模型.在傳統(tǒng)的回歸問(wèn)題中，通常使用留一交叉驗(yàn)證（LOO，Leave－one－out Cross－validation）方法來(lái)進(jìn)行模型泛化誤差的估計(jì)，并且早期的一些工作也已證明留一交叉驗(yàn)證估計(jì)是漸進(jìn)無(wú)偏的[1].但是，基于留一交叉驗(yàn)證方法卻不具有模型選擇的一致性[2].為此，Shao[2]的工作指出，當(dāng)且n1→∞（n1，n2為訓(xùn)練集及測(cè)試集容量，n為樣本總?cè)萘浚r(shí)，交叉驗(yàn)證方法才會(huì)保證模型選擇的一致性.在此基礎(chǔ)上，他提出了基于均衡不完全組塊的交叉驗(yàn)證方法（BICV，Balanced Incomplete Cross－validation）.不過(guò)，并未給出滿足上述條件的BICV的構(gòu)造方法.

對(duì)于分類問(wèn)題，Yang[3]研究了分類器選擇的一致性問(wèn)題.他指出，由于分類模型的性能收斂速率與回歸模型的性能收斂速率完全不同，因此，分類器選擇的一致性并不需要滿足Shao[2]提出的條件.他給出了分類器選擇的一致性的充分條件，并特別指出當(dāng)高維分類數(shù)據(jù)中相應(yīng)收斂率滿足一定條件時(shí)，標(biāo)準(zhǔn)2折交叉驗(yàn)證方法是具有分類器選擇的一致性的.

標(biāo)準(zhǔn)2折交叉驗(yàn)證雖然計(jì)算量較小，但受到樣本劃分的影響較大.對(duì)于樣本容量為n的數(shù)據(jù)集，總共可以得到個(gè)不同的2折交叉驗(yàn)證劃分.而標(biāo)準(zhǔn)2折交叉驗(yàn)證只隨機(jī)地取其中一次.為了彌補(bǔ)這個(gè)缺陷，一些研究者提出使用多次重復(fù)結(jié)果的平均值來(lái)提高性能，并構(gòu)造出m組2折交叉驗(yàn)證方法.本文稱之為隨機(jī)m×2交叉驗(yàn)證（R m×2CV），也有文獻(xiàn)稱之為多次對(duì)折分割方法（RHS，Repeated Half Splitting）[4].

Smyth[5]提出使用MCCV的方法來(lái)選取混合模型中的份數(shù)K.他的試驗(yàn)結(jié)果表明，MCCV中設(shè)置時(shí)可以得到較好的結(jié)果.他的這種設(shè)置可以看作是隨機(jī)m×2交叉驗(yàn)證中的一種簡(jiǎn)單的變形.另外，Nason[6]，Celeux[7]等的模擬結(jié)果均表明在某些情況下，使用隨機(jī)m×2交叉驗(yàn)證方法可以得到模型參數(shù)的最優(yōu)估計(jì)值.

在檢驗(yàn)問(wèn)題中，Dietterich[8]針對(duì)兩個(gè)分類模型性能差異的檢驗(yàn)問(wèn)題，提出了5×2交叉驗(yàn)證t檢驗(yàn).他的模擬實(shí)驗(yàn)結(jié)果證明，5×2交叉驗(yàn)證t檢驗(yàn)比一些其他的檢驗(yàn)具有更優(yōu)的勢(shì).Alpaydn[9]對(duì)Dietterich[8]的檢驗(yàn)方法進(jìn)行了改進(jìn)，提出了5×2交叉驗(yàn)證F檢驗(yàn).

盡管隨機(jī)m×2交叉驗(yàn)證方法使用了多次獨(dú)立的重復(fù)劃分來(lái)減小標(biāo)準(zhǔn)2折交叉驗(yàn)證估計(jì)的波動(dòng)，但由于多次重復(fù)都是針對(duì)同一數(shù)據(jù)集進(jìn)行的，這導(dǎo)致不同切分的訓(xùn)練集之間存在共同樣本.因此，m次獨(dú)立的2折交叉驗(yàn)證之間的結(jié)果并不完全獨(dú)立.m次標(biāo)準(zhǔn)2折交叉驗(yàn)證的平均結(jié)果與各次劃分后訓(xùn)練集和測(cè)試集的共同樣本有關(guān)，共同樣本個(gè)數(shù)會(huì)影響最終m×2交叉驗(yàn)證估計(jì)的方差.因此，本文針對(duì)m＝7的情形，提出了一種均衡的7×2交叉驗(yàn)證方法，它使得2次獨(dú)立劃分后訓(xùn)練集和測(cè)試集之間的共同樣本個(gè)數(shù)相同（稱此為均衡性），并給出了均衡7×2交叉驗(yàn)證的構(gòu)造方法.

本文的主要目的在于考察分類問(wèn)題中均衡7×2交叉驗(yàn)證對(duì)最優(yōu)模型選擇的性能.為此，本文將其與常用的標(biāo)準(zhǔn)5折交叉驗(yàn)證、標(biāo)準(zhǔn)10折交叉驗(yàn)證以及最近提出的組塊3×2交叉驗(yàn)證方法進(jìn)行對(duì)比.模擬實(shí)驗(yàn)結(jié)果表明，本文提出的均衡7×2交叉驗(yàn)證方法比其余的三種交叉驗(yàn)證方法具有更高的選到真模型的概率.

1 模型選擇的交叉驗(yàn)證方法

交叉驗(yàn)證方法（如5折、10折交叉驗(yàn)證）常用于模型選擇任務(wù)中.但不同的交叉驗(yàn)證方法在選到真模型的概率上會(huì)有差異.本節(jié)將介紹兩種基于交叉驗(yàn)證策略的模型選擇方法.

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

組塊3×2交叉驗(yàn)證方法由李濟(jì)洪等[10]提出，主要的思想是使用3次重復(fù)的2折交叉驗(yàn)證來(lái)進(jìn)行泛化誤差的估計(jì)，但與隨機(jī)3×2交叉驗(yàn)證不同，他將均衡設(shè)計(jì)的思想融合到重復(fù)實(shí)驗(yàn)的構(gòu)造中，提高了2折交叉驗(yàn)證估計(jì)的精度.組塊3×2交叉驗(yàn)證具體的構(gòu)造方法是首先將數(shù)據(jù)集隨機(jī)分成4份，不失一般性，可將其設(shè)為（1）、（2）、（3）、（4），使用其中任意2份作為訓(xùn)練集，其余2份作為測(cè)試集，這樣便可做3組2折交叉驗(yàn)證，見(jiàn)表1所示的3組實(shí)驗(yàn).

表1 組塊3×2交叉驗(yàn)證實(shí)驗(yàn)設(shè)置

記表示第i組中第k折交叉驗(yàn)證得到的泛化誤差.表示第i組中2折交叉驗(yàn)證的泛化誤差的均值，即.這樣，可以得到組塊3×2交叉驗(yàn)證泛化誤差的估計(jì)如下:

組塊3×2交叉驗(yàn)證方法中，不同組的任意兩份之間的樣本交叉?zhèn)€數(shù)均為n／4.與隨機(jī)3×2交叉驗(yàn)證中不同組之間任意兩份交叉?zhèn)€數(shù)不相等且隨機(jī)變化的情況不同.組塊3×2交叉驗(yàn)證體現(xiàn)了試驗(yàn)中均衡設(shè)計(jì)的思想.

1.2 均衡7×2交叉驗(yàn)證

沿用組塊3×2交叉驗(yàn)證的思想，我們這里考慮將數(shù)據(jù)集切分為8份，提出均衡7×2交叉驗(yàn)證，即針對(duì)標(biāo)準(zhǔn)2折交叉驗(yàn)證構(gòu)造7次不同的重復(fù)，每2次重復(fù)之間要保證樣本的交叉?zhèn)€數(shù)為.但如何將這8份數(shù)據(jù)組合來(lái)滿足均衡設(shè)計(jì)交叉驗(yàn)證的要求，這里與組塊3×2交叉驗(yàn)證不同，因?yàn)橹挥?組實(shí)驗(yàn)滿足均衡設(shè)計(jì)的思想，這里不再是C48的完全組合.為了快速找到滿足組塊7×2交叉驗(yàn)證的7組實(shí)驗(yàn)，我們提出了正交表選擇法.我們選取L8（27）正交表見(jiàn)表2.但與一般正交表使用方法不同的是，正交表中的7列代表了7組2折交叉驗(yàn)證試驗(yàn)，其中每列里“＋”代表這份數(shù)據(jù)屬于訓(xùn)練集，“－”代表這份數(shù)據(jù)屬于測(cè)試集.具體的構(gòu)造方法如下，首先把數(shù)據(jù)集平均分為8份，不失一般性可設(shè)為（1），（2），…，（8），然后按照上述方法得到表3所示的7個(gè)分組，將8份數(shù)據(jù)集組合形成7組不同的標(biāo)準(zhǔn)2折交叉驗(yàn)證.

表2 L8（27）正交表

表3 組塊7塊2交叉驗(yàn)證實(shí)驗(yàn)設(shè)置

根據(jù)表2所示的構(gòu)造方法，可以得到均衡7×2交叉驗(yàn)證泛化誤差的估計(jì)如下:

從構(gòu)造均衡7×2交叉驗(yàn)證的方式來(lái)看，對(duì)于不同組的數(shù)據(jù)集之間重疊的樣本數(shù)相同，均為n／4.Nadeau和Bengio[11]證明了對(duì)于任意兩次獨(dú)立的劃分，兩個(gè)訓(xùn)練集中相同的樣本個(gè)數(shù)是一個(gè)隨機(jī)變量且服從期望為n／4的超幾何分布.我們提出的均衡7×2交叉驗(yàn)證方法正好滿足n／4這個(gè)理想值，這就是均衡設(shè)計(jì)的思想.直觀上這種設(shè)計(jì)可能會(huì)得到較小的方差，從而得到性質(zhì)更優(yōu)良的交叉驗(yàn)證估計(jì).以下通過(guò)模擬來(lái)比較幾種交叉驗(yàn)證的方差.

參照文獻(xiàn)[3]模擬試驗(yàn)的設(shè)置，產(chǎn)生500個(gè)樣本，重復(fù)100 000次模擬試驗(yàn)得到分類回歸樹(shù)（CART）模型下泛化誤差的4種交叉驗(yàn)證估計(jì)的真實(shí)方差.由表4的試驗(yàn)結(jié)果可以看出均衡7×2交叉驗(yàn)證的真實(shí)方差明顯小于標(biāo)準(zhǔn)5折、10折交叉驗(yàn)證.另外，相對(duì)于組塊3×2交叉驗(yàn)證來(lái)說(shuō)，由于重復(fù)次數(shù)增多，均衡7×2交叉驗(yàn)證可以有效地降低估計(jì)的方差，因而在模型選擇中可能會(huì)有較好的結(jié)果.

表4 幾種交叉驗(yàn)證方差的模擬比較

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

本節(jié)以分類回歸樹(shù)（CART）為分類模型，通過(guò)各種模擬來(lái)比較5折交叉驗(yàn)證、10折交叉驗(yàn)證、組塊3×2交叉驗(yàn)證和均衡7×2交叉驗(yàn)證在模型選擇中的表現(xiàn).特別地，考慮到均衡7×2交叉驗(yàn)證的計(jì)算量大于標(biāo)準(zhǔn)10折交叉驗(yàn)證，為了比較在相同計(jì)算量下均衡設(shè)計(jì)的交叉驗(yàn)證與標(biāo)準(zhǔn)交叉驗(yàn)證之間的模型選擇性能的好壞，我們從均衡7×2交叉驗(yàn)證的7組試驗(yàn)中隨機(jī)抽取5組，構(gòu)成均衡5×2交叉驗(yàn)證，并通過(guò)模擬試驗(yàn)與其他幾種交叉驗(yàn)證在模型選擇中的表現(xiàn)進(jìn)行了對(duì)比.

2.1 模擬試驗(yàn)的設(shè)置

考慮一個(gè)兩類分類問(wèn)題，設(shè)模擬數(shù)據(jù)為Z＝（X，Y），其中Y～b（1，p），實(shí)驗(yàn)假定共有10個(gè)特征，自變量系數(shù)取值非0的特征組成了真模型，為了減少試驗(yàn)復(fù)雜度，不失一般性，假設(shè)前5個(gè)特征的系數(shù)非0，即β＝（β1，β2.β3，β4，β5，0，0，0，0，0，），其中p由 Logistic模型產(chǎn)生:

對(duì)于β中的非0項(xiàng)，借鑒了文獻(xiàn)[7]模擬試驗(yàn)中的設(shè)置，即從（－1）u（α＋｜2｜）中隨機(jī)產(chǎn)生，其中α＝.通過(guò)這樣的數(shù)據(jù)設(shè)置既可以保證真模型中的特征對(duì)響應(yīng)變量的影響是顯著的，又可以使產(chǎn)生的模型有比較合適的信噪比.由于α是由N決定的，因此當(dāng)給定N的時(shí)候，便可以為真模型產(chǎn)生一組系數(shù)值，并將其固定.本文共選擇了包含真模型在內(nèi)的6個(gè)模型作為候選模型，分別為s0:前5個(gè)特征（即真模型）；s1:前6個(gè)特征；s2:前7個(gè)特征；s3:前8個(gè)特征；s4:前9個(gè)特征；s5:前10個(gè)特征.

產(chǎn)生模擬數(shù)據(jù)時(shí)，假定10個(gè)特征獨(dú)立且都服從標(biāo)準(zhǔn)高斯分布N（0，1），隨機(jī)產(chǎn)生N個(gè)獨(dú)立同分布的樣本，則可以得到一個(gè)N×10的特征矩陣X，將X帶入真模型s0中，得到相應(yīng)的Y值.以Z為觀測(cè)數(shù)據(jù)，分別計(jì)算6個(gè)候選模型在5種不同的交叉驗(yàn)證策略下得到的泛化誤差的估計(jì)值，以最小的泛化誤差的估計(jì)值為目標(biāo)得到每種交叉驗(yàn)證策略所選出的最優(yōu)模型.重復(fù)試驗(yàn)1 000次，計(jì)算每種交叉驗(yàn)證下選到真模型的頻次，并以此來(lái)比較不同的交叉驗(yàn)證模型選擇方法性能的優(yōu)劣.這里應(yīng)當(dāng)注意，每個(gè)候選模型所對(duì)應(yīng)的特征矩陣是不同的，如s3只含有前8個(gè)特征，其特征矩陣應(yīng)為X的前8列.依照上述實(shí)驗(yàn)設(shè)置，樣本量N分別取值為500，1 000，1 500，2 000，得到4組實(shí)驗(yàn)結(jié)果，見(jiàn)表5.

從表5的試驗(yàn)結(jié)果可以得到如下結(jié)論:

1）在4種交叉驗(yàn)證方法中，均衡7×2交叉驗(yàn)證模選到真模型的概率明顯高于其余3種交叉驗(yàn)證.這說(shuō)明本文提出的均衡7×2交叉驗(yàn)證方法更適用于進(jìn)行模型選擇.

表5 試驗(yàn)結(jié)果

2）通過(guò)選取不同樣本量的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)樣本容量減小時(shí)，5種交叉驗(yàn)證模型選擇性能均有所提高，而且均衡7×2交叉驗(yàn)證模型選擇性能更加突出.所以在樣本容量較小時(shí)我們提出均衡7×2交叉驗(yàn)證模型選擇方法更加有效.但隨著樣本量的增加，幾種交叉驗(yàn)證策略之間的差異逐漸減小.

3）通過(guò)均衡5×2交叉驗(yàn)證和標(biāo)準(zhǔn)10折交叉驗(yàn)證之間的比較來(lái)看，兩者計(jì)算量基本相同，但是在小樣本的情況下，我們提出的帶有均衡設(shè)計(jì)的交叉驗(yàn)證選到真模型的概率更大，在模型選擇中的表現(xiàn)更好.另外，均衡5×2交叉驗(yàn)證比均衡7×2交叉驗(yàn)證選到真模型的概率小，那么在計(jì)算能力允許的前提下，采用均衡7×2交叉驗(yàn)證進(jìn)行模型選擇會(huì)獲得更好的結(jié)果.

3 總結(jié)和展望

本文通過(guò)模擬實(shí)驗(yàn)證明了均衡7×2交叉驗(yàn)證在小樣本分類問(wèn)題下，模型選擇的性能高于組塊3×2交叉驗(yàn)證和標(biāo)準(zhǔn)5折、10折交叉驗(yàn)證.下一步，我們可以將組塊7×2交叉驗(yàn)證模型選擇方法進(jìn)一步推廣至高維數(shù)據(jù)下，驗(yàn)證其是否在高維數(shù)據(jù)模型選擇任務(wù)中仍然具有更好的性能，同時(shí)可以進(jìn)一步驗(yàn)證在高維情形下是否可以具有模型選擇的一致性.另外，本文通過(guò)對(duì)組塊3×2交叉驗(yàn)證的推廣提出了均衡7×2交叉驗(yàn)證，下一步將提出一種均衡m×2交叉驗(yàn)證的構(gòu)造方法，驗(yàn)證其在模型選擇方面是否會(huì)得到了更好的性能.我們推測(cè)，隨著m的增大，這種組塊m×2交叉驗(yàn)證會(huì)具有更好的性能.在未來(lái)的研究中可以在這些方面做進(jìn)一步工作.

[1]Li Ker Chau.Asymptotic optimality for Cp，CL，cross－validation and generalized cross－validation:discrete index set[J].Ann.Statist.，1987，15（3）:958－975

[2]Shao Jun.Linear model selection by cross－validation[J].Amer.Statist.Assoc.，1993，88（422）:486－494

[3]Yang Yuhong.Comparing learning method for classification[J].Statist.Sinica.，2006，16（2）:635－657

[4]Hafidi B，Mkhadri A.Repeated half sampling criterion for model selection[J].The Indian Journal of Statistics，2004，66（3）:566－581

[5]Smyth P.Clustering using monte－carlo cross－validation[C].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining.USA:AAAI Press，1996:126－133

[6]Nason G P.Wavelet shrinkage using cross－validation[J].JRSS，1996，58（2）:463－479

[7]Celeux G，Durand JB.Selecting hidden markov model state number with cross－validation likelihood[J].Comput Stat，2008，23（4）:541－564

[8]Dietterich T G.Approximate statistical tests for comparing supervised classification learning algorithms[J].Neur.Comp.，1998，10（7）:1 895－1 924

[9]Alpaydin E.Combined 5×2CVFtest for comparing supervised classification learing algorithms[J].Neur.Comp.，1999，11（8）:1 885－1 892

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

[11]Nadeau C，Bengio Y.Inference for the generalization error[J].Machine Learning，2003，52（3）:39－281