Chapter 5 Consistent and Self-Consistent Representations

Notice that in the above construction, the linear transform $\bm{U}$ used for encoding and decoding is computed “offline” from all the input data beforehand. One question is whether this transform can be learned “online” as the input data comes in order. This question was answered by the work of Oja in 1982 [Oja82].

The normalized Hebbian scheme (5.1.9) can be interpreted as a first-order approximation to a stochastic projected gradient descent scheme on the objective of the problem (5.1.7) (with batch size $1$, and with the number of columns of $\bm{U}$ equal to $1$) as long as $\|\bm{u}\|_{2}=1$, which is maintained by the projection operation in (5.1.9). It is worth keeping its existence in the back of one’s mind, both as a proof of correctness for the use of stochastic gradient methods for optimizing reconstruction costs such as (5.1.7), and for its suggestion that simpler algorithms than (end-to-end) back propagation can succeed in learning consistent autoencoders.

So, to move beyond the linear structure addressed by PCA, we may assume that the data distribution lies on a (smooth) submanifold $\mathcal{M}$. The intrinsic dimension of the submanifold, say $d$, is typically much lower than the dimension of the ambient space $\mathbb{R}^{D}$. From this geometric perspective, we typically want to find a nonlinear mapping $f$ such that the resulting manifold $f(\mathcal{M})$ is flattened, as illustrated by the example shown in Figure 5.2. The resulting feature $\bm{z}$-space is typically more compact (of lower-dimension) than the $\bm{x}$-space, and the manifold is flat. From the statistical perspective, which is complementary to the geometric perspective but distinct in general, we may also want to ensure that the data distribution on $\mathcal{M}$ is mapped to a sufficiently regular distribution, say a Gaussian or uniform distribution (with very low-dimensional support), in the $\bm{z}$-space. These two properties ensure that sampling and interpolation in the $\bm{z}$-space are as easy as possible, and they are mathematical formalizations of the desirable notions of compact and structured features in the low-dimensional manifold model for the data distribution. In general, the problem of learning such an autoencoding mapping for this class of data distributions is known as nonlinear principal component analysis (NLPCA).

As we have seen above, in the case of PCA, a single-layer linear neural network is sufficient. That is no longer the case for NLPCA. In 1991, Kramer [Kra91] proposed to solve NLPCA by using a two-layer neural network to represent the encoder mapping $f$ (or its inverse $g$) based on the universal representation property of two-layer networks with sigmoid activation:

where $\sigma(\,\cdot\,)$ is the sigmoid function:

Cybenko [Cyb89] showed that functions of the above form (with enough hidden nodes) can approximate any smooth nonlinear function, say the encoder $f(\,\cdot\,)$, to an arbitrary precision. In particular, they can represent the flattening and reconstruction maps for data distributions supported on unions of low-dimensional manifolds, as in Figure 5.2. The overall architecture of the original networks proposed by Kramer is illustrated in Figure 5.3.

Unfortunately, unlike the case of PCA above, there is in general no closed-form learning scheme for the parameters $\bm{\theta}=(\bm{W},\bm{b})$ of these networks. Hence it was proposed to train the network via back propagation with the supervision of reconstruction error:

Compared to the simple case of PCA, we utilize the same reconstruction objective for learning, but a far more complex nonlinear class of models for parameterizing and learning the encoder and decoder. Although universal approximation properties such as Cybenko’s suggest that in principle learning consistent autoencoders via this framework is possible—because for any random sample of data, given enough parameters, such autoencoding pairs exist—one often finds it highly nontrivial to find them using gradient descent. Moreover, to obtain a sufficiently informative reconstruction objective and model for the distribution of high-dimensional real-world data such as images, the required number of samples and hidden nodes can be huge. In addition, as a measure of the compactness of the learned representation, the (lower) dimension of $\bm{z}$ for the bottleneck layer is often chosen heuristically.⁴⁴4In the later work [HZ93], Hinton et al. suggested to use the minimum description length (MDL) principle to promote the compactness of the learned coding scheme, in a spirit very similar to the rate distortion measure introduced in this book.

Based on the modern practice of deep networks, such classical shallow and wide network architectures are known to be rather difficult to train effectively and efficiently via back propagation (BP), partly due to the vanishing gradient of the sigmoid function. Hence, the modern practice normally suggests further decomposing the nonlinear transform $f$ (or $g$) into a composition of many more layers of simpler transforms, resulting in a deeper network architecture [HS06], as illustrated in Figure 5.4. In the modern context, further elaborations over the basic reconstruction cost (5.1.12) also prove necessary to achieve good performance on complex real-world data distributions such as images.

In light of universal approximation theorems such as Cybenko’s, one may initially wonder why, conceptually, deeper autoencoders should be preferred over shallow ones. From purely an expressivity perspective, we can understand this phenomenon through a geometric angle related to the task of flattening the nonlinear manifold on which our hypothesized data distribution is supported. A purely constructive approach to flattening the manifold proceeds incrementally, in parallel to what we have seen in Chapters 3 and 4 with the interaction between diffusion, denoising, and compression. In the geometric setting, the incremental flattening process corresponding to $f_{\ell}$ takes the form of transforming a neighborhood of one point of the manifold to be closer to a flat manifold (i.e., a subspace), and enforcing local consistency with the rest of the data samples; the corresponding incremental operation in the decoder, $g_{\ell}$, undoes this transformation. This procedure precisely incorporates curvature information about the underlying manifold, which is estimated from data samples. Given enough samples from the manifold and a careful instantiation of this conceptual process, it is possible to implement this procedure as a computational procedure that verifiably flattens nonlinear manifolds in a white-box fashion [PPR+24]. However, the approach is limited in its applicability to high-dimensional data distributions such as images due to unfavorable scalability, motivating the development of more flexible methods to incremental autoencoding.

However, as we have discussed above, if we do not have the option to compute the distance between $\bm{X}$ and $\hat{\bm{X}}$, we are left with the option of comparing their corresponding features $\bm{Z}$ and $\hat{\bm{Z}}=f(\hat{\bm{X}},\bm{\theta})$. Notice that under the MCR² objective, the distributions of the resulting $\bm{Z}$ or $\hat{\bm{Z}}$ tend to be piecewise linear so their distance can be computed more easily. More precisely, since the features of each class, $\bm{Z}_{k}$ and $\hat{\bm{Z}}_{k}$, are close to being a low-dimensional subspace/Gaussian, their “distance” can be measured by the rate reduction, with (5.2.8) restricted to two sets of equal size:

The overall distance between $\bm{Z}$ and $\hat{\bm{Z}}$ is given by:

If we are interested in discerning any differences in the distributions of the original data $\bm{X}$ and their decoded $\hat{\bm{X}}$, we may view the feature encoder $f(\cdot,\bm{\theta})$ as a “discriminator” to magnify any difference between all pairs of $\bm{X}_{k}$ and $\hat{\bm{X}}_{k}$, by simply maximizing the distance $d(\bm{X},\hat{\bm{X}})$:

That is, a “distance” between $\bm{X}$ and $\hat{\bm{X}}$ can be measured as the maximally achievable rate reduction between all pairs of classes in these two sets. In a way, this measures how well or badly the decoded $\hat{\bm{X}}$ aligns with the original data $\bm{X}$—hence measuring the goodness of “injectivity” of the encoder $f$. Notice that such a discriminative measure is consistent with the idea of GAN (5.2.3) that tries to separate $\bm{X}$ and $\hat{\bm{X}}$ into two classes, measured by the cross-entropy.

Nevertheless, here the discriminative encoder $f$ naturally generalizes to cases when the data distributions are multi-class and multi-modal, and the discriminativeness is measured with a more refined measure—the rate reduction—instead of the typical two-class loss (e.g., cross entropy) used in GANs. That is, we may view the encoder $f$ as a generalized discriminator that replaces the binary classifier $d$ in (5.2.3):

The overall pipeline can be illustrated by the following “closed-loop” diagram:

where the overall model has parameters: $\bm{\Theta}=\{\bm{\theta},\bm{\eta}\}$. Figure 5.6 shows the overall process.

Obviously, to ensure the learned autoencoding is self-consistent, the main goal of the decoder $g(\cdot,\bm{\eta})$ is to minimize the distance between $\bm{Z}$ and $\hat{\bm{Z}}$. That is, to learn $g$, we want to minimize the distance $d(\bm{Z},\hat{\bm{Z}})$:

where $\bm{Z}_{k}=f(\bm{X}_{k},\bm{\theta})$ and $\hat{\bm{Z}}_{k}=f(\hat{\bm{X}}_{k},\bm{\theta})$.

Comparing the contractive and contrastive nature of (5.2.15) and (5.2.12) on the same distance measure, we see the roles of the encoder $f(\cdot,\bm{\theta})$ and the decoder $g(\cdot,\bm{\eta})$ naturally as “a two-player game”: while the encoder $f$ tries to magnify the difference between the original data and their transcribed data, the decoder $g$ aims to minimize the difference. Now for convenience, let us define the “closed-loop encoding” function:

Ideally, we want this function to be very close to $f(\bm{x},\bm{\theta})$ or at least the distributions of their images should be close. With this notation, combining (5.2.15) and (5.2.12), a closed-loop notion of “distance” between $\bm{X}$ and $\hat{\bm{X}}$ can be computed as an equilibrium point to the following Stackelberg game (cf Section A.3) for the same utility in terms of rate reduction:

Notice that this only measures the difference between (features of) the original data and its transcribed version. It does not measure how good the representation $\bm{Z}$ (or $\hat{\bm{Z}}$) is for the multiple classes within $\bm{X}$ (or $\hat{\bm{X}}$). To this end, we may combine the above distance with the original MCR²-type objectives (5.2.8): namely, the rate reduction $\Delta R_{\epsilon}(\bm{Z})$ and $\Delta R_{\epsilon}(\hat{\bm{Z}})$ for the learned LDR $\bm{Z}$ for $\bm{X}$ and $\hat{\bm{Z}}$ for the decoded $\hat{\bm{X}}$. Notice that although the encoder $f$ tries to maximize the multi-class rate reduction of the features $\bm{Z}$ of the data $\bm{X}$, the decoder $g$ should minimize the rate reduction of the multi-class features $\hat{\bm{Z}}$ of the decoded $\hat{\bm{X}}$. That is, the decoder $g$ tries to use a minimal coding rate needed to achieve a good decoding quality.

Hence, the overall “multi-class” Stackelberg game for learning the closed-loop transcription, named CTRL-Multi, is

subject to certain constraints (upper or lower bounds) on the first term and the second term.

Notice that, without the terms associated with the generative part $h$ or with all such terms fixed as constant, the above objective is precisely the original MCR² objective introduced in Chapter 3. In an unsupervised setting, if we view each sample (and its augmentations) as its own class, the above formulation remains exactly the same. The number of classes $k$ is simply the number of independent samples. In addition, notice that the above game’s objective function depends only on (features of) the data $\bm{X}$, hence one can learn the encoder and decoder (parameters) without the need for sampling or matching any additional distribution (as typically needed in GANs or VAEs).

As a special case, if $\bm{X}$ only has one class, the Stackelberg game reduces to a special “two-class” or “binary” form,¹¹¹¹11As the first two rate reduction terms automatically become zero named CTRL-Binary,

between $\bm{X}$ and the decoded $\hat{\bm{X}}$ by viewing $\bm{X}$ and $\hat{\bm{X}}$ as two classes $\{\bm{0},\bm{1}\}$. Notice that this binary case resembles the formulation of the original GAN (5.2.3). Instead of using cross entropy, our formulation adopts a more refined rate-reduction measure, which has been shown to promote diversity in the learned representation in Chapter 3.

Sometimes, even when $\bm{X}$ contains multiple classes/modes, one could still view all classes together as one class. Then, the above binary objective is to align the union distribution of all classes with their decoded $\hat{\bm{X}}$. This is typically a simpler task to achieve than the multi-class one (5.2.20), since it does not require learning of a more refined multi-class CTRL for the data, as we will later see in experiments. Notice that one good characteristic of the above formulation is that all quantities in the objectives are measured in terms of rate reduction for the learned features (assuming features eventually become subspace Gaussians).

One may notice that the above learning framework draws inspiration from closed-loop error correction widely practiced in feedback control systems. The closed-loop mechanism is used to form an overall feedback system between the two encoding and decoding networks for correcting any “error” in the distributions between the data $\bm{x}$ and the decoded $\hat{\bm{x}}$. Using terminology from control theory, one may view the encoding network $f$ as a “sensor” for error feedback while the decoding network $g$ as a “controller” for error correction. However, notice that here the “target” for control is not a scalar nor a finite dimensional vector, but a continuous distribution—in order for the distribution of $\hat{\bm{x}}$ to match that of the data $\bm{x}$. This is in general a control problem in an infinite dimensional space. The space of possible diffeomorphisms of submanifolds that $f$ tries to model is infinite-dimensional [Lee02]. Ideally, we hope when the sensor $f$ and the controller $g$ are optimal, the distribution of $\bm{x}$ becomes a “fixed point” for the closed loop while the distribution of $\bm{z}$ reaches a compact linear discriminative representation. Hence, the minimax programs (5.2.20) and (5.2.21) can also be interpreted as games between an error-feedback sensor and an error-reducing controller.

The remaining question is whether the above framework can indeed learn a good (autoencoding) representation of a given dataset? Before we give some formal theoretical justification (in the next subsection), we present some empirical results.

We visualize the cosine similarity between $\bm{Z}$ and $\hat{\bm{Z}}$ learned from the multi-class objective (5.2.20) on MNIST, CIFAR-10 and ImageNet (10 classes), which indicates how close $\hat{\bm{z}}=f\circ g(\bm{z})$ is from $\bm{z}$. Results in Figure 5.8 show that $\bm{Z}$ and $\hat{\bm{Z}}$ are aligned very well within each class. The block-diagonal patterns for MNIST are sharper than those for CIFAR-10 and ImageNet, as images in CIFAR-10 and ImageNet have more diverse visual appearances.

We compare some representative $\bm{X}$ and $\hat{\bm{X}}$ on MNIST, CIFAR-10 and ImageNet (10 classes) to verify how close $\hat{\bm{x}}=g\circ f(\bm{x})$ is to $\bm{x}$. The results are shown in Figure 5.9, and visualizations are created from training samples. Visually, the autoencoded $\hat{\bm{x}}$ faithfully captures major visual features from its respective training sample $\bm{x}$, especially the pose, shape, and layout. For the simpler dataset such as MNIST, autoencoded images are almost identical to the original.

The simple linear structures of LDR make it uniquely suited for incremental learning: the distribution of features $\bm{Z}_{j}$ of each previously learned class can be explicitly and concisely represented by a principal subspace $\mathcal{S}_{j}$ in the feature space. To preserve the memory of an old class $j$, we only need to preserve the subspace while learning new classes. To this end, we simply sample $m$ representative prototype features on the subspace along its top $r$ principal components, and denote these features as $\bm{Z}_{j,old}$. Because of the simple linear structures of LDR, we can sample from $\bm{Z}_{j,old}$ by calculating the mean and covariance of $\bm{Z}_{j,old}$ after learning class $j$. The storage required is extremely small, since we only need to store means and covariances, which are sampled from as needed. Suppose a total of $t$ old classes have been learned so far. If prototype features, denoted $\bm{Z}_{old}\doteq[\bm{Z}^{1}_{old},\ldots,\bm{Z}^{t}_{old}]$, for all of these classes can be preserved when learning new classes, the subspaces $\{\mathcal{S}_{j}\}_{j=1}^{t}$ representing past memory will be preserved as well. Details about sampling and calculating mean and covariance can be found in the work of [TDW+23].

Notice that, with the learned autoencoding (5.2.9), one can replay and use the images, say $\hat{\bm{X}}_{old}=g(\bm{Z}_{old},\bm{\eta})$, associated with the memory features to avoid forgetting while learning new classes. This is typically how generative models have been used for prior incremental learning methods. However, with the closed-loop framework, explicitly replaying images from the features is not necessary. Past memory can be effectively preserved through optimization exclusively on the features themselves.

Consider the task of incrementally learning a new class of objects.¹³¹³13Of course, one may also consider the more general setting where the task contains a small batch of new classes, without serious modification. We denote a corresponding new sample set as $\bm{X}_{new}$. The features of $\bm{X}_{new}$ are denoted as $\bm{Z}_{new}(\bm{\theta})=f(\bm{X}_{new},\bm{\theta})$. We concatenate them together with the prototype features of the old classes $\bm{Z}_{old}$ and form $\bm{Z}=[\bm{Z}_{new}(\bm{\theta}),\bm{Z}_{old}]$. We denote the replayed images from all features as $\hat{\bm{X}}=[{\hat{\bm{X}}_{new}(\bm{\theta},\bm{\eta})},{\hat{\bm{X}}_{old}(\bm{\eta})}]$ although we do not actually need to compute or use them explicitly. We only need features of replayed images, denoted $\hat{\bm{Z}}=f(\hat{\bm{X}},\bm{\theta})=[{\hat{\bm{Z}}_{new}(\bm{\theta},\bm{\eta})},{\hat{\bm{Z}}_{old}(\bm{\theta},\bm{\eta})}]$.