1.1.4 加權分位數縮略圖

事實上， XGBoost 不是簡單地按照樣本個數進行分位，而是以二階導數值 作為樣本的權重進行劃分，如下：

那么問題來了：為什么要用 進行樣本加權？

我們知道模型的目標函數為：

我們稍作整理，便可以看出 有對 loss 加權的作用。

其中 與 C 皆為常數。我們可以看到 h_i 就是平方損失函數中樣本的權重。

對于樣本權值相同的數據集來說，找到候選分位點已經有了解決方案（GK 算法），但是當樣本權值不一樣時，該如何找到候選分位點呢？（作者給出了一個 Weighted Quantile Sketch 算法，這里將不做介紹。）

1.1.5 稀疏感知算法

在決策樹的第一篇文章中我們介紹 CART 樹在應對數據缺失時的分裂策略，XGBoost 也給出了其解決方案。

XGBoost 在構建樹的節點過程中只考慮非缺失值的數據遍歷，而為每個節點增加了一個缺省方向，當樣本相應的特征值缺失時，可以被歸類到缺省方向上，最優的缺省方向可以從數據中學到。至于如何學到缺省值的分支，其實很簡單，分別枚舉特征缺省的樣本歸為左右分支后的增益，選擇增益最大的枚舉項即為最優缺省方向。

在構建樹的過程中需要枚舉特征缺失的樣本，乍一看該算法的計算量增加了一倍，但其實該算法在構建樹的過程中只考慮了特征未缺失的樣本遍歷，而特征值缺失的樣本無需遍歷只需直接分配到左右節點，故算法所需遍歷的樣本量減少，下圖可以看到稀疏感知算法比 basic 算法速度塊了超過 50 倍。

1.2 工程實現

1.2.1 塊結構設計

我們知道，決策樹的學習最耗時的一個步驟就是在每次尋找最佳分裂點是都需要對特征的值進行排序。而 XGBoost 在訓練之前對根據特征對數據進行了排序，然后保存到塊結構中，并在每個塊結構中都采用了稀疏矩陣存儲格式（Compressed Sparse Columns Format，CSC）進行存儲，后面的訓練過程中會重復地使用塊結構，可以大大減小計算量。

• 每一個塊結構包括一個或多個已經排序好的特征；
• 缺失特征值將不進行排序；
• 每個特征會存儲指向樣本梯度統計值的索引，方便計算一階導和二階導數值；

這種塊結構存儲的特征之間相互獨立，方便計算機進行并行計算。在對節點進行分裂時需要選擇增益最大的特征作為分裂，這時各個特征的增益計算可以同時進行，這也是 Xgboost 能夠實現分布式或者多線程計算的原因。

1.2.2 緩存訪問優化算法

塊結構的設計可以減少節點分裂時的計算量，但特征值通過索引訪問樣本梯度統計值的設計會導致訪問操作的內存空間不連續，這樣會造成緩存命中率低，從而影響到算法的效率。

為了解決緩存命中率低的問題，XGBoost 提出了緩存訪問優化算法：為每個線程分配一個連續的緩存區，將需要的梯度信息存放在緩沖區中，這樣就是實現了非連續空間到連續空間的轉換，提高了算法效率。

此外適當調整塊大小，也可以有助于緩存優化。

1.2.3 “核外”塊計算

當數據量過大時無法將數據全部加載到內存中，只能先將無法加載到內存中的數據暫存到硬盤中，直到需要時再進行加載計算，而這種操作必然涉及到因內存與硬盤速度不同而造成的資源浪費和性能瓶頸。為了解決這個問題，XGBoost 獨立一個線程專門用于從硬盤讀入數據，以實現處理數據和讀入數據同時進行。

此外，XGBoost 還用了兩種方法來降低硬盤讀寫的開銷：

• 塊壓縮：對 Block 進行按列壓縮，并在讀取時進行解壓；
• 塊拆分：將每個塊存儲到不同的磁盤中，從多個磁盤讀取可以增加吞吐量。

1.3 優缺點

1.3.1 優點

1. 精度更高：GBDT 只用到一階泰勒展開，而 XGBoost 對損失函數進行了二階泰勒展開。XGBoost 引入二階導一方面是為了增加精度，另一方面也是為了能夠自定義損失函數，二階泰勒展開可以近似大量損失函數；
2. 靈活性更強：GBDT 以 CART 作為基分類器，XGBoost 不僅支持 CART 還支持線性分類器，（使用線性分類器的 XGBoost 相當于帶 L1 和 L2 正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題））。此外，XGBoost 工具支持自定義損失函數，只需函數支持一階和二階求導；
3. 正則化：XGBoost 在目標函數中加入了正則項，用于控制模型的復雜度。正則項里包含了樹的葉子節點個數、葉子節點權重的 L2 范式。正則項降低了模型的方差，使學習出來的模型更加簡單，有助于防止過擬合；
4. Shrinkage（縮減）：相當于學習速率。XGBoost 在進行完一次迭代后，會將葉子節點的權重乘上該系數，主要是為了削弱每棵樹的影響，讓后面有更大的學習空間；
5. 列抽樣：XGBoost 借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算；
6. 缺失值處理：XGBoost 采用的稀疏感知算法極大的加快了節點分裂的速度；
7. 可以并行化操作：塊結構可以很好的支持并行計算。

1.3.2 缺點

1. 雖然利用預排序和近似算法可以降低尋找最佳分裂點的計算量，但在節點分裂過程中仍需要遍歷數據集；
2. 預排序過程的空間復雜度過高，不僅需要存儲特征值，還需要存儲特征對應樣本的梯度統計值的索引，相當于消耗了兩倍的內存。

LightGBM

LightGBM 由微軟提出，主要用于解決 GDBT 在海量數據中遇到的問題，以便其可以更好更快地用于工業實踐中。

從 LightGBM 名字我們可以看出其是輕量級（Light）的梯度提升機（GBM），其相對 XGBoost 具有訓練速度快、內存占用低的特點。下圖分別顯示了 XGBoost、XGBoost_hist（利用梯度直方圖的 XGBoost） 和 LightGBM 三者之間針對不同數據集情況下的內存和訓練時間的對比：

那么 LightGBM 到底如何做到更快的訓練速度和更低的內存使用的呢？

我們剛剛分析了 XGBoost 的缺點，LightGBM 為了解決這些問題提出了以下幾點解決方案：

1. 單邊梯度抽樣算法；
2. 直方圖算法；
3. 互斥特征捆綁算法；
4. 基于最大深度的 Leaf-wise 的垂直生長算法；
5. 類別特征最優分割；
6. 特征并行和數據并行；
7. 緩存優化。

本節將繼續從數學原理和工程實現兩個角度介紹 LightGBM。

2.1 數學原理

2.1.1 單邊梯度抽樣算法

GBDT 算法的梯度大小可以反應樣本的權重，梯度越小說明模型擬合的越好，單邊梯度抽樣算法（Gradient-based One-Side Sampling, GOSS）利用這一信息對樣本進行抽樣，減少了大量梯度小的樣本，在接下來的計算鍋中只需關注梯度高的樣本，極大的減少了計算量。

GOSS 算法保留了梯度大的樣本，并對梯度小的樣本進行隨機抽樣，為了不改變樣本的數據分布，在計算增益時為梯度小的樣本引入一個常數進行平衡。具體算法如下所示：

我們可以看到 GOSS 事先基于梯度的絕對值對樣本進行排序（無需保存排序后結果），然后拿到前 a% 的梯度大的樣本，和剩下樣本的 b%，在計算增益時，通過乘上 \\frac{1-a}{b} 來放大梯度小的樣本的權重。一方面算法將更多的注意力放在訓練不足的樣本上，另一方面通過乘上權重來防止采樣對原始數據分布造成太大的影響。

2.1.2 直方圖算法

1. 直方圖算法

直方圖算法的基本思想是將連續的特征離散化為 k 個離散特征，同時構造一個寬度為 k 的直方圖用于統計信息（含有 k 個 bin）。利用直方圖算法我們無需遍歷數據，只需要遍歷 k 個 bin 即可找到最佳分裂點。

我們知道特征離散化的具有很多優點，如存儲方便、運算更快、魯棒性強、模型更加穩定等等。對于直方圖算法來說最直接的有以下兩個優點（以 k=256 為例）：

• 內存占用更小：XGBoost 需要用 32 位的浮點數去存儲特征值，并用 32 位的整形去存儲索引，而 LightGBM 只需要用 8 位去存儲直方圖，相當于減少了 1/8；
• 計算代價更小：計算特征分裂增益時，XGBoost 需要遍歷一次數據找到最佳分裂點，而 LightGBM 只需要遍歷一次 k 次，直接將時間復雜度從 O(#data * #feature) 降低到 O(k * #feature) ，而我們知道 #data >> k 。

雖然將特征離散化后無法找到精確的分割點，可能會對模型的精度產生一定的影響，但較粗的分割也起到了正則化的效果，一定程度上降低了模型的方差。

2. 直方圖加速

在構建葉節點的直方圖時，我們還可以通過父節點的直方圖與相鄰葉節點的直方圖相減的方式構建，從而減少了一半的計算量。在實際操作過程中，我們還可以先計算直方圖小的葉子節點，然后利用直方圖作差來獲得直方圖大的葉子節點。

3. 稀疏特征優化

XGBoost 在進行預排序時只考慮非零值進行加速，而 LightGBM 也采用類似策略：只用非零特征構建直方圖。