Gradient Boosting

摘要

• Gradient Boosting
• 簡介
  • STEP 0－定義損失函數並推導其梯度
  • STEP 1－初始化基準模型
  • STEP 2－依序建立 T 個模型
    • STEP 2.1－計算樣本負梯度（虛擬殘差）
    • STEP 2.2－根據樣本負梯度（虛擬殘差）建立模型
    • STEP 2.3－計算模型輸出值
    • STEP 2.4－更新模型
  • STEP 3－產出最終模型
• 迴歸（Regression）任務
• 分類（Classification）任務
• 參考資料

簡介

注意

此篇筆記是嘗試將 Gradient Boosting 那些艱澀難懂的數學式，應用在實際例子上（迴歸與分類），建議先看參考資料，瞭解什麼是 Gradient Boosting 再來看這篇會比較有心得（吧

STEP 0－定義損失函數並推導其梯度

根據任務性質，定義個可微分的損失函數：

重點

$$L(y,h(x))$$

給定已經定義好的損失函數，推導其在

$h(x)$ 的梯度（gradient）：

重點

$$\frac{\partial }{\partial h(x)}L(y,h(x))$$

STEP 1－初始化基準模型

初始化第

$0$ 個模型

$h_0(x)$，通常稱為 base learner。該模型很簡單，不論輸入什麼，它只輸出一個固定值

$\gamma$。而該值必須最小化總樣本損失：

重點

$$h_0(x)=\underset{\gamma }{\arg min}\sum _{n=1}^{N}L(y_n,\gamma )$$

實際上，我們會將損失函數在

$\gamma$ 的梯度加總起來並設為

$0$，推導出

$\gamma$：

重點

$$\sum _{n=1}^N\frac{\partial }{\partial \gamma }L(y_n,\gamma )=0$$

STEP 2－依序建立 T 個模型

初始化好基準模型後，接下來就是依序建立

$T$ 個模型，疊加在前個模型之上。以下的步驟都是給定我們正在建立第

$t$ 個模型。

STEP 2.1－計算樣本負梯度（虛擬殘差）

給定前個模型

$h_{t-1}(x)$，計算每個樣本的負梯度

$r_{tn}$：

重點

$$r_{tn}=-[\frac{\partial }{\partial h(x_n)}L(y_n,h(x_n)){]}_{h(x)=h_{t-1}(x)}\mathrm{\forall }n=1,\dots ,N$$

$r_{tn}$ 通常又被稱為虛擬殘差（pseudo residual），後續的實際例子會更瞭解其內涵。

STEP 2.2－根據樣本負梯度（虛擬殘差）建立模型

以輔助資料集

$\{(x_n,r_{tn}){\}}_{n=1}^N$ ，建立第

$t$ 個模型

$h_t(x)$，用來預測虛擬殘差

$r_{tn}$。如此一來，該模型就正朝著正確的方向更新其輸出值了。

STEP 2.3－計算模型輸出值

假設模型訓練完成後會有

$K_t$ 個葉節點

$\{R_{tk}{\}}_{k=1}^{K_t}$。那麼接下來就是計算這些葉節點的輸出應該要是多少。計算每個葉節點的輸出值

${\gamma }_{tk}$，負責預測

$r_{tn}$：

重點

$${\gamma }_{tk}=\underset{\gamma }{\arg min}\sum _{x_n\in R_{tk}}L(y_n,h_{t-1}(x_n)+\gamma )\mathrm{\forall }k=1,\dots ,K_t$$

實際上，我們會將損失函數在

${\gamma }_{tk}$ 的梯度加總起來並設為

$0$，推導出

${\gamma }_{tk}$：

重點

$$\sum _{x_n\in R_{tk}}\frac{\partial }{\partial {\gamma }_{tk}}L(y_n,h_{t-1}(x_n)+{\gamma }_{tk})=0\mathrm{\forall }k=1,\dots ,K_t$$

STEP 2.4－更新模型

重點

$$h_t(x)=h_{t-1}(x)+\nu \sum _{k=1}^{K_t}{\gamma }_{tk}I[x\in R_{tk}]$$

STEP 3－產出最終模型

重點

$$H(x)$$

迴歸（Regression）任務

目前還沒整理，但這篇文章已經有很完整的介紹了。

STEP 0－定義損失函數並推導其梯度
STEP 1－初始化基準模型
STEP 2－依序建立 T 個模型
STEP 2.1－計算樣本負梯度（虛擬殘差）
STEP 2.2－根據樣本負梯度（虛擬殘差）建立模型
STEP 2.3－計算模型輸出值
STEP 2.4－更新模型
STEP 3－產出最終模型
STEP 3－產出最終模型

分類（Classification）任務

在分類任務中使用梯度提升樹，會借用到 Logistic 迴歸的理論。

STEP 0－定義損失函數並推導其梯度

首先，分類任務的梯度提升樹的損失函數定義如下：

重點

$$L(y,h(x))=-(y\log (\sigma (h(x)))+(1-y)\log (1-\sigma (h(x))))$$

其中

$$\sigma (z)=\frac{1}{1+e^{-z}}$$

可以看得出來，就是 Logistic 迴歸的 negative log likelihood。

實際上，上述損失函數也可以簡化為以下兩種形式（省略推導過程）：

$$\begin{array}{rl}L(y,h(x))& =-((y-1)h(x)-\log (1+e^{-h(x)}))\\ & =-(y\cdot h(x)-\log (1+e^{h(x)}))\end{array}$$

透過簡化過後的損失函數，我們可以更容易推導出其在

$h(x)$ 的梯度（省略推導過程）：

重點

$$\begin{array}{rl}\frac{\partial }{\partial h(x)}L(y,h(x))& =-(y-\frac{1}{1+e^{-h(x)}})\\ & =-(y-\sigma (h(x)))\end{array}$$

可以觀察到，結果是實際值（

$0$ 或

$1$）減去預測機率值（介於

$0$ 到

$1$）再加上負號。

STEP 1－初始化基準模型

初始化基準模型

$h_0(x)$：

$$\begin{array}{rl}{h}_0(x)& =\underset{\gamma }{\arg min}\sum _{n=1}^{N}L(y_n,\gamma )\\ & =\underset{\gamma }{\arg min}\sum _{n=1}^N-(y_n\cdot \gamma -\log (1+e^{\gamma }))\end{array}$$

實際上，我們會將損失函數在

$\gamma$ 的梯度加總起來並設為

$0$，推導出

$\gamma$：

$$\begin{array}{rl}& \sum _{n=1}^N\frac{\partial }{\partial \gamma }L(y_n,\gamma )=0\\ ⟹& \sum _{n=1}^N-(y_n-\sigma (\gamma ))=0\end{array}$$

重點

$$\gamma =-\log (\frac{N-\sum y_n}{\sum y_n})=-\log (\text{odds})$$

可以看到，最小化損失函數的基準模型，固定會輸出

$-\log (\text{odds})$，非常容易計算。

STEP 2－依序建立 T 個模型

初始化好基準模型後，接下來就是依序建立

$T$ 個模型，疊加在前個模型之上。以下的步驟都是給定我們正在建立第

$t$ 個模型。

STEP 2.1－計算樣本負梯度（虛擬殘差）

第一步就是計算每個樣本的虛擬殘差，定義如下：

$$r_{tn}=-[\frac{\partial }{\partial h(x_n)}L(y_n,h(x_n)){]}_{h(x)=h_{t-1}(x)}\mathrm{\forall }n=1,\dots ,N$$

推導後結果如下所示：

重點

$$r_{tn}=y_n-\sigma (h_{t-1}(x_n))\mathrm{\forall }n=1,\dots ,N$$

$r_{tn}$ 為實際值減去前個模型

$h_{t-1}(x)$ 的預測機率值，可以理解成殘差（residual），但通常被稱為虛擬殘差（pseudo residual），因為會隨著不同的損失函數而變，有時候可能並沒有這麼好的直覺。

STEP 2.2－根據樣本負梯度（虛擬殘差）建立模型

以輔助資料集

$\{(x_n,r_{tn}){\}}_{n=1}^N$ ，建立第

$t$ 個模型

$h_t(x)$，用來預測虛擬殘差

$r_{tn}$。如此一來，該模型就能朝著正確的方向更新其輸出值了。

STEP 2.3－計算模型輸出值

假設訓練完成後會有

$K_t$ 個葉節點

$\{R_{tk}{\}}_{k=1}^{K_t}$。接下來就是計算每個葉節點的輸出值

${\gamma }_{tk}$，負責預測

$r_{tn}$：

$${\gamma }_{tk}=\underset{\gamma }{\arg min}\sum _{x_n\in R_{tk}}L(y_n,h_{t-1}(x_n)+\gamma )\mathrm{\forall }k=1,\dots ,K_t$$

這裡我們並不會「直接」將上述的損失函數在

$\gamma$ 的梯度加總起來並設為

$0$，推導出

${\gamma }_{tk}$，如果這麼做，式子將會變得很複雜。

取而代之的是，我們會先將損失函數以二階泰勒公式展開：

重點

$$L(y,h(x)+\gamma )\approx L(y,h(x))+\frac{\partial }{\partial h(x)}L(y,h(x))\gamma +\frac{1}{2}\frac{{\partial }^2}{\partial h(x{)}^2}L(y,h(x)){\gamma }^2$$

接著，再求展開後的損失函數在

$\gamma$ 的梯度：

重點

$$\frac{\partial }{\partial \gamma }L(y,h(x)+\gamma )\approx \frac{\partial }{\partial h(x)}L(y,h(x))+\frac{{\partial }^2}{\partial h(x{)}^2}L(y,h(x))\gamma$$

再來，才跟過去一樣，將損失函數在

${\gamma }_{tk}$ 的梯度加總起來並設為

$0$，推導出

${\gamma }_{tk}$：

$$\begin{array}{rl}& \sum _{x_n\in R_{tk}}\frac{\partial }{\partial {\gamma }_{tk}}L(y_n,h_{t-1}(x_n)+{\gamma }_{tk})=0\mathrm{\forall }k=1,\dots ,K_t\\ ⟹& \cdots \cdots \cdots \\ ⟹& {\gamma }_{tk}=\frac{-\sum _{x_n\in R_{tk}}(\frac{\partial }{\partial h_{t-1}(x_n)}L(y_n,h_{t-1}(x_n)))}{\sum _{x_n\in R_{tk}}(\frac{{\partial }^2}{\partial h_{t-1}(x_n{)}^2}L(y_n,h_{t-1}(x_n)))}\mathrm{\forall }k=1,\dots ,K_t\\ ⟹& \cdots \cdots \cdots \end{array}$$

重點

$${\gamma }_{tk}=\frac{\sum _{x_n\in R_{tk}}{r}_{tn}}{\sum _{x_n\in R_{tk}}[\sigma (h_{t-1}(x_n))\cdot (1-\sigma (h_{t-1}(x_n)))]}\mathrm{\forall }k=1,\dots ,K_t$$

將損失函數經由泰勒公式展開後，能簡化

${\gamma }_{tk}$ 的計算，結果也相當容易理解，分子是樣本的虛擬殘差相加，而分母則是樣本在前個模型的「預測成功機率值」乘上「預測失敗機率值」，再相加。

STEP 2.4－更新模型

重點

$$h_t(x)=h_{t-1}(x)+\nu \sum _{k=1}^{K_t}{\gamma }_{tk}I[x\in R_{tk}]$$

STEP 3－產出最終模型

重點

$$H(x)=\{\begin{array}{ll}1& \text{if}\sigma (h_T(x))\ge \text{threshold}\\ 0& \text{o.w.}\end{array}$$

參考資料

• Gradient Boosting 簡介, Chih-Wei Chang
• Gradient Boost Part 1: Regression Main Ideas, StatQuest with Josh Starmer
• Gradient Boost Part 2: Regression Details, StatQuest with Josh Starmer
• Gradient Boost Part 3: Classification, StatQuest with Josh Starmer
• Gradient Boost Part 4: Classification Details, StatQuest with Josh Starmer

tags: ML

$$$$