Fitting by Walking

Three people, at 165 centimetres and 62 kilograms, 170 and 68, and 175 and 68. The regression page’s formula gives their best line in one step, and it is the dashed line in the box above.

Nothing on this page will improve on those numbers. They are the destination, and everything the walk does can be judged by how close to them it gets and how long it takes. Do not start the walk yet.

Some models have a direct least-squares solution. Many of the important ones do not, and for those the only route to a fit is to start somewhere, ask which way makes the loss smaller, move a little that way, and repeat. That method needs four things and nothing else. A current set of parameters, a loss, the gradient of that loss, and a rule for the update.

So treat this page as a controlled experiment. Gradient descent is being used where it is not needed, on purpose, because the known answer lets us check whether the method arrived, how fast, and what went wrong when it did not. On the logistic page and every page after it, that check will not be available.

The regression page wrote a line as an intercept and a slope. This page writes the same line a different way.

ŷ = α + β·x                 intercept and slope
ŷ = level + slope·(x − x̄)   level at the mean, and slope

The level is the prediction at the mean height, which is 170 centimetres here. The slope is the predicted change per centimetre. A level of 66 and a slope of 0.6 describe the same line as an intercept of −36 and a slope of 0.6.

intercept = level − slope × mean height
          = 66 − 0.6 × 170
          = −36

Only the reference point used to describe the line has changed.

Before any formula and before any walk, hunt for the line by hand. The two sliders below set a level and a slope, the picture draws the line they make with its three residuals, and the readout gives the mean squared error. Try to get the error as low as you can, then press the button to see how close you came.

Every combination of level and slope defines one candidate line, and every candidate line earns one loss. That is the whole of what the walk is going to search through, and doing it by hand first makes the next section’s picture obvious rather than abstract.

Now put the two settings on two axes. Level across, slope up, and at every pair the mean squared error the line there earns, shaded darker where it is larger.

(level, slope)  ⟼  MSE

Move a slider and both panels move together. That is the central picture of the page. Fitting a line can be seen as moving a line through the data, or as moving a point across an error surface, and those are the same act. The regression page found the bottom of this surface by algebra. This page is going to walk down to it.

Before moving in two directions, freeze the slope and move the level alone. The loss becomes a curve over one number, and at the current level that curve has a tangent whose slope says which way is down.

In the left panel the tangent tilts downward to the right whenever the level is below 66 and upward to the right whenever it is above, so its slope, the derivative of the loss with respect to the level, is negative on one side and positive on the other and is what tells the walk which way to shift the line up or down.

Now the other way round, in the right panel. Freeze the level and rotate the line. The loss is again a curve over one number, its tangent again says which way is down, and the derivative with respect to the slope says whether to tilt the line steeper or flatter.

The two panels ask the same kind of question of two different settings. How does the loss change if this one number moves a little? A derivative is the answer to that question, and a model with two settings has two of them.

Only now put the two derivatives together.

∇L = ( ∂L/∂level ,  ∂L/∂slope )

Each component describes one direction. Together they are an arrow in the plane of section 5, and it points the way the loss increases fastest. Its negative points the way the loss decreases fastest, and that is the direction a pass steps.

The red arrow is uphill, the green arrow is downhill, and the hollow ring is where one pass at a rate of 0.02 would land. Drag the sliders around the surface and the arrows always cross the contours at right angles, because the direction along a contour is the direction in which the loss does not change at all. Gradient descent moves both settings at once using one arrow assembled from their two partial derivatives.

A pass is a fixed sequence, and it is worth seeing it as one before seeing any of its arithmetic. Use the current settings. Make predictions. Take residuals. Square and average them into the loss. Read the gradient. Scale it by the learning rate. Update both settings. Begin again from the new ones.

The inspector starts where the fit starts, a flat line at zero, which is deliberately poor rather than the worst line there is, since arbitrarily bad lines exist. Step through the stages with the buttons, then make the new line current and step through again. The next four sections are the arithmetic of the first pass, and the inspector’s numbers are the ones to check them against.

At pass zero the level and the slope are both 0, so every prediction is 0 and every residual is the person’s whole weight.

L = (3844 + 4624 + 4624) / 3 = 13092 / 3 = 4364

Take one person. Their residual depends on the level, and their squared residual depends on the residual, so the level reaches the loss through a chain of two steps.

eᵢ = yᵢ − level − slope·x′ᵢ
Lᵢ = eᵢ²
level → eᵢ → Lᵢ

Only now put in the numbers. The three residuals are 62, 68 and 68, so the level gradient is minus two thirds of their sum.

∂L/∂level = −(2/3)(62 + 68 + 68) = −132

Same chain, one change. The slope reaches a residual through that person’s centred height, so the middle step is −x′ᵢ instead of −1.

∂eᵢ/∂slope = −x′ᵢ
∂Lᵢ/∂slope = −2eᵢ·x′ᵢ
∂L/∂slope = −(2/n) Σ eᵢ·x′ᵢ

Every observation contributes to the gradient, and what each contributes depends on both its residual and its input. The gradient stage of the inspector shows these two share columns for whatever line it is standing on.

The update rule is the same for both settings.

θ_new = θ_old − η·∇L

With η = 0.02, stepping against the two gradients gives

level = 0 − 0.02·(−132) = 2.64
slope = 0 − 0.02·(−20)  = 0.4

Run the new line forward and its loss is 4017.16, down from 4364. One pass used the gradient at the old line to produce the new one, and the next pass will read its gradient at the new line rather than the old, which is what makes the walk a walk. The second pass reads residuals of 61.36, 65.36 and 63.36, a level gradient of −126.72 and a slope gradient of −6.667, and lands at 5.1744 and 0.5333.

Every pass of one walk is recorded, and the dashboard below reads that record off every instrument at once. The scrubber picks a pass and every panel follows it.

Four things are visible here that a single loss curve hides. The two settings move at very different speeds. The slope is at 0.6 to four decimals by pass 10, while the level is at 22.1 then, 64.9 at pass 100 and 65.98 at pass 200. The loss drops fast at first and slowly later, and on the log scale the late part is a straight line, which is geometric approach.

The gradient shrinks with it. And the fit agrees ever more closely with the closed form, without ever being told what the closed form is.

The status board on the dashboard separates claims that are easy to run together. Loss is finite. Loss fell during the last pass. The gradient is small. The largest movement is under the tolerance. The distance from the known answer is small. The pass limit was reached. The convergence criterion was met.

Those are different facts, and a run can hold some without the rest. Set the passes allowed to 100 and the loss is finite, falling and near its floor, while the pass limit was hit and the criterion was not met, and the level is still a kilogram from home. A run ending is not the same as a run converging, and converging is not the same as being right.

Same three people, same flat start, same sixty passes, four rates.

At 0.005 the walk is heading the right way and is nowhere near arriving, level 29.9 after sixty passes with a loss of 1306. At 0.02 it is at 60.3 with a loss of 34.5. At 0.055 it is at 65.94 with a loss of 2.004, close enough that the difference is the fourth decimal. At 0.07 the slope is at −19 million and the record had to stop before the numbers overflowed. The table below asks for a plain fit at eight rates and reports what came back.

The small parabolas under each contour plot are the slope direction on its own, the loss along the slope with the level held at its optimum, and the dots are the first eight passes hopping along it. They show four behaviours.

At 0.055 the slope crosses 0.6 on every pass and still arrives, because the crossings shrink. At 0.07 they grow. The boundary between those two is the threshold the rest of the page is about, and it is at 0.06 for these people.

The readouts on this page quote a factor per pass, 0.96 at a rate of 0.02, and it matters what that factor measures. For one direction with curvature c, a pass turns the distance from the optimum into

e_{k+1} = (1 − ηc)·e_k

so the distance, in the parameter’s own units, keeps a share of |1 − ηc| per pass. The loss contribution from that direction is quadratic in the distance, so it keeps the square.

Two bowls, one wide and shallow, one narrow and steep. Start the same distance from the bottom of each and take one pass at the same rate.

At the same distance from its minimum the steeper bowl has the larger derivative, so the same rate takes a larger step on it. A rate that creeps politely down the shallow bowl can leap clean across the steep one and land farther from the bottom than it started. A learning rate is safe or unsafe only relative to a curvature.

Take the bowl to be a quadratic in the distance from its minimum.

So every pass multiplies the remaining distance by the same fixed factor, and what the walk does is entirely a question of where that factor sits.

|1 − ηc| < 1
0 < η < 2/c

Shrinking needs the size of the factor below one, and solving that for η gives the bound. The walk arrives for any rate between zero and two over the curvature, and runs away above it.

The surface of section 5 has two directions, and on centred heights each has its own curvature.

c_level = 2
c_slope = 2·Var(x′) = 2 × 50/3 = 100/3

Each has its own factor, and the rate has to be safe for both. The two number lines below move together as η changes, and the slope’s marker reaches −1 first.

η = 2 / (100/3) = 0.06

The steepest direction sets the largest safe learning rate. The level direction would tolerate any rate below 1, and it never gets the chance, because the slope direction runs away at 0.06.

A rate safe for the steep direction is small for the shallow one. At η = 0.02 the two factors are

|1 − 0.02 × 2|       = 0.96
|1 − 0.02 × 100/3|   ≈ 0.333

so the slope error is cut to a third every pass and the level error is cut by four percent. The slope has thrown away two thirds of its error before the level has thrown away four percent of its, and after the first dozen passes the walk is entirely a walk in the level direction.

The distance panel on the dashboard in section 14 draws both errors on a log scale, where each is a straight line and the slope’s is far steeper. The 477 passes are the level’s doing, and nothing is wrong with the slope at all.

For a single direction with curvature c, there is a rate that removes all the remaining error in one step.

rate η = 1/c
remaining-error factor = 1 − ηc = 1 − (1/c)c = 0

With two different curvatures, one rate cannot do that for both. The best fixed rate must balance the two directions.

worst factor = max(|1 − ημ|, |1 − ηL|)
balance condition: 1 − ημ = −(1 − ηL)

η* = 2 / (L + μ)

for the three people:  η* = 2 / (2 + 100/3) ≈ 0.0566
worst factor there:    1 − 0.0566 × 2 ≈ 0.8868

The page has walked on centred heights throughout, and the reason can now be shown. Below are the same three people handed over three ways, with the loss surface and a walk at the same rate drawn for each.

On raw heights the two settings are an intercept at a height of zero and a slope, and they are strongly coupled. Rotating the line about the origin swings its height near 170 by hundreds of kilograms, so almost any change in slope has to be repaid by a change in intercept to keep the predictions where they were, and the contours are a valley tilted so steeply that its two curvatures are 0.00115 and 57,835. A rate of 0.02 runs away in four passes, and the largest safe rate is 0.0000346.

Centred, the level is the prediction at the mean input, rotating the line about the mean leaves that prediction untouched, and the two settings stop pulling against each other. The contours line up with the axes, the curvatures are 2 and 33.3, and the same rate arrives in 477 passes. Same fit, same loss of 2.0 at the optimum, a different parameterisation of it. Centring removes the coupling.

Centring does not make the two curvatures equal. The bowl is still seventeen times steeper along the slope than along the level, which is the whole of section 22. Scaling the centred height changes that.

zᵢ = (xᵢ − x̄) / sₓ

Dividing by the standard deviation changes the numerical spread of the input, and the slope’s curvature is twice the variance of the input, so it changes that curvature directly. Switch the playground to centred and scaled. Both curvatures are now 2, the contours are circles, and the slope is 2.449 per standard deviation instead of 0.6 per centimetre, which is the same line described in a different unit.

Set the rate to 0.5 and the walk lands on the optimum in one pass, because 1/c is the same for both directions and section 23’s compromise no longer has anything to compromise between.

Centring and scaling are related and distinct. Centring removes the coupling between the settings. Scaling evens out the curvature across them. Each helps on its own, and the feature scaling page does both routinely for reasons this page has now earned.

The two curvatures do two different jobs. The largest sets stability, since it decides the threshold. The smallest sets the late-stage speed, since its direction is the one still crawling when the others have arrived. Their ratio describes how uneven the surface is, and it has a name.

κ = L / μ

Near 1, every direction is curved alike and one rate serves all of them. Large, the surface is a narrow valley and any fixed rate is a poor compromise between crawling along it and bouncing off its walls. Centring and scaling took these three people from fifty million to one, and that is not a promise. They often improve the conditioning a great deal, and they do not always repair it, since features can be coupled in ways that a shift and a stretch per column cannot undo.

A walk can stop for four different reasons, and the reason is part of the result.

The verdicts in section 16’s table draw these lines exactly where they fall. At 0.07 and 0.1 the walk is doomed and has not yet overflowed, so it runs out of its 500 passes holding numbers that are large and useless, and the verdict is that the passes ran out. Only at 0.2 do the coefficients stop being finite inside the budget, and only then is the fit refused by name.

Non-finite arithmetic detects the wreck, not the beginning of the skid, which can be many passes earlier. A run should be read by its loss and gradient over time, which is the dashboard’s middle row, and not by whether it happened to crash.

The walk stops when no coefficient moved more than 10⁻⁸ in a whole pass. That is a movement tolerance, and a movement is the rate times the gradient.

Δθ = −η·∇L

So a tiny movement can mean the gradient is genuinely small, which is what the test is for. It can also mean the rate is extremely small, so that a large gradient produces a tiny step and the walk declares itself finished while standing halfway down the hill. And it depends on the scale of the parameters, since 10⁻⁸ is a different demand on a level of 66 than on a coefficient of 0.0004.