# AdaBoost-DTree

Random Forest 是把 Decision Tree 加上了 Bagging 做 Uniform 投票 。

AdaBoost-DTree 是把 Decision Tree 加上 AdaBoost 做 non-uniform / Linear 的投票。

## Sampling Proportional to $u_{n}$

AdaBoost 我們都知道是要修改成帶權重的 $E_{in}$：

$$
E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum_{n=1}^{N}u_{n}\cdot err(y_{n},h(\mathbf{x}_{n}))
$$

要做 Virtual Copy 修改的話就必須要把整個演算法攤開來，找出有 $E_{in}$ 的地方進行修改。

但是現在我們覺得太麻煩了，希望把演算法當作黑盒子，我們只想要對資料動手腳就好。

方法很簡單，把 Virtual Copy 換成 Real Copy 就好；把 BAGging 從平均抽樣改成以資料的權重作為比例去抽樣。

>可以回顧 [第八週 Adaptive Boosting](https://hackmd.io/Vt4wNa_JR9iwbtTS-gx_jQ?both#Weighted-Base-Algorithm)

## ${\boldsymbol\alpha}$ & weak Tree

AdaBoost 希望的是集合弱弱的 $g_{t}$；當中 $\alpha$ 的部分一旦遇到 Fully-grown Tree，$\epsilon=0$

這樣的樹太強了，我們希望要會犯錯，弱一點的樹。

方法有：

- 樹方面：就是修枝或是限制高度
- 資料方面：不要用全部的資料
- 這點在採樣的時候已經順便做好了

## Special Case：Adaboost-Stump

高度限制在 1 ，並且計算不純度的時候[不是用 Gini 而是一般的分類錯誤](https://hackmd.io/@ShawnNTU-CS/SkCMtCf62#For-Classification)，就會退化成之前的 Adaboost-Stump。

---

# Optimization View of AdaBoost

:::warning
下面我們以最佳化的角度來看看 AdaBoost 到底做了甚麼。
:::

把 $u_{n}^{(t+1)}$ 回溯展開可以得到：

$$
u_{n}^{(T+1)}=u_{n}^{(t)}\cdot exp(-y_{n}\alpha_{t}g_{t}(\mathbf{x}_{n}))=u_{n}^{(0)}\cdot exp\left(-y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})\right)\\
=\frac{1}{N}exp\left(-y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})\right)
$$

>[因為統一使用乘號 $\cdot$ 所以才會有負號 $-y_{n}\alpha_{t}g_{t}$](https://hackmd.io/@ShawnNTU-CS/SJvNkG16h#Adaptive-Boosting-AdaBoost-Algorithm)

其中的 $\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})$，如果回顧之前 $G$ 的投票公式和 SVM 的距離公式：

$$
G(\mathbf{x}_{n})=\left(\sum_{t=1}^{T}\underbrace{\alpha_{t}}_{w_{t}}\underbrace{g_{t}(\mathbf{x}_{n})}_{z_{t}}\right)\\
distance=\frac{y_{n}\left(\mathbf{w}^{T}\mathbf{z}_{n}+b\right)}{\left\|\mathbf{w}\right\|}
$$

把 $\alpha_{t}$ 看作 $w_{t}$，$g_{t}(\mathbf{x}_{n})$ 看作是 $z_{t}$，會發現 $y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})$ **「大致上來說就是在某個空間中未標準化 (unnormalized) 的 margin」**。

> $G$ 原本是一個有限制的最佳化問題，所以可以轉成沒有限制的 [Lagrange Function](https://hackmd.io/I6TUxZjeSw270SMrwVDvUw?view#Lagrange-Function)
>因此 b 常數項會對應在 $\alpha_{n} \ge 0$ 轉換的限制項
>但後來就不需要了。

既然他是一個 margin ，那我們就會希望他越大越好。

## Exponential error measure / algorithmic error measure

$$
u_{n}^{(T+1)}=\frac{1}{N}exp\left(-y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})\right)=\frac{1}{N}exp(-y_{n}s)
$$

這是 AdaBoost 的 err：

$$
\widehat{err}_{ADA}=exp(-y_{n}s)
$$

當中的 $exp(-y_{n}s)$，就是老師在基石就提過的 err 中最後一塊拼圖，Exponential error measure；他也是 $err_{0/1}$ 的 Upper Bound。

$\widehat{err}_{ADA}$ 又叫做 algorithmic error measure。

# AdaBoost Error Function

所以我們來把每個 $\mathbf{x}_{n}$ 的 err 都加起來：

$$
\widehat{E}_{ADA}=\sum_{n=1}^{N}u_{n}^{(T+1)}=\frac{1}{N}\sum_{n=1}^{N}exp\left(-y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})\right)
$$

這樣就構成了我們的 AdaBoost Error Function。

# Concept from Gradient Descent

在 GD 中，目的是要從當前的 $\mathbf{w}$ 開始走，希望找到一個方向，還有要走的長度，讓 $E_{in}$ 可以最小：

$$
\min_{\left\|\mathbf{v}\right\|=1}E_{in}(\mathbf{w}_{t}+\eta\mathbf{v})\approx E_{in}(\mathbf{w}_{t})+\eta\mathbf{v}^{T}\nabla E_{in}(\mathbf{w}_{t})
$$
>後來發現跟 Gradient 走相反方向就可以達到最小，並且依據當前 Gradient 大小來決定要走多長。

現在同樣但有一點不一樣，我們改成希望找到「一個函數」，還有要走的長度 ，讓 $E_{in}$ 可以最小：

$$
\min_{h}\widehat{E}_{ADA}
=\frac{1}{N}\sum_{n=1}^{N}exp\left(-y_{n}\left(\sum_{t=1}^{T-1}\alpha_{t}g_{t}(\mathbf{x}_{n})+\eta h(\mathbf{x}_{n})\right)\right)\\
=\sum_{n=1}^{N}u_{n}^{(T)}exp(-y_{n}\eta h(\mathbf{x}_{n}))
$$

:::warning
雖然在上面比擬的時候 $\alpha_{t}$ 對到的是 $w_{t}$，$g_{t}(\mathbf{x}_{n})$ 對到的是 $z_{t}$。

但是在這裡，由於是「以比較特別的角度來看」，所以原本 $E_{in}(\mathbf{w}_{t}+\eta\mathbf{v})$ 中的 $\mathbf{w}_{t}$ 在這裡對應到的是 $\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})$；

- 原本 GD 要找的是「一個方向」，所以是從「原本的位置 $\mathbf{w}_{t}$」，以「要走的方向 $\mathbf{v}$」跨過 $\eta$ 距離。
- 這裡 AdaBoost 要找的是「一個函數」，所以是從「原本的位置 $\sum_{t=1}^{T-1}\alpha_{t}g_{t}(\mathbf{x}_{n})$」，以「要找的函數 $h(\mathbf{x}_{n})$」跨過 $\eta$ 距離。

可以發現 $\eta$ 會成為之後的 $\alpha$
:::

總之我們希望找到一個 $h$ 還有 $\eta$ 可以讓 $E_{in}$ 最小。

:::info
從 T 或從 T-1 開始沒有關係，改成從 T-1 是為了下面表示法方便。
:::

## 推導下去

經過 Taylor 一階展開，可以得到：

$$
\min_{h}\widehat{E}_{ADA}
=\sum_{n=1}^{N}u_{n}^{(T)}exp(-y_{n}\eta h(\mathbf{x}_{n}))\\
\approx\sum_{n=1}^{N}u_{n}^{(T)}(1-y_{n}\eta h(\mathbf{x}_{n}))\\
=\sum_{n=1}^{N}u_{n}^{(T)}-\eta\sum_{n=1}^{N}u_{n}^{(T)}y_{n}h(\mathbf{x}_{n})
$$

>$e^{-X}\approx 1-X$

所以可以知道想要使 $E_{in}$ 最小，就是要讓 $-\sum_{n=1}^{N}u_{n}^{(T)}y_{n}h(\mathbf{x}_{n})$ 最小。

最後把 $y_{n}$ 跟 $h(\mathbf{x}_{n})$ 兩種情形列出來，會得到：

$$
\sum_{n=1}^{N}u_{n}^{(T)}(-y_{n}h(\mathbf{x}_{n}))=
\sum_{n=1}^{N}u_{n}^{(T)}
\left\{\begin{matrix}
-1 &y_{n} = h(\mathbf{x}_{n})\\
1 &y_{n} \ne h(\mathbf{x}_{n})
\end{matrix}\right.\\
\\
=-\sum_{n=1}^{N}u_{n}^{(T)}+\sum_{n=1}^{N}u_{n}^{(T)}\cdot
\left\{\begin{matrix}
0 &y_{n} = h(\mathbf{x}_{n})\\
2 &y_{n} \ne h(\mathbf{x}_{n})
\end{matrix}\right.\\
$$

此時回顧：

$$
E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum_{n=1}^{N}u_{n}\cdot err(y_{n},h(\mathbf{x}_{n}))
$$

所以可以得到：

$$
-\sum_{n=1}^{N}u_{n}^{(T)} + 2NE_{in}^{\mathbf{u}}(h)
$$

所以我們得到一個重磅的結論：

:::success
要讓 $\widehat{E}_{ADA}$ 最小，就是要找到一個 $h$ 可以讓 $E_{in}^{\mathbf{u}}(h)$ 最小。
:::

此時回想 AdaBoost 的 $\mathcal{A}$，這不正是他每回合 t 在做的事情嗎，他每回合都在找一個 $h$ 可以讓 $E_{in}^{\mathbf{u}}(h)$ 最小。

## Optimal $\eta$

既然知道 $h$ 可以由 AdaBoost 的 $\mathcal{A}$ 找到，為了不浪費他的心血，希望「貪心一點」、「要走就走最大的一步」，可以讓當前的 $E_{in}$ 降到最小；在那之前先把原本 $\widehat{E}_{ADA}$ 的式子，依照 $y_{n}$ 跟 $h(\mathbf{x}_{n})$ 的兩種情形轉換一下：

$$
\widehat{E}_{ADA}
=\sum_{n=1}^{N}u_{n}^{(T)}exp\left(-\eta y_{n}h(\mathbf{x}_{n})\right)\\
\Rightarrow \left(\sum_{n=1}^{N}u_{n}^{(T)}\right)\cdot\left(\frac{\sum_{n=1}^{N}u_{n}^{(T)}[[y_{n}=g_{t}(\mathbf{x}_{n})]]}{\sum_{n=1}^{N}u_{n}^{(T)}}exp(-\eta)+\frac{\sum_{n=1}^{N}u_{n}^{(T)}[[y_{n}\ne g_{t}(\mathbf{x}_{n})]]}{\sum_{n=1}^{N}u_{n}^{(T)}}exp(\eta)\right)\\
=\left(\sum_{n=1}^{N}u_{n}^{(T)}\right)\cdot \biggl((1-\epsilon_{t})exp(-\eta)+\epsilon_{t}exp(\eta)\biggr)
$$

對 $\eta$ 微分後可以驚人的發現：

$$
\eta=ln\left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)=\alpha_{t}
$$

# Optimization View of AdaBoost 總結

經過上面推導，可以發現：

- $\mathcal{A}$ 每次為了最小化 $E_{in}^{\mathbf{u}}(h)$ 而找到的 $h$，就是可以讓 $\widehat{E}_{ADA}$ 最小的函數
- 以此函數作為方向，走最貪心、最大步，會發現步寬剛好就是每次算出的 $\alpha_{t}$

也就是說 AdaBoost 實際上每一步就是在做最佳化的動作。

## Steepest descent

像這樣只走「眼前、當下最大的一步」的走法，就叫做 Steepest descent。

## Approximate Functional Gradient

如同前面提到的，由於前面在最小化的時候不是「找一個向量」，而是「找一個函數」，這種叫做 Functional Gradient；並且由於用上了 Taylor 一階展開，或者說線性逼近，所以有個 Approximate 前綴。

---

# Gradient Boosting

如果把 Approximate Functional Gradient 的概念拓展到不同的 err，這個酷東西就叫做 Gradient Boosting。

這是 AdaBoost：

$$
\min_{\eta}\min_{h}\frac{1}{N}\sum_{n=1}^{N}exp\left(-y_{n}\left(\sum_{t=1}^{T-1}\alpha_{t}g_{t}(\mathbf{x}_{n})+\eta h(\mathbf{x}_{n})\right)\right)
$$

這裡的 $h$ 輸出是 1 或 -1；也就是 Binary-Output Hypothesis。

下面是 Gradient Boost：

$$
\min_{\eta}\min_{h}\frac{1}{N}\sum_{n=1}^{N}err\left(\sum_{t=1}^{T-1}\alpha_{t}g_{t}(\mathbf{x}_{n})+\eta h(\mathbf{x}_{n}),y_{n}\right)
$$

可以使用任意的 $h$，並且通常是輸出為實數的 $h$，也就是 Real-Output Hypothesis。

:::info
於是我們就有了可以拿來做 Regression、Soft Classification 等等的 GradientBoost；而 AdaBoost 算是 GradientBoost 拿來做 Binary Classification 的其中一種。
:::

---

# GradientBoost for Regression

$$
err(s,y)=(s-y)^{2}
$$

使用一階泰勒展開：

>$f(\mathbf{x}+\mathbf{a})\approx f(\mathbf{x})+f'(\mathbf{x})\cdot \mathbf{a}$
>跟 exp 的推導過程一樣，都是以 $s_{n}=\sum_{t=1}^{T-1}\alpha_{t}g_{t}(\mathbf{x}_{n})$ 作為變數 $x_{n}$

$$
\min_{h}\frac{1}{N}\sum_{n=1}^{N}\underbrace{err(s_{n},y_{n})}_{constant}+\frac{1}{N}\sum_{n=1}^{N}\eta h(\mathbf{x}_{n})\frac{\partial err(s,y_{n})}{\partial s}\Large|_{s=s_{n}}\\
=\min_{h}constant+\frac{\eta}{N}\sum_{n=1}^{N}h(\mathbf{x}_{n})\cdot 2(s_{n}-y_{n})
$$

這時會出現不同 $h$ 所擁有的特色；原本 AdaBoost 的 $h$ 是輸出 Binary，但是這裡的 $h$ 是輸出實數，所以如果上面取 min 會發生跑到負無限大這件事，因此我們需要對 $h$ 做限制。

但其實我們不需要特別說要限制多少，因為 $\eta$ 這個係數會幫我們處理好，我們只需要「處罰」大的值就好：

$$
\min_{h}\color{gray}{constant+\frac{\eta}{N}}\sum_{n=1}^{N}2h(\mathbf{x}_{n})(s_{n}-y_{n})+(h(\mathbf{x}_{n})^{2})
$$
>老師說利用[類似 lagrange multiplyer 的概念](https://hackmd.io/I6TUxZjeSw270SMrwVDvUw?view#Lagrange-Function)，但我同時也很像 regularizer

有了處罰項之後，整理一下：

$$
\min_{h}\color{gray}{constant+\frac{\eta}{N}}\sum_{n=1}^{N}\left(h(\mathbf{x}_{n}) - (y_{n}-s_{n})\right)^{2}
$$

驚人的發現，上面這個樣子，就是一個經典的 Regression 問題。

也就是說每次 $\mathcal{A}$ 在找 $h$ 的時候，其實就是去算 $\mathbf{x}_{n}$ 們對 $y_{n}-s_{n}$ 這個 residual 項做線性回歸，[可以使用之前的公式解](https://hackmd.io/@ShawnNTU-CS/ryXNKME3h)。

$y_{n}-s_{n}$ 就是我們尚未達成的部分，希望這個尚未達成的部分可以交由 $h$ 去更進一步。

有了 $h$ 後，一樣處理 $\eta$：

$$
\min_{\eta}\frac{1}{N}\sum_{n=1}^{N}(s_{n}+\eta h(\mathbf{x}_{n})-y_{n})^{2}\\
=\min_{\eta}\frac{1}{N}\sum_{n=1}^{N}((y_{n}-s_{n})-\eta h(\mathbf{x}_{n}))^{2}
$$

這個樣子一樣是個 Regression 問題，而且是個單變數的 Regression，直接列出解：

$$
\eta=\frac{\sum_{n=1}^{N}h(\mathbf{x}_{n})(y_{n}-s_{n})}{\sum_{n=1}^{N}(h(\mathbf{x}_{n}))^{2}}
$$

## GradientBoost for Regression 演算法

- 一開始全部點的 $S_{n}$ 都是 0。
- 執行迴圈：
- 算出 $h$ 跟 $\eta$
- 更新 $s_{n}$：
- $$s_{n}^{t+1}=s_{n}^{t}+\alpha_{t}g_{t}(\mathbf{x}_{n})$$
- 回傳 $G(\mathbf{x})=\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x})$

:::warning
在 AdaBoost 中，一樣可以去更新 $s_{n}$，但是下一次的 $g_{t+1}$ 需要最小化的 $E_{in}^{\mathbf{u}}(h)$ 中的 $u_{n}$ 也要更新：

$$
u_{n}^{(T+1)}=\frac{1}{N}exp\left(-y_{n}\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x}_{n})\right)
$$

並且整個 AdaBoost 中並沒有用到 $s_{n}$ 的地方，所以實際上 AdaBoost 中並不需要做更新 $s_{n}$ 的動作。

在 GradientBoost 中，每次新的 $g_{t+1}$ 就是要解決 $\mathbf{x}_{n}$ 對 $(y_{n}-s_{n})$ 的 Regression 問題，所以只需要更新 $s_{n}$ 就好；並且也沒有 $u_{n}$ 需要進行更新。
:::

:::info
總的來說，兩種 Boost 演算法都會對某個更新過的內容做最佳化：
- AdaBoost 每輪會更新 $u_{n}^{t}$ 來放大某些資料的重要性
- GradientBoost 更新 $s_{n}$，由 $(y_{n}-s_{n})$ 來著重尚未做的好的部分。
:::

---

# Gradient Boosted Decision Tree (GBDT)

- AdaBoost Decision Tree 是把 Adaboost 中的 $g_{t}$ 從 Decision stump 換成 Decision Tree
- 並且為了避免修改原本樹舊有的演算法，每輪根據 $u_{n}$ 的比例執行 Real Copy
- 來達到調整權重的目的
- Gradient Boosted Decision Tree，這裡以做 Regression 的來說：
- [把做 Regression 的決策樹](https://hackmd.io/@ShawnNTU-CS/SkCMtCf62#Impurity-function)，每層分枝時計算的 Regression 問題， $y_{n}$ 改成 $y_{n}-s_{n}$
- 並且搭配修剪 pruned 和採樣

:::info
不確定 GBDT 要怎麼做採樣
:::

## GBDT 演算法

- 一開始全部點的 $S_{n}$ 都是 0。
- 執行迴圈：
- 算出 $h$ 跟 $\eta$
- 更新 $s_{n}$：
- $$s_{n}^{t+1}=s_{n}^{t}+\alpha_{t}g_{t}(\mathbf{x}_{n})$$
- 回傳 $G(\mathbf{x})=\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x})$

>所以一層的 GBDT 也會退化回 GB。

---

# Aggregation Model 總結

## Blending

Blending 是指在學會 $g_{t}$ 後把他們混在一起。

- uniform
- voting
- averaging
- non-uniform
- 經由 $g_{t}$ 轉換成新資料的 linear model
- conditional
- 經由 $g_{t}$ 轉換成新資料的 non linear model

uniform 追求的是穩定性；而 non-uniform 和 conditional，因為是經過一次學習轉換後再一次學習，所以會更為強大，但也因此要小心 Overfitting 的發生。

## Aggregation-Learning

Aggregation-Learning 是指一邊混在一起，一邊學會新的 $g_{t}$。

### 四大基礎工具：

- `Uniform`：`BAGging`
- uniform vote
- 經由 Bootstrapping 學會新的 $g_{t}$。
- `Linear`：`AdaBoost`
- linear vote，使用 steepest search 找到 $\alpha$
- 經由 Reweighting 學會新的 $g_{t}$。
- `Linear`：`GradientBoost`
- linear vote，使用 steepest search 找到 $\alpha$
- 經由 Residual Fitting 學會新的 $g_{t}$。
- `Conditional`：`Decision Tree`
- conditional vote，透過 Branching 學會。
- 經由 Data Splitting 學會新的 $g_{t}$。

### 三大混合工具

- Random Forest
- radomized Bagging + strong DTree
- AdaBoost-DTree
- AdaBoost + weak DTree
- GBDT
- GradientBoost + weak DTree

:::success
Aggregation Model，有的可以治療 underfitting，例如 AdaBoost，因為把很多個合起來，就好像是做了 Feature Transform；

有的可以治療 overfitting，例如 Random Forest，因為合起來就好像是做了中庸的選擇，所以有 large margin 的效果，就好像做了 Regularization。

總之各個模型所擅長的不一樣，只要知道何時用哪種，交互使用他們，就可以達到很好的表現。
:::