Q
GBDT是一種基于前向策略的加法模型, 每階段使用一個基模型去擬合上一階段基模型的殘差. 殘差是連續(xù)值, 因此用到的是回歸樹. 為什么當GBDT用作分類任務時可以選擇deviance loss和exponential loss, 而這兩個損失函數(shù)的$y^{(i)}$取值都為0-1標量, 如何計算殘差?
A
在梯度提升做二分類任務時, $y^{(i)}$不再是標量, 而是概率(為正的概率); 另一方面, deviance loss(二分類就是交叉熵損失)和exponential loss都是評價預測(概率)與真實(概率)之間的差距, 也就是殘差, 是一個連續(xù)值, 從而是一個回歸問題.
GBDT如何做分類任務?
若選擇deviance loss為分類任務的損失函數(shù):
求損失函數(shù)對當前模型的負梯度:
作為殘差的近似(就是梯度下降求解Logistics回歸參數(shù)的式子, 就是殘差, 驚人的聯(lián)系)
其中概率$p_k(x)$的計算:
- 概率來自$f_k(x)$, 也就是葉節(jié)點的輸出(輸出為對數(shù)幾率, 后轉換為概率), 其中$f_k(x) \geq 0$, $\sum_{k=1}^{K} p_k(x) = 1$
也就是說, GBDT做分類任務時, 提升的是關于概率的近似殘差
決策樹的兩個參數(shù)
損失函數(shù)的負梯度僅僅是用來作為
目標(殘差的近似)使用
最小二乘法計算樹結構(決策樹參數(shù)一)-
使用
目標(殘差的近似)計算葉子節(jié)點權值(決策樹參數(shù)二)(這里可以和XGBoost進行比較, XGBoost使用最小化損失函數(shù)計算樹結構, 使用二階梯度作為殘差的近似)
再看梯度提升算法
注意:
- 在訓練過程中并不是求的與上一棵樹結果的殘差, 而是求的與前面所有樹和的殘差! 在預測過程中, 可分別計算每棵樹, 求和即為最后的結果
- 在做分類任務時, 當樹構建完成后
- 計算每個葉節(jié)點的權值(這里的權值是對數(shù)幾率)
- 把對數(shù)幾率轉換為概率值(二分類就是logistics函數(shù), 多分類用上面的概率公式)
- 得到提升的概率值
- 對與(c)計算葉權重時, 使用均方誤差就是均值, 其他函數(shù)需要帶入計算最優(yōu)權值
GBDT與XGBoost在算法上的比較
XGBoost的每一階段的損失函數(shù)(經驗損失 + 結構損失):
其中, $w$是葉節(jié)點權值, 也是模型需要提升的值, 相當于GBDT中損失函數(shù)的負梯度:
- 葉節(jié)點權值是如何得來的? 使用牛頓法計算的增量$\Delta \theta = -\frac{G}{H}$作為梯度值的近似
- 這里用到了二階導信息, 更加接近于真實值, 所以收斂速度更快
- 分母加上了對結構損失的懲罰(如果結構復雜, 就少下降一點, 降低影響)
每個葉子是相互獨立的, 因此可以直接帶入到損失函數(shù)中:
GBDT的損失函數(shù)僅用在了計算目標值(進而計算葉節(jié)點的值), 而XGBoost不僅僅是計算葉節(jié)點的值, 進一步把損失函數(shù)用在了計算樹結構:
- 選擇劃分后損失降低最多的特征作為分裂特征
- 為什么GBDT不這么做呢? 可能是直接使用的CART的原因吧!
- 為什么XGBoost要這么做呢? $G, H$都求出來了, 又不和葉子節(jié)點相關, 很完美呀!(XGBoost完全基于$G, H$求解)
- 求每個樣本的近似殘差(一階梯度 vs 二階梯度)
- 計算樹結構(最小二乘法 vs 損失函數(shù))
- 計算葉子權值(落在葉子節(jié)點上的樣本取平均)
GBDT與XGBoost算法上區(qū)別的總結
-
GBDT使用一階梯度作為殘差的近似, XGBoost使用二階梯度作為殘差的近似
- 更加接近真實值, 收斂更快
GBDT的損失函數(shù)沒有考慮到樹的復雜度, 而XGBoost添加了正則項對復雜度進行了懲罰
-
GBDT是用的最小二乘法計算樹結構(CART), 而XGBoost使用的是損失函數(shù)來計算樹的結構
(注: 這里的區(qū)別僅僅是算法上的, XGBoost在并行上, 過擬合上, 適用范圍上還有改進)
另外, XGBoost的剪枝是基于最小增益Gamma的. 需要注意的是, 預剪枝的效果沒有后剪枝好(容易出現(xiàn)下潛不足), 因此XGBoost選擇了同一層所有節(jié)點都做分裂, 后剪枝的方法.
XGBoost: Introduction to Boosted Trees
GBDT vs 離散特征(Categorical Features)
- GBDT在處理離散特征時, 會默認特征是有序的
- 如果排序后的特征對應的標記為為[0, 1, ..., 0, 1]交叉型, 則不能很好的分類
- 如果使用one-hot, 對于高基數(shù)離散特征, 會生成不平衡的樹, 且每次劃分帶來的增益較少
- 解決辦法: 計算每個特征取值的熵, 通過熵的大小對特征進行有序重編碼
- LightGBM vs 離散特征
- 根據標簽的關聯(lián)性對特征進行重排序, 特別的, 使用加速值(
sum_gradient / sum_hessian)度量標簽與特征取值的關聯(lián)性 - catboost同樣是把離散值轉化為連續(xù)值來處理類別特征
- 根據標簽的關聯(lián)性對特征進行重排序, 特別的, 使用加速值(
LightGBM: Optimal Split for Categorical Features
LightGBM: Categorical feature support
GBDT vs LR vs DNN
GBDT損失函數(shù)的負梯度作為殘差的近似 與 LR求損失函數(shù)的負梯度去更新參數(shù)是一個性質嗎?
對于logloss:
$$
J(\theta) = - \sum_{i=1}^{m} y_i log(h_{\theta}(x)) + (1 - y_i)log(1 - h_{\theta}(x))
$$
不同在于GBDT的變量為模型$h_{\theta}(x)$
- 對$h_{\theta}(x)$求偏導, 來作為殘差的近似. ($h_{\theta}(x)$雖然為一個函數(shù), 但在這里視為為變量)
而LR的變量進一步為每個參數(shù)$\theta_j$
- 對$\theta_j$求偏導. (因此$\theta_j$需要歸一化, 這個過程是通過對特征的歸一化實現(xiàn)的)
總結
GBDT 和 梯度下降的LR 都可以認作是在擬合殘差(一步一步向目標值的迭代邁進), 不同在于一個是對模型求導, 作為的殘差的近似(其實也是提升模型的一個方向). 一個是對參數(shù)求導, 作為提升模型的方向. 同樣, DNN也可以這么想, 每一次更新參數(shù)為了更接近目標.
一個把梯度作為擬合的目標, 一個使用梯度下降來更新參數(shù)
logloss vs cross entropy
logloss 用來評價預測結果為概率的分類器的性能
cross entropy 是損失函數(shù), 衡量的是樣本的不確定性
其實就是一樣的(ps: wikipedia會把logloss指向cross entropy)
Quora: What is an intuitive explanation for the log loss function?
附錄1: GBDT分類任務源碼解析
sklearn GBDT 文檔
在每個階段, 使用回歸樹去擬合
交叉熵損失的負梯度
http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.GradientBoostingClassifier.html
另外的一個文檔
- 使用的是負的對數(shù)似然函數(shù)作為損失
- 使用對數(shù)幾率初始化模型(葉節(jié)點的值為對數(shù)幾率)
- 需要注意的一點, 使用deviance輸出的是
概率, 所以有可能評價的是概率上的損失
http://scikit-learn.org/stable/modules/ensemble.html#classification
查看源代碼
- 確實是擬合的交叉熵損失的負梯度
- 基模型使用的回歸樹!
其中的殘差的計算
numpy.ravel(): 把多維數(shù)組轉換為一維數(shù)組(兩個類別連接起來)
scipy.expit(): logistic function, expit(x) = 1/(1+exp(-x)), logistic 變換, 把對數(shù)幾率轉為概率
負梯度的值(殘差的近似)就是殘差(使用梯度下降求解的Logistic回歸相同)
附錄2: 樹模型與其他模型的比較
- 樹模型是不能提取特征的線性組合信息的
- SVM的好處就是就是泛化能力強和能處理特征間的線性組合問題
其他參考:
The Elements of Statistical Learning
