Boosting — Concept and Why It Improves Decision Tree Accuracy

What is Boosting?

Boosting is an ensemble method that combines several weak learners (classifiers only slightly better than random guessing) into a single strong classifier by training them sequentially, gradually focusing more weight on the tuples that earlier learners misclassified.

Main (AdaBoost-style) idea:

1. Assign an equal initial weight to every training tuple.
2. Train a weak learner (typically a single-level decision tree / decision stump) on the weighted data.
3. Increase the weights of misclassified tuples and decrease the weights of correctly classified ones, so the next learner concentrates on the "hard" cases.
4. Repeat for $T$ rounds; each new learner specialises in the mistakes of its predecessors.
5. Combine all $T$ models by weighted voting, where each classifier's vote is weighted by its accuracy:

$$\text{final}_{}(x) = \operatorname{sign}\left(\sum_{t=1}^{T} \alpha_t \, h_t(x)\right), \qquad \alpha_t = \frac12 \ln\frac{1-\varepsilon_t}{\varepsilon_t}$$

   weighted data ──▶ T1 ──▶ raise weights of errors ──▶ T2 ──▶ ... ──▶ weighted vote
                    (weak)                                          (strong ensemble)

Why boosting may improve the accuracy of decision tree induction

• Focuses on hard instances. Instead of a single tree that may miss complex regions, boosting builds many simple trees, each paying special attention to tuples the earlier trees got wrong — so subtle patterns that no single stump could capture are learned by the committee.
• Reduces variance and bias. Decision trees are unstable (small data changes → very different trees). Averaging many trees in an ensemble drastically reduces variance; the committee can also express relationships that are beyond any single shallow tree, reducing bias.
• Margin-based generalisation. Weighted combinations of weak classifiers tend to produce large margins on the training points, and larger margins yield better theoretical generalisation bounds.

Limitation / caution: boosting aggressively emphasises hard tuples, so it is sensitive to noise and outliers — with very noisy data it can overfit. Also, the rounds are sequential, so it is not trivially parallelised.