Boosting makes the next model focus on the hard examples. Compute one round of AdaBoost's bookkeeping.
What to build
A program that computes a weak model's weighted error, its say α, and the new example weights.
Requirements
- Normalize the given weights to sum to 1, then compute ε, the total weight of examples where the prediction differs from the label.
- Compute α = ½ ln((1 − ε) / ε).
- Update each weight: × e^α if wrong, × e^(−α) if right; then normalize to sum to 1.
- Print
error E,alpha Aandweightsfollowed by the new weights, all with 4 decimal places.
Input
Line 1: the labels (1 or −1). Line 2: the model's predictions (1 or −1). Line 3: the current weights (positive numbers).
Output
Three lines.
Constraints
1 to 1000 examples; 0 < ε < 0.5.
Example
Input:
1 1 -1 -1
1 -1 -1 -1
0.25 0.25 0.25 0.25
Output:
error 0.2500
alpha 0.5493
weights 0.1667 0.5000 0.1667 0.1667
Why it works
α grows as the error shrinks, so better models get more say; after the update the misclassified examples carry exactly half of the total weight, which forces the next model to do better on them.
Examples
1 1 -1 -1 1 -1 -1 -1 0.25 0.25 0.25 0.25
error 0.2500 alpha 0.5493 weights 0.1667 0.5000 0.1667 0.1667
1 -1 1 1 0.6 0.4
error 0.4000 alpha 0.2027 weights 0.5000 0.5000
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Normalize the weights first; the error ε is the total weight of the examples the model got wrong.
Hint 2
α = ½ ln((1 − ε) / ε).
Hint 3
Multiply wrong examples' weights by e^α and right ones' by e^(−α), then divide every weight by the new total.
Solution
Show one correct solution (try it yourself first)
import math
labels = list(map(int, input().split()))
predicted = list(map(int, input().split()))
weights = list(map(float, input().split()))
total = sum(weights)
weights = [w / total for w in weights]
error = sum(w for w, y, p in zip(weights, labels, predicted) if y != p)
alpha = 0.5 * math.log((1 - error) / error)
new = [w * math.exp(alpha if y != p else -alpha) for w, y, p in zip(weights, labels, predicted)]
total = sum(new)
print(f"error {error:.4f}")
print(f"alpha {alpha:.4f}")
print("weights", *[f"{w / total:.4f}" for w in new])