【機器學習 09】Aggregation Models — Part 3— Adaptive Boosting、Gradient Boosting
在 Part 1中，我們介紹兩種 aggregation 方法：
- 在得到 gₜ 之後才做 aggregation，不會修改原本模型，只是藉由不同的模型選擇、結合方式，以決定最終結果。
其中依照結合方式的不同，可分為 uniform blending、linear blending 和 non-linear blending。 - 一邊調整模型 gₜ，一邊做 aggregation。
依照調整模型方式的不同，可分為 bagging（bootstrap aggregation） 和 boosting。
並且也介紹 boosting 的原理。
另外，也在 Part 2 中介紹 Decision Tree 和 Random Forest。在本篇文章中，讓我們一起來認識 boosting 要如何運用在機器學習演算法中、甚至結合之前學到的 Decision Tree 吧！
Adaptive boosting (Adaboost) for Classification
在上一篇介紹 boosting 方法時，我們提過 boosting 主要是藉由不斷變化 data，並凸顯原本做錯的資料。
要如何凸顯原本做錯的資料？利用調整每筆資料的權重，調低正確分類的資料點權重，提高錯誤分類的資料點權重。
換句話說，我們希望錯誤率（εₜ）越低的 gₜ 有更高的貢獻度 αₜ，使用 βₜ 計算 gₜ 的權重。
Algorithm1. Initialize data weights u⁽¹⁾ = [1/N, 1/N, ...]
2. Iterate t = 1, 2, ... ,T
(1) Obtain gₜ via a classification model and weighted D with u⁽ᵗ⁾
(2) εₜ = Σₙuₙ⁽ᵗ⁾[yₙ≠gₜ(xₙ)] / Σₙuₙ⁽ᵗ⁾ ← 錯誤率
βₜ = √[(1-εₜ)/εₜ]
αₜ = ln(βₜ) ← 調高權重
(3) Update weights
- If correct [yₙ=gₜ(xₙ)]: uₙ⁽ᵗ⁺¹⁾ ← uₙ⁽ᵗ⁾ × βₜ
- If wrong [yₙ≠gₜ(xₙ)]: uₙ⁽ᵗ⁺¹⁾ ← uₙ⁽ᵗ⁾ ÷ βₜ
3. Return G(x) = sign[Σₜαₜgₜ(x)]
經過多次迭代後，會得到很多個 gₜ：
- 當錯誤率極小的 gₜ 出現時，βₜ 和 αₜ 都會趨近於無限大，會有完全的貢獻。
- 當有預測效果不好的 gₜ 出現時，例如錯誤率（εₜ）為 0.5， 則 βₜ 計算得 1，而 αₜ 為 0，因此此模型沒有參考價值。
Gradient boosting for Regression
上述的 Adaboost 是處理二元分類問題，若想要處理 regression 問題，則可以使用 gradient boost。
Gradient boost 主要是使用 regression with residuals 的方式，計算 xₙ 和 residual（yₙ-sₙ）的 regression。
換而言之，如果原本的 regression 沒有做好，我們就將剩餘的 residuals 當作另外一個 regression 問題處理，再將結果附到原先的模型上。
最後，線性組合所有的 gt(x)，以獲得更好的模型。每個模型的貢獻度 αₜ 利用求解 one-variable-linear regression 決定，縮放 gt(x) 以更接近 residuals (yn-sn)。
Algorithm1. Initialize predicted values: s₁ = s₂ = ... = sₙ = 0
2. Iterate t = 1, 2, ... ,T
(1) Obtain gₜ via a regression model A({xₙ, yₙ-sₙ})
(2) Compute αₜ
= One-Variable-Linear-Regression
(3) Update predicted values: sₙ ← sₙ + αₜgₜ(xₙ)
3. Return G(x) = Σₜαₜgₜ(x)
Adaptive Boosted Decision Tree and Gradient Boosted Decision Tree
就如同 random forest 是 bagging + decision tree 一樣，要做分類問題可以用 adaboosted + decision tree，要做 regression 的話則是用 gradient boost + decision tree。
根據權重 weighted D with u⁽ᵗ⁾ 將 Ein 做到最好。但是要怎麼決定權重放哪？之前是 Ein 在哪裡就放哪裡。可是 DT 不像 SVM 之類的演算法一樣很清楚地知道 Ein 在哪裡。解法是類似於 bootstrap，可以依照權重做 sampling，有多少權重就在抽樣佔多少比例。這樣就不用修改演算法本身。
通常都要拿比較弱的 DTree，也就是 pruned tree、或是限制樹的高度，且不要使用所有的資料，可以透過 sampling（正比於 u⁽ᵗ⁾ ） 只抽樣部分資料。因為如果樹太強，讓 error = 0，則 αₜ 會是無限大 → 獨裁的樹，也就失去做 boost 的意義。
Adaboosted Decision Tree
AdaBoosted Decision Tree1. Initialize data weights u⁽¹⁾ = [1/N, 1/N, ...]
2. Iterate t = 1, 2, ... ,T
(1) gₜ(x) = DecisionTree(weighted D with u⁽ᵗ⁾)
(2) εₜ = Σₙuₙ⁽ᵗ⁾[yₙ≠gₜ(xₙ)] / Σₙuₙ⁽ᵗ⁾ ← 錯誤率
βₜ = √[(1-εₜ)/εₜ]
αₜ = ln(βₜ) ← 調高權重
(3) Update weights
- If correct [yₙ=gₜ(xₙ)]: uₙ⁽ᵗ⁺¹⁾ ← uₙ⁽ᵗ⁾ × βₜ
- If wrong [yₙ≠gₜ(xₙ)]: uₙ⁽ᵗ⁺¹⁾ ← uₙ⁽ᵗ⁾ ÷ βₜ
3. Return G(x) = sign[Σₜαₜgₜ(x)]
Gradient Boosted Decision Tree
Gradient Boosted Decision Tree1. Initialize predicted values: s₁ = s₂ = ... = sₙ = 0
2. Iterate t = 1, 2, ... ,T
(1) gₜ = DecisionTree({xₙ, yₙ-sₙ})
(2) Compute αₜ
= One-Variable-Linear-Regression
(3) Update predicted values: sₙ ← sₙ + αₜgₜ(xₙ)
3. Return G(x) = Σₜαₜgₜ(x)
想要更深入了解的話，別忘了去最上面的目錄看其他章的課程筆記！
喜歡這篇文章或是對你有幫助的話，別忘了拍手給我鼓勵哦 👏🏻
