# Concept From BAGging

BAGging 中，由於是從 $\mathcal{D}$ 抽資料出來組成 $\tilde{\mathcal{D}}$，所以有可能會有重複的資料。

因此我們可以將原本的 $E_{in}$：

$$
E_{in}^{0/1}(h)=\frac{1}{N}\sum_{(\mathbf{x},y)\in\tilde{\mathcal{D}}}[[y\ne h]]
$$

改寫為：

$$
E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum_{n=1}^{N}u_{n}[[y_{n}\ne h(\mathbf{x}_{n})]]
$$

也就是說：

- 沒抽到的資料 $u_{n}=0$
- 抽到一次的資料 $u_{n}=1$
- 抽到 $k$ 次資料 $u_{n}=k$

這樣的表示法「**將次數作為權重**」。

:::warning
所以每次 BAGging 出來的新資料集，**抽到比較多次的資料在該資料集中就會比較重要**。
:::

---

# AdaBoost 核心概念

從 BAGging 改進，變成自己調整資料的重要程度。

每一次學到新的 $g_{t}$ 時，會將當前 $g_{t}$ 犯錯的資料「變得重要」，沒犯錯的則「變得不重要」，然後以這個更改重要性的資料再去學新的 $g_{t}$。

經過每一輪更改重要性的操作可以讓前後兩個 $g_{t}$ 之間具有差異性，以達到 blending 所要求的多樣性。

## Re-weighting

原本 $u^{t}_{n}$ 是從 Bootstraping 得到的資料中，代表第 n 筆資料「有幾份」，同時也代表著重要程度。

為了不要讓當前的 $g_{t}$ 在下一輪也會被生產出來，所以得將資料的「份數」做修改，讓預測成功跟錯誤的量達到 1 比 1。

換句話說就是讓 $g_{t}$ 在新資料中跟投骰子一樣，對錯機率都是 $\frac{1}{2}$，沒有預測的效果，也因此會跟 $g_{t+1}$ 具有差異性。

所以以此推導下去可知可以將錯誤的份數乘上成功的份數，成功的份數乘上錯誤的份數，兩者份數就一樣。

## $\mathbf{u}^{t}$

但這樣份數會持續變大，會有點困擾；所以想要改成乘「成功率跟錯誤率」，而原本的 $u^{t}_{n}$ 也從份數變成了佔總體比例。

這樣做不會影響：

$$
\frac{1}{2}=\frac{\sum_{n=1}^{N}u_{n}^{t+1}[[y_{n}\ne g_{t}(\mathbf{x}_{n})]]}{\sum_{n=1}^{N}u_{n}^{t+1}[[y_{n}\ne g_{t}(\mathbf{x}_{n})]]+\sum_{n=1}^{N}u_{n}^{t+1}[[y_{n} = g_{t}(\mathbf{x}_{n})]]}=\frac{錯誤次數}{成功次數+錯誤次數}=錯誤率
$$

因為 $u^{t}_{n}$ 從份數變為比例，只不過是上下同除 $N$；成功率和錯誤率其分母的 N 在計算時也可以被通分掉。
>這個 N 是由包含前幾輪的總共份數的乘積所構成：$N_{1}N_{2}...N_{t}$

## 縮放參數

上面的想法很美好，但是會遇到一個問題，首先 $u^{t}_{n}$ 已經讓他小於 1 了，然後每輪又給他乘以一個小於 1 的數值，這樣一直乘下去就會越來越小。

所以聰明的...這方面的專家想到的是「縮放參數」：

$$
\sqrt{\frac{1-\epsilon}{\epsilon}}=\sqrt{\frac{成功率}{錯誤率}}=\sqrt{\frac{成功次數}{錯誤次數}}
$$

這個函數的特點是，如果成功率大於錯誤率，縮放參數會大於 1，反之會小於 1；並且「成功的除以縮放參數，失敗的乘上縮放參數」這個操作不會影響上面 $\frac{1}{2}$ 的計算：

$$
\frac{錯誤次數\times\sqrt{\frac{成功次數}{錯誤次數}}}{成功次數{\div}\sqrt{\frac{成功次數}{錯誤次數}}+錯誤次數\times\sqrt{\frac{成功次數}{錯誤次數}}}=\frac{\sqrt{成功次數\times錯誤次數}}{\sqrt{成功次數\times錯誤次數}+\sqrt{成功次數\times錯誤次數}}=\frac{1}{2}
$$

這樣一來保持了 $\frac{1}{2}$，二來有時大於 1 有時小於 1 可以避免越乘越小的問題，雖然我不是數學家，但這聽起來超厲害對吧。

## 持有投票量 $\alpha_{t}$

這裡使用票票不等值，總不能有些真的很差的 $g_{t}$ 還給一樣的票。

所以聰明的專家們使用的是具有單調性質的 $ln$：

$$
\alpha_{t}=ln\left(\sqrt{\frac{1-\epsilon}{\epsilon}}\right)
$$

這函數的特性是，如果成功率是 $\frac{1}{2}$，代表這個 $g_{t}$ 跟投骰子沒兩樣，不要參考他，所以票量 $\alpha_{t}=0$；如果成功率接近 1，根號內的值就會很大，票量也會很大。
>如果錯誤率是 0 的話就變成無限大了，代表直接選他

# Adaptive Boosting (AdaBoost) Algorithm

初始權重：$\mathbf{u}^{(1)}=[\frac{1}{N},\frac{1}{N},...,\frac{1}{N}]$
- 也就是說每個資料一樣重要

執行 T 次迴圈，對於第 t 次：
- $\mathcal{A}$ 從 $\mathcal{D}$ 中為了最小化 $E_{in}^{\mathbf{u}}(h)$ 而學到 $g_{t}$
- $\frac{1}{N}\sum_{n=1}^{N}u_{n}[[y_{n}\ne h(\mathbf{x}_{n})]]$
- 實際上可以不用管 $\frac{1}{N}$ 這個係數。
- 使用縮放參數更新錯誤率
- 對於預測錯誤的資料的權重，「乘上」縮放參數
- 對於預測正確的資料的權重，「除以」縮放參數
- 其中縮放參數為 $\sqrt{\frac{1-\epsilon}{\epsilon}}$，$\epsilon=\frac{\sum_{n=1}^{N}u_{n}^{t}[[y_{n}\ne g_{t}(\mathbf{x}_{n})]]}{\sum_{n=1}^{N}u_{n}^{t}}$
- 或者說縮放參數為 $\sqrt{\frac{正確率}{錯誤率}}$，$\epsilon=錯誤率$
- 計算 $g_{t}$ 的持有投票量 $\alpha_{t}=ln(縮放參數)$

最後回傳 $G(\mathbf{x})=sign\left(\sum_{t=1}^{T}\alpha_{t}g_{t}(\mathbf{x})\right)$；如果不是 Classification 的話就是其他 Blending。

:::warning
再次注意 $E_{in}^{\mathbf{u}}(h)$ 是 Error Function，跟底下的 $\epsilon$ 錯誤率不一樣。
:::

# Theoretical Guarantee

可以從 [VC Bound](https://hackmd.io/r5nQOa1wS3-QKFpjHj3jbw?view#Model-Complexity) 證明出：

$$
E_{out}(G)\le E_{in}(G)+O\left(\sqrt{\underbrace{O(d_{vc}(\mathcal{H})\cdot Tlog(T))}_{d_{vc}\text{ of all possible G}}\cdot\frac{log(N)}{N}}\right)
$$

然後 Adaboost 的作者也有證明，只需要 $T=log(N)$ 就可以讓 $E_{in}=0$，只要每次的錯誤率都可以小於 $\frac{1}{2}$ 就好。

一旦 $T=log(N)$，那就代表 $d_{vc}$ 會跟著 T 緩慢的成長，也就讓 $E_{out}$ 一樣很小。

## Boosting

像這樣只要求 base Algorithm 的 $\mathcal{A}$ 不用太強，只要每次都可以比亂猜還要好，聚集起來後就可以很強大的效果叫 Boosting。

Adaboost 是逐步做到 Boosting 的演算法。

---

# AdaBoost-Stump

以 Decision stump 作為 base Algorithm。

Decision stump 就剛好符合我們需要的特性，雖然弱弱的，但是比亂猜好。

## 人臉辨識

AdaBoost-Stump 是第一個能夠做到「實時」人臉辨識的方法。

### Feature Selection

將圖片分成很多個小小圖片 patches，用 Adaboost 去學會哪種 patches 具有重要的特徵，最後用 Linear Aggregation 整合起來。

但是在判斷 patches 時有將 Linear Aggregation 稍微修改一下，因為圖片中如果是遠景，大部分都不會是人臉，所以如果計算到一半時 G 的分數夠低了就會直接判斷該 patch 沒有人臉。

---

# Weighted Base Algorithm

在 $E_{in}$ 中帶有權重的叫做 Weighted Base Algorithm。

## 以選取產生帶權資料

原本沒有權重的 $E_{in}^{0/1}(h)$ 各自演算法有對應的理論保證可以最佳化；那帶有權重的 $E_{in}^{\mathbf{u}}(h)$ 我們有對應的理論保證可以最佳化嗎？

有，在 [基石上第八周](https://hackmd.io/Uq9IWK63TY2aaDruk-Sz6A?view#Weighted-Classification) 的時候老師提過了 Virtual Copy ；也就是帶有權重的 $E_{in}^{\mathbf{u}}(h)$ 其實跟另一種資料分佈的情境是等價的。

# Virtual Copy / Systematic route

- 當前的資料集 $\mathcal{D}$ 有 $(\mathbf{x}_{1},y_{1}),...(\mathbf{x}_{n},y_{n})$
- 從中以你想要的資料分佈 $\mathbf{u}$ 去抽 $M$ 筆資料出來組成新資料集 $\mathcal{D}_{M}$
- 這樣 $(\mathbf{x}_{1},y_{1}),...(\mathbf{x}_{n},y_{n})$ 的資料「份數」就會呈現出你想要的分佈
- 最後只要以這個新的資料集 $\mathcal{D}_{M}$ 來執行演算法，在算 $E_{in}$ 的時候：

$$
\left(E_{in}^{0/1}(h)=\frac{1}{M}\sum_{(\mathbf{x},y)\in\tilde{\mathcal{D}}}[[y\ne h]]\right)
\equiv
\left(E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum_{n=1}^{N}u_{n}[[y_{n}\ne h(\mathbf{x}_{n})]]\right)
$$

由於 LHS 有對應的理論保證可以最佳化 $E_{in}^{0/1}(h)$，也就代表 RHS 一樣有理論保證可以最佳化 $E_{in}^{\mathbf{u}}(h)$。

但是由於不會真的複製出 $\mathcal{D}_{M}$，而是直接用 $E_{in}^{\mathbf{u}}(h)$，所以才會叫做 Virtual Copy。

:::warning
所以在 $\mathcal{D}_{M}$ 中有「$N$ 種資料」，並且總共有「$M$ 筆資料」
:::

## Weighted Pocket PLA

如果 Pocket PLA 改成在 $\mathcal{D}_{M}$ 中做挑選點修正的動作，被複製出的點會更容易被抽到；因此使用 $E_{in}^{\mathbf{u}}(h)$ 的話，各個點被抽取的機率不再是平均的，而是會根據 $u_{n}$ 而有各自的比例。

## Weighted Logistic Regression

如果 Logistic Regression 改成在 $\mathcal{D}_{M}$ 中做 SGD ，跟上面一樣，各種資料 $\mathbf{x}_{n}$ 被抽到的機率會不一樣；所以使用 $E_{in}^{\mathbf{u}}(h)$ 的話：

$$
\left(E_{in}^{0/1}(h)=\frac{1}{M}\sum_{(\mathbf{x},y)\in\mathcal{D}_{M}}ln\left(1+e^{-y\mathbf{w}^{T}\mathbf{x}}\right)\right)
\equiv
\frac{1}{N}\sum_{n=1}^{N}u_{n} ln\left(1+e^{-y_{n}\mathbf{w}^{T}\mathbf{x}_{n}}\right)
$$

做 SGD 的時候，資料的採樣分佈要遵循 $u_{n}$ 的比率。

## Weighted Soft-margin SVM

$$
\frac{1}{2}\mathbf{w}^{T}\mathbf{w} + C\sum_{n=1}^{N}\color{green}{u_{n}}\xi_{n}+\color{red}{\sum_{n=1}^{N}\alpha_{n}(1-\xi_{n}-y_{n}(\mathbf{w}^{T}\mathbf{z}_{n}+b))}+\color{blue}{\sum_{n=1}^{N}\beta_{b}(-\xi_{n})}
$$

SVM 的話，推導的過程中 $\alpha_{n}$ 的範圍就會變成：

$$
0\le \alpha_{n}\le C u_{n}
$$

## BAGging & AdaBoost

從 BAGging 跟 AdaBoost 可以發現：

- BAGging 的隨機選取導致資料帶有權重，也因此該資料的重要性發生改變
- **實際上這就是把 Virtual Copy 變成了 Real Copy**
- AdaBoost 則是 Virtual Copy，每輪修改權重來更新資料的重要性

---

## Example-weighted learning

計算 $E_{in}$ 的時候為手上的「每種資料 $\mathbf{x}_{n}$」給予一個權重 $u_{n}$

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

>像上面都是 Example-weighted。

## class-weighted learning

$$
E_{in}^{\mathbf{u}}(h)=\frac{1}{N}\sum_{n=1}^{N}
\begin{Bmatrix}
a&y_{n}=1\\
b&y_{n}=-1
\end{Bmatrix}
err(y_{n},h(\mathbf{x}_{n}))
$$

[基石上第八周的內容](https://hackmd.io/Uq9IWK63TY2aaDruk-Sz6A?view#Weighted-Classification)。

做分類的話長的如上，或者依據不同情況跟類別而有不同的權重值。

跟 Example-weighted 不一樣，不是「每種資料 $\mathbf{x}_{n}$」給予一個權重 $u_{n}$。

>如果是分類問題，則 a 的情況是 false reject，b 的情況是 false accept。