Stochastic gradient descent for a line

Stochastic gradient descent updates the model after every single example instead of after all of them. Train a line that way.

What to build

A program that trains ŷ = w x + b with stochastic gradient descent and reports the line after each epoch.

Requirements

  • Start at w = 0, b = 0.
  • For each point in order: e = w x + b − y, then w ← w − rate × 2 e x and b ← b − rate × 2 e (both computed with the same e).
  • After each epoch, print epoch i: w W b B with 4 decimal places.

Input

Line 1: n, rate and epochs. Then n lines x y.

Output

One line per epoch.

Constraints

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

Example

Input:

2 0.1 2
1 2
2 3

Output:

epoch 1: w 1.1200 b 0.7600
epoch 2: w 1.1152 b 0.7696

Why it works

Each update follows the gradient of one example's squared error; on average these steps point the same way as the full gradient, but each costs only one example.

Examples

Example 1 · Input
2 0.1 2
1 2
2 3
Expected output
epoch 1: w 1.1200 b 0.7600
epoch 2: w 1.1152 b 0.7696
Example 2 · Input
1 0.25 2
2 4
Expected output
epoch 1: w 4.0000 b 2.0000
epoch 2: w -2.0000 b -1.0000

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

Hints

Hint 1

For one point, the error is e = w x + b − y, and the gradients are 2 e x and 2 e.

Hint 2

Update w and b after every point, in the given order; an epoch is one pass over all the points.

Solution

Show one correct solution (try it yourself first)
n, rate, epochs = input().split()
rate = float(rate)
points = [tuple(map(float, input().split())) for _ in range(int(n))]
w = b = 0.0
for i in range(int(epochs)):
    for x, y in points:
        e = w * x + b - y
        w, b = w - rate * 2 * e * x, b - rate * 2 * e
    print(f"epoch {i + 1}: w {w:.4f} b {b:.4f}")

Lesson: Gradient descent →