多核貝葉斯優化的模型決策樹算法

高虹雷，門昌騫，王文劍,2

(1. 山西大學 計算機與信息技術學院， 山西 太原 030006；2. 山西大學 計算智能與中文信息處理教育部重點實驗室， 山西 太原 030006)

在機器學習中，模型要想達到一個不錯的預測結果始終離不開超參數的合理設置。在當前大數據背景下，模型的超參數越來越多，比如神經網絡[1]、支持向量機[2]、隨機森林[3](random forest，RF)以及極端梯度提升樹[4](extreme gradient boosting，XGBoost)、輕量級梯度提升機[5](light gradient boosting machine，LightGBM)等廣泛運用于工程領域的模型，這些模型在現實應用中由此帶來的問題也層出不窮，比如組合過多，空間復雜，調參費時費力，還可能導致過擬合等問題。針對以上現狀，如何高效地進行超參數優化是機器學習領域中至關重要的一個方面。一些算法提出了有效的參數優化方法，例如Falkner等[6]結合貝葉斯優化和賭博機方法的優點提出了一種快速收斂的參數確定方法。Narayan等[7]提出了一個用于超參數優化的開源分布式框架，用戶可以靈活定制參數優化方法。此外，Liu等[8]提出一種通用的超參數優化框架，它使用戶可以在分布式設置中使用所有可用的計算資源進行模型訓練。而貝葉斯優化[9](Bayesian optimization，BO)作為當前超參數優化算法中的主流方法，在自適應機器學習算法[10]、強化學習[11]、自然語言處理[12]、推薦系統[13]、游戲設計[14]、傳感器應用[15]、環境監測[16]、醫學[17]等應用廣泛，相較經驗調參方式以及網格搜索[18]、隨機搜索[19]等調參算法，貝葉斯優化算法大量降低了訓練模型的時間，并且能夠自動選擇出最優參數，取得了很好的成績。近年來，對貝葉斯優化算法的研究主要集中在概率代理模型以及效用函數的改進方面[20]。例如，Srinivas等[21]利用置信邊界策略重新構造效用函數，接著Desautels等[22]提出批處理置信邊界策略使實驗可以分批進行。

傳統上，多數調參過程憑借經驗以及對算法的深刻理解，通過手動選參調參使得模型擁有一個良好的性能，但這種反復實驗的方法無法保證能有效地找到最合適的超參數組合，且會耗費大量時間。近年來，超參數優化[23]技術一直被業界積極探索，網格搜索即帶有步長的窮舉搜索，也是參數選擇比較常用的算法之一，但在參數過多的情況下，該算法將會耗費大量的時間，在計算代價上呈指數級上升。而隨機搜索則對超參數分布隨機采樣，且Bergstra和Bengio通過實驗證明隨機搜索算法[19]比網格搜索更加高效快捷。雖然網格搜索和隨機搜索在算法思想上比較簡單，在給定的參數范圍中測試，以此來確定最優值，理論上網格搜索一定可以找到全局最優值，但在面臨參數較多、范圍較廣的實際情況下，計算代價特別龐大，且兩者每次尋找新參數的過程都是獨立于之前尋參過程的，即忽略先驗分布，隨機搜索雖然比網格搜索效率高一些，但同樣也無法保證可以得到最優結果。

本文提出一種基于高斯過程的多核貝葉斯優化的模型決策樹(model decision tree based on multi-kernel Bayesian optimization, MBOMDT)算法，針對模型決策樹算法在構造模型決策樹時超參數較多，參數組合復雜，利用網格搜索尋找最優參數費時費力，且不一定能夠找到合適的參數值，設計了三種不同類型的核函數作為模型協方差函數組合，以此來應對不同分類數據的特性，實驗表明所提算法在參數尋優上要優于傳統的模型決策樹(model decision tree, MDT)尋優方法，在一定程度上提升了算法的分類性能，節省了大量的調參時間。

1 MBOMDT算法

1.1 MDT算法

文獻[24]提出的MDT算法的主要思想為在分類樹葉子規模到達給定閾值時停止樹的構建，并在生成的不完全決策樹的可辨識結點(非葉結點且包含不同類別的樣本)上搭載分類器，然后通過分類器繼續進行分類，圖1為模型決策樹的構建示意圖。

圖1 模型決策樹構建示意Fig.1 Construction of model decision tree

1.2 多核貝葉斯優化算法

貝葉斯優化核心算法包含兩個部分，即概率代理模型及效用函數(utility function)。在MDT算法中，葉子規模以及模型超參數的設置嚴重影響模型的分類性能。為了減少參數搜索的復雜度以及提升參數選擇的穩定性，本文提出了一種MBOMDT算法。

如給定模型決策樹MDT，將葉子規模(參數)視為變量，用x表示。將MDT的分類錯誤率當作目標函數f(x)，則貝葉斯優化的目標是找到恰當的x使得f(x)最小。與網格搜索或隨機搜索不同，貝葉斯優化在選擇下一個觀測點時考慮了已有的觀測點。具體來說,給定x的已有觀測點集合X={x1,x2,…,xn}以及目標函數值集合Y={y1,y2,…,yn}，貝葉斯優化利用集合Y、X以及概率代理模型擬合真實目標函數f(x)，之后根據效用函數得到下一個觀測點，并將觀測點及其目標函數值分別放入集合X與Y中，更新概率代理模型。重復上述過程，直到滿足終止條件，此時得到最優參數值。

f(x)～GP(M(x),Σ)

(1)

假設集合X、Y在忽視噪聲的情況下，即y=f(x),Y服從聯合高斯分布N(M(X),Σ)，并且協方差函數可由核矩陣K(X,X′)替代，公式如下：

(2)

(3)

k(X,x*)表示x*與X之間的3×1階核矩陣。通過以下公式可以形式化地表達上述過程：

p(y*|X,Y,x*)=N(M*,Σ*)

(4)

其中，Σ*=k(x*,x*)-k(x*,X)k(X,X)-1k(X,x*)，M*=k(x*,X)k(X,X)-1Y。最終，通過上述過程可以對目標函數進行擬合。

效用函數則起到了確定下一估計點的作用，常用的效用函數有：提升概率最大評估點[26](probability of improvement，POI)、最大化期望增量[27](expected improvement，EI)、最大化高斯過程置信區間[28](GP upper confidence bound，GP-UCB)。其中，GP-UCB表達式為：

(5)

參數β用來權衡均值及協方差，本文實驗中選擇的效用函數即GP-UCB。

由式(1)可知，構建函數分布的能力以及理想的預測結果很大程度上依賴于協方差函數，即核函數的選取。此外，對于多信息源、多模態數據，如果可以結合多個單核函數，可以提升模型辨識能力，即多核學習算法[29]。本文運用多核學習算法的思想，通過使用不同的核函數來提升算法性能。實驗所使用的徑向基函數(radial basis function, RBF)核函數分別表示為：

百分比是玉米粉碎后7目上，7～18目，18目下分別占玉米總重量的百分比。經不同工藝進行玉米粉碎，并對粉碎后粒度的分布情況統計分析如表2。

(6)

(7)

(8)

為更好地理解貝葉斯優化過程，本文給出一個例子進行說明，假設目標函數為f(x)=sinxcosx+1/(x2+1)，圖2分別為使用RBF核、Matern核以及DotProduct核的貝葉斯優化過程示意圖，每個實驗迭代10次。

由圖2可以看出，在后驗分布中方差越小的點代表越接近真實分布，接下來通過最大化效用函數，將下一評估點選出，即圖2中星點所在的位置，通過多次迭代過程，找到目標函數的最大值也即待調參數全局最優值。通過圖2中不同核函數對同一目標函數進行優化可以得出，在尋優的過程中，使用不同核函數擬合出的后驗分布具有不同的分布特性，當使用核函數組合來進行這一操作時，可以更大程度地覆蓋沒有被考慮的情況，提升算法整體的性能。多核貝葉斯優化算法如算法1所示。

(a) RBF核(a) RBF kernel

(b) Matern核(b) Matern kernel

(c) DotProduct核(c) DotProduct kernel圖2 貝葉斯優化模型Fig.2 Bayesian optimization model

2 實驗結果及分析

2.1 實驗數據集及實驗設置

實驗所用13個分類數據集均來自UCI數據集，如表1所示。計算機硬件及環境配置為：Intel(R)Core(TM)i7-7700 3.60 GHz 處理器，內存為16.0 GB，Windows 10 操作系統，Python 3.7 版本。

算法1 多核貝葉斯優化算法

表1 實驗數據集

MBOMDT算法選用了軟件包LIBLINEAR模型和標準支持向量機(support vector machine, SVM)模型，創建出三種新的模型，其中使用了LIBLINEAR模型的記為MBOMDT_LIB，使用線性核的SVM模型記為MBOMDT_SVM(linear)，使用高斯核的SVM模型記為MBOMDT_SVM(rbf)。

實驗中的超參數分別為可辨識結點樣本個數閾值V、LIBLINEAR中的類型參數s、SVM中懲罰參數c、高斯核參數γ。實驗內容主要為通過改進的貝葉斯優化算法對模型決策樹超參數進行調參，以期得到直觀明確的最優參數值，其中因為LIBLINEAR模型的參數s為類型參數，故在涉及使用LIBLINEAR模型的算法中類型參數s統一設置為2，不再另做討論。實驗中所用到的6種算法的相關參數如表2所示，MDT相關算法實驗參數設置來自文獻[24]。

表2 各算法實驗參數一覽表

文獻[24]中提出的三種模型決策樹算法MDT_LIB、MDT_SVM(linear)和MDT_SVM(rbf) 的超參數較多、調參過程費時費力，且三種算法已與SVM、KNN、LR(logistic regression)、LIBLINEAR等幾種常用的分類方法進行了比較，實驗結果表明文獻[24]中提出的三種模型決策樹算法在分類錯誤率及運行時間上大多優于其他方法，因此，本文所提三種模型將與文獻[24]中提出的三種模型決策樹算法以及原始貝葉斯優化下的模型決策樹BOMDT_LIB算法、BOMDT_SVM(linear)算法、BOMDT_SVM(rbf)算法進行比較。

2.2 算法參數的優化

MDT算法通過實驗探究了可辨識結點樣本個數閾值V對實驗結果的影響，即調整參數V的大小以期找到實驗結果的最優值，并作為算法的最優參數值進行下一步的分類研究。其方案為令可辨識結點樣本個數閾值V分別取樣本數的10%、30%、50%、70%、90%并在不同數據集上進行實驗，找到相對較優參數值，SVM模型中的懲罰參數c、高斯核參數γ均為人工調參并結合經驗設定的固定值。其中：MDT_LIB算法除在Credit Card Cliet和Cod_rna數據集上V取訓練樣本數的30%，在Spambase數據集上V取訓練樣本數的90%外，其余算法中V均為訓練樣本數的10%。MDT_SVM(linear)算法除在Spambase和Cod_rna數據集上V取訓練樣本數的50%，在Credit Card Cliet數據集上V取訓練樣本數的70%外，其余算法中V均為訓練樣本數的10%。MDT_SVM(rbf)算法除在Germen數據集上V取訓練樣本數的50%，在Image、Magic Gamma Telescope以及Cod_rna數據集上V取訓練樣本數的70%，在Credit Card Cliet數據集上V取訓練樣本數的90%以外，其余算法中V均為訓練樣本數的10%。使用線性核SVM模型中的懲罰參數c均為1，使用高斯核SVM模型算法中的懲罰參數c均為1、高斯核參數γ均為0.5。相應地，本文通過改進貝葉斯優化算法對模型決策樹進行參數選擇，各參數范圍分別是：V∈(0,100)、c∈(1,50)、γ∈(0.01,1)，算法首先選取3個初始點，總計迭代次數為20次。通過實驗為每種模型優化后的參數如表3所示。

在參數尋優的過程中，通過實驗可以看出：各算法基本迭代次數為10次以內就可將綜合范圍內的最優參數值找到。因此，利用改進的貝葉斯優化方法尋優可大幅減少原算法訓練最優參數的時間，提高算法分類效率。當使用LIBLINEAR模型時，算法參數為V。不同算法下運行時間比較如表4所示。MDT算法從{1,5,10,…,100}中尋找V的最優值，MBOMDT算法從(1,100)中尋找V的最優值，從表4中可以看到MBOMDT算法選擇參數的時間明顯低于MDT算法。另外，當使用高斯核SVM模型時，MDT算法分別從{1,5,10,…,100}、{1,10,20,…,50}、{0.01,0.1,0.2,…,1}中尋找V、c、γ的最優值，而MBOMDT算法從(1,100)、(1,50)、(0.01,1)中尋找參數值，從表4還可以看出MBOMDT的參數尋優時間遠低于MDT，其中“/”表示時間超于24 h。

表3 MBOMDT算法下參數的最優值

表4 不同算法下運行時間比較結果

2.3 本文算法與MDT算法的比較

本節將本文提出的三種算法MBOMDT_LIB、MBOMDT_SVM(linear)以及MBOMDT_SVM(rbf)分別與文獻[24]中的MDT_LIB、MDT_SVM(linear)和MDT_SVM(rbf)三種算法進行分類性能的比較，實驗結果如表5所示。MDT三種算法在部分數據集上的實驗結果來自文獻[24]，本文所提算法中的最優超參數設定均依照表3所得結果設置。由表5可知，本文所提三種算法在得到最優參數值之后使得算法的分類性能與之前對應的MDT算法相比，均得到了提升，其中MBOMDT_SVM(rbf)算法在所有算法中表現最好，表中標黑數據為該數據集下6種算法分類錯誤率最小值。

表5 不同算法下分類錯誤率比較結果

為直觀地理解實驗結果，圖3給出了MBOMDT算法與MDT算法采用三種不同分類器時分類錯誤率的大小關系比較。其中，黑點表示所用的13個數據集，橫坐標代表MDT算法的錯誤率，縱坐標代表MBOMDT算法的錯誤率。對角線上的黑點表示兩種算法錯誤率一致或基本相同，在對角線上方的黑點表示在此數據集上MBOMDT算法錯誤率高于MDT算法錯誤率，對角線下方的黑點代表在此數據集上MBOMDT算法錯誤率低于MDT算法錯誤率。黑點距離對角線越遠，表示在此數據集上兩種算法的分類錯誤率相差越大。

由圖3可知，當采用LIBLINEAR模型時，在5個數據集上MBOMDT的錯誤率明顯低于MDT算法，且提升幅度較大，其余數據集上基本持平或稍好于原結果；當采用SVM(linear)模型時，同樣5個數據集上MBOMDT算法的錯誤率明顯低于MDT算法，5個數據集上有小幅度提升，2個數據集基本持平，只有在1個數據集上略低于MDT算法；當采用SVM(rbf)模型時，MBOMDT算法只有在其中1個數據集上的結果與MDT算法基本持平，在剩下的數據集上，表現均有明顯提升。特別地，在Diabetis數據集上MBOMDT_SVM(rbf)算法的分類錯誤率比MDT_SVM(rbf)算法降低了91%。綜上，MBOMDT算法可通過找到全局最優超參數使模型分類的性能得到進一步提升。

(a) LIBLINEAR

(b) SVM(linear)

(c) SVM(rbf)圖3 MBOMDT與MDT分類錯誤率比較Fig.3 Comparison of classification error rate for MBOMDT and MDT

2.4 本文算法與BOMDT算法的比較

本節將本文所提出的三種算法MBOMDT_LIB、MBOMDT_SVM(linear)以及MBOMDT_SVM(rbf)與使用原始貝葉斯優化后的模型決策樹BOMDT_LIB、BOMDT_SVM(linear)和BOMDT_SVM(rbf)三種算法進行分類性能的比較。各算法均在最優超參數下運行，結果如表6所示。

由表6可知，MBOMDT_SVM(rbf)算法表現最好，表中標黑數據為該數據集下6種算法分類錯誤率最小值。從表中可以看出，三種MBOMDT算法在絕大部分數據集上的分類性能均優于BOMDT算法，這說明使用三種不同類型的核函數作為模型協方差函數組合要優于單一核函數下的貝葉斯優化算法，實驗結果表明，本文所提算法可應對不同分類數據的特性，從而獲得了較為理想的模型預測性能。

圖4給出了MBOMDT算法與BOMDT算法采用三種不同分類器時分類錯誤率的大小關系比較。由圖4可知，只有采用SVM(linear)模型時，在1個數據集上略低于BOMDT算法，其他算法均好于或與BOMDT算法相當。特別地，在Image數據集上MBOMDT_SVM(rbf)算法的分類錯誤率比BOMDT_SVM(rbf)算法降低了73%。綜上，MBOMDT算法通過在高斯過程中構建三個核函數組合，對分類問題適用更加廣泛，且在一定程度上可以提升模型的分類性能。

表6 不同算法下分類錯誤率比較結果

(a) LIBLINEAR

(b) SVM(linear)

(c) SVM(rbf)圖4 MBOMDT與BOMDT分類錯誤率比較Fig.4 Comparison of classification error rate for MBOMDT and BOMDT

3 結論

本文提出一種多核貝葉斯優化的模型決策樹算法，算法采用三種不同的高斯過程建模尋優，以應對不同的分類數據特性，利用貝葉斯優化技術，不斷加入新的信息，找到新的后驗分布，選出最佳的參數組合。實驗表明，所提算法在參數尋優上要優于傳統的MDT尋優方法，能夠在迭代次數不多的情況下找到更優的參數值，且在一定程度上提升算法的分類性能，減少計算代價。不過多核貝葉斯優化的模型決策樹算法對數據維度和算力要求方面比較高，在未來的工作中，需研究數據降維對算法的影響，以增強本算法的適用性。