# Random Forest = Bagging + Decision Tree
- BAGging 是藉著多個 $g_{t}$ 團結在一起減少消除[單個 $g_{t}$ 會有的 Variance](https://hackmd.io/@ShawnNTU-CS/BywPOgyan#bias-%E5%92%8C-variance)，所以 Variance 低。
- Decision Tree 只要得到的 $\mathcal{D}$ 有一些些的不同，下刀的地方就會不一樣，所以 Variance 很大
- $Variance=E[(X-\mu)^{2}]$
- 資料越小就更容易發生，尤其是 Fully-grown Tree。

所以我們就用 Bagging 的方式，把一堆 fully-grown C&RT Decision Tree 結合起來消除 Variance，也就降低了 overfitting 發生。

由於 Bagging 的特性，所以容易平行化；並且決策樹又很有效率，所以就是效率再效率。

:::warning
對隨機性很敏感可以回顧 [第七週 Blending and Bagging](https://hackmd.io/@ShawnNTU-CS/BywPOgyan)
:::

# Random Subspace

Bagging 的特色是在 Data 上 randomness。

另一種製造 randomness 的方式是在 feature 上；也就是不需要每個維度都用，只挑某幾個維度。

$$
\mathcal{Z} \in \mathbb{R}^{d^{'}}\\
\mathcal{X} \in \mathbb{R}^{d}
$$

是一種新的**特徵轉換**，可知 $\mathcal{Z} \in \mathcal{X}$；通常 $d^{'} \ll d$，可以讓 stump 容易切許多。

Random Subspace 也可以用在其他演算法，例如 SVM。

## re-sample when Branching

除了轉換一次後就用那些維度到底，RF 的作者建議可以改在 Branching 的時候就轉換一次維度。

例如總共 100 個維度，第一次可能挑第 1, 3, 5, 7, 9 維度，第二次可能挑第 2, 4, 6, 8, 10 維度。

# 原本的投影 & 更強的投影

原本的 Subspace 特徵轉換可以看做是一個投影的動作：

$$
\phi(\mathbf{x})=\mathbf{P}\cdot \mathbf{x}\\
\mathbf{P}=
\begin{bmatrix}
1 & 0 & \dots & 0\\
0 & 1 & \dots & 0\\
\vdots & \vdots & \ddots & 0\\
0 & 0 & \dots & 1
\end{bmatrix}
$$

可以知道 $\mathbf{P}$ 的每 row 都是各個維度的單位方向 **Natural Basis**。

上面的 $\mathbf{P}$ 是全部的維度都選，所以是個 $d\times d$ 矩陣，如果要投影到 Subspace，就會變成 $d^{'}\times d$ 矩陣，看你想保留幾個維度。

## 更強的投影 combination

每個 row 不一定要是 natural basis，可以換成某幾個維度的線性組合，也就是說讓 row 可能長的像：

$$
\mathbf{p}_{row}=[0,0,c_{1},c_{2},0,...,,c_{j},0]
$$

可知原本的投影是現在的 special case，也就是每個 row 只含有一個值為 1。

## Perceptron-like

所以每次分枝的時候，先將原本的維度，投影到某幾個自己合成的維度，然後從中挑選一個做 stump。

這樣其實就是之前的 perceptron，而 stump 在決定最終的常數值落在哪裡。

:::warning
RF = bagging + radom-combination C&RT，到處充滿了隨機。
:::

:::success
像這樣轉換到比較小的維度可以對照之後 [深度學習](https://hackmd.io/@ShawnNTU-CS/HkIxZtv6h) 提到的 [線性編碼機和PCA](https://hackmd.io/@ShawnNTU-CS/HkIxZtv6h#Principal-Component-Analysis--PCA)。
一個是用來製造隨機性，一個是用來挑選最好的表現方式。
:::

---

# out-of-bag / OOB

Bagging 時沒有被選到的資料叫做 out-of-bag examples；OOB 資料就很像 Valid 沒有被選到的資料，所以一樣可以拿來驗證。

但是我們其實沒有必要驗證 $g_{t}$，因為最後會把他們合成 $G$，我們想驗證的是 $G$。

## $E_{oob}$

所以可以去紀錄 $\mathbf{x}_{n}$ 在哪些 $g_{t}$ 沒有被用到，由這些 $g_{t}$ 組成的 $G^{-}_{n}$ 來對 $\mathbf{x}_{n}$ 預測。

最終把全部可以製造的 $G^{-}_{n}$ 預測的錯誤進行平均，所得到的錯誤平均就是 $E_{oob}$。

$$
\frac{1}{N}\sum_{n=1}^{N}err(y_{n},G^{-}_{n}(\mathbf{x}_{n}))
$$

很像之前的 $E_{loocv}$，都一樣是對「單筆」資料預測後取平均值。

:::warning
$E_{oob}$ 在 RF 實務上通常可以很準確的衡量 $G$ 的表現。
:::

## self-validation

像這樣不需要格外獨立 valid 資料區的特性就叫做 self-validation；並因此少了將 $g^{-}$ 訓練回 $g$ 的動作，更有效率。

---

# Feature Selection

降維打擊，除去冗餘的 redundant，或不相關的 irrelevant 維度。

可以依照特徵的重要性由大到小排列出來，選前面幾大留下來。

- 好處
- 較少的維度讓訓練更有效率
- 如果選到好的維度，代表可以移除掉 noise，因此增加 generalization 減少 overfitting
- 更有助於解釋。
- 壞處
- 要計算怎麼做才是好的選擇，找到之前的計算量可能已經很大，反而更沒效率
- 有可能不小心選到剛好 overfit 的維度組合。
- 因此導致了錯誤的解釋。有可能只有有關係，但其實沒有因果關係。

C&RT 決策樹和 AdaBoost-Stump 因為用了 Stump 所以算是內建的 Feature Selection。

:::success
像這樣轉換到比較小的維度可以對照之後 [深度學習](https://hackmd.io/@ShawnNTU-CS/HkIxZtv6h) 提到的 [線性編碼機和PCA](https://hackmd.io/@ShawnNTU-CS/HkIxZtv6h#Principal-Component-Analysis--PCA)。
:::

# 特徵重要性

可以以各維度的權重的大小做為其重要性。

- 所以如果是一個線性模型可以很容易算出特徵重要性。
- 但是非線性模型就不容易算出出重要性

不過 RF 雖然是非線性模型，但是 Permutation test 可以簡單地評估出特徵重要性。

# Permutation test

- 如果一個維度很重要，那麼將該維度加上雜訊，表現會下降。
- 要注意加上雜訊不能用直接修改值的方式，因為會影響原本值的分布。
- 可以透過把值洗牌的方式來達到雜訊的效果，同時不失去原本資料的分佈
- 假設要洗牌第 n 個維度
- 那麼可能 $x_{1126,n}$ 變成 $x_{6211,n}$，$x_{2611,n}$ 變成 $x_{1126,n}$ ...。

## Importance 函數

對於非線性模型可以透過表現函數算出重要性：

$$
importance(i)=performance(\mathcal{D})-performance(\mathcal{D}^{(p)})
$$

$\mathcal{D}^{(p)}$ 就是經過 Permutation test 洗牌的資料。

普遍來說任何非線性模型表現函數可以使用 $E_{val}$ 來比較洗牌前後的差異，錯誤率變越高通常代表該維度越重要。

## 近似

由於 RF 有 OOB，所以相比其他需要 Validation 的非線性模型方便許多。

但是如果嫌訓練兩次很麻煩，可以用近似的方法，改成對原本 $\mathcal{D}$ 做 OOB 驗證時，同時對 $\mathbf{x}_{n}$ 洗牌的動作。

OOB 是一個 $\mathbf{x}_{n}$ 會有相對應的 $G^{-}_{n}$，所以只能對那些 $\mathbf{x}_{n}$ 進行洗牌。

- 所以不是對全部資料都洗牌，因為可能有資料沒有相對應的 $G^{-}_{n}$
- 由於是對 Valid 的動作進行洗牌，這樣就不用重新訓練。

---

# 特色

可以做出平滑且類似 large margin 的結果；並且 Bagging 的投票機制可以消除 noise。
>或者說消除掉 Variance

# 樹大便是美

幾乎全部的理論都會告訴你，越多棵樹越好，因為這樣會[逼近我們所要的 $\bar{g}$](https://hackmd.io/QKHftqsISyO7gz-nsDVLUQ?view#bias-%E5%92%8C-variance)：

$$
\bar{g}=\lim_{T\rightarrow \infty}G
$$

## 要幾顆樹

由於 RF 會受隨機過程影響而不穩定，所以直到 $G$ 的結果受 random seed 的影響很小的時候就可以了。
>也就是說我們消除了大部分的 Variance