XGBoost 是 eXtreme Gradient Boosting 的縮寫稱呼，它是一個非常強大的 Boosting 算法工具包，優(yōu)秀的性能（效果與速度）讓其在很長一段時間內(nèi)霸屏數(shù)據(jù)科學比賽解決方案榜首，現(xiàn)在很多大廠的機器學習方案依舊會首選這個模型。 XGBoost 在并行計算效率、缺失值處理、控制過擬合、預測泛化能力上都變現(xiàn)非常優(yōu)秀。本文我們給大家詳細展開介紹 XGBoost，包含『算法原理』和『工程實現(xiàn)』兩個方面。
1.算法原理可視化解讀關于XGBoost的原理，其作者陳天奇本人有一個非常詳盡的 Slides 做了系統(tǒng)性的介紹，我們在這里借助于這個資料給大家做展開講解。(鏈接見文末) 1）監(jiān)督學習中的一些重要概念在開始介紹Boosted Tree之前，我們先來回顧一下機器學習中的一些重要的概念。 （1）監(jiān)督學習核心要素 符號（Notations）： 表示訓練集中的第 個樣本。 模型（Model）：對于已知的 如何預測 ？ 線性模型（Linear Model） （包括線性回歸和邏輯回歸），預測值 根據(jù)不同的任務有不同的解釋：
 參數(shù)（Parameters）：需要從數(shù)據(jù)中學習的東西。
目標函數(shù)（Objective function）
訓練數(shù)據(jù)損失函數(shù)（Training Loss）
正則化項（Regularization）：描述了模型的復雜程度。
（2）監(jiān)督學習進階知識 Ridge回歸：
Lasso：
邏輯回歸（Logistic Regression）：
（3）目標函數(shù)及偏差方差權衡回顧一下目標函數(shù) ，為什么目標函數(shù)需要兩部分組成呢？ 
2）回歸樹（Regression Tree）和集成（Ensemble）（1）回歸樹（Regression Tree）回歸樹，也就是分類回歸樹（Classification and Regression Tree）（詳情請查看ShowMeAI文章回歸樹模型詳解）
（2）回歸樹集成（Regression Tree Ensemble） 從上圖的左圖可以看出，共有 個訓練樣本。 從上圖的中圖可以看出，每個葉子節(jié)點都有預測值：第一個葉子結點的預測值是 ，第二個葉子結點的預測值是 ，第三個葉子結點的預測值是 。
最終的預測值就是樣本在每顆樹中所在的葉子結點的預測值的和。 （3）樹集成方法樹集成的方法使用非常廣泛，像GBM、隨機森林等（詳見ShowMeAI文章 圖解機器學習 | GBDT模型詳解 和 圖解機器學習 | 隨機森林分類模型詳解）。多達半數(shù)的數(shù)據(jù)挖掘競賽通過使用各種各樣的樹集成方法而獲勝。
（4）Boosted Tree的模型和參數(shù) 模型：假設我們有K棵樹： 。其中，F(xiàn)為包含所有回歸樹的函數(shù)空間。
參數(shù)：包括每棵樹的結構和葉子結點中的分數(shù)。或者使用函數(shù)當作參數(shù)： 。
（5）在單變量上學習Boosted Tree單變量也就是單個特征，通過了解如何在單變量上學習Boosted Tree，我們可以對Boosted Tree的學習模式有個簡單的概念。 舉例：假設回歸樹只有一個輸入變量t（時間），希望預測小哥在t時刻有多喜歡浪漫音樂。 
為了構建上右圖的樹，我們需要學習兩個東西：
 單變量回歸樹的目標（階躍函數(shù)）
（6）一般情形的Boosted Tree首先回顧上面我們對Boosted Tree的定義： 模型：假設我們有K棵樹： 目標函數(shù)：
當我們討論樹的時候，通常是啟發(fā)式的： 
大多數(shù)啟發(fā)式算法都能很好地映射到目標函數(shù)，采用形式（目標）視圖讓我們知道我們正在學習什么：
回歸樹集成定義了如何得到預測值，它不僅僅可以做回歸，同樣還可以做分類和排序。具體做什么任務依賴于『目標函數(shù)』的定義：
3）Gradient Boosting（如何學習）在這一節(jié)中我們將正式學習Gradient Boosting。這里，xgboost的處理大家可以對比GBDT模型（可參考ShowMeAI文章 圖解機器學習 | GBDT模型詳解）來理解核心差異。 （1）解決方案目標函數(shù)： 在做GBDT的時候，我們沒有辦法使用SGD，因為它們是樹，而非數(shù)值向量——也就是說從原來我們熟悉的參數(shù)空間變成了函數(shù)空間。
解決方案：初始化一個預測值，每次迭代添加一個新函數(shù)（ ）：
（2）目標函數(shù)變換第一步：根據(jù)上面的公式，目標函數(shù)可以做如下變形 這里我們考慮平方損失，此時目標函數(shù)又可以變形為： 第二步：所以我們的目的就是找到 使得目標函數(shù)最低。然而，經(jīng)過上面初次變形的目標函數(shù)仍然很復雜，目標函數(shù)會產(chǎn)生二次項。 在這里我們引入泰勒展開公式：
目標函數(shù)利用泰勒展開式就可以變成： 第三部：把常數(shù)項提出來，目標函數(shù)可以簡化為 思考：為什么要做這么多變化而不直接生成樹？
（3）重新定義樹在前面，我們使用 代表一顆樹，在本小節(jié)，我們重新定義一下樹：我們通過葉子結點中的分數(shù)向量和將實例映射到葉子結點的索引映射函數(shù)來定義樹：（有點兒抽象，具體請看下圖）
從上圖可以看出，共有3個葉子結點，第一個葉子結點的權重為+1，第二個葉子結點的權重為0.1，第三個葉子結點的權重為-1；其中，小男孩屬于第1個葉子結點，老奶奶屬于第3個葉子結點。 （4）定義樹的復雜程度通過下面的式子定義樹的復雜程度（定義并不是唯一的）
（5）重新審視目標函數(shù)定義在葉子結點 中的實例的集合為： 根據(jù)每棵葉子重新定義目標函數(shù)：
（6）計算葉子結點的值一些知識需要先了解。對于一元二次函數(shù)： ，我們很容易得到這個函數(shù)的最小值和最小值對應的 。
也就是： 如何求葉子結點最優(yōu)的值？接著繼續(xù)變化目標函數(shù)：
假設樹的結構 是固定的，那么每一個葉子結點的權重的最優(yōu)值為 目標函數(shù)的最優(yōu)值為 下圖是前面公式講解對應的一個實際例子。 這里再次總結一下，我們已經(jīng)把目標函數(shù)變成了僅與 這五項已知參數(shù)有關的函數(shù)，把之前的變量 消滅掉了，也就不需要對每一個葉子進行打分了！ 那么現(xiàn)在問題來，剛才我們提到，以上這些是假設樹結構確定的情況下得到的結果。但是樹的結構有好多種，我們應該如何確定呢？ （7）貪婪算法生成樹上一部分中我們假定樹的結構是固定的。但是，樹的結構其實是有無限種可能的，本小節(jié)我們使用貪婪算法生成樹：
接下來要考慮的是如何尋找最佳分裂點。 例如，如果 是年齡，當分裂點是 的時候的增益 是多少？ 我們需要做的僅僅只是計算每一邊的 和 ，然后計算 對排序后的實例進行從左到右的線性掃描就足以決定特征的最佳分裂點。 所以，分裂一個結點的方法是：
時間復雜度：
（8）如何處理分類型變量一些樹學習算法分別處理分類變量和連續(xù)變量，我們可以很容易地使用我們推導出的基于分類變量的評分公式。但事實上，我們沒有必要單獨處理分類變量： 我們可以使用 one-hot 方式處理分類變量： 如果有太多的分類的話，矩陣會非常稀疏，算法會優(yōu)先處理稀疏數(shù)據(jù)。 （9）修剪和正則化回顧之前的增益，當訓練損失減少的值小于正則化帶來的復雜度時，增益有可能會是負數(shù)： 此時就是模型的簡單性和可預測性之間的權衡。
2.XGBoost核心原理歸納解析1）目標函數(shù)與泰勒展開XGBoost也是一個Boosting加法模型，每一步迭代只優(yōu)化當前步中的子模型。 第 步我們有：
目標函數(shù)設計為『經(jīng)驗風險』+『結構風險』（正則項）：
在數(shù)學中，我們可以用泰勒公式近似 ，具體如下式。XGBoost對損失函數(shù)運用二階展開來近似。
對應 XGBoost 的損失函數(shù)，我們在上式里將 視作 ， 視作 ， 視作關于 的函數(shù)，得到： 又因前 個子模型已經(jīng)確定了，故上式中除了關于 的部分都是常數(shù)，不影響對 的優(yōu)化求解。目標函數(shù)可轉化為：
2）XGBoost的正則化實際上，XGBoost的基分類器對決策樹和線性模型都支持，這里我們只討論更常見的『基于樹』的情況。為防止過擬合，XGBoost設置了基于樹的復雜度作為正則項：
作為回歸樹，葉子節(jié)點越多、輸出的回歸值越大，樹的復雜度越高。 最終目標函數(shù)如下： 下面是一個數(shù)學轉換處理，為了使正則項和經(jīng)驗風險項合并到一起。我們把在樣本層面上求和的經(jīng)驗風險項，轉換為葉節(jié)點層面上的求和。 定義節(jié)點 上的樣本集為 ，其中 為將樣本映射到葉節(jié)點上的索引函數(shù)，葉節(jié)點 上的回歸值為 。 進一步簡化表達，令 ， 注意這里 和 都是關于 的函數(shù)： 轉化到這個形式后，我們可以看出，若一棵樹的結構已經(jīng)確定，則各個節(jié)點內(nèi)的樣本 也是確定的，即 ， 、 被確定，每個葉節(jié)點輸出的回歸值應該使得上式最小，由二次函數(shù)極值點： 按此規(guī)則輸出回歸值后，目標函數(shù)值也就是樹的評分如下公式，其值越小代表樹的結構越好。觀察下式，樹的評分也可以理解成所有葉節(jié)點的評分之和： 3）節(jié)點分裂準則我們之前文章決策樹模型詳解里給大家講到了決策樹模型是遞歸生長形成的，而XGBoost的子模型樹也一樣，需要要依賴節(jié)點遞歸分裂的貪心準則來實現(xiàn)樹的生成。 （1）貪心準則XGBoost子樹的基本處理思路和CART一樣，會對特征值排序后遍歷劃分點，將其中最優(yōu)的分裂收益作為該特征的分裂收益，選取具有最優(yōu)分裂收益的特征作為當前節(jié)點的劃分特征，按其最優(yōu)劃分點進行二叉劃分，得到左右子樹。 上圖是一次節(jié)點分裂過程，很自然地，分裂收益是樹 A 的評分減去樹B的評分。虛線框外的葉節(jié)點，即非分裂節(jié)點的評分均被抵消，只留下分裂后的 LR 節(jié)點和分裂前的 S 節(jié)點進行比較，因此分裂收益的表達式為： （2）近似算法基于性能的考量，XGBoost還對貪心準則做了一個近似版本，簡單說，處理方式是『將特征分位數(shù)作為劃分候選點』。這樣將劃分候選點集合由全樣本間的遍歷縮減到了幾個分位數(shù)之間的遍歷。 展開來看，特征分位數(shù)的選取還有global和local兩種可選策略：
這兩種情況里，由于 global 只能劃分一次，其劃分粒度需要更細。 XGB 原始 paper 中對 Higgs Boson 數(shù)據(jù)集進行了實驗，比較了精確貪心準則、global 近似和 local 近似三類配置的測試集 AUC，用 eps 代表取分位點的粒度，如 代表將數(shù)據(jù)集劃分為 個 buckets，發(fā)現(xiàn) global（）和 local（）均能達到和精確貪心準則幾乎相同的性能。 XGBoost工具包支持上述提到的3類配置。 （3）加權分位數(shù)查看目標函數(shù) ，令偏導為易得 ，此目標函數(shù)可理解為以 為權重， 為標簽的二次損失函數(shù)： 在近似算法取分位數(shù)時，實際上XGBoost會取以二階導 為權重的分位數(shù)（Weighted Quantile Sketch），如下圖表示的三分位。 4）列采樣與學習率XGBoost為了進一步優(yōu)化效果，在以下2個方面進行了進一步設計： 列采樣
學習率
5）特征缺失與稀疏性XGBoost也能對缺失值處理，也對特征稀疏問題（特征中出現(xiàn)大量的0或one-hot encoding結果）做了一些優(yōu)化。XGBoost用『稀疏感知』策略來同時處理這兩個問題：
依然通過遍歷得到分裂節(jié)點，NA的方向有兩種情況，在此基礎上對非缺失值進行切分遍歷。 如上圖所示，若某個特征值取值為1，2，5和大量的NA，XGBoost會遍歷以上6種情況（3個非缺失值的切分點×缺失值的兩個方向），最大的分裂收益就是本特征上的分裂收益，同時，NA將被分到右節(jié)點。 3.XGBoost工程優(yōu)化1）并行列塊設計XGBoost將每一列特征提前進行排序，以塊（Block）的形式儲存在緩存中，并以索引將特征值和梯度統(tǒng)計量對應起來，每次節(jié)點分裂時會重復調(diào)用排好序的塊。而且不同特征會分布在獨立的塊中，因此可以進行分布式或多線程的計算。 2）緩存訪問優(yōu)化特征值排序后通過索引來取梯度 會導致訪問的內(nèi)存空間不一致，進而降低緩存的命中率，影響算法效率。為解決這個問題，XGBoost為每個線程分配一個單獨的連續(xù)緩存區(qū)，用來存放梯度信息。 3）核外塊計算數(shù)據(jù)量非常大的情形下，無法同時全部載入內(nèi)存。XGBoost將數(shù)據(jù)分為多個blocks儲存在硬盤中，使用一個獨立的線程專門從磁盤中讀取數(shù)據(jù)到內(nèi)存中，實現(xiàn)計算和讀取數(shù)據(jù)的同時進行。 為了進一步提高磁盤讀取數(shù)據(jù)性能，XGBoost還使用了兩種方法：
4.XGBoost vs GBDT我們對之前講解過的GBDT（參考ShowMeAI文章 GBDT算法詳解）和這里的XGBoost做一個對比總結：
鏈接整理
|
|
|
