Linear regression with gradient descent

Fit a line by repeatedly stepping the parameters downhill on the squared error, and check it against the closed form.

xs = [0, 1, 2, 3, 4]
ys = [1, 3, 5, 7, 9]
w = b = 0.0
n = len(xs)
for _ in range(2000):
    grad_w = sum(2 * (w * x + b - y) * x for x, y in zip(xs, ys)) / n
    grad_b = sum(2 * (w * x + b - y) for x, y in zip(xs, ys)) / n
    w -= 0.05 * grad_w
    b -= 0.05 * grad_b

mean_x = sum(xs) / n
mean_y = sum(ys) / n
closed_w = sum((x - mean_x) * (y - mean_y) for x, y in zip(xs, ys)) / sum((x - mean_x) ** 2 for x in xs)
closed_b = mean_y - closed_w * mean_x
print(round(w, 3), round(b, 3))
print(closed_w, closed_b)

2.0 1.0
2.0 1.0

Explanation

Regression predicts a number. Linear regression models the output as ŷ = w·x + b with a slope w and an intercept b. Training means finding the w and b that minimize a loss. The usual choice is the mean squared error (MSE), the average of (ŷ − y)² over the training examples.

Gradient descent minimizes the loss iteratively. The gradient says how the loss changes as each parameter changes. For MSE, ∂L/∂w = (2/n) Σ (ŷ − y)·x and ∂L/∂b = (2/n) Σ (ŷ − y). Each step moves the parameters a small distance, set by the learning rate, in the direction that reduces the loss. A learning rate that is too small makes training slow, and one that is too large overshoots and can diverge. Features on very different scales also slow convergence, which is why they are often standardized.

The data here lie exactly on y = 2x + 1, so after 2000 steps the parameters converge to w = 2 and b = 1. For one feature there is also a closed-form answer, ordinary least squares: w = Σ(x − x̄)(y − ȳ) / Σ(x − x̄)² and b = ȳ − w·x̄. Gradient descent gives the same result here, but it scales to models with millions of parameters where no closed form exists, which is why it is the basis of neural network training.

—

—

2.0 1.0

2.0 1.0
2.0 1.0

Cost and common mistakes

Each gradient step costs O(n) for n examples, so training costs O(steps × n). The closed form for one feature costs O(n).

• A learning rate that is too large makes the loss grow instead of shrink. Reduce it if training diverges.
• Real data are noisy, so the fitted line will not pass through every point. The goal is the best fit, not a perfect one.
• Check the model on data it was not trained on. A line that fits the training set may still predict poorly.

Try it yourself

What happens if you set the learning rate to 0.5 in this program?

Further reading

• Stanford CS229: Machine Learning (external)
• An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani) (external)
• scikit-learn user guide (external)