Train a perceptron

Train the lesson's perceptron on any two-input data and watch its weights change epoch by epoch.

What to build

A program that runs the perceptron learning rule and reports the weights after each epoch.

Requirements

  • Go through the examples in order; update immediately after each mistake.
  • After each epoch print epoch e: w1 A w2 B b C, mistakes M, with A, B and C formatted with :g.
  • Stop after an epoch with no mistakes, or after the maximum number of epochs.

Input

Line 1: n, rate and the maximum number of epochs. Then n lines x1 x2 y, with y 0 or 1.

Output

One line per epoch run.

Constraints

1 ≤ n ≤ 100, 1 ≤ epochs ≤ 100.

Example

Input:

4 1 10
0 0 0
0 1 0
1 0 0
1 1 1

Output:

epoch 1: w1 1 w2 1 b 1, mistakes 1
epoch 2: w1 2 w2 1 b 0, mistakes 3
epoch 3: w1 2 w2 1 b -1, mistakes 3
epoch 4: w1 2 w2 2 b -1, mistakes 2
epoch 5: w1 2 w2 1 b -2, mistakes 1
epoch 6: w1 2 w2 1 b -2, mistakes 0

Why it works

Each mistake moves the boundary towards classifying that example correctly; on linearly separable data this happens only finitely often, so an epoch without mistakes eventually comes.

Examples

Example 1 · Input
4 1 10
0 0 0
0 1 0
1 0 0
1 1 1
Expected output
epoch 1: w1 1 w2 1 b 1, mistakes 1
epoch 2: w1 2 w2 1 b 0, mistakes 3
epoch 3: w1 2 w2 1 b -1, mistakes 3
epoch 4: w1 2 w2 2 b -1, mistakes 2
epoch 5: w1 2 w2 1 b -2, mistakes 1
epoch 6: w1 2 w2 1 b -2, mistakes 0
Example 2 · Input
2 0.5 5
1 1 1
-1 -1 0
Expected output
epoch 1: w1 0.5 w2 0.5 b 0.5, mistakes 1
epoch 2: w1 0.5 w2 0.5 b 0.5, mistakes 0

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Start with both weights and the bias at 0; predict 1 when w₁x₁ + w₂x₂ + b > 0.

Hint 2

On a mistake: wᵢ += rate × (y − ŷ) × xᵢ and b += rate × (y − ŷ), straight away, before the next example.

Hint 3

Print numbers with the `:g` format, and stop after an epoch with no mistakes.

Solution

Show one correct solution (try it yourself first)
n, rate, epochs = input().split()
rate = float(rate)
data = [tuple(map(float, input().split())) for _ in range(int(n))]
w1 = w2 = b = 0.0
for epoch in range(1, int(epochs) + 1):
    mistakes = 0
    for x1, x2, y in data:
        error = y - (1 if w1 * x1 + w2 * x2 + b > 0 else 0)
        if error != 0:
            mistakes += 1
            w1 += rate * error * x1
            w2 += rate * error * x2
            b += rate * error
    print(f"epoch {epoch}: w1 {w1:g} w2 {w2:g} b {b:g}, mistakes {mistakes}")
    if mistakes == 0:
        break

Lesson: Perceptrons and neural networks →