AdaBoost

簡單介紹

AdaBoost是基於boosting的思想，通過多個弱分類器的線性組合來得到強分類器，訓練時重點關注被錯分的樣本，準確率高的弱分類器權重大。

更深一步的介紹

在訓練過程中，它不改變所給的訓練數據，而是不斷改變訓練數據權值的分布，使得被誤分類的數據再後一輪的分類中受到更大的關注。

同時採用加權多數表決的方法，加大分類誤差率小的弱分類器的權值，使其在最後的表決中起更大的作用，減小分類誤差率大的弱分類器的權值，使其在最後的表決中起較小的作用。所有弱分類器的權值之和並不為1，是通過最後結果的符號來決定實例的類別，該結果的絕對值表示分類的確信度。（參考《統計學習方法》P140）

Adaboost 還有另外一種理解，即可以認為其模型是加法模型、損失函數為指數函數、學習演算法為前向分步演算法的二類分類學習方法。(參考《統計學習方法》P143)

加法模型就是多個基函數線性組合得到的模型

前向分步演算法：對於加法模型，從前往後，每一步只學習一個基函數及其係數，而不是一次性學習所有的基函數，從而簡化優化的複雜度。

損失函數是根據 adaboost 演算法特點推導而來的。

GBDT

簡單介紹

GBDT是基於boosting的思想，串列地構造多棵決策樹來進行數據的預測，它是在損失函數所在的函數空間中做梯度下降，即把待求的決策樹模型當作參數，每輪迭代都去擬合損失函數在當前模型下的負梯度，從而使得參數朝著最小化損失函數的方向更新。

更深一步的介紹

GBDT可以看作是AdaBoost的一個推廣，AdaBoost是通過錯分數據點來識別問題，通過調整錯分數據點的權重來改進模型，GBDT是通過負梯度來識別問題，通過計算負梯度來改進模型，實際上，負梯度絕對值大的樣例同樣會在之後的訓練中受到更大的關注，因為它造成的損失更容易在最後的損失函數中占很大的比重，因此，需要更多地偏向於它去減小損失。這也是GBDT和AdaBoost相似的一個點，而相比AdaBoost, Gradient Boosting可以使用更多類型的損失函數，因此可以解決更多的問題。

最常見的損失函數是平方損失函數，square loss的優點是便於理解和實現，它的負梯度就是殘差，而其他損失函數的負梯度只能看作殘差的近似值，它的缺點在於對於異常值它的魯棒性較差，因此會常用absolute loss或Huber loss來代替。

Random Forest

簡單介紹

隨機森林演算法背後的思想是群體智慧的體現，它通過隨機的行採樣(bagging)和列採樣(feature bagging)構造不同的訓練集，建立一個決策樹森林，利用加權平均方式或多數表決的方式得到最後的預測結果，能夠並行學習，對雜訊和異常數據具有很好的過濾作用，因此有很廣泛的應用。

更深一步的介紹

隨機森林的行採樣(bagging)和列採樣(feature bagging)都是為了減小模型之間的相關性使基學習器變得不同從而減小集成模型的方差，但這種隨機性會導致隨機森林的偏差有所增加（相比於單棵不隨機樹），因此隨機森林的單棵樹都會採用很深的決策樹，並不進行剪枝操作，以減小每棵樹的偏差，這使得每一棵決策樹就是一個精通於某一個窄領域的專家（因為我們從全部特徵中選擇部分來讓每一棵決策樹學習），這樣在隨機森林中就有了很多個精通不同領域的專家，對一個新的問題（新的輸入數據），可以用不同的角度去看待它，最終再通過投票或平均得到結果。這也正是群體智慧的體現。

XGboost

簡單介紹

xgboost是梯度提升樹的一種高效系統實現，是對GBDT進一步的改進，包括對代價函數進行了二階泰勒展開，在代價函數里加入了正則項，借鑒了隨機森林的列採樣方法，支持並行計算等

更深一步的介紹

  • 傳統GBDT在優化時只用到一階導數信息，xgboost則對代價函數進行了二階泰勒展開，同時用到了一階和二階導數。順便提一下，xgboost工具支持自定義代價函數，只要函數可一階和二階求導。
  • xgboost在代價函數里加入了正則項，用於控制模型的複雜度。正則項里包含了樹的葉子節點個數、每個葉子節點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學習出來的模型更加簡單，防止過擬合，這也是xgboost優於傳統GBDT的一個特性。
  • Shrinkage（縮減），相當於學習速率（xgboost中的eta）。xgboost在進行完一次迭代後，會將葉子節點的權重乘上該係數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間。實際應用中，一般把eta設置得小一點，然後迭代次數設置得大一點。（補充：傳統GBDT的實現也有學習速率）
  • 列抽樣（column subsampling）。xgboost借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算，這也是xgboost異於傳統gbdt的一個特性。
  • 對缺失值的處理。對於特徵的值有缺失的樣本，xgboost可以自動學習出它的分裂方向。
  • xgboost工具支持並行。boosting不是一種串列的結構嗎?怎麼並行的？注意xgboost的並行不是tree粒度的並行，xgboost也是一次迭代完才能進行下一次迭代的（第t次迭代的代價函數里包含了前面t-1次迭代的預測值）。xgboost的並行是在特徵粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特徵的值進行排序（因為要確定最佳分割點），xgboost在訓練之前，預先對數據進行了排序，然後保存為block結構，後面的迭代中重複地使用這個結構，大大減小計算量。這個block結構也使得並行成為了可能，在進行節點的分裂時，需要計算每個特徵的增益，最終選增益最大的那個特徵去做分裂，那麼各個特徵的增益計算就可以開多線程進行。

  • 可並行的近似直方圖演算法。樹節點在進行分裂時，我們需要計算每個特徵的每個分割點對應的增益，即用貪心法枚舉所有可能的分割點。當數據無法一次載入內存或者在分散式情況下，貪心演算法效率就會變得很低，所以xgboost還提出了一種可並行的近似直方圖演算法，用於高效地生成候選的分割點。

這裡參考：機器學習演算法中 GBDT 和 XGBOOST 的區別有哪些？

LightGBM

簡單介紹

LightGBM是一個實現GBDT演算法的分散式高效框架。它通過leaf-wise分裂方法進行決策樹的生成，通過基於直方圖的演算法尋找特徵分割點，並支持並行學習，能夠更高效的處理大數據，也得到了越來越廣泛的應用。

更深一步的介紹

首先，它通過leaf-wise分裂方法產生比level-wise分裂方法更複雜的樹，能夠實現更高的準確率。雖然這樣有時候會導致過擬合，但可以通過設置 max-depth 參數來防止過擬合的發生。（每一次的生長都是選取分裂增益最高的節點，而不是對一層中的所有節點都進行分裂）。

其次，它使用基於直方圖的演算法，將連續的特徵值分桶(buckets)裝進離散的箱子(bins)，並通過直方圖做差加速計算兄弟節點的直方圖，能夠加速訓練過程，並實現更少的內存佔用。

另外，它支持並行學習，包括特徵並行和數據並行

  • 特徵並行的主要思想是不同機器在不同的特徵集合上分別尋找最優的分割點，然後在機器間同步最優的分割點。（mapreduce思想）
  • 數據並行則是讓不同的機器先在不同的記錄集合上構造直方圖，然後進行全局的合併，最後在合併的直方圖上面尋找最優分割點。

它還支持直接輸入類別特徵，在對離散類別特徵分裂時，每個取值都當作一個桶，分裂時的增益算的是」是否屬於某個類別「的增益，對於類別特徵的操作類似於one-hot編碼。

CatBoost

簡單介紹

CatBoost是Category 和 Boosting的縮寫，最大的特點就是可以直接處理類別特徵，不需要任何預處理來將類別轉換為數字。

具體詳細的介紹請參考：CatBoost原理及實踐

對比分析

xgb是對gbdt的優化改進

1、目標函數中加入了正則項來控制模型的複雜度，替代原來的剪枝方法。

2、利用了one-hot編碼等情況中的特徵稀疏性。（僅對特徵值為非缺失值的樣本的特徵進行遍歷）

3、支持列抽樣（同random forest）。

4、數據事先排序並按block結構保存，有利於並行運算（樹的生成還是串列的，這裡說的並行計算指並行計算各個特徵的增益或是基尼係數）。除此之外，xgb還通過一種可並行的近似直方圖演算法來高效生成候選的分割點。

5、對損失函數進行了優化，gbdt只用到了其一階導數信息，而xgb同時用到其一階導與二階導。

lgb則是在xgb基礎上進一步改進

1、內存需求小：xgb使用基於pre-sorted的決策樹演算法，而lgb使用基於histogram的決策樹演算法。histogram演算法佔用的內存很小：pre-sorted需要兩倍數據大小的內存空間，一半用於數據（float32），一半用於存放排好序的索引，而histogram不需要存放索引，且特徵值只需要存放離散後的值，用uint8即可，故內存需求僅為pre-sorted的1/8。

2、計算速度快：決策樹演算法的主要操作包括「尋找分割點」與「數據分割」兩步，pre-sorted演算法和histogram演算法在「尋找分割點」上的時間複雜度是一致的；但是在「數據分割」上histogram要快，histogram所有特徵共享一張索引，而pre-sorted一個特徵對應一張索引，若集合level-wise，pre-sorted也可以共用一張索引，但是會帶來很多隨機訪問的問題，速度仍不及histogram。此外，histogram演算法還減少了計算分割點增益的次數。

3、通信代價小：histogram演算法的通信代價遠遠小於pre-sorted，可用於分散式計算。

但是，histogram不能找到很精確的分割點，訓練誤差不如pre-sorted演算法，可以說是犧牲一定精度來換取速度。需要指出的是，這種粗獷的分割相當於自帶正則效果，所以測試集的誤差兩種決策樹演算法差距不大。

以上參考：cnblogs.com/asprin/p/92

關鍵兩點差別

1、決策樹演算法

XGBoost使用的是pre-sorted演算法，能夠更精確的找到數據分隔點；LightGBM使用的是histogram演算法，佔用的內存更低，數據分隔的複雜度更低。

2、決策樹生長策略

XGBoost採用的是level（depth）-wise生長策略，能夠同時分裂同一層的葉子，從而進行多線程優化，不容易過擬合；但不加區分的對待同一層的葉子，帶來了很多沒必要的開銷。

LightGBM採用leaf-wise生長策略，每次從當前所有葉子中找到分裂增益最大（一般也是數據量最大）的一個葉子，然後分裂，如此循環；但會生長出比較深的決策樹，產生過擬合。因此，LightGBM 在leaf-wise 之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。


推薦閱讀：
相关文章