AdaBoost: reweighting misclassified samples each round

The problem, from first principles

A single decision stump (a tree of max_depth=1) can only ask one question about one feature before it has to commit to an answer. That makes it a weak learner almost by definition — better than a coin flip, but not by much. 03-gradient-boosting-negative-gradient and 04-full-boosting-loop already showed one way to chain weak learners into a strong one: fit each new tree to the previous ensemble's residual. AdaBoost, historically the earlier idea, chains weak learners a different way. It never touches what a tree predicts — it changes which training samples the next tree is trained to care about, by making the hard-to-classify samples louder in the training data each round.

From theory to code

Theory below derives three things: how much to trust a round's tree (alpha), how to make the next round pay more attention to this round's mistakes (the weight update), and how to combine every round's tree into one final prediction. adaboost_train runs the round loop and produces the list of (tree, alpha) pairs; adaboost_predict implements the final weighted vote. Neither reimplements tree-building — both call 03-best-split-minimal-tree's build_tree/predict_tree directly.

Constraints

• labels are {-1, +1}-valued, AdaBoost's standard convention, not {0, 1}.
• adaboost_train(input, labels, n_rounds, max_depth=1, seed=None) returns a list of exactly n_rounds (tree, alpha) pairs, one per round, in round order.
• max_depth=1 by default: a shallow decision stump, AdaBoost's classic weak learner.
• Sample weights start uniform (1/n_samples) and must stay a valid probability distribution (renormalized to sum to 1) after every round's update.
• Resampling for tree training is done via rng built once from seed before the loop starts, not re-seeded each round, so results are reproducible for a fixed seed.
• The weighted error rate must be clipped away from exactly 0 or 1 before it's used in alpha's formula, to avoid log(0) or division by zero.
• adaboost_predict(ensemble, input) returns an array of {-1, +1} predictions, one per row of input, never anything else.
• Reuse 03-best-split-minimal-tree's build_tree/predict_tree, don't reimplement tree construction.

Hints

Open one at a time. Each gives away a little more than the last.