GBDT 與 LR 區別總結

最近面試被問到這個問題，之前總是總是零星記得幾條，現總結梳理如下。

1. 從機器學習三要素的角度：

1.1 模型

本質上來說，他們都是監督學習，判別模型，直接對數據的分布建模，不嘗試挖據隱含變數，這些方面是大體相同的。但是又因為一個是線性模型，一個是非線性模型，因此其具體模型的結構導致了VC維的不同：其中，Logistic Regression作為線性分類器，它的VC維是d+1，而 GBDT 作為boosting模型，可以無限分裂，具有無限逼近樣本VC維的特點，因此其VC維遠遠大於d+1，這都是由於其線性分類器的特徵決定的，歸結起來，是Logistic Regression對數據線性可分的假設導致的

1.2 策略

從 Loss(經驗風險最小化) + 正則(結構風險最小化) 的框架開始說起；

從Loss的角度：

因為 Logistic Regression 的輸出是 y = 1 的概率，所以在極大似然下，Logistic Regression的Loss是交叉熵，此時，Logistic Regression的準則是最大熵原理，也就是「為了追求最小分類誤差，追求最大熵Loss」，本質上是分類器演算法，而且對數據的雜訊具有高斯假設；而 GBDT 採用 CART 樹作為基分類器，其無論是處理分類還是回歸均是將採用回歸擬合（將分類問題通過 softmax 轉換為回歸問題，具體可參考本博客 GBDT 章節），用當前輪 CART 樹擬合前一輪目標函數與實際值的負梯度：，本質上是回歸演算法。

也正是因為 GBDT 採用的 CART 樹模型作為基分類器進行負梯度擬合，其是一種對特徵樣本空間進行劃分的策略，不能使用 SGD 等梯度優化演算法，而是 CART 樹自身的節點分裂策略：均方差(回歸) 也帶來了演算法上的不同； GBDT 損失函數值得是前一輪擬合模型與實際值的差異，而樹節點內部分裂的特徵選擇則是固定為 CART 的均方差，目標損失函數可以自定義，當前輪 CART 樹旨在擬合負梯度。

從特徵空間的角度: 就是因為 Logistic Regression 是特徵的線性組合求交叉熵的最小化，也就是對特徵的線性組合做 logistic，使得Logistic Regression會在特徵空間中做線性分界面，適用於分類任務；

而 GBDT 採用 CART 樹作為基分類器，其每輪樹的特徵擬合都是對特徵空間做平行於坐標軸的空間分割，所以自帶特徵選擇和可解釋性，GBDT 即可處理分類問題也可解決回歸問題，只是其統一採用回歸思路進行求解（試想，如果不將分類轉換為回歸問題，GBDT 每輪目標函數旨在擬合上一輪組合模型的負梯度，分類信息無法求梯度，故而依舊是採用 softmax 轉換為回歸問題進行求解）。

線性分類器（處理線性可分）有三大類：感知器準則函數、SVM、Fisher準則。
感知準則函數 ：準則函數以使錯分類樣本到分界面距離之和最小為原則。其優點是通過錯分類樣本提供的信息對分類器函數進行修正，這種準則是人工神經元網路多層感知器的基礎。 支持向量機 ：基本思想是在兩類線性可分條件下，所設計的分類器界面使兩類之間的間隔為最大，它的基本出發點是使期望泛化風險儘可能小。（使用核函數可解決非線性問題） Fisher 準則 ：更廣泛的稱呼是線性判別分析（LDA），將所有樣本投影到一條原點出發的直線，使得同類樣本距離儘可能小，不同類樣本距離儘可能大，具體為最大化「廣義瑞利商」。根據兩類樣本一般類內密集，類間分離的特點，尋找線性分類器最佳的法線向量方向，使兩類樣本在該方向上的投影滿足類內儘可能密集，類間儘可能分開。這種度量通過類內離散矩陣 Sw 和類間離散矩陣 Sb 實現。

從正則的角度：

Logistic Regression 的正則採用一種約束參數稀疏的方式，其中 L2 正則整體約束權重係數的均方和，使得權重分布更均勻，而 L1 正則則是約束權重係數絕對值和，其自帶特徵選擇特性；

GBDT 的正則：

弱演算法的個數T，就是迭代T輪。T的大小就影響著演算法的複雜度
步長（Shrinkage）在每一輪迭代中，原來採用 $F_t({f x}) = F_{t-1}({f x}) + alpha_th_t({f x}; {f w_t})$ 進行更新，可以加入步長v，使得一次不更新那麼多： $F_t({f x}) = F_{t-1}({f x}) + v alpha_th_t({f x}; {f w_t}); vin(0,1]$

XGBoost的正則是在 GBDT 的基礎上又添加了是一棵樹裡面節點的個數，以及每個樹葉子節點上面輸出分數的 L2 模平方。

區別在於 LR 採用對特徵係數進行整體的限定，GBDT 採用迭代的誤差控制本輪參數的增長；

1.3 演算法

Logistic Regression 若採用 SGB, Momentum, SGD with Nesterov Acceleration 等演算法，只用到了一階導數信息，若用 AdaGrad, AdaDelta / RMSProp, Adam, Nadam, 牛頓法則用到了二階導數信息，

而GBDT 直接擬合上一輪組合函數的特梯度，只用到了一階倒數信息，XGBoost 則是用到了二階導數信息。

SAG/SAGA 等優化器在scikit-learn上可用，但是業界用得比較多的還是BGFS，L-BGFS等，個人認為是計算量的原因，Logistic Regression模型很快就可以收斂，在線性可分的空間中也不容易出現鞍點，而且一般用Logistic Regression模型的數據量都比較大，大到不能上更複雜的模型，所以優化方法一般都是往計算量小的方向做。

2. 從特徵的角度：

2.1 特徵組合：

如前所說，GBDT 特徵選擇方法採用最小化均方損失來尋找分裂特徵及對應分裂點，所以自動會在當前根據特徵 A 分裂的子樹下尋求其他能使負梯度最小的其他特徵 B，這樣就自動具備尋求好的特徵組合的性能，因此也能給出哪些特徵比較重要（根據該特徵被選作分裂特徵的次數）。

而 LR 只是一次性地尋求最大化熵的過程，對每一維的特徵都假設獨立，因此只具備對已有特徵空間進行分割的能力，更不會對特徵空間進行升維（特徵組合）

2.2 特徵的稀疏性：

如前所述，Logistic Regression不具有特徵組合的能力，並假設特徵各個維度獨立，因此只具有線性分界面，實際應用中，多數特徵之間有相關性，只有維度特別大的稀疏數據中特徵才會近似獨立，所以適合應用在特徵稀疏的數據上。

而對於 GBDT，其更適合處理稠密特徵，如 GBDT+LR 的Facebook論文中，對於連續型特徵導入 GBDT 做特徵組合來代替一部分手工特徵工程，而對於 ID 類特徵的做法往往是 one-hot 之後直接傳入 LR，或者先 hash，再 one-hot 傳入樹中進行特徵工程，而目前的主流做法是直接 one-hot + embedding 來將高維稀疏特徵壓縮為低緯稠密特徵，也進一步引入了語意信息，有利於特徵的表達。