基于正則化KL距離的交叉驗證折數K的選擇

褚榮燕，王 鈺，楊杏麗，李濟洪

(1.山西大學 數學科學學院，山西 太原 030006；2.山西大學 現代教育技術學院，山西 太原 030006；3.山西大學 軟件學院，山西 太原 030006)

0 引 言

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

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

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

圖1 隨著折數K的變化KL距離的變化

1 KL距離

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

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

(1)

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

(2)

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

(3)

(4)

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

(5)

2 K折交叉驗證折數K的選擇準則

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

2.1 K折交叉驗證折數K的選擇準則

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

(6)

進一步，基于K折交叉驗證K次重復的對稱KL距離為：

(7)

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

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

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

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

(8)

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

(9)

3 真實數據實驗

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

3.1 實驗設置

四個數據集的相關描述如下：

(1)Wholesale customers數據集：關于批發商批發產品年度支出的一個二類分類(三類分類)數據集，根據批發商渠道把其中的餐飲業渠道分為第一類，零售渠道分為第二類(或按照客戶所在的區域(里斯本，波爾圖，其他區域這三個區域)把數據分為三類)，包含7個特征(Fresh，Milk，Grocery，Frozen等特征)，共440個樣本。

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

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

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

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

在式(8)給出的基于正則化KL距離的選擇準則中，正則化函數設置為f(K)=exp(-K)。這是因為在如Wholesale customers數據集中，KL距離是從2.12×1014變化到6.71×1016，而折數K是從2變化到220，它們是不同數量級的，因此，為了二者的折中，不失一般性，正則化函數設置為f(K)=exp(-K)。事實上，不同的正則化函數(例如log(x)函數，exp(x)函數)對于最優折數K的選擇是沒有影響的。因為對于不同的正則化函數，通過調節不同的調節參數值始終可以選出相同的最優折數K，只是收斂速度不同罷了[20]。

進一步，為了保證實驗的準確性，對該實驗過程重復1 000次，最后取這1 000次的平均值作為最終正則化KL距離。

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

3.2 實驗結果

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

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

(a) (b)

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

表1 Wholesale customers數據集的DCKL距離結果

表2 Wine數據集的DCKL距離結果

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

表3 wine quality-red數據集的DCKL距離結果

表4 wine quality-white數據集的DCKL距離結果

4 結束語

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

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