决策树之 GBDT 算法 - 回归部分
GBDT(Gradient Boosting Decision Tree)是被工業界廣泛使用的機器學習算法之一,它既可以解決回歸問題,又可以應用在分類場景中,該算法由斯坦福統計學教授 Jerome H. Friedman 在 1999 年發表。本文中,我們主要學習 GBDT 的回歸部分。
在學習 GBDT 之前,你需要對?CART、AdaBoost?決策樹有所了解,和 AdaBoost 類似,GBDT 也是一種 Boosting 類型的決策樹,即在算法產生的眾多樹中,前一棵樹的錯誤決定了后一棵樹的生成。
我們先從最為簡單的例子開始,一起來學習 GBDT 是如何構造的,然后結合理論知識,對算法的每個細節進行剖析,力求由淺入深的掌握該算法。
我們的極簡數據集由以下 3 條數據構成,使用它們來介紹 GBDT 的原理是再好不過了,假設我們用這些數據來構造一個 GBDT 模型,該模型的功能是:通過身高、顏色喜好、性別這 3 個特征來預測體重,很明顯這是一個回歸問題。
身高(米) 顏色喜好 性別 體重(kg)
1.6 Blue Male 88
1.6 Green Female 76
1.5 Blue Female 56
構造 GBDT 決策樹
GBDT 的第一棵樹只有 1 個葉子節點,該節點為所有樣本的初始預測值,且該值到所有樣本間的 MSE(Mean Squared Error)是最小的。實際上,初始值就是所有樣本的平均值,即 (88+76+56)/3 = 73.3,原因我們在下文會詳細介紹。
接下來,根據預測值,我們算出每個樣本的殘差(Residual),如第一個樣本的殘差為:88 - 73.3 = 14.7,所有樣本的殘差如下:
身高(米) 顏色喜好 性別 體重(kg) 殘差
1.6 Blue Male 88 14.7
1.6 Green Female 76 2.7
1.5 Blue Female 56 -17.3
接著,我們以殘差為目標值來構建一棵決策樹,構造方式同 CART 決策樹,這里你可能會問到為什么要預測殘差?原因我們馬上就會知道,產生的樹如下:
因為我們只有 3 個樣本,且為了保留算法的細節,這里只用了 2 個葉子節點,但實際工作中,GBDT 的葉子節點通常在 8-32 個之間。
然后我們要處理有多個預測值的葉子節點,取它們的平均值作為該節點的輸出,如下:
上面這棵樹便是第 2 棵樹,聰明的你一定發現了,第 2 棵樹實際上是第 1 棵樹和樣本之間的誤差,我們拿第 3 個樣本作為例子,第一棵樹對該樣本的預測值為 73.3,此時它和目標值 56 之間的誤差為 -17.3,把該樣本輸入到第 2 棵樹,由于她的身高值為 1.5,小于 1.55,她將被預測為 -17.3。
既然后一棵樹的輸出是前一棵樹的誤差,那只要把所有的樹都加起來,是不是就可以對前面樹的錯誤做出補償,從而達到逼近真實值的目的呢。這就是我們為什么以殘差建樹的原因。
當然樹之間不會直接相加,而是在求和之前,乘上一個學習率,如 0.1,這樣我們每次都可以在正確的方向上,把誤差縮小一點點。Jerome Friedman 也說過這么做有助于提升模型的泛化能力(low variance)。
整個過程有點像梯度下降,這應該也是 GBDT 中 Gradient 的來歷。GBDT 的預測過程如下圖所示:
按此方法更新上述 3 個樣本的預測值和殘差,如下:
樣本 目標值 預測值 殘差
1 88 73.3 + 0.1 × 8.7 = 74.17 13.83
2 76 73.3 + 0.1 × 8.7 = 74.17 1.83
3 56 73.3 + 0.1 × (-17.3) = 71.57 -15.57
比較這兩棵樹的殘差:
樣本 樹1的殘差 樹2的殘差
1 14.7 13.83
2 2.7 1.83
3 -17.3 -15.57
可見,通過 2 棵樹預測的樣本比只用 1 棵樹更接近目標值。接下來,我們再使用第 2 棵樹的殘差來構建第 3 棵樹,用第 3 棵樹的殘差來構建第 4 棵樹,如此循環下去,直到樹的棵數滿足預設條件,或總殘差小于一定閾值為止。以上,就是 GBDT 回歸樹的原理。
深入 GBDT 算法細節
GBDT 從名字上給人一種不明覺厲的印象,但從上文可以看出,它的思想還是非常直觀的。對于只想了解其原理的同學,至此已經足夠了,想學習更多細節的同學,可以繼續往下閱讀。
初始化模型
該算法主要分為兩個步驟,第一步為初始化模型:
F0(x)=arg?minγ∑i=1nL(yi,γ)
上式中,FFF 表示模型,F0F_0F0? 即模型初始狀態;L 為 Loss Function,n 為訓練樣本的個數,yiy_iyi? 為樣本 i 的目標值,gamma 為初始化的預測值,意為找一個 gamma,能使所有樣本的 Loss 最小。
前文提過,GBDT 回歸算法使用 MSE 作為其 Loss,即:
L(yi,yi)=12(yi?yi)2
公式中 yi^\hat{y_i}yi?^? 表示第 i 個樣本的預測值,我們把例子中的 3 個樣本帶入 F0F_0F0? 中,得:
F0(x)=12(88?γ)2+12(76?γ)2+12(56?γ)2
要找到一個 gamma,使上式最小,因為上式是一個拋物線,那么 d(F0)/dγ=0d(F_0)/d\gamma=0d(F0?)/dγ=0 時,上式有最小值,于是:
d(F0)dγ=(γ?88)+(γ?76)+(γ?56)=0
上式化簡后,你一眼就可以看出 gamma = (88+76+56)/3 = 73.3,即初始值就是所有樣本的平均值,
模型迭代
算法的第二個步驟是一個循環,偽代碼如下:
for m = 1 to M:
(A)
(B)
?
(D)
其中,m 表示樹的序號,M 為樹的總個數(通常該值設為 100 或更多),(A) (B) ? (D) 代表每次循環中的 4 個子步驟,我們先來看 (A)
(A) 計算
rim=?[?L(yi,F(xi))?F(xi)]F(x)=Fm?1(x)
我們把 F(xi)F(x_i)F(xi?) 換成 yi^\hat{y_i}yi?^?,該式子其實是對 Loss 求 yi^\hat{y_i}yi?^? 的偏微分,該偏微分為:
?L(yi,yi)?yi=?12(yi?yi)2?yi=?(yi?yi^)
而 F(x)=Fm?1(x)F(x)=F_{m-1}(x)F(x)=Fm?1?(x) 意為使用上一個模型來計算 yi^\hat{y_i}yi?^?,即用 m-1 棵已生成的樹來預測每一個樣本,那么 rim=yi?yi^r_{im} = y_i-\hat{y_i}rim?=yi??yi?^? 就是上面說的計算殘差這一步。
(B) 使用回歸決策樹來擬合殘差 rimr_{im}rim?,樹的葉子節點標記為 RjmR_{jm}Rjm?,其中 j 表示第 j 個葉子節點,m 表示第 m 棵樹。該步驟的細節如果不清楚可以查看?CART 回歸樹一文。
? 對每個葉子節點,計算
γjm=arg?minγ∑xi∈RijL(yi,Fm?1(xi)+γ)
上面式子雖然較為復雜,但它和初始化步驟中的式子的目的是一樣的,即在每個葉子節點中,找到一個輸出值 gamma,使得整個葉子節點的 Loss 最小。
γjm\gamma_{jm}γjm? 為第 m 棵樹中,第 j 個葉子節點的輸出,∑xi∈RijL\sum_{x_i \in R_{ij}}L∑xi?∈Rij??L 表示在第 j 個葉子節點中所有樣本的 Loss,如下面的樹中,左邊葉子節點上有 1 個樣本,而右邊葉子節點內有 2 個樣本,我們希望根據這些樣本來求得對應葉子的唯一輸出,而 Loss 最小化就是解決之道。
在 Loss 函數中,第 2 個參數 Fm?1(xi)+γF_{m-1}(x_i) + \gammaFm?1?(xi?)+γ 是模型對樣本 i 的預測,再加上 γ\gammaγ,對于只有 1 個樣本的葉子節點來說,γ\gammaγ 就是該樣本殘差,而對于有多個樣本的節點來說,γ\gammaγ 為能使 Loss 最小的那個值,下面就這兩種情況分別說明:
以上面這棵樹為例,左邊葉子節點只有 1 個樣本,即樣本 3,將它帶入到公式中:
γ11=arg?minγL(y3,F0(x3)+γ)=arg?minγ(12(56?(73.3+γ))2)=arg?minγ(12(?17.3?γ)2)
要求右邊的式子最小,和上面一樣,我們令其導數為 0:
ddγ[12(?17.3?γ)2]=17.3+γ=0
算得 γ11=?17.3\gamma_{11} = -17.3γ11?=?17.3,所以當葉子中只有 1 個樣本時,該葉子的輸出就是其殘差。
再來看下右邊這個節點,其中包含 2 個樣本,同樣把樣本 1 和樣本 2 帶入到公式中,得:
γ21=arg?minγ(L(y1,F0(x1)+γ)+L(y2,F0(x2)+γ))=arg?minγ(12(88?(73.3+γ))2+12(76?(73.3+γ))2)=arg?minγ(12(14.7?γ)2+12(2.7?γ)2)
對右邊求導:
ddγ[12(14.7?γ)2+12(2.7?γ)2)]=γ?14.7+γ?2.7
上式為 0 時,Loss 最小,即
γ?14.7+γ?2.7=0
于是
γ=14.7+2.72=8.7
可見,當葉子中有多個樣本時,該葉子的輸出值就是所有樣本殘差的平均值。
(D) 更新模型,下次迭代中使用 m 棵樹來做預測:
Fm(x)=Fm?1(x)+ν∑j=1Jmγjm
上式中,ν\nuν 表示學習率。之后,訓練將重新來到 (A) 步驟,進入下一棵樹構建的循環中。
總結
本文我們一起學習了 GBDT 的回歸算法,一開始,通過一個簡單的例子描述了 GBDT 的原理,之后,我們對 GBDT 的每個步驟進行了逐一剖析,希望本文能給你帶來收獲。
原文鏈接
本文為阿里云原創內容,未經允許不得轉載。
總結
以上是生活随笔為你收集整理的决策树之 GBDT 算法 - 回归部分的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 洞察设计模式的底层逻辑
- 下一篇: 多角度分析平台即服务?PaaS的类型和用