Building a Machine Learning Algorithm

Section 1

The four-part recipe

Picture a dish: change one ingredient and you get another dish, with no new theory of cooking. A learning algorithm is built the same way. Nearly all deep learning algorithms, and many older ones, are one recipe with four slots, a dataset, a cost, a model and an optimizer.

How to use this page

Click any colored symbol, in an equation or in a sentence, and it explains itself. Then move the controls before you read the sentence below each demo.

Pick one option per slot

Dataset

Cost

Model

Optimizer

Each slot can be swapped, and the algorithm changes with it. The four slots are:

a dataset, the examples the learner may look at: inputs , with answers when they exist;
a cost , one number that says how bad the current model is on the data;
a model, a family of functions with adjustable numbers inside, such as the weights and the bias ;
an optimizer, the method that searches for weights with a small cost.

, data , coefficients the learner tunes cost and gradients , predictions and reconstructions , penalty and step size

Challenge +8 XP

Set the dataset to Inputs only, the cost to Reconstruction error and the model to Linear reconstruction, then choose Gradient descent or SGD. The readout must name the first PCA vector.

Some combinations break. Choose a Bernoulli cost with a linear model and the card says why. Those slots describe different problems.

Predict first. Keep the dataset, cost and model of linear regression. Change only the optimizer from the closed-form solve to gradient descent. What happens to the algorithm?

Going deeper: the same recipe for six familiar algorithms

The table fills the four slots for several algorithms. It groups the dataset with the cost, and the model with the optimizer. The first row is the book’s example. The other rows are added here for comparison and are not printed in this section.

Algorithm	Data and cost	Model and optimizer
Linear regression	, ; negative log-likelihood	Gaussian with linear mean; normal equations
Ridge regression	, ; negative log-likelihood plus weight decay	Gaussian with linear mean; closed form
Logistic regression	, ; negative log-likelihood	Bernoulli with sigmoid score; gradient descent
First PCA vector	only; reconstruction error	unit vector ; eigenvector or gradient
Neural network	, ; negative log-likelihood	layers of units; (stochastic) gradient descent
Decision tree, k-means	(and ); cost with flat regions	regions with constants; special-case procedure

Section 2

Linear regression and its optimizer

The book’s first example combines a dataset of inputs and answers, the cost of Equation 5.100, and a model. The model says that the answer is a bell curve around a linear score:

Click any coloured symbol to see what it means.

The cost is the average negative log-likelihood of the answers under that model, written as over the training pairs:

(5.100)

Click any coloured symbol to see what it means.

Gradient descent reaches the same answer by steps. Set the learning rate and the number of steps below, and watch the two lines. Drag a point to move the data.

Closed form against gradient descent

data (drag the points)closed formgradient descent after steps

Gradient descent steps

Learning rate

Setting the gradient to zero gives the normal equations. Stack a column of ones next to the inputs, so that the bias joins the weights as , and the solution is one formula with no loop and no learning rate. The book names the normal equations, and this formula is added here:

Predict first. Gradient descent starts at slope 0 and intercept 0. Now set the learning rate to 2.0 and run. What happens?

Challenge +8 XP

Raise the learning rate past the stability limit, then run 300 steps. The readout must say that gradient descent has diverged.

Below the stability limit, each step shrinks the error. Above it, each step overshoots by more than it gains, and the numbers grow.

Going deeper: the normal equations from the cost

Write the cost of Equation 5.100 for the bell curve model. Its negative log-likelihood per example is

so minimizing the cost is minimizing the average squared error. (Section 5.5 of the book makes this link through maximum likelihood.) The gradient with respect to the stacked weights must vanish at the minimum, which gives , which is the formula above when the matrix on the left is invertible.

Section 3

The cost: weight decay

Because the slots are independent, the cost can change without touching the data or the model. Add a penalty on large weights, with strength . This is weight decay, the regularization term of Equation 5.101:

(5.101)

Click any coloured symbol to see what it means.

The penalty does not look at the data. It prefers small weights, so polynomial curves are smoother. The demo fits a polynomial of degree to twelve noisy points. The fit uses a Legendre basis for numerical stability, so the penalty acts on the Legendre coefficients, not on the powers of .

The penalty tames a flexible model

training pointstrue curvefitted polynomialtraining errortest error

Polynomial degree

Weight decay

Predict first. The polynomial has degree 9 and no penalty, so its test error is large. Add a small penalty, λ = 0.0001. What happens to the test error?

Challenge +8 XP

At degree 9, find a λ that makes the test error at least 10 times smaller than with no penalty, while the training error stays below 0.05.

The penalty can be added to the cost without losing the closed form, because the gradient is still linear in the weights. The penalty only adds a term to the diagonal of the linear system.

Going deeper: the ridge equation

With the Gaussian cost of Equation 5.100 and the penalty of Equation 5.101, the gradient with respect to the stacked weights is , which is zero at the minimum. The bias is left out of the penalty, so the diagonal matrix \htmlClass{s-Dg c-ink}{\boldsymbol{D}} has ones for the weights and a zero for the bias. The terms in \htmlClass{s-wt c-acc}{\tilde{\boldsymbol{w}}} collect into the equation below. This derivation is added here and is not printed in the book.

The demo keeps one number for the strength. Its readout also gives the test error with no penalty, so you can see the ratio as you move the slider.

Section 4

The model: no closed form

Now change the model. Make the linear score , which is , pass through a sigmoid, so the output is a probability. Logistic regression is not in this section of the book. It is added here as the standard example of a model that has no closed-form solution:

The cost is the negative log-likelihood of a yes or no answer. Its gradient has a clean form: the prediction error times the input.

Predict first. All the weights start at zero, so the score is zero for every input. What probability does the model give to every point?

The color shows the probability for class 1 at each place. The boundary is where the score is zero, a straight line, because the score is linear. When the two classes overlap, the cost stops falling at a positive value.

Gradient descent on logistic regression

class 1class 0

A click on the plane adds a point of the chosen class.

Learning rate

Challenge +8 XP

From reset weights, train to a cost below 0.15 in 200 steps or fewer. The readout shows the steps and the cost.

Step through the derivation one line at a time. Each line is one rule.

The cost of one example. The bracket has two cases, answer 1 and answer 0.

Going deeper: why the cost may keep falling forever

If the two classes can be separated by a line, the cost can approach zero. The weights then grow without limit, because a larger scale makes each probability closer to 0 or 1. The cost has a lower bound, but the best weights may not exist. This remark is added here and is not printed in the book.

Section 5

The data: unsupervised learning

The dataset can hold inputs alone. Then the cost compares each input with its reconstruction, and the model is a direction. The book’s example is the first principal component (PCA vector). The model keeps a unit vector and reconstructs an input by projecting it onto that direction:

(5.102)

Click any coloured symbol to see what it means.

Predict first. The cloud of points is twice as long as it is wide. Along which direction is the reconstruction error smallest?

The number is the position of along . The point on the line through the origin is that number times . The cost is the average squared distance between each input and its reconstruction. The demo centers the cloud at the origin, because this form of reconstruction has no offset.

Find the direction with the smallest reconstruction error

datadirection reconstruction errorsbest direction (appears after your guess)

Direction angle (degrees)

Rotate the cloud (degrees)

Elongation of the cloud

Challenge +8 XP

Turn the direction by hand until the reconstruction cost is within 1 percent of its lowest value.

The cost curve over the angle has one valley, and its bottom is the direction of the long axis. The button runs gradient descent on the angle, a second optimizer for the same recipe.

Going deeper: why minimizing the error is maximizing the variance

For a unit vector the squared length of an input splits into the part along the direction and the part that is lost. For data centered at the origin, the average of the lost part is the cost, and the average of the kept part is the variance along the direction. So the two sum to the average squared length, which does not depend on the direction. This derivation is added here and is not printed in the book.

Section 6

Special-case optimizers

Decision trees and k-means look hand-designed. The book’s explanation is that their cost functions have flat regions. In a flat region, a small change in a parameter leaves the cost exactly the same, so a gradient-based optimizer sees a slope of zero and cannot tell which way to move.

The simplest tree is a stump: one threshold , which predicts class 1 above the threshold and class 0 below it. Its cost counts mistakes, so the cost is a staircase. A smooth substitute, the sigmoid cross-entropy, has a slope everywhere.

Predict first. Gradient descent starts at a threshold far to the left, where the mistake count does not change. Where does it go?

Where the slope is zero, gradient descent is blind

number of mistakes (0-1 cost)smooth substitute (sigmoid cross-entropy)

Threshold

Sharpness of the smooth substitute

Challenge +8 XP

Find the threshold with the fewest mistakes. The readout must show the minimum count, which you find by moving the slider.

The smooth valley sits near 0.34, and at that threshold the stump makes more mistakes than the best one. That is the price of the substitute. A special-case procedure can instead try every candidate split and keep the one with the fewest mistakes.

The book makes a wider point on pages 153 to 155. Some costs cannot be evaluated exactly, for computational reasons. The cost can still be minimized approximately by an iterative numerical optimizer, as long as its gradients can be approximated. This is why the recipe of Section 1 still applies to them.

Section 7

The recipe builder

Put the four slots together and train. Each choice below is one slot, and the readout names the algorithm you have built. The closed-form solve is available only when the model is linear in its weights and the cost is the Gaussian one.

Predict first. The Ring data has an inner disc and an outer ring. Use a linear model with the cross-entropy cost, trained by gradient descent. What accuracy do you expect?

Assemble the four parts and train

data (regression) or class 1 pointsfitted function or class 1 regionclass 0 region

1. Dataset

2. Model

3. Cost

4. Optimizer

Weight decay

Learning rate

SGD minibatch size

Two things to try. On Line with outliers, the squared error pulls the slope up, while switching to absolute error and training again lands nearer the true slope of 0.8. On Ring, the linear model stays near 50 percent, because both classes share one center and the start gives almost no push towards a boundary.

Challenge +8 XP

Choose the Ring data, then pick the model that can bend its boundary, and train until the accuracy reads all points correct.

What to take away

A learning algorithm combines a dataset, a cost, a model and an optimizer, and the four parts can be changed mostly independently.
Linear regression uses inputs and answers, the negative log-likelihood (5.100), a Gaussian linear model and the normal equations. Weight decay (5.101) changes only the cost, and the closed form survives.
A nonlinear model usually removes the closed form, so an iterative optimizer such as gradient descent is used.
Unsupervised learning uses inputs alone and a reconstruction cost (5.102).
Flat-regioned costs need special-case optimizers, which is why trees and k-means look hand-designed.

Final quiz

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 5.10 (pages 153–155), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.