14.4 Dimensionality Reduction II: Advanced Techniques

Beyond Linearity: Manifold Learning

While PCA is excellent for finding linear structures in data, many real-world datasets have complex, non-linear relationships. For example, the data might lie on a curved surface, or "manifold," within the high-dimensional space.

Manifold learning algorithms are designed to uncover these underlying non-linear structures. Two of the most powerful and popular techniques are t-SNE and UMAP.

t-Distributed Stochastic Neighbor Embedding (t-SNE)

t-SNE is a technique for visualizing high-dimensional data by giving each datapoint a location in a two or three-dimensional map. It is particularly good at revealing the local structure of the data, such as clusters.

How it Works: The Intuition

1. High-Dimensional Similarities: t-SNE starts by converting high-dimensional Euclidean distances between data points into conditional probabilities that represent similarities. The similarity of datapoint \(x_j\) to datapoint \(x_i\) is the probability \(p_{j|i}\) that \(x_i\) would pick \(x_j\) as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at \(x_i\).
2. Low-Dimensional Similarities: Next, t-SNE defines a similar probability distribution for the points in the low-dimensional map (e.g., 2D). Here, it uses a Student's t-distribution with one degree of freedom, which has heavier tails than a Gaussian. This allows dissimilar points to be placed further apart in the map.
3. Minimizing Divergence: The algorithm then minimizes the Kullback-Leibler (KL) divergence between the two distributions of similarities (high-dim and low-dim). This process adjusts the positions of the points in the low-dimensional map to best represent the high-dimensional structure.

A key parameter in t-SNE is perplexity, which can be thought of as a guess about the number of close neighbors each point has. Typical values are between 5 and 50.

Uniform Manifold Approximation and Projection (UMAP)

UMAP is a more recent dimensionality reduction technique that is often faster than t-SNE and can be better at preserving the global structure of the data.

It is based on a solid mathematical foundation in manifold theory and topology. Like t-SNE, it works by modeling the manifold with a fuzzy topological structure and then finding a low-dimensional embedding that has a similar structure. UMAP is often preferred for larger datasets due to its performance and better balance between local and global detail.