機器學習 — Gradient Boosting (1)

黃琮耀
黃琮耀
Sep 10 · 10 min read

數學原理及演算法說明

在最近幾年的 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),回歸樹有兩個特點:

  1. 擁有和決策樹 (Decision Tree) 一樣的分支方式
  2. 除此之外,在各個葉端 (Leaf) 含有一個預測分數 (Prediction Score)
CART 回歸樹示意圖

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

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

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

集成樹的目標函數

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

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

回歸樹學習分支條件以及葉端分數

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

誤差函數以及正則函數的平衡

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

怎麼學:Gradient Boosting

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

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

Boosting 學習方式:每次加入新學習函數

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

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

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

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

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

Boosting 目標函數

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

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

  1. gᵢ、hᵢ 是由誤差函數定義而來
  2. 新加入的學習函數只由 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),以避免過擬合。

總結

Gradient Boosting 為一種監督式學習,其目標函數為:

為找出最優參數,在每次迭代中首先計算 gᵢ、hᵢ ,並使用貪婪演算法計算 Gain 並找出最優分支做新增,並對負 Gain 的分支做刪減。

現在我們了解 XGBoost 的原理了,在下一篇文章中,將會對 Python 的 XGBoost Framework 的使用方式及實際操作多加說明。

Taiwan AI Academy

news, tech reviews and supplemental materials

黃琮耀

Written by

黃琮耀

Taiwan AI Academy

news, tech reviews and supplemental materials

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade