Weighted Decision Stump

Fit a decision stump to weighted data. A stump is a tree with a single split, and it is the usual weak learner inside AdaBoost.

Labels are -1 or +1, and each sample has a weight w[i] >= 0. A stump is described by a feature j, a threshold t and a polarity p in {+1, -1}. It predicts p where X[i, j] > t and -p everywhere else. Its error is the sum of the weights of the samples it gets wrong.

Try every feature, every threshold that is a midpoint between two consecutive unique values of that feature, and both polarities. Return the stump with the lowest weighted error as (feature, threshold, polarity, error).

Break ties in this order: lower feature index, then lower threshold, then polarity +1 before -1.

Function signature

def fit_stump(X, y, w):

Example

Input

X = np.array([[1.0], [2.0], [3.0], [4.0]])
y = np.array([-1, -1, 1, 1])
w = np.full(4, 0.25)
fit_stump(X, y, w)

Output

(0, 2.5, 1, 0.0)

Reasoning

The candidate thresholds are 1.5, 2.5 and 3.5. With threshold 2.5 and polarity +1, the stump predicts +1 for the values 3 and 4 and -1 for 1 and 2. That matches every label, so the error is 0.

Constraints and notes

• Weights do not have to sum to one.
• A feature with only one unique value has no thresholds, so skip it.
• Compare errors with a small tolerance, such as 1e-12, so that the tie rules hold under floating point error.