AdaBoost

AdaBoost's parameter T controls the bias-complexity tradeoff, so deciding how to set T is part of model selection rather than a minor decision made afterward.

Programming

Interactive lab

Try it: AdaBoost with Decision Stumps

How AdaBoost keeps a distribution D over the training examples, asks the weak learner for the decision stump with the smallest weighted error , gives it weight , raises the weight of its mistakes, and combines the stumps into .

How it works

Start with the uniform distribution D(1) = 1/m.
Weak learner: try every stump b·sign(theta - x) (thresholds around and between the points, both signs) and keep the one with the smallest weighted error .
Give it the weight .
Reweight: , so misclassified examples gain weight.
The ensemble predicts ; its training error is shown after each round.

Default run (12 steps): 9 labelled points on a line. Start AdaBoost with the uniform distribution D(1) = 1/9 on every example; run up to T = 4 rounds. … Reweight: D(5)_i = D(4)_i exp(-w4 y_{_i} h4(x_{_i})) / Z. Misclassified D, E, F gain weight. The ensemble sign(0.35 h1 + 0.55 h2 + 0.8 h3 + 0.69 h4) gets 0/9 training examples wrong.

Simplified: 1-D toy data (2–12 labelled points) and at most 10 rounds. Ties between equally good stumps go to the smaller threshold (then b = +1); a score of exactly 0 predicts +1; if a stump has eps = 0 boosting stops because its weight would be infinite.

Educational simulation

Loading the simulation…

The Decision Before Training

Suppose a practical problem could be approached with several algorithms, and each algorithm could be configured in several ways. The central challenge is not only writing down an algorithm. You must decide which algorithm fits the problem and which parameter settings fit it. This decision-making task is called model selection.

What two choices define the selected model, and where does AdaBoost's T belong?

Definition

Model selection is the task of choosing an algorithm for a particular problem and setting its parameters. A selected model is therefore defined by both an algorithm choice and parameter choices.

Rounds of Adaptive Attention

AdaBoost, short for Adaptive Boosting, begins with access to a weak learner rather than a single powerful classifier. Across consecutive rounds, the weak learner receives a distribution over the training examples and produces a hypothesis from that distribution and the sample. AdaBoost then evaluates that hypothesis. Examples it misclassifies receive more attention in the following round, encouraging the next hypothesis to focus on cases that earlier hypotheses handled poorly.

What happens to attention on training examples after each weak learner makes mistakes?

What do you think happens?

A weak hypothesis handles some training examples poorly. What should AdaBoost do with those examples in the following round?

Give them more attention
Give them less attention
Discard the entire training set

Reveal answer

Answer:

Give them more attention

AdaBoost adapts by changing the distribution over training examples. Misclassified examples receive more attention in the following round, encouraging later learning to focus on them.

The Weak Learner's Input

The weak learner is the learning component AdaBoost repeatedly uses. At a given round, it works with the current distribution over training examples and the training sample, then produces a hypothesis. The distribution determines how much attention different examples receive at that point in the process. After the hypothesis is evaluated, its mistakes help determine the distribution used in the next round.

How does the current distribution flow into the weak learner, and how does the learner's output affect the next distribution?

Worked example

Tracing Two Rounds

Follow the role of one training example that the first weak hypothesis misclassifies.

1
Round 1 input
The weak learner receives the training sample together with the current distribution over training examples.
2
Round 1 output
The weak learner produces a hypothesis, and AdaBoost evaluates that hypothesis's error.
3
Attention update
Because the example was misclassified, it receives more attention in the following round.
4
Round 2 input
The weak learner now receives the changed distribution, so the next hypothesis is encouraged to focus more on examples handled poorly earlier.

Result

AdaBoost is adaptive because the result of one round changes the distribution used in the next round.

Error Becomes Influence

AdaBoost does not simply keep every weak hypothesis with equal influence, nor does it automatically discard a hypothesis after measuring it. A hypothesis's error determines its weight in the final combination. Thus, each hypothesis has two consequences: its error affects how much influence it receives, and its mistakes affect which training examples receive more attention later.

How does a weak hypothesis's error on the weighted training set determine its influence in the final classifier?

The important distinction is between error and attention. The error of a hypothesis determines that hypothesis's weight in the final combination. Separately, the examples that the hypothesis misclassifies receive more attention in the following round. AdaBoost therefore evaluates each weak hypothesis individually while also using its mistakes to guide later learning.

Building the Strong Classifier

After successive rounds, AdaBoost has a collection of weak hypotheses and a weight for each one. It combines those weighted hypotheses to form the strong classifier. The final classifier is therefore not just the last weak hypothesis. It uses the collection of hypotheses, with each hypothesis contributing according to the influence assigned from its measured error.

How are individual weak hypotheses and their weights combined to produce the final prediction?

Worked example

Why the Collection Matters

Compare the role of one weak hypothesis with the role of the final strong classifier.

1
One hypothesis
A weak hypothesis is produced from the current distribution and sample. Its measured error determines its weight.
2
Several hypotheses
Across rounds, AdaBoost collects multiple weak hypotheses. Each one has an influence determined by its error.
3
Final combination
AdaBoost combines the weighted hypotheses rather than relying only on the most recently produced hypothesis.

Result

The strong classifier is the weighted combination of the weak hypotheses gathered across rounds.

Choosing the Number of Rounds

AdaBoost's parameter T controls the number of rounds used in the process. Changing T changes how the model is configured, so selecting T belongs to model selection. The source identifies T as controlling the bias-complexity tradeoff: parameter setting requires considering the balance between the model's bias and its complexity.

How does changing AdaBoost's number of rounds T relate to model complexity and the bias-complexity tradeoff?

Mistakes in Reasoning

Common mistake
Defining model selection as only choosing an algorithm.
What it looks like
The learner says, "Model selection means deciding whether to use AdaBoost."
Why it fails
Model selection also includes setting the algorithm's parameters.
Do this instead
Include both decisions: choose an algorithm and choose its parameter settings.
Common mistake
Treating T as a detail outside model selection.
What it looks like
The learner chooses AdaBoost and assumes the number of rounds can be ignored.
Why it fails
T controls the bias-complexity tradeoff, so choosing T is part of selecting the model.
Do this instead
Ask how T should be set for the particular practical problem.
Common mistake
Assuming every weak hypothesis has equal influence.
What it looks like
The learner describes the final classifier as an unweighted collection of hypotheses.
Why it fails
A hypothesis's error determines its weight in the final combination.
Do this instead
Track the measured error and the resulting hypothesis weight.
Common mistake
Assuming AdaBoost focuses on the same examples in every round.
What it looks like
The learner treats the training-example distribution as fixed after the first round.
Why it fails
Misclassified examples receive more attention in the following round.
Do this instead
Trace how each round's mistakes change the distribution used by the next round.
Common mistake
Calling the last weak hypothesis the strong classifier.
What it looks like
The learner ignores all earlier hypotheses after the final round.
Why it fails
AdaBoost forms the strong classifier by combining the weighted weak hypotheses.
Do this instead
Describe the final classifier as a weighted combination of the collected hypotheses.

Check Your Understanding

MEDIUM

Explain AdaBoost's process in four connected steps: first identify what the weak learner receives, then state what it produces, then explain how hypothesis error affects the hypothesis's weight, and finally describe how mistakes change the next example distribution and contribute to the strong classifier.

Hints

Mention the training sample and the current distribution over training examples.
Separate the hypothesis's weight from the increased attention given to misclassified examples.
End with the weighted combination of weak hypotheses.

Your attempt (not saved)

EASY

In your own words, explain why choosing AdaBoost's parameter T is a model-selection decision rather than a post-selection implementation detail.