One round of AdaBoost

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 A and weights followed 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

Example 1 · Input
1 1 -1 -1
1 -1 -1 -1
0.25 0.25 0.25 0.25
Expected output
error 0.2500
alpha 0.5493
weights 0.1667 0.5000 0.1667 0.1667
Example 2 · Input
1 -1
1 1
0.6 0.4
Expected output
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])

Lesson: Ensembles: random forests and boosting →