Chapter 1 An Informal Introduction

As discussed in Section 1.2.1, a central task of intelligence is to learn what is predictable in sequences of observations. The simplest class of predictable sequences—or signals—are those generated by a linear time-invariant (LTI) process:

where $*$ is the convolution operation, $z$ is the input and $h$ is the impulse response function.¹¹¹¹11Typically, $h$ is assumed to have certain desirable properties, such as finite length or a band-limited spectrum. Here $\epsilon[n]$ denotes additive observation noise. Given the input process $\{z[n]\}$ and observations of the output process $\{x[n]\}$, the goal is to find the optimal $h[n]$ such that $\hat{x}[n]=h[n]*z[n]$ predicts $x[n]$ optimally. Prediction quality (i.e., goodness) is measured by the mean squared error (MSE):

The optimal solution $h[n]$ is called a (denoising) filter. Norbert Wiener—who also initiated the Cybernetics movement—studied this problem in the 1940s and derived an elegant closed-form solution known as the Wiener filter [Wie42, Wie49]. This result, also known as least-variance estimation and filtering, became one of the cornerstones of signal processing. Interested readers may refer to [MKS+04, Appendix B] for a detailed derivation of this type of estimator.

The idea of denoising or filtering a dynamical system was later extended by Rudolph Kalman in the 1960s to a linear time-invariant system described by a finite-dimensional state-space model:

The problem is to estimate the system state $\bm{z}[n]$ from noisy observations of the form

where $\bm{w}$ is (white) noise. The optimal causal¹²¹²12This means the estimator can use only observations up to the current time step $n$. The Kalman filter is always causal, whereas the Wiener filter need not be. state estimator that minimizes the minimum-MSE (MMSE) prediction error

is given in closed form by the so-called Kalman filter [Kal60]. This result is a cornerstone of modern control theory because it enables estimation of a dynamical system’s state from noisy observations. One can then introduce linear state feedback, for example $\bm{u}[n]=\bm{F}\hat{\bm{z}}[n]$, and render the closed-loop system fully autonomous, as shown in Equation 1.2.13. Interested readers may refer to [MKS+04, Appendix B] for a detailed derivation of the Kalman filter.

To derive the Kalman filter, the system parameters $\bm{A},\bm{B},\bm{C}$ are assumed to be known. If they are not given in advance, the problem becomes more challenging and is known as system identification: how to learn the parameters $\bm{A},\bm{B},\bm{C}$ from many samples of the input sequence $\{\bm{u}[n]\}$ and observation sequence $\{\bm{x}[n]\}$. This is a classic problem in systems theory. If the system is linear, the input and output sequences $\{\bm{u}[n],\bm{x}[n]\}$ jointly lie on a certain low-dimensional subspace¹³¹³13which has the same dimension as the order of the state-space model (1.3.3).. Hence, the identification problem is essentially equivalent to identifying this low-dimensional subspace [VM96, LV09, LV10].

Note that the above problems have two things in common: first, the noise-free sequences or signals are assumed to be generated by an explicit family of parametric models; second, these models are essentially linear. Conceptually, let $\bm{x}_{o}$ be a random variable whose “true” distribution is supported on a low-dimensional linear subspace, say $S$. To a large extent, the Wiener filter and Kalman filter both try to estimate such an $\bm{x}_{o}$ from its noisy observations:

where $\bm{\epsilon}$ is typically a random Gaussian noise (or process). Hence, their solutions rely on identifying a low-dimensional linear subspace that best fits the observed noisy data. By projecting the data onto this subspace, one obtains the optimal denoising operations, all in closed form.

From the above problems in classical signal processing and system identification, we see that the main task behind all these problems is to learn a single low-dimensional linear subspace from noisy observations. Mathematically, we may model such a structure as

where $\bm{\epsilon}\in\mathbb{R}^{D}$ is small random noise. Figure 1.10 illustrates such a distribution with two principal components.

The problem is to find the subspace basis $\bm{U}$ from many samples of $\bm{x}$. A typical approach is to minimize the projection error onto the subspace:

This is essentially a denoising task: once the basis $\bm{U}$ is correctly found, we can denoise the noisy sample $\bm{x}$ by projecting it onto the low-dimensional subspace spanned by $\bm{U}$:

If the noise is small and the low-dimensional subspace $\bm{U}$ is correctly learned, we expect $\bm{x}\approx\hat{\bm{x}}$. Thus, PCA is a special case of a so-called “auto-encoding” scheme, which encodes the data by projecting it into a lower-dimensional space, and decodes a lower-dimensional code by it into the original space:

Because of the simple data structure, the encoder $\mathcal{E}$ and decoder $\mathcal{D}$ both become simple linear operators (projecting and lifting).

This classic problem in statistics is known as principal component analysis (PCA). It was first studied by Pearson in 1901 [Pea01] and later independently by Hotelling in 1933 [Hot33]. The topic is systematically summarized in the classic book [Jol86, Jol02]. One may also explicitly assume the data $\bm{x}$ is distributed according to a single low-dimensional Gaussian:

which is equivalent to assuming that $\bm{z}$ in the PCA model (1.3.7) is a standard normal distribution. This problem is known as probabilistic PCA [TB99] and has the same computational solution as PCA.

In this book, we revisit PCA in Chapter 2 from the perspective of learning a low-dimensional distribution. Our goal is to use this simple and idealistic model to convey some of the most fundamental ideas for learning a compact representation of a low-dimensional distribution, including the important notions of compression via denoising and auto-encoding for a consistent representation.

Independent component analysis (ICA) was originally proposed by [BJC85] as a classic model for learning a good representation. In fact, it was originally proposed as a simple mathematical model for our memory. The ICA model takes a deceptively similar form to the above PCA model (1.3.7) by assuming that the observed random variable $\bm{x}$ is a linear superposition of multiple independent components $z_{i}$:¹⁴¹⁴14In PCA the “components” are the learned vectors, whereas in ICA they are scalars. This is just a difference in names and convention.

However, here the components $z_{i}$ are assumed to be independent non-Gaussian variables. For example, a popular choice is

where $\sigma_{i}$ is a Bernoulli random variable and $w_{i}$ could be a constant value or another random variable, say Gaussian.¹⁵¹⁵15Even if $w$ is Gaussian, $\sigma w$ is no longer a Gaussian variable! The ICA problem aims to identify both $\bm{U}$ and $\bm{z}$ from observed samples of $\bm{x}$. Figure 1.11 illustrates the difference between ICA and PCA.

Although the (decoding) mapping from $\bm{z}$ to $\bm{x}$ seems linear and straightforward once $\bm{U}$ and $\bm{z}$ are learned, the (encoding) mapping from $\bm{x}$ to $\bm{z}$ can be complicated and may not be represented by a simple linear mapping. Hence, ICA generally gives an auto-encoding of the form:

Thus, unlike PCA, ICA is somewhat more difficult to analyze and solve. In the 1990s, researchers such as Erkki Oja and Aapo Hyvärinen [HO97, HO00a] made significant theoretical and algorithmic contributions to ICA. In Chapter 2, we will study and provide a solution to ICA from which the encoding mapping $\mathcal{E}$ will become clear.

If $p$ in (1.3.13) is very small, the probability that any component is non-zero is small. In this case we say $\bm{x}$ is sparsely generated and concentrates on a union of linear subspaces whose dimension is $k=p\cdot d$. We may therefore extend the ICA model to a more general family of low-dimensional structures known as sparse models.

A $k$-sparse model is the set of all $k$-sparse vectors:

where $\|\cdot\|_{0}$ counts the number of non-zero entries. Thus $\mathcal{Z}$ is the union of all $k$-dimensional subspaces aligned with the coordinate axes, as illustrated in Figure 1.7 (left). A central problem in signal processing and statistics is to recover a sparse vector $\bm{z}$ from its linear observations

where $\bm{A}$ is given, typically $m<n$, and $\bm{\epsilon}$ is small noise. This seemingly benign problem is NP-hard to solve and even hard to approximate (see [WM22] for details).

Despite a rich history dating back to the eighteenth century [Bos50], no provably efficient algorithm existed for this class of problems, although many heuristic algorithms were proposed between the 1960s and 1990s. Some were effective in practice but lacked rigorous justification. A major breakthrough came in the early 2000s when mathematicians including David Donoho, Emmanuel Candés, and Terence Tao [Don05, CT05a, CT05] established a rigorous theoretical framework that characterizes precise conditions under which the sparse recovery problem can be solved effectively and efficiently via convex $\ell^{1}$ minimization:

where $\|\cdot\|_{1}$ is the sparsity-promoting $\ell^{1}$ norm of a vector and $\epsilon$ is a small constant. Any solution yields a sparse (auto) encoding

We will describe such an algorithm (and thus mapping) in Chapter 2, revealing fundamental connections between sparse coding and deep learning.¹⁶¹⁶16Similarities between sparse-coding algorithms and deep networks were noted as early as 2010 [GL10].

Conditions for $\ell^{1}$ minimization to succeed are surprisingly general: the minimum number of measurements $m$ required for a successful recovery is only proportional to the intrinsic dimension $k$. This is the compressive sensing phenomenon [Can06]. It extends to broad families of low-dimensional structures, including low-rank matrices. These results fundamentally changed our understanding of recovering low-dimensional structures in high-dimensional spaces. David Donoho, among others, celebrated this reversal as the “blessing of dimensionality” [D ̵D00], in contrast to the usual pessimistic belief in the “curse of dimensionality.” The complete theory and body of results is presented in [WM22].

The computational significance of this framework cannot be overstated. It transformed problems previously believed intractable into ones that are not only tractable but scalably solvable using extremely efficient algorithms:

The algorithms come with rigorous theoretical guarantees of correctness given precise requirements in data and computation. The deductive nature of this approach contrasts sharply with the empirical, inductive practice of deep neural networks. Yet we now know that both approaches share a common goal—pursuing low-dimensional structures in high-dimensional spaces.

Conceptually, an even harder problem than the sparse-coding problem (1.3.16) arises when the observation matrix $\bm{A}$ is unknown and must itself be learned from a set of (possibly noisy) observations $\bm{X}=[\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}]$:

Here we are given only $\bm{X}$, not the corresponding $\bm{Z}=[\bm{z}_{1},\bm{z}_{2},\ldots,\bm{z}_{n}]$ or the noise term $\bm{E}=[\bm{\epsilon}_{1},\bm{\epsilon}_{2},\ldots,\bm{\epsilon}_{n}]$, except that the $\bm{z}_{i}$ are known to be sparse. This is the dictionary learning problem, which generalizes the ICA problem (1.3.12) discussed earlier. In other words, given that the distribution of the data $\bm{X}$ is the image of a standard sparse distribution $\bm{Z}$ under a linear transform $\bm{A}$, we wish to learn both $\bm{A}$ and its “inverse” mapping $\mathcal{E}$ so as to obtain an autoencoder:

PCA, ICA, and dictionary learning all assume that the data distribution is supported on or near low-dimensional linear or piecewise-linear structures. Each method requires learning a (global or local) basis for these structures from noisy samples. In Chapter 2 we study how to identify such low-dimensional structures through these classical models. In particular, we will see that all of these low-dimensional (piecewise) linear models can be learned efficiently by the same family of fast algorithms known as power iteration [ZMZ+20]. Although these linear or piecewise-linear models are somewhat idealized for most real-world data, understanding them is an essential first step toward understanding more general low-dimensional distributions.

In the 1950s, statisticians became interested in the problem of denoising data drawn from an arbitrary distribution. Let $\bm{x}_{o}$ be a random variable with probability density function $p_{o}(\cdot)$. Suppose we observe a noisy version of $\bm{x}_{o}$:

where $\bm{g}\sim\operatorname{\mathcal{N}}(\bm{0},\bm{I})$ is standard Gaussian noise and $\sigma$ is the noise level of the observation. Let $p(\cdot)$ be the probability density function of $\bm{x}$.¹⁸¹⁸18That is, $p(\bm{x})=\int_{-\infty}^{\infty}\varphi_{\sigma}(\bm{x}-\bm{z})p_{o}(\bm{z})\mathrm{d}\bm{z}$, where $\varphi_{\sigma}$ is the density function of the Gaussian distribution $\mathcal{N}(\bm{0},\sigma^{2}\bm{I})$. Remarkably, the posterior expectation of $\bm{x}_{o}$ given $\bm{x}$ can be calculated by an elegant formula, known as Tweedie’s formula [Rob56]:¹⁹¹⁹19Herbert Robbins gave the credit for this formula to Maurice Kenneth Tweedie from their personal correspondence.

As can be seen from the formula, the function $\nabla\log p(\bm{x})$ plays a very special role in denoising the observation $\bm{x}$ here. The noise $\bm{g}$ can be explicitly estimated as

for which we only need to know the distribution $p(\cdot)$ of $\bm{x}$, not the ground truth $p_{o}(\cdot)$ for $\bm{x}_{o}$. An important implication of this result is that if we add Gaussian noise to any distribution, the denoising process can be done easily if we can somehow obtain the function $\nabla\log p(\bm{x})$.

Because this is such an important and useful result, it has been rediscovered and used in many different contexts and areas. For example, after Tweedie’s formula [Rob56], it was rediscovered a few years later by [Miy61] where it was termed “empirical Bayesian denoising.” In the early 2000s, the function $\nabla\log p(\bm{x})$ was rediscovered again in the context of learning a general distribution and was named the “score function” by Aapo Hyvärinen [Hyv05]. Its connection to (empirical Bayesian) denoising was soon recognized by [Vin11]. Generalizations to other measurement distributions (beyond Gaussian noise) have been made by Eero Simoncelli’s group [RS11]. Today, the most direct application of Tweedie’s formula and denoising is image generation via iterative denoising [KS21, HJA20].

The score has an intuitive information-theoretic and geometric interpretation. In information theory, $-\log p(\bm{x})$ corresponds to the number of bits needed to encode $\bm{x}$²⁰²⁰20at least for discrete variables, as detailed in Chapter 3.. The gradient $\nabla\log p(\bm{x})$ points toward higher-probability-density regions, as shown in Figure 1.12 (left). Moving in this direction reduces the number of bits required to encode $\bm{x}$. Thus, the operator $\nabla\log p(\bm{x})$ pushes the distribution to “shrink” toward high-density regions. Formally, one can show that the (differential) entropy

decreases under this operation (see Chapter 3 and Appendix B). With an optimal codebook, the resulting distribution achieves a lower coding rate and is thus more compressed. Repeating this denoising process indefinitely produces a distribution whose probability mass is concentrated on a support of lower dimension. For instance, the distribution $p(\bm{x})$ in Figure 1.12 (left) converges to $p^{*}(\bm{x})$ (right):²¹²¹21Strictly speaking, $p^{*}(\bm{x})$ is a generalized function: $p^{*}(\bm{x})=p^{*}(\bm{x}_{1})\delta(\bm{x}-\bm{x}_{1})+p^{*}(\bm{x}_{2})\delta(\bm{x}-\bm{x}_{2})$ with $p^{*}(\bm{x}_{1})+p^{*}(\bm{x}_{2})=1$.²²²²22Notice that in this section we discuss the process of iteratively denoising and compressing a high-entropy noise distribution until it converges to the low-entropy data distribution. As we will see in Chapter 3, this problem is dual to the problem of learning an optimal encoding for the data distribution, which is also a useful application [RAG+24].

As the distribution converges to $p^{*}(\bm{x})$, its differential entropy approaches negative infinity due to a technical difference between continuous and discrete entropy definitions. Chapter 3 resolves this using a unified rate-distortion measure.

Later in this chapter and Chapter 3, we explore how this simple denoising-compression framework unifies powerful methods for learning low-dimensional distributions in high-dimensional spaces, including natural image distributions.

Inspired by the nervous system in the brain, the first mathematical model of an artificial neuron²³²³23known as the Linear Threshold Unit, or perceptron. was proposed by Warren McCulloch²⁴²⁴24a professor of psychiatry at the University of Chicago at the time and Walter Pitts in 1943 [MP43]. It describes the relationship between the input $x_{i}$ and output $o_{j}$ as:

where $\varphi(\cdot)$ is some nonlinear activation, typically modeled by a threshold function. This model is illustrated in Figure 1.13. As we can see, this form already shares the main characteristics of a basic unit in modern deep neural networks. The model is derived from observations of how a single neuron works in our nervous system. However, researchers did not know exactly what functions a collection of such neurons could realize and perform. On a more technical level, they were also unsure which nonlinear activation function $\varphi(\cdot)$ should be used. Hence, historically many variants have been proposed.²⁵²⁵25Step function, hard or soft thresholding, rectified linear unit (ReLU), sigmoid, etc. [DSC22].

In the 1950s, Frank Rosenblatt was the first to build a machine with a network of such artificial neurons, shown in Figure 1.15. The machine, called Mark I Perceptron, consists of an input layer, an output layer, and a single hidden layer of 512 artificial neurons, as shown in Figure 1.15 left, which is similar to what is illustrated in Figure 1.14 (left). It was designed to classify optical images of letters. However, the capacity of a single-layer network is limited and can only learn linearly separable patterns. In the 1969 book Perceptrons: An Introduction to Computational Geometry by Marvin Minsky and Seymour Papert [MP69], it was shown that the single-layer architecture of Mark I Perceptron cannot learn an XOR function. This result significantly dampened interest in artificial neural networks, even though it was later proven that a multi-layer network can learn an XOR function [RHW86]. In fact, a sufficiently large multi-layer network, as shown in Figure 1.14 (right), consisting of such simple neurons can simulate any finite-state machine, even the universal Turing machine.²⁶²⁶26Do not confuse what neural networks are capable of doing in principle with whether it is tractable or easy to learn a neural network that realizes certain desired functions. Nevertheless, the study of artificial neural networks subsequently entered its first winter in the 1970s.

Early experiments with artificial neural networks such as the Mark I Perceptron in the 1950s and 1960s were somewhat disappointing. They suggested that simply connecting neurons in a general fashion, as in multi-layer perceptrons (MLPs), might not suffice. To build effective and efficient networks, it is extremely helpful to understand the collective purpose or function neurons in the network must achieve so that they can be organized and learned in a specialized way. Thus, at this juncture, once again the study of machine intelligence turned to the animal nervous system for inspiration.

It is known that most of our brain is dedicated to processing visual information [Pla99]. In the 1950s and 1960s, David Hubel and Torsten Wiesel systematically studied the visual cortices of cats. They discovered that the visual cortex contains different types of cells—simple cells and complex cells—which are sensitive to visual stimuli of different orientations and locations [HW59]. Hubel and Wiesel won the 1981 Nobel Prize in Physiology or Medicine for this groundbreaking discovery.

On the artificial neural network side, Hubel and Wiesel’s work inspired Kunihiko Fukushima to design the “neocognitron” network in 1980, which consists of artificial neurons that emulate biological neurons in the visual cortices [Fuk80]. This is known as the first convolutional neural network (CNN), and its architecture is illustrated in Figure 1.16. Unlike the perceptron, the neocognitron had more than one hidden layer and could be viewed as a deep network, as shown in Figure 1.14 (right).

Also inspired by how neurons work in the cat’s visual cortex, Fukushima was the first to introduce the rectified linear unit (ReLU):

as the activation function $\varphi(\cdot)$ in 1969 [Fuk69]. However, it was not until recent years that ReLU became widely used in modern deep (convolutional) neural networks. This book will explain why ReLU is a good choice once we discuss the main operations deep networks implement: compression.

CNN-type networks continued to evolve in the 1980s, and many different variants were introduced and studied. However, despite the remarkable capacities of deep networks and the improved architectures inspired by neuroscience, it remained extremely difficult to train such deep networks for real tasks such as image classification. Getting a network to work depended on many unexplainable heuristics and tricks, which limited the appeal and applicability of neural networks. A major breakthrough came around 1989 when Yann LeCun successfully used back propagation (BP) to learn a deep convolutional neural network for recognizing handwritten digits [LBD+89], later known as LeNet (see Figure 1.17). After several years of persistent development, his perseverance paid off: LeNet’s performance eventually became good enough for practical use in the late 1990s [LBB+98]. It was used by the US Post Office for recognizing handwritten digits (for zip codes). LeNet was considered the “prototype” network for all modern deep neural networks, such as AlexNet [KSH12] and ResNet [HZR+16a], which we will discuss later. For this work, Yann LeCun was awarded the 2018 Turing Award.²⁷²⁷27Together with two other pioneers of deep networks, Yoshua Bengio and Geoffrey Hinton.

Throughout history, the fate of deep neural networks has been tied to how easily and efficiently they can be trained. Backpropagation (BP) was introduced for this purpose. A multilayer perceptron can be expressed as a composition of linear mappings and nonlinear activations:

To train the network weights $\{\bm{W}_{l}\}_{l=1}^{L}$ via gradient descent, we must evaluate the gradient $\partial h/\partial\bm{W}_{l}$. The chain rule in calculus shows that gradients can be computed efficiently for such functions—a technique later termed backpropagation or BP; see Appendix A for details. BP was already known in optimal control and dynamic programming during the 1960s and 1970s, appearing in Paul Werbos’s 1974 PhD thesis [Wer74, Wer94]. In 1986, David Rumelhart et al. were the first to apply it to train a multilayer perceptron (MLP) [RHW86]. Since then, BP has become the dominant technique for training deep networks, as it is scalable and can be efficiently implemented on parallel and distributed computing platforms. However, nature likely does not use BP,²⁸²⁸28As we have discussed earlier, nature almost ubiquitously learns to correct errors via closed-loop feedback. as the mechanism is too expensive for physical implementation.²⁹²⁹29End-to-end BP is computationally intractable for neural structures as complex as the brain, especially if the updates need to happen in real time. Instead, localized updates to small sections of the neural circuitry are much more biologically feasible. There is a relatively small amount of work on transplanting such “local learning” rules to training deep networks, circumventing BP [BS16, MSS+22, LTP25]. We believe this is an exciting opportunity to improve the scalability of training deep networks. This leaves ample room for future improvement.

Despite the aforementioned algorithmic advances, training deep networks remained finicky and computationally expensive in the 1980s and 1990s. By the late 1990s, support vector machines (SVMs) [CV95] had gained popularity as a superior alternative for classification tasks.³⁰³⁰30Similar ideas for classification problems trace back to Thomas Cover’s 1964 PhD dissertation, which was condensed and published in a paper in 1964 [Cov64]. SVMs offered two advantages: a rigorous statistical learning framework known as the Vapnik–Chervonenkis (VC) theory and efficient convex optimization algorithms [BV04]. The rise of SVMs ushered in a second winter for neural networks in the early 2000s.

In the late 1980s and 1990s, artificial neural networks were already being used to learn low-dimensional representations of high-dimensional data such as images. It had been shown that neural networks could learn PCA directly from data [Oja82, BH89], rather than using the classic methods discussed in Section 1.3.1. It was also argued during this period that, due to their ability to model nonlinear transformations, neural networks could learn low-dimensional representations for data with nonlinear distributions. Similar to the linear PCA case, one can simultaneously learn a nonlinear dimension-reduction encoder $f$ and a decoder $g$, each modeled by a deep neural network [RHW86, Kra91]:

By enforcing consistency between the decoded data $\hat{\bm{X}}$ and the original $\bm{X}$—for example, by minimizing a MSE-type reconstruction error³¹³¹31MSE-type errors are known to be problematic for imagery data with complex nonlinear structures. As we will soon discuss, much recent work in generative methods, including GANs, has focused on finding better surrogate distance functions between the original data $\bm{X}$ and the regenerated $\hat{\bm{X}}$.:

an autoencoder can be learned directly from the data $\bm{X}$.

But how can we guarantee that such an auto-encoding indeed captures the true low-dimensional structures in $\bm{X}$ rather than yielding a trivial redundant representation? For instance, one could simply choose $f$ and $g$ to be identity maps and set $\bm{Z}=\bm{X}$. To ensure the auto-encoding is worthwhile, the resulting representation should be compressive according to some computable measure of complexity. In 1993, Geoffrey Hinton and colleagues proposed using coding length as such a measure, transforming the auto-encoding objective into finding a representation that minimizes coding length [HZ93]. This work established a fundamental connection between the principle of minimum description length [Ris78] and free (Helmholtz) energy minimization. Later work from Hinton’s group [HS06] empirically demonstrated that such auto-encoding can learn meaningful low-dimensional representations for real-world images. Pierre Baldi provided a comprehensive survey of autoencoders in 2011 [Bal11], just before deep networks gained widespread popularity. We will discuss measures of complexity and auto-encoding further in Section 1.4, and present a systematic study of compressive auto-encoding in Chapter 5 from a more unified perspective.

The tremendous potential of deep networks could be unleashed only once sufficient data and computational power became available. By the 2010s, large datasets such as ImageNet had emerged, and GPUs had become powerful enough to make back-propagation affordable even for networks far larger than LeNet. In 2012, the deep convolutional network AlexNet — named for Alex Krizhevsky, one of the authors [KSH12] — attracted widespread attention by surpassing existing classification methods on ImageNet by a significant margin.³²³²32Deep networks had already achieved state-of-the-art results on speech-recognition tasks, but these successes received far less attention than the breakthrough on image classification. Figure 1.18 compares AlexNet with LeNet. AlexNet retains many characteristics of LeNet—it is simply larger and replaces LeNet’s sigmoid activations with ReLUs. This work contributed to Geoffrey Hinton’s 2018 Turing Award.

This early success inspired the machine intelligence community to explore new neural network architectures, variations, and improvements. Empirically, it was discovered that larger and deeper networks yield better performance on tasks such as image classification. Notable architectures that emerged include VGG [SZ15], GoogLeNet [SLJ+14], ResNet [HZR+16], and, more recently, Transformers [VSP+17]. Despite rapid empirically-driven performance improvements, theoretical explanations for these architectures—and the relationships among them, if any —remained scarce. One goal of this book is to uncover the common objective these networks optimize and to explain their shared characteristics, such as multiple layers of linear operators interleaved with nonlinear activations (see Chapter 4).

Early deep network successes were mainly in supervised classification tasks such as speech and image recognition. Later, deep networks were adopted to learn decision-making or control policies for game playing. In this context, deep networks model the optimal decision/control policy (i.e., a probability distribution over actions to take in order to maximize the expected reward) or the associated optimal value function (an estimate of the expected reward from the given state), as shown in Figure 1.19. Network parameters are incrementally optimized³³³³33Typically via back-propagation (BP). based on rewards returned from the success or failure of playing the game with the current policy. This learning paradigm is called reinforcement learning [SB18]; it originated in control-systems practice of the late 1960s [WF65, MM70] and traces back through a long and rich history to Richard Bellman’s dynamic programming [Bel57] and Marvin Minsky’s trial-and-error learning [Min54] in the 1950s.

From an implementation standpoint, the marriage of deep networks and reinforcement learning proved powerful: deep networks can approximate control policies and value functions for real-world environments that are difficult to model analytically. This culminated in DeepMind’s AlphaGo system, which stunned the world in 2016 by defeating top Go player Lee Sedol and, in 2017, world champion Jie Ke.³⁴³⁴34In 1996, IBM’s Deep Blue made history by defeating Russian grandmaster Garry Kasparov in chess using traditional machine learning techniques such as tree search and pruning, methods that have proven less scalable and unsuccessful for more complex games like Go.

AlphaGo’s success surprised the computing community, which had long regarded the game’s state space as too vast for any efficient solution in terms of computation and sample size. The only plausible explanation is that the optimal value and policy function of Go possess significant favorable structure: qualitatively speaking, their intrinsic dimensions are low enough so that they can be well approximated by neural networks learnable from a manageable number of samples.

From a certain perspective, the early practice of deep networks in the 2010s was focused on extracting relevant information from the data $\bm{X}$ and encoding it into a task-specific representation $\bm{Z}$ (say $\bm{Z}$ denotes class labels in classification tasks³⁵³⁵35This is a highly atypical notation for labels — the usual notation is $\bm{y}$ — but it is useful for our purposes to consider labels as highly compressed and sparse representations of the data. See Example 1.2 for more details.):

Here the learned mapping $f$ needs not preserve most distributional information about $\bm{X}$; it suffices to retain only the sufficient statistics for the task. For example, a sample $\bm{x}\in\bm{X}$ might be an image of an apple, mapped by $f$ to the class label $\bm{z}=\text{``apple''}$.

In many modern settings—such as the so-called large general-purpose (“foundation”) models—we may need to also decode $\bm{Z}$ to recover the corresponding $\bm{X}$ to a prescribed precision:

Because $\bm{X}$ typically represents data observed from the external world, a good decoder allows us to simulate or predict what happens in the world. In a “text-to-image” or “text-to-video” task, for instance, $\bm{z}$ is the text describing the desired image $\bm{x}$, and the decoder should generate an $\hat{\bm{x}}$ whose content matches $\bm{x}$. Given an object class $\bm{z}=\text{``apple''}$, the decoder $g$ should produce an image $\hat{\bm{x}}$ that looks like an apple, though not necessarily identical to the original $\bm{x}$.

For the generated images $\hat{\bm{X}}$ to resemble true natural images $\bm{X}$, we must be able to evaluate and minimize some distance:

As it turns out, most theoretically motivated distances are extremely difficult—if not impossible—to compute and optimize for distributions in high-dimensional space with low intrinsic dimension.³⁶³⁶36This remains true even when a parametric family of distributions for $\bm{X}$ is specified. The distance often becomes ill-conditioned or ill-defined for distributions with low-dimensional supports. Worse still, the chosen family might poorly approximate the true distribution of interest.

In 2007, Zhuowen Tu, disappointed by early analytical attempts to model and generate natural images, decided to try a drastically different approach. In a paper published at CVPR 2007 [Tu07], he first suggested learning a generative model for images via a discriminative approach. The idea is simple: if evaluating the distance $\operatorname{dist}(\bm{X},\hat{\bm{X}})$ proves difficult, one can instead learn a discriminator $d$ to separate $\hat{\bm{X}}$ from $\bm{X}$:

where labels $0$ and $1$ indicate whether an image is generated or real. Intuitively, the harder it becomes to separate $\hat{\bm{X}}$ and $\bm{X}$, the closer they likely are.

Tu’s work [Tu07] first demonstrated the feasibility of learning a generative model from a discriminative approach. However, the work employed traditional methods for image generation and distribution classification (such as boosting), which proved slow and difficult to implement. After 2012, deep neural networks gained popularity for image classification. In 2014, Ian Goodfellow and colleagues again proposed generating natural images with a discriminative approach [GPM+14]. They suggested modeling both the generator $g$ and discriminator $d$ with deep neural networks. Moreover, they proposed learning $g$ and $d$ via a minimax game:

where $\ell(\cdot)$ is some natural loss function associated with the classification task. In this formulation, the discriminator $d$ maximizes its success in separating $\bm{X}$ and $\hat{\bm{X}}$, while the generator $g$ does the opposite. This approach is named generative adversarial networks (GANs). It was shown that once trained on a large dataset, GANs can indeed generate photo-realistic images. Partially due to this work’s influence, Yoshua Bengio received the 2018 Turing Award.

The discriminative approach appears to cleverly bypass a fundamental difficulty in distribution learning. However, rigorously speaking, this approach does not fully resolve the fundamental difficulty. It is shown in [GPM+14] that with a properly chosen loss, the minimax formulation becomes mathematically equivalent to minimizing the Jensen-Shannon distance (see [CT91]) between $\bm{X}$ and $\hat{\bm{X}}$. This remains a hard problem for two low-dimensional distributions in high-dimensional space. Consequently, GANs typically rely on many heuristics and engineering tricks and often suffer from instability issues such as mode collapsing.³⁷³⁷37Nevertheless, such a minimax formulation provides a practical approximation of the distance. It simplifies implementation and avoids certain caveats in directly computing the distance.

In 2015, shortly after GANs were introduced and gained popularity, Surya Ganguli and his students proposed that an iterative denoising process modeled by a deep network could be used to learn a general distribution, such as that of natural images [SWM+15]. Their method was inspired by properties of special Gaussian and binomial processes studied by William Feller in 1949 [Fel49].³⁸³⁸38Again, in the magical era of the 1940s!

Soon, denoising operators based on the score function [Hyv05], briefly introduced in Section 1.3.1, were shown to be more general and unified the denoising and diffusion processes and algorithms [SE19, SSK+21, HJA20]. Figure 1.20 illustrates the process that transforms a generic Gaussian distribution $q^{0}=\mathcal{N}(\bm{0},\bm{I})$ to an (arbitrary) empirical distribution $p(\bm{x})$ by performing a sequence of iterative denoising (or compressing) operations:

By now, denoising (and diffusion) has replaced GANs and become the mainstream method for learning distributions of images and videos, leading to popular commercial image generation engines such as Midjourney and Stability.ai. In Chapter 3 we will systematically introduce and study the denoising and diffusion method for learning a general low-dimensional distribution.