Ensemble Methods: Bagging, Boosting (AdaBoost) & Random Forest（非考試範圍）

1. 咩係 Ensemble Methods（Slide 2–3）

呢章講兩類 ensemble techniques：Bagging 同 Boosting，之後再介紹 Random Forest 同 Gradient Boosting。Slide 3 嘅定義：

• Construct a set of classifiers from the training data
• Predict class label of test records by combining the predictions made by multiple classifiers

即係唔再靠一個 classifier 做決定，而係訓練好多個 base classifiers，再用投票嘅方式決定最終 class label。

2. 點解 Ensemble 有效（Slide 4–5）

Slide 4 嘅設定：

• 有 25 個 base classifiers，每個嘅 error rate 都係 $\varepsilon = 0.35$
• 用 majority vote 做 classification
• 假設各個 classifiers 犯嘅錯誤 uncorrelated

Ensemble 要錯，即係 25 個入面最少 13 個錯（過半數）。每個 classifier 錯唔錯可以當係一次 Bernoulli trial，所以「錯嘅數目」跟 Binomial distribution $B(25, 0.35)$：

由單一 classifier 嘅 0.35 跌到 ensemble 嘅 0.06，改善好明顯。

Slide 5 嘅圖顯示 25 個 base classifiers（errors uncorrelated）時，base classifier error（x 軸）同 ensemble classifier error（y 軸）嘅關係。紅色曲線係 ensemble，藍色虛線係 $y = x$（即係同單一 classifier 一樣）：

• $\varepsilon < 0.5$：紅線喺虛線下面，ensemble 比單一 classifier 好，例如 $\varepsilon = 0.35$ 時大約 0.06。
• $\varepsilon = 0.5$：兩條線相交，ensemble 冇幫助。
• $\varepsilon > 0.5$：紅線喺虛線上面，ensemble 反而更差，好快去到接近 1。

所以 Slide 5 列出 ensemble 比單一 base classifier 好嘅 necessary conditions：

1. All base classifiers are independent of each other
2. All base classifiers perform better than random guessing（binary classification 嘅 error rate $< 0.5$）

3. General Approach（Slide 6）

Slide 6 嘅流程圖分三步：

1. Step 1: Create Multiple Data Sets：由 original training data $D$ 產生 $D_1, D_2, \dots, D_{t-1}, D_t$
2. Step 2: Build Multiple Classifiers：每份 data set 訓練一個 classifier $C_1, \dots, C_t$
3. Step 3: Combine Classifiers：合併成 $C^*$，using majority vote or weighted majority vote（weighted according to their accuracy or relevance）

4. Ensemble Methods 嘅種類（Slide 7）

做法	例子	點樣令 base classifiers 唔同
Manipulate data distribution	Bagging、Boosting	每個 classifier 用唔同嘅 training sample（resampling）
Manipulate input features	Random forests	每個 classifier（或者每個 split）只用部分 attributes
Manipulate class labels	Error-correcting output coding (ECOC)	將 multi-class 問題拆成好多個 binary 問題，每個 classifier 學一種 class 分組

Slide 只列出 ECOC 嘅名，冇詳細講。概念上，ECOC 會為每個 class 編一個 binary code，每個 base classifier 負責預測其中一個 bit，最後揀同預測 code 最接近嘅 class。

5. Bagging（Slide 8–9）

Bagging（Bootstrap aggregating）：

• Bootstrap sampling：Sampling with replacement。每個 bootstrap sample 嘅 size 同原本 training set 一樣（$n$ 個 records），所以有啲 records 會重複出現，有啲就冇被抽中。
• Build classifier on each bootstrap sample。

每抽一次，某個 instance 冇被抽中嘅機會係 $1 - 1/n$。抽 $n$ 次都冇被抽中嘅機會係 $(1-1/n)^n$。所以：

例如 $n = 10$：$1 - 0.9^{10} = 1 - 0.3487 \approx 0.651$；$n$ 越大就越接近 0.632。即係每個 bootstrap sample 大約包含原本 63.2% 嘅 distinct records，其餘大約 36.8% 冇被抽中。

Bagging Algorithm（Slide 9），用文字描述：

1. 設 $k$ 為 bootstrap samples 嘅數目。
2. For $i = 1$ to $k$：由 $D$ 用 sampling with replacement 抽一個 size 為 $n$ 嘅 bootstrap sample $D_i$，再用 $D_i$ 訓練 base classifier $C_i$。
3. Test record $x$ 嘅 prediction：$C^*(x) = \arg\max_y \sum_i \delta(C_i(x) = y)$，即係 majority vote。（$\delta(\cdot)$ 條件成立時等於 1，否則等於 0）

6. Bagging Example（Slide 10–15）

1-dimensional data set（10 個 records）：

x	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0
y	1	1	1	−1	−1	−1	−1	1	1	1

Base classifier 係 decision stump（decision tree of size 1，即係得一個 split 嘅 tree）。Decision rule：$x \le k$ 就預測 $y_{left}$，$x > k$ 就預測 $y_{right}$。Split point $k$ 用 entropy 揀。

Slide 11–13 顯示 10 個 bagging rounds 嘅 bootstrap samples 同每個 stump。例如 Round 1 抽到 x = 0.1, 0.2, 0.2, 0.3, 0.4, 0.4, 0.5, 0.6, 0.9, 0.9，學到 $x \le 0.35 \Rightarrow y = 1$，$x > 0.35 \Rightarrow y = -1$。Round 2 抽到 0.1, 0.2, 0.3, 0.4, 0.5, 0.5, 0.9, 1.0, 1.0, 1.0，學到 $k = 0.7$，兩邊都預測 1。

Summary of training sets（Slide 14）：

Round	Split point $k$	Left class	Right class
1	0.35	1	−1
2	0.7	1	1
3	0.35	1	−1
4	0.3	1	−1
5	0.35	1	−1
6	0.75	−1	1
7	0.75	−1	1
8	0.75	−1	1
9	0.75	−1	1
10	0.05	1	1

Slide 15：假設 test set 同 original data 一樣，用 majority vote。將每個 round 嘅 prediction（+1 / −1）加埋，睇個 sum 嘅正負號（Sign）：

x	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9	1.0
Sum	2	2	2	−6	−6	−6	−6	2	2	2
Predicted (Sign)	1	1	1	−1	−1	−1	−1	1	1	1
True class	1	1	1	−1	−1	−1	−1	1	1	1

點計：x = 0.1 時，Round 1–5 同 10 都預測 1（+6），Round 6–9 預測 −1（−4），sum $= 6 - 4 = 2$。x = 0.4 時，只有 Round 2 同 10 預測 1（+2），其餘 8 個預測 −1，sum $= 2 - 8 = -6$。x = 0.8 時，Round 2、6–10 預測 1（+6），Round 1、3、4、5 預測 −1（−4），sum $= 2$。

結果 ensemble 嘅 accuracy 係 100%，但單一 stump 最多只有 70%。Bagging 合併咗「左邊切一刀」同「右邊切一刀」兩類 stumps，等於 decision boundary 有兩個切點。

7. Boosting（Slide 16–17）

Slide 16 嘅定義：

• An iterative procedure to adaptively change distribution of training data by focusing more on previously misclassified records
• Initially, all $N$ records are assigned equal weights（$1/N$）
• Unlike bagging, weights may change at the end of each boosting round

Slide 17：

• Records that are wrongly classified will have their weights increased
• Records that are classified correctly will have their weights decreased

Slide 17 嘅例子：Original data 係 record 1–10；Boosting Round 1 抽到 7, 3, 2, 8, 7, 9, 4, 10, 6, 3；Round 2 抽到 5, 4, 9, 4, 2, 5, 1, 7, 4, 2；Round 3 抽到 4, 4, 8, 10, 4, 5, 4, 6, 3, 4。Example 4 is hard to classify，佢嘅 weight 增加咗，所以之後嘅 rounds 越嚟越多機會抽中佢（Round 3 出現咗 4 次）。

8. AdaBoost 公式（Slide 18–20）

Base classifiers：$C_1, C_2, \dots, C_T$。

Error rate（weighted）：

即係將所有被 $C_i$ 分錯嘅 records 嘅 weights 加埋。$\delta(\cdot)$ 條件成立時等於 1，否則等於 0。

Importance of a classifier：

Slide 18 嘅圖係 $\ln((1-\varepsilon)/\varepsilon)$ 對 $\varepsilon$ 嘅曲線：

• $\varepsilon$ 接近 0 時，$\alpha$ 好大（準嘅 classifier 投票 weight 大）。
• $\varepsilon = 0.5$ 時，$\alpha = 0$（同亂估一樣，冇投票權）。
• $\varepsilon > 0.5$ 時，$\alpha < 0$。所以 AdaBoost 會避免呢種情況（見下面 weight update）。

Weight update（Slide 19）：

$Z_i$ 係 normalization factor，令新 weights 加埋等於 1。分啱嘅乘 $e^{-\alpha_i} < 1$（weight 減少），分錯嘅乘 $e^{\alpha_i} > 1$（weight 增加）。

如果中途任何一個 round 嘅 error rate 高過 50%，weights 會 reset 返 $1/n$，再重新做 resampling。

Classification（Slide 19）：

即係 weighted majority vote：每個 classifier 嘅一票，價值等於佢嘅 $\alpha_i$。對 $y \in \{-1, 1\}$，等同計 $\sum_i \alpha_i C_i(x)$ 嘅正負號。

9. AdaBoost Example（Slide 21–23）

用返同 bagging example 一樣嘅 1-D data 同 decision stump。Slide 22 顯示頭 3 個 boosting rounds 嘅 training sets：

• Round 1：0.1, 0.4, 0.5, 0.6, 0.6, 0.7, 0.7, 0.7, 0.8, 1.0（uniform weights 抽樣）
• Round 2：0.1, 0.1, 0.2, 0.2, 0.2, 0.2, 0.3, 0.3, 0.3, 0.3（集中喺 Round 1 分錯嘅 0.1–0.3）
• Round 3：0.2, 0.2, 0.4, 0.4, 0.4, 0.4, 0.5, 0.6, 0.6, 0.7（集中喺 Round 2 分錯嘅 0.4–0.7）

Summary（Slide 22）：

Round	Split point	Left class	Right class	$\alpha$
1	0.75	−1	1	1.738
2	0.05	1	1	2.7784
3	0.3	1	−1	4.1195

Weights（Slide 23）：

Round	x = 0.1–0.3	x = 0.4–0.7	x = 0.8–1.0
1	0.1	0.1	0.1
2	0.311	0.01	0.01
3	0.029	0.228	0.009

逐步解釋：

1. Round 1：stump $x \le 0.75 \Rightarrow -1$，否則 1。喺 original data 上分錯 x = 0.1, 0.2, 0.3（真 class 係 1）。所以呢三個嘅 weight 由 0.1 升到 0.311，其餘 7 個跌到 0.01（$3 \times 0.311 + 7 \times 0.01 \approx 1$）。
2. Round 2：sample 幾乎全部係 0.1–0.3（class 1），學到「全部都係 1」（split 0.05，兩邊都係 1）。分錯 x = 0.4–0.7，所以佢哋嘅 weight 升到 0.228。
3. Round 3：sample 集中喺 0.4–0.7，學到 $x \le 0.3 \Rightarrow 1$，否則 −1，分錯 x = 0.8–1.0。

Classification（Slide 23）：計 $\sum_i \alpha_i C_i(x)$：

x	Round 1 ($\alpha=1.738$)	Round 2 ($\alpha=2.778$)	Round 3 ($\alpha=4.120$)	Sum	Sign	True
0.1–0.3	−1	1	1	$-1.738 + 2.778 + 4.120 = 5.16$	1	1
0.4–0.7	−1	1	−1	$-1.738 + 2.778 - 4.120 \approx -3.08$	−1	−1
0.8–1.0	1	1	−1	$1.738 + 2.778 - 4.120 \approx 0.40$	1	1

（Slide 嘅 Sum 係 5.16、−3.08、0.397。）只用 3 個 stumps，AdaBoost 已經做到 100% accuracy。留意 Round 3 嘅 $\alpha$ 最大，但佢喺 x = 0.8–1.0 投錯票，仍然被 Round 1 同 2 加埋嘅票蓋過，所以結果正確。

# 參考用 scikit-learn 示範（唔係 lecture code）
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import BaggingClassifier, AdaBoostClassifier

X = np.arange(1, 11).reshape(-1, 1) / 10
y = np.array([1, 1, 1, -1, -1, -1, -1, 1, 1, 1])
stump = DecisionTreeClassifier(max_depth=1)   # decision stump

print(stump.fit(X, y).score(X, y))            # 單一 stump：0.7
bag = BaggingClassifier(stump, n_estimators=10, random_state=1).fit(X, y)
ada = AdaBoostClassifier(stump, n_estimators=3).fit(X, y)
print(bag.score(X, y), ada.score(X, y))       # 通常可以去到 1.0（bagging 視乎 random_state）

10. Random Forest（Slide 24–25）

Construct an ensemble of decision trees by manipulating training set as well as features：

• Use bootstrap sample to train every decision tree（similar to Bagging）
• Tree induction：At every internal node, randomly sample $p$ attributes for selecting split criterion
• Repeat until all leaves are pure（unpruned tree）

Characteristics（Slide 25）：

• Base classifiers are unpruned trees and hence are unstable classifiers（low bias、high variance）
• Base classifiers are decorrelated（due to randomization in training set as well as features）
• Random forests reduce variance without negatively impacting the bias
• Selection of hyper-parameter $p$：
  • Small values ensure lack of correlation（trees 之間更唔同）
  • High value promotes strong base classifiers（每棵 tree 更準）
  • Common default choices：$\sqrt{d}$、$\log_2(d+1)$（$d$ 係 attributes 嘅總數）

11. Gradient Boosting（Slide 26）

• Constructs a series of models（sequential，同 boosting 一樣）
• Models can be any predictive model that has a differentiable loss function；commonly, trees are the chosen model
• XGBoost（extreme gradient boosting）is a popular package because of its impressive performance
• Boosting can be viewed as optimizing the loss function by iterative functional gradient descent
• Implementations are available in Python, R, Matlab, and more

# 參考用（唔係 lecture code）
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
rf  = RandomForestClassifier(n_estimators=100, max_features="sqrt")  # p = sqrt(d)
gbm = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, max_depth=3)
# XGBoost：pip install xgboost；from xgboost import XGBClassifier

自我測驗 Self-test

Q1. Ensemble method 嘅定義係咩？Ensemble 要比單一 base classifier 好，需要咩 necessary conditions？

由 training data 建立一組 classifiers，再合併佢哋嘅 predictions 嚟預測 test records 嘅 class label。條件：(1) base classifiers 之間互相 independent；(2) 每個 base classifier 都比 random guessing 好（binary classification 嘅 error rate $< 0.5$）。

Q2. 有 5 個 independent base classifiers，每個 $\varepsilon = 0.2$，用 majority vote。Ensemble 嘅 error rate 係幾多？

最少 3 個錯先會錯：$\binom{5}{3}(0.2)^3(0.8)^2 + \binom{5}{4}(0.2)^4(0.8) + (0.2)^5 = 0.0512 + 0.0064 + 0.00032 \approx 0.058$，比 0.2 細好多。

Q3. 如果每個 base classifier 嘅 $\varepsilon = 0.6$，用 ensemble 會點？

Ensemble error 會比 0.6 更高（Slide 5 曲線喺 $\varepsilon > 0.5$ 時喺 $y = x$ 上面），因為大多數 classifiers 都會錯，majority vote 會放大錯誤。

Q4. Training set 有 $n = 5$ 個 records。某個 record 喺一個 bootstrap sample 入面出現最少一次嘅機會係幾多？$n$ 好大時呢？

$1 - (1 - 1/5)^5 = 1 - 0.8^5 = 1 - 0.32768 \approx 0.672$。$n$ 好大時趨向 $1 - 1/e \approx 0.632$。

Q5. Ensemble methods 分邊三類？每類舉一個例子。

Manipulate data distribution（bagging、boosting）；manipulate input features（random forests）；manipulate class labels（error-correcting output coding）。

Q6. Bagging 同 boosting 有咩主要分別？

Bagging：每個 bootstrap sample 都係 uniform 抽樣，classifiers 互相獨立（可以 parallel），用 majority vote，主要減 variance。Boosting：iterative，每個 round 按 weights 抽樣，分錯嘅 records weight 增加，classifiers 有先後次序，用 weighted vote（$\alpha_i$），較易受 noise / outliers 影響。

Q7. 某個 AdaBoost round 嘅 $\varepsilon_i = 0.1$。計 $\alpha_i$。分啱同分錯嘅 records 嘅 weight（normalize 之前）會乘咩數？

$\alpha_i = \frac{1}{2}\ln(0.9/0.1) = \frac{1}{2}\ln 9 \approx 1.099$。分啱乘 $e^{-1.099} \approx 0.333$，分錯乘 $e^{1.099} \approx 3$，之後再除以 $Z_i$，令 weights 加埋等於 1。

Q8. 點解 AdaBoost 要求每個 round 嘅 $\varepsilon_i \le 0.5$？超過咗會點做？

$\varepsilon_i = 0.5$ 時 $\alpha_i = 0$，$\varepsilon_i > 0.5$ 時 $\alpha_i < 0$，即係 classifier 比亂估仲差，亦違反 ensemble 嘅 necessary condition。Slide 19：如果 error rate 高過 50%，weights 會 reset 返 $1/n$，再重新 resampling。

Q9. 喺 AdaBoost example 入面，3 個 stumps 嘅 $\alpha$ 係 1.738、2.778、4.120。x = 0.8 時三個 stumps 分別預測 1、1、−1。Ensemble 預測咩？

$1.738 + 2.778 - 4.120 = 0.396 > 0$，所以預測 1（正確）。雖然 $\alpha$ 最大嘅 Round 3 投 −1，但另外兩個加埋嘅 weight 更大。

Q10. Random forest 同 bagging 有咩分別？Hyper-parameter $p$ 大細有咩 trade-off？

兩者都用 bootstrap samples，但 random forest 喺每個 internal node 只隨機揀 $p$ 個 attributes 嚟揀 split，而且 tree 唔做 pruning，所以 trees 更 decorrelated。$p$ 細：trees 之間 correlation 低，但每棵 tree 較弱；$p$ 大：每棵 tree 較強，但 trees 較相似（$p = d$ 就變返 bagging）。常用 $\sqrt{d}$ 或 $\log_2(d+1)$。

一頁總結 Cheat sheet