本文包含

  • xgboost在gbdt基礎上的重要改進
  • xgboost的缺點
  • LightGBM在gbdt上的差異化實現
  1. 直方圖演算法 （從源碼角度詳細解讀）
  2. leaf-wise

本文不包含

  • gbdt的詳細訓練過程
  • 各種框架優化的原理論證

xgboost 和 LightGBM是gbdt的兩種實現框架。在項目實踐和面基中都是經常碰到的。

gbdt是boosting方式訓練的base model，而xgboost在gbdt基礎做出眾多改進，使得它成為業界的一大殺器。前人已經做了整理，這裡直接引用（由於未能找到原始出處，這裡沒能指出具體引用源，若有侵權，請郵件聯繫）

1.傳統GBDT以CART作為基分類器，xgboost還支持線性分類器，這個時候xgboost相當於帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。

2.傳統GBDT在優化時只用到一階導數信息，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。順便提一下，xgboost工具支持自定義代價函數，只要函數可一階和二階求導。

3.Xgboost在代價函數里加入了正則項，用於控制模型的複雜度。正則項里包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和。

從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過擬合，這也是xgboost優於傳統GBDT的一個特性。4.Shrinkage（縮減），相當於學習速率（xgboost中的eta）。xgboost在進行完一次迭代後，會將葉子節點的權重乘上該係數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間。實際應用中，一般把eta設置得小一點，然後迭代次數設置得大一點。（補充：傳統GBDT的實現也有學習速率）5.列抽樣（column subsampling）。xgboost借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算，這也是xgboost異於傳統gbdt的一個特性。

6.缺失值的處理。對於特徵的值有缺失的樣本，xgboost可以自動學習出它的分裂方向。

7.xgboost工具支持並行。預先對數據進行了排序，然後保存為block結構，後面的迭代中重複地使用這個結構，大大減小計算量。這個block結構也使得並行成為了可能，在進行節點的分裂時，需要計算每個特徵的增益，最終選增益最大的那個特徵去做分裂，那麼各個特徵的增益計算就可以開多線程進行。8.可並行的近似直方圖演算法。樹節點在進行分裂時，我們需要計算每個特徵的每個分割點對應的增益，即用貪心法枚舉所有可能的分割點。當數據無法一次載入內存或者在分散式情況下，貪心演算法效率就會變得很低，所以xgboost還提出了一種可並行的近似直方圖演算法，用於高效地生成候選的分割點。

xgboost做出的改進也並不是完美的。例如上面的第七點，關於並行計算的改進。由於pre sort的方式，不僅要保存原始的特徵值，而且還需要保存排序的結果，造成了兩倍的內存開支。另外，level-wise的葉子分裂方式，對同一層的所有節點，無區別的進行分裂，造成了極大的計算消耗。

LightGBM是另一種boosting方式的實現框架，在Higgs數據集上表現強勁。模型訓練時間花費是xgboost的1/10，內存是xgboost的1/6, 同時模型的準確率還得到了提升。更多對比結果詳見參考文獻

LightGBM在boosting上做出的改進，主要也是針對了xgboos的顯著問題，進行內存優化和時間開銷優化。與一般的分析lightgbm和xgboost的方式不同，本文著眼於lightgbm的源代碼，希望可以給出更為透徹的解析。

直方圖演算法

直方圖演算法的基本思想是先把連續的浮點特徵值離散化成k個整數，同時構造一個寬度為k的直方圖。在遍曆數據的時候，根據離散化後的值作為索引在直方圖中累積統計量，當遍歷一次數據後，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點。

很明顯，在對特徵進行離散化之後，對當前節點進行分割的時間複雜度從O(#data*#feature)優化到O(k*#features)。

針對lightgbm如何進行bins，下面進行解析。首先我將給出讀了源碼後，總結的實現流程。後面大家可以順著源碼，自己走一遍，把流程順一下。

一句話小結：每個特徵根據無重複特徵值的數量是否大於bins限制，分為兩種情況。如果<max_bins，直接無重複特徵排序後，取兩兩特徵值的平均作為劃分點；如果>max_bins，當前特徵值計數超過mean_bin_size（#data/max_bins）的單獨成桶，其他的在桶內數量超過mean_bin_size或者下一個特徵值計數計數超過mean_bin_size，分為一個桶。

偽代碼分析
"""
下面所有變數針對一個具體特徵而言
max_bin 預設的最大桶數
counts特徵取值計數的數組
distinct_values為特徵的不同的取值的數組
num_distinct_values; 無重複特徵value的數量。
rest_bin_cnt 剩下待劃分的桶數
rest_sample_cnt 剩下待劃分的樣本數
mean_bin_size = rest_sample_cnt / rest_bin_cnt表示桶內樣本數量的期望值。
cur_cnt_inbin 當前桶內樣本數量
"""
if num_distince_values <= max_bin:
直接無重複特徵排序後，取兩兩特徵值的平均作為劃分點；
else:
初始化rest_sample_cnt, rest_bin_cnt, mean_bin_size,cur_cnt_inbin
for i in range(num_distince_values):
更新rest_sample_cnt, rest_bin_cnt, mean_bin_size,cur_cnt_inbin
if 當前特徵值計數超過mean_bin_size（#data/max_bins）的單獨成桶 || 桶內累積樣本數量超過mean_bin_size || 下一個特徵值計數計數超過mean_bin_size:
upper_bounds.append(當前特徵值)#上邊界
lower_bounds.append(下一個非重複特徵值)#下邊界
for b in bins:
bin_upper_bound.append(（上邊界+下邊界）/ 2)
return bin_upper_bound

源碼路徑github.com/microsoft/Li

std::vector<double> GreedyFindBin(const double* distinct_values, const int* counts,
int num_distinct_values, int max_bin, size_t total_cnt, int min_data_in_bin) {
std::vector<double> bin_upper_bound;
CHECK(max_bin > 0);
if (num_distinct_values <= max_bin) {
bin_upper_bound.clear();
int cur_cnt_inbin = 0;
for (int i = 0; i < num_distinct_values - 1; ++i) {
cur_cnt_inbin += counts[i];
if (cur_cnt_inbin >= min_data_in_bin) {
auto val = Common::GetDoubleUpperBound((distinct_values[i] + distinct_values[i + 1]) / 2.0);
if (bin_upper_bound.empty() || !Common::CheckDoubleEqualOrdered(bin_upper_bound.back(), val)) {
bin_upper_bound.push_back(val);
cur_cnt_inbin = 0;
}
}
}
cur_cnt_inbin += counts[num_distinct_values - 1];
bin_upper_bound.push_back(std::numeric_limits<double>::infinity());
} else {
if (min_data_in_bin > 0) {
max_bin = std::min(max_bin, static_cast<int>(total_cnt / min_data_in_bin));
max_bin = std::max(max_bin, 1);
}
double mean_bin_size = static_cast<double>(total_cnt) / max_bin;

// mean size for one bin
 int rest_bin_cnt = max_bin;
int rest_sample_cnt = static_cast<int>(total_cnt);
std::vector<bool> is_big_count_value(num_distinct_values, false);
for (int i = 0; i < num_distinct_values; ++i) {
if (counts[i] >= mean_bin_size) {
is_big_count_value[i] = true;
--rest_bin_cnt;
rest_sample_cnt -= counts[i];
}
}
mean_bin_size = static_cast<double>(rest_sample_cnt) / rest_bin_cnt;
std::vector<double> upper_bounds(max_bin, std::numeric_limits<double>::infinity());
std::vector<double> lower_bounds(max_bin, std::numeric_limits<double>::infinity());

int bin_cnt = 0;
lower_bounds[bin_cnt] = distinct_values[0];
int cur_cnt_inbin = 0;
for (int i = 0; i < num_distinct_values - 1; ++i) {
if (!is_big_count_value[i]) {
rest_sample_cnt -= counts[i];
}
cur_cnt_inbin += counts[i];
// need a new bin
 if (is_big_count_value[i] || cur_cnt_inbin >= mean_bin_size ||
(is_big_count_value[i + 1] && cur_cnt_inbin >= std::max(1.0, mean_bin_size * 0.5f))) {
upper_bounds[bin_cnt] = distinct_values[i];
++bin_cnt;
lower_bounds[bin_cnt] = distinct_values[i + 1];
if (bin_cnt >= max_bin - 1) { break; }
cur_cnt_inbin = 0;
if (!is_big_count_value[i]) {
--rest_bin_cnt;
mean_bin_size = rest_sample_cnt / static_cast<double>(rest_bin_cnt);
}
}
}
++bin_cnt;
// update bin upper bound
 bin_upper_bound.clear();
for (int i = 0; i < bin_cnt - 1; ++i) {
auto val = Common::GetDoubleUpperBound((upper_bounds[i] + lower_bounds[i + 1]) / 2.0);
if (bin_upper_bound.empty() || !Common::CheckDoubleEqualOrdered(bin_upper_bound.back(), val)) {
bin_upper_bound.push_back(val);
}
}
// last bin upper bound
 bin_upper_bound.push_back(std::numeric_limits<double>::infinity());
}
return bin_upper_bound;
}

leaf-wise的葉子分裂方式

拋棄了大多數GBDT工具使用的按層生長 (level-wise)的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise)演算法。Level-wise過一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型複雜度，不容易過擬合。但實際上Level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。

這個在實現上比較容易理解，不展開討論。至此，我們已經將lightgbm在框架設計上最重要的兩個優化點（直方圖演算法、leaf-wise葉子節點分裂）理解清楚。其他的優化點諸如：直方圖做差加速，類別特徵支持等等。感興趣可以從參考文獻入手進行拓展。

參考

msra.cn/zh-cn/news/feat

zhuanlan.zhihu.com/p/25

blog.csdn.net/anshuai_a


推薦閱讀：
相关文章