久久久999,国内精品久久久久伊人,一本色道HEZY免

GBDT（Gradient Boosting Decision Tree）是被工業(yè)界廣泛使用的機器學習算法之一，它既可以解決回歸問題，又可以應用在分類場景中，該算法由斯坦福統(tǒng)計學教授 Jerome H. Friedman 在 1999 年發(fā)表。本文中，我們主要學習 GBDT 的回歸部分。

在學習 GBDT 之前，你需要對 CART、AdaBoost 決策樹有所了解，和 AdaBoost 類似，GBDT 也是一種 Boosting 類型的決策樹，即在算法產生的眾多樹中，前一棵樹的錯誤決定了后一棵樹的生成。

我們先從最為簡單的例子開始，一起來學習 GBDT 是如何構造的，然后結合理論知識，對算法的每個細節(jié)進行剖析，力求由淺入深的掌握該算法。

我們的極簡數據集由以下 3 條數據構成，使用它們來介紹 GBDT 的原理是再好不過了，假設我們用這些數據來構造一個 GBDT 模型，該模型的功能是：通過身高、顏色喜好、性別這 3 個特征來預測體重，很明顯這是一個回歸問題。

身高（米）	顏色喜好	性別	體重（kg）
1.6	Blue	Male	88
1.6	Green	Female	76
1.5	Blue	Female	56

構造 GBDT 決策樹

GBDT 的第一棵樹只有 1 個葉子節(jié)點，該節(jié)點為所有樣本的初始預測值，且該值到所有樣本間的 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 個樣本，且為了保留算法的細節(jié)，這里只用了 2 個葉子節(jié)點，但實際工作中，GBDT 的葉子節(jié)點通常在 8-32 個之間。

然后我們要處理有多個預測值的葉子節(jié)點，取它們的平均值作為該節(jié)點的輸出，如下：

上面這棵樹便是第 2 棵樹，聰明的你一定發(fā)現(xiàn)了，第 2 棵樹實際上是第 1 棵樹和樣本之間的誤差，我們拿第 3 個樣本作為例子，第一棵樹對該樣本的預測值為 73.3，此時它和目標值 56 之間的誤差為 -17.3，把該樣本輸入到第 2 棵樹，由于她的身高值為 1.5，小于 1.55，她將被預測為 -17.3。

既然后一棵樹的輸出是前一棵樹的誤差，那只要把所有的樹都加起來，是不是就可以對前面樹的錯誤做出補償，從而達到逼近真實值的目的呢。這就是我們?yōu)槭裁匆詺埐罱涞脑颉?/p>

當然樹之間不會直接相加，而是在求和之前，乘上一個學習率，如 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 棵樹，如此循環(huán)下去，直到樹的棵數滿足預設條件，或總殘差小于一定閾值為止。以上，就是 GBDT 回歸樹的原理。

深入 GBDT 算法細節(jié)

GBDT 從名字上給人一種不明覺厲的印象，但從上文可以看出，它的思想還是非常直觀的。對于只想了解其原理的同學，至此已經足夠了，想學習更多細節(jié)的同學，可以繼續(xù)往下閱讀。

初始化模型

該算法主要分為兩個步驟，第一步為初始化模型：
$F_0(x) = \arg\min_{\gamma} \sum_{i=1}^n L(y_i, \gamma)$
上式中， $F$ 表示模型， $F_0$ 即模型初始狀態(tài)；L 為 Loss Function，n 為訓練樣本的個數， $y_i$ 為樣本 i 的目標值，gamma 為初始化的預測值，意為找一個 gamma，能使所有樣本的 Loss 最小。

前文提過，GBDT 回歸算法使用 MSE 作為其 Loss，即：
$L(y_i,\hat{y_i}) = \frac{1}{2}(y_i-\hat{y_i})^2$
公式中 $\hat{y_i}$ 表示第 i 個樣本的預測值，我們把例子中的 3 個樣本帶入 $F_0$ 中，得：
$F_0(x) = \frac{1}{2}(88-\gamma)^2 + \frac{1}{2}(76-\gamma)^2+\frac{1}{2}(56-\gamma)^2$
要找到一個 gamma，使上式最小，因為上式是一個拋物線，那么 $d(F_0)/d\gamma=0$ 時，上式有最小值，于是：
$\frac{d(F_0)}{d\gamma}=(\gamma-88)+(\gamma-76)+(\gamma-56)=0$
上式化簡后，你一眼就可以看出 gamma = (88+76+56)/3 = 73.3，即初始值就是所有樣本的平均值，

模型迭代

算法的第二個步驟是一個循環(huán)，偽代碼如下：

for m = 1 to M:
    (A)
    (B)
    (C)
    (D)

其中，m 表示樹的序號，M 為樹的總個數（通常該值設為 100 或更多），(A) (B) (C) (D) 代表每次循環(huán)中的 4 個子步驟，我們先來看 (A)

(A) 計算
$r_{im} = -\left[ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right]_{F(x)=F_{m-1}(x)}$
我們把 $F(x_i)$ 換成 $\hat{y_i}$ ，該式子其實是對 Loss 求 $\hat{y_i}$ 的偏微分，該偏微分為：
$\frac{\partial{L(y_i, \hat{y_i})}}{\partial \hat{y_i}} = \frac{\partial \frac{1}{2}(y_i-\hat{y_i})^2}{\partial \hat{y_i}} = -(y_i-\hat{y_i})$
而 $F(x)=F_{m-1}(x)$ 意為使用上一個模型來計算 $\hat{y_i}$ ，即用 m-1 棵已生成的樹來預測每一個樣本，那么 $r_{im} = y_i-\hat{y_i}$ 就是上面說的計算殘差這一步。

(B) 使用回歸決策樹來擬合殘差 $r_{im}$ ，樹的葉子節(jié)點標記為 $R_{jm}$ ，其中 j 表示第 j 個葉子節(jié)點，m 表示第 m 棵樹。該步驟的細節(jié)如果不清楚可以查看 CART 回歸樹一文。

(C) 對每個葉子節(jié)點，計算
$\gamma_{jm} = \arg\min_{\gamma} \sum_{x_i \in R_{ij}} L(y_i,F_{m-1}(x_i)+\gamma)$
上面式子雖然較為復雜，但它和初始化步驟中的式子的目的是一樣的，即在每個葉子節(jié)點中，找到一個輸出值 gamma，使得整個葉子節(jié)點的 Loss 最小。

$\gamma_{jm}$ 為第 m 棵樹中，第 j 個葉子節(jié)點的輸出， $\sum_{x_i \in R_{ij}}L$ 表示在第 j 個葉子節(jié)點中所有樣本的 Loss，如下面的樹中，左邊葉子節(jié)點上有 1 個樣本，而右邊葉子節(jié)點內有 2 個樣本，我們希望根據這些樣本來求得對應葉子的唯一輸出，而 Loss 最小化就是解決之道。

在 Loss 函數中，第 2 個參數 $F_{m-1}(x_i) + \gamma$ 是模型對樣本 i 的預測，再加上 $\gamma$ ，對于只有 1 個樣本的葉子節(jié)點來說， $\gamma$ 就是該樣本殘差，而對于有多個樣本的節(jié)點來說， $\gamma$ 為能使 Loss 最小的那個值，下面就這兩種情況分別說明：

以上面這棵樹為例，左邊葉子節(jié)點只有 1 個樣本，即樣本 3，將它帶入到公式中：
$\begin{aligned} \gamma_{11} &= \arg\min_{\gamma}L(y_3, F_0(x_3)+\gamma)\\ &=\arg\min_{\gamma}(\frac{1}{2}(56-(73.3+\gamma))^2)\\ &=\arg\min_{\gamma}(\frac{1}{2}(-17.3-\gamma)^2) \end{aligned}$
要求右邊的式子最小，和上面一樣，我們令其導數為 0：
$\fracu0z1t8os{d\gamma}\left[\frac{1}{2}(-17.3-\gamma)^2\right] = 17.3+\gamma = 0$
算得 $\gamma_{11} = -17.3$ ，所以當葉子中只有 1 個樣本時，該葉子的輸出就是其殘差。

再來看下右邊這個節(jié)點，其中包含 2 個樣本，同樣把樣本 1 和樣本 2 帶入到公式中，得：
$\begin{aligned} \gamma_{21} &=\arg\min_{\gamma}(L(y_1, F_0(x_1)+\gamma)+L(y_2, F_0(x_2)+\gamma))\\ &=\arg\min_{\gamma}(\frac{1}{2}(88-(73.3+\gamma))^2+\frac{1}{2}(76-(73.3+\gamma))^2)\\ &=\arg\min_{\gamma}(\frac{1}{2}(14.7-\gamma)^2+\frac{1}{2}(2.7-\gamma)^2) \end{aligned}$
對右邊求導：
$\fracu0z1t8os{d\gamma}\left[ \frac{1}{2}(14.7-\gamma)^2+\frac{1}{2}(2.7-\gamma)^2) \right] = \gamma-14.7+\gamma-2.7$
上式為 0 時，Loss 最小，即
$\gamma-14.7+\gamma-2.7 = 0$
于是
$\gamma = \frac{14.7+2.7}{2} = 8.7$
可見，當葉子中有多個樣本時，該葉子的輸出值就是所有樣本殘差的平均值。