Section 0
Learning from labeled examples
How to use this pageClick any colored symbol for its meaning. Predict first, then read on.
x, y, n data θ, w, b, α coefficients σ, k, f, φ sigmoid, kernel, score ε, C, ν, σ step, settings J, ∇, G errors, gradients
Supervised learning is a stack of flashcards. Each card holds an input and an output .
Start with a straight line: class 1 on one side, class 0 on the other.
Place the line yourself
class 1 (circles)class 0 (squares)
Challenge +8 XPPlace your line so that 5 or fewer of the 60 points are on the wrong side (ringed).
Your eye is the search here. The four algorithms of this module replace it with a score for each line and a rule that finds the best one. Each answers the same question: what output goes with a new input?
- Logistic regression weighs the evidence with a linear score.
- The support vector machine draws a boundary set by a few critical examples.
- k-nearest neighbors looks up the closest flashcards and takes a vote.
- Decision trees ask a chain of yes or no questions.
Predict first. Which of the four uses a sigmoid to turn a linear score into a probability?
Probabilistic supervised learning
Most supervised algorithms estimate a conditional distribution . They choose a parametric family with adjustable numbers and fit it by maximum likelihood.
Linear regression is one such family, with a Gaussian output:
Click any coloured symbol to see what it means.
Read it as: given , the output is normal with mean and identity covariance .
From a number to a probability
A linear score can be any real number, but a probability cannot. The logistic sigmoid squashes the real line into (0, 1):
Click any coloured symbol to see what it means.
Click any coloured symbol to see what it means.
Predict first. The weight and the bias is 0. What does the curve of look like against the input?
The sigmoid is the standard definition (added here, the book assumes it). Its input is the score , and a score of 0 gives probability 0.5. The book calls the model logistic regression, a somewhat strange name since it is used for classification.
Sigmoid of a linear score
p(y=1) = σ(wx+b)raw score wx+berror of each example
Challenge +8 XPMake the curve a steep step: a weight of at least 2.5, with the point where the probability is 0.5 between −0.5 and 0.5.
The 14 examples sit at height 1 or 0. Set the weight to zero and the curve flattens at 0.5. A large weight makes a steep step.
Training: no closed form, so search
Logistic regression has no closed-form solution, so we minimize the negative log-likelihood (NLL) by gradient descent. For examples with labels , the NLL is (added here; the book names the method only):
Click any coloured symbol to see what it means.
Each example gives probability of class 1. A confident wrong prediction costs a lot, because the logarithm of a tiny probability is a large negative number.
Predict first. Example is already classified correctly with high confidence. How much does it move ?
Its factor is the error of example .
Click any coloured symbol to see what it means.
Going deeper: the gradient of the NLL
Added here, not printed in the book. Differentiate one term with respect to . The sigmoid has derivative , and this cancels the denominator of the logarithm. What remains is the predicted probability minus the label, times the input.
Each example pushes along its input by an amount proportional to its error, so examples that are already right add almost nothing. Gradient descent repeats the update with step size :
Click any coloured symbol to see what it means.
Gradient descent on the negative log-likelihood
class 1 (circles)class 0 (squares)
NLL J(θ), average over the examples
Challenge +8 XPOn the overlapping classes, choose the step size and run the descent. Bring the cost below 0.33 within 20 steps.
Too small a step makes the descent slow: at about 10−0.5 the cost is still near 0.35 after 20 steps. A step between about 1 and 3 settles quickly. A step near 25 overshoots, and the cost stays high.
Predict first. On the separable classes, what does the cost do after many steps?
On the separable classes the cost keeps falling and the weights keep growing. That is the demo's own result for this data, and the book does not discuss it.
The general recipeNothing here is special to labels. Fit any parametric family of conditional distributions by maximum likelihood. Logistic regression is one such family, with a Bernoulli output.
Section 2 · Book §5.7.2
Support vector machines
The support vector machine (SVM) is driven by the same linear score as logistic regression, . It reports only a class identity, with no probability.
Predict first. A new point gets the score . What does the SVM report?
It also chooses and differently: the separating line that stays farthest from the nearest examples on both sides. Those nearest examples are the support vectors. (The margin and the penalty are the standard textbook setting, not printed in the book.)
Writing the line in terms of the examples
The book rewrites the linear function so that appears only in dot products, one coefficient per example:
Click any coloured symbol to see what it means.
Here is the -th training example. Most coefficients end up at zero. Drag the test point to check both ways.
Two ways to compute the same score
boundary, w·x+b = 0margin, w·x+b = ±1
Circled points are the support vectors, the only non-zero coefficients. Equation 5.82 is an algebraic rewrite here, because the line is straight anyway.
Section 3 · Book §5.7.2
The kernel trick
Since appears only in dot products, replace by a feature function and the dot product by a kernel:
Click any coloured symbol to see what it means.
Predictions then use the kernel in place of the dot product:
Click any coloured symbol to see what it means.
This is nonlinear in but linear in and . Press the button to see one separating line in the lifted space.
Nonlinear in x, linear after the lift
class 1 (circles)class 0 (squares)lifted points φ(x) = (x, x²)
On the left no single threshold on separates the classes. On the right, the lift turns the same points into a curve in a plane, and a straight line splits it. A straight line in the lifted plane is an interval on the original axis.
The book illustrates the efficiency point with a non-negative integer and a feature vector of ones followed by infinitely many zeros. The dot product of two such vectors is the min kernel. The book notes that some infinite-dimensional spaces need other inner products; this module does not develop them.
Click any coloured symbol to see what it means.
Predict first. The book’s vector for has seven ones, and the vector for has four. How many positions do both have as ones?
The shorter run of ones sets the overlap, so the kernel is the smaller number. The demo's second panel is a squared dot product (added here).
A kernel is a dot product you never compute
The book’s min kernel
Squared dot product (added example)
The explicit route counts overlapping ones. The kernel route compares two numbers and never builds the vector. In the second panel both routes give the same number.
Why the trick is powerful
- Convex optimization. is fixed and only is optimized, so training is convex.
- Computational efficiency. can be far cheaper than two vectors, even when is infinite-dimensional.
Section 4 · Book §5.7.2
The Gaussian kernel and support vectors
The most commonly used kernel is the Gaussian kernel:
Click any coloured symbol to see what it means.
Predict first. Two inputs and are far apart. What is their kernel value?
The kernel evaluates the normal density at the difference . The width sets how fast the kernel falls off with distance. It is also called the radial basis function (RBF) kernel. The book reuses σ for the width, but here it is not the sigmoid.
Template matching
The book describes the Gaussian kernel as template matching. Each training example with label is a template for class . Drag the test point and watch the responses.
Templates voting on a new point
templates with coefficient > 0templates with coefficient < 0test point
kernel response k(x, x⁽ⁿ⁾) in [0,1]contribution α·k
Going deeper: the explicit form with the constant
Added here, not printed in the book. Implementations drop the normalizing constant of the density, because it only rescales the coefficients:
Click any coloured symbol to see what it means.
Two points at the same place give 1, and the value decays towards 0 as they move apart, at a speed set by .
With a small width each template claims only a small disc around itself. With a large width the discs overlap, and all templates vote on every point. The width is a hyperparameter that sets how local the model is.
Predict first. You shrink the width towards 0. What happens to the SVM?
Many linear models can be enhanced with the kernel trick, and the whole family is called kernel machines. Their drawback is cost: every training example adds a term to the decision function.
The SVM mitigates this by learning a mostly-zero coefficient vector, so only the support vectors need a kernel evaluation.
The demo trains a real SVM with soft-margin settings, using SMO, which stops at a stated tolerance. Change the data, kernel, width and penalty .
A kernel SVM, trained live
boundary f(x) = 0f(x) = ±1ring = support vector
On the ring a linear kernel reaches only about 65%, because no straight line separates a blob from the ring around it.
Challenge +8 XPOn the ring data with the Gaussian kernel, reach at least 96% accuracy on the 200 fresh points.
Shrink the width and the boundary hugs single points: at width 0.2 the demo makes 56 of 60 training examples support vectors (93%). The penalty moves the count up or down.
Section 5 · Book §5.7.3
k-nearest neighbors
The book has already used nearest neighbor regression. k-nearest neighbors (k-NN) is a family of techniques for classification and regression. It is non-parametric: it stores the training set and has no training stage.
For a test input , it finds the closest training inputs and averages their outputs:
Click any coloured symbol to see what it means.
Neighbors vote
class Aclass Bclass Cquery
(The book describes this in words, and the formula is added here.) The set holds the nearest examples.
Going deeper: one-hot codes as probabilities
Added here, not printed in the book. For a class , the code vector has a 1 in its class position and 0 everywhere else. Averaging the codes of the neighbors gives
Click any coloured symbol to see what it means.
which can be read as a probability distribution over the classes.
With the regions form a patchwork around single points. As grows, they smooth out. You choose ; it is not learned.
Predict first. With and a lot of training data, the book shows that 1-nearest neighbor with 0-1 loss converges to what?
High capacity, and what it costs
The book states a classical fact: with 0-1 loss, 1-nearest neighbor converges to double the Bayes error, the lowest error any classifier can reach. The extra error comes from breaking ties at random between equally distant neighbors.
The next demo uses a case computable exactly: one input in [0, 1], class 1 in the middle half, and each label flipped with probability . The Bayes error is , and the 1-NN error tends to (added here).
1-nearest neighbor against the Bayes error
1-NNk-NN, chosen kBayes error ν1-NN limit 2ν(1−ν)
The 1-NN curve settles near , above the Bayes line. A larger pulls it towards , because the vote averages out the label noise. The cost: every prediction compares the query with all stored examples.
A weakness: it cannot learn which feature matters
The book’s example has from an isotropic Gaussian, where only is relevant and the output equals it, . The 99 irrelevant features decide the nearest neighbor, so the output is essentially random.
Ninety-nine distractions
test pointsperfect prediction
The last slider scales before distances are measured. A weight above 1 repairs the prediction. k-NN cannot find that weight by itself.
Section 6 · Book §5.7.3
Decision trees
A decision tree (Breiman and colleagues, 1984, and its variants) splits the input space with axis-aligned cuts, one threshold on one feature per node. Each leaf maps its region to one output, so the function is piecewise constant.
Predict first. Each leaf of a decision tree outputs what?
Figure 5.7 of the book draws the tree as a diagram and as a partition of the plane. Each node has a binary identifier: the parent’s identifier plus a 0 for the left or top child, or a 1 for the right or bottom child. Grow your own tree below and click a node to see its region.
Grow a tree
class 1 (circles)class 0 (squares)
click a node to see its region
tree, trainingtree, testlogistic regression, test
Challenge +8 XPOn the diagonal boundary, reach at least 90% test accuracy with a maximum depth of 4 or less. A new sample may be easier, so draw one if the first is hard.
On the diagonal data the boundary is , which is not axis-aligned. The tree approximates it with a staircase. Logistic regression finds the diagonal with three numbers. On the ring the lesson reverses.
Going deeper: how the splits are chosen
Added here. The demo grows the tree greedily by Gini impurity, for a node with class-1 share :
Click any coloured symbol to see what it means.
Each node tries every feature and threshold and keeps the cut with the largest drop in impurity.
Predict first. Every cut of a tree uses one feature. What does a diagonal boundary need?
Capacity and size
Trees are usually regularized with a depth limit. The book’s figure caption adds that each leaf needs at least one training example.
The book judges k-NN and trees in balance: both have many limitations.
Section 7 · Wrap-up
The same data through four lenses
This final demo runs all four algorithms on one sample and scores them on the same 400 held-out points. The data are seeded random samples.
Four classifiers, one sample
class 1 (circles)class 0 (squares)
No algorithm wins everywhere. Logistic regression is excellent when a line is the right shape and cannot represent the ring at all. The kernel SVM handles the ring and the diagonal, at the price of choosing a width. Nearest neighbors pay with memory and prediction cost. The tree is cheap and readable.
The book ends with a historical note. Kernel machines are costly on large data sets (Section 5.9 of the book) and generalize poorly with generic kernels (Section 5.11). Hinton and colleagues showed in 2006 that a neural network could outperform an RBF-kernel SVM on MNIST.
Predict first. A new data set is a ring. Which choice is the poor one?
What to take away
- Probabilistic supervised learning fits by maximum likelihood.
- Logistic regression squashes a linear score with the sigmoid and is trained by gradient descent.
- Support vector machines output only a class, and can be written with dot products.
- The kernel trick replaces the dot product with a kernel, so the model is nonlinear in .
- k-nearest neighbors averages the closest examples, and its 1-NN error approaches double the Bayes error.
- Decision trees split space into axis-aligned regions, with a constant output per leaf.
Final quizCheck 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.7 (pages 140–146), 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.