杜偉杰 王瑞波 李濟洪

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

0 引言

模型選擇是統(tǒng)計機器學習中的重要研究領域.模型選擇的主要目標就是選擇到真模型.在傳統(tǒng)的回歸問題中，通常使用留一交叉驗證（LOO，Leave－one－out Cross－validation）方法來進行模型泛化誤差的估計，并且早期的一些工作也已證明留一交叉驗證估計是漸進無偏的[1].但是，基于留一交叉驗證方法卻不具有模型選擇的一致性[2].為此，Shao[2]的工作指出，當且n1→∞（n1，n2為訓練集及測試集容量，n為樣本總容量）時，交叉驗證方法才會保證模型選擇的一致性.在此基礎上，他提出了基于均衡不完全組塊的交叉驗證方法（BICV，Balanced Incomplete Cross－validation）.不過，并未給出滿足上述條件的BICV的構造方法.

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

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

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

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

盡管隨機m×2交叉驗證方法使用了多次獨立的重復劃分來減小標準2折交叉驗證估計的波動，但由于多次重復都是針對同一數(shù)據(jù)集進行的，這導致不同切分的訓練集之間存在共同樣本.因此，m次獨立的2折交叉驗證之間的結果并不完全獨立.m次標準2折交叉驗證的平均結果與各次劃分后訓練集和測試集的共同樣本有關，共同樣本個數(shù)會影響最終m×2交叉驗證估計的方差.因此，本文針對m＝7的情形，提出了一種均衡的7×2交叉驗證方法，它使得2次獨立劃分后訓練集和測試集之間的共同樣本個數(shù)相同（稱此為均衡性），并給出了均衡7×2交叉驗證的構造方法.

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

1 模型選擇的交叉驗證方法

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

1.1 組塊3×2交叉驗證

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

表1 組塊3×2交叉驗證實驗設置

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

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

1.2 均衡7×2交叉驗證

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

表2 L8（27）正交表

表3 組塊7塊2交叉驗證實驗設置

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

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

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

表4 幾種交叉驗證方差的模擬比較

2 模擬實驗

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

2.1 模擬試驗的設置

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

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

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

從表5的試驗結果可以得到如下結論:

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

表5 試驗結果

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

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

3 總結和展望

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

[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].軟件學報，2010，30（4）:597－611

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