AdaBoost fit (decision stumps)

Background

AdaBoost turns a crowd of weak learners — here, one-level decision trees ("stumps") — into a strong classifier. It trains stumps in sequence; after each one it re-weights the training examples so the next stump focuses on those still misclassified, and assigns each stump a vote $\alpha$ proportional to its accuracy. The final prediction is the sign of the weighted vote.

Problem statement

Implement adaboost_fit(X, y, n_clf) that fits n_clf decision stumps by AdaBoost and returns them. Start from uniform sample weights $w_i = 1/n$. Each round, pick the stump (feature, threshold, polarity) with the smallest weighted error $\varepsilon$, then update:

$$\alpha = \tfrac{1}{2}\ln\!\frac{1 - \varepsilon}{\varepsilon + 10^{-10}}$$ $$w_i \leftarrow w_i\, e^{-\alpha\, y_i\, \hat{y}_i}, \qquad w \leftarrow \frac{w}{\sum_j w_j}$$

A stump predicts $-1$ where $x_f < \text{threshold}$ and $+1$ otherwise (flipped when polarity $=-1$). If a stump's weighted error exceeds $0.5$, set polarity $=-1$ and use $1 - \varepsilon$.

Input

• X — np.ndarray of shape (n_samples, n_features): numeric features.
• y — np.ndarray of shape (n_samples,): labels in $\{-1, +1\}$.
• n_clf — int: the number of stumps (boosting rounds).

Output

Returns a list of n_clf dicts, each a stump with keys feature_index (int), threshold (the split value), polarity ($\pm 1$), and alpha (float, the stump's vote weight).

Examples

Example 1

Input:  X = [[1, 2], [2, 3], [3, 4], [4, 5]], y = [1, 1, -1, -1], n_clf = 3
Output: clfs[0] = {'feature_index': 0, 'threshold': 3, 'polarity': -1, 'alpha': 11.5129}

Explanation: the stump "predict -1 when feature 0 >= 3" (polarity -1, threshold 3) separates the two classes with zero weighted error, so its vote $\alpha$ is very large and all three rounds re-select the same perfect stump.

Constraints

• Initialise sample weights uniformly to $1/n$.
• Candidate thresholds are the unique values of each feature; a sample predicts $-1$ when $x_f < \text{threshold}$.
• If the weighted error $> 0.5$, set polarity $=-1$ and replace $\varepsilon$ with $1 - \varepsilon$.
• Apply the $\alpha$ and weight-update formulas above, then renormalise the weights each round.
• Labels are $\{-1, +1\}$ (not $\{0, 1\}$).

Notes

• The $+10^{-10}$ inside $\alpha$ guards against division by zero when a stump is perfect ($\varepsilon = 0$); $\alpha$ then blows up and that stump dominates the vote.
• Re-weighting is the heart of boosting: misclassified points become heavier, forcing later stumps to attack the hard cases instead of re-solving the easy ones.