挪威科技大學 Didrik Nielsen 的碩士論文《使用 XGBoost 的樹提升：為什麼 XGBoost 能贏得「每一場」機器學習競賽？（Tree Boosting With XGBoost - Why Does XGBoost Win "Every" Machine Learning Competition?）》研究分析了 XGBoost 與傳統 MART 的不同之處以及在機器學習競賽上的優勢。本文對這篇長達 110 頁的論文進行了解讀，提煉出了其中的要點和核心思想，匯成此篇。引言

tree boosting（樹提升）已經在實踐中證明可以有效地用於分類和迴歸任務的預測挖掘。

之前很多年來，人們所選擇的樹提升演算法一直都是 MART（multiple additive regression tree/多重累加回歸樹）。但從 2015 年開始，一種新的且總是獲勝的演算法浮出了水面：XGBoost。這種演算法重新實現了樹提升，並在 Kaggle 和其它資料科學競賽中屢獲佳績，因此受到了人們的歡迎。

在《Tree Boosting With XGBoost - Why Does XGBoost Win "Every" Machine Learning Competition?》這篇論文中，來自挪威科技大學的 Didrik Nielsen 研究調查了：

1.XGBoost 與傳統 MART 的不同之處

2.XGBoost 能贏得「每一場」機器學習競賽的原因

這篇論文分成三大部分：

1. 回顧統計學習的一些核心概念

機器學習演算法的目標是減少預期的泛化誤差，這也被稱為風險（risk）。如果我們知道真實的分佈 P(x,y)，那麼風險的最小化就是一個可以透過最佳化演算法解決的最佳化任務。但是，我們並不知道真實分佈，只是有一個用於訓練的樣本集而已。我們需要將其轉換成一個最佳化問題，即最小化在訓練集上的預期誤差。因此，由訓練集所定義的經驗分佈會替代真實分佈。上述觀點可以表示成下面的統計學公式：

其中是模型的真實風險 R(f) 的經驗估計。L(.) 是一個損失函式，比如平方誤差損失函式（這是迴歸任務常用的損失函式），其它損失函式可以在這裡找到：http://www.cs.cornell.edu/courses/cs4780/2017sp/lectures/lecturenote10.html。n 是樣本的數量。

當 n 足夠大時，我們有：

ERM（經驗風險最小化）是一種依賴於經驗風險的最小化的歸納原理（Vapnik, 1999）。經驗風險最小化運算 是目標函式的經驗近似，定義為：

其中 F 屬於某個函式類，並被稱為某個模型類（model class），比如常數、線性方法、區域性迴歸方法（k-最近鄰、核迴歸）、樣條函式等。ERM 是從函式集 F 中選擇最優函式 的標準。

這個模型類和 ERM 原理可以將學習問題轉變成最佳化問題。模型類可以被看作是候選的解決方案函式，而 ERM 則為我們提供了選擇最小化函式的標準。

針對最佳化問題的方法有很多，其中兩種主要方法是梯度下降法和牛頓法；MART 和 XGBoost 分別使用了這兩種方法。

這篇論文也總結了常見的學習方法：

1. 常數

2. 線性方法

3. 區域性最優方法

4. 基函式擴充套件：顯式非線性項、樣條、核方法等

5. 自適應基函式模型：GAM（廣義相加模型）、神經網路、樹模型、boosting

另一個機器學習概念是模型選擇（model selection），這要考慮不同的學習方法和它們的超引數。首要的問題一直都是：增加模型的複雜度是否更好？而答案也總是與模型自身的泛化效能有關。如下圖 1 所示，我們也許可以在模型更加複雜的同時得到更好的表現（避免欠擬合），但我們也會失去泛化效能（過擬合）：

圖 1：泛化效能 vs 訓練誤差

（僅）為平方損失使用預期條件風險的經典的偏置-方差分解（bias-variance decomposition），我們可以觀察風險相對於複雜度的變化：

圖 2：預期風險 vs 方差 vs 偏置

為此通常使用的一種技術是正則化（regularization）。透過隱式和顯式地考慮資料的擬合性和不完善性，正則化這種技術可以控制擬合的方差。它也有助於模型具備更好的泛化效能。

不同的模型類測量複雜度的方法也不一樣。LASSO 和 Ridge（Tikhonov regularization）是兩種常用於線性迴歸的測量方法。我們可以將約束（子集化、步進）或懲罰（LASSO、Ridge）直接應用於複雜度測量。

理解 boosting、樹方法和樹提升

boosting

boosting 是一種使用多個更簡單的模型來擬合數據的學習演算法，它所用的這些更簡單的模型也被稱為基本學習器（base learner）或弱學習器（weak learner）。其學習的方法是使用引數設定一樣或稍有不同的基本學習器來自適應地擬合數據。

Freund 和 Schapire (1996) 帶來了第一個發展：AdaBoost。實際上 AdaBoost 是最小化指數損失函式，並迭代式地在加權的資料上訓練弱學習器。研究者也提出過最小化對數損失的二階近似的新型 boosting 演算法：LogitBoost。

Breiman (1997a,b 1998) 最早提出可以將 boosting 演算法用作函式空間中的數值最佳化技術。這個想法使得 boosting 技術也可被用於迴歸問題。這篇論文討論了兩種主要的數值最佳化方法：梯度提升和牛頓提升（也被稱為二階梯度提升或 Hessian boosting，因為其中應用了 Hessian 矩陣）。

讓我們一步一步瞭解 boosting 演算法：

boosting 擬合同一類的整合模型（ensemble model）：

其可以被寫成自適應基函式模型：

其中 且，m=1,…,M，Φm 是按順序累加的基本函式，可用於提升當前模型的擬合度。

因此，大多數 boosting 演算法都可以看作是在每次迭代時或準確或近似地求解

所以，AdaBoost 就是為指數損失函式求解上述等式，其約束條件為：Φm 是 A={-1,1} 的分類器。而梯度提升或牛頓提升則是為任意合適的損失函式近似求解上述等式。

梯度提升和牛頓提升的演算法如下：

最常用的基本學習器是迴歸樹（比如 CART），以及分量形式的線性模型（component-wise linear model）或分量形式的平滑樣條（component-wise smoothing spline）。基本學習器的原則是要簡單，即有很高的偏置，但方差很低。

boosting 方法中的超引數有：

1. 迭代次數 M：M 越大，過擬合的可能性就越大，因此需要驗證集或交叉驗證集。

2. 學習率 η ：降低學習率往往會改善泛化效能，但同時也會讓 M 增大，如下圖所示。

在 Boston Housing 資料集上的不同學習率的樣本外（out-of-sample）RMSE

樹方法

樹模型是簡單和可解釋的模型。它們的預測能力確實有限，但將多個樹模型組合到一起（比如 bagged trees、隨機森林或在 boosting 中），它們就可以變成一種強大的預測模型。

我們可以將樹模型看作是將特徵空間分割成幾個不同的矩形和非重疊區域集合，然後它可以擬合一些簡單的模型。下圖給出了使用 Boston Housing 資料得到的視覺化結果：

終端節點的數量和樹的深度可以看作是樹模型的複雜度度量。為了泛化這種模型，我們可以在複雜度度量上輕鬆地應用一個複雜度限制，或在終端節點的數量或葉權重的懲罰項上應用一個懲罰（XGBoost 使用的這種方法）。

因為學習這種樹的結構是 NP 不完全的，所以學習演算法往往會計算出一個近似的解。這方面有很多不同的學習演算法，比如 CART（分類和迴歸樹）、C4.5 和 CHAID。這篇論文描述了 CART，因為 MART 使用的 CART，XGBoost 也實現了一種與 CART 相關的樹模型。

CART 以一種自上而下的方式生長樹。透過考慮平行於座標軸的每次分割，CART 可以選擇最小化目標的分割。在第二步中，CART 會考慮每個區域內每次平行的分割。在這次迭代結束時，最好的分割會選出。CART 會重複所有這些步驟，直到達到停止標準。

給定一個區域 Rj，學習其權重 wj 通常很簡單。令 Ij 表示屬於區域 Rj 的索引的集合，即 xi∈Rj，其中 i∈Ij。

其權重是這樣估計的：

對於一個樹模型，經驗風險為：

其中我們令 表示節點 j 處的累積損失。

在學習過程中，當前樹模型用 和 表示。

我們可以計算所考慮的分割所帶來的增益：

對於每一次分割，每個可能節點的每個可能分割都會計算這種增益，再取其中最大的增益。

現在讓我們看看缺失值。CART 會使用替代變數（surrogate variable）來處理缺失值，即對於每個預測器，我們僅使用非缺失資料來尋找分割，然後再基於主分割尋找替代預測因子，從而模擬該分割。比如，假設在給定的模型中，CART 根據家庭收入分割資料。如果一個收入值不可用，那麼 CART 可能會選擇教育水平作為很好的替代。

但 XGBoost 是透過學習預設方向來處理缺失值。XGBoost 會在內部自動學習當某個值缺失時，最好的方向是什麼。這可以被等價地看作是根據訓練損失的減少量而自動「學習」缺失值的最佳插補值。

根據類別預測器，我們可以以兩種方式處理它們：分組類別或獨立類別。CART 處理的是分組類別，而 XGBoost 需要獨立類別（one-hot 編碼）。

這篇論文以列表的形式總結了樹模型的優缺點：

優點（Hastie et al., 2009; Murphy, 2012）：

• 容易解釋

• 可以相對快地構建

• 可以自然地處理連續和分類資料

• 可以自然地處理缺失資料

• 對輸入中的異常值是穩健的

• 在輸入單調變換時是不變的

• 會執行隱式的變數選擇

• 可以得到資料中的非線性關係

• 可以得到輸入之間的高階互動

• 能很好地擴充套件到大型資料集

缺點（Hastie et al., 2009; Kuhn and Johnson, 2013; Wei-Yin Loh, 1997; Strobl et al., 2006）：

• 往往會選擇具有更高數量的不同值的預測器

• 當預測器具有很多類別時，可能會過擬合

• 不穩定，有很好的方差

• 缺乏平滑

• 難以獲取疊加結構

• 預測效能往往有限

樹提升

在上述發展的基礎上，現在我們將 boosting 演算法與基本學習器樹方法結合起來。

提升後的樹模型可以看作是自適應基函式模型，其中的基函式是迴歸樹：

提升樹模型（boosting tree model）是多個樹 fm 的和，所以也被稱為樹整合（tree ensemble）或疊加樹模型（additive tree model）。因此它比單個樹模型更加平滑，如下圖所示：

擬合 Boston Housing 資料的疊加樹模型的視覺化

在提升樹模型上實現正則化的方法有很多：

1. 在基函式擴充套件上進行正則化

2. 在各個樹模型上進行正則化

3. 隨機化

一般來說，提升樹往往使用很淺的迴歸樹，即僅有少數終端節點的迴歸樹。相對於更深度的樹，這樣的方差較低，但偏置更高。這可以透過應用複雜度約束來完成。

XGBoost 相對於 MART 的優勢之一是複雜度的懲罰，這對疊加樹模型而言並不常見。目標函式的懲罰項可以寫成：

其中第一項是每個單個樹的終端節點的數量，第二項是在該項權重上的 L2 正則化，最後一項是在該項權重上的 L1 正則化。

Friedman(2002) 最早引入了隨機化，這是透過隨機梯度下降實現的，其中包括在每次迭代時進行行子取樣（row subsampling）。隨機化有助於提升泛化效能。子取樣的方法有兩種：行子取樣與列子取樣（column subsampling）。MART 僅包含行子取樣（沒有替代），而 XGBoost 包含了行子取樣和列子取樣兩種。

其基函式是樹：

其一般步驟包含 3 個階段：

1. 確定一個固定的候選樹結構的葉權重 ；

2. 使用前一階段確定的權重，提出不同的樹結構，由此確定樹結構和區域；

3. 一旦樹結構確定，每個終端節點中的最終葉權重（其中 j=1,..,T）也就確定了。

演算法 3 和 4 使用樹作為基函式，對演算法 1 和 2 進行了擴充套件：

XGBoost 和 MART 的差異

最後，論文對兩種樹提升演算法的細節進行了比較，並試圖給出 XGBoost 更好的原因。

演算法層面的比較

即不使用貪婪搜尋，而是每次新增一個樹。在第 m 次迭代時，使用下式學習新的樹：

XGBoost 使用了上面的演算法 3，即用牛頓樹提升來近似這個最佳化問題。而 MART 使用了上面的演算法 4，即用梯度樹提升來做這件事。這兩種方法的不同之處首先在於它們學習樹結構的方式，然後還有它們學習分配給所學習的樹結構的終端節點的葉權重的方式。

再看看這些演算法，我們可以發現牛頓樹提升有 Hessian 矩陣，其在確定樹結構方面發揮了關鍵性的作用，XGBoost：

而使用了梯度樹提升的 MART 則是：

然後，XGBoost 可以直接這樣定義牛頓樹提升的葉權重：

使用梯度樹提升的 MART 則這樣定義：

總結一下，XGBoost 使用的 Hessian 是一種更高階的近似，可以學習到更好的樹結構。但是，MART 在確定葉權重上表現更好，但卻是對準確度更低的樹結構而言。

在損失函式的應用性方面，牛頓樹提升因為要使用 Hessian 矩陣，所以要求損失函式是二次可微的。所以它在選擇損失函式上要求更加嚴格，必須要是凸的。

當 Hessian 每一處都等於 1 時，這兩種方法就是等價的，這就是平方誤差損失函式的情況。因此，如果我們使用平方誤差損失函式之外的任何損失函式，在牛頓樹提升的幫助下，XGBoost 應該能更好地學習樹結構。只是梯度樹提升在後續的葉權重上更加準確。因此無法在數學上對它們進行比較。

儘管如此，該論文的作者在兩個標準資料集上對它們進行了測試：Sonar 和 Ionosphere（Lichman, 2013）。這個實證比較使用了帶有 2 個終端節點的樹，沒有使用其它正則化，而且這些資料也沒有分類特徵和缺失值。梯度樹提升還加入了一個線搜尋（line search），如圖中紅色線所示。

這個比較圖說明這兩種方法都能無縫地執行。而且線搜尋確實能提升梯度提升樹的收斂速度。

正則化比較

正則化引數實際上有 3 類：

1.boosting 引數：樹的數量 M 和學習率η

2. 樹引數：在單個樹的複雜度上的約束和懲罰

3. 隨機化引數：行子取樣和列子取樣

兩種 boosting 方法的主要差別集中在樹引數以及隨機化引數上。

對於樹引數，MART 中的每個樹都有同樣數量的終端節點，但 XGBoost 可能還會包含終端節點懲罰 γ，因此其終端節點的數量可能會不一樣並且在最大終端節點數量的範圍內。XGBoost 也在葉權重上實現了 L2 正則化，並且還將在葉權重上實現 L1 正則化。

在隨機化引數方面，XGBoost 提供了列子取樣和行子取樣；而 MART 只提供了行子取樣。

為什麼 XGBoost 能贏得「每一場」競賽？

透過使用模擬資料，論文作者首次表明樹提升可以被看作是自適應地確定區域性鄰域。

使用

生成

然後使用區域性線性迴歸（使用了兩種不同靈活度的擬合）來擬合它：

然後使用平滑樣條函式（使用了兩種不同靈活度的擬合）來擬合它：

現在我們嘗試提升的樹樁（boosted tree stump）（兩個終端節點）擬合：

本論文詳細說明了權重函式影響擬合的確定的方式，並且表明樹提升可以被看作是直接在擬合階段考慮偏置-方差權衡。這有助於鄰域保持儘可能大，以避免方差不必要地增大，而且只有在複雜結構很顯然的時候才會變小。

儘管當涉及到高維問題時，樹提升「打敗了」維度的詛咒（curse of dimensionality），而沒有依賴任何距離指標。另外，資料點之間的相似性也可以透過鄰域的自適應調整而從資料中學習到。這能使模型免疫維度的詛咒。

另外更深度的樹也有助於獲取特徵的互動。因此無需搜尋合適的變換。

因此，是提升樹模型（即自適應的確定鄰域）的幫助下，MART 和 XGBoost 一般可以比其它方法實現更好的擬合。它們可以執行自動特徵選擇並且獲取高階互動，而不會出現崩潰。

透過比較 MART 和 XGBoost，儘管 MART 確實為所有樹都設定了相同數量的終端節點，但 XGBoost 設定了 Tmax 和一個正則化引數使樹更深了，同時仍然讓方差保持很低。相比於 MART 的梯度提升，XGBoost 所使用的牛頓提升很有可能能夠學習到更好的結構。XGBoost 還包含一個額外的隨機化引數，即列子取樣，這有助於進一步降低每個樹的相關性。

本文的看法

這篇論文從基礎開始，後面又進行了詳細的解讀，可以幫助讀者理解提升樹方法背後的演算法。透過實證和模擬的比較，我們可以更好地理解提升樹相比於其它模型的關鍵優勢以及 XGBoost 優於一般 MART 的原因。因此，我們可以說 XGBoost 帶來了改善提升樹的新方法。

參考文獻

Chen, T. and Guestrin, C. (2016). Xgboost: A scalable tree boosting system. In Proceedings of the 22Nd ACM SIGKDD International Conference on Knowl- edge Discovery and Data Mining, KDD 』16, pages 785–794, New York, NY, USA. ACM.

Freund, Y. and Schapire, R. E. (1996). Experiments with a new boosting algorithm. In Saitta, L., editor, Proceedings of the Thirteenth International Conference on Machine Learning (ICML 1996), pages 148–156. Morgan Kaufmann.

Friedman, J. H. (2002). Stochastic gradient boosting. Comput. Stat. Data Anal., 38(4):367–378.

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition. Springer Series in Statistics. Springer.

Kuhn, M. and Johnson, K. (2013). Applied Predictive Modeling. SpringerLink : Bu ̈cher. Springer New York.

Lichman, M. (2013). UCI machine learning repository.

Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. The MIT Press.

Strobl, C., laure Boulesteix, A., and Augustin, T. (2006). Unbiased split selection for classification trees based on the gini index. Technical report.

Vapnik, V. N. (1999). An overview of statistical learning theory. Trans. Neur. Netw., 10(5):988–999.

Wei-Yin Loh, Y.-S. S. (1997). Split selection methods for classification trees. Statistica Sinica, 7(4):815–840.

Wikipedia::Lasso. https://en.wikipedia.org/wiki/Lasso_(statistics)

Wikipedia::Tikhonov regularization. https://en.wikipedia.org/wiki/Tikhonov_regularization

全文共3492字，預計學習時長15分鐘

前幾天，Z同學面試完一臉生無可戀地問我，“你知道XGBoost嗎？”“當然知道啊，前幾天不看你還在手推來著。”“嗯，那你知道XGBoost的中英文全稱是啥麼？”“ummmmm...X的話難道是羅馬數字10? G的話Gradient梯度，Boost的Boosting tree？所以是第十代梯度提升樹？”“。。。換你答，你也涼。”

學習演算法的最大誤區還記得那個吐槽清華某畢業生連手寫紅黑樹都不會卻張口就要一萬八的HR嗎？

這事曾一度引起網友的廣泛關注和熱烈討論，不過圈子不同，影響不同。對於普通吃瓜群眾，“HR說得對，太膨脹。”對於某些資深程式猿，“我也不會，我月薪30k。”對於求職小白，“好慌，手寫紅黑樹？面試不會還要手推SVM、XGBoost吧？溜了溜了，去推泰勒二次展開了。”然後，就像我的同學小Z一樣，只顧著埋頭推導XGBoost的二階泰勒展開，卻連XGBoost的中英文全稱都答不上來。顧此失彼，乃是兵家大忌。很多時候，我們在學習演算法時，要麼過於糾結弄懂原理而忽略了從宏觀上對演算法有一個總體的瞭解和把握，要麼是囫圇吞棗一口氣看個十來篇部落格介紹卻往往還是一知半解不求甚解，可能還會莫名自我感覺良好。

基於此，本文就從宏觀上來幫大家梳理梳理XGBoost，力求通俗易懂，精準得當。至於演算法原理和資源連結嘛，請直接拜讀陳天奇博士的論文XGBoost: A Scalable Tree Boosting System，同時請參考Github上的開源資源進行原始碼的學習和實戰（https://github.com/dmlc/xgboost）。

什麼是 XGBoost?

原圖來自Unsplash（by Jared Subia）

十幾年前，迴歸建模是預測分析中毫無爭議的女王。但如今迴歸建模的時代已經結束，XGBoost已被成功加冕！XGBoost的英文全稱為Extreme Gradient Boosting, 中文可以解釋為極端梯度提升（Extreme，一聽就很牛X），它是一種基於決策樹的整合機器學習演算法，採用了梯度提升（Gradient Boosting）框架。在預測有關非結構化資料（如影象、文字等）的問題時，人工神經網路往往表現得比其他演算法或框架更出色。但在有關中小型結構/表格資料方面，基於決策樹的演算法則是目前為止的最佳方式。請參閱以下圖表，瞭解幾年來基於決策樹的演算法演變。

基於決策樹的演算法演變

XGBoost演算法最初由華盛頓大學的一個研究專案發展而來。2016年，陳天奇和卡洛斯·格斯特林在知識發現和資料探勘（SIGKDD）會議上共同發表了一篇論文，一時間這轟動了整個機器學習領域。自演算法提出以來，它不僅幫助競賽者贏得了多場Kaggle競賽的勝利，還被幾款尖端行業的應用所採納。在GitHub上，有一群強大的資料科學家們為XGBoost開源專案提供幫助，約有350名科學家，總提交次數約為3,600次。

總體而言，XGBoost具有以下特徵：

1. 應用廣泛：可用於解決迴歸、分類、排名和使用者定義的預測問題。

2. 移植性強：可在Windows、Linux和OS X上流暢執行。

3. 語言支援：支援目前主要的全部程式語言，包括C ++、Python、R、Java、Scala和Julia。

4. 雲集成：支援AWS、GCE、Azure和 Yarn叢集，可以與 Flink、Spark和其他雲資料流系統整合。

通俗理解基於決策樹的演算法演變

照片來自Unsplash（by rawpixel）

假設你是一名面試官，正在面試幾位資歷優秀的候選人。基於決策樹的演算法演變中的每一環，都可看作面試過程的一部分。

1. 決策樹：每名面試官都有一套面試評價標準，如教育水平、工作經驗以及面試表現，透過決策樹來預測分析，就類似於面試官根據他自己的標準面試候選人。

2. Bagging：假設現在面試官不止一名，而是一個面試小組，每名面試官都有一票，Bagging（也稱作bootstrap aggregating）意味著透過民主投票方式，將所有面試官的投票結果進行輸入，從而做出最終決定。

3. 隨機森林：這是一種基於bagging的演算法，與bagging的不同在於僅隨機選擇特徵的子集。換句話說，每名面試官只會根據某些隨機的資質測試方式（例如，測試程式設計技能的技術面試和非技術技能評估的行為面試）來考查面試者。

4. Boosting：這是一種動態評估方法，每位面試官根據前一位面試官的反饋，改變評估標準。透過部署更加動態的評估流程，“提高”面試流程的效率。

5. Gradient Boosting：這是Boosting的一種特殊情況，透過梯度下降演算法將誤差最小化，打個比方說，就好比戰略諮詢公司利用面試案例，剔除不合格的候選人。

6. XGBoost：將XGBoost視為強化版的的gradient boosting，畢竟extreme不是隨隨便便就能“冠”名的。它是軟體和硬體最佳化技術的完美結合，可在最短的時間內，使用較少的計算資源，得到較為出色的結果。

XGBoost為什麼這麼“絕”？XGBoost之所以能叫XGBoost，因為她夠“絕”（夠Extreme）。XGBoost和Gradient Boosting Machines（GBMs）都是基於決策樹的集合方法，透過梯度下降架構來提升較弱學習者（通常是CARTs）。透過系統最佳化和演算法增強，XGBoost進一步改進了基礎GBM框架。

XGBoost 如何最佳化GBM 標準演算法

系統最佳化：

1. 並行化：

XGBoost透過多執行緒實現了迴歸樹的並行構建。由於用於構建基礎學習者的迴圈具有可互換性，因此設計並行是可能的。外部迴圈列舉樹的節點，內部迴圈則計算特徵。這種迴圈巢狀在一定程度上限制了並行化，當沒有完成內部迴圈，外部迴圈就無法啟動。因此，為改善執行時間，可透過對所有例項的全域性掃描實現初始化，使用並行執行緒分類來交換迴圈順序。這一交換透過抵消計算中的並行化開銷，提高演算法效能。

2. 決策樹剪枝：

當剪枝分裂遇到一個負損失時，GBM會停止分裂。因此GBM實際上是一個貪心演算法（只求達到區域性最優解就ok）。但XGBoost會一直分裂到指定的最大深度(max_depth)，然後回過頭來剪枝。這種“深度優先”方法顯著提高了計算效能。

3.硬體最佳化：

該演算法旨在有效利用硬體資源。透過在每個執行緒中分配內部緩衝區，儲存梯度統計資訊，獲取快取感知。諸如“核外”計算等進一步增強功能可最佳化可用磁碟空間，同時處理不適合儲存的大資料幀。

演算法增強：

1. 正則化：

透過LASSO（L1）和Ridge（L2）正則化來對更為複雜的模型進行懲罰，防止過度擬合。

2. 稀疏性感知：

XGBoost具有稀疏性的離散特徵，根據訓練缺失自動“學習”最佳缺失值，並且可以更有效率地處理資料中不同型別的稀疏模式。

3. 加權分位數草圖：

XGBoost採用分散式加權分位數草圖演算法，有效地找到加權資料集中的最佳分裂點。

4. 交叉驗證：

在每次迭代時，該演算法都有內建的交叉驗證方法，無需顯式地對搜尋進行程式設計或明確在指定單次執行中所需的增強迭代數量。有何證據？我們使用Scikit-learn的“Make_Classification”資料包建立了一個包含20類特徵（2類資訊型和2類冗餘型）的100萬個資料點的隨機樣本。我們測試了幾種演算法，如邏輯迴歸、隨機森林、標準Gradient Boosting和XGBoost。

使用SKLearn的Make_Classification資料集比較XGBoos與其他機器學習演算法如上圖所示，與其他演算法相比，XGBoost模型是兼顧預測效能和處理時間的最佳預測方式。其他嚴格的基準研究也產生相同結果。正因如此，XGBoost在最近的資料科學競賽中被廣泛使用。如有疑問，請使用XGBoost。——Kaggle網站上Avito Context Ad Click Prediction競賽的獲獎者OwenZhang

XGBoost的未來儘管就目前而言，XGBoost的王座還難以撼動。但機器學習這一領域的學者大都比較活躍，而且不畏權貴，一心戀戰。目前已有幾種據說可以匹敵XGBoost的新演算法框架被提出，比如微軟研究中心新發布的LightGBM框架和Yandex Technology開發的CatBoost框架。

每當NIPS/ICML/KDD等頂級會議上一有新的演算法被提出，最忙活的可能就是資料科學家了。資料科學家們必須測試所有可能的資料演算法，以保證最終選擇的演算法是最佳的。

此外，選擇正確的演算法還遠遠不夠，還必須透過不斷調整超引數，正確對演算法資料集進行配置。

此外，如何選擇最佳的演算法還有其他幾個值得考慮的因素，例如演算法的計算複雜度、可解釋性以及實現的難易程度。而這正是機器學習開始從科學走向藝術的時刻。歷史的車輪總是在不斷向前滾動。XGBoost的鐵王座早就被許多人覬覦垂涎，開發一個優於XGBoost的更強大的模型框架只是時間上的早晚問題。然而，在強大的挑戰者出現之前，XGBoost將繼續統治機器學習的世界！

我們一起分享AI學習與發展的乾貨