Concepts / AdaBoost and Distribution-Weighted Risk

AdaBoost and Distribution-Weighted Risk

The central mechanism is selection: AdaBoost supplies D, and the weak learner returns the decision stump that minimizes risk relative to D.

  • 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

  1. Start with the uniform distribution D(1) = 1/m.
  2. 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 .
  3. Give it the weight .
  4. Reweight: , so misclassified examples gain weight.
  5. 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 yi h4(xi)) / 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…

From Many Stumps to One

AdaBoost needs a weak learner that can return one precise hypothesis rather than an arbitrary decision stump. The learner searches a class of threshold-based stumps and selects the stump with the smallest relevant risk. In ordinary empirical risk minimization, that risk is the training loss L_S(h). In AdaBoost, the learner instead uses a probability distribution D over the training examples, so the examples do not all have the same influence on the selection.

Key point

The central mechanism is selection: AdaBoost supplies D, and the weak learner returns the decision stump that minimizes risk relative to D.

Anatomy of a Decision Stump

For an input x in R^d, the decision-stump class used here contains hypotheses of the form sign(θ - x_i). The index i chooses one coordinate of x, and θ chooses a threshold for that coordinate. The sign test then maps the input to a binary prediction. A stump therefore makes its decision from one coordinate and one threshold, rather than combining all coordinates at once.

signbinary mappingθthreshold−comparisonx_iselected coordinateacts onpaired withcompares
How does a decision stump choose one coordinate, apply a threshold, and map each input to a binary prediction?
Worked example

Reading One Stump

Interpret a hypothesis written as sign(θ - x_i).

  1. 1
    Choose i

    Select one coordinate of the input x. The index i identifies which coordinate the stump will inspect.

  2. 2
    Choose θ

    Set a threshold for the selected coordinate.

  3. 3
    Apply the sign test

    Evaluate the threshold expression for that coordinate and use sign to produce the stump's binary prediction.

Result

The hypothesis is completely specified by one coordinate choice and one threshold choice.

ERM Chooses the Best Candidate

Let the training set be S = ((x₁, y₁), ..., (x_m, y_m)). An empirical risk minimization rule searches the decision-stump hypothesis class instead of returning an arbitrary stump. It compares the training loss L_S(h) of candidate stumps and selects a hypothesis h whose loss is as small as possible. The selected hypothesis is a function from the input space X to the output space Y.

h₁coordinate i₁, threshold θ₁L_S(h)training lossh*smallest lossh₂coordinate i₂, threshold θ₂h₃coordinate i₃, threshold θ₃evaluateevaluateevaluateminimize
What does an ERM rule compare, and which threshold and coordinate does it ultimately select?
Worked example

An ERM Decision

Suppose the stump class contains several choices of coordinate and threshold. What must an ERM rule return?

  1. 1
    Search

    Consider the available hypotheses of the form sign(θ - x_i).

  2. 2
    Evaluate

    Determine the training loss L_S(h) for the candidate stumps.

  3. 3
    Select

    Choose the stump whose training loss is as small as possible.

Result

ERM returns a selected stump h, not merely the class of all possible stumps and not an arbitrary member of that class.

Reading the Distribution D

Definition

The distribution D is a probability vector over the m training examples. Each entry is nonnegative, and all entries together sum to 1. The entry associated with a particular training example describes how probability is assigned to that example.

D₁example (x₁, y₁)1total probabilityD₂example (x₂, y₂)D_mexample (x_m, y_m)contributescontributescontributes
How are the entries of D associated with individual training examples, and how do they sum to one?
Worked example

Interpreting D

Use the illustrative distribution D = (0.2, 0.5, 0.3) over three training examples.

  1. 1
    Match entries to examples

    The first, second, and third entries correspond to the first, second, and third training examples.

  2. 2
    Check nonnegativity

    Each listed probability is nonnegative.

  3. 3
    Check the total

    The entries add to 1, so they form a probability vector.

Result

The second training example receives the largest probability in this illustrative distribution, while the entries still describe one total distribution over the training set.

Weighted Risk Guides the Next Stump

AdaBoost keeps the selection idea from ERM but changes the evaluation context. The weak learner receives D and must minimize risk relative to that supplied distribution. Consequently, the preferred stump is determined not only by which examples it classifies correctly, but also by how probability is distributed across those examples. If D assigns more probability to one part of the training set, errors affecting that part have greater influence on the risk comparison than they would under a different distribution.

Dprobabilities over examplesh₁sign(θ₁ − x_i₁)risk_D(h₁)evaluated using Dselected stumpsmallest risk relative to Dh₂sign(θ₂ − x_i₂)risk_D(h₂)evaluated using Dweights evaluationweights evaluationevaluateevaluatecomparecompare
How do the example weights in D change which stump has the smallest risk?
D₁first supplied distributionh₁stump minimizing risk underD₁D₂different supplieddistributionh₂stump minimizing risk underD₂minimize risknext supplied distributionminimize risk
What changes when AdaBoost supplies a distribution that emphasizes different training examples, and how does that guide the next stump?

Mistakes in the Selection Rule

  • Common mistake

    Treating a decision stump as an arbitrary rule

    What it looks like

    Describing a stump without identifying a coordinate and a threshold

    Why it fails

    The stated stump class has the form sign(θ - x_i), where i identifies a coordinate and θ supplies a threshold.

    Do this instead

    Name both ingredients: one selected coordinate and one threshold.

  • Common mistake

    Saying that ERM returns any stump in the class

    What it looks like

    Choosing a stump before comparing its training loss with the losses of other candidates

    Why it fails

    ERM searches the hypothesis class for a stump whose training loss L_S(h) is as small as possible.

    Do this instead

    Describe ERM as a search-and-selection rule based on training loss.

  • Common mistake

    Forgetting that D is a probability vector

    What it looks like

    Using negative entries or entries whose total is not 1

    Why it fails

    The entries of D are nonnegative probabilities assigned to the m training examples, and they sum to 1.

    Do this instead

    Check nonnegativity, correspondence with the training examples, and total probability 1.

  • Common mistake

    Using ordinary ERM when the task supplies D

    What it looks like

    Selecting a stump only by unweighted training loss in an AdaBoost round

    Why it fails

    For AdaBoost, the learner must minimize risk relative to the supplied distribution D.

    Do this instead

    Evaluate candidate stumps using the risk associated with the given D and return the minimizing stump.

Apply the Rule

MEDIUM

A learner receives a training set S and a probability vector D over its m examples. Explain what the learner must search over, what quantity it must minimize, and what form the returned hypothesis must have.

Hints
  • Start with the hypothesis class used by the weak learner.
  • Distinguish ordinary training loss L_S(h) from risk relative to the supplied D.
  • State the required form using one coordinate and one threshold.
Worked example

Complete Answer Pattern

Give a concise but complete description of the AdaBoost weak learner in this setting.

  1. 1
    Identify the class

    The learner searches decision stumps over Rd of the form sign(θ - x_i).

  2. 2
    Identify the distribution

    D assigns nonnegative probabilities to the m training examples, with total 1.

  3. 3
    Identify the objective

    The learner minimizes risk relative to the supplied D rather than choosing an arbitrary stump.

  4. 4
    Identify the output

    The returned hypothesis is the stump that minimizes that distribution-relative risk.

Result

The weak learner searches the stump class, evaluates candidates using D, and returns a stump sign(θ - x_i) with minimum risk relative to D.

Key Takeaways

  1. 1
    A decision stump over Rd has the form sign(θ - x_i): one coordinate, one threshold, and a sign-based binary prediction.
  2. 2
    ERM searches the stump class and selects a hypothesis with training loss L_S(h) as small as possible.
  3. 3
    D is a probability vector over the m training examples; its entries are nonnegative and sum to 1.
  4. 4
    AdaBoost supplies D to the weak learner, which must minimize risk relative to that distribution.
  5. 5
    Changing D can change which stump is preferred because the distribution changes how the training examples influence the risk comparison.

At a glance

  • Decision stumps select one coordinate and compare it with one threshold through sign(θ - x_i).
  • ERM selects the lowest-training-loss stump from the hypothesis class.
  • A distribution D assigns nonnegative probabilities to the training examples and has total 1.
  • AdaBoost uses D to define the relevant risk, so the next stump is chosen according to the supplied example distribution.

Related Topics

Related concepts

More concepts starting with A