Deep learning: Fit a line by gradient descent

Train the simplest model there is, one step at a time.

What to build

A program that fits y = w x + b to data with gradient descent on the mean squared error.

Requirements

  • Start from w = 0 and b = 0. Each step computes both derivatives, then sets w ← w − rate × ∂L/∂w and b ← b − rate × ∂L/∂b.
  • After each step, print step I: w W, b B, loss L, the loss computed with the new parameters, all with four decimal places.

Input

Line 1: the learning rate and the number of steps. Line 2: the x values. Line 3: the y values.

Output

One line per step.

Constraints

At most 100 steps and 100 points.

Example

Input:

0.1 2
1 2
2 4

Output:

step 1: w 1.0000, b 0.6000, loss 1.0600
step 2: w 1.3200, b 0.7800, loss 0.1732

Why it works

Each step moves both parameters downhill on the loss surface, so with a suitable learning rate the line moves towards the best fit.

Examples

Example 1 · Input
0.1 2
1 2
2 4
Expected output
step 1: w 1.0000, b 0.6000, loss 1.0600
step 2: w 1.3200, b 0.7800, loss 0.1732
Example 2 · Input
0.25 2
0
3
Expected output
step 1: w 0.0000, b 1.5000, loss 2.2500
step 2: w 0.0000, b 2.2500, loss 0.5625

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

Hints

Hint 1

Compute both derivatives from the current w and b before changing either.

Hint 2

∂L/∂w = (2/n) Σ (w x + b − y) x and ∂L/∂b = (2/n) Σ (w x + b − y).

Solution

Show one correct solution (try it yourself first)
rate, steps = input().split()
rate, steps = float(rate), int(steps)
xs = list(map(float, input().split()))
ys = list(map(float, input().split()))
n = len(xs)
w = b = 0.0


def loss(w, b):
    return sum((w * x + b - y) ** 2 for x, y in zip(xs, ys)) / n


for i in range(1, steps + 1):
    dw = 2 * sum((w * x + b - y) * x for x, y in zip(xs, ys)) / n
    db = 2 * sum(w * x + b - y for x, y in zip(xs, ys)) / n
    w, b = w - rate * dw, b - rate * db
    print(f"step {i}: w {w:.4f}, b {b:.4f}, loss {loss(w, b):.4f}")

Lesson: Loss functions and gradient descent →