101 puffs

Chapter 1 · How machines learnPuff 3 of 23

Rolling downhill

In the first puff, the machine nudged its line again and again until it fitted the café’s sales. But how did it know which way to nudge? It can’t see the best line in advance. All it can do is feel, right where it stands, whether the error goes up or down. Picture a ball on a hillside in thick fog.

Guess first

The ball sits on the left wall of the valley, where the ground slopes down to the right. Which way should the machine turn its knob?

Play with it

Fig. 1 · Gradient descent The error valley, and the line it gives

The blue ball is the line’s slope knob, resting on the error valley. Press “Take a step”, or drag the ball somewhere else first.

How it works

Tap a step to see it in the figure.

Check yourself

Why does the ball slow down near the bottom?

Go deeper: the mathDerivatives, the update rule, and many knobs at once

The valley

The line is ŷ = w·x + b, with slope w and height b. To draw the error against one knob, the page sets the height to its best value for each slope. That best height always puts the line through the middle of the dots, the average temperature and average sales (x̄, ȳ) = (22.2 °C, 41.7 coffees). So the error, the mean squared error from the last puff, depends on w alone:

L(w) = 1n Σ ( w(xi − x̄) + ȳ − yi )²

Where the ball is now: w = 0, L = 334.4.

The slope of the ground

The slope under the ball is the derivative: how much L changes for a tiny change h in w, divided by h. Working it out for this valley gives

dLdw ≈ L(w + h) − L(w)h

dLdw = 2n Σ (ŷi − yi)(xi − x̄)

Each day pushes on the knob in proportion to its miss and to how far its temperature is from average. Right now: dL/dw = −231.3.

The update rule

w ← w − η dLdw

This page uses η = 0.004, so the next step is 0.004 × 231.3 = 0.93 to the right.

Many knobs: the gradient

With more knobs there is one slope per knob, each measured while the others are held still. Together they form the gradient, written ∇L: an arrow pointing in the steepest uphill direction. Every knob then steps against its own slope at once:

∇L = ( ∂L∂w, ∂L∂b, … )

knobs ← knobs − η ∇L

Fig. 2 · Two knobs at once

Each ring joins knob settings with the same error, like contour lines on a map; the error is lowest at the green dot. The blue dots are the path the machine in puff 1 took: 47 steps.

The height knob settles first, because the valley is steeper in that direction. The map uses the same trick as puff 1: while learning, temperatures are measured from their average in steps of 10 °C, which keeps the valley about as steep for one knob as for the other. The axes are still labelled in ordinary units.

What this page simplifies

The café valley is a perfect bowl with one lowest point. A neural network’s error landscape has millions or billions of directions, with flat plains, saddles and many dips. Gradient descent still works remarkably well there, usually in a form that measures the slope on a small random batch of examples at a time (stochastic gradient descent). And unlike a real ball, plain gradient descent has no momentum; adding some is a popular upgrade.

Sources

  1. I. Goodfellow, Y. Bengio and A. Courville, Deep Learning, MIT Press, 2016, section 4.3, Gradient-based optimization.
  2. Google, Machine Learning Crash Course: Linear regression, Gradient descent.
  3. A.-L. Cauchy, “Méthode générale pour la résolution des systèmes d’équations simultanées”, Comptes rendus de l’Académie des sciences 25, 1847: the first description of the method.
  4. The café numbers are made up for this course.