Principal Component Analysis (PCA) & Autoencoders

Recap & Introduction

The methods covered so far - regression, classification, and SVMs - are all supervised: they learn from labeled examples. We now turn to unsupervised learning, where the goal is to discover structure in data without labels. The central technique is dimensionality reduction: finding low-dimensional representations that capture the essential variation in high-dimensional data. This section builds on the eigenvalue decomposition and SVD from Section I, and extends PCA to nonlinear settings using both kernels and neural networks.

Principal Component Analysis (PCA) is one of the most fundamental techniques in machine learning and statistics for dimensionality reduction. It provides a method to reduce the number of variables in high-dimensional datasets while retaining the most meaningful structure and variation present in the original data.

PCA begins by analyzing the covariance structure of the data. Given a dataset, we compute the covariance matrix to understand how different features co-vary. Since the covariance matrix is always symmetric and positive semi-definite, it can be orthogonally diagonalized. The resulting eigenvectors, called principal components (PCs), form an orthonormal basis that captures the directions of maximum variance. The corresponding eigenvalues indicate how much of the total variance is captured by each component.

By projecting the data onto the subspace spanned by the top \(k\) principal components (those associated with the largest eigenvalues), PCA identifies a lower-dimensional representation that retains as much variance as possible. This allows us to reduce dimensionality by discarding less informative directions (i.e., those with small variance), thereby simplifying the dataset while minimizing information loss.

For example, if a dataset in \(\mathbb{R}^{10}\) has 3 principal components capturing 95% of the total variance, we can project the original data onto a 3D subspace. This projection preserves the dominant patterns and relationships in the data and filters out noise and redundancy. The transformed vectors in the low-dimensional space are known as latent representations.

While PCA is a powerful tool, it identifies directions of maximum variance using linear combinations of the original features. As a result, it may fail to uncover complex, nonlinear structures in the data.

Kernel PCA

Given an \(N \times D\) data matrix, PCA requires the eigenvectors of the \(D \times D\) covariance matrix \(X^\top X\). If \(D \gg N\), working with the \(N \times N\) Gram matrix \(K = \Phi \Phi^\top\) is much more efficient - its entries are inner products \(\langle \phi(x_i), \phi(x_j) \rangle\). In the linear case, \(\phi\) is the identity and \(K_{ij} = x_i^\top x_j\).

Kernel PCA (KPCA) is a nonlinear generalization of classical PCA that uses the kernel trick, which allows us to replace inner products \(x_i^\top x_j\) with a kernel function \(K_{ij} = \mathcal{K}(x_i, x_j)\).

The kPCA implicitly replaces \(x_i\) with \(\phi(x_i) = \phi_i\). Let \(\Phi\) be the corresponding design matrix. Assuming the features are centered, the covariance matrix in feature space is represented by: \[ S_{\phi} = \frac{1}{N} \sum_i \phi_i \phi_i^T. \] The normalized eigenvectors of \(S\) are given by: \[ V_{kPCA} = \Phi^\top U \Lambda^{-\frac{1}{2}} \] where \(U\) is an orthogonal matrix containing the eigenvectors of the kernel (Gram) matrix \(K = \Phi \Phi^\top\) with corresponding eigenvalues in \(\Lambda\).

Since \(\phi_i\) can be infinite dimensional, we cannot compute \(V_{kPCA}\) directly. Instead, we express the projection of a test vector \(x_*\) entirely in terms of kernel evaluations:

Note that using \(K = \Phi \Phi^\top\) is valid only if \(\mathbb{E}[\phi_i] = 0\). However, the feature space can be infinite dimensional, so we cannot subtract off the mean. Here, we introduce the double centering trick. Let the centered feature vector be \[ \tilde{\phi}_i = \phi(x_i) - \frac{1}{N} \sum_{j =1}^N \phi(x_j). \] Its Gram matrix is given by \[ \tilde{K}_{ij} = \tilde{\phi}_i^\top \tilde{\phi}_j. \]

Autoencoders

Data reconstruction serves as the primary quality control mechanism for dimensionality reduction. When we compress data from the original high-dimensional feature space \(\mathbb{R}^D\) to low-dimensional space \(\mathbb{R}^L\) (where \(L < D\)), we need to ensure that the essential structure and information of the original data is preserved. The reconstruction error provides a quantitative measure of information loss. If reconstruction is poor, the learned representation is inadequate for the task at hand.

Reconstruction ensures that the learned latent representation \(z = f_e(x)\) captures the most relevant and meaningful features of the data. The function \(f_e : x \to z\) is called the encoder. If the decoder \(f_d : z \to x\) can successfully reconstruct the original input \(x\) from \(z\), it demonstrates that \(z\) contains sufficient information about the underlying data structure.

We can consider PCA as the process of learning linear mappings such as \(f_e\) and \(f_d\). Then the reconstruction function can be represented as \(r(x) = f_d \left(f_e(x) \right)\), which is trained to minimize \(\mathcal{L}(\theta) = -\log p(x | r(x))\).

We can implement \(f_e\) and \(f_d\) by neural networks. This is called an autoencoder. In particular, a linear autoencoder is equivalent to PCA:

In general, it is known that if we introduce nonlinearities into the autoencoder, the model becomes strictly more powerful than PCA. Moreover, autoencoders designed with deep learning architectures handle large datasets and complex structures much better than Kernel PCA, so autoencoders have generally become more popular than Kernel PCA for nonlinear mapping in practical applications.

Demo: Kernel PCA and Autoencoders

This interactive demo allows you to explore and compare different dimensionality reduction techniques:

PCA Comparison Tab

Compare how standard PCA and Kernel PCA handle non-linear datasets. Standard PCA finds linear projections, while Kernel PCA can "unfold" complex structures like circles and spirals using the kernel trick. Try different kernels (RBF, polynomial) and adjust parameters to see their effects.

Autoencoder Tab

Explore how a neural network autoencoder with a 1D bottleneck learns to compress and reconstruct 2D data. Unlike PCA which finds linear subspaces, the autoencoder learns non-linear mappings through its hidden layers. The 1D latent space visualization shows how the network arranges data points along a single dimension, effectively finding the principal curve through the data.

💡Tip:
Start with the "circles" dataset to see how each method handles non-linear structure. PCA will struggle, Kernel PCA (with RBF kernel) will separate the circles, and the autoencoder will "unfold" them into a line.

Denoising Autoencoders

Denoising autoencoders (DAE) are a more regularized variant of standard autoencoders that add noise to the input during training, then learn to reconstruct the original, uncorrupted data. This seemingly simple modification has profound theoretical implications.

The training process involves corrupting the input \(x\) to produce \(\tilde{x}\), typically using Gaussian noise: \[ p_c (\tilde{x} | x) = \mathcal{N}(\tilde{x} | x, \sigma^2 I) \] The model then minimizes the reconstruction error between its output \(r(\tilde{x})\) and the clean input \(x\): \[ \ell (x, r(\tilde{x})) = \| e \|_2^2 \] where \(e(x) = r(\tilde{x}) - x \) is the residual error for a sample \(x\).

This score function forms a vector field over the entire feature space. At each point, this vector field indicates the direction and magnitude to move toward regions of higher data density. The reconstruction process follows these vectors, effectively "flowing" corrupted points back to the data manifold along the steepest ascent of the probability landscape.

Data Manifolds in Our Demo:

The autoencoder tab in our demo visualizes data manifolds. When the 2D data is compressed through a 1D bottleneck, the network must learn the underlying 1-D manifold (curve) that best represents the data. The "Reconstructed" visualization shows points projected onto this learned manifold This is the autoencoder discovering and representing the intrinsic lower-dimensional structure of the data.

Note: Lipschitz continuity is a common regularity condition that ensures a function does not change too rapidly.

This means the function's output changes at most linearly with respect to the input. In autoencoders, Lipschitz continuity in the reconstruction map \(r(x)\) ensures stability - small changes in input lead to small changes in reconstruction.

In the context of denoising autoencoders, enforcing or assuming Lipschitz continuity makes the learned vector field well-behaved. It guarantees smooth flows along the data manifold and avoids sharp or unstable reconstructions, which is essential when approximating the gradient \(\nabla_x \log p(x)\).

Manifolds

Intuitively, a manifold is a topological space that locally resembles Euclidean space near each point. Imagine a curved surface like a sphere—zooming in on any small patch makes it look flat, like \(\mathbb{R}^2\). In machine learning, we often assume data lies on a low-dimensional manifold embedded in high-dimensional space.

The Manifold Hypothesis: Real-world high-dimensional data (e.g., images, speech) tends to lie on or near a low-dimensional manifold embedded in the ambient space. For example, each \(64 \times 64\) grayscale face image can be represented as a point in \(\mathbb{R}^{4096}\), but the set of "realistic" face images occupies only a small, structured region of this space - likely a nonlinear manifold of much lower dimension, governed by factors such as pose, lighting, expression, and identity.

Dimensionality reduction reveals low-dimensional structure in data, but does not assign data points to groups. In Part 8: Clustering, we address this complementary unsupervised task: partitioning data into meaningful groups without labels. We will see how K-means minimizes distortion in the original feature space, while spectral clustering leverages the graph Laplacian to discover clusters that respect the geometry of the data manifold.