Machine Learning and Deep Learning: An Interactive Introduction

Murphy (§1.1) defines machine learning as a set of methods that can automatically detect patterns in data, and then use the uncovered patterns to predict future data or to make other kinds of decisions under uncertainty. Instead of writing every rule by hand, you show the machine examples and let it find the rules.

Three kinds of learning

• Supervised learning learns a function that maps inputs x to outputs y from training data made of input–answer pairs. When y is a category (spam or legitimate email), the task is classification. When y is a real number (a house price, a temperature), it is regression.
• Unsupervised learning receives only inputs, with no answers, and finds structure in the data. Clustering similar items and reducing data to a few axes are the classic examples. Nothing says in advance what to look for, so the problem is less clearly defined than supervised learning.
• Reinforcement learning learns how to act from occasional rewards or punishments. Murphy gives the example of a baby learning to walk.

Each item of the input is a feature. The input can be a vector of numbers, such as a person’s height and weight, or a structured object such as an image, a sentence, or a time series (Murphy §1.1.1).

Machine learning deals with uncertainty. Data are noisy, and the same input often has no single right answer. That is why a model’s output is often a probability, such as “this email is spam with probability 0.93.”

A conditional probability \(p(A\mid B)\) is the probability of A given that B has happened. Bayes’ rule turns a probability that runs from cause to effect, p(effect | cause), into one that runs back from effect to cause, p(cause | effect).

Take Murphy’s example (§2.2.3.1). A woman in her 40s has a mammogram for breast cancer, and the result is positive. The test’s sensitivity is 80%, meaning that if she has cancer, the test is positive with probability 0.8. Is the chance that she has cancer therefore 80%? Many people answer yes, and they are wrong. The prior probability of breast cancer at this age is only 0.4%, and even without cancer the test is positive 10% of the time. Bayes’ rule gives an actual probability of about 3%. Ignoring the prior in this way is the base rate fallacy.

The normal distribution

The most widely used distribution for continuous values is the normal (Gaussian) distribution \(\mathcal{N}(x;\mu,\sigma^2)\). It is bell-shaped around the mean \(\mu\), and the standard deviation \(\sigma\) sets its spread. The linear regression of chapter 3 can be read as assuming “answer = straight line + Gaussian noise” (Goodfellow §3.9.3, 5.5.1).

Linear regression is the simplest model for predicting a real number y from an input x. With a single input, the prediction is a straight line \(\hat{y}=wx+b\), and the slope \(w\) and intercept \(b\) are the model’s parameters. Learning means finding the \(w\) and \(b\) that explain the data best.

The yardstick for “best” is the cost function. Linear regression usually uses the mean squared error (MSE), the average of the squared differences (residuals) between predictions and answers. Because the errors are squared, points that are far off are penalized much more heavily.

Linear regression has a closed-form solution, but most models do not. Instead we lower the cost step by step. The gradient \(\nabla f\) points in the direction in which the function rises most steeply. A small step in the opposite direction lowers the cost. This is gradient descent.

A learning rate that is too small converges slowly, and one that is too large can jump across the valley and make the cost grow (Goodfellow §4.3.1). When the cost surface is stretched in one direction, that is, when the Hessian has a large condition number, gradient descent zigzags between the valley walls and slows down.

With large datasets, computing the gradient over all the data at every step is expensive. Stochastic gradient descent (SGD) estimates the gradient from a small random batch of examples, a minibatch. The path wobbles, but each step is much cheaper, and SGD has become the workhorse of deep learning (Goodfellow §5.9).

The goal of machine learning is to do well on data the model has never seen, not to memorize the training data. This ability is generalization. The error on the training data is the training error, and the expected error on new data is the generalization error (test error).

The variety of functions a model can represent is its capacity. With too little capacity the model cannot even explain the training data, which is underfitting. With too much, it memorizes the noise in the training data and fails on new data, which is overfitting. Goodfellow’s figure 5.2 fits polynomials of degree 1, 2, and 9 to data generated from a quadratic. The line misses the curvature, and the degree-9 polynomial passes through every point but swings wildly between them.

Regularization is another way to rein in capacity. Weight decay adds the sum of squared weights to the cost and suppresses large coefficients the data do not require. With a suitable \(\lambda\), even a degree-9 polynomial recovers a shape close to the quadratic (Goodfellow fig. 5.5; ridge regression in Murphy §7.5).

Validation sets and cross-validation

If you choose hyperparameters such as the degree or \(\lambda\) using the test data, the test data are no longer “unseen.” So you set aside part of the training data as a validation set. Goodfellow (§5.3.1) notes that one typically trains on about 80 percent of the training data and validates on 20 percent. With little data, k-fold cross-validation splits the data into k parts and takes turns validating on each.

No single model is best for every problem. This is the no free lunch theorem (Murphy §1.4.9). Each problem needs its own choice of model and hyperparameters, made on validation data.

k-nearest neighbors (k-NN)

The simplest classifier looks at the K training points closest to a new point and picks the majority class among them (Murphy §1.4.2). It has no parameters to learn; the training data themselves are the model. Models like this are nonparametric. A small K lets single training points bend the boundary, and a large K smooths it.

Logistic regression

Logistic regression feeds the linear output \(\mathbf{w}^{\top}\mathbf{x}+b\) into the sigmoid function \(\sigma(z)=1/(1+e^{-z})\), turning it into a probability between 0 and 1. Despite its name, it is a classification model. The decision boundary is where \(p(y=1\mid\mathbf{x})=0.5\), the line \(\mathbf{w}^{\top}\mathbf{x}+b=0\) (Murphy §8.2).

Its cost function is the cross-entropy (negative log-likelihood), the average negative log of the probability given to the correct class. Assigning high probability to the right answer gives a small cost; assigning it low probability makes the cost climb steeply. There is no closed-form solution like the normal equations, so it is solved by gradient descent (Murphy §8.3, Goodfellow §5.7.1).

Here is Goodfellow’s example (§11.1). Suppose we build a test for a rare disease that affects one person in a million. A classifier that always answers “no disease” scores 99.9999 percent accuracy. A model can have very high accuracy and still be useless.

So we look at the positive class separately. Precision is the fraction of the model’s positive calls that are truly positive, and recall is the fraction of true positives that the model finds. Their harmonic mean, the F-score, combines the two. Precision is the same quantity as the posterior p(disease | positive) computed with Bayes’ rule in chapter 2.

A classifier usually outputs a score or probability and reports a positive when that value exceeds a threshold. Lowering the threshold finds more cases (higher recall) but raises more false alarms (lower precision), and raising it does the opposite. The precision–recall curve (PR curve), traced as the threshold moves, shows this trade-off. Which kind of error costs more depends on the problem (Murphy §5.7.2).

k-means clustering

k-means splits the data into K groups. After placing K centers, it alternates two steps: assign each point to the group of its nearest center, then move each center to the mean of its group’s points. It stops when no assignment changes (Goodfellow §5.8.2, Murphy algorithm 11.1).

Each iteration reduces the sum of squared distances from points to their centers (the distortion), but the answer it reaches is not guaranteed to be the best one. The result depends on where the centers start. Choosing K is hard too, because the distortion keeps falling as K grows. Murphy (§11.4.2.5) presents k-means as a simplified form of the EM algorithm for Gaussian mixture models.

Principal components analysis (PCA)

PCA summarizes data with fewer axes. It finds the axis that loses the least information (the reconstruction error) when the data are projected onto it and mapped back. That axis is also the direction in which the projected data have the largest variance, the eigenvector of the covariance matrix with the largest eigenvalue (Goodfellow §2.12, Murphy §12.2.1). The new coordinates PCA produces are uncorrelated with one another (Goodfellow §5.8.1).

The smallest problem a linear model cannot solve is XOR, which outputs 1 exactly when one of its two inputs is 1. Goodfellow (§6.1) fits a linear model to the four points by least squares and gets \(w=0\), \(b=0.5\), an answer of 0.5 for every input. The effect of \(x_2\) must flip depending on whether \(x_1\) is 0 or 1, but a linear model can give \(x_2\) only one coefficient.

The fix is a hidden layer that turns the input into a new representation. The hidden layer computes \(\mathbf{h}=g(W^{\top}\mathbf{x}+\mathbf{c})\), and the output layer applies a linear model on top of \(\mathbf{h}\), \(y=\mathbf{w}^{\top}\mathbf{h}+b\). Here \(g\) is the activation function. Without \(g\), any stack of layers is still one linear function, so the extra layers buy nothing. The default recommendation today is the ReLU, \(g(z)=\max(0,z)\).

Universal approximation and depth

The universal approximation theorem says that a network with even a single hidden layer can approximate a continuous function as accurately as desired, given enough hidden units (Goodfellow §6.4.1). Goodfellow adds that the layer may be infeasibly large and may fail to learn and generalize correctly. In many cases, deeper models represent the same function with fewer units and reduce generalization error.

Gradient descent needs the gradient of the cost with respect to every parameter. A neural network is a composition of many functions, so the gradient comes from the chain rule of calculus: if \(y=g(x),\ z=f(y)\), then \(\dfrac{dz}{dx}=\dfrac{dz}{dy}\dfrac{dy}{dx}\) (Goodfellow eq. 6.44).

It helps to draw the computation as a computational graph, with one node per operation. The forward pass computes values from the inputs toward the output, and back-propagation runs from the output back toward the inputs, computing the gradient at each node. Back-propagation stores intermediate results and reuses them, which avoids recomputing the same subexpressions over and over (Goodfellow §6.5).

Hand-written back-propagation code is easy to get wrong. Goodfellow (§11.5) recommends comparing back-propagated derivatives with numerical derivatives computed by finite differences. The experiment below shows that comparison.

Vanishing and exploding gradients

In a deep network the chain-rule product gets long. If each layer multiplies by a value below 1, the gradient shrinks exponentially (vanishes), and if each multiplies by a value above 1, it grows exponentially (explodes) (Goodfellow §8.2.5). The sigmoid saturates over much of its domain, where its gradient is nearly zero, and its derivative never exceeds 0.25. That is why it is rarely used in the hidden layers of deep networks (Goodfellow §6.3.2).

Momentum and Adam

In a long, narrow valley, plain gradient descent zigzags slowly downhill. Momentum accumulates the direction of past steps in a velocity v. It speeds up along consistent directions, and directions that keep reversing cancel out. The update is \(\mathbf{v}\leftarrow\alpha\mathbf{v}-\epsilon\nabla J,\ \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}+\mathbf{v}\), and common values of \(\alpha\) are 0.5, 0.9, and 0.99 (Goodfellow §8.3.2).

Adam is an adaptive method that sets a separate learning rate for each parameter. It tracks both the mean of the gradient (the first moment) and the mean of its square (the second moment). The suggested defaults in Goodfellow’s algorithm 8.7 are a step size of 0.001, decay rates \(\rho_1=0.9\) and \(\rho_2=0.999\), and a stabilizing constant of \(10^{-8}\) (§8.5.3). It is fairly robust to its hyperparameters and widely used.

Early stopping and dropout

Train a large network for long enough and the training loss keeps falling while the validation loss eventually starts to rise again. Goodfellow’s figure 7.3 shows this asymmetric U-shaped curve. Early stopping saves the parameters from the point where the validation loss was lowest and returns them as the result (§7.8). It is the most commonly used form of regularization.

Dropout randomly switches off some neurons at every training step. Typically an input unit is kept with probability 0.8 and a hidden unit with probability 0.5 (§7.12). The network can no longer rely on any particular neuron, and the effect resembles training an ensemble of many smaller networks. At evaluation time all neurons are on.

An image is data laid out on a grid of pixels. Convolution slides a small grid of weights, the kernel, across the image and sums the products of the kernel and the pixels it covers. The result is a feature map. Mathematical convolution flips the kernel, but most machine learning libraries implement the related cross-correlation, without the flip, and call it convolution (Goodfellow §9.1).

Goodfellow (§9.2) names three ideas behind convolution: sparse interactions, where each output connects to a small region of the input; parameter sharing, where the same kernel is reused at every position; and equivariance to translation, where shifting the input shifts the output by the same amount. In figure 9.6, finding the vertical edges of a 280 × 320 image takes a kernel with just two elements. Writing the same transformation as a matrix multiplication would need over eight billion matrix entries.

A typical convolutional layer has three stages: several convolutions in parallel, a nonlinearity such as the ReLU (the detector stage), and pooling (§9.3). Max pooling keeps only the largest value in each neighborhood, so the output barely changes when the input shifts slightly.

Ordered data such as sentences, speech, and time series come in many lengths. A recurrent neural network (RNN) reuses the same weights at every time step and carries a summary of everything it has seen so far in its hidden state \(\mathbf{h}\), passing it on to the next step. Unfolded along time, it looks like a deep network with one layer per time step (Goodfellow §10.1).

The problem of long-term dependencies

An RNN composes the same function again and again, once per time step. Gradients arriving from the distant past therefore tend to vanish, as in chapter 10, and occasionally explode (Goodfellow §10.7). Dropping the nonlinearity and simplifying to \(\mathbf{h}^{(t)}=W^{\top}\mathbf{h}^{(t-1)}\), the influence after \(t\) steps shrinks or grows with the eigenvalues of \(W\) raised to the power \(t\). The LSTM greatly eased this problem by learning, through input, forget, and output gates, how much information to keep (§10.10).

The fixed-length-vector bottleneck

An encoder–decoder RNN for translation compresses the whole source sentence into one fixed-length vector and generates the translation from that vector. Bahdanau et al. (2015) conjectured that this fixed-length vector is a bottleneck. They let the decoder, each time it produces a word, softly search the source sentence for the relevant parts and take a weighted average of them. This is attention. In Goodfellow’s words (§12.4.5.1), the model reads the whole sentence to get the gist and then produces the translated words one at a time, each time focusing on a different part of the input.

Vaswani et al. (2017) went one step further with the Transformer, which processes sentences with attention alone and no recurrence. A recurrent layer must compute its time steps in order, but self-attention computes every position at once. The path between two distant words is \(O(n)\) steps long in an RNN but \(O(1)\) in self-attention (Vaswani et al., table 1).

The Transformer is an encoder–decoder model built from attention alone, with no recurrence and no convolution. The encoder stacks six identical layers (\(N=6\)), each made of multi-head self-attention followed by a position-wise feed-forward network. The decoder also has six layers, plus one more attention sub-layer that looks at the encoder’s output. Each sub-layer is wrapped in a residual connection and layer normalization, so its output is \(\mathrm{LayerNorm}(x+\mathrm{Sublayer}(x))\), and every layer outputs vectors of dimension \(d_{\text{model}}=512\) (Vaswani et al. §3.1).

Queries, keys, and values

Attention takes one query and a set of key–value pairs and returns a weighted sum of the values. The weights depend on how well the query matches each key. In a library, the query is the topic you are looking for, the keys are the titles on the spines, and the values are the contents of the books. The Transformer divides the dot product of query and key by \(\sqrt{d_k}\) and applies a softmax. This is scaled dot-product attention.

Why divide by \(\sqrt{d_k}\)?

If the components of the query and key are independent with mean 0 and variance 1, their dot product has mean 0 and variance \(d_k\). With large \(d_k\), the dot products spread far apart and the softmax gives almost all of the weight to the largest one. In that region the softmax has extremely small gradients and learning stalls. Dividing by \(\sqrt{d_k}\) brings the variance back to 1 (Vaswani et al. §3.2.1, footnote 4).

Multi-head attention and masking

A single attention function blurs several relationships into one average. The Transformer instead projects the queries, keys, and values \(h\) times with different learned matrices, computes attention for each projection, concatenates the results, and projects them once more. This is multi-head attention. The original paper uses \(h=8\) heads with \(d_k=d_v=512/8=64\) each. Because each head is smaller, the total computational cost is similar to that of a single head with full dimensionality (§3.2.2). Like the two heads of experiment 14-1, different heads can attend to different relationships.

The decoder produces the translation one word at a time, so position \(i\) must not peek at later words. The decoder’s self-attention therefore sets the scores of later positions to \(-\infty\) before the softmax, which makes their weights zero. This mask, together with shifting the output embeddings by one position, ensures that the prediction for position \(i\) depends only on the words before it (§3.1, 3.2.3).

Positional encoding

Attention treats the words like a set, so on its own it cannot tell their order. The Transformer therefore adds a positional encoding of the same dimension to each word embedding. The original paper uses sines and cosines with a different frequency in each dimension, with wavelengths forming a geometric progression from \(2\pi\) to \(10000\cdot 2\pi\). The authors expected this to make relative positions easy to learn and to extend to sentences longer than those seen in training. Learned positional embeddings performed nearly the same (§3.5).

The feed-forward layer and model size

After attention comes a two-layer network, \(\mathrm{FFN}(x)=\max(0,\,xW_1+b_1)W_2+b_2\), applied to each position separately and identically. Its inner dimension is \(d_{\text{ff}}=2048\) (§3.3). Words become vectors through learned embeddings, and the two embedding layers share one weight matrix with the linear transformation just before the softmax (§3.4).

The paper’s base model has 65 million parameters and trained for 100,000 steps, about 12 hours, on eight P100 GPUs. The big model has 213 million parameters and trained for 3.5 days. On WMT 2014 English-to-German translation, the big model reached 28.4 BLEU, more than 2.0 BLEU above the best previously reported models, including ensembles (§5.2, 6.1, tables 2–3).

After the Transformer

• BERT (Devlin et al. 2019) pre-trains a Transformer encoder on bidirectional context, then fine-tunes it for each task.
• GPT (Radford et al. 2018) generatively pre-trains a 12-layer masked Transformer decoder on unlabeled text, then fine-tunes it. It is the starting point of today’s large language models.
• The Vision Transformer (Dosovitskiy et al. 2021) cuts an image into 16×16 patches and feeds them in like words, showing that a pure Transformer can classify images very well.
• Autoencoders and representation learning (Goodfellow ch. 14–15), deep generative models (ch. 20), and the probabilistic view of models (Murphy ch. 5, 10, 11, 15) are good next topics.

This table matches the chapters of this guide to the chapters and sections of the two textbooks. Both textbooks predate the Transformer (2017), so chapters 13–14 also rest on the papers listed below.

Textbooks

• Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. MIT Press.
• Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.

Papers

• Bahdanau, D., Cho, K., & Bengio, Y. (2015). Neural machine translation by jointly learning to align and translate. ICLR. arXiv:1409.0473
• Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention is all you need. NeurIPS. arXiv:1706.03762
• Radford, A., Narasimhan, K., Salimans, T., & Sutskever, I. (2018). Improving language understanding by generative pre-training. OpenAI. PDF
• Devlin, J., Chang, M.-W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of deep bidirectional transformers for language understanding. NAACL. arXiv:1810.04805
• Dosovitskiy, A., et al. (2021). An image is worth 16×16 words: Transformers for image recognition at scale. ICLR. arXiv:2010.11929