GBDT-梯度提升決策樹的一些思考 FesianXu 20210129 @ Baidu intern

前言

最近筆者工作中用到了GBRank模型[1]，其中用到了GBDT梯度提升決策樹，原論文的原文并不是很容易看懂，在本文紀錄下GBDT的一些原理和個人理解，作為筆記。如有謬誤請聯系指出，本文遵守 CC 4.0 BY-SA 版權協議，轉載請聯系作者并注明出處，謝謝。

$?$ 聯系方式：

e-mail: FesianXu@gmail.com

QQ: 973926198

github: https://github.com/FesianXu

知乎專欄: 計算機視覺/計算機圖形理論與應用

微信公眾號：

---

梯度提升決策樹（Gradient Boost Decision Tree，GBDT）是一種通過梯度提升策略去提高決策樹性能表現的一種樹模型設計思想，本文集中討論的是GBDT在回歸中的應用。對于一個數據集$\mathcal{D}=\{{\mathbf{x}}_i,y_i{\}}_{i=1,?,N}$而言，${\mathbf{x}}_i\in {\mathbb{R}}^d,y_i\in \mathbb{R}$為第$i$個樣本的特征和輸出目標值，我們期望學習到一個模型$f(?)$，有$y_i=f({\mathbf{x}}_i)$。在GBDT中，我們用加性模型（additive model）去對這個模型建模，也即是有：
$$f({\mathbf{x}}_i)=f_0({\mathbf{x}}_i)+\sum _{k=1}^K{\alpha }_k{f}_k({\mathbf{x}}_i)\text{\hspace{1em}(1)}$$
其中的$f_k(?),k=0,?,K$為基礎子模型（base model），在GBDT中使用CART決策樹作為這個基礎子模型。假設得到了$f_{k?1}({\mathbf{x}}_i)$的情況下，我們期望通過CART樹模型，學習到一個$h_k({\mathbf{x}}_i)$，使得有式子(2)表示的loss最小，那么就可以更新模型到$f_k(?)$了：
$$\sum _{i=1}^N\mathcal{L}(y_i,f_k({\mathbf{x}}_i))=\sum _{i=1}^N\mathcal{L}(y_i,f_{k?1}({\mathbf{x}}_i)+h_k({\mathbf{x}}_i))\text{\hspace{1em}(2)}$$
那么我們要如何去更新模型，以及取得最初始的$f_0(?)$呢？我們先看一個例子，如Fig 1所示，藍色點表示若干樣本點，現在希望GBDT模型可以擬合這些樣本點，從直觀上，我們的初始值考慮需要和所有樣本的loss之和最小，也就是：
$$f_0(\mathbf{x})=\arg \underset{c}{\min }\sum _{i=1}^N\mathcal{L}(y_i,c)\text{\hspace{1em}(3)}$$
當損失函數為MSE函數時，也即是$\mathcal{L}(x,y)=\frac{1}{2}(x?y{)}^2$時，我們通過求導的方法可以求得式子(3)的最優解為:
$$c=\frac{1}{N}\sum _{i=1}^N{y}_i\text{\hspace{1em}(4)}$$
也即是所有待回歸值的均值，如Fig 1中的綠色虛線所示。這一點也很容易理解，在不知道其他任何信息量時，初始化選擇數據集待回歸值的中心時可能導致偏差可能性最小的。

Fig 1. 若干樣本點（藍色），現在希望學習到的GBDT模型可以擬合這些樣本點。

接下來我們得考慮如何去更新模型，在得到了$f_{k?1}(\mathbf{x})$之后，擬合并不是完美的，和最終目標$y_i$仍然有偏差，這個偏差就是$\mathcal{L}(y_i,f_{k?1}(\mathbf{x}))$，為了讓模型更新方向操作縮小這個偏差的方向行進，我們可以借助負梯度方向更新的方法。首先我們得求出此時偏差的負梯度：
$$r_{ki}=?\frac{?\mathcal{L}(y_i,f_{k?1}({\mathbf{x}}_i))}{?f_{k?1}({\mathbf{x}}_i)}\text{\hspace{1em}(5)}$$
然而，式子(5)有個小問題，一個函數如何對一個函數求導數呢，我們之前接觸的都是一個函數對其中一個變量求導數。其實這個倒也不難，因為對于函數的每個輸入而言，都會輸出一個值（對于單值函數而已），因此我們可以把函數看成是一個無限維的向量，向量的每一個維度都是對應輸入的函數輸出，如$f(x)=[v_0,?,v_n]\in {\mathbb{R}}^{\infty }$。在樣本有限的情況下，比如只有$N$個，那么我們可以用$N$維向量去近似表示這個函數。回歸到我們的原問題，我們的$f_{k?1}(\mathbf{x})$其實可以表示為$N$個樣本的向量輸出表示，為$f_{k?1}(\mathbf{x})=[v_0,?,v_N]\in {\mathbb{R}}^N$，那么對函數求導的問題就變成對向量求導了。如果損失函數是MSE函數，那么我們可以求得其梯度為：
$$\frac{?\mathcal{L}(y_i,f_{k?1}({\mathbf{x}}_i))}{?f_{k?1}({\mathbf{x}}_i)}=f_{k?1}({\mathbf{x}}_i)?y_i\text{\hspace{1em}(6)}$$
但是！我們注意到這個梯度計算得并不準確，因為我們只能用到能夠觀察到的$N$個訓練樣本去估計梯度，這個梯度對于未知樣本而言是不置信的。如Fig 2所示，黃色點是通過有限的$N$個樣本估計出來的$N$個梯度，而虛線才是實際梯度函數，因此我們需要用某種方式從有限個樣本中估計出梯度函數，在GBDT中采用了CART樹模型去進行這個操作。也即是說，通過樹模型$h_k(\mathbf{x})$去擬合$\mathcal{G}=\{{\mathbf{x}}_i,r_{ki}\},i=1,?,N$。在損失函數為MSE函數的情況下，我們發現其實就是在擬合前$k?1$模型所造成的誤差，如式子(6)所示。

Fig 2. 黃色點是觀察有限樣本估計的梯度，而虛線才是實際的梯度函數曲線。

注意到得到的CART樹模型$h_k(\mathbf{x})$，對于每個輸入的樣本${\mathbf{x}}_i$其最終都會歸結為某端的某個葉子節點，也即是預測梯度值，我們用$R_{kj}$表示第$k$個回歸樹的第$j$個葉子節點，其中$j=1,?,J$，$J$為葉子節點的數量。這樣不夠準確，應該很可能不同的樣本貢獻同一個預估的梯度值，如Fig 3所示，對于屬于某個集合$\mathcal{S}$的樣本${\mathbf{x}}_i$來說，可能CART樹$h_k(?)$會將其歸為同一個葉子節點$R_{kj}{|}_{j=j_0}$，此時樹模型其實起到的作用跟類似與聚類，如Fig 1所示就可以發現有明顯的三個聚類簇。對于不同的聚類簇，其需要“彌補”以減少與待回歸值之前差別的值$c_{kj}$是不同的，我們同樣可以求最小值的方法求得，如：
$$c_{kj}=\arg \underset{c}{\min }\sum _{{\mathbf{x}}_i\in R_{kj}}\mathcal{L}(y_i,f_{k?1}({\mathbf{x}}_i)+c)\text{\hspace{1em}(7)}$$
這個式子一眼并不容易看懂，式子(7)其實是對于被CART回歸樹$h_k(?)$歸為同一葉子節點的樣本進行處理，對于同一類的樣本${\mathbf{x}}_i$而言（也即是${\mathbf{x}}_i\in R_{kj}$），我們通過Linear Search的方法求得了對于該類的$c$，使得$f_{k?1}(\mathbf{x})+c$之后使得損失最小，這就是式子(7)的含義。這個過程同樣可以通過求導的方式進行最優化求解，假如損失函數為MSE函數，那么我們可以求得：
$$c_{kj}=\frac{1}{|i:{\mathbf{x}}_i\in R_{kj}|}\sum _{{\mathbf{x}}_i\in R_{kj}}(y_i?f_{k?1}({\mathbf{x}}_i))\text{\hspace{1em}(8)}$$
其中的$|i:{\mathbf{x}}_i\in R_{kj}|$是求得該類樣本的數量，以便于做歸一化。

Fig 3. 可能多個不同的輸入樣本在CART樹模型中會被歸為同一個葉子節點。

此時我們便有：
$$h_k(\mathbf{x})=\sum _{j=1}^J{c}_{kj}I(\mathbf{x}\in R_{kj})\text{\hspace{1em}(9)}$$
$I(?)$表示其中條件滿足時，返回1，否則返回0。因此本輪的最終更新的回歸函數為：
$$f_k(\mathbf{x})=f_{k?1}(\mathbf{x})+h_k(\mathbf{x})\text{\hspace{1em}(10)}$$
對于$k=1,?,K$我們不停地迭代計算，可以求得最終的回歸函數為：
$$f(\mathbf{x})=f_K(\mathbf{x})=f_0(\mathbf{x})+\sum _{k=1}^K\sum _{j=1}^J{c}_{kj}I(\mathbf{x}\in R_{kj})\text{\hspace{1em}(11)}$$
這也就是加性模型(1)的另一種表現形式而已。

因此，如果當損失函數為MSE函數時，可以表現為是用多棵CART樹模型對殘差的不斷擬合，但是如果當損失函數不是MSE時，則不能這樣解釋。

Reference

[1]. Zheng, Z., Chen, K., Sun, G., & Zha, H. (2007, July). A regression framework for learning ranking functions using relative relevance judgments. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 287-294).

總結

以上是生活随笔為你收集整理的GBDT-梯度提升决策树的一些思考的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。