A sorting robot on a production line measures two numbers for every part and must decide +1 (keep) or -1 (reject). It uses a linear rule: keep when w·x + b > 0, reject otherwise. It learns the rule from labelled parts as follows.
Start with every weight 0 and b = 0. An epoch goes through the examples once, in the order given. For each example x with label y, if y · (w·x + b) <= 0 (wrong, or exactly on the boundary) it is a mistake, and the robot corrects itself at once: w ← w + y·x and b ← b + y. Otherwise nothing changes.
Write train_perceptron(X, y, max_epochs) that returns a tuple (w, b, mistakes), where mistakes is a list with the number of mistakes in each epoch that was run. Stop after the first epoch without mistakes (it is included in the list), or after max_epochs epochs.
Examples
Input: X = [[1, 1], [2, 3], [3, 1], [4, 4]], y = [-1, 1, -1, 1], max_epochs = 10
Output: ([-2, 3], -2, [4, 2, 0])
Explanation: in the first epoch every example is a mistake. In the second, [1, 1] and [3, 1] are
still misclassified. The third epoch makes no mistakes: -2·x0 + 3·x1 - 2 = 0 separates the parts.
Input: X = [[0, 0], [1, 1], [0, 1], [1, 0]], y = [-1, -1, 1, 1], max_epochs = 6
Output: ([1, 1], 1, [3, 4, 4, 4, 4, 4])
Explanation: no straight line separates these four parts, so the robot never has a perfect epoch.
Constraints
1 <= len(X) <= 500,1 <= d <= 10, the numbers are integers or floats, labels are1or-10 <= max_epochs <= 200- the weights may be returned as integers or floats; numbers are compared with a tolerance of
1e-6
Goals
- Implement the perceptron's mistake-driven update with labels +1 and -1
- Visit the examples in a fixed order, epoch after epoch, and count the mistakes of each epoch
- Stop after a perfect epoch or when the epoch budget runs out