AdaBoost and Distribution-Weighted Risk
Decision stumps are threshold-based hypotheses of the form sign(θ - x_i).
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.
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.
Reading One Stump
Interpret a hypothesis written as sign(θ - x_i).
Choose i: Select one coordinate of the input x. The index i identifies which coordinate the stump will inspect.
Choose θ: Set a threshold for the selected coordinate.
Apply the sign test: Evaluate the threshold expression for that coordinate and use sign to produce the stump's binary prediction.
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.
An ERM Decision
Suppose the stump class contains several choices of coordinate and threshold. What must an ERM rule return?
Search: Consider the available hypotheses of the form sign(θ - x_i).
Evaluate: Determine the training loss L_S(h) for the candidate stumps.
Select: Choose the stump whose training loss is as small as possible.
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
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.
Interpreting D
Use the illustrative distribution D = (0.2, 0.5, 0.3) over three training examples.
Match entries to examples: The first, second, and third entries correspond to the first, second, and third training examples.
Check nonnegativity: Each listed probability is nonnegative.
Check the total: The entries add to 1, so they form a probability vector.
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.
Mistakes in the Selection Rule
Treating a decision stump as an arbitrary rule
The stated stump class has the form sign(θ - x_i), where i identifies a coordinate and θ supplies a threshold.
Fix:
Name both ingredients: one selected coordinate and one threshold.Saying that ERM returns any stump in the class
ERM searches the hypothesis class for a stump whose training loss L_S(h) is as small as possible.
Fix:
Describe ERM as a search-and-selection rule based on training loss.Forgetting that D is a probability vector
The entries of D are nonnegative probabilities assigned to the m training examples, and they sum to 1.
Fix:
Check nonnegativity, correspondence with the training examples, and total probability 1.Using ordinary ERM when the task supplies D
For AdaBoost, the learner must minimize risk relative to the supplied distribution D.
Fix:
Evaluate candidate stumps using the risk associated with the given D and return the minimizing stump.
Apply the Rule
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.
Complete Answer Pattern
Give a concise but complete description of the AdaBoost weak learner in this setting.
Identify the class: The learner searches decision stumps over R^d of the form sign(θ - x_i).
Identify the distribution: D assigns nonnegative probabilities to the m training examples, with total 1.
Identify the objective: The learner minimizes risk relative to the supplied D rather than choosing an arbitrary stump.
Identify the output: The returned hypothesis is the stump that minimizes that distribution-relative risk.
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
- A decision stump over R^d has the form sign(θ - x_i): one coordinate, one threshold, and a sign-based binary prediction.
- ERM searches the stump class and selects a hypothesis with training loss L_S(h) as small as possible.
- D is a probability vector over the m training examples; its entries are nonnegative and sum to 1.
- AdaBoost supplies D to the weak learner, which must minimize risk relative to that distribution.
- Changing D can change which stump is preferred because the distribution changes how the training examples influence the risk comparison.
Key Takeaways
- 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.