Decision Tree

Boosting

Boosting combines many weak learners (55% accuracy, barely better than random) into a strong learner (90%+) by iteratively reweighting the dataset.

Why reweight instead of resample like bagging?

Bagging reduces variance by averaging independent-ish learners. Boosting targets bias: each new learner focuses on the mistakes of the previous ones, so the committee as a whole can represent functions none of them could alone.

Unlike bagging, boosting is inherently sequential.

Iterative process:

1. Train a classifier on the current weights
2. Downweight points it gets right, upweight points it gets wrong
3. Train the next classifier on the new weighted dataset
4. Final prediction: weighted vote of all learners

Detour: Online Learning with Experts (Hedge)

Before AdaBoost, consider the prediction-with-experts setting. For $t=1,\dots ,T$:

1. Algorithm chooses a distribution $p^{(t)}\in {\Delta }^n$ over $n$ experts
2. Adversary reveals loss vector ${\ell }^{(t)}\in [0,1{]}^n$
3. Algorithm incurs loss $⟨p^{(t)},{\ell }^{(t)}⟩$

Goal: minimize ${\sum }_t⟨p^{(t)},{\ell }^{(t)}⟩$, competing with the best single expert in hindsight ${\min }_i{\sum }_t{\ell }_i^{(t)}$.

Hedge Algorithm

Parameter $\beta \in [0,1]$:

1. Init $w^{(1)}=(1/n,\dots ,1/n)$
2. For $t=1,\dots ,T$:
   • $p^{(t)}=w^{(t)}/{\sum }_i{w}_i^{(t)}$
   • Suffer loss $⟨p^{(t)},{\ell }^{(t)}⟩$
   • Update $w_i^{(t+1)}=w_i^{(t)}{\beta }^{{\ell }_i^{(t)}}$ (downweight bad experts)

Guarantee:

${\sum }_t⟨p^{(t)},{\ell }^{(t)}⟩\le \frac{1}{1-\beta }\left[\log n+\log (1/\beta ){\min }_i{\sum }_t{\ell }_i^{(t)}\right]$

where:

• $\beta \in [0,1]$ is the learning-rate-like parameter
• $n$ is the number of experts, $T$ the number of rounds

Average regret goes to 0 as $T\to \infty$. Extremely general, used in linear programming, game theory, etc.

AdaBoost: Hedge on Datapoints

The insight: instead of treating classifiers as experts, treat datapoints as experts. Upweight points that haven’t been learned yet.

Intuition

Each round, the algorithm stares at which points the current committee still botches and says “next learner, focus here.” Easy points (already correct) get turned down; hard points get turned up until some weak learner picks up on them. You end up with a committee where each member specializes in a different slice of the hard cases, and the weighted vote stitches the specialists together.

1. Init weights $w^{(1)}=(1/n,\dots ,1/n)$
2. For $t=1,\dots ,T$:
   1. Normalize: $p^{(t)}=w^{(t)}/{\sum }_i{w}_i^{(t)}$
   2. Run WeakLearn on the weighted training set to get classifier $h^{(t)}:(x,y)\to [0,1]$
   3. Compute weighted error ${\epsilon }_t={\sum }_i{p}_i^{(t)}|h^{(t)}(x_i)-y_i|$ (should be $<1/2$ by the weak learner guarantee)
   4. Let ${\beta }_t={\epsilon }_t/(1-{\epsilon }_t)$ and update $w_i^{(t+1)}=w_i^{(t)}{\beta }_t^{1-|h^{(t)}(x_i)-y_i|}$ (upweight points misclassified by $h^{(t)}$)
3. Final classifier: weighted vote,

$h(x)=1\left[{\sum }_{t=1}^T\log \frac{1}{{\beta }_t}{h}^{(t)}(x)\ge \frac{1}{2}{\sum }_{t=1}^T\log \frac{1}{{\beta }_t}\right]$

Training Error Bound

If each weak learner has error ${\epsilon }_t\le \frac{1}{2}-\gamma$, then training error decays exponentially:

$\frac{1}{n}{\sum }_{i}1[h(x_i)\ne y_i]\le 2^T{\prod }_{t=1}^T\sqrt{{\epsilon }_t(1-{\epsilon }_t)}\le \exp (-2T{\gamma }^2)$

where:

• $\gamma$ is the weak learner edge over random guessing
• $T$ is the number of boosting rounds

Alternate View: Gradient Descent on Exponential Loss

AdaBoost can be derived as coordinate descent on ${\sum }_i\exp (-y_{i}h(x_i))$. This perspective underlies Gradient Boosted Trees, which generalize to any differentiable loss.

Intuition

Boosting is greedy gradient descent in function space. Each weak learner fits the residual (the negative gradient of the loss at the current ensemble’s predictions) and gets added with a small step size. The weight-updating view and the gradient-descent view are the same algorithm seen from two angles: “focus on what we got wrong” is literally “move in the direction of the gradient.”

Overfitting behavior

AdaBoost surprisingly often keeps improving test error even after training error hits 0, as the margin keeps growing. With very expressive base learners, it can and does overfit.

Viola-Jones face detection (2001): start with very simple Haar-like feature classifiers, use boosting to combine into a cascade. First real-time face detector.

Bagging vs Boosting

	Bagging	Boosting
Goal	Reduce variance	Reduce bias
Data	Bootstrap (parallel)	Reweighted (sequential)
Parallel?	Yes	No, inherently sequential
Base learner	Full-depth trees	Weak (decision stumps)

Both are simple and flexible with any base learner, but both lose some interpretability compared to a single tree.

Slides: http://www.gautamkamath.com/courses/CS480-fa2025-files/lec8.pdf

Related

• Bootstrap Aggregating (Bagging)
• Decision Tree
• Gradient Boosted Decision Tree
• Ensemble Modelling