基于正則化KL距離的交叉驗(yàn)證折數(shù)K的選擇

褚榮燕，王 鈺，楊杏麗，李濟(jì)洪

(1.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006；2.山西大學(xué) 現(xiàn)代教育技術(shù)學(xué)院，山西 太原 030006；3.山西大學(xué) 軟件學(xué)院，山西 太原 030006)

0 引 言

在機(jī)器學(xué)習(xí)中，交叉驗(yàn)證技術(shù)廣泛地應(yīng)用于模型(算法)性能評(píng)估、特征選擇、模型選擇、模型參數(shù)確定、過(guò)擬合檢驗(yàn)等任務(wù)[1-5]。例如，給定一組線性空間(模型)，在這些線性空間(模型)中選擇最佳的最小二乘估計(jì)量時(shí)可用交叉驗(yàn)證進(jìn)行模型選擇。所謂交叉驗(yàn)證技術(shù)，即數(shù)據(jù)集被隨機(jī)地切分為多個(gè)訓(xùn)練集和測(cè)試集，訓(xùn)練集用來(lái)進(jìn)行模型的擬合，測(cè)試集用來(lái)進(jìn)行模型性能的評(píng)估，最后通過(guò)多次性能評(píng)估的均值(投票)來(lái)分析模型的優(yōu)劣。其中，常見(jiàn)的交叉驗(yàn)證技術(shù)包括留一(leave-one-out)交叉驗(yàn)證、Hold-out交叉驗(yàn)證、RLT(repeated learning testing)交叉驗(yàn)證、5×2交叉驗(yàn)證、組塊3×2交叉驗(yàn)證、組塊m×2交叉驗(yàn)證、K折交叉驗(yàn)證等[6-9]。在這些交叉驗(yàn)證技術(shù)中，K折交叉驗(yàn)證是最廣泛使用的方法，因?yàn)樗蕾囉谝粋€(gè)整數(shù)參數(shù)K，比其他經(jīng)典交叉驗(yàn)證方法的計(jì)算代價(jià)更小。K折交叉驗(yàn)證指的是數(shù)據(jù)集被平均分成K個(gè)大小近似相同但不相交的子集，選取其中K-1個(gè)子集作為訓(xùn)練集來(lái)擬合模型，剩下的一個(gè)子集作為測(cè)試集來(lái)評(píng)估模型性能。然而，在機(jī)器學(xué)習(xí)中，關(guān)于K折交叉驗(yàn)證方法的折數(shù)K的選擇雖然很多文獻(xiàn)中都對(duì)其進(jìn)行了研究并給出了推薦，但它一直是一個(gè)公開未解決的問(wèn)題[10-15]。比如文獻(xiàn)[6]中提到當(dāng)模型選擇的目標(biāo)是估計(jì)時(shí)，最優(yōu)的折數(shù)K為5到10之間，這是因?yàn)镵值越大，統(tǒng)計(jì)性能不會(huì)增加太多，并且小于10次分割的平均值在計(jì)算上仍然可行。文獻(xiàn)[8，11，12，14]皆推薦在進(jìn)行泛化誤差估計(jì)，算法性能對(duì)照和超參數(shù)選擇時(shí)應(yīng)選擇二折或多次二折重復(fù)的交叉驗(yàn)證(5×2交叉驗(yàn)證、組塊3×2交叉驗(yàn)證、組塊m×2交叉驗(yàn)證)。文獻(xiàn)[15]在多個(gè)分類器下的大量實(shí)驗(yàn)中驗(yàn)證了在進(jìn)行模型精度估計(jì)和模型選擇時(shí)十折交叉驗(yàn)證優(yōu)于留一交叉驗(yàn)證。另外，注意到上述文獻(xiàn)中大多是從模型性能評(píng)估和選擇的角度來(lái)進(jìn)行折數(shù)的選擇，但事實(shí)上，執(zhí)行上述交叉驗(yàn)證過(guò)程的一個(gè)前提條件是訓(xùn)練樣本和測(cè)試樣本的分布一致，然而在實(shí)際中對(duì)于訓(xùn)練樣本和測(cè)試樣本的分布是否一致許多文獻(xiàn)中并沒(méi)有驗(yàn)證。因此，該文考慮通過(guò)度量訓(xùn)練樣本和測(cè)試樣本的分布一致性來(lái)進(jìn)行K折交叉驗(yàn)證折數(shù)K的選擇。

實(shí)際中，常用的度量?jī)蓚€(gè)分布函數(shù)之間差異的度量有KL(Kullback-Leibler)距離、全變差(total variation)距離、海靈格(Hellinger)距離、KMM(kernel mean matching)度量、MMD(maximum mean discrepancy)度量、Wasserstein 距離等[16-17]，其中KL距離是最簡(jiǎn)單且廣泛使用的方法。因此，該文基于KL距離進(jìn)行K折交叉驗(yàn)證中折數(shù)K的選擇。

為此在UCI數(shù)據(jù)庫(kù)中選取的四個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)發(fā)現(xiàn)直接用KL距離來(lái)進(jìn)行K折交叉驗(yàn)證中折數(shù)K的選擇可能是不合理的，因?yàn)槿鐖D1所示，隨著K折交叉驗(yàn)證折數(shù)K的增加，訓(xùn)練樣本和測(cè)試樣本分布間KL距離也在增大，這樣直接基于KL距離進(jìn)行折數(shù)K的選擇往往選出的都是最小的或接近最小的折數(shù)K。因此不能直接應(yīng)用KL距離來(lái)進(jìn)行K折交叉驗(yàn)證折數(shù)K的選擇，為此考慮通過(guò)對(duì)KL距離增加一個(gè)隨著折數(shù)K增加而變小的正則化項(xiàng)來(lái)得到一個(gè)正則化的KL距離，以此作為交叉驗(yàn)證中折數(shù)K的選擇準(zhǔn)則。

圖1 隨著折數(shù)K的變化KL距離的變化

1 KL距離

在兩個(gè)分布函數(shù)之間差異的度量中最廣泛使用的方法是KL距離。接下來(lái)給出KL距離的定義。

如果記P(x)和Q(x)是兩個(gè)已知的分布函數(shù)，則P(x)和Q(x)之間的KL距離為：

(1)

特別地，當(dāng)P(x)和Q(x)分別為高斯分布Nd(uS,ΣS)和Nd(uF,ΣF)時(shí)，根據(jù)矩陣的性質(zhì)及多元高斯分布期望和協(xié)方差的性質(zhì)[18]，其KL距離可寫為:

(2)

具體地，在對(duì)數(shù)據(jù)進(jìn)行分析時(shí)，P(x)和Q(x)的總體均值和總體協(xié)方差一般使用樣本均值和樣本協(xié)方差來(lái)估計(jì)[19]：

(3)

(4)

此時(shí)，把式(3)和式(4)代入式(2)中，得到式(5)：

(5)

2 K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則

本節(jié)我們將基于上一節(jié)定義的KL距離進(jìn)行具體分析，通過(guò)對(duì)原始KL距離增加一正則化項(xiàng)，利用此正則化KL距離來(lái)選擇使得訓(xùn)練樣本和測(cè)試樣本分布盡可能一致的K折交叉驗(yàn)證的折數(shù)K。

2.1 K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則

觀察式(5)發(fā)現(xiàn)DKL[P(x)||Q(x)]≠DKL[Q(x)||P(x)]，也就是說(shuō)KL距離不是對(duì)稱的，因此該文考慮對(duì)稱的KL距離，即：

(6)

進(jìn)一步，基于K折交叉驗(yàn)證K次重復(fù)的對(duì)稱KL距離為：

(7)

雖然，在經(jīng)驗(yàn)上，基于訓(xùn)練樣本與測(cè)試樣本的KL距離選擇合適的折數(shù)K的方法是一個(gè)比較理想的方法，但是在實(shí)際結(jié)果中發(fā)現(xiàn)直接基于式(7)進(jìn)行K折交叉驗(yàn)證折數(shù)K的選擇并不是一個(gè)好的方法(詳見(jiàn)圖1)，因?yàn)殡S著折數(shù)K的增加KL距離也會(huì)增大，這會(huì)導(dǎo)致幾乎所有數(shù)據(jù)選出的折數(shù)都較小。為了解決此問(wèn)題，該文進(jìn)一步提出了一種新的基于正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則。

2.2 正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇

把一個(gè)隨著折數(shù)K增加而減小的函數(shù)作為一個(gè)正則化項(xiàng)添加到式(7)中，這樣對(duì)原始KL距離起到折中作用。為此，給出如下正則化KL距離選擇準(zhǔn)則:

DReKL(K)=DAKL[P(x),Q(x)]+λf(K)

(8)

其中，DAKL[·]定義為第K折訓(xùn)練樣本與測(cè)試樣本之間的平均KL距離，K為折數(shù)；f(K)是關(guān)于K的函數(shù)；λ是調(diào)節(jié)參數(shù)，通過(guò)調(diào)整λ確定正則化的程度。這時(shí)，基于最小化正則化KL距離的交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則為：

(9)

3 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

選取了UCI數(shù)據(jù)庫(kù)中的Wholesale customers，Wine，wine quality-red，wine quality-white四個(gè)數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)，以驗(yàn)證提出的基于正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則的合理性和有效性。

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

四個(gè)數(shù)據(jù)集的相關(guān)描述如下：

(1)Wholesale customers數(shù)據(jù)集：關(guān)于批發(fā)商批發(fā)產(chǎn)品年度支出的一個(gè)二類分類(三類分類)數(shù)據(jù)集，根據(jù)批發(fā)商渠道把其中的餐飲業(yè)渠道分為第一類，零售渠道分為第二類(或按照客戶所在的區(qū)域(里斯本，波爾圖，其他區(qū)域這三個(gè)區(qū)域)把數(shù)據(jù)分為三類)，包含7個(gè)特征(Fresh，Milk，Grocery，F(xiàn)rozen等特征)，共440個(gè)樣本。

(2)Wine數(shù)據(jù)集：關(guān)于三種不同品種的葡萄酒化學(xué)分析的一個(gè)三類分類數(shù)據(jù)集，三種葡萄酒即為三類，含有13個(gè)特征(Malic acid，Ash，Alkalinity of ash，Magnesium等特征)且每個(gè)特征是連續(xù)的變量，共178個(gè)樣本。

(3)wine quality-red數(shù)據(jù)集：關(guān)于紅葡萄酒質(zhì)量?jī)?yōu)劣檢測(cè)的一個(gè)二類分類(六類分類)數(shù)據(jù)集，根據(jù)酒的質(zhì)量把質(zhì)量指標(biāo)大于5的分成一類，質(zhì)量指標(biāo)小于等于5的分成另一類(或不同的指標(biāo)各表示一類)，包含11個(gè)特征(fixed acidity，volatile acidity，citric acid，residual sugar等特征)，共1 599個(gè)樣本。

(4)wine quality-white數(shù)據(jù)集：關(guān)于白葡萄酒質(zhì)量?jī)?yōu)劣檢測(cè)的一個(gè)二類分類(七類分類)數(shù)據(jù)集，根據(jù)酒的質(zhì)量把質(zhì)量指標(biāo)大于5的分成一類，質(zhì)量指標(biāo)小于等于5的分成另一類(或不同的指標(biāo)各表示一類)，包含11個(gè)特征(fixed acidity，volatile acidity，citric acid，residual sugar等特征)，共4 898個(gè)樣本。

此外為了考慮不同類別對(duì)于KL距離的影響，按照數(shù)據(jù)的屬性描述重新進(jìn)行了分類。例如Wholesale customers數(shù)據(jù)根據(jù)渠道和區(qū)域分為3類和2類，wine quality-red數(shù)據(jù)根據(jù)質(zhì)量指標(biāo)分為6類和2類，wine quality-white數(shù)據(jù)根據(jù)質(zhì)量指標(biāo)分為7類和2類。

在式(8)給出的基于正則化KL距離的選擇準(zhǔn)則中，正則化函數(shù)設(shè)置為f(K)=exp(-K)。這是因?yàn)樵谌鏦holesale customers數(shù)據(jù)集中，KL距離是從2.12×1014變化到6.71×1016，而折數(shù)K是從2變化到220，它們是不同數(shù)量級(jí)的，因此，為了二者的折中，不失一般性，正則化函數(shù)設(shè)置為f(K)=exp(-K)。事實(shí)上，不同的正則化函數(shù)(例如log(x)函數(shù)，exp(x)函數(shù))對(duì)于最優(yōu)折數(shù)K的選擇是沒(méi)有影響的。因?yàn)閷?duì)于不同的正則化函數(shù)，通過(guò)調(diào)節(jié)不同的調(diào)節(jié)參數(shù)值始終可以選出相同的最優(yōu)折數(shù)K，只是收斂速度不同罷了[20]。

進(jìn)一步，為了保證實(shí)驗(yàn)的準(zhǔn)確性，對(duì)該實(shí)驗(yàn)過(guò)程重復(fù)1 000次，最后取這1 000次的平均值作為最終正則化KL距離。

注：交叉驗(yàn)證折數(shù)K的實(shí)際取值范圍為[2，n/2]，n為數(shù)據(jù)容量，因?yàn)樵谑褂枚嘣咚狗植紒?lái)估計(jì)KL距離時(shí)，訓(xùn)練集/測(cè)試集最小需要兩個(gè)樣本估計(jì)樣本協(xié)方差陣。

3.2 實(shí)驗(yàn)結(jié)果

基于3.1節(jié)的數(shù)據(jù)集，首先驗(yàn)證了隨著K折交叉驗(yàn)證的折數(shù)K的增加，所有訓(xùn)練樣本和測(cè)試樣本分布之間的KL距離逐漸增大。然后，給出了基于提出的正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則的選擇結(jié)果。

圖1展示了不同折交叉驗(yàn)證的訓(xùn)練樣本和測(cè)試樣本之間的KL距離。根據(jù)圖1，首先可以看到所有訓(xùn)練樣本和測(cè)試樣本分布之間的差異是明顯的，例如，在Wholesale customers數(shù)據(jù)中，折數(shù)從2折增到10折時(shí)，對(duì)應(yīng)的KL距離從2.12×1014上升到7.04×1014，在Wine數(shù)據(jù)中，折數(shù)從2折增到10折時(shí)，對(duì)應(yīng)的KL距離從3.31×107上升到9.94×107。第二，圖中直觀地顯示了隨著折數(shù)K的增加，KL距離逐漸增大。例如，wine quality-red數(shù)據(jù)集中，折數(shù)范圍從2變化到799時(shí)，KL距離從1 532上升到6.05×105。wine quality-white數(shù)據(jù)集中，折數(shù)范圍從2變化到2 449時(shí)，KL距離從1 695上升到1.26×106，也就是說(shuō)當(dāng)折數(shù)從2上升到n/2(n為樣本量)時(shí)，不同數(shù)據(jù)的KL距離都是持續(xù)上升的。且?guī)缀跛袛?shù)據(jù)訓(xùn)練樣本和測(cè)試樣本的KL距離都是2折或者接近2折時(shí)最小，顯然這是不合適的，因?yàn)樗傔x擇最小或接近最小的折數(shù)，因此為KL距離增加一個(gè)正則化項(xiàng)，提出了基于正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則，通過(guò)最小化式(8)中給出的準(zhǔn)則來(lái)選擇最優(yōu)折數(shù)。結(jié)果如圖2所示。

(a) (b)

圖2展示了正則化后的DReKL(·)變化趨勢(shì)。為了更清楚地看到正則化KL距離的變化，表1～表4給出了K=2，5，8，9，10，11，12，13，14，15，20時(shí)，四個(gè)數(shù)據(jù)集上正則化KL距離的數(shù)值。首先可以看出，隨著折數(shù)的增加正則化KL距離先減小后增大，例如在表1的Wholesale customers數(shù)據(jù)集中3類的情況下，9折時(shí)正則化KL距離的值為7.27×1014，10折時(shí)正則化KL距離的值為7.18×1014，20折時(shí)正則化KL距離的值為15.92×1014。在表2的Wine數(shù)據(jù)集中，9折時(shí)正則化KL距離的值為10×107，10折時(shí)正則化KL距離的值為9.94×107，20折時(shí)正則化KL距離的值為19.47×107。在表4的wine quality-white數(shù)據(jù)集中，9折時(shí)正則化KL距離的值為9.93×103，10折時(shí)正則化KL距離的值為6.23×103，20折時(shí)正則化KL距離的值為7.78×103，這都驗(yàn)證了提出的方法是合適的。

表1 Wholesale customers數(shù)據(jù)集的DCKL距離結(jié)果

表2 Wine數(shù)據(jù)集的DCKL距離結(jié)果

另外，可以在表1～表4中看到每個(gè)數(shù)據(jù)的最優(yōu)折數(shù)(表1～表4中的黑色粗斜體表示不同數(shù)據(jù)分為2類時(shí)最優(yōu)的折數(shù)及其對(duì)應(yīng)的正則化KL距離值，黑色粗體表示不同數(shù)據(jù)分為其他類時(shí)最優(yōu)的折數(shù)及其對(duì)應(yīng)的正則化KL距離值)，例如Wholesale-customers數(shù)據(jù)分3類時(shí)最優(yōu)折數(shù)為10折，分2類時(shí)最優(yōu)折數(shù)為9折。Wine數(shù)據(jù)最優(yōu)折數(shù)為10折。wine quality-red數(shù)據(jù)分6類時(shí)最優(yōu)折數(shù)10折，2類時(shí)最優(yōu)折數(shù)為9折。wine quality-white數(shù)據(jù)分為7類時(shí)最優(yōu)折數(shù)為12折，2類時(shí)最優(yōu)折數(shù)為12折。最后，發(fā)現(xiàn)不同分類類別對(duì)同一數(shù)據(jù)集的訓(xùn)練樣本和測(cè)試樣本之間的正則化KL距離是有影響的，一般情況下同一數(shù)據(jù)集下多類分類比二類分類的正則化KL距離的差異小(除Wholesale customers數(shù)據(jù)集外)，例如在表4中，當(dāng)折數(shù)為12時(shí)，7類的正則化KL距離的數(shù)值約為5.17×103，2類的正則化KL距離的數(shù)值約為5.25×103。

表3 wine quality-red數(shù)據(jù)集的DCKL距離結(jié)果

表4 wine quality-white數(shù)據(jù)集的DCKL距離結(jié)果

4 結(jié)束語(yǔ)

K折交叉驗(yàn)證技術(shù)在機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)中被廣泛使用，但關(guān)于其折數(shù)K的選擇一直是一個(gè)公開未解決的問(wèn)題。而在傳統(tǒng)的機(jī)器學(xué)習(xí)中使用K折交叉驗(yàn)證進(jìn)行分析時(shí)，都是在假設(shè)訓(xùn)練樣本和測(cè)試樣本分布一致進(jìn)行的，但是實(shí)際中訓(xùn)練樣本和測(cè)試樣本的分布往往不一致。該文在考慮K折交叉驗(yàn)證過(guò)程中訓(xùn)練樣本和測(cè)試樣本的分布一致性的情況下，利用KL距離來(lái)度量訓(xùn)練集樣本和測(cè)試集樣本二者分布的差異，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)直接使用KL距離進(jìn)行選擇時(shí)，往往選出的是最小的或者接近最小的折數(shù)，這并不合理?；诖?，提出了一種基于正則化KL距離的K折交叉驗(yàn)證折數(shù)K的選擇準(zhǔn)則。并通過(guò)UCI數(shù)據(jù)庫(kù)中的四個(gè)數(shù)據(jù)集對(duì)提出的準(zhǔn)則進(jìn)行驗(yàn)證，最終結(jié)果驗(yàn)證了該選擇準(zhǔn)則的合理性和有效性。

同時(shí)我們應(yīng)該看到，雖然我們通過(guò)使訓(xùn)練樣本和測(cè)試樣本的分布差異最小化選出了K折交叉驗(yàn)證的合適的折數(shù)K，但是訓(xùn)練樣本和測(cè)試樣本的分布之間仍存在差異，本文并未給出使訓(xùn)練集與測(cè)試集盡可能一致的校正策略，未來(lái)我們將在此框架下進(jìn)一步研究二者分布的校正策略。