Equation sheet

Key Equations and Algorithms

The key equations and algorithms of the masterclass, collected unit by unit. Each one is derived or motivated in its unit, with a worked example small enough for pencil and paper.

Artificial intelligence runs on a small number of equations, and most of them are the three ideas of Unit 1 in different clothes: a dot product, a probability, and a gradient. The weighted sum inside a neuron is a dot product, and so is the score between a query and a key inside a transformer. The loss that a language model minimizes when it predicts the next token is the cross-entropy that logistic regression minimizes in Unit 5, taken over a vocabulary of tens of thousands of tokens instead of two labels. The update that trains every one of these models is the same step downhill, a parameter minus a learning rate times a gradient. This page collects the equations and the algorithms in the order of the units, so that you can see on one screen how the loss of Unit 4 becomes the loss of Unit 13.

Each card states a result as the Key Equation box of its unit does: one displayed equation, or one numbered list of steps for an algorithm such as A*, backpropagation, or Q-learning, followed by a sentence on what the symbols mean and when the result applies. The notation is the same on every card, with bold lower case for vectors, bold upper case for matrices, and the parameters of a model always written as one symbol. The page grows as units are published, so an equation you cannot find yet belongs to a unit that is still to come.

The AI Researcher's Toolkit

The dot product and the length of a vector

\[ \mathbf{w}\cdot\mathbf{x} = \sum_{j=1}^{d} w_j x_j = w_1 x_1 + w_2 x_2 + \cdots + w_d x_d , \qquad \|\mathbf{x}\| = \sqrt{\mathbf{x}\cdot\mathbf{x}} = \sqrt{x_1^2 + x_2^2 + \cdots + x_d^2} \] The dot product of two vectors of the same dimension \(d\) is the sum of the products of corresponding components, a single number. The length (or norm) of a vector is the square root of its dot product with itself. The dot product also equals \(\|\mathbf{w}\|\,\|\mathbf{x}\|\cos\theta\), where \(\theta\) is the angle between the two vectors, so it is largest when they point the same way and zero when they are at right angles.

Bayes’ rule

\[ P(A \mid B) = \frac{P(B \mid A)\,P(A)}{P(B)} , \qquad P(B) = P(B \mid A)\,P(A) + P(B \mid \text{not } A)\,P(\text{not } A) \] \(P(A)\) is the prior probability of \(A\) before the evidence \(B\) is seen, \(P(B \mid A)\) is the likelihood of the evidence if \(A\) is true, and \(P(A \mid B)\) is the posterior probability of \(A\) after the evidence. The rule holds for any two events with \(P(B) > 0\), and it is the correct way to update a belief on evidence.

Expectation

\[ \mathbb{E}[X] = \sum_{x} x\,P(X = x) \] The expectation of a discrete random variable \(X\) is the probability-weighted sum of its values. For a function \(g\) of the variable, \(\mathbb{E}[g(X)] = \sum_x g(x)\,P(X = x)\). The expectation of a sum of random variables is the sum of their expectations, whether or not they are independent.

The derivatives the units use

\[ \frac{\dd}{\dd x}\,x^n = n\,x^{n-1} , \qquad \frac{\dd}{\dd x}\,e^x = e^x , \qquad \frac{\dd}{\dd x}\,\log x = \frac{1}{x} \] The derivative of a power lowers the exponent by one and multiplies by the old exponent; the exponential function is its own derivative; the natural logarithm has the derivative \(1/x\) for \(x > 0\). A constant factor stays in front, \((c\,f)' = c\,f'\), the derivative of a sum is the sum of the derivatives, \((f + g)' = f' + g'\), and the derivative of a constant is zero.

The gradient and the downhill step

\[ \nabla f = \left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_d}\right) , \qquad x \leftarrow x - \eta\,f'(x) \quad\text{or, for several variables,}\quad \mathbf{x} \leftarrow \mathbf{x} - \eta\,\nabla f(\mathbf{x}) \] The gradient \(\nabla f\) of a function of \(d\) variables is the vector of its partial derivatives, and it points in the direction in which \(f\) increases fastest. A step of \(\eta\) times the gradient, taken against the gradient, decreases \(f\) when \(\eta\) is small enough. The number \(\eta\) is the learning rate, and the arrow means that the new value replaces the old one. Unit 4 writes the same step for the parameters \(\boldsymbol{\theta}\) of a model and a real loss \(L\) as \(\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\nabla_{\boldsymbol{\theta}} L\).

Search and Planning

Breadth-first search

  1. Put the initial state into the frontier and into the list of reached states.
  2. Take the node that entered the frontier earliest. If it is a goal state, return the path from the root to it.
  3. Generate its children by applying every action. Add each child that is not yet in the list of reached states to the end of the frontier and to the list.
  4. If the frontier is empty, there is no solution; otherwise go back to step 2.

Breadth-first search finds the solution with the fewest actions, because it examines every path of \(d\) actions before any path of \(d + 1\) actions. When all actions cost the same, that solution is also the cheapest.

The cost of exhaustive search

\[ \text{nodes examined} = O(b^d), \qquad \text{for example } b^d = 35^{10} \approx 2.8\times10^{15} \] A search without knowledge of the goal examines a number of nodes that grows exponentially with the depth \(d\) of the solution, with the branching factor \(b\) as the base. Breadth-first and uniform cost search also hold about \(b^d\) nodes in memory at once; depth-first search holds about \(b\,m\), with \(m\) the length of the longest path.

The A* algorithm

  1. Put the initial state into the frontier with \(g = 0\) and \(f = h\).
  2. Take the node \(n\) with the smallest \(f(n) = g(n) + h(n)\) from the frontier. If it is a goal state, return the path to it.
  3. For every child \(n'\) of \(n\) with action cost \(c(n, n')\), compute \(g(n') = g(n) + c(n, n')\). If \(n'\) has not been reached before, or if the new \(g(n')\) is smaller than the one recorded, record it with \(f(n') = g(n') + h(n')\) and put \(n'\) into the frontier.
  4. If the frontier is empty, there is no solution; otherwise go back to step 2.

\(g(n)\) is the cost of the path found so far from the initial state to \(n\), and \(h(n)\) is the heuristic estimate of the cheapest cost from \(n\) to a goal. With an admissible and consistent heuristic, the first path to the goal that A* returns is a cheapest path.

Minimax with alpha-beta pruning

  1. Search the game tree depth first to a fixed depth. At a leaf, return the value of the evaluation function.
  2. At a Max node, return the largest value among the children; at a Min node, the smallest.
  3. Carry along two bounds: \(\alpha\), the best value Max is already sure of on the path from the root, and \(\beta\), the best value Min is already sure of. Update \(\alpha\) at Max nodes and \(\beta\) at Min nodes as the children return.
  4. As soon as \(\alpha \ge \beta\) at a node, stop examining its remaining children: the opponent higher up will never allow this node to be reached.

Alpha-beta pruning returns exactly the move and the value that minimax returns. With the best move examined first at every node it searches about \(b^{d/2}\) leaves instead of \(b^d\), which doubles the depth that a given amount of time buys, since depth \(2d\) then costs about what depth \(d\) cost before.

Reasoning under Uncertainty

Conditional independence

\[ P(A \mid B, C) = P(A \mid C) \qquad\text{or equivalently}\qquad P(A, B \mid C) = P(A \mid C)\,P(B \mid C) \] The variables \(A\) and \(B\) are conditionally independent given \(C\) when the probability of \(A\) no longer changes with \(B\) once \(C\) is known; the comma in \(P(A \mid B, C)\) means that both \(B\) and \(C\) are known. Plain independence, \(P(A, B) = P(A)\,P(B)\), is the special case with no conditioning variable, and the two are different properties. Two variables can be dependent and still conditionally independent given a third, and the other way round.

The chain rule of probability and the factorization of a Bayesian network

\begin{align*} P(x_1, x_2, \ldots, x_n) &= P(x_1)\,P(x_2 \mid x_1)\,P(x_3 \mid x_1, x_2) \cdots P(x_n \mid x_1, \ldots, x_{n-1}) \\ &= \prod_{i=1}^{n} P\big(x_i \mid \mathrm{parents}(x_i)\big) \end{align*} The first equality is the chain rule and holds for any variables in any order. The second holds in a Bayesian network, where \(\mathrm{parents}(x_i)\) are the variables with arrows into \(x_i\), and it says that the joint probability of any complete assignment, that is, of one chosen value for every variable, is the product of one entry from each conditional probability table.

The naive Bayes decision rule with Laplace smoothing

\[ \hat{c} = \arg\max_{c}\; P(c)\prod_{j=1}^{V} P(w_j \mid c)^{x_j} = \arg\max_{c}\;\Big[\log P(c) + \sum_{j=1}^{V} x_j \log P(w_j \mid c)\Big], \qquad P(w_j \mid c) = \frac{n_{j,c} + 1}{n_c + V} \] An input is the vector of counts \(\mathbf{x} = (x_1, \ldots, x_V)\) of the \(V\) vocabulary words; \(n_{j,c}\) is how often word \(j\) occurred in the training emails of class \(c\) and \(n_c\) the total number of word occurrences in that class. A word that occurs \(x_j\) times contributes its probability \(x_j\) times, which is what the exponent says, and a word that does not occur has \(x_j = 0\) and contributes a factor of one. The rule chooses the class with the largest product, or, which gives the same answer, with the largest sum of logarithms.

Running a Markov chain

\[ \mathbf{p}_{t+1} = \mathbf{p}_t\,\mathbf{T} , \qquad \mathbf{p}_{t} = \mathbf{p}_0\,\mathbf{T}^{t} \] \(\mathbf{p}_t\) is the row vector of state probabilities after \(t\) steps and \(\mathbf{T}\) the transition matrix, whose entry \(T_{ij}\) is the probability of a step from state \(i\) to state \(j\); \(\mathbf{T}^{t}\) is the matrix multiplied by itself \(t\) times, one factor for each step. A distribution \(\boldsymbol{\pi}\) with \(\boldsymbol{\pi}\,\mathbf{T} = \boldsymbol{\pi}\) is a stationary distribution of the chain; for a chain with finitely many states in which every state can reach every other and no cycle forces a fixed rhythm, there is exactly one, and \(\mathbf{p}_t\) approaches it from any start.

Learning from Data

The mean squared error

\[ L(w, b) = \frac{1}{N}\sum_{i=1}^{N}\bigl(y_i - wx_i - b\bigr)^2 \] The loss of the line with slope \(w\) and intercept \(b\) on a training set of \(N\) examples \((x_i, y_i)\). It is zero only when the line passes through every point, and its square root has the units of \(y\).

The least squares line

\[ w = \frac{\sum_{i=1}^{N}(x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^{N}(x_i - \bar{x})^2} , \qquad b = \bar{y} - w\,\bar{x} \] The slope and intercept that minimize the mean squared error, where \(\bar{x}\) and \(\bar{y}\) are the means of the inputs and the targets. The numerator of \(w\) divided by \(N\) is the covariance of \(x\) and \(y\), which measures how much the two move together, and the denominator divided by \(N\) is the variance of \(x\), so the slope is their ratio.

The normal equations

\[ \mathbf{X}^{\top}\mathbf{X}\,\mathbf{w} = \mathbf{X}^{\top}\mathbf{y} \qquad\Longleftrightarrow\qquad \mathbf{w} = \bigl(\mathbf{X}^{\top}\mathbf{X}\bigr)^{-1}\mathbf{X}^{\top}\mathbf{y} \] The least squares weights for linear regression with any number of features, where \(\mathbf{X}\) holds one feature vector per row (with a constant feature 1 for the intercept) and \(\mathbf{y}\) the targets. \(\mathbf{X}^{\top}\), the transpose of \(\mathbf{X}\), is the same table with rows and columns swapped, so that \(\mathbf{X}^{\top}\mathbf{X}\) is a square table of the dot products between the feature columns. The first form is a system of \(d + 1\) linear equations in the \(d + 1\) weights, and the second form, with the inverse \((\mathbf{X}^{\top}\mathbf{X})^{-1}\), is the matrix way of writing its solution, which applies when that system has exactly one solution.

The gradient descent update

\[ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\nabla_{\boldsymbol{\theta}} L \] All parameters \(\boldsymbol{\theta}\) of a model are moved at once by a small step against the gradient of the loss \(L\) on the training data, and the step is repeated until the loss stops falling. The learning rate \(\eta\), a positive number chosen by the person who trains, sets the size of the step. For the line, \(\boldsymbol{\theta} = (w, b)\) and the gradient has the two components \(\partial L/\partial w\) and \(\partial L/\partial b\).

Ridge regression

\[ L_{\mathrm{ridge}}(\mathbf{w}, b) = \frac{1}{N}\sum_{i=1}^{N}\bigl(y_i - \mathbf{w}\cdot\mathbf{x}_i - b\bigr)^2 + \lambda\,\|\mathbf{w}\|^2 \] The mean squared error plus a penalty on the squared length of the weight vector, \(\|\mathbf{w}\|^2 = \sum_j w_j^2\). The regularization strength \(\lambda \ge 0\) sets how much a large weight costs; \(\lambda = 0\) is ordinary least squares. The intercept \(b\) is not penalized, because shifting all predictions up or down is not a sign of overfitting.

Classifiers and Decision Trees

Logistic regression

\[ P(y = 1 \mid \mathbf{x}) = \sigma(\mathbf{w}\cdot\mathbf{x} + b) = \frac{1}{1 + e^{-(\mathbf{w}\cdot\mathbf{x} + b)}} \] The model’s output is the probability that the input \(\mathbf{x}\) belongs to the category \(y = 1\), with the weight vector \(\mathbf{w}\) and the bias \(b\) as parameters. It predicts \(y = 1\) when this probability is at least \(0.5\), which is the case exactly when \(\mathbf{w}\cdot\mathbf{x} + b \geq 0\).

The cross-entropy loss and its gradient

\[ \ell = -\bigl[y\log\hat{y} + (1 - y)\log(1 - \hat{y})\bigr] , \qquad L(\mathbf{w}, b) = \frac{1}{N}\sum_{i=1}^{N}\ell_i , \qquad \nabla_{\mathbf{w}}\,\ell = (\hat{y} - y)\,\mathbf{x} , \quad \frac{\partial\ell}{\partial b} = \hat{y} - y \] The loss of one example with label \(y\) and predicted probability \(\hat{y} = \sigma(\mathbf{w}\cdot\mathbf{x} + b)\), in nats because the logarithm is natural (the nat is the unit of information that goes with the natural logarithm, as the bit, which Section 3 uses, goes with the logarithm to base 2); it is zero for a confident correct prediction and grows without bound as the prediction becomes confidently wrong. The training loss \(L\) is the average over the \(N\) examples, and its gradient is the average of the gradients of the single examples.

The softmax function

\[ \mathrm{softmax}(\mathbf{z})_k = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}} \qquad\text{and}\qquad \ell = -\log\hat{y}_{c} \] The softmax turns any vector \(\mathbf{z}\) of \(K\) scores into \(K\) positive numbers that add up to one, with the largest score getting the largest probability. The loss of an example whose true category is \(c\) is the negative logarithm of the probability \(\hat{y}_c\) the model gave to that category. For \(K = 2\) the softmax is the sigmoid of the difference of the two scores, because dividing the numerator and the denominator of \(e^{z_1}/(e^{z_1} + e^{z_2})\) by \(e^{z_1}\) gives \(1/(1 + e^{-(z_1 - z_2)})\), so logistic regression is the special case.

Entropy and information gain

\[ H = -\sum_{k} p_k\log_2 p_k , \qquad \mathrm{Gain} = H(\text{parent}) - \sum_{\text{children } c} \frac{N_c}{N}\,H(c) \] The entropy \(H\) of a set of labels in which a fraction \(p_k\) of the examples belongs to category \(k\), in bits, where the logarithm to base 2 is the ordinary logarithm divided by \(\log 2\) and \(0\log_2 0 = 0\) by convention, so that an absent category contributes nothing; it is zero when all labels agree and largest when they are spread evenly. The information gain of a question is the entropy of the set before the question minus the average entropy of the groups it creates, each weighted by the fraction \(N_c/N\) of the examples that fall into it. A decision tree asks, at each node, the question with the largest gain.

Precision, recall, and the F1 score

\[ \mathrm{precision} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}} , \qquad \mathrm{recall} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}} , \qquad F_1 = \frac{2\,\mathrm{precision}\times\mathrm{recall}}{\mathrm{precision} + \mathrm{recall}} \] Precision is the fraction of the flagged examples that really belong to the positive category; recall is the fraction of the positive examples that were flagged. The \(F_1\) score is their harmonic mean (the harmonic mean of two numbers \(a\) and \(b\) is \(2ab/(a + b)\), which lies closer to the smaller of the two), so it is high only when both are high, and it is the usual single number for a classifier on imbalanced data. Medicine calls recall the sensitivity and calls \(\mathrm{TN}/(\mathrm{TN} + \mathrm{FP})\), the fraction of healthy people correctly cleared, the specificity.

Neural Networks and Backpropagation

The artificial neuron

\[ z = \mathbf{w}\cdot\mathbf{x} + b , \qquad a = \phi(z) \] A neuron with input vector \(\mathbf{x}\), weight vector \(\mathbf{w}\), and bias \(b\) first computes its pre-activation \(z\), which is the weighted sum of the inputs, and then its activation \(a\) by applying the activation function \(\phi\) to \(z\). The weights and the bias are the parameters that training changes; the function \(\phi\) is chosen once.

The perceptron learning rule

\[ \mathbf{w} \leftarrow \mathbf{w} + \eta\,(y - \hat{y})\,\mathbf{x} , \qquad b \leftarrow b + \eta\,(y - \hat{y}) \] After each example \((\mathbf{x}, y)\) with the perceptron’s answer \(\hat{y} = \phi(\mathbf{w}\cdot\mathbf{x} + b)\), where \(\phi\) is the step function, the weights move by \(\eta\) times the error \(y - \hat{y}\) times the input. The error is \(0\), \(+1\), or \(-1\), so a correct answer leaves the weights alone. When the weights start at zero, every update is a multiple of \(\eta\), so a different learning rate gives weights that are all larger or smaller by the same factor and a perceptron that gives the same answers; \(\eta\) may then be set to 1.

The forward pass of a two-layer network

\[ \mathbf{z}^{(1)} = \mathbf{W}^{(1)}\mathbf{x} + \mathbf{b}^{(1)} , \qquad \mathbf{h} = \phi\bigl(\mathbf{z}^{(1)}\bigr) , \qquad z^{(2)} = \mathbf{w}^{(2)}\cdot\mathbf{h} + b^{(2)} , \qquad \hat{y} = \sigma\bigl(z^{(2)}\bigr) \] The input \(\mathbf{x}\) is multiplied by the weight matrix \(\mathbf{W}^{(1)}\) of the hidden layer and shifted by its biases, the activation function \(\phi\) is applied to every component, and the hidden vector \(\mathbf{h}\) is fed to the output neuron, whose sigmoid gives the prediction \(\hat{y}\). A network with more hidden layers repeats the first two steps once per layer.

The backpropagation algorithm

  1. Forward pass. For \(l = 1, \ldots, L\) compute \(\mathbf{z}^{(l)} = \mathbf{W}^{(l)}\mathbf{h}^{(l-1)} + \mathbf{b}^{(l)}\) and \(\mathbf{h}^{(l)} = \phi(\mathbf{z}^{(l)})\), and keep every \(\mathbf{z}^{(l)}\) and \(\mathbf{h}^{(l)}\).
  2. Output error. Compute \(\boldsymbol{\delta}^{(L)} = \partial \ell/\partial \mathbf{z}^{(L)}\) from the loss; for the squared error with a sigmoid output it is \((\hat{\mathbf{y}} - \mathbf{y}) \odot \sigma'(\mathbf{z}^{(L)})\), and for the cross-entropy with a sigmoid or softmax output it is \(\hat{\mathbf{y}} - \mathbf{y}\).
  3. Backward pass. For \(l = L - 1, \ldots, 1\) compute \(\boldsymbol{\delta}^{(l)} = \bigl(\mathbf{W}^{(l+1)\top}\boldsymbol{\delta}^{(l+1)}\bigr) \odot \phi'(\mathbf{z}^{(l)})\).
  4. Gradients. For every layer, \(\partial \ell/\partial \mathbf{W}^{(l)} = \boldsymbol{\delta}^{(l)}\,\mathbf{h}^{(l-1)\top}\), the matrix whose entry \((i, j)\) is \(\delta^{(l)}_i h^{(l-1)}_j\), and \(\partial \ell/\partial \mathbf{b}^{(l)} = \boldsymbol{\delta}^{(l)}\).
  5. Update every weight and bias with \(\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\nabla_{\boldsymbol{\theta}} L\), where the gradient of the training loss \(L\) is the average of the gradients of \(\ell\) over the examples.

The symbol \(\odot\) multiplies two vectors component by component, and \(\phi'\) is applied to each component. The error signal \(\boldsymbol{\delta}^{(l)}\) of a layer is the gradient of the loss with respect to its pre-activations.

Softmax output with the cross-entropy

\[ \hat{y}_k = \mathrm{softmax}(\mathbf{z})_k = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}} , \qquad \ell = -\sum_{k=1}^{K} y_k \log \hat{y}_k = -\log \hat{y}_c , \qquad \frac{\partial \ell}{\partial \mathbf{z}} = \hat{\mathbf{y}} - \mathbf{y} \] The softmax turns \(K\) pre-activations into \(K\) positive numbers that sum to 1, the cross-entropy is minus the log-probability of the correct category \(c\), and the gradient of the loss with respect to the pre-activations is the predicted probability vector minus the target vector. The last expression is the error signal \(\boldsymbol{\delta}^{(L)}\) that the backpropagation algorithm starts from.

Training Deep Networks

Minibatch stochastic gradient descent

  1. Shuffle the \(N\) training examples and cut them into minibatches of \(B\) examples each.
  2. For each minibatch, run the forward and the backward pass of Unit 6 on its \(B\) examples and average their gradients, which gives the estimate \(\mathbf{g} \approx \nabla_{\boldsymbol{\theta}} L\).
  3. Update all parameters, \(\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\mathbf{g}\).
  4. After the last minibatch one epoch is complete; measure the loss on the validation set and go back to step 1 until the rule of early stopping, which is explained later in this unit, says to stop.

The batch size \(B\) and the learning rate \(\eta\) are chosen before training. With \(B = N\) the method is the plain gradient descent of Unit 4, and with \(B = 1\) every example causes a step of its own.

Gradient descent with momentum

\[ \mathbf{v} \leftarrow \beta\,\mathbf{v} + \mathbf{g} , \qquad \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\mathbf{v} \] The velocity \(\mathbf{v}\) is a running sum of past gradient estimates \(\mathbf{g}\), each older one weighted by a further factor of the momentum constant \(\beta\), which is usually \(0.9\); the parameters move along the velocity rather than along the current gradient. Gradients that point the same way step after step add up to a velocity of up to \(\mathbf{g}/(1 - \beta)\), because the weights \(1, \beta, \beta^2, \ldots\) add up to \(1/(1 - \beta)\), which is ten times the gradient at \(\beta = 0.9\); gradients that alternate in sign cancel. The velocity starts at zero.

The Adam update

\begin{align*} \mathbf{m} &\leftarrow \beta_1\,\mathbf{m} + (1 - \beta_1)\,\mathbf{g} , & \mathbf{v} &\leftarrow \beta_2\,\mathbf{v} + (1 - \beta_2)\,\mathbf{g} \odot \mathbf{g} , \\ \hat{\mathbf{m}} &= \frac{\mathbf{m}}{1 - \beta_1^{\,t}} , & \hat{\mathbf{v}} &= \frac{\mathbf{v}}{1 - \beta_2^{\,t}} , \\ \boldsymbol{\theta} &\leftarrow \boldsymbol{\theta} - \eta\,\frac{\hat{\mathbf{m}}}{\sqrt{\hat{\mathbf{v}}} + \varepsilon} . \end{align*} At step \(t\), \(\mathbf{m}\) is a running average of the gradient and \(\mathbf{v}\) a running average of its square, taken component by component (the symbol \(\odot\) multiplies two vectors component by component, as in Unit 6); both start at zero and are divided by \(1 - \beta^{t}\) to correct for that start. Each parameter moves by \(\eta\) times the ratio of its average gradient to the square root of its average squared gradient, so that a parameter with a steady gradient, large or small, moves by about \(\eta\) per step. The constants published with the method are \(\beta_1 = 0.9\), \(\beta_2 = 0.999\), and \(\varepsilon = 10^{-8}\), and the usual starting value for \(\eta\) is \(10^{-3}\); the paper writes the learning rate as \(\alpha\). The square root, the square, and the division act on each component separately.

Xavier and He initialization

\[ \mathrm{Var}(w) = \frac{2}{n_{\mathrm{in}} + n_{\mathrm{out}}} \quad\text{(Xavier, for sigmoid and tanh)} , \qquad \mathrm{Var}(w) = \frac{2}{n_{\mathrm{in}}} \quad\text{(He, for the ReLU function)} \] The weights of a layer with \(n_{\mathrm{in}}\) inputs and \(n_{\mathrm{out}}\) neurons are drawn at random, from a Gaussian or a uniform distribution, with mean zero and the given variance; biases start at zero. The first rule, from a 2010 paper by Xavier Glorot and Yoshua Bengio, keeps the signal of the forward pass and the error signal of the backward pass at roughly constant size through the layers. The second, from a 2015 paper by Kaiming He and co-authors, doubles the variance because the ReLU function sets half of its inputs to zero and halves the variance of each layer’s output; the paper reports a 30-layer ReLU network that trained with this rule and did not move at all with the Xavier rule.

The residual block

\[ \mathbf{h}^{(l+1)} = \mathbf{h}^{(l)} + F\bigl(\mathbf{h}^{(l)}\bigr) \] A residual block adds the input \(\mathbf{h}^{(l)}\) of a group of layers, usually two, to their output \(F(\mathbf{h}^{(l)})\), so that the layers learn only the correction to the identity mapping, which returns its input unchanged, rather than the whole mapping. The addition is carried by a shortcut connection with no parameters. If the layers inside the block have weights near zero, the block passes its input through unchanged, and the gradient of the loss with respect to \(\mathbf{h}^{(l)}\) contains the gradient with respect to \(\mathbf{h}^{(l+1)}\) undiminished, plus whatever the layers add.

The cost of a training step

\[ C \approx 6\,P\,\text{FLOP per example} , \qquad C_{\mathrm{run}} \approx 6\,P \times N \times E \] Training a network with \(P\) parameters costs about 6 floating point operations per parameter per training example: 2 for the forward pass (one multiplication and one addition per weight), 2 for sending the error signal backward through the transposed weights, and 2 for forming the gradient of each weight. A full run over \(N\) examples for \(E\) epochs costs about \(6PNE\) FLOP. The rule holds for networks in which every weight is used once per example, as in the fully connected layers of this program; networks that apply the same weight at many positions of an input cost more per parameter.

The Big Questions of Artificial Intelligence

The imitation game

Three parties take part. An interrogator sits in a separate room and exchanges typed messages with two others, one of them a person and one a machine, each trying to convince the interrogator that it is the person. After a fixed time the interrogator must say which is which. A machine passes the test if the interrogator identifies it correctly no more often than a fixed share of the time. Turing set no pass mark himself; the bar in use is the figure of his 1950 prediction, quoted below, that the interrogator would be right no more than 70 per cent of the time. In the paper Turing first describes the game as a party game in which a man pretends to be a woman, and he then lets a machine take the man’s place. The game, now called the Turing test, replaces the question “can a machine think?” by the question “can a machine be told apart from a person in conversation?”, which can be answered by an experiment.

The AlexNet result

In the ImageNet challenge of 2012 the AlexNet network reached a top-5 error of 15.3 per cent on the test images, and the best entry that did not use a neural network reached 26.2 per cent. The gap of 10.9 percentage points convinced the field that trained networks with many layers, given enough data and compute, beat features designed by hand.

The gradient descent update, the one equation under Units 4 to 7

\[ \boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\nabla_{\boldsymbol{\theta}} L \] Every parameter of a model moves a small step against the gradient of the loss \(L\) on the training data, with the learning rate \(\eta\) setting the step, and the step is repeated until the loss stops falling. The least squares line, logistic regression, the perceptron rule, and backpropagation through a deep network are this update with a different loss and a different way of computing the gradient; the training of the largest systems in use today is this update too.

Convolutional Networks and Computer Vision

The transpose

\[ (\mathbf{A}^{\top})_{ij} = A_{ji} , \qquad \mathbf{w}^{\top}\mathbf{x} = \sum_{j=1}^{d} w_j x_j = \mathbf{w}\cdot\mathbf{x} , \qquad (\mathbf{A}\mathbf{B})^{\top} = \mathbf{B}^{\top}\mathbf{A}^{\top} \] The transpose \(\mathbf{A}^{\top}\) of a matrix with \(m\) rows and \(n\) columns is the matrix with \(n\) rows and \(m\) columns whose entry in row \(i\) and column \(j\) is the entry of \(\mathbf{A}\) in row \(j\) and column \(i\). A vector \(\mathbf{x}\) is a matrix with \(d\) rows and one column, its transpose \(\mathbf{x}^{\top}\) is a single row, and the product of a row with a column is a single number, the dot product. The transpose of a product is the product of the transposes in reverse order.

The two-dimensional convolution

\[ (\mathbf{X} * \mathbf{K})_{ij} = \sum_{m=1}^{k}\sum_{n=1}^{k} X_{i+m-1,\, j+n-1}\, K_{mn} \] The image \(\mathbf{X}\) has \(n\) rows and columns, the kernel \(\mathbf{K}\) has \(k\) of each, and the output entry in row \(i\) and column \(j\) is the sum of the products of the kernel with the \(k\) by \(k\) patch whose top-left corner is pixel \((i, j)\). Without padding, \(i\) and \(j\) run from 1 to \(n - k + 1\), so the output is smaller than the input by \(k - 1\) in each direction. A bias \(b\) is added to every output, and an activation function, usually the ReLU function, is applied to each. In mathematics a convolution flips the kernel before multiplying, which would read \(X_{i-m,\, j-n}\); what the field calls a convolution is strictly a cross-correlation, and since the kernel is learned, the network learns the flipped kernel instead, so nothing is lost.

The output size of a convolution

\[ n_{\mathrm{out}} = \left\lfloor \frac{n + 2p - k}{s} \right\rfloor + 1 \] An input of width \(n\), a kernel of width \(k\), a padding of \(p\) pixels on each side, and a stride \(s\) give an output of width \(n_{\mathrm{out}}\), where the brackets round down to a whole number; the same formula applies to the height. With \(p = 0\) and \(s = 1\) it reduces to \(n - k + 1\).

The parameter count of a convolutional layer

\[ P = k^2\, c_{\mathrm{in}}\, c_{\mathrm{out}} + c_{\mathrm{out}} \] A layer with \(c_{\mathrm{out}}\) kernels of size \(k\) by \(k\) that reads \(c_{\mathrm{in}}\) input channels has \(k^2 c_{\mathrm{in}}\) weights per kernel and one bias per kernel. The count does not depend on the size of the image, which is the whole point: the same layer serves a 32 by 32 image and a 2,000 by 2,000 image.

Max pooling

\[ (\mathrm{pool}\,\mathbf{H})_{ij} = \max_{1 \le m, n \le w} H_{s(i-1)+m,\, s(j-1)+n} \] Max pooling with a window of \(w\) by \(w\) and a stride \(s\) replaces each window of the feature map \(\mathbf{H}\) by its largest value; the usual choice \(w = s = 2\) halves the height and the width and keeps the number of channels. Average pooling takes the mean instead of the maximum. Neither has parameters to learn.

The fast gradient sign method

\[ \mathbf{x}' = \mathbf{x} + \varepsilon\, \mathrm{sign}\bigl(\nabla_{\mathbf{x}}\, \ell(\boldsymbol{\theta}, \mathbf{x}, y)\bigr) \] Take the gradient of the loss with respect to the pixels rather than the weights, which backpropagation delivers at no extra cost, keep only its sign per pixel, and move every pixel by a small step \(\varepsilon\) in the direction that increases the loss. Here \(y\) is the true label; the weights \(\boldsymbol{\theta}\) stay fixed, the image moves.

Embeddings and Sequence Models

Cosine similarity

\[ \cos\theta = \frac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{a}\|\,\|\mathbf{b}\|} \] The cosine of the angle \(\theta\) between the vectors \(\mathbf{a}\) and \(\mathbf{b}\) is their dot product divided by the product of their lengths. It is \(1\) for vectors that point the same way, \(0\) for perpendicular vectors, and \(-1\) for opposite ones, and it does not change when either vector is scaled by a positive number.

Skip-gram with negative sampling

For a centre word \(c\), one of its context words \(o\), and \(K\) negative samples \(k = 1, \ldots, K\) drawn from the vocabulary, the loss of the pair is \[ \ell = -\log\sigma(\mathbf{u}_o\cdot\mathbf{v}_c) - \sum_{k=1}^{K}\log\sigma(-\mathbf{u}_k\cdot\mathbf{v}_c) , \] and training proceeds in four steps:

  1. Slide a window of \(m\) words on each side over the text; every centre word with every word in its window is one training pair \((c, o)\).
  2. For each pair draw \(K\) negative words at random, with a probability proportional to their frequency raised to the power \(3/4\), which draws frequent words often but gives rare words a somewhat larger share than their frequency alone would.
  3. Compute the gradient of \(\ell\) with respect to \(\mathbf{v}_c\), \(\mathbf{u}_o\), and the \(K\) vectors \(\mathbf{u}_k\), and take one step of stochastic gradient descent on these vectors only.
  4. After one or a few passes over the text, keep the centre vectors \(\mathbf{v}_w\) as the embeddings.

Here \(\mathbf{v}_w\) is the centre vector and \(\mathbf{u}_w\) the context vector of the word \(w\), \(\sigma\) is the sigmoid, and the 2013 paper recommends \(K\) between 5 and 20 for small corpora and 2 to 5 for large ones.

The recurrent update

\[ \mathbf{h}_t = \phi\bigl(\mathbf{W}_h\mathbf{h}_{t-1} + \mathbf{W}_x\mathbf{x}_t + \mathbf{b}\bigr) , \qquad \hat{\mathbf{y}}_t = \mathrm{softmax}\bigl(\mathbf{W}_y\mathbf{h}_t + \mathbf{b}_y\bigr) \] At step \(t\) the new hidden state \(\mathbf{h}_t\) is an activation function \(\phi\), usually \(\tanh\), applied to a weighted sum of the previous hidden state \(\mathbf{h}_{t-1}\) and the current input \(\mathbf{x}_t\). The matrices \(\mathbf{W}_h\), \(\mathbf{W}_x\), and \(\mathbf{W}_y\) and the biases are the same at every step, and \(\mathbf{h}_0\) is a vector of zeros. The output \(\hat{\mathbf{y}}_t\) is whatever the task needs, for instance a softmax over the vocabulary for the next word.

The LSTM cell

\begin{align*} \mathbf{f}_t &= \sigma\bigl(\mathbf{W}_f[\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_f\bigr) &&\text{forget gate} \\ \mathbf{i}_t &= \sigma\bigl(\mathbf{W}_i[\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_i\bigr) &&\text{input gate} \\ \tilde{\mathbf{c}}_t &= \tanh\bigl(\mathbf{W}_c[\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_c\bigr) &&\text{candidate} \\ \mathbf{o}_t &= \sigma\bigl(\mathbf{W}_o[\mathbf{h}_{t-1}, \mathbf{x}_t] + \mathbf{b}_o\bigr) &&\text{output gate} \\ \mathbf{c}_t &= \mathbf{f}_t \odot \mathbf{c}_{t-1} + \mathbf{i}_t \odot \tilde{\mathbf{c}}_t &&\text{new cell state} \\ \mathbf{h}_t &= \mathbf{o}_t \odot \tanh(\mathbf{c}_t) &&\text{new hidden state} \end{align*} The bracket \([\mathbf{h}_{t-1}, \mathbf{x}_t]\) is the previous hidden state and the current input written one after the other as a single vector, \(\sigma\) is the sigmoid, and \(\odot\) multiplies two vectors component by component. Each gate has its own weight matrix and bias, so an LSTM layer has four times the parameters of the plain recurrent layer of the same size.

A language model as next-word prediction

\[ P(w_1, \ldots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_{<t}) , \qquad L = -\frac{1}{T}\sum_{t=1}^{T}\log P(w_t \mid w_{<t}) \] The probability of a sentence is the product of the probabilities of each word given all the words before it, by the chain rule of probability. A model that outputs a probability distribution over the next word at every position therefore defines a probability for every text, and it is trained by minimizing the average cross-entropy \(L\) of the true next words, in nats, the unit of Unit 5, when the logarithm is natural.

Perplexity

\[ \mathrm{PP} = \exp\!\left(-\frac{1}{T}\sum_{t=1}^{T}\log P(w_t \mid w_{<t})\right) = \exp(L) = \left(\prod_{t=1}^{T} P(w_t \mid w_{<t})\right)^{-1/T} \] The perplexity of a model on a text of \(T\) words is the exponential of its average cross-entropy per word, which equals the inverse of the geometric mean of the probabilities it assigned to the words that actually came (the geometric mean of \(T\) numbers is the \(T\)-th root of their product). A perplexity of \(\mathrm{PP}\) means that the model was, on average, as uncertain as if it had been choosing uniformly among \(\mathrm{PP}\) equally likely words. Lower is better, and the value depends on the vocabulary and the text, so perplexities are compared only on the same test set.

Attention and Transformers

Scaled dot-product attention

\[ \mathbf{Q} = \mathbf{X}\mathbf{W}_Q, \qquad \mathbf{K} = \mathbf{X}\mathbf{W}_K, \qquad \mathbf{V} = \mathbf{X}\mathbf{W}_V, \qquad \mathrm{Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \mathrm{softmax}\!\left(\frac{\mathbf{Q}\mathbf{K}^{\top}}{\sqrt{d_k}}\right)\mathbf{V} \] The rows of \(\mathbf{X}\) are the \(T\) input vectors, and \(\mathbf{W}_Q\), \(\mathbf{W}_K\), and \(\mathbf{W}_V\) are learned matrices, called the projection matrices, with \(d_{\mathrm{model}}\) rows and \(d_k\) columns, where \(d_k\) is called the key dimension. The entry \((i, j)\) of \(\mathbf{Q}\mathbf{K}^{\top}\) is the dot product \(\mathbf{q}_i\cdot\mathbf{k}_j\), the score of token \(i\) for token \(j\); the softmax is applied to each row separately, so every row of weights sums to 1; and row \(i\) of the result is the weighted sum of the value vectors for token \(i\). When queries, keys, and values all come from the same sequence, the step is called self-attention.

Multi-head attention

\[ \mathrm{head}_i = \mathrm{Attention}(\mathbf{X}\mathbf{W}_Q^{(i)}, \mathbf{X}\mathbf{W}_K^{(i)}, \mathbf{X}\mathbf{W}_V^{(i)}), \qquad \mathrm{MultiHead}(\mathbf{X}) = \mathrm{Concat}(\mathrm{head}_1, \ldots, \mathrm{head}_h)\,\mathbf{W}_O \] Each of the \(h\) heads has its own projection matrices with \(d_k = d_{\mathrm{model}}/h\) columns. The outputs of the heads, each with \(d_k\) components per token, are placed next to one another to give \(d_{\mathrm{model}}\) components again, and the learned output matrix \(\mathbf{W}_O\) with \(d_{\mathrm{model}}\) rows and columns mixes them. The original model used \(h = 8\) heads of \(d_k = 64\) on a width of \(d_{\mathrm{model}} = 512\).

Sinusoidal positional encoding

\[ \mathrm{PE}(t, 2i) = \sin\!\left(\frac{t}{10000^{2i/d_{\mathrm{model}}}}\right), \qquad \mathrm{PE}(t, 2i + 1) = \cos\!\left(\frac{t}{10000^{2i/d_{\mathrm{model}}}}\right) \] This is the vector added to the embedding of the token at position \(t\), counted from \(0\). Its components come in pairs: the component with the even index \(2i\) is a sine and the next one, with index \(2i + 1\), is the cosine of the same frequency. The pair with index \(i = 0\) has a wavelength of \(2\pi\) positions, and each following pair has a longer wavelength by a fixed factor, up to nearly \(10000\cdot 2\pi\), which is about 63,000 positions, for the last pair.

The transformer block

A block maps the \(T\) input vectors \(\mathbf{X}\), each of \(d_{\mathrm{model}}\) components, to \(T\) output vectors of the same size in four steps:

  1. Multi-head self-attention: \(\mathbf{A} = \mathrm{MultiHead}(\mathbf{X})\).
  2. Residual connection and layer normalization: \(\mathbf{X}' = \mathrm{LayerNorm}(\mathbf{X} + \mathbf{A})\), row by row.
  3. A feed-forward network applied to each row \(\mathbf{x}'_t\) separately, with the same weights at every position: \(\mathbf{f}_t = \mathbf{W}_2\,\mathrm{ReLU}(\mathbf{W}_1\mathbf{x}'_t + \mathbf{b}_1) + \mathbf{b}_2\), where \(\mathbf{W}_1\) has \(d_{\mathrm{ff}}\) rows and \(d_{\mathrm{model}}\) columns, \(\mathbf{W}_2\) the reverse, and \(d_{\mathrm{ff}}\) is called the feed-forward width.
  4. Residual connection and layer normalization again: \(\mathbf{X}'' = \mathrm{LayerNorm}(\mathbf{X}' + \mathbf{F})\), where the rows of \(\mathbf{F}\) are the vectors \(\mathbf{f}_t\).

The original model used \(d_{\mathrm{model}} = 512\) and \(d_{\mathrm{ff}} = 2048\), so the feed-forward network widens each token’s vector to 2048 components and narrows it back. Blocks are stacked, the output of one being the input of the next, 6 deep in the encoder and 6 deep in the decoder of the original model.

Parameters of a transformer block

\[ N_{\mathrm{block}} \approx 4\,d_{\mathrm{model}}^2 + 2\,d_{\mathrm{model}}\,d_{\mathrm{ff}} \] The four matrices of multi-head attention (\(\mathbf{W}_Q\), \(\mathbf{W}_K\), and \(\mathbf{W}_V\) of all heads together, and \(\mathbf{W}_O\)) each have \(d_{\mathrm{model}}^2\) entries, because the \(h\) heads with \(d_k = d_{\mathrm{model}}/h\) columns each add up to \(d_{\mathrm{model}}\) columns, and the two matrices of the feed-forward network have \(d_{\mathrm{model}}\,d_{\mathrm{ff}}\) each. Biases and the gains and shifts of layer normalization add a few thousand more, which the approximation ignores. A decoder block with its second attention has \(8\,d_{\mathrm{model}}^2 + 2\,d_{\mathrm{model}}\,d_{\mathrm{ff}}\).

Reinforcement Learning

The return

\[ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \] The return from time \(t\) is the sum of all later rewards, each multiplied by the discount \(\gamma\) raised to the number of steps it lies in the future; for an episode the sum ends with the last reward. For \(\gamma = 1\) the return is the plain sum, and for \(\gamma < 1\) a reward \(k\) steps away counts \(\gamma^k\) times its face value.

The Bellman equations

\begin{align*} V^{\pi}(s) &= \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\,\bigl[R(s, a, s') + \gamma V^{\pi}(s')\bigr] \qquad\text{(expectation equation)} \\ Q^{*}(s, a) &= \sum_{s'} P(s' \mid s, a)\,\bigl[R(s, a, s') + \gamma \max_{a'} Q^{*}(s', a')\bigr] \qquad\text{(optimality equation)} \end{align*} The value of a state under a policy \(\pi\) is the expected reward of the next step plus \(\gamma\) times the expected value of the next state, averaged over the policy’s choice of action and the environment’s choice of successor. The optimal action value \(Q^*\) obeys the same relation with the best next action in place of the average, and \(V^*(s) = \max_a Q^*(s, a)\). In a deterministic environment the sum over \(s'\) has one term.

Value iteration

  1. Set \(V_0(s) = 0\) for every state, and \(V_k(s) = 0\) for every terminal state in every sweep.
  2. In sweep \(k + 1\), compute for every non-terminal state \[ V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a)\,\bigl[R(s, a, s') + \gamma V_k(s')\bigr] . \]
  3. Stop when no value changes by more than a chosen tolerance. The values converge to \(V^*\) for \(\gamma < 1\).
  4. Read off the optimal policy by choosing in every state the action that attains the maximum in step 2.

Each sweep applies the Bellman optimality equation once to every state, using the values of the previous sweep. The policy of step 4 is the greedy policy with respect to \(V^*\), and it is optimal.

Q-learning

  1. Start with \(Q(s, a) = 0\) for every state and action, and choose a step size \(\alpha\) and an exploration rate \(\varepsilon\).
  2. In the current state \(s\), choose an action \(a\): with probability \(1 - \varepsilon\) the action with the largest \(Q(s, a)\), and with probability \(\varepsilon\) a random one.
  3. Take the action, observe the reward \(r\) and the next state \(s'\), and update \[ Q(s, a) \leftarrow Q(s, a) + \alpha\bigl[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\bigr] , \] where the maximum is 0 if \(s'\) is terminal.
  4. Set \(s \leftarrow s'\) and repeat from step 2; when an episode ends, start a new one.

The bracket is the temporal difference error of the action value: the sample \(r + \gamma\max_{a'} Q(s', a')\) of the Bellman optimality target minus the current estimate. The table converges to \(Q^*\) if every state-action pair is tried infinitely often and the step size decreases suitably, a result proved by Watkins and Peter Dayan in 1992; in practice a constant \(\alpha\) between \(0.1\) and \(0.5\) is common.

The policy gradient (REINFORCE)

\[ \nabla_{\boldsymbol{\theta}} J = \mathbb{E}\Bigl[\sum_{t} G_t\, \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(a_t \mid s_t)\Bigr] \] The gradient of the expected return is the expectation, over episodes played with the current policy, of the return from each step times the gradient of the log-probability of the action taken at that step. An estimate is obtained by playing one or more episodes and summing the terms, and the policy is then moved by \(\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} + \eta\,\nabla_{\boldsymbol{\theta}} J\). Subtracting a baseline \(b(s_t)\) from \(G_t\) leaves the expectation unchanged and reduces its variance.

Monte Carlo tree search

  1. Selection. From the root, descend the tree until a node with an untried move is reached, choosing in each node the child \(i\) with the largest score \[ \frac{W_i}{N_i} + c\,\sqrt{\frac{\ln N}{N_i}} , \] where \(W_i\) is the number of wins recorded below child \(i\), \(N_i\) is its number of visits, \(N\) is the number of visits of the parent, and \(c\) is a constant.
  2. Expansion. Add one child for an untried move to the tree.
  3. Simulation. Play the game from the new node to the end, with random or cheaply chosen moves, and record the result.
  4. Backup. Add one visit to every node on the path from the new node to the root, and add the result to their win counts.

After many iterations the move at the root with the most visits is played. The first term of the score favours moves that have won often, the second favours moves tried rarely, and the rule with this score is called UCT (upper confidence bounds applied to trees).

Pretraining and Scaling Laws

The pretraining loss

\[ L(\boldsymbol{\theta}) = -\frac{1}{T}\sum_{t=1}^{T} \log p_{\boldsymbol{\theta}}(w_t \mid w_{<t}) \] The average cross-entropy per token over a text of \(T\) tokens, where \(p_{\boldsymbol{\theta}}(w_t \mid w_{<t})\) is the probability the model with parameters \(\boldsymbol{\theta}\) gives to the token that actually came next. With the natural logarithm the loss is measured in nats per token, the nat being the measure of information that goes with the natural logarithm, as the bit goes with \(\log_2\); with \(\log_2\) it is measured in bits per token. It is zero only for a model that gives probability one to every next token, and it is minimized by gradient descent on the text, as in every earlier unit.

Byte pair encoding

  1. Split the training text into words, write every word as a sequence of characters, and append an end-of-word mark to each. The starting vocabulary is the set of distinct characters plus the mark.
  2. Count, over the whole text, how often each pair of neighbouring symbols occurs inside a word.
  3. Merge the most frequent pair into one new symbol, add it to the vocabulary, and replace every occurrence of the pair in the text.
  4. Repeat steps 2 and 3 until the vocabulary has the wanted size.

The vocabulary size is the number of starting symbols plus the number of merges, and the ordered list of merges is the tokenizer. A new text is tokenized by splitting it into characters and applying the merges in the order they were learned.

The compute of a training run

\[ C \approx 6\,N\,D \] A model with \(N\) parameters trained on \(D\) tokens costs about \(C\) floating point operations, counted as FLOP: \(2N\) for each token’s forward pass and \(4N\) for its backward pass. The rule counts only the operations of the weight matrices and holds when one pass is made over the data; a second pass over the same data, which is called a second epoch, doubles \(D\).

The Chinchilla loss fit

\[ L(N, D) = E + \frac{A}{N^{\alpha}} + \frac{B}{D^{\beta}} \qquad\text{with}\qquad E = 1.69,\; A = 406.4,\; B = 410.7,\; \alpha = 0.34,\; \beta = 0.28 \] The final pretraining loss, in nats per token, of a transformer with \(N\) parameters trained on \(D\) tokens, as fitted by Hoffmann et al. (2022) to their runs. \(E\) is the loss that an infinitely large model trained on infinite data would still have, which is the entropy of the text itself; the second term is the price of a finite model, and the third the price of finite data. The constants belong to that paper’s text and tokenizer and are not transferable to another corpus.

The few-shot prompt

A few-shot prompt is an input text that consists of a short description of a task, followed by \(K\) worked examples of the task written as text, followed by a new instance whose answer the model is to continue. The model’s parameters are not changed; the examples act only through the context, and the behaviour is called in-context learning. With \(K = 0\) the prompt is zero-shot, with \(K = 1\) one-shot, and in the GPT-3 experiments few-shot meant as many examples as fit into the context window, typically 10 to 100.

Instruction Tuning and Learning from Human Feedback

The supervised fine-tuning loss

\[ L_{\mathrm{SFT}}(\boldsymbol{\theta}) = -\frac{1}{N}\sum_{i=1}^{N}\;\sum_{t=1}^{T_i} \log p_{\boldsymbol{\theta}}\bigl(y^{(i)}_t \,\big|\, x^{(i)}, y^{(i)}_{<t}\bigr) \] The training set holds \(N\) demonstrations, each a prompt \(x^{(i)}\) with an answer of \(T_i\) tokens \(y^{(i)}_1, \ldots, y^{(i)}_{T_i}\) written by a person. The loss is the cross-entropy of next-token prediction summed over the answer tokens only, where each token \(y^{(i)}_t\) is conditioned on the prompt and on the earlier answer tokens, written \(y^{(i)}_{<t}\). The model is trained with the gradient descent update \(\boldsymbol{\theta} \leftarrow \boldsymbol{\theta} - \eta\,\nabla_{\boldsymbol{\theta}} L\) of Unit 4, with the learning rate \(\eta\), for a few passes over the data.

The reward model loss

\[ L_{\mathrm{R}}(\boldsymbol{\phi}) = -\,\mathbb{E}_{(x, y_w, y_l) \sim \mathcal{D}}\Bigl[\log\sigma\bigl(r_{\boldsymbol{\phi}}(x, y_w) - r_{\boldsymbol{\phi}}(x, y_l)\bigr)\Bigr] \] The reward model \(r_{\boldsymbol{\phi}}\) gives the preferred answer \(y_w\) and the rejected answer \(y_l\) of every recorded comparison a score, and the loss is the negative log-probability of the recorded choice under the Bradley-Terry model, averaged over the dataset \(\mathcal{D}\). Only score differences are determined by it, so the scale is fixed afterwards by a convention, for example that the written demonstrations score zero on average.

The objective of reinforcement learning from human feedback

\[ J(\boldsymbol{\theta}) = \mathbb{E}_{x \sim \mathcal{D},\; y \sim \pi_{\boldsymbol{\theta}}(\cdot \mid x)}\bigl[r_{\boldsymbol{\phi}}(x, y)\bigr] \;-\; \beta\,\mathrm{KL}\bigl(\pi_{\boldsymbol{\theta}}(\cdot \mid x) \,\big\|\, \pi_{\mathrm{ref}}(\cdot \mid x)\bigr) \] The policy \(\pi_{\boldsymbol{\theta}}\) is trained to maximize the expected score that the reward model \(r_{\boldsymbol{\phi}}\) gives to its answers \(y\) to prompts \(x\) drawn from a set \(\mathcal{D}\), minus \(\beta\) times the Kullback-Leibler divergence of the policy from the reference model \(\pi_{\mathrm{ref}}\) it started from. The coefficient \(\beta\) sets the length of the leash; InstructGPT used \(\beta = 0.02\). In practice the penalty is charged token by token as a negative reward, \(-\beta\,[\log\pi_{\boldsymbol{\theta}}(y_t \mid x, y_{<t}) - \log\pi_{\mathrm{ref}}(y_t \mid x, y_{<t})]\), and the reward model’s score is added at the last token.

The three stages of reinforcement learning from human feedback

  1. Supervised fine-tuning. Collect prompts with written demonstrations and train the pretrained model on them with the loss \(L_{\mathrm{SFT}}\); the result is the reference model \(\pi_{\mathrm{ref}}\).
  2. Reward modelling. Sample several answers to each of a new set of prompts from \(\pi_{\mathrm{ref}}\), have people compare or rank them, and train the reward model \(r_{\boldsymbol{\phi}}\) on the comparisons with the loss \(L_{\mathrm{R}}\), starting from a copy of \(\pi_{\mathrm{ref}}\) with a single-output final layer.
  3. Reinforcement learning. Starting from \(\pi_{\mathrm{ref}}\), sample answers to a third set of prompts, score them with \(r_{\boldsymbol{\phi}}\), charge the penalty \(\beta\) times the divergence from \(\pi_{\mathrm{ref}}\), and update the policy with a policy gradient method such as PPO. Repeat until the reward stops rising or the divergence reaches a chosen limit.

Each stage needs its own prompts, and only the first two need human labels; the third needs only prompts. Stages 2 and 3 can be repeated with comparisons collected from the improved policy.

The direct preference optimization loss

\[ L_{\mathrm{DPO}}(\boldsymbol{\theta}) = -\,\mathbb{E}_{(x, y_w, y_l) \sim \mathcal{D}}\left[\log\sigma\!\left(\beta\log\frac{\pi_{\boldsymbol{\theta}}(y_w \mid x)}{\pi_{\mathrm{ref}}(y_w \mid x)} - \beta\log\frac{\pi_{\boldsymbol{\theta}}(y_l \mid x)}{\pi_{\mathrm{ref}}(y_l \mid x)}\right)\right] \] The policy \(\pi_{\boldsymbol{\theta}}\) is trained directly on the comparisons: for each one, the log-probabilities of the two answers under the policy and under the frozen reference model \(\pi_{\mathrm{ref}}\) are computed, and the loss is the reward model loss with \(\beta\log(\pi_{\boldsymbol{\theta}}/\pi_{\mathrm{ref}})\) in the place of the reward. Minimizing it moves the policy toward the optimum of the RLHF objective with the same \(\beta\), without a reward model and without sampling.

The expected score of an Elo rating difference

\[ E_A = \frac{1}{1 + 10^{\,(R_B - R_A)/400}} \] A player or model with the rating \(R_A\) is expected to win against one with the rating \(R_B\) with the probability \(E_A\), counting a tie as half a win. The formula is the Bradley-Terry model with the score \(r = R\log 10/400\), so a difference of 100 points gives \(0.64\), of 200 points \(0.76\), and of 400 points \(0.91\). After a match, a chess player’s rating moves by a fixed factor times the difference between the actual and the expected score; an arena instead fits all ratings to all votes at once.

Reasoning, Tools, and Agents

The temperature softmax

\[ p_k = \frac{\exp(z_k/\tau)}{\sum_{j=1}^{V}\exp(z_j/\tau)} \] The model outputs a score \(z_k\), called a logit, for every one of the \(V\) tokens of the vocabulary. Dividing all logits by the temperature \(\tau > 0\) before the softmax sharpens the distribution when \(\tau < 1\) and flattens it when \(\tau > 1\). As \(\tau \to 0\) all probability moves to the token with the largest logit, which is called greedy decoding; as \(\tau \to \infty\) every token becomes equally likely. The token is then drawn at random from the resulting distribution, and \(\tau = 1\) returns the distribution the model was trained to produce.

Self-consistency

  1. Write the chain-of-thought prompt once, with the question at the end.
  2. Sample \(m\) complete chains independently from the model at a temperature \(\tau\) between about \(0.5\) and \(0.7\), each ending in a final answer \(a_i\).
  3. Return the answer that occurs most often among \(a_1, \ldots, a_m\); where answers are numbers, count them as equal only when they agree exactly.

The chains themselves are discarded; only their final answers vote. The method costs \(m\) times the computation of a single chain, and it helps only when the model’s individual samples are right more often than they are wrong.

The verifiable reward and its policy gradient

\[ r(x, y) \in \{0, 1\}, \qquad \nabla_{\boldsymbol{\theta}} J = \mathbb{E}\Bigl[\bigl(r(x, y) - b(x)\bigr)\, \nabla_{\boldsymbol{\theta}} \log \pi_{\boldsymbol{\theta}}(y \mid x)\Bigr] \] The reward is \(r(x, y) = 1\) if the final answer in the written solution \(y\) passes the check for problem \(x\) and \(0\) otherwise. The policy \(\pi_{\boldsymbol{\theta}}\) is the language model, an episode is one complete solution, and the reward is paid once at the end by a checker. The gradient is the policy gradient of Unit 12 with the return replaced by the reward of the episode and a baseline \(b(x)\) subtracted, so that solutions better than the model’s average on that problem have their log-probability raised and worse ones lowered. The log-probability of a solution is the sum over its tokens, which means every token of a correct chain is pushed up a little, including the steps that made the answer possible. A KL penalty against the starting model, as in Unit 14, is usually added.

Retrieval, then generation

  1. Before any question is asked, split the document collection into passages \(d_1, \ldots, d_M\) of a few hundred tokens each, compute an embedding vector \(\mathbf{e}(d_j)\) for every passage with an embedding model, and store the vectors in an index.
  2. Given a question \(x\), compute its embedding \(\mathbf{e}(x)\) with the same model and find the \(k\) passages with the largest cosine similarity \(\mathbf{e}(x)\cdot\mathbf{e}(d_j) / (\|\mathbf{e}(x)\|\,\|\mathbf{e}(d_j)\|)\).
  3. Place the \(k\) passages in the prompt, before or after the question, with an instruction to answer from them and to cite them, and let the language model generate \(y \sim p_{\boldsymbol{\theta}}(y \mid x, d_{(1)}, \ldots, d_{(k)})\).

The embedding model is a transformer trained so that a question and a passage that answers it have nearby vectors; it is not the language model. The number \(k\) is typically between 3 and 20.

The ReAct loop

  1. Place the task, the list of available actions, and optionally a few example trajectories in the context.
  2. The model writes a thought: free text about what it knows so far and what to do next.
  3. The model writes an action in the agreed format, such as search[Bombe], and stops.
  4. The harness executes the action in the environment and appends the result to the context as an observation.
  5. Return to step 2, until the model writes the action finish[answer] or a step limit is reached.

The context grows by one thought, one action, and one observation per step, so the model sees the whole history. One complete record of thoughts, actions, and observations, from the task to the finish action, is called a trajectory. The thought is not executed and may be wrong; the action is the only part that touches the world, and the observation is the only new information that enters.

Interpretability and Alignment

The linear probe

\[ \hat{c} = \arg\max_k \,(\mathbf{W}\mathbf{h} + \mathbf{b})_k \] A linear probe predicts a property \(c\) with \(K\) possible values from a hidden vector \(\mathbf{h}\) with \(d\) components. The matrix \(\mathbf{W}\) has \(K\) rows and \(d\) columns and the vector \(\mathbf{b}\) has \(K\) components; they are the only parameters trained, by the cross-entropy loss on pairs \((\mathbf{h}, c)\) collected from many inputs, while the network itself stays fixed. A probe that reaches high accuracy shows that the property is present in \(\mathbf{h}\) as a direction, which means that one weighted sum of the components separates the values of the property; a probe that fails shows only that no linear reading exists.

The causal test by intervention

  1. Train a probe that reads the property of interest from the activations, and record the model’s output on a chosen input.
  2. Choose a target value of the property that differs from the true one in a single respect, such as one square flipped.
  3. Edit the activations, from a starting layer onward, until the probe reads the target value, by gradient descent on the probe’s score or by adding the probe’s direction with a chosen weight.
  4. Continue the forward pass with the edited activations, and compare the new output with what the model should produce if the property really had the target value. Agreement over many cases, against a baseline of unedited outputs, supports the claim that the model computes its output from that property.

The test shows that the representation is used, which a probe alone cannot show. It assumes that the edit changed only the property of interest; an edit that also damages unrelated information proves less.

The sparse autoencoder

\[ \mathbf{f} = \mathrm{ReLU}(\mathbf{W}_e\mathbf{h} + \mathbf{b}_e), \qquad \hat{\mathbf{h}} = \mathbf{D}\mathbf{f}, \qquad L = \|\mathbf{h} - \mathbf{D}\mathbf{f}\|^2 + \lambda\,\|\mathbf{f}\|_1 \] A hidden vector \(\mathbf{h}\) with \(d\) components is encoded into \(m\) feature activations \(\mathbf{f}\), with \(m\) several times to several hundred times larger than \(d\), and decoded by the dictionary \(\mathbf{D}\), a matrix with \(d\) rows and \(m\) columns, each column a direction of length one and one column per feature. The loss adds the squared reconstruction error to \(\lambda\) times the sum of the feature activations, which is written \(\|\mathbf{f}\|_1\), and the second term, the penalty, drives most of the activations to exactly zero. The encoder, the dictionary, and the biases are trained by gradient descent on millions of hidden vectors collected from the frozen model; \(\lambda\) sets the trade between faithful reconstruction and sparsity.

Activation patching

  1. Choose a clean input and a corrupted input that differ only in the thing under study, such as “The Eiffel Tower is in” and “The Colosseum is in”, and a metric on the output, a single number computed from the output, such as the difference between the scores of “Paris” and “Rome”.
  2. Run the model on both inputs and store every activation of both runs.
  3. Run the corrupted input again, but at one chosen component and position, such as the output of attention head 7 of layer 9 at the subject token, the last token of the name “Eiffel Tower”, replace the activation with the one stored from the clean run, and let the rest of the pass continue.
  4. Record how much of the clean metric is restored by this one replacement.
  5. Repeat steps 3 and 4 for every component and position of interest, and draw the restored fractions as a map over layers and positions.

The map shows where the information that distinguishes the two inputs travels through the network. The same procedure run in the other direction, with corrupted activations patched into the clean run, asks a different question. A component whose clean activation restores the answer on its own is sufficient for the answer; a component whose corrupted activation destroys the answer on its own is necessary for it; and the two sets of components can differ, for example when two routes through the network each carry the answer.