# Aggregation

把很多 $g_{t}$ 混和在一起，可以達到：

- 使邊界複雜化，類似 Feature Transform 的效果
- 使模型更 Powerful
- 選取中庸的結果，類似 Regularization
- 例如 SVM 選取了 Large margin，不像 PLA 是隨便挑一個

# Uniform Blending (Voting) for Classification

$$
G(\mathbf{x})=sign\left(\sum_{t=1}^{T}1\cdot g_{t}(\mathbf{x})\right)
$$

多人投票，看哪種票最多。

## Multiclass

$$
G(\mathbf{x})=arg\max_{1\le k\le K}\sum_{t=1}^{T}[[g_{t}(\mathbf{x})=k]]
$$

跟之前的 [OVA](https://hackmd.io/@ShawnNTU-CS/HJLqw44hh#One-Versus-All-OVA-Decomposition) 很像，OVA 是每種類別一個 $g_{t}$，然後看誰勝利；而這裡則是把 OVA 那群 $g_{t}$ 再看做是一個 $g_{t}$，這些 $g_{t}$ 做決定。

# Uniform Blending for Regression

$$
G(\mathbf{x})=\frac{1}{T}\sum_{t=1}^{T}g_{t}(\mathbf{x})
$$

# diverse hypotheses

前面兩個 Uniform Blending for Classification 和 Regression，前提是 $g_{t}$ 要**多樣化 diversity**，這樣平均起來才有效果；都一樣的話那就跟單一一個效果是一樣的。

## Theoretical Analysis

對於 Regression，我們可以透過證明得到對於單一一個點 $\mathbf{x}$：

$$
avg\left(\left(g_{t}(\mathbf{x})-f(\mathbf{x})\right)^{2}\right)=avg\left(\left(g_{t}(\mathbf{x})-G(\mathbf{x})\right)^{2}\right)+\left(G(\mathbf{x})-f(\mathbf{x})\right)^{2}
$$

$avg$ 是 $\frac{1}{T}\sum$ 的另一個寫法。

如果不只對單一個點而是對全部點的話，也就是在上面兩邊都取期望值：

$$
avg\left(E_{out}(g_{t})\right)=avg\left(\mathcal{E}\left(g_{t}(\mathbf{x})-G(\mathbf{x})\right)^{2}\right)+E_{out}(G)\ge E_{out}(G)
$$

> $\mathcal{E}\left[err(y_{n},g_{t}(\mathbf{x}))\right]=E_{out}(g_{t})$

所以可以知道 $E_{out}(g_{t})$ 平均來說會比 $E_{out}(G)$ 來的大一些。

## bias 和 variance

如果 T 趨近無限大，我們將這個特殊的 $G$ 給個代號 $\bar{g}$，代表 $g_{t}$ 的「共識 consensus」：

$$
\bar{g}=\lim_{T\rightarrow \infty}G=\lim_{T\rightarrow \infty}\frac{1}{T}\sum_{t=1}^{T}g_{t}(\mathbf{x})=\underset{\mathcal{D}}{\mathcal{E}}\mathcal{A}(\mathcal{D})
$$

會得到：

$$
avg\left(E_{out}(g_{t})\right)=avg\left(\mathcal{E}\left(g_{t}(\mathbf{x})-\bar{g}(\mathbf{x})\right)^{2}\right)+E_{out}(\bar{g})
$$

而在 Regression 中

- $avg\left(\mathcal{E}\left(g_{t}(\mathbf{x})-\bar{g}(\mathbf{x})\right)^{2}\right)$ 這個部分叫做「對共識的期望偏差 expected deviation to consensus」
- 又叫做「variance」
- 畢竟變異數就是 $E[(X-\mu)^{2}]$
- $E_{out}(\bar{g})$ 這個部分是「共識的表現 performance of consensus」
- 又叫做「bias」

variance 和 bias 組合起來就是 $\mathcal{A}$ 的期望表現 expected performance。

:::warning
所以可以發現，如果沒有用 Blending，那麼原本的 $E_{out}(g_{t})$ 平均來說就會跟由大家組合起來，並且比較好的 $E_{out}(\bar{g})$ 差一個變異數的平均值；所以只要使用 Blending 得到的 $E_{out}(\bar{g})$ 就可以擺脫掉這個變異數。
:::

---

# Linear Blending (non-Uniform Blending)

前面 Uniform 的是一人一票，票票等值，這裡換考慮票票不等值的情況：

$$
G(\mathbf{x})=sign\left(\sum_{t=1}^{T}\alpha_{t}\cdot g_{t}(\mathbf{x})\right)with\ \alpha_{t} \ge 0
$$

希望得到：

$$
\min_{\alpha_{t}\ge 0}E_{in}(\boldsymbol{\alpha})
$$

## linear blending for regression

$$
\min_{\alpha_{t}\ge 0}E_{in}(\boldsymbol{\alpha})=\min_{\alpha_{t}\ge 0}\frac{1}{N}\sum_{n=1}^{N}\left(y_{n}-\sum_{t=1}^{T}\alpha_{t}\cdot g_{t}(\mathbf{x}_{n})\right)^{2}
$$

也就是說我參考了很多 $g_{t}$，對一個點進行預測後看看跟原本的值平方差多少，然後要找最小平方的 $\boldsymbol{\alpha}$。

這個方法跟之前拿 SVM 近似 LogReg 的 Two Level Learning 很像，都是將原本的 $\mathbf{x}$ 以學到的內容轉換成「新資料」，然後再用「新資料」去學新的變數。

所以 linear blending 就是將 Linear Model 搭配以 hypotheses as transform 的新資料，再加上一些 constraints。

$\alpha_{t}\ge 0$ 是因為我們相信學到的 $g_{t}$ 都是對的方向。

但其實還是有可能有學錯的時候，所以實務上不需要加上 $\alpha_{t}\ge 0$，小於 0 的時候代表要跟該 $g_{t}$ 唱反調。

## 搭配 Validation

讓 $E_{in}$ 最小這件事之前就有提到他的風險，所以最好是用 Validation。

也就是改成：

$$
\min_{\alpha_{t}\ge 0}E_{val}(\boldsymbol{\alpha})
$$

而 $g_{t}^{-}$ 是從 $E_{train}$ 中挑最小的出來。

最後學到最好的 $\boldsymbol{\alpha}$ 後，再將 $g_{t}^{-}$ 訓練出 $g_{t}$ 就大功告成；看是用來做 Regression，那麼 $\boldsymbol{\alpha}$ 跟經過 $g_{t}$ 轉換的新資料內積的值就好；如果是 Classification 那就再取個 sign。

# Stacking / Any Blending (conditional Blending)

Linear Blending 是採用了 Linear Regression 或是其他 Linear Model 來進行錯誤評估後，找到最佳的 $\boldsymbol{\alpha}$，當然我們也可以用非線性的 model 來進行評估，這樣的就叫做 Any Blending，或也叫做 Stacking。

但是要注意，老樣子，更有 Power 的就更要注意 overfitting 的發生。

---

# Bootstrap Aggregation / BAGging

要有多樣性才可以達到 Aggregation 的目的，多樣性可以來自於：

- different models
- different parameters
- 像是 SVM 中的 $C$、kernel 的 $\gamma$ 和 GD 中的 $\eta$
- algorithmic randomness
- 像 PLA 會隨機給你符合條件的線
- data randomness
- 像 within-cross-validation 可以產生很多 $g^{-}$

## bootstrapping

在討論 Uniform Blending 時的這個式子中：

$$
\bar{g}=\lim_{T\rightarrow \infty}G=\lim_{T\rightarrow \infty}\frac{1}{T}\sum_{t=1}^{T}g_{t}(\mathbf{x})=\underset{\mathcal{D}}{\mathcal{E}}\mathcal{A}(\mathcal{D})
$$

想要產生出 $\bar{g}$ 就必須讓 $T\rightarrow \infty$，並且每個 $g_{t}$ 都要來自不同的資料，但我們只能做到近似的結果，因為只能讓 T 夠大而已。

而不同的資料 $\mathcal{D}_{t}$，也不是每次都有，所以我們希望從 $\mathcal{D}$ 中以相同分佈重新取樣來模擬 $\mathcal{D}_{t}$，這個方法是一個統計的工具叫 bootstrapping。

方法就是每次從原本的 $\mathcal{D}$ 中「平均抽樣取後放回」直到抽到需要的數量；這樣就可以產生很多 $g_{t}$ 然後再去進行接下來的 Uniform 的動作。

## Meta Algorithm

接下來的 Uniform 可以是 Regression 或 Classification 等等，像這樣建立在其他演算法之上的演算法叫做 meta algorithm，在他底下的叫做 Base Algorithm

## Algorithm sensitivity

如果演算法對於資料的隨機性很敏感，例如 PLA，那麼在這樣平均的隨機重新取樣所得到的資料，Bagging 的效果會很好，因為不同的資料就容易有不同的 $g_{t}$。

:::warning
對隨機性很敏感可以參考之後的：
- [第十週 Random Forest](https://hackmd.io/@ShawnNTU-CS/rkSqrG7an)
- [第十二週 Neural Network](https://hackmd.io/@ShawnNTU-CS/BJuSNKEp2)
- [不同的隨機權重初始值，可能會使結果到達不同的局部最佳解](https://hackmd.io/@ShawnNTU-CS/BJuSNKEp2#Neural-Network-Optimization)
- [第十四週 Radial Basis Function Network](https://hackmd.io/@ShawnNTU-CS/S1hTRhOa2)
- [當中的 K-means 演算法](https://hackmd.io/@ShawnNTU-CS/S1hTRhOa2#k-Means--Alternating-Optimization)
:::

:::info
或許無法達到全局最佳的都可以考慮使用 Aggregation
:::