Learning Algorithms

Learning from experience

Think of a child learning to tell cats from dogs. Nobody hands over a rulebook: the child guesses and gets corrected. A machine learning algorithm does the same with data.

The lower chart is the performance measure plotted against the experience . With no examples the program can only guess, so accuracy sits at chance, 50 percent. A few examples give a noisy result, because each new draw gives a different dividing line. The solid curve averages 25 draws. It climbs and then flattens near 80 percent, because the two groups overlap and no straight line separates every point.

Mitchell (1997) defines it this way: a program learns from experience on tasks if its performance improves with .

• , the task: what the program is asked to do (Sections 1 to 3).
• , the performance measure: a number that says how well it does the task (Section 4).
• , the experience: the data it may learn from (Sections 5 to 7).

Learning is not the task. A walking robot's task is walking, and learning is one way to gain that ability.

Classification and images as vectors

The task starts with an example: a vector of features, which are numbers measured from something. Here , where is the number of features. In classification the program says which of categories an example belongs to, so its function is .

An image is the classic example. A gray five by five picture has 25 pixel brightnesses, written as one long vector. Paint the picture and watch the vector.

Classification gets harder when some measurements may be missing. A doctor may not be able to run every test, because many tests are expensive or invasive. The book suggests learning one probability distribution over all the variables, then classifying by marginalizing out the missing ones. With inputs there are classification functions, one for each set of missing inputs, but only one joint distribution has to be learned.

Drag the query point and switch the inputs on and off. The table gives the class probabilities that remain once the missing inputs are summed out. The same model answers every combination of available inputs.

Regression and structured output

In regression the program predicts a number from an input: a function . Only the output format differs from classification. Predicting the claim amount an insured person will make, or the future price of a security, are regression tasks. The demo uses one set of exam scores against hours studied, and fits it both ways.

Structured output tasks produce a vector, or another structure, whose entries are tightly related. Transcription, which turns a photo of text or a speech waveform into characters, is one. Machine translation, which turns a sentence into a sentence in another language, is another. So are parsing a sentence into a grammar tree and labeling every pixel of an aerial photo as road or not.

The output need not copy the structure of the input. Each pixel of the left grid decides from its own noisy score. On the right, each round replaces every score by the average over its 3 by 3 neighborhood, so isolated mistakes get outvoted. A few rounds usually remove most errors, but too many blur the edges of the road. For such outputs the entries should be predicted together.

Density estimation and the other tasks

Density estimation is the most general task. The learner outputs a function that scores how likely each example is. For continuous features is a density, and for discrete ones a mass function. Doing this well means learning where the examples cluster and where they are unlikely to occur.

Other tasks become computations on this density. Anomaly detection flags an example whose density is very low, such as a card payment unlike the owner's usual purchases. Synthesis draws new examples from it. Imputation fills a missing entry from , the distribution of that entry given the others. Often these computations are intractable, so density estimation does not always deliver them.

Denoising receives a corrupted example , made from a clean example by an unknown corruption process. The learner must predict the clean example, or more generally the distribution . The demo below is a toy: a moving average of a noisy curve.

The average removes some noise, but it also blurs the sharp parts. A learned denoiser faces the same trade-off, and it has to make that trade-off with in mind.

The performance measure

The second letter is , the performance measure: a number that says how well the program does its task. For classification the direct choice is the accuracy, the proportion correct. The error rate is the proportion wrong, which is the expected 0-1 loss: 0 for a correct output and 1 for an incorrect one.

Performance is measured on a test set that the learner does not see during training, because performance on new data is what matters once the model is deployed. Density estimation has no accuracy, so the book reports the average log-probability of the examples instead. Higher means more plausible. Try the Gaussian model below.

Some choices are subtle. For transcription, should the system be scored on whole sequences, or should it earn partial credit for each correct element? The demo compares three answers on the same output.

For regression the same kind of choice appears. Should the system be penalized more for frequent medium mistakes, or for rare very large ones? The book says the answer depends on the application. Move the sliders and watch the ranking of the two models change.

Some quantities are impractical to measure. In density estimation many good models only represent the distribution implicitly, so the probability of a point is intractable. Then one designs an alternative criterion that still matches the goal, or a good approximation to it. A measure that rewards the wrong behavior produces a program that does the wrong thing well.

The experience: datasets, clusters and the chain rule

The third letter is , the experience. An algorithm is unsupervised if it sees only features, and supervised if each example also has a label or target. The book's example is the Iris data set: 150 plants, four measurements each, and a species label. The demo uses a synthetic stand-in with the same shape and invented means, not Fisher's measurements.

Clustering is an unsupervised role: it divides a dataset into groups of similar examples. The book notes that the line between supervised and unsupervised learning is blurred, since many techniques serve both purposes.

The chain rule splits a joint distribution into one conditional per feature, so modeling becomes supervised problems. Equation 5.1 states it:

A supervised learner estimates , the probability of a target given the input. A joint distribution gives it directly, by dividing by the total over all targets (Equation 5.2):

A dataset is usually a design matrix with one example per row and one feature per column. Iris is a matrix with 150 rows and four columns, so its shape is . The demo below uses synthetic plants of the same shape.

A design matrix needs every example to be a vector of the same length. Photographs of different sizes break that rule. The book then describes the dataset as a set of elements, which does not assume equal sizes, and points to Section 9.7 and Chapter 10 for such data.

The book also names other settings. In semi-supervised learning some examples have targets and others do not. In multi-instance learning a whole collection carries one label. In reinforcement learning the data depend on the learner's own actions, a case the book leaves to other texts. The book stresses that there is no rigid taxonomy, and new structures can be designed for new applications.

Linear regression and its error

The book's first full learning algorithm predicts from with , using a weight vector with one number per feature. A positive weight pushes the prediction up as the feature grows, a negative weight pushes it down, and a zero weight has no effect.

The learner scores a weight vector by its mean squared error on the training set, , the average of the squared gaps between predictions and targets. Figure 5.1 rebuilds the book's example: ten points with one feature, and the line through the origin.

Performance on new data is measured on a held-out test set of examples, with design matrix and targets . Its mean squared error, , is given by Equation 5.4, which is zero exactly when every prediction equals its target. The book also writes it as a squared Euclidean distance, so the error grows as predictions move away from targets (Equation 5.5).

The normal equations

To make a learning algorithm, the weights must lower the test error without seeing the test set. The book's intuitive route is to minimize the training error , by setting its gradient with respect to to zero, the stationarity condition:

Writing out and taking its gradient keeps the factor 1/, which gives Equations 5.7 and 5.8:

Equation 5.12 gives the normal equations solution, a simple learning algorithm: one solve, with no step size and no repeated passes. This note is added here, not printed in the book: the inverse exists when the columns of are linearly independent, which needs at least as many examples as features.

The bias term

The term linear regression often refers to a slightly richer model with one more parameter, an intercept . Equation 5.3 is a straight line through the origin, and an intercept lets the line miss it:

The map from parameters to predictions is still linear, but from features to predictions it is now affine, so the line need not pass through the origin. The book notes that the same effect comes from appending an extra feature that is always 1. The word bias names the intercept, because the output is pulled towards when the input is zero. A statistical bias is different: an estimate's expected value differs from the true quantity.

What to take away

• A program learns when its performance on tasks improves with experience .
• An example is a feature vector. Classification, regression and density estimation differ in output.
• Accuracy and the error rate are 0-1 losses. Density estimation uses log-probability.
• Supervised learning estimates . The chain rule splits into supervised problems.
• A dataset is a design matrix , or a set when examples differ in size.
• Linear regression gives the weights from the normal equations.
• The bias adds an intercept, so the prediction becomes affine.

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.1 (pages 99–110), 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.