---
tags: 機器學習技法
---

Ch11 Gradient Boosted Decision Tree
===

## Content
[TOC]

## [Slides & Videos](https://www.csie.ntu.edu.tw/~htlin/mooc/)

## [Adaptive Boosted Decision Tree](https://www.coursera.org/learn/machine-learning-techniques/lecture/pWVz1/adaptive-boosted-decision-tree)

### From Random Forest to AdaBoost-DTree

- 要把 decision tree 跟 adaboost 結合，就要讓 decision tree 能夠接受每筆 data 有不同 weight $u$

### Weighted Decision Tree Algorithm

- 一種加 weight 的方式就是直接把 algorithm 攤開來看，看哪些部份是跟 data 的 weight 會有關係的，我們把 weight 加進去
- 但是像 decision tree 這種 algorithm 有許多作者自己的巧思，全都拆開來看太麻煩了，我們就直接把演算法當成 black box，直接對 data 動手腳即可
- 根據權重 $u$ 對 data 做 sampling，這樣就不需要修改演算法。

### Weak Decision Tree Algorithm

- fully grown 的 tree 會導致 $\alpha_t$ 幾乎是無限大，這樣就沒有 aggregation 了
- 我們需要: **pruned** tree trained on **some** $x_n$ to be **weak**
- some: sampling 即可算是只 train 在部分 data
- pruned: pruning or limiting height
- AdaBoost-DTree: often via
- AdaBoost + sampling $\propto u^{(t)}$ + pruned $\textrm{DTree}(\tilde{\mathcal D})$

### AdaBoost with Extremely-Pruned Tree

- 若 tree 只有一層高，其實就是 decision stump
- 因此 AdaBoost-Stump = special case of AdaBoost-DTree

### Fun Time: Weights of AdaBoost-DTree

- 在 $\tilde{\mathcal D}$ 上 zero-error，但是在 $\mathcal D$ 上什麼 $\epsilon$ 都有可能
- > Q: 不是也應該是 0 嗎 @@，sample data 的 weight $u$ 有可能有 0 嗎? 沒有 0 的話 $\mathcal D$ 的 error 應該也是 0 吧?
- > 可能是因為雖然 $u$ 不會變 0，但是 sample 可能會沒 sample 到吧

## [Optimization View of AdaBoost](https://www.coursera.org/learn/machine-learning-techniques/lecture/fTNGj/optimization-view-of-adaboost)

### Example Weights of AdaBoost

- 本來的 $u_n^{(t+1)}$ 可以寫成 $u_n^{(t)}\cdot 菱形_t^{-y_ng_t(x_n)}$
- $u_n^{(t+1)}$: 第 n 筆資料下一次的權重
- 當初的 $菱形_t=\exp(\alpha_t)$
- 因此原式 $u_n^{(t+1)} = u_n^{(t)}\cdot\exp(-y_n\alpha_t g_t(x_n))$
- 這樣就可以用 $u_n^{(1)}$ 表示了 (注意 $u_n^{(1)}=\frac 1 N$)，然後再把連乘移到指數變連加，可以得到 $u_n^{(T+1)}=\frac 1 N\cdot\exp(-y_n\sum_{t=1}^T \alpha_t g_t(x_n))$
- 回想一下我們整個 model 的 prediction $G(x)=\textrm{sign}(\sum_{t=1}^T \alpha_t g_t(x))$，prediction 是根據這個加總而定的
- 因此我們先把這個 $\sum_{t=1}^T \alpha_t g_t(x)$ 命名為 **voting score** (以 $\alpha_t$ 為 voting weight)
- 也就是說，data 的 weight 可以視為 $\propto \exp(-y_n(\textrm{voting score on }x_n))$
- 等等針對 voting score 進行探討。
- (直覺: ensemble 結果越正確，新權重越小)
- 這裡可以先 review [Ch8 AdaBoost](https://hackmd.io/@johnnyasd12/ryDZnL_kI/https%3A%2F%2Fhackmd.io%2F%40johnnyasd12%2FBk1joyIZU)
- $u_n^{(t)}$ 用來找 $g_t$
- $g_t$ 用來找 $u_n^{(t+1)}$

### Voting Score and Margin

- 之前說過，linear blending 可以視為 linear model + hypotheses as transform，因此**我們把 $\alpha_t$ 看成是 $w_i$；$g_t(x_n)$ 看成是 feature transform $\phi_i(x_n)$**
- $w_i$ 即轉換後的第 $i$ 個 feature 的權重
- 回顧 SVM，$\frac{y_n w^T\phi(x_n)}{\|w\|}$ 是 「$x_n$ 距離邊界有多遠」，即 margin
- > Q: 可能要回去複習+確認一下QQ
- 注意 $b$ 並不影響幾何意義
- 這樣 $y_n(\textrm{voting score})$ 就可以看成是未正規化的 margin
- 若是 SVM，則我們希望 margin 越大越好
- margin 越大
- $\leftrightarrow\exp(-y_n(\textrm{voting score}))$ 越小
- $\leftrightarrow u_n^{(T+1)}$ 越小
- 而 AdaBoost 有一個性質：$\sum_{n=1}^N u_n^{(t)}$ 會隨著 $t$ 而越來越小，這樣也就可以導致 large margin 的效果
- 等等就來證明 權重加總會越來越小

### AdaBoost Error Function

- 如果說 AdaBoost 試著減少 $\sum_{n=1}^N u_n^{(t)}$，也可以說是減少 $\sum_{n=1}^N u_n^{(T+1)}=\frac 1 N \sum_{n=1}^N \exp(-y_n\sum_{t=1}^T \alpha_t g_t(x_n))$
- 我們把 $\sum_{t=1}^T \alpha_t g_t(x_n)$ 當成 score $s$，可以看出我們在 minimize $\exp(-ys)$，而這也是 0/1 error 的 upper bound
- $\widehat{err}_{ADA}(s,y)=\exp(-ys)$ 這又稱做 **exponential error measure**

### Gradient Descent on AdaBoost Error Function
- 但是 AdaBoost 真的可以做到好嗎?
- > Q: 這裡指的是 minimize $\sum_{n=1}^N u_n^{(T+1)}$ 嗎?
- 回顧基石教的 gradient descent，我們要找一個最好的向量 $v$ (方向)，而我們在基石已經推導出最好的方向就是負的梯度的方向
- 那麼我們現在跟 gradient descent 一樣，要找一個最好的函數(函數可以視為向量)，來優化 error function $\hat E_{ADA}$
- 會說函數可以視為向量，是因為函數跟向量都是 input 一個數字(整數/實數)，然後會 output 一個 scalar
- 這樣 $\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(x_n)$ 部分就可以視為「現在的位置」
- 而 $h(\cdot)$ (也就是新的 $g_t$) 就可以視為最佳的方向
- 又紫色部分可以化簡為 $u_n^{(t)}$，因此 $\widehat E_{ADA} = \sum_{n=1}^N u_n^{(t)}\exp(-y_n\eta h(x_n))$
- 在原點附近做泰勒展開 (線性逼近)，可以得到 $\sum_{n=1}^N u_n^{(t)}(1-y_n \eta h(x_n))$
- > Q: 可能要回去複習一下泰勒展開...
- 然後就可以拆成 $\sum_{n=1}^N u_n^{(t)} - \eta \sum_{n=1}^N u_n^{(t)}y_n h(x_n)$
- 前面那項(在 gradient descent 所扮演的角色?) 就是「目前的 $E_{in}$」了
- > Q: 是因為這項是已知的? 還是真的是 $E_{in}$?
- 好像是因為是目前以 $u$ 為 weight 的 0/1 error?
- 既然要找到一個 $h$ 來最小化整個式子，那就跟前面那項無關啦，所以我們專心最小化後面那項的 $\sum_{n=1}^N u_n^{(t)}(-y_n h(x_n))$

### Learning Hypothesis as Optimization

- 注意這裡 $h(x)$ 跟 $y$ 一樣是 $\in\{+1,-1\}$
- 利用以上性質分別討論後可以得到 $\sum_{n=1}^N u_n^{(t)}(-y_n h(x_n))=-\sum_{n=1}^N u_n^{(t)}+2E_{in}^{u^{(t)}}(h)\cdot N$
- $E_{in}^{u^{(t)}}(h)$ 應該就是以 $u$ 為權重的 0/1 error
- 也就是說 AdaBoost 找一個好的 $g_t=h$ 這樣的「方向」來讓 $E_{in}^u$ 變小??
- > Q: 不太確定結論是不是這樣，以及因果關係，可能要再梳理一下整個脈絡

### Deciding Blending Weight as Optimization

- 我們除了想找出最好的 $g_t$，其實也想在找到 $g_t$ 之後，找出最好的 $\eta$ (跨大步一點)，因為 $\eta$ 太小的話就要求很多個 $g_t$，cost 太大
- 這又叫 steepest gradient descent
- 利用剛剛說的 $h(x)\in\{+1,-1\}$ 就可以故技重施，分別討論
- 第 $n$ 筆 data 若預測正確，summation 當中的該項就會是 $u_n^{(t)}\exp(-\eta)$
- 這樣的 data 占全部的 $1-\epsilon_t$
- 第 $n$ 筆 data 若預測錯誤，summation 當中的該項就會是 $u_n^{(t)}\exp(\eta)$
- 這樣的 data 占全部的 $\epsilon_t$
- 所以 $\widehat E_{ADA}=(\sum_{n=1}^N u_n^{(t)})((1-\epsilon_t)\exp(-\eta)+\epsilon_t \exp(\eta))$
- 最佳解在微分$\frac{\partial\widehat E_{ADA}}{\partial\eta}=0$，可以導出 $\eta_t=\ln\sqrt{\frac{1-\epsilon_t}{\epsilon_t}}=\alpha_t$
- 所以 AdaBoost 的另外一個解釋就是，叫後面的 algorithm 找出一個好的方向(函數) $g_t$，做 steepest gradient descent
- 而且這個 gradient 是 functional gradient (因為是在函數的世界做 gradient descent)

## [Gradient Boosting](https://www.coursera.org/learn/machine-learning-techniques/lecture/LsWkO/gradient-boosting)

### Gradient Boosting for Arbitrary Error Function

- 之前的討論已經得知：AdaBoost 是在做兩個 optimization
- **AdaBoost**: $\min_\limits{\eta}\min_\limits{h}\frac 1 N\sum_\limits{n=1}^N\exp(-y_n(\sum_\limits{\tau=1}^{t-1}\alpha_\tau g_\tau(x_n)+\eta h(x_n)))$
- 那我們可不可以不 minimize exponential error 呢? 可不可以 minimize cross entropy / square error 之類的? 擴展它? 這就叫 gradient boosting。
- **GradientBoost**: $\min_\limits \eta \min_\limits h \frac 1 N \sum_\limits{n=1}^N err(\sum_\limits{\tau=1}^{t-1}\alpha_\tau g_\tau(x_n)+\eta h(x_n),y_n)$

### GradientBoost for Regression

- 現在先把 $\sum_\limits{\tau=1}^{t-1} \alpha_\tau g_\tau(x_n)$ 寫做 $s_n$ (即第 $n$ 筆資料的 score)
- 想要找到 $\eta$ 跟 $h$ 使得 error function $(s-y)^2$ 加總最小
- (做泰勒展開?) 得到 $\frac 1 N\sum_{n=1}^N err(s_n,y_n)+\frac 1 N\sum_{n=1}^N\eta h(x_n)\frac{\partial err}{\partial s}|_{s_n}$
- 微分要在現在的位置 (也就是 $s_n$) 取值
- > Q: 回去複習泰勒展開啦!!
- 因為是要找 $h$ 所以重點是把後面那項 $\sum_{n=1}^N h(x_n)\cdot 2(s_n-y_n)$ 做到好
- 但是如果不限制 $h$ 的話就有個問題
- $s_n-y_n$ 如果是正的，那就讓 $h(x_n)$ 是負無限大
- $s_n-y_n$ 如果是負的，就讓 $h(x_n)$ 是正無限大。
- 也就是說讓 $h(x_n)=-\infty\cdot(s_n-y_n)$ 即可。
- 回想，當做 gradient descent 的時候我們不希望它變負無限大，我們只是想要找到對的方向，因此直接限制他的大小為 1。
- > Q: 雖然負無限大怪怪的，但為何不行?
- 反正之後會找一個 $\eta$ 來決定要跨多大步。

### Learning Hypothesis as Optimization (GradientBoost)

- 這樣的話我們也來照著當初推導 gradient descent 的方式，限制 $h(x)$ 的大小
- 把本來想要 minimize 的 $2h(x_n)(s_n-y_n)$ 加上 $h(x_n)^2$
- 然後發現可以整理成平方的形式 $(h(x_n)-(y_n-s_n))^2-(y_n-s_n)^2$
- 而這個 $(y_n-s_n)^2$ 對 $h$ 來說是 constant 因此 minimize 過程這項可以省略
- 發現最終式子 $\min_\limits h \sum_{n=1}^N(h(x_n)-(y_n-s_n))^2$ 其實就是在解一個 **regression with residual** 的問題
- 註：residual 即 $y_n-s_n$

### Deciding Blending Weight as Optimization

- 找到 $g_t$ 之後要找 $\eta$ 其實就相當於做 linear regression
- input 是經由 $g_t$ transform 之後的 input
- output 是 residual

### Putting Everything Together

- 這就是 AdaBoostDTree 的 regression 版本

## [Summary of Aggregation Models](https://www.coursera.org/learn/machine-learning-techniques/lecture/u1D3V/summary-of-aggregation-models)

### Map of Blending Models

- 「已給定」數個 model，如何做結合
- uniform blending
- 簡單且穩定
- non-uniform blending (linear or nonlinear)
- 強大，但要面臨 overfitting 的風險
- linear
- nonlinear
- 又稱 stacking
- > Q: 那 linear 算嗎? 要回去複習 Blending 了...

### Map of Aggregation-Learning Models


### Map of Aggregation of Aggregation Models

### Specialty of Aggregation Models

- aggregation (a.k.a. **ensemble**)
- 不同的 aggregation 可以有不同的效果

### Summary