1 Boosting 方法概述
本文需要讀者有以下的前置知識儲備：決策樹算法、梯度下降法、泰勒展開式。
1.1 集成方法
集成方法（ Ensemble Learning ）是一種應用得非常廣泛的機器學習方法，主流的集成方法包括 Bagging 、 Boosting 、 Stacking 。
俗話說“三個臭皮匠，頂個諸葛亮”，這就是集成方法的思路。很多時候，我們無法直接訓練出優質的模型（強學習機），而只能得到一些較差的模型（弱學習機）。集成方法就是將多個弱學習機的預測結果綜合起來，以達到甚至是超過強學習機的預測效果。
Bagging 採用並行組合弱學習機的思路，代表算法是隨機森林（ RF ， RandomForest ）， Bagging 在降低方差方面有很好的效果。
Boosting 採用串行組合弱學習機的思路，代表算法是 XGBoost 和 LightGBM ， Boosting 在降低偏差方面有很好的效果。
本文將要介紹的是 Boosting 。
1.2 Boosting 方法
Boosting 是一種串行的集成方法，每輪迭代後算法會計算當前模型預測值和樣本實際值的差異度，下一輪迭代會針對這個差異度來繼續訓練模型。這個差異度有時也叫殘差，它可以是平方損失函數、指數損失函數（ AdaBoost ）、對數損失函數（邏輯迴歸）、 Hinge 損失函數（ SVM ），等等。
AdaBoost 算法 是早期的經典 Boosting 算法，它是前向分佈算法的一個特例。 AdaBoost 採用指數損失函數來評估差異度，指數損失函數的缺點是對於異常點非常敏感，因而在噪音比較多的數據集上經常表現不佳。
GBDT 算法 在健壯性方面做了改進：它結合了 CART 決策樹和梯度提升方法，由於 CART 樹是複雜度低的樹，所以方差很小，能夠很好地解決過擬合的問題；同時 GBDT 可以使用任何損失函數 ( 只要損失函數是一階連續可導的 ) ，這樣一些比較健壯的損失函數就能得以應用，使模型抗噪音能力得到增強。
XGBoost 和 LightGBM 是現在最流行的 Boosting 算法，它們被廣泛用於 kaggle 、天池等競賽中。 Boosting 共有的缺點是模型串行訓練，難以並行處理，這樣在數據量增大時，無法通過大數據技術提高訓練速度，而 xgb 和 lgb 在這方面做出了突破，極大地提高了訓練速度，這在後文中會詳細說明。
2 AdaBoost 算法和 GBDT 算法
第 2 節將會簡要地介紹 AdaBoost 算法和 GBDT 算法，偏重於應用而非理論的讀者，可以跳過本節。
2.1 AdaBoost 算法概述
如前文所述， AdaBoost 是一個串行算法，通過 M 輪迭代，在每輪迭代中都訓練出 1 個分類器（分類器可以根據需要，採用任意合適的模型），最後將這 M 個分類器相加，得到最終的預測模型。
在構建模型的過程中，我們需要對被錯誤預測的樣本賦予更多的關注，讓這些樣本在下一輪迭代過程中能夠更大地影響分類器模型的構建，所以我們要 提高被錯誤預測的樣本的權重 。
在最後組合模型的過程中，我們需要讓預測效果更好的模型，起到更大的作用，以提高最終模型的預測效果，所以我們要 提高預測效果好的分類器的權重 。
以上兩點，就是 AdaBoost 在構建模型的過程中，需要遵循的思路。
2.2 AdaBoost 算法流程
我們利用 AdaBoost 算法，對一個包含有 N 個樣本的數據集，進行 M 輪迭代，構建預測模型。
其中，表達式的下標 m 表示迭代的次數，下標 i 表示樣本標號。
算法流程如下：
（ 1 ）初始化樣本權重，將每個樣本的權重 w 設置為 1/N 。
（ 2 ）進行 M 次循環迭代，依次求得 M 個分類器
（ 2.1 ）通過計算，獲取此次迭代的最優分類器（根據實際需要，採用合適的分類模型） :
（ 2.2 ）計算此次迭代分類器的誤差：
（ 2.3 ）計算此次迭代分類器的權重：
如此設置分類器權重的思路是：在構建最終模型時，要對 M 個分類器加權相加，為了得到更好的分類效果，就要賦予誤差低的分類器高權重，賦予誤差高的分類器低權重。
（ 2.4 ）更新樣本的權重：
如此設置樣本權重的思路是：為了能夠讓被錯誤分類的樣本，在下一輪迭代中對分類器的構建產生更大的影響，從而達到糾正錯誤的目的，就需要賦予被錯誤分類的樣本高權重，賦予被正確分類的樣本低權重。
最後對樣本權重進行歸一化：
歸一化的目的是：保證所有樣本的權重和為 1 。
（ 3 ）最後，將所有分類器加權求和，獲得最終分類器：
2.3 前向分佈算法流程
前向分佈算法比 AdaBoost 算法更為簡潔，我們可以通過學習前向分佈算法，進一步瞭解 Boosting 算法的思路。
另外，可以證明， AdaBoost 算法是前向分佈算法的一個特例（證明過程見李航《統計學習方法》 8.3.2 ）。
前向分佈算法流程如下，其中表達式的下標 m 表示迭代的次數（一共迭代 M 次），下標 i 表示樣本標號（一共有 N 個樣本）：
（ 0 ）記損失函數為：
並初始化：
（ 1 ）進行 M 次循環迭代，依次求得 M 個分類器（求得分類器的參數和權重）
（ 1.1 ）求解最優化問題，通過極小化損失函數，求得 β 和 γ ：
（ 1.2 ）根據求得的 β 和 γ ，更新 f(x) ：
（ 2 ）整理得到最終模型：
2.4 GBDT 算法概述
AdaBoost 算法使用指數損失函數作為損失函數，所以求解最優化問題的過程較為簡單，與之類似還有平方損失函數。但是，如果採用其它損失函數， 求解最優化問題就有可能較為困難 。
為了解決這個問題，同時也為了能夠採用一些更健壯的損失函數以 減小異常點 的影響，我們 採用損失函數的梯度作為殘差 。我們可以採用任意損失函數，只要這個損失函數一階可導。
由於 CART 樹模型較為簡單 ， GBDT 算法利用 CART 樹作為基本學習機，這樣能夠彌補 Boosting 算法方差較高的缺點。
2.5 GBDT 算法流程
我們要利用 GBDT 算法，對一個包含有 N 個樣本的數據集，進行 M 輪迭代，構建預測模型。
其中，表達式的下標 m 表示迭代的次數，下標 i 表示樣本標號。
算法流程如下：
（ 1 ）初始化 f(x) , 並記為 T0(x) ：
（ 2 ）進行 M 次循環迭代，依次求得 M 個決策樹。
（ 2.1 ）遍歷所有樣本，對每個樣本的損失函數求導，記為樣本的殘差：
（ 2.2 ）將所有樣本的值，替換成殘差。
（ 2.3 ）以所有樣本的新值（殘差）為訓練樣本，訓練並輸出決策樹模型：
其中，每個葉子節點輸出的值 w 為
在這裡， w 不是一個常數，在不同的葉子節點區域， w 取不同的常數值。
在這一步中，需要求得決策樹模型兩方面的內容，一是決策樹的結構（使用哪些特徵進行分割，分割點的值是多少），二是葉子節點的輸出值。
（ 2.4 ）根據 T(x,w) ，更新 f(x)
（ 3 ）最後，整理輸出最終的 GBDT 模型
3 XGBoost 算法
3.1 概述
Boosting 算法最大的缺點有兩個：一是方差過高，容易過擬合；二是模型的構建過程是串行的，難以應用於大數據場景。這兩個問題在 XGB 算法中，都得到了很大的改善。
過擬合的問題還算好解決，很多類似的研究結論都可以被拿來借鑑。所以，在我看來， XGB 最大的貢獻，就是創造性地給出了 Boosting 算法的並行計算思路，使之能夠適應大數據場景，應用於大數據分佈式集群環境中。
下面，我們將先學習 XGB 算法，然後對它的特性進行歸納總結。
3.2 目標函數
要構建一個模型，我們首先要確定要以什麼目標來衡量模型的好壞，然後再圍繞這個目標，一步步地改進模型。所以，在 XGB 算法中，我們要先確定算法的目標函數。隨後， XGB 模型的構建，就是以實現這個目標函數最小化為目標。
XGBoost 的目標函數包括損失函數和正則項兩個部分。
損失函數 衡量的是模型輸出值和樣本真實值的差異度，差異度的值越低，模型越好。
正則項 衡量的是模型的複雜度，複雜度越高，模型越容易過擬合，所以正則項的值越低，模型越好。
如下式所示，第一項 L(y,y’) 表示的是模型的損失函數，第二項 Ω( δ ) 表示的是模型的正則項。
其中 f(x) 表示前 m 次迭代生成模型之和， δ (x) 表示當前迭代輪次生成的模型，表達式的下標 m 表示迭代的次數（一共迭代 M 次），下標 i 表示樣本標號（一共有 N 個樣本），下標 j 表示葉子節點標號（一共有 T 個葉子結點）：
將損失函數進行泰勒展開，並且記 g(x) 為 L(y,y’) 的一階導數， h(x) 為 L(y,y’) 的二階導數：
（注： g(x) 和 h(x) 均為損失函數 L(y,y’) 對變量 y’ 的求導，此時 y 為常數）
正則項表示如下，其中 T 表示葉子節點的個數， w 表示葉子節點的輸出值
注：本文中使用的是 L2 範數。在 XGB 的實際應用中，可以使用 L1 範數。
最後，代入以上損失函數和正則項的表達式（第 2 行），刪除常數項（第 3 行），最後按葉子節點彙總（第 4 、 5 行），可得：
其中 Tj 表示屬於不同葉子節點（模型輸出的預測值，而非真實值）的樣本的集合。 i ∈ Tj 表示經過當前迭代輪次模型的預測，第 i 個樣本被分到葉子節點 j 處。
確定了目標函數，下一步就是構建決策樹模型。決策樹模型的構建包括兩個方面：一是要確定決策樹模型的結構，包括每個節點使用什麼特徵進行分割，分割點的值是多少；二是要確定每個葉子節點的輸出值。
接下來的兩個小節，將分別通過計算葉子節點的輸出值和進行節點分裂判定，來完成對決策樹模型的構建。
3.3 計算葉子節點輸出值
我們先假設決策樹的結構已經被確定了，那麼在這個前提條件下，我們嘗試計算葉子節點的最優輸出值。
觀察目標函數：
最後一項 γ T 只與決策樹的結構有關，在結構確定的情況下是常數，可以忽略。
第一大項可以按葉子節點 j 進行分解，分解後的子項互不相關。所以可以根據以下表達式，按葉子節點 j 進行劃分，各自單獨求解 w 的最優值：
顯而易見的，這是一個一元二次多項式， w 的最優解為：
其中，為便於書寫和記憶，記：
3.4 節點分裂判定
在求得葉子節點的最優輸出值後，我們接下來求解決策樹的結構。
由於樹的組成結構有無窮多種，我們無法窮舉遍歷所有的情況，所以我們採用貪婪算法，在每個節點都進行一次判定，決定是否該分裂這個節點，以及該如何分裂這個節點，以此逐步迭代構成一棵決策樹。
我們先將上一節求得的 w 的最優解代入目標函數，可以得到目標函數的表達式：
當我們判定一個葉子節點是否需要分裂時，需要計算分裂操作執行前後，目標函數的變化情況。記待分裂節點為 t 。
分裂前整棵樹的代價函數：
分裂後整棵樹的代價函數：
將以上兩式相減，可得：
這個式子即為是否分裂節點的判別公式。如果該式大於 0 ，則表示目標函數的值減少了，分裂是有增益效果的，可以分裂。如果該式小於 0 ，則表示分裂後的目標函數反而增加了，則不建議分裂。
注：
在單機版的 XGB 算法中，使用的是精準貪婪節點分裂算法。算法會遍歷所有特徵的所有值，以判定：是否分裂、如果分裂的話採用哪個特徵進行分裂、分裂點選取為什麼數值。
在數據無法全部放到內存中的場合，或者在分佈式應用的場合， XGB 使用近似節點分裂算法。 XGB 首先根據樣本數據的百分位分佈計算出備選分割點，然後將連續的樣本數據分配到由這些備選分割點確定的桶（ bucket ）裡，最後彙總數據（不同分佈式集群上的數據、或不同處理線程上的數據），並求出最優分割點。
3.5 XGBoost 算法流程
在這一小節，我對前面幾個小節得出的結論進行整理，歸納出 XGBoost 的算法流程。
其中， f(x) 表示前 m 次迭代生成模型之和， δ (x) 表示當前迭代輪次生成的模型，表達式的下標 m 表示迭代的次數（一共迭代 M 次），下標 i 表示樣本標號（一共有 N 個樣本），下標 j 表示葉子節點標號（一共有 T 個葉子節點）：
（ 1 ）根據實際場景需求，設計損失函數 L(y,y’) 和正則項 Ω( δ ) 。進行 f0(x) 的初始化 。
（ 2 ）進行 M 次循環迭代，依次求得 M 個決策樹。
（ 2.1 ）在每次迭代開始前，遍歷所有樣本，計算所有樣本的損失函數 L(y,y’) 關於 y’ 的一階導數 g 和二階導數 h 。
（ 2.2 ）使用以下表達式，進行節點分裂判定。逐步迭代生成樹，以確定決策樹結構：
表達式大於 0 則可以分裂，小於 0 則不建議分裂。
（ 2.3 ）決策樹結構確定後，根據下式，計算當前迭代輪次決策樹的葉子節點輸出值：
（ 2.4 ）根據當前迭代輪次生成的決策樹 δ (x) ，更新模型 f(x) ：
（ 3 ）整理輸出最終的 XGBoost 模型：
在接下來的幾個小節裡，我將會對 XGB 的特性進行歸納總結，包括前文提及的過擬合預防方法、大數據場景實現方法、以及其它的一些特性。
3.6 大數據場景實現方法
（ 1 ）樣本間並行計算：在每次迭代前，需要遍歷所有樣本，求解損失函數的一次導數 g 和二次導數 h ，由於不同樣本間無相關性，故此時可以對不同的樣本使用並行計算。
（ 2 ）特徵間並行計算：在進行節點分裂判定時，需要遍歷所有特徵，此時可以對不同的特徵使用並行計算，最後再彙總不同特徵的判定結果，輸出最優解。
（ 3 ）預排序：在每次迭代前，事先將樣本數據按照不同的特徵，根據其數值進行預排序，方便後續在節點分裂判定環節，順序訪問樣本數據，對一階導數和二階導數進行取數和累加。（注：在構建樹的過程中，耗時最長的步驟，就是對樣本數據進行排序）
（ 4 ）塊壓縮技術 (Block Compression) ：按列（特徵）對數據進行壓縮，在數據被讀取入內存時，通過一個額外的線程進行解壓。這個技術是將磁盤讀寫的時間耗費，轉嫁到內存解壓縮的時間耗費上。
（ 5 ）塊共享技術 (Block Sharding) ：將數據存儲到不同的磁盤上，通過額外的線程預讀取數據，將數據提前讀取到不同磁盤各自的內存緩衝區裡，在需要的時候，再將數據送到模型訓練線程中。這個技術減小了磁盤讀寫的時間耗費。
（ 6 ）數據預讀取：建立一個獨立的線程，在模型執行運算操作的同時，用這個線程向磁盤讀取後續需要用到的數據。但是，由於程序在計算模型時常常也要讀寫磁盤，所以這個方法未必很有效。
（ 7 ）構建樹的算法包括精確貪婪算法和近似算法（直方圖算法），近似算法對每維特徵按照分位數進行分桶 (bucket) 。
3.7 過擬合預防方法
（ 1 ）學習效率參數 shrinkage ：類似於其它算法的學習效率參數 LearningRate 。
（ 2 ）引入正則項：包括樹的葉子節點數量，葉子節點輸出值的 L1 或 L2 範數。
（ 3 ）列（特徵）採樣：在迭代時只使用一部分特徵來構建模型。列採樣不僅縮短了計算時間，還提高了模型的預測效果。列採樣方法源自於隨機森林算法。
（ 4 ）行（樣本）採樣：在迭代時只使用一部分樣本來構建模型。
3.8 其它特性
（ 1 ）自定義目標函數： XGB 可以自定義目標函數，只需要目標函數滿足二次可導。
（ 2 ）基分類器：不僅可以採用 CART 樹作為基分類器（本文中默認使用 CART 樹），也可以使用線性模型。
（ 3 ）分裂準則：節點分裂時，能夠直接根據目標函數（損失函數 + 正則項）進行判定。
（ 4 ）有效處理缺失值和稀疏值：對於特徵值缺失或特徵值稀疏的樣本，分別嘗試將缺失 \\ 稀疏數據劃分到左葉子和右葉子，計算增益並進行對比，選擇增益更大的劃分方案。
（注：產生稀疏矩陣的三個常見原因：數據缺失，數據本身含有大量零值，使用了 one-hot 方法。）
（ 5 ） XGBoost 允許在每一輪 boosting 迭代中使用交叉驗證。因此，可以方便地獲得最優 boosting 迭代次數。而 GBDT 只能使用網格搜索（ Grid Search ）檢測有限個值。
（ 6 ）支持加權數據：陳天奇在論文裡提了一下，但是沒給出具體算法。
[1] Tianqi Chen AScalable Tree Boosting System
[2] Tianqi Chen Introductionto Boosted Trees
[3] 李航 統計學習方法 清華大學出版社
閱讀更多 sandag 的文章
