GBDT演算法用於分類問題
GBDT演算法用於分類問題
GBDT演算法概述
GBDT是boosting演算法的一種,按照boosting的思想,在GBDT演算法的每一步,用一棵決策樹去擬合當前學習器的殘差,獲得一個新的弱學習器。將這每一步的決策樹組合起來,就得到了一個強學習器。
具體來說,假設有訓練樣本 ,第m-1步獲得的集成學習器為 ,那麼GBDT通過下面的遞推式,獲得一個新的弱學習器 :
其中 是在函數空間 上最小化損失函數,一般來說這是比較難以做到的。但是,如果我們只考慮精確地擬合訓練數據的話,可以將損失函數 看作向量 上的函數。這樣在第m-1輪迭代之後,向量位於 ,如果我們想進一步減小損失函數,則根據梯度下降法,向量移動的方嚮應為損失函數的負梯度方向,即:
這樣如果使用訓練集: 去訓練一棵樹的話,就相當於朝著損失函數減小的方向又走了一步(當然在實際應用中需要shrinkage,也就是考慮學習率)。由此可見,GBDT在本質上還是梯度下降法,每一步通過學習一棵擬合負梯度(也就是所謂「殘差」)的樹,來使損失函數逐漸減小。
GBDT用於分類問題
將GBDT應用於回歸問題,相對來說比較容易理解。因為回歸問題的損失函數一般為平方差損失函數,這時的殘差,恰好等於預測值與實際值之間的差值。每次拿一棵決策樹去擬合這個差值,使得殘差越來越小,這個過程還是比較intuitive的。而將GBDT用於分類問題,則顯得不那麼顯而易見。下面我們就通過一個簡單的二分類問題,去看看GBDT究竟是如何學習到一棵樹的。
類似於邏輯回歸、FM模型用於分類問題,其實是在用一個線性模型或者包含交叉項的非線性模型,去擬合所謂的對數幾率 。而GBDT也是一樣,只是用一系列的梯度提升樹去擬合這個對數幾率,實際上最終得到的是一系列CART回歸樹。其分類模型可以表達為:
其中 就是學習到的決策樹。
清楚了這一點之後,我們便可以參考邏輯回歸,單樣本 的損失函數可以表達為交叉熵:
假設第k步迭代之後當前學習器為 ,將 的表達式帶入之後, 可將損失函數寫為:
可以求得損失函數相對於當前學習器的負梯度為:
可以看到,同回歸問題很類似,下一棵決策樹的訓練樣本為: ,其所需要擬合的殘差為真實標籤與預測概率之差。於是便有下面GBDT應用於二分類的演算法:
- ,其中 是訓練樣本中y=1的比例,利用先驗信息來初始化學習器
- For :
- 計算 ,並使用訓練集 訓練一棵回歸樹 ,其中
- 通過一維最小化損失函數找到樹的最優權重:
- 考慮shrinkage,可得這一輪迭代之後的學習器 , 為學習率
- 得到最終學習器為:
以上就是將GBDT應用於二分類問題的演算法流程。類似地,對於多分類問題,則需要考慮以下softmax模型:
其中 是 個不同的tree ensemble。每一輪的訓練實際上是訓練了 棵樹去擬合softmax的每一個分支模型的負梯度。softmax模型的單樣本損失函數為:
這裡的 是樣本label在k個類別上作one-hot編碼之後的取值,只有一維為1,其餘都是0。由以上表達式不難推導:
可見,這k棵樹同樣是擬合了樣本的真實標籤與預測概率之差,與二分類的過程非常類似。
推薦閱讀: