A fruit scanner sorts mangoes into ripe (1) and unripe (-1) from two scores, sweetness and acidity. The ripe and unripe mangoes overlap, so the perceptron never has a perfect epoch: it keeps fixing one mistake by making another, and the weights it happens to hold when you stop can be poor. The fix is to keep the best weights seen so far "in your pocket".
The perceptron: start with every weight 0 and b = 0, and go through the examples in the order given, epoch after epoch. An example (x, y) is a mistake when y · (w·x + b) <= 0; then w ← w + y·x and b ← b + y.
Write pocket_perceptron(X, y, epochs) that runs at most epochs epochs (stop early after an epoch without any mistake) and returns (w, b, errors) for the pocket: the weights and bias, among the starting point and the result of every single update, with the fewest mistakes on the whole training set, and that number of mistakes. When two candidates have the same number of mistakes, keep the earlier one.
The helper crate_scan(n, seed) returns (X, y) for n scanned mangoes (whole-number scores).
Examples
Input: X = [[1], [2], [3], [4], [5]], y = [-1, -1, 1, -1, 1], epochs = 10
Output: ([3], -7, 1)
Explanation: the line 3·x - 7 = 0 (at x = 2.33) gets only the mango at x = 4 wrong. The perceptron
passes through these weights and moves on, but the pocket keeps them.
Input: X = [[1, 1], [2, 3], [3, 1], [4, 4]], y = [-1, 1, -1, 1], epochs = 10
Output: ([-2, 3], -2, 0)
Explanation: separable data: the pocket ends with the perfect line the perceptron finds.
Constraints
1 <= len(X) <= 200,1 <= d <= 5, whole-number features, labels1or-1,0 <= epochs <= 20- the starting point (all zeros) counts as a candidate: it gets every example wrong
Goals
- Run the perceptron on data that no line separates
- Measure the training mistakes of every weight vector the perceptron visits
- Return the best one seen, not the last one