Chapter 4Parameterized programs

Neural networks can be thought of as parameterized programs: programs with learnable parameters. In this chapter, we begin by reviewing how to represent programs mathematically. We then review several key neural network architectures and components.

4.1 Representing computer programs

4.1.1 Computation chains

To begin with, we consider simple programs that apply a sequence of functions $f_1,\dots,f_K$ to an input $\s_0 \in \cS_0$. We call such programs computation chains. For example, an image may go through a sequence of transformations such as cropping, rotation, normalization, and so on. In neural networks, the transformations are typically parameterized, and the parameters are learned, leading to feedforward networks, presented in Section 4.2. Another example of a sequence of functions is a for loop, presented in Section 5.8.

Formally, a computation chain can be written as $$\begin{align*} \s_0 &\in \cS_0 \\ \s_1 &\coloneqq f_1(\s_0) \in \cS_1 \\ & \hspace{6pt} \vdots \\ \s_K &\coloneqq f_K(\s_{K-1}) \in \cS_K \\ f(\s_0) &\coloneqq \s_K. \tag{4.1}\end{align*}$$ Here, $\s_0$ is the input, $\sv_k \in \cS_k$ is an intermediate state of the program, and $\s_K \in \cS_K$ is the final output. Of course, the domain (input space) of $f_k$ must be compatible with the image (output space) of $f_{k-1}$. That is, we should have $f_k \colon \cS_{k-1} \to \cS_k$. We can write a computation chain equivalently as $$\begin{align*} f(\s_0) &= (f_K \circ \dots \circ f_2 \circ f_1)(\s_0) \\ &= f_K(\dots f_2(f_1(\s_0))). \end{align*}$$ A computation chain can be represented by a directed graph, shown in Fig. 4.1. The edges in the chain define a total order. The order is total, since two nodes are necessarily linked to each other by a path.

4.1.2 Directed acyclic graphs

In generic programs, intermediate functions may depend, not only on the previous function output, but on the outputs of several different functions. Such dependencies are best expressed using graphs.

A directed graph $\cG = (\cV, \cE)$ is defined by a set of vertices or nodes $\cV$ and a set of edges $\cE$ defining directed dependencies between vertices. An edge $(i,j) \in \cE$ is an ordered pair of vertices $i \in \cV$ and $j \in \cV$. It is also denoted $i \rightarrow j$, to indicate that $j$ depends on $i$. For representing inputs and outputs, it will be convenient to use incoming half-edges $\rightarrow j$ and outgoing half-edges $i \rightarrow$.

In a graph $\cG= (\cV, \cE)$, the parents of a vertex $j$ are the set of nodes pointing to $j$, denoted $\parent(j) \coloneqq \{i: i \rightarrow j\}$. The children of a vertex $i$ are the set of nodes $i$ is pointing to, that is, $\child(i) \coloneqq \{j \colon i \rightarrow j\}$. Vertices without parents are called roots and vertices without children are called leaves.

A path from $i$ to $j$ is defined by a sequence of vertices $j_1, \ldots, j_m$, potentially empty, such that $i \rightarrow j_1 \rightarrow \ldots \rightarrow j_m \rightarrow j$. An acyclic graph is a graph such that there exists no vertex $i$ with a path from $i$ to $i$. A directed acyclic graph (DAG) is a graph that is both directed and acyclic.

The edges of a DAG define a partial order of the vertices, denoted $i \preceq j$ if there exists a path from $i$ to $j$. The order is partial, since two vertices may not necessarily be linked to each other by a path. Nevertheless, we can define a total order called a topological order: any order such that $i \leq j$ if and only if there is no path from $j$ to $i$.

4.1.3 Computer programs as DAGs

We assume that a program defines a mathematically valid function (a.k.a. pure function): the program should return identical values for identical arguments and should not have any side effects. We also assume that the program halts, i.e., that it terminates in a finite number of steps. As such a program is made of a finite number of intermediate functions and intermediate variables, the dependencies between functions and variables can be expressed using a directed acyclic graph (DAG). Without loss of generality, we make the following simplifying assumptions:

1. There is a single input $\s_0 \in \cS_0$.

2. There is a single output $\s_K \in \cS_K$.

3. Each intermediate function $f_k$ in the program outputs a single variable $\s_k \in \cS_k$.

We number the nodes as $\cV \coloneqq \{0, 1, \dots, K\}$. Node $0$ is the root, corresponding to the input $\s_0 \in \cS_0$. Node $K$ is the leaf, corresponding to the final output $\s_K \in \cS_K$. Because of the third assumption above, apart from $\s_0$, each variable $\s_k$ is in bijection with a function $f_k$. Therefore, node $0$ represents the input $\s_0$, and nodes $1, \dots, K$ represent both a function $f_k$ and an output variable $\s_k$.

Edges in the DAG represent dependencies. The parents $i_1, \dots, i_{p_k} \coloneqq \parent(k)$ of node $k$, where $p_k \coloneqq |\parent(k)|$, indicate the variables $\s_{\parent(k)} \coloneqq \s_{i_1}, \dots, \s_{i_{p_k}}$ that the function $f_k$ needs to perform its computation. Put differently, the parents $i_1, \dots, i_{p_k}$ indicate the functions $f_{i_1}, \ldots, f_{i_{p_k}}$ that need to be evaluated, prior to evaluating $f_k$. An example of a computation graph in our formalism is presented in Fig. 4.3.

Executing a program

To execute a program, we need to ensure that we evaluate the intermediate functions in the correct order. Therefore, we assume that the nodes $0, 1, \dots, K$ are in a topological order (if this is not the case, we need to perform a topological sort first). We can then execute a program by evaluating for $k \in [K]$ $$\begin{align*} \s_k \coloneqq f_k(\s_{\parent(k)}) \coloneqq f_k(\s_{i_1}, \dots, \s_{i_{p_k}}) \in \cS_k. \end{align*}$$ Note that we can either view $f_k$ as a single-input function of $\s_{\parent(k)}$, which is a tuple of elements, or as a multi-input function of $\s_{i_1}, \dots, \s_{i_{p_k}}$. The two views are essentially equivalent.

The procedure for executing a program is summarized in Algorithm 4.1.

Dealing with multiple program inputs or outputs

When a program has multiple inputs, we can always group them into $\s_0 \in \cS_0$ as $\s_0 = (\s_{0,1}, \dots, \s_{0,N_0})$ with $\cS_0 = (\cS_{0,1} \times \dots \times \cS_{0,N_0})$, since later functions can always filter out what elements of $\s_0$ they need. Likewise, if an intermediate function $f_k$ has multiple outputs, we can always group them as a single output $\s_k = (\s_{k,1},\dots,\s_{k,N_k})$ with $\cS_k = (\cS_{k,1} \times \dots \times \cS_{k,N_k})$, since later functions can filter out the elements of $\s_k$ that they need.

Alternative representation: bipartite graphs

In our formalism, because a function $f_k$ always has a single output $\s_k$, a node $k$ can be seen as representing both the variable $\s_k$ and the function $f_k$. Alternatively, as shown in Fig. 4.4, we can represent variables and functions as separate nodes, that is, using a bipartite graph. This formalism is akin to factor graphs (Frey et al., 1997; Loeliger, 2004) used in probabilistic modeling, but with directed edges. One advantage of this formalism is that it allows functions to explicitly have multiple outputs. We focus on our formalism for simplicity.

4.1.4 Arithmetic circuits

Arithmetic circuits are one of the simplest examples of computation graph, originating from computational complexity theory. Formally, an arithmetic circuit over a field $\FF$, such as the reals $\RR$, is a directed acyclic graph (DAG) whose root nodes are elements of $\FF$ and whose functions $f_k$ are either $+$ or $\times$. The latter are often called gates. Contrary to the general computation graph case, because each $f_k$ is either $+$ or $\times$, it is important to allow the graph to have several root nodes. Root nodes can be either variables or constants, and should belong to $\FF$.

Arithmetic circuits can be used to compute polynomials. There are potentially multiple arithmetic circuits for representing a given polynomial. One important question is then to find the most efficient arithmetic circuit for computing a given polynomial. To compare arithmetic circuits representing the same polynomial, an intuitive notion of complexity is the circuit size, as defined below.

For more information on arithmetic circuits, we refer the reader to the monograph of Chen et al. (2011).

4.2 Feedforward networks

A feedforward network can be seen as a computation chain with parameterized functions $f_k$, $$\begin{align*} \sv_0 &\coloneqq \xv \\ \sv_1 &\coloneqq f_1(\sv_0, \wv_1) \\ \sv_2 &\coloneqq f_2(\sv_1, \wv_2) \\ &\vdots \\ \sv_K &\coloneqq f_K(\sv_{K-1}, \wv_K), \end{align*}$$ for a given input $\x \in \cX$ and learnable parameters $\w_1, \ldots, \w_K \in \cW_1 \times \dots \times \cW_K$. Each function $f_k$ is called a layer and each $\sv_k \in \cS_k$ can be seen as an intermediate representation of the input $\xv$. The dimensionality of $\cS_k$ is known as the width (or number of hidden units) of layer $k$. A feedforward network defines a function $\s_K \eqqcolon f(\xv, \wv)$ from $\cX \times \cW$ to $\cS_K$, where $\wv \coloneqq (\wv_1, \dots, \wv_K) \in \cW \coloneqq \cW_1 \times \ldots \times \cW_K$.

Given such a parameterized program, we can learn the parameters by adjusting $\wv$ to fit some data. For instance, given a dataset of $(\xv_i, \yv_i)$ pairs, we may minimize the squared loss $\|\yv_i - f(\x_i, \w)\|_2^2$ on average over the data, w.r.t. $\wv$. The minimization of such a loss requires accessing its gradients with respect to $\w$.

4.3 Multilayer perceptrons

4.3.1 Combining affine layers and activations

In the previous section, we did not specify how to parametrize the feedforward network. A typical parametrization, called the multilayer perceptron (MLP), uses fully-connected (also called dense) layers of the form $$\sv_k = f_k(\sv_{k-1}, \wv_k) \coloneqq a_k(\W_k \sv_{k-1} + \bv_k),$$ where we defined the tuple $\wv_k \coloneqq (\W_k, \bv_k)$ and where we assumed that $\W_k$ and $\bv_k$ are a matrix and a vector of appropriate size. We can further decompose the layer into two functions. The function $\sv \mapsto \W_k \sv + \bv_k$ is called an affine layer. The function $\vv \mapsto a_k(\vv)$ is a parameter-free nonlinearity, often called an activation function (see Section 4.4). The value $\alphav_k \coloneqq \W_k \sv_{k-1} + \bv_k$ is often called the pre-activation value and the value $a_k(\alphav_k)$ is the activation value.

More generally, we may replace the matrix-vector product $\W_k \sv_{k-1}$ by any parametrized linear function of $\sv_{k-1}$. For example, convolutional layers use the convolution of an input $\sv_{k-1}$ with some filters $W_k$, seen as a linear map.

4.3.2 Link with generalized linear models

When the depth is $K=1$ (only one layer), the output of an MLP is $$\s_1 = a_1(\W_1 \xv + \bv_1).$$ This is called a generalized linear model (GLM); see Section 3.4. Therefore, MLPs include GLMs as a special case. In particular, when $a_1$ is the softargmax (see Section 4.4), we obtain (multiclass) logistic regression. For general depth $K$, the output of an MLP is $$\s_K = a_K(\W_K \sv_{K-1} + \bv_K).$$ This can be seen as a GLM on top of learned representation $\sv_{K-1}$ of the input $\xv$. This is the main appeal of MLPs: they learn the feature representation and the output model at the same time! We will see that MLPs can also be used as subcomponents in other architectures.

4.4 Activation functions

As we saw in Section 4.3, feedforward networks typically use an activation function $a_k$ at each layer. In this section, we present various nonlinearities from scalar to scalar or from vector to scalar. We also present probability mappings that can be used as such activations.

4.4.1 ReLU and softplus

Many activations are scalar-to-scalar functions, but they can also be applied to vectors in an element-wise fashion. The ReLU (rectified linear unit) is a popular nonlinearity defined as the non-negative part of its input $$\mathrm{relu}(u) \coloneqq \max(u, 0) = \begin{cases} u, & u \ge 0 \\ 0, & u < 0 \end{cases}.$$ It is a piecewise linear function and includes a kink at $u=0$. A multilayer perceptron with ReLU activations is called a rectifier neural network. The layers take the form $$\sv_k = \mathrm{relu}(\Av_k \sv_{k-1} + \bv_k),$$ where the ReLU is applied element-wise. The ReLU can be replaced with a smooth approximation (i.e., without kinks), called the softplus $$\mathrm{softplus}(u) \coloneqq \log(1 + e^u).$$ Unlike the ReLU, it is always strictly positive. Other smoothed variants of the ReLU are possible, see Section 13.4.

4.4.2 Max pooling and log-sum-exp

Many activations are vector-to-scalar functions: they reduce vectors to a scalar value. This scalar value can be seen as a statistic, “summarizing” the vector.

Max pooling

An example of vector-to-scalar reduction is the maximum value, also known as max pooling. Given a vector $\u \in \R^M$, it is defined as $$\max(\u) \coloneqq \max_{j \in [M]} u_j.$$

Log-sum-exp as a soft maximum

Another example of vector-to-scalar reduction is the log-sum-exp, $$\lse(\u) \coloneqq \mathrm{softmax}(\u) \coloneqq \log \sum_{j=1}^M e^{u_j}.$$ As illustrated in Fig. 4.5, it is known to behave like a soft maximum. The log-sum-exp can be seen as a generalization of the softplus, as we have for all $u \in \RR$ $$\lse((u, 0)) = \mathrm{softplus}(u).$$ A numerically stable implementation of the log-sum-exp is given by $$\lse(\u) = \lse(\u - c\ones) + c,$$ where $c \coloneqq \max_{j \in [M]} u_j$.

More generally, we can introduce a temperature parameter $\gamma > 0$ $$\lse_\gamma(\u) = \gamma \cdot \lse(\u / \gamma).$$ It can be shown that for all $\u \in \RR^M$, $$\max(\u) \le \lse_\gamma(\u) \le \max(\u) + \gamma \cdot \log(M).$$ Therefore, $\lse_\gamma(\u) \to \max(\u)$ as $\gamma \to 0$. Other definitions of soft maximum are possible; see Section 13.5.

Log-sum-exp as a log-domain sum

Besides its use as a soft maximum, the log-sum-exp often arises for computing sums in the log domain. Indeed, suppose we want to compute $s \coloneqq \sum_{i=1}^M u_i$, where $u_i > 0$. If we define $\tilde{u}_i \coloneqq \log u_i$ and $\tilde{s} \coloneqq \log s$, we then have $$\tilde{s} = \log \sum_{i=1}^M \exp(\tilde{u}_i).$$ Written differently, we have the identity $$\log\left(\sum_{i=1}^M u_i\right) = \lse(\log(\u)).$$ We can therefore see the log-sum-exp as the sum counterpart of the identity for products $$\log\left(\prod_{i=1}^M u_i \right) = \sum_{i=1}^M \log(u_i).$$ As an example, we use the log-sum-exp to perform the forward-backward algorithm in the log-domain in Section 10.7.1.

4.4.3 Sigmoids: binary step and logistic functions

Oftentimes, we want to map a real value to a number in $[0,1]$, that can represent the probability of an event. For that purpose, we generally use sigmoids. A sigmoid is a function with a characteristic “S”-shaped curve. These functions are scalar-to-scalar probability mappings: they are used to squash real values to $[0,1]$.

Binary step function

An example is the binary step function, also known as Heaviside step function, $$\mathrm{step}(u) \coloneqq \begin{cases} 1, & u \ge 0 \\ 0, & u < 0 \end{cases}.$$ It is a mapping from $\R$ to $\{0, 1\}$. Unfortunately, it has a discontinuity: a jump in its graph at $u=0$. Moreover, because the function is constant at all other points, it has zero derivative at these points, which makes it difficult to use as part of a neural network trained with backpropagation.

Logistic function

A better sigmoid is the logistic function, which is a mapping from $\R$ to $(0, 1)$ and is defined as $$\begin{align*} \mathrm{logistic}(u) &\coloneqq \frac{1}{1 + e^{-u}} \\ &= \frac{e^u}{1 + e^u} \\ &= \frac{1}{2} + \frac{1}{2} \tanh\left(\frac{u}{2}\right). \end{align*}$$ It maps $(-\infty, 0)$ to $(0, 0.5)$, $[0, +\infty)$ to $[0.5, 1)$ and it satisfies $\mathrm{logistic}(0) = 0.5$. It can therefore be seen as mapping from real values to probability values. The logistic can be seen as a differentiable approximation to the discontinuous binary step function $\mathrm{step}(u)$. The logistic function can be shown to be the derivative of softplus, i.e., for all $u \in \RR$ $$\mathrm{softplus}'(u) = \mathrm{logistic}(u).$$ Two important properties of the logistic function are that for all $u \in \RR$ $$\mathrm{logistic}(-u) = 1 - \mathrm{logistic}(u)$$ and $$\begin{align*} \mathrm{logistic}'(u) &= \mathrm{logistic}(u) \cdot \mathrm{logistic}(-u) \\ &= \mathrm{logistic}(u) \cdot (1 - \mathrm{logistic}(u)). \end{align*}$$ Other sigmoids are possible; see Section 13.6.

4.4.4 Probability mappings: argmax and softargmax

It is often useful to transform a real vector into a vector of probabilities. This is a mapping from $\R^M$ to the probability simplex, defined by $$\triangle^M \coloneqq \left\{\piv \in \R^M \colon \forall j \in [M],\ \pi_j \geq 0,\ \sum_{j=1}^M \pi_j= 1\right\}.$$ Two examples of such vector-to-vector probability mappings are the argmax and the softargmax.

Argmax

The argmax operator is defined by $$\mathrm{argmax}(\u) \coloneqq \phi\left(\argmax_{j \in [M]} u_j\right) \in \{\e_1, \dots, \e_M\},$$ where $\phi(j)$ denotes the one-hot encoding of an integer $j \in [M]$, that is, $$\phi(j) \coloneqq (0, \ldots, 0, \underbrace{1}_j, 0, \ldots, 0) = \e_j \in \{0,1\}^M.$$ This mapping puts all the probability mass onto a single coordinate (in case of ties, we pick a single coordinate arbitrarily). Unfortunately, this mapping is a discontinuous function.

Softargmax

As a differentiable everywhere relaxation, we can use the softargmax defined by $$\mathrm{softargmax}(\u) \coloneqq \frac{\exp(\u)}{\sum_{j=1}^M \exp(u_j)} \in \mathrm{relint}(\triangle^M).$$ This operator is commonly known in the literature as softmax but this is a misnomer: this operator really defines a differentiable relaxation of the argmax. The output of the softargmax belongs to the relative interior of the probability simplex $\mathrm{relint}(\triangle^M) = \{\piv \in \triangle^M \colon \piv > \zeros\}$, meaning that it can never reach the borders of the simplex. If we denote $\piv = \mathrm{softargmax}(\u)$, this means that $\pi_j \in (0,1)$, that is, $\pi_j$ can never be exactly $0$ or $1$. The $\mathrm{softargmax}$ is the gradient of log-sum-exp, $$\nabla \mathrm{logsumexp}(\u) = \mathrm{softargmax}(\u).$$ The $\mathrm{softargmax}$ can be seen as a generalization of the logistic function, as we have for all $u \in \RR$ $$[\mathrm{softargmax}((u, 0))]_1 = \mathrm{logistic}(u).$$

4.5 Normalization layers

Intermediate states in neural networks, such as activations, can often attain a wide range of different values, potentially making it difficult for gradient descent to converge. To remedy this issue, we can introduce normalization layers at suitable locations in the network. In this section, we present the two most popular ones: batch normalization and layer normalization.

4.5.1 Batch normalization

Suppose we are given a batch of intermediate variables (such as activations or states) $\s_1,\dots,\s_B \in \RR^D$, where $\s_i \coloneqq (s_{i,1},\dots, s_{i,D})$, obtained by applying some function to $B$ samples drawn from the training set (we omit the dependency on the layer index $k$ for clarity). In batch normalization (Ioffe and Szegedy, 2015), we normalize the values by calculating the standard score (a.k.a. z-score) across batch samples, $$\begin{align*} \mu_{\blue{j}} &\coloneqq \frac{1}{B} \sum_{\blue{i=1}}^{\blue{B}} s_{i,j} \quad \forall j \in [D] \\ \sigma_{\blue{j}}^2 &\coloneqq \frac{1}{B} \sum_{\blue{i=1}}^{\blue{B}} (s_{i,j} - \mu_j)^2 \quad \forall j \in [D]\\ \widehat{s}_{i,j} &\coloneqq \frac{s_{i,j} - \mu_j}{\sigma_j} \quad i \in [B], j \in [D]. \end{align*}$$ Here, the means $\mu_j$ and the standard deviations $\sigma_j$ are computed for each feature $j \in [D]$ across samples $i \in [B]$ in the batch. In practice, we often add a small value $\varepsilon > 0$ to $\sigma_j$ to avoid division by zero or numerical instabilities. Moreover, we often rescale the values as $$\widetilde{s}_{i,j} \coloneqq \beta_j + \gamma_j \widehat{s}_{i,j} \quad i \in [B], j \in [D],$$ where the means $\betav \coloneqq (\beta_1, \dots, \beta_D)$ and standard deviations $\gammav \coloneqq (\gamma_1, \dots, \gamma_D)$ are learnable parameters.

One issue with batch normalization is that the means $\mu_j$ and standard deviations $\sigma_j$ cannot be computed at inference time, as there is no notion of training batch (a single sample would lead to a variance of $0$). To address this issue, we can estimate means $\widehat{\mu}_j$ and standard deviations $\widehat{\sigma}_j$ across the whole training set during the course of training, usually using a running average. A practical batch normalization implementation therefore needs to maintain $D$ mean and standard deviation statistics, so as to be able to use them at inference time.

4.5.2 Layer normalization

As an alternative, in layer normalization (Ba et al., 2016), we instead standardize the values by summing across features, $$\begin{align*} \mu_{\blue{i}} &\coloneqq \frac{1}{D} \sum_{\blue{j=1}}^{\blue{D}} s_{i,j} \quad \forall i \in [B] \\ \sigma_{\blue{i}}^2 &\coloneqq \frac{1}{D} \sum_{\blue{j=1}}^{\blue{D}} (s_{i,j} - \mu_i)^2 \quad \forall i \in [B] \\ \widehat{s}_{i,j} &\coloneqq \frac{s_{i,j} - \mu_i}{\sigma_i} \quad i \in [B], j \in [D]. \end{align*}$$ This time, the means $\mu_i$ and the standard deviations $\sigma_i$ are computed for each sample $i \in [B]$ across features $j \in [D]$ (as before, we often add a small value $\varepsilon$ to $\sigma_i$). Similarly to batch normalization, we often rescale the values as $$\widetilde{s}_{i,j} \coloneqq \beta_j + \gamma_j \widehat{s}_{i,j} \quad i \in [B], j \in [D],$$ where the means $\betav \coloneqq (\beta_1, \dots, \beta_D)$ and standard deviations $\gammav \coloneqq (\gamma_1, \dots, \gamma_D)$ are learnable parameters. A key advantage of layer normalization compared to batch normalization is that it is well defined at inference time, since it is applied on a per-sample basis and does not rely on the notion of a training batch. As a result, we can view layer normalization as a function that to any $\s_i \in \RR^D$ (regardless of whether it is part of a batch or not) associates $$\widetilde{\s_i} \coloneqq \mathrm{LayerNorm}(\s_i).$$

4.6 Residual neural networks

We now discuss another feedforward network parametrization: residual neural networks. Consider a feedforward network with $K+1$ layers $f_1$, $\dots$, $f_K$, $f_{K+1}$. Surely, as long as $f_{K+1}$ can exactly represent the identity function, the set of functions that this feedforward network can express should be a superset of the functions that $f_1$, $\dots$, $f_K$ can express. In other words, depth should in theory not hurt the expressive power of feedforward networks. Unfortunately, the assumption that each $f_k$ can exactly represent the identity function may not hold in practice. This means that deeper networks can sometimes be more difficult to train than shallower ones, making the accuracy saturate or degrade as a function of depth.

The key idea of residual neural networks (He et al., 2016) is to design layers $f_k$, called residual blocks, that make it easier to represent the identity function. Formally, a residual block takes the form $$\sv_k = f_k(\sv_{k-1}, \wv_k) \coloneqq \sv_{k-1} + h_k(\sv_{k-1}, \wv_k).$$ The function $h_k$ is called residual, since it models the difference $\sv_k - \sv_{k-1}$. The addition with $\sv_{k-1}$ is often called a skip connection. As long as it is easy to adjust $\wv_k$ so that $h_k(\sv_{k-1}, \wv_k) = \zeros$, $f_k$ can freely become the identity function. For instance, if we use $$h_k(\sv_{k-1}, \wv_k) \coloneqq \Cv_k a_k(\W_k \sv_{k-1} + \bv_k) + \dv_k,$$ where $\wv_k \coloneqq (\W_k, \bv_k, \Cv_k, \dv_k)$, it suffices to set $\Cv_k$ and $\dv_k$ to a zero matrix and vector. Residual blocks are known to remedy the so-called vanishing gradient problem.

Many papers and software packages include an additional activation and instead define the residual block as $$\sv_k = f_k(\sv_{k-1}, \wv_k) \coloneqq a_k(\sv_{k-1} + h_k(\sv_{k-1}, \wv_k)),$$ where $a_k$ is typically chosen to be the ReLU activation. Whether to include this additional activation or not is essentially a modelling choice. In practice, residual blocks may also include additional operations such as batch norm and convolutional layers.

4.7 Recurrent neural networks

Recurrent neural networks (RNNs) are a class of neural networks that operate on sequences of vectors, either as input, output or both. Their actual parametrization depends on the setup but the core idea is to maintain a state vector that is updated from step to step by a recursive function that uses shared parameters across steps. Unrolling this recursion defines a valid computational graph, as we will see in Chapter 8. We distinguish between the following setups illustrated in Fig. 4.7:

• Vector to sequence (one to many):
  $f^d \colon \R^D \times \R^P \to \R^{L \times M}$

• Sequence to vector (many to one):
  $f^e \colon \R^{L \times D} \times \R^P \to \R^M$

• Sequence to sequence (many to many, aligned):
  $f^a \colon \R^{L \times D} \times \R^P \to \R^{L \times M}$

• Sequence to sequence (many to many, unaligned):
  $f^u \colon \R^{L \times D} \times \R^P \to \R^{L' \times M}$

where $L$ stands for length. Note that we use the same number of parameters $P$ for each setup for notational convenience, but this of course does not need to be the case. Throughout this section, we use the notation $\p_{1:L} \coloneqq (\p_1, \dots, \p_L)$ for a sequence of $L$ vectors.

4.7.1 Vector to sequence

In this setting, we define a decoder function $\p_{1:L} = f^d(\xv, \wv)$ from an input vector $\x \in \R^D$ and parameters $\w \in \R^P$ to an output sequence $\p_{1:L} \in \R^{L \times M}$. This is for instance useful for image caption generation, where a sentence (a sequence of word embeddings) is generated from an image (a vector of pixels). Formally, we may define $\p_{1:L} \coloneqq f^d(\x, \w)$ through the recursion $$\begin{aligned} \z_l &\coloneqq g(\x, \z_{l-1}, \w_g) \quad l \in [L] \\ \p_l &\coloneqq h(\z_l, \w_h) \quad l \in [L]. \end{aligned}$$ where $\wv \coloneqq (\w_g, \w_h, \z_0)$. The goal of $g$ is to update the current decoder state $\z_l$ given the input $\x$, and the previous decoder state $\z_{l-1}$. The goal of $h$ is to generate the output $\p_l$ given the current decoder state $\z_l$. Importantly, the parameters of $g$ and $h$ are shared across steps. Typically, $g$ and $h$ are parametrized using one-hidden-layer MLPs. Note that $g$ has multiple inputs; we discuss how to deal with such cases in Section 4.3.

4.7.2 Sequence to vector

In this setting, we define an encoder function $\p = f^e(\x_{1:L}, \wv)$ from an input sequence $\x_{1:L} \in \R^{L \times D}$ and parameters $\w \in \R^P$ to an output vector $\p \in \R^M$. This is for instance useful for sequence classification, such as sentiment analysis. Formally, we may define $\p \coloneqq f^e(\x_{1:L}, \w)$ using the recursion $$\begin{aligned} \s_l &\coloneqq \gamma(\x_l, \s_{l-1}, \w_\gamma) \quad l \in [L] \\ \p &= \mathrm{pooling}(\s_{1:L}) \end{aligned}$$ where $\w \coloneqq (\w_\gamma, \s_0)$. The goal of $\gamma$ is similar to $g$, except that it updates encoder states and does not take previous predictions as input. The pooling function is typically parameter-less. Its goal is to reduce a sequence to a vector. Examples include using the last state, the average of states and the coordinate-wise maximum of states.

4.7.3 Sequence to sequence (aligned)

In this setting, we define a function $\p_{1:L} = f^a(\x_{1:L}, \wv)$ from an input sequence $\x_{1:L} \in \R^{L \times D}$ and parameters $\w \in \R^P$ to an output sequence $\p_{1:L} \in \R^{L \times M}$, which we assume to be of the same length. An example of application is part-of-speech tagging, where the goal is to assign each word $\x_l$ to a part-of-speech (noun, verb, adjective, etc). Formally, we may define $\p_{1:L} = f^a(\x_{1:L}, \w)$ as $$\begin{aligned} \s_l &\coloneqq \gamma(\x_l, \s_{l-1}, \w_\gamma) \quad l \in [L] \\ \p_l &= h(\s_l, \w_h) \quad l \in [L] \\ \end{aligned}$$ where $\wv \coloneqq (\wv_\gamma, \wv_h, \sv_0)$. The functions $\gamma$ and $h$ are similar as before.

4.7.4 Sequence to sequence (unaligned)

In this setting, we define a function $\p_{1:L'} = f^u(\x_{1:L}, \wv)$ from an input sequence $\x_{1:L} \in \R^{L \times D}$ and parameters $\w \in \R^P$ to an output sequence $\p_{1:L'} \in \R^{L' \times M}$, which potentially has a different length. An example of application is machine translation, where the sentences in the source and target languages do not necessarily have the same length. Typically, $\p_{1:L'} = f^u(\x_{1:L}, \w)$ is defined as the following two steps $$\begin{aligned} \c &\coloneqq f^e(\x_{1:L}, \w_e) \\ \p_{1:L'} &\coloneqq f^d(\c, \w_d) \end{aligned}$$ where $\w \coloneqq (\w_e, \w_d)$, and where we reused the previously-defined encoder $f^e$ and decoder $f^d$. Putting the two steps together, we obtain $$\begin{aligned} \s_l &\coloneqq \gamma(\x_l, \s_{l-1}, \w_\gamma) \quad l \in [L] \\ \c &= \mathrm{pooling}(\s_{1:L}) \\ \z_l &\coloneqq g(\c, \p_{l-1}, \z_{l-1}, \w_g) \quad l \in [L'] \\ \p_l &\coloneqq h(\z_l, \w_h) \quad l \in [L']. \end{aligned}$$

This architecture is aptly named the encoder-decoder architecture. Note that we denoted the length of the target sequence as $L'$. However, in practice, the target length can be input dependent and is often not known ahead of time. To deal with this issue, the vocabulary (of size $D$ in our notation) is typically augmented with an “end of sequence” (EOS) token so that, at inference time, we know when to stop generating the output sequence. One disadvantage of this encoder-decoder architecture, however, is that all the information about the input sequence is contained in the context vector $\c$, which can therefore become a bottleneck.

4.8 Transformers

Transformers (Vaswani et al., 2017) are one of the most successful recent developments in deep learning. In this section, we review Transformers, component by component.

4.8.1 Attention

The goal of an attention layer is to map a sequence of inputs $\v_1,\dots,\v_L \in \RR^{D_v}$ to a sequence of outputs $\u_1,\dots,\u_L \in \RR^{D_v}$, of same dimension. A natural idea is to define each output element $\u_i$ using a linear combination of the input elements, $$\u_i \coloneqq \sum_{j=1}^L a_{i,j} \v_j \in \RR^{D_v}.$$ We typically use a convex combination: we assume that the combination weights are such that $\a_i \coloneqq (a_{i,1},\dots,a_{i,L}) \in \triangle^L$. This ensures that increasing a coefficient $a_{i,j}$ is made at the expense of decreasing another coefficient $a_{i,j'}$, for $j \neq j'$. Let us form the matrices $\V \in \RR^{L \times D_v}$ and $\U \in \RR^{L \times D_v}$ by stacking $\v_1,\dots,\v_L$ and $\u_1,\dots,\u_L$, seen as row vectors. Let us also form the attention matrix $\A \in \triangle^{L \times L}$ gathering the entries $a_{i,j}$, where $\triangle^{L \times L}$ denotes the set of row-wise stochastic $L \times L$ matrices. Then, we can rewrite attention succinctly as $$\U = \A \V \in \RR^{L \times D_v}.$$ Following Section 6.2, we can view attention as a soft dictionary lookup. From this perspective, the matrix $\V \in \RR^{L \times D_v}$ plays the role of dictionary values, and the attention matrix can be defined as $$\A \coloneqq \mathrm{softargmax}(\Q \K^\top) \in \triangle^{L \times L},$$ where $\Q \in \RR^{L \times D_k}$ and $\K \in \RR^{L \times D_k}$ play the roles of queries and dictionary keys, respectively. Intuitively, $\Q\K^\top \in \RR^{L \times L}$ can be seen as a similarity matrix containing the similarities between queries and dictionary keys. Putting everything together, we can define attention as $$\mathrm{Attention}(\Q, \K, \V) \coloneqq \mathrm{softargmax}\left(\Q \K^\top\right)\V \in \RR^{L \times D_v}.$$ In masked attention, we additionally incorporate a mask $\M \in \RR^{L \times L}$, $$\mathrm{Attention}(\Q, \K, \V; \M) \coloneqq \mathrm{softargmax}\left((\Q \K^\top) \circ \M\right)\V \in \RR^{L \times D_v},$$ where $\circ$ denotes the Hadamard product (element-wise multiplication). The mask can be used to force some attention weights $a_{i,j}$ to be zero, by setting the corresponding mask entry $m_{i,j}$ to $-\infty$. For instance, in decoder-only architectures (Section 4.8.8), the mask will prove useful to define causal attention for autoregressive models.

4.8.2 Self-attention

Suppose we are given a sequence of feature vectors $\x_1, \dots, \x_L \in \RR^D$, that we gather as a matrix $\X \in \RR^{L \times D}$. To define the attention weights $a_{i,j}$, a natural idea is to consider the similarity between $\x_i$ and $\x_j$, as measured by the inner product $\langle \x_i, \x_j \rangle$. To ensure that $\a_i \coloneqq (a_{i,1},\dots,a_{i,L}) \in \triangle^L$, we can then define $$a_{i,j} \coloneqq \frac{\exp(\langle \x_i, \x_j \rangle)}{ \sum_{j'=1}^L \exp(\langle \x_i, \x_{j'} \rangle)} \in (0,1).$$ In matrix notation, this can be written $$\A \coloneqq \mathrm{softargmax}(\X \X^\top) \in \triangle^{L \times L},$$ where $\mathrm{softargmax}$ is applied in a row-wise fashion. The matrix $\X \X^\top \in \RR^{L \times L}$ is the Gram matrix associated with the row vectors $\x_1, \dots, \x_L$. In the notation of the previous section, this corresponds to using $\mathrm{Attention}(\Q, \K, \V)$ with $\Q = \K = \V = \X$. In other words, the elements of the sequence “pay attention” to each other. This is called self-attention.