Fit a line with gradient descent

Learn it

Words to know

mean squared error

A loss for predicting numbers: the average of the squared differences between predictions and true values.

gradient

The slope of the loss for one number in the model: which way the loss moves, and how fast, when that number goes up a little.

learning rate

How far to move against the gradient on each update. Too small is slow; too large overshoots.

How it works

1. Predict w * x + b for every point, and take the error prediction - y for each. The loss is the mean of the squared errors.
2. The slope for w is 2 * mean(error * x). A point with a large x moves the weight more.
3. The slope for b is 2 * mean(error).
4. Update both together: w = w - rate * dw and b = b - rate * db. Both slopes come from the same errors, worked out before either number changes.

Worked example

Input
xs = [1, 2]
ys = [2, 4]
rate = 0.1
steps = 1

Output
[1, 0.6]

The true line is y = 2x. After one step the model already says 1.6 and 2.6 for the two points, much closer than 0 and 0.

Why it matters

Chapter 4 runs this same loop in PyTorch, where the slopes are worked out for you. Knowing what happens by hand makes that code readable.

Your turn

Fit a line w * x + b to some points with gradient descent on the mean squared error. Start from w = 0 and b = 0.

xs

the x value of each point; at least one

ys

the y value of each point, in the same order

rate

the learning rate

steps

how many updates to make; 0 or more

Returns

The list [w, b] after the last update.

Input
xs = [1, 2]
ys = [2, 4]
rate = 0.1
steps = 1

Output
[1, 0.6]

Input
xs = [1, 2]
ys = [2, 4]
rate = 0.1
steps = 2

Output
[1.32, 0.78]

Input
xs = [0, 1, 2, 3]
ys = [1, 3, 5, 7]
rate = 0.1
steps = 1

Output
[1.7, 0.8]

Input
xs = [1]
ys = [2]
rate = 0.1
steps = 0

Output
[0, 0]

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Where to start

   One update needs three things in order: the error of every point, the two slopes, and then the two new values.

2. Hint 2: The key step

   Work out all the errors with the current w and b first, and keep them in a list. Use that one list for both slopes.

3. Hint 3: The outline

   Set n to len(xs). Repeat steps times: build errors as w * x + b - y for each point; set dw to 2 * sum(e * x for e, x in zip(errors, xs)) / n and db to 2 * sum(errors) / n; then subtract rate * dw from w and rate * db from b. Return [w, b].

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Step by step

1. How far each prediction is from its true value. The errors are stored once, so both slopes are measured against the same line.
2. The slope of the loss for w and for b. Each error is multiplied by x for the weight, because the weight's effect on a prediction grows with x. The bias affects every prediction equally.
3. Move both against their slopes. Both slopes were worked out before this point, so changing w first does not disturb the update of b.

The same numbered steps are the comments in the solution.

def solve(xs, ys, rate, steps):
    w = 0.0
    b = 0.0
    n = len(xs)
    for _ in range(steps):
        # 1. How far each prediction is from its true value
        errors = [w * x + b - y for x, y in zip(xs, ys)]
        # 2. The slope of the loss for w and for b
        dw = 2 * sum(error * x for error, x in zip(errors, xs)) / n
        db = 2 * sum(errors) / n
        # 3. Move both against their slopes
        w = w - rate * dw
        b = b - rate * db
    return [w, b]

Watch out

• Do not update w and then work out the errors again for b. Both slopes must come from the line as it was at the start of the step.
• Divide by the number of points. Without it the slopes grow with the size of the data, and a rate that worked for 2 points fails for 200.

Check yourself