Chapter 1 An Informal Introduction

As we have discussed before in Section 1.2.1, a main task of intelligence is to learn what is predictable in sequences of observations. Probably the simplest class of predictable sequences, or signals, are generated via a linear time-invariant (LTI) process:

where $z$ is the input and $h$ is the impulse response function.¹⁴¹⁴14Normally $h$ is assumed to have certain nice structures, say finite length or banded spectrum. Here $\epsilon[n]$ is some additive noise in the observations. The problem is that given the input process $\{z[n]\}$ and observations of the output process $\{x[n]\}$, how to find the optimal $h[n]$ such that $\hat{x}[n]=h[n]*z[n]$ predicts $x[n]$ in an optimal way. In general, we measure the goodness of the prediction by the minimum mean squared error (MMSE):

The optimal solution $h[n]$ is referred to as a (denoising) filter. Norbert Wiener, the same person who initiated the Cybernetics movement, studied this problem in the 1940s and gave an elegant closed-form solution known as the Wiener filter [Wie42, Wie49]. This became one of the most fundamental results in the field of Signal Processing.

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

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

where $\bm{w}$ is some (white) noise. The optimal causal¹⁵¹⁵15Which means the estimation can only use observations up to the current time step $n$. Kalman filter is always causal whereas Wiener filter need not be. state estimator that minimizes the MMSE-type prediction error

is given in closed-form by the so-called Kalman filter [Kal60]. This is one of the cornerstones of modern Control Theory because it allows us to estimate the state of a dynamical system from its noisy observations. Then one can subsequently introduce a (linear) state feedback, say of the form $\bm{u}[n]=\bm{F}\hat{\bm{z}}[n]$, and make the closed-loop system fully autonomous, as we saw in equation (1.2.13).

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, it would be a more challenging problem 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, it can be shown that the input and output sequences $\{\bm{u}[n],\bm{x}[n]\}$ would jointly lie on a certain low-dimensional subspace¹⁶¹⁶16which 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 essentially are all linear. So 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, Wiener filter and Kalman filter all try to estimate such an $\bm{x}_{o}$ from its noisy observations:

where $\bm{\epsilon}$ is typically a random Gaussian noise (or process). Hence, essentially, their solutions all rely on identifying a low-dimensional linear subspace that best fits the observed (noisy) data. Then 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 of all these problems is to learn from noisy observations a single low-dimensional linear subspace. Mathematically, we may model such a structure as:

where $\bm{\epsilon}\in\mathbb{R}^{D}$ is some 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 to estimate the subspace $\bm{U}$ is to minimize the variance of the noise, also known as the minimum mean square error (MMSE):

Notice that 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}$ as

If the noise is small and if we learned the correct low-dimensional subspace $\bm{U}$, we should expect $\bm{x}\approx\hat{\bm{x}}$. That is, PCA is a special case of the auto-encoding:

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

This is a classic problem in statistics known as the Principal Component Analysis (PCA). It was first studied by Pearson in 1901 [Pea01] and later independently by Hotelling in 1933 [Hot33]. This topic is systematically summarized in the classic book [Jol86, Jol02]. In addition, one may 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 above PCA model (1.3.7) is a standard normal distribution. This is known as Probabilistic PCA [TB99].

In this book, we will 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 for a low-dimensional distribution, including the important notion of compression via denoising and autoencoding 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 deceivingly similar form as 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}$:

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.¹⁷¹⁷17Even if $w$ is Gaussian, $\sigma w$ is no longer a Gaussian variable! The ICA problem is trying 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 easy 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 autoencoding of the form:

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

As one may see, if $p$ in (1.3.13) is very small, the probability that any of the components is non-zero is small. In this case, we say $\bm{x}$ is sparsely generated and it concentrates on a set of linear subspaces of dimension $k=p\cdot d$. Hence, to some extent, we may extend the above ICA model to a more general family of low-dimensional structures known as sparse models.

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

where $\|\cdot\|_{0}$ is the $\ell^{0}$-norm that counts the number of non-zero entries in a vector $\bm{z}$. That is, $\mathcal{Z}$ is the union of all $k$-dimensional subspaces that align with the coordinate axes, as illustrated in Figure 1.7 left. One important problem in classic signal processing and statistics is how to recover a sparse vector $\bm{z}$ from its linear observations:

where $\bm{A}$ is given but typically $m<n$ and $\bm{\epsilon}$ is some small noise. This seemingly benign problem turns out to be NP-hard to compute and it is even hard to approximate (see the book [WM22] for details).

So despite a very rich and long history of study which can be dated back as early as the 18th century [Bos50], there was no provably efficient algorithm to solve this class of problems, although many heuristic algorithms have been proposed and developed between the 1960s and the 1990s. Some are rather effective in practice but without any rigorous justification. A major breakthrough came in the early 2000s when a few renowned mathematicians including David Donoho, Emmanuel Candès, and Terence Tao [Don05, CT05a, CT05] established a rigorous theoretical framework that allows us to characterize precise conditions under which the sparse recovery problem can be solved effectively and efficiently, say via a convex $\ell^{1}$ minimization:

where $\|\cdot\|_{1}$ is the sparsity-promoting $\ell^{1}$ norm of a vector and $\epsilon$ is some small constant. Any solution to this problem essentially gives a sparse coding mapping:

We will give a brief account of such an algorithm, hence mapping, in Chapter 2 which will reveal interesting fundamental connections between sparse coding and deep learning.¹⁸¹⁸18Although similarities between algorithms for sparse coding and deep networks were noticed as early as in 2010 [GL10].

As it turns out, conditions under which $\ell^{1}$ minimization succeeds are surprisingly general. The minimum number of measurements $m$ required for a successful recovery is only proportional to the intrinsic dimension of the data $k$. This is now known as the compressive sensing phenomenon [Can06]. Moreover, this phenomenon is not unique to sparse structures. It also applies to very broad families of low-dimensional structures such as low-rank matrices etc. These results have fundamentally changed our understanding about recovering low-dimensional structures in high-dimensional spaces. This dramatic reversal of fortune with high-dimensional data analysis was even celebrated as the “blessing of dimensionality” by David Donoho [D ̵D00] as opposed to the typical pessimistic belief in the “curse of dimensionality” for high-dimensional problems. This coherent and complete body of results has been systematically organized in the book [WM22].

From a computational perspective, one cannot overestimate the significance of this new framework. It has fundamentally changed our views about an important class of problems previously believed to be largely intractable. It has enabled us to develop extremely efficient algorithms that scale gracefully with the dimension of the problem, hence making the problem of sparse recovery from:

These algorithms also come with rigorous theoretical guarantees of their correctness given precise requirements in data and computation. The rigorous and precise nature of this approach is almost opposite to that of practicing deep neural networks, which is largely empirical. Yet, despite their seemingly opposite styles and standards, we now know both approaches share a common goal: trying to pursue low-dimensional structures in high-dimensional spaces.

Conceptually, an even harder problem than the sparse coding problem (1.3.16) is when the observation matrix $\bm{A}$ is not even known in advance and we need to learn $\bm{A}$ from a set of (possibly noisy) observations, say $\bm{X}=[\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}]$:

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

One can see what is in common with PCA, ICA, and Dictionary Learning is that they all assume that the distribution of the data is supported around low-dimensional linear or mixed linear structures. They all require learning a (global or local) basis of the linear structures, from probably noisy samples of the distribution. In Chapter 2, we will study how to identify low-dimensional structures through these classical models. In particular, we will see an interesting and important fact: all these low-dimensional (piecewise) linear models can be learned effectively and efficiently by the same type of fast algorithms, known as power iteration [ZMZ+20]. Although the above linear or mixed linear models are somewhat too simplistic or idealistic for most real-world data, understanding these models is an important 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)$. So if 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}$,²¹²¹21That 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})$. Amazingly, the posterior expectation of $\bm{x}_{o}$ given $\bm{x}$ can be calculated by an elegant formula, known as Tweedie’s formula [Rob56]:²²²²22Herbert 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 get hold of 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]. 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]. But 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], and later applied to image denoising [KS21, HJA20].

In fact, this function has a very intuitive information-theoretic and geometric interpretation. Note that in information theory $-\log p(\bm{x})$ generally corresponds to the number of bits needed to encode $\bm{x}$²³²³23at least in the case of a discrete variable, as we will explain in more detail in Chapter 3.. The gradient $\nabla\log p(\bm{x})$ points to a direction in which the density is higher, as shown in Figure 1.12 left. The number of bits needed to encode $\bm{x}$ decreases if it moves in that direction. Hence, the overall effect of the operator $\nabla\log p(\bm{x})$ is to push the distribution to “shrink” towards areas of higher density. Actually, one can formally show that the (differential) entropy of the distribution

indeed decreases under such an operation (see Chapter 3 and Appendix B). Therefore, if we encode it with an optimal code book, the overall coding length/rate of the resulting distribution is reduced, hence more “compressed.”. Intuitively, one can imagine that, if we repeat such a denoising process indefinitely, the distribution will eventually shrink to one whose mass is concentrated on a support of lower dimension. For example, the distribution $p(\bm{x})$ shown on the left of Figure 1.12, under the action of the score function $\nabla\log p(\bm{x})$, eventually will converge to the distribution $p^{*}(\bm{x})$ on the right²⁴²⁴24Strictly speaking, $p^{*}(\bm{x})$ is a distribution whose density 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$. :

Strictly speaking, as the distribution converges to $p^{*}(\bm{x})$, its differential entropy converges to negative infinity. This is due to a technical difference between the definition of differential entropy for continuous random variables and discrete random variables, respectively. We will see how to resolve this technical difficulty in Chapter 3, using a more uniform measure of rate distortion.

We will discuss later in this chapter and in Chapter 3 how such a seemingly simple concept of denoising and compression leads to a very unifying and powerful method for learning general low-dimensional distributions in a high-dimensional space, including the distribution of natural images.

Inspired by the nerve system in the brain, the mathematical model of the first artificial neuron²⁵²⁵25known as the Linear Threshold Unit, or a perceptron. was proposed by Warren McCulloch²⁶²⁶26A 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, normally 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 nerve system. However, people did not know exactly what functions a collection of such neurons wants to realize and perform. On a more technical level, neither were they sure what nonlinear activation function $\varphi(\cdot)$ should be used. Hence, historically many variants have been proposed.²⁷²⁷27Step function, Hard or soft thresholding, Rectified Linear Unit (ReLU), sigmoid, etc.

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 is called Mark I Perceptron which consists of an input layer, an output layer, and a single hidden layer consisting 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 a 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 had significantly damped people’s interest in artificial neural networks, even though it was later proven that a multi-layer network is able to learn an XOR function [RHW86]. In fact, a (big enough) 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.²⁸²⁸28Do 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, subsequently, the study of artificial neural networks went into its first winter in the 1970s.

The somewhat disappointing early experimentation with artificial neural networks like Mark I Perceptron in the 50s and 60s suggested that it might not be enough to simply connect neurons in a general fashion as multi-layer perceptrons (MLP). In order to build effective and efficient networks, we need to understand what purpose or function neurons in a network need to achieve collectively so that they should be organized and learned in a certain special way. Once again, the study of machine intelligence turned to drawing inspiration from how the animal’s nervous system works.

It is known that most of our brain is dedicated to processing visual information. In the 1950s and 1960s, David Hubel and Torsten Wiesel systematically studied the visual cortices of cats. It was discovered that the visual cortex contains different types of cells (known as 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 their ground-breaking discovery.

On the artificial neural network side, Hubel and Wiesel’s work had inspired Kunihiko Fukushima who designed 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 compared in Figure 1.14 right.

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

for the activation function $\varphi(\cdot)$ in 1969 [Fuk69]. But not until recent years has the ReLU become a widely used activation function in modern deep (convolutional) neural networks. We will learn from this book why this is a good choice once we explain the main operations that deep networks try to implement: compression.

CNN-type networks continued to evolve in the 1980s and many different variants had been 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 a real task such as image classification. How to get a network to work depended on many unexplainable heuristics and tricks that really limited the appeal and applicability of neural networks. One major breakthrough came around 1989 when Yann LeCun successfully used back propagation (BP) to learn a deep convolutional neural network for recognizing hand-written digits [LBD+89], later known as the LeNet (see Figure 1.17). After several years’ persistent development, his perseverance paid off: performance of the LeNet eventually became good enough for practical usage in the late 1990s [LBB+98]: it was used by the US Post Office for recognizing handwritten digits (for zip codes). The LeNet was considered as the “prototype” network for all modern deep neural networks, such as the AlexNet and ResNet, which we will discuss later. Due to this work, Yann LeCun was awarded the 2018 Turing Award.²⁹²⁹29Together with two other pioneers of deep networks, Yoshua Bengio and Geoffrey Hinton.

In history, the fate of deep neural networks seems to be tied closely to how they can be trained easily and efficiently. Back propagation (BP) was introduced for this reason. We know that a multiple layer perceptron can be expressed as a composition of a sequence of linear mappings and nonlinear activations as follows:

In order to train the network weights $\{\bm{W}_{l}\}_{l=1}^{L}$ to reduce the prediction/classification error based on a gradient descent algorithm, we need to evaluate the gradient ${\partial h}/{\partial\bm{W}_{l}}$. It has been well known, from the chain rule in calculus, that gradients can be computed efficiently for this type of functions, later known as back propagation (BP). See Appendix A for a detailed description. The technique of back propagation was already known and practiced by people in fields such as optimal control and dynamic programming in the 1960s and 1970s. For example, it appeared in the 1974 PhD thesis of Dr. Paul Werbos [Wer74, Wer94]. In 1986, David Rumelhart et al. were the first to apply back propagation to train a multiple layer perceptron (MLP) network [RHW86]. Since then, BP has become increasingly popular since it gives a scalable algorithm to learn large deep neural networks.³⁰³⁰30as it can be efficiently implemented on computing platforms that facilitate parallel and distributed computing. It is now an almost dominant technique for training deep neural networks today. However, it is believed that nature does not learn by back propagation, because such a mechanism is still way too expensive for physical implementation by nature³¹³¹31As we have discussed earlier, nature almost ubiquitously learns to correct error via closed-loop feedback.. This obviously leaves tremendous room for improvement in the future, as we will discuss more.

However, despite the above algorithmic progress and promising practice in the 1980s, training deep neural networks remained extremely finicky and expensive for computing systems in the 1980s and 1990s. In the late 1990s, support vector machines (SVM) [CV95] had become very popular as they were viewed as a better alternative to neural networks for tasks such as classification.³²³²32In fact, similar ideas to solve classification problems can be traced back to the PhD dissertation work of Thomas Cover, which as condensed and published in a paper in 1964 [Cov64]. There were two main reasons: first, SVM was based on a rigorous statistical learning framework known as the Vapnik–Chervonenkis (VC) theory; and second, it leads to rather efficient algorithms based on convex optimization [BV04]. The rise of SVM had brought a second winter to the study of neural networks around the early 2000s.

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

By enforcing the decoded data $\hat{\bm{X}}$ to be consistent with the original $\bm{X}$, say by minimizing an MMSE type reconstruction error³³³³33Although MMSE type of errors are known to be problematic to imagery data that have complex nonlinear structures. As we will soon discuss, much of the recent work in generative methods, including GANs, has been to find surrogates of better distance functions between the original data $\bm{X}$ and the regenerated $\hat{\bm{X}}$.:

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

But how can we guarantee that such an autoencoding indeed captures the true low-dimensional structures in $\bm{X}$ instead of giving a trivial redundant representation? For example, we can simply choose $f$ and $g$ to be the identity map and $\bm{Z}=\bm{X}$. So to ensure the autoencoding to be worthwhile, one wishes the resulting representation to be compressive, in terms of a certain computable measure of complexity. In 1993, Geoffrey Hinton and colleagues proposed to use the coding length as such a measure, hence the objective of autoencoding became to find such a representation that minimizes the coding length [HZ93]. This work also established a fundamental connection between the principle of minimum description length [Ris78] and free (Helmholtz) energy minimization. Later work [HS06] from Hinton’s group showed empirically that such an autoencoding is capable of learning meaningful low-dimensional representations for real-world images. A more comprehensive survey of autoencoders was done by Pierre Baldi in 2011 [Bal11], just before deep networks became popular. We will discuss more about the measure of complexity and autoencoding later in Section 1.4, and give a systematic study of compressive autoencoding in Chapter 5, with a more unifying view.

As it turns out, the tremendous potential of deep neural networks could only be unleashed once there are enough data and computing power. Fast forward to the 2010s, much larger datasets such as ImageNet became available, and GPUs became powerful enough to make BP much more affordable, even for networks much larger than LeNet. Around 2012, a deep convolutional neural network known as the AlexNet drew attention as it surpassed existing classification methods by a significant margin with the ImageNet dataset [KSH12].³⁴³⁴34In fact, before this, deep networks had demonstrated state-of-the-art performance on speech recognition tasks. But it did not receive so much attention until their success with image classification. Figure 1.18 shows the comparison between the AlexNet and the LeNet. The AlexNet shares many common characteristics as the LeNet, only it is bigger and has adopted ReLU as the nonlinear activation instead of the Sigmoid function used in LeNet. Partly due to the influence of this work, Geoffrey Hinton was awarded the 2018 Turing Award.

This early success inspired the machine intelligence community, in the next few years, to explore new variations and improvements to the network design. In particular, people had discovered empirically that the larger and deeper the networks, the better the performance in tasks such as image classification. Many deep network architectures have been tried, tested, and popularized. A few notable ones include VGG [SZ15], GoogLeNet [SLJ+14], ResNet [HZR+16], and more recently Transformers [VSP+17] etc. Despite fast progress in empirical performance, there was a lack of theoretical explanation for these empirically discovered architectures, including relationships among them if any. One purpose of this book is to reveal what common objective all these networks may serve and why they share certain common characteristics, including multiple layers of linear operator interleaved with nonlinear activation (see Chapter 4).

The early successes of deep networks were mainly for classification tasks in a supervised learning setting, such as speech recognition and image recognition. Deep networks were later adopted by the DeepMind team, led by Demis Hassabis, to learn decision-making or control policies for playing games. In this context, deep networks are used to model the optimal decision/control policy or the associated optimal value function, as shown in Figure 1.19. These network parameters are incrementally optimized ³⁵³⁵35Say based on back propagation (BP). based on reward returned from the success or failure of playing the game with the current policy. This learning method is generally referred to as reinforcement learning [SB18], originated from the practice of control systems in the late 1960s [WF65, MM70]. Its earlier roots can be traced back to a much longer and richer history of dynamic programming by Richard Bellman [Bel57] and trial-and-error learning by Marvin Minsky [Min54] in the 1950s.

From an implementation perspective, the combination of deep networks and reinforcement learning turned out to be rather powerful: deep networks can be used to approximate control policy and value function for real-world environments that are difficult to model analytically. This practice eventually led to the AlphaGo system, developed by the company DeepMind, which surprised the world in 2016 by beating a top human player Lee Sedol in the game Go and then the world champion Ke Jie in 2017.³⁶³⁶36In 1996, IBM’s Deep Blue system made history by defeating Russian grandmaster Garry Kasparov in chess. It mainly used traditional machine learning techniques, such as tree search and pruning, which were not so scalable and had not been proven successful for more challenging games such as Go for over 20 years.

The success of AlphaGo came as a big surprise to the computing society which generally believes that the state space for search is too prohibitively large to admit any efficient solution, in terms of computation and sample size. The only reasonable explanation for its success is that there must be very good structures in the optimal value/policy function of the game Go. Their intrinsic dimension is not so high and they can be approximated well by a neural network, learnable from not so prohibitively many samples.

One may view early practices of deep networks in the 2010s as focused more on extracting relevant information from the data $\bm{X}$ and encoding it for certain task-specific representation $\bm{Z}$ (say $\bm{Z}$ represents class labels in classification tasks):

In this setting, the mapping $f$ to be learned does not need to preserve most distributional information about $\bm{X}$ but only the sufficient statistics needed for a specific task. For example, a sample $\bm{x}$ in $\bm{X}$ could be an image of an apple, which is mapped by $f$ to its class label $\bm{z}=$ “apple.” The information bottleneck framework [TZ15] was proposed in 2015 to analyze the role of deep networks in such a context.

However, in many modern situations such as those so-called large foundation models, people often need to decode $\bm{Z}$ to recover the corresponding $\bm{X}$ to a certain degree of precision:

As $\bm{X}$ typically represents data observed from the external world, a good decoder would allow us to simulate or predict what happens in the world. For example, in a “text to image” or “text to video” task, $\bm{z}$ normally represents the texts that describe the content of a desired image $\bm{x}$. The decoder should be able to generate an $\hat{\bm{x}}$ that has the same content as $\bm{x}$. For example, given an object class $\bm{z}=$ “apple”, the decoder $g$ should generate an image $\hat{\bm{x}}$ that looks like an apple, although not necessarily exactly the same as the original $\bm{x}$.

In order for the generated images $\hat{\bm{X}}$ to be similar to the true natural images $\bm{X}$, we need to 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 but with a low intrinsic dimension.³⁷³⁷37This is the case even if a parametric family of distribution for $\bm{X}$ is given. The distance often becomes ill-conditioned or ill-defined for distributions with low-dimensional supports. What could be even worse is that the chosen family might not be able to approximate well the true distribution of interest.

In 2007, Zhuowen Tu, a former student of Song-Chun Zhu, probably disappointed by early analytical attempts to model and generate natural images (discussed earlier), decided to try a drastically different approach. In a paper published in CVPR 2007 [Tu07], he was the first to suggest that one could learn a generative model for images via a discriminative approach. The idea is simple: if it is difficult to evaluate the distance $d(\bm{X},\hat{\bm{X}})$, one could try to learn a discriminator $d$ to separate $\hat{\bm{X}}$ from $\bm{X}$:

where $\bm{0},\bm{1}$ indicate an image is generated or not. Intuitively, the harder we could separate $\hat{\bm{X}}$ and $\bm{X}$, probably the closer they are.

Tu’s work [Tu07] was the first to demonstrate the feasibility of learning a generative model from a discriminative approach. However, the work adopted traditional methods to generate images and classify distributions (such as boosting), and they were slow and hard to implement. After 2012, deep neural networks became very popular for image classification. In 2014, Ian Goodfellow and colleagues proposed again to generate natural images with a discriminative approach [GPM+14]. They suggested using deep neural networks to model the generator $g$ and the discriminator $d$ instead. Moreover, they proposed to learn the generator $g$ and discriminator $d$ via a minimax game:

where $\ell(\cdot)$ is some natural loss function associated with the classification. In words the discriminator $d$ tries to maximize its success in separating $\bm{X}$ and $\hat{\bm{X}}$, whereas the generator $g$ tries to do the opposite. For this reason, this approach is named as generative adversarial networks (GANs). It was shown that once trained on a large dataset, GANs can indeed generate photo-realistic images. Partially due to the influence of this work, Yoshua Bengio was awarded the 2018 Turing Award.

The discriminative approach seems to be a rather clever way to bypass a fundamental difficulty in distribution learning. However, rigorously speaking, this approach does not fully resolve this fundamental difficulty at all. It is shown by [GPM+14] that with a properly chosen loss, the minimax formulation is mathematically equivalent to minimize the Jensen-Shannon distance (see [CT91]) between $\bm{X}$ and $\hat{\bm{X}}$. This is known to be a hard problem for two low-dimensional distributions in a high-dimensional space. As a result, in practice, GANs typically rely on many heuristics and engineering tricks and often suffer from instability issues such as mode collapsing.³⁸³⁸38Nevertheless, such a minimax formulation provides a practical approximation of the distance. It simplifies the implementation and avoids certain caveats in directly computing the distance. Overall, there has been a lack of theoretical guidance on how to improve the practice of GANs.

In 2015, shortly after GAN was introduced and became popular, Surya Ganguli and his students realized and suggested that an iterative denoising process modeled by a deep network can be used to learn a general distribution, such as that of natural images [SWM+15]. Their method was inspired by properties of the special Gaussian and binomial processes, studied by William Feller back in 1949 [Fel49].³⁹³⁹39Again, in the magical era of 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 gives an illustration of 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) have replaced GANs and become a mainstream method for learning distributions of images and videos, leading to popular commercial image generating 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.