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

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

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

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

1 KL距離

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

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

(1)

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

(2)

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

(3)

(4)

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

(5)

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

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

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

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

(6)

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

(7)

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

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

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

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

(8)

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

(9)

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

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

3.1 實(shí)驗設(shè)置

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

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

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

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

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

此外為了考慮不同類別對于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)。這是因為在如Wholesale customers數(shù)據(jù)集中，KL距離是從2.12×1014變化到6.71×1016，而折數(shù)K是從2變化到220，它們是不同數(shù)量級的，因此，為了二者的折中，不失一般性，正則化函數(shù)設(shè)置為f(K)=exp(-K)。事實(shí)上，不同的正則化函數(shù)(例如log(x)函數(shù)，exp(x)函數(shù))對于最優(yōu)折數(shù)K的選擇是沒有影響的。因為對于不同的正則化函數(shù)，通過調(diào)節(jié)不同的調(diào)節(jié)參數(shù)值始終可以選出相同的最優(yōu)折數(shù)K，只是收斂速度不同罷了[20]。

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

注：交叉驗證折數(shù)K的實(shí)際取值范圍為[2，n/2]，n為數(shù)據(jù)容量，因為在使用多元高斯分布來估計KL距離時，訓(xùn)練集/測試集最小需要兩個樣本估計樣本協(xié)方差陣。

3.2 實(shí)驗結(jié)果

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

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

(a) (b)

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

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

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

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

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

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