Ensemble Learning: Cheat Sheet

The whole topic compressed for the night before the exam.

Ensembles

≡FactsWhy a committee beats a member

• Combine weak learners (accuracy slightly above 50%) into a strong learner.
• It only works if the learners' errors are independent.
• Averaging $n$ independent observations gives $\operatorname{Var}(\bar{Z}) = \sigma^2 / n$.

Bagging

#NumbersBagging in one card

• Sample with replacement; the learners are parallel and independent.
• About 63% in-bag, about 37% out-of-bag, because $(1 - 1/n)^n \to 1/e \approx 0.368$.
• OOB error is close to leave-one-out cross-validation, with no separate validation set.
• Roughly 100 learners are usually enough.

Boosting

≡FactsBoosting in one card

• Sequential: each learner focuses on the previous learner's errors by up-weighting the misclassified points.
• The weak learner is typically a decision stump.
• Bagging reduces variance; boosting reduces bias, and can overfit.

AdaBoost

$$\varepsilon_m = \sum_n w_n \cdot I(\text{wrong}) \qquad \alpha_m = \frac{1}{2}\ln\!\left(\frac{1-\varepsilon}{\varepsilon}\right)$$ $$w_{i+1} = w_i \cdot e^{-\alpha \cdot \text{actual} \cdot \text{pred}} \quad (\text{then normalize}) \qquad H(x) = \operatorname{sign}\!\left(\sum_m \alpha_m h_m(x)\right)$$

#NumbersThe three anchor values for α

• $\varepsilon = 0 \Rightarrow \alpha = +\infty$.
• $\varepsilon = 0.5 \Rightarrow \alpha = 0$.
• $\varepsilon = 1 \Rightarrow \alpha = -\infty$.
• Worked: $\varepsilon = 0.3 \Rightarrow \alpha = \tfrac{1}{2}\ln(2.333) = 0.42$.

◎Exam cueThe three-way sort

Manipulate the data distribution means bagging or boosting; manipulate the input features means random forests; manipulate the class labels means error-correcting output coding.