Ensemble Methods

1. Idea

An ensemble combines the predictions of several base classifiers to obtain a classifier that is usually more accurate than any single member. Necessary condition: the base models must be accurate (better than random) and diverse (make errors on different tuples).

                  Training data
                        |
        +---------------+---------------+
        |               |               |
     Model 1         Model 2   ...   Model k     (different samples / features / algorithms)
        |               |               |
      pred y1         pred y2         pred yk
        +---------------+---------------+
                        v
              COMBINATION RULE
       classification -> majority vote / weighted vote
       numeric        -> average / weighted average
                        v
                    final prediction

Error reduction intuition for $k$ independent classifiers each with error $p$ , combined by majority vote:

P(\text{majority wrong})=\sum_{i=\lfloor k/2\rfloor+1}^{k}\binom{k}{i}p^{i}(1-p)^{k-i}

For $p=0.35$ and $k=25$ , this probability drops to about $0.06$ — but only if the errors are independent, which is why diversity matters.

2. Bagging (Bootstrap Aggregating, Breiman)

Generate $k$ bootstrap samples of the training set (sample $n$ tuples with replacement).
Train one base classifier per sample, using the same algorithm.
Combine: majority vote for classification, average for numeric prediction.

\hat y = \arg\max_{c}\ \sum_{i=1}^{k}\mathbb{1}\,[h_i(x)=c],\qquad \hat y = \frac{1}{k}\sum_{i=1}^{k}h_i(x) \ \text{(numeric)}

Properties: reduces variance (helps unstable, high-variance learners such as decision trees, neural nets); does not help much for stable learners (naive Bayes, k-NN); base models can be trained in parallel; out-of-bag tuples give a free validation estimate (basis of random forests).

3. Boosting (AdaBoost — Adaptive Boosting)

Each training tuple gets a weight, initially all equal to $1/n$ .
For round $i = 1 \dots T$ : train a base classifier $C_i$ on the weighted data.
Compute the weighted error $\varepsilon_i$ of $C_i$ ; if $\varepsilon_i > 0.5$ restart (or abort); if $\varepsilon_i = 0$ use a very small value.
Give the classifier a say (weight) in the vote:

\alpha_i=\frac{1}{2}\ln\frac{1-\varepsilon_i}{\varepsilon_i}

Update the tuple weights — increase for misclassified tuples, decrease for correct ones (normalise):

w^{(i+1)}=\frac{w^{(i)}}{Z_i}\times\begin{cases}e^{-\alpha_i} & \text{if correctly classified}\\ e^{+\alpha_i} & \text{if misclassified}\end{cases}

Final classifier = weighted vote of all $T$ classifiers:

C^*(x)=\arg\max_{c}\ \sum_{i=1}^{T}\alpha_i\,\mathbb{1}\,[C_i(x)=c]

Properties: reduces bias as well as variance; can boost a weak learner (decision stump) into a strong one; sensitive to noisy data and outliers (their weights escalate) and requires the base learner to accept weights; sequential — not parallelisable; overfitting is often surprisingly slow but possible with too many rounds.

4. Random Forests (Bagging + random attribute selection)

Build $k$ decision trees on bootstrap samples; at each node split on the best attribute among a random subset of $m$ attributes (typical $m=\sqrt{d}$ for classification, $d/3$ for regression).
Predict by majority vote (or average); report out-of-bag error, variable importance (permutation or Gini decrease) and proximity matrices.
Extremely popular for tabular data; robust, hard to overfit; slower and less interpretable than a single tree.

5. Other Ensemble Strategies

Method	How diversity is created	Combining rule
Bagging	Bootstrap resampling of tuples	Majority vote / average
Boosting (AdaBoost, Gradient Boosting, XGBoost, LightGBM)	Reweighting misclassified tuples / fitting residuals of previous models	Weighted vote / additive sum
Random forest	Bootstrap + random attribute subsets	Majority vote
Stacking (stacked generalisation)	Different algorithms (heterogeneous base models)	A meta-learner trained on base predictions (e.g. logistic regression)
Voting ensemble	Different algorithms trained on the same data	Hard voting (majority) or soft voting (average of probabilities)
Bayesian model averaging	Posterior probability of each model	Weighted by posterior model probability
Mixture of experts	Input region gating network	Gate-weighted combination

\text{Stacking: } \hat y = g\big(h_1(x), h_2(x), \dots, h_k(x)\big) \text{ where } g \text{ is learned on out-of-fold predictions}

6. Why Ensembles Work — Bias–Variance

\mathbb{E}[(y-\hat y)^2]=\text{Bias}^2+\text{Variance}+\sigma^{2}

Averaging $k$ models with pairwise correlation $\rho$ and variance $\sigma^2$ :

\text{Var}\Big(\frac{1}{k}\sum_i h_i\Big)=\rho\sigma^{2}+\frac{1-\rho}{k}\sigma^{2}

As $k$ grows only the second term vanishes — hence the need to decorrelate members (bagging + feature randomness in random forests achieves exactly this).

7. Advantages and Limitations

Advantages

Usually the highest accuracy among practical methods; robust to noise and to the choice of a single algorithm.
Bagging/random forests give out-of-bag error estimates and variable importance for free.
Parallel training for bagging/forests; boosting extracts maximum accuracy from weak learners; ensembles can combine heterogeneous evidence (different features/views).

Limitations

Loss of interpretability — many models are hard to explain; though variable importance and rule extraction mitigate this.
Higher computational cost (time/memory) for training and prediction; large model size.
Boosting is sensitive to label noise and outliers and is sequential; bagging does not reduce bias for stable learners.
Diminishing/negative returns without diversity — correlated members add cost, not accuracy.

8. Exam Points

Define ensemble methods and explain bagging with the algorithm and a diagram — 10 marks (frequent).
Explain AdaBoost in full detail: weights, $\varepsilon_i$ , $\alpha_i$ , the weight update and the final vote — 10 marks (very frequent).
Explain random forests and how they differ from bagging — 5 marks.
Why do ensembles improve accuracy? Bias-variance discussion — 5 marks.
Advantages and limitations of ensemble methods — 5 marks.

Ensemble Methods