機器學習 — Gradient Boosting (1)

10 min readSep 10, 2019

數學原理及演算法說明

在最近幾年的 Kaggle 競賽中，能得到優秀成績的參賽者大多都有使用一種機器學習的方法 — XGBoost ( eXtreme Gradient Boosting, 極限梯度提升)因為它擁有非常高的預測精準度，而且可以調整的參數多，訓練速度也相當快，因此被大家拱為 Kaggle 神器。這篇文章將介紹 XGBoost 的由來以及數學原理，說明它的建構方式，和它是經由什麼做訓練的。

是什麼：Supervised Learning (監督式學習)

XGBoost 屬於監督式學習的範疇，我們首先介紹監督式學習是如何被訓練以及用來做預測的。舉個例子，對於一組有 d 個特徵的第 i 筆資料 xᵢ ，我們透過特徵與權重 w 的內積去預測 ŷᵢ：

這個預測 ( ŷᵢ ) 在不同的問題中，例如線性回歸、對數回歸和排名等，都可以被各自做運用。

在這個例子中，我們要讓模型去學習的參數 Θ ，是式子裡面的所有權重 w ，希望透過預測誤差 (Loss) 去優化這個參數，但我們又不希望透過無止盡的複雜化而導致過擬合 (Over-fit)，於是我們會加入正則項 (Regularization)，於是形成了目標函數 (Objective)：

式中 L 即為 Loss，其值可以作為判斷模型訓練優劣的依據。對於一個資料量為 n 筆的資料集，其誤差就是所有預測值與實際值的誤差函數總和：

這邊列出兩種常用的誤差函數 (Loss Function)：

而 Ω 為對每個參數施加的正則項 (Regularization)，調整此項可以簡化模型複雜度，使未來預測更穩定。一般常用的正則項有 Ridge (L2 Norm) 和 Lasso (L1 Norm)：

上述兩組誤差函數與正則項的例子組合，即為常見的回歸模型。到目前為止我們了解了目標函數的包含的兩個部分，而誤差函數與正則項是要互相做取捨的，如果我們要更精準的預測模型 (至少在 Training Dataset)，那麼可以針對誤差函數做優化，反之若想要模型精簡，可以往正則項優化。

了解監督式學習後，我們接著探討 XGBoost 真正套用的模型內容。

學什麼：CART (回歸樹)

XGBoost 是一種 Tree Based 的算法，所以我們先介紹一下所謂的回歸樹 (Classification and Regression Tree, CART)，回歸樹有兩個特點：

擁有和決策樹 (Decision Tree) 一樣的分支方式
除此之外，在各個葉端 (Leaf) 含有一個預測分數 (Prediction Score)

這種回歸樹是可以做集成的，疊加的方式為，把一筆資料丟進所有樹得到的預測分數做加總。

若以函數表示，假設我們有 K 棵樹 fₖ ，則此樹集對資料 xᵢ 的總預測為：

而樹的學習參數 Θ 有其分支方式以及葉端的分數，為求方便，我們先把整棵樹 f 都作為參數。那麼有了學習參數後，就能定義目標函數：

注意到右半邊的正則項 Ω ，由於參數是 K 棵樹 fₖ ，所以對於每棵樹我們都要施加正則化；而左邊為 n 筆資料的預測誤差總合。至於正則函數的內容，我們可以對葉端分數設 L2 Norm，也可以定義樹的深度以及分支數量，詳細會在後面說明。

不過具體來說目標函數到底學習什麼呢？下圖可以稍微說明：

上圖中我們能看到，調整分支點 (條件敘述) 以及各區段的高度 (葉端分數) 可以讓回歸樹對資料集做擬合 (Fit)，即對誤差函數做優化。此外，增加分支點可增強樹對複雜資料的擬合能力，不過為了避免過擬合 (Over-fit)現象的發生，我們可以調整正則項去做抑制，因此我們透過尋找誤差函數和正則函數的平衡，找出適合該資料集的設定。

了解使用的模型 (回歸樹) 以及目標函數，我們對 XGBoost 要學什麼有了概念，接下來的部分將介紹它怎麼學習。

怎麼學：Gradient Boosting

在一般深度學習的神經網路中，我們可以透過 Gradient Descent 讓模型學習，但對於回歸樹，它並非只有一般數值向量，我們沒有辦法使用一樣的方式做學習。因此這邊有適用於回歸樹的學習方式：Gradient Boosting。

又名為 Additive Training，此方法最初先以常數作為預測，在之後每次預測時新加入一個學習函數 (參數)：

從式中我們可以看到，在每一次的預測中，都保留了先前的所有學習函數，並多加入一個新的，所以我們可以很直觀的得出，第 t 次的預測 ŷᵢᵗ 即為前 t 次加入的所有函數值的總和。至於我們要怎麼決定新的函數 fₜ(xᵢ) 要加入什麼呢？回想先前提到的目標函數 Obj，我們要讓 fₜ(xᵢ) 對目標函數做優化！

在上圖中第 t 次預測時，目標函數經代入後為：

由於前 t-1 個正則項在此已經是固定值，直接把它列為常數項即可。然而，誤差函數的部分目前看起來不是很好用，我們再另外想辦法進一步簡化，考慮到多項式的泰勒展開式：

若我們能求得多項式的一次、二次微分，則可以利用上式對目標函數做簡化近似，於是定義 f(x) 為 l(yᵢ,ŷᵢᵗ⁻¹)，Δx 為新加入的 fₜ(xᵢ)，並令 gᵢ、hᵢ 分別為誤差函數的一次、二次微分：

其中 l(yᵢ,ŷᵢᵗ⁻¹) 為常數 (因為前 t -1 個函數已定義完成)，故我們可以直接把它和後面的 constant 省略，最後得到最精簡的目標函數：

那我們把平方誤差 (Square Loss) 作為誤差函數實際代入試試看：

目前為止，透過一步步求得的 Boosting 目標函數，我們可以知道

gᵢ、hᵢ 是由誤差函數定義而來
新加入的學習函數只由 gᵢ、hᵢ 決定 (當然也受正則項限制)

接著我們探討正則函數 Ω，在此之前得先完整地定義一下回歸樹，對於所有資料 xᵢ ，我們都可以適當地把它分流至某個葉端，因此我們定義葉端的分數為權重 w ，並把通過分支的過程稱為分類函數 q ，下圖有較易懂的解釋：

圖中我們可以看到，分流的過程統稱為 q ，因此小孩透過 q 分流至第一個葉端，而老奶奶透過 q 分流至第三個葉端，所以我們就可以這麼定義樹：

假設樹有 T 個葉端(權重)，那麼正則函數可以訂為：

左邊是葉端數量，右邊是各個葉端分數的 L2 Norm。拿上圖的樹來當例子的話，我們可以得到正則值為：

定義正則函數以及樹的函數式後，我們把它代回目標函數，得到：

但這邊我們發現前半段的加總和右邊的東西不太一樣，左邊是 n 筆資料，右邊為 T 個葉端權重。事實上 n 筆資料在進入回歸樹後，都會被分流至某一個葉端權重上，所以我們其實可以直接用數學式將 n 筆資料，分配至 T 個集合中：

這麼一來，目標函數即可合併為：

我們可以看到，括號內形成一個 wⱼ 的一元二次式，回顧以前學過的公式解，我們知道一元二次式的極值公式：

為求精簡，我們把 gᵢ、hᵢ 的加總用 G、H 代換：

最後可以一步步透過二次式公式解，求得目標函數的最佳權重和最佳目標分數：

下圖可以大致解釋公式以及代號在實際上的意義：

現在我們知道，對於 Boosting 學習，每次透過最佳權重計算最佳分數，去尋找並新增一個分支。不過… 增加分支的方式有千千萬萬種，我們要怎麼去尋找呢？這時我們可以利用貪婪演算法 (Greedy Algorithm)，從深度0開始，對於每個葉端都嘗試做分支，並計算分支前後的目標分數增益 (Gain)

至於嘗試做分支的方法，就是把屬於該分支的所有資料，排序後對彼此的區間都嘗試一次，就可以找到，參考下面示意圖：

我們可以把某葉端上每個資料之間都嘗試做一次分支，並透過計算各嘗試得到的 Gain，找出最優的分支方式。而此演算法的複雜度，假設有 n 筆資料，並且每筆資料有 d 個特徵，而我們想要搜索出深度為 K 的樹，則對每個深度、每個特徵，我們都需要對資料做排序，故複雜度為 O( d K n log n)。

不過在做分支的過程，我們可能會遇到最佳 Gain 為負的情況，此時我們有兩種方式，一種是 Pre-stopping，即遇到負值就停止分支，這個方法的好處是快又好寫，不過有可能負值分支之後的再分支可達到更好的結構，提早停止算是扼殺了這種可能；另一種是 Post-Prunning，讓樹成長到定義好的 K 深度，然後再回頭砍掉所有帶有負 Gain 的分支。

另外是在新增分支的時候，我們通常會對新的分支乘上一個 Shrinkage ϵ (通常為0.1)，以避免過擬合。