Gradient Boosting

# Gradient Boosting :::warning :notebook_with_decorative_cover: **摘要** [toc] ::: # 簡介 :::danger **注意** 此篇筆記是嘗試將 Gradient Boosting 那些艱澀難懂的數學式，應用在實際例子上（迴歸與分類），建議先看參考資料，瞭解什麼是 Gradient Boosting 再來看這篇會比較有心得（吧 ::: ### STEP 0－定義損失函數並推導其梯度根據任務性質，定義個可微分的損失函數： :::success **重點** $$ \large L\big(y,~h(x)\big) $$ ::: 給定已經定義好的損失函數，推導其在 $h(x)$ 的梯度（gradient）： :::success **重點** $$ \large \frac{\partial }{\partial h(x)} L\big(y,~h(x)\big) $$ ::: ### STEP 1－初始化基準模型初始化第 $0$ 個模型 $h_0(x)$，通常稱為 base learner。該模型很簡單，不論輸入什麼，它只輸出一個固定值 $\gamma$。而該值必須最小化總樣本損失： :::success **重點** $$ \large h_0(x)=\mathop{\arg\min}\limits_{\gamma}\sum_{n=1}^N L(y_n,\gamma) $$ ::: 實際上，我們會將損失函數在 $\gamma$ 的梯度加總起來並設為 $0$，推導出 $\gamma$： :::success **重點** $$ \large \sum_{n=1}^N \frac{\partial }{\partial \gamma} L\big(y_n,~\gamma\big) = 0 $$ ::: ### STEP 2－依序建立 T 個模型初始化好基準模型後，接下來就是依序建立 $T$ 個模型，疊加在前個模型之上。以下的步驟都是給定我們正在建立第 $t$ 個模型。 #### STEP 2.1－計算樣本負梯度（虛擬殘差）給定前個模型 $h_{t-1}(x)$，計算每個樣本的負梯度 $r_{tn}$： :::success **重點** $$ r_{tn}=-\Bigg[\frac{\partial }{\partial h(x_n)} L\big(y_n,~h(x_n)\big) \Bigg]_{h(x)=h_{t-1}(x)}~~\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}$： :::success **重點** $$ \gamma_{tk}=\mathop{\arg\min}\limits_{\gamma}\sum_{x_n~\in~R_{tk}}L\big(y_n,~h_{t-1}(x_n)+\gamma\big)~~\forall~~k=1,~\dots,~K_t $$ ::: 實際上，我們會將損失函數在 $\gamma_{tk}$ 的梯度加總起來並設為 $0$，推導出 $\gamma_{tk}$： :::success **重點** $$ \sum_{x_n~\in~R_{tk}} \frac{\partial}{\partial \gamma_{tk}}L\big(y_n,~h_{t-1}(x_n)+\gamma_{tk}\big)=0 ~~\forall~~ k=1 ,~\dots,~K_t $$ ::: #### STEP 2.4－更新模型 :::success **重點** $$ h_t(x) = h_{t-1}(x) + \nu\sum_{k=1}^{K_t}\gamma_{tk} I\big[x \in R_{tk}\big] $$ ::: ### STEP 3－產出最終模型 :::success **重點** $$ H(x) $$ ::: # 迴歸（Regression）任務目前還沒整理，但[這篇文章](https://medium.com/@cwchang/gradient-boosting-%E7%B0%A1%E4%BB%8B-f3a578ae7205)已經有很完整的介紹了。 **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－定義損失函數並推導其梯度** 首先，分類任務的梯度提升樹的損失函數定義如下： :::success **重點** $$ \large L(y,h(x)) = -\Bigg(y \log\Big(\sigma\big(h(x)\big)\Big)+(1-y)\log\Big(1-\sigma\big(h(x)\big)\Big)\Bigg) $$ :::spoiler 其中 $$ \large \sigma(z)=\frac{1}{1+e^{-z}} $$ ::: 可以看得出來，就是 Logistic 迴歸的 negative log likelihood。實際上，上述損失函數也可以簡化為以下兩種形式（省略推導過程）： $$ \large \begin{align} L(y,h(x)) &= -\Big( (y-1)h(x) - \log\big(1+e^{-h(x)}\big)\Big) \\ &= - \Big(y \cdot h(x)-\log\big( 1+e^{h(x)} \big)\Big) \end{align} $$ 透過簡化過後的損失函數，我們可以更容易推導出其在 $h(x)$ 的梯度（省略推導過程）： :::success **重點** $$ \large \begin{align} \frac{\partial}{\partial h(x)}L\big(y,~h(x)\big) &= -\Big( y-\frac{1}{1+e^{-h(x)}} \Big) \\ &=-\Big( y-\sigma\big(h(x)\big) \Big) \end{align} $$ ::: 可以觀察到，結果是實際值（$0$ 或 $1$）減去預測機率值（介於 $0$ 到 $1$）再加上負號。 **STEP 1－初始化基準模型** 初始化基準模型 $h_0(x)$： $$ \begin{align} h_0(x) &= \mathop{\arg\min}\limits_{\gamma} \sum_{n=1}^N L(y_n,\gamma) \\ &= \mathop{\arg\min}\limits_{\gamma} \sum_{n=1}^N - \Big(y_n \cdot \gamma-\log\big( 1+e^{\gamma} \big)\Big) \end{align} $$ 實際上，我們會將損失函數在 $\gamma$ 的梯度加總起來並設為 $0$，推導出 $\gamma$： $$ \begin{align} & \sum_{n=1}^N \frac{\partial }{\partial \gamma} L\big(y_n,~\gamma\big) = 0 \\ \implies & \sum_{n=1}^N -\Big( y_n-\sigma\big(\gamma\big) \Big)=0 \end{align} $$ :::success **重點** $$ \large \gamma=-\log \big(\tfrac{N-\sum y_n}{\sum y_n}\big)=-\log(\text{odds}) $$ ::: 可以看到，最小化損失函數的基準模型，固定會輸出 $-\log(\text{odds})$，非常容易計算。 **STEP 2－依序建立 T 個模型** 初始化好基準模型後，接下來就是依序建立 $T$ 個模型，疊加在前個模型之上。以下的步驟都是給定我們正在建立第 $t$ 個模型。 **STEP 2.1－計算樣本負梯度（虛擬殘差）** 第一步就是計算每個樣本的虛擬殘差，定義如下： $$ r_{tn} = -\Bigg[\frac{\partial }{\partial h(x_n)} L\big(y_n,~h(x_n)\big) \Bigg]_{h(x)=h_{t-1}(x)}~~\forall~~n=1,~\dots,~N $$ 推導後結果如下所示： :::success **重點** $$ \large r_{tn} = y_n-\sigma\big(h_{t-1}(x_n)\big) ~~\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} = \mathop{\arg\min}\limits_{\gamma} \sum_{x_n~\in~R_{tk}} L\big(y_n,~h_{t-1}(x_n)+\gamma\big)~~\forall~~k=1,~\dots,~K_t $$ 這裡我們並不會「直接」將上述的損失函數在 $\gamma$ 的梯度加總起來並設為 $0$，推導出 $\gamma_{tk}$，如果這麼做，式子將會變得很複雜。取而代之的是，我們會先將損失函數以二階泰勒公式展開： :::success **重點** $$ L\big(y,~h(x)+\gamma\big) \approx L\big( y,~h(x) \big) + \frac{\partial}{\partial h(x)}L\big( y,~h(x) \big)\gamma + \frac{1}{2}\frac{\partial^2}{\partial h(x)^2}L\big( y,~h(x) \big)\gamma^2 $$ ::: 接著，再求展開後的損失函數在 $\gamma$ 的梯度： :::success **重點** $$ \frac{\partial}{\partial \gamma}L\big(y,~h(x)+\gamma\big) \approx \frac{\partial}{\partial h(x)}L\big( y,~h(x) \big) + \frac{\partial^2}{\partial h(x)^2} L\big( y,~h(x) \big)\gamma $$ ::: 再來，才跟過去一樣，將損失函數在 $\gamma_{tk}$ 的梯度加總起來並設為 $0$，推導出 $\gamma_{tk}$： $$ \begin{align} & \sum_{x_n~\in~R_{tk}} \frac{\partial}{\partial \gamma_{tk}}L\big(y_n,~h_{t-1}(x_n)+\gamma_{tk}\big)=0 ~~\forall~~ k=1 ,~\dots,~K_t \\ \implies & \cdots\cdots\cdots \\ \implies & \gamma_{tk}=\frac{-\sum_{x_n \in R_{tk}} \Big(\tfrac{\partial}{\partial h_{t-1}(x_n)}L\big(y_n,~h_{t-1}(x_n)\big)\Big)}{\sum_{x_n \in R_{tk}} \Big(\tfrac{\partial^2}{\partial h_{t-1}(x_n)^2} L\big( y_n,~h_{t-1}(x_n) \big)\Big)}~~\forall~~k=1,~\dots,~K_t \\ \implies & \cdots\cdots\cdots \end{align} $$ :::success **重點** $$ \large \gamma_{tk}=\frac{\sum_{x_n \in R_{tk}} r_{tn}}{\sum_{x_n \in R_{tk}}\Big[ \sigma(h_{t-1}(x_n)) \cdot \big(1-\sigma(h_{t-1}(x_n))\big) \Big]}~~\forall~~k=1,~\dots,~K_t $$ ::: 將損失函數經由泰勒公式展開後，能簡化 $\gamma_{tk}$ 的計算，結果也相當容易理解，分子是樣本的虛擬殘差相加，而分母則是樣本在前個模型的「預測成功機率值」乘上「預測失敗機率值」，再相加。 **STEP 2.4－更新模型** :::success **重點** $$ \large h_t(x) = h_{t-1}(x) + \nu\sum_{k=1}^{K_t}\gamma_{tk} I\big[x \in R_{tk}\big] $$ ::: **STEP 3－產出最終模型** :::success **重點** $$ \large H(x)= \begin{cases} 1 & \text{if}~~\sigma\big(h_T(x)\big) \ge \text{threshold} \\ 0 & \text{o.w.} \end{cases} $$ ::: # 參考資料 - [Gradient Boosting 簡介, Chih-Wei Chang](https://medium.com/@cwchang/gradient-boosting-%E7%B0%A1%E4%BB%8B-f3a578ae7205) - [Gradient Boost Part 1: Regression Main Ideas, StatQuest with Josh Starmer](https://www.youtube.com/watch?v=3CC4N4z3GJc) - [Gradient Boost Part 2: Regression Details, StatQuest with Josh Starmer](https://www.youtube.com/watch?v=2xudPOBz-vs) - [Gradient Boost Part 3: Classification, StatQuest with Josh Starmer](https://www.youtube.com/watch?v=jxuNLH5dXCs) - [Gradient Boost Part 4: Classification Details, StatQuest with Josh Starmer](https://www.youtube.com/watch?v=StWY5QWMXCw) ###### tags: `ML` $$ \DeclareMathOperator{\argmin}{\arg\min} $$