UMAP for dimensionality reduction

Think of it like making a map of a crumpled piece of paper: you want neighborhoods to stay together, but you also want the overall layout to make sense.

Why UMAP? The Motivation

The Problem withCA: Linear projection loses manifold structure (think: projecting a Swiss roll).

The Problem with t-SNE:

• Optimizes only local structure → global distances meaningless
• Computationally expensive: $O(n^2)$
• Non-deterministic layout between runs
• Doesn't preserve density information

UMAP's Solution:

1. Model high-D data as a fuzy topological structure (Riemannian manifold)
2. Construct a similar structure in low-D
3. Find the layout that makes these two structures as similar as possible
4. Use clever approximations to make it fast: $O(n^{1.14})$ instead of $O(n^2)$

Key Hyperparameters:

• n_neighbors ($k$): Controls local vs global structure balance (typical: 5-50)
• min_dist: Minimum separation in low-D embedding (typical: 0.0-0.99)
• metric: Distance function in high-D space (Euclidean, cosine, etc.)

Output: Low-dimensional embedding $\mathbf{Y} \in \mathbb{R}^{n \times d'}$ (typically $d' = 2$ or $3$)

Derivation from First Principles

Step 1: Build the High-Dimensional Graph

For each point $x_i$, find its $k$ nearest neighbors. We model the "connectedness" between points as fuzy sets.

The Distance-to-Similarity Transform:

For point $x_i$ and its neighbor $x_j$, compute:

Why this formula?

• $d_{ij}$: Distance between points $i$ and $j$
• $\rho_i$: Distance to the nearest neighbor of $x_i$ (makes each point "see" at least one neighbor with weight ~1)
• $\sigma_i$: Local bandwidth chosen so that $\sum_{j \in N(i)} w_{ij} = \log_2(k)$ (ensures consistent local density modeling)
• The exponential decay creates a smooth transition: close neighbors get high weights, distant ones fade to zero

Why $\rho_i$? This is the "local connectivity" constraint. Each point must see its immediate nearest neighbor fully connected (weight = 1) to avoid isolated points. We subtract $\rho_i$ so the decay starts after the first neighbor.

Symmetrization (fuzy set union):

This creates an undirected graph where connection strength reflects fuzy topological membership.

Step 2: Define the Low-Dimensional Layout

In the low-D space, we want similar fuzy connectivity. Use a different kernel:

Why this t-distributionlike kernel?

• Allows both tight clusters (small distances) and separated groups (large distances)
• Parameters $a, b$ (typically $a=1.929, b=0.7915$ from fitting) control the spread
• Heavy tails prevent "crowding problem" where too many points compress into small space

Step 3: Optimize the Cross-Entropy Loss

We want the low-D fuzy structure to match the high-D one. Measure disagrement with cross-entropy:

Breaking this down:

1. First term: If high-D says "connected" ($w_{ij}$ high), penalize if low-D disagrees ($v_{ij}$ low)
2. Second term: If high-D says "disconnected" ($w_{ij}$ low), penalize if low-D has them close ($v_{ij}$ high)

Why cross-entropy? It's the natural measure of difference between probability distributions (fuzy sets are modeled as probabilities).

Optimization: Use stochastic gradient descent with:

• Negative sampling (sample unconnected pairs to enforce repulsion)
• Initial layout via spectral embedding (for speed)
• Typical: 500 epochs, learning rate starts at 1.0

High-D Edge Weight: $w_{ij} = \exp\left(-\frac{\max(0, d_{ij} - \rho_i)}{\sigma_i}\right)$

Low-D Edge Weight: $v_{ij} = \frac{1}{1 + a \cdot ||y_i - y_j||_2^{2b}}$

Optimization Objective: $\min_{\mathbf{Y}} \sum_{i,j} w_{ij}^{\text{sym}} \log\left(\frac{w_{ij}^{\text{sym}}}{v_{ij}}\right) + (1 - w_{ij}^{\text{sym}}) \log\left(\frac{1 - w_{ij}^{\text{sym}}}{1 - v_{ij}}\right)$

Scenario: Embedings of 1000 MNIST digits

With n_neighbors=5:

• Each point looks at only 5 nearest neighbors
• High-D graph is very sparse
• Low-D embedding emphasizes local structure: tight, well-separated digit clusters
• May fragment large manifolds into disconnected pieces

With n_neighbors=50:

• Each point looks at 50 neighbors
• High-D graph is denser, captures broader context
• Low-D embedding preserves global structure: relationships between digit groups visible
• Clusters may blend more at boundaries

Why this behavior? The $\sigma_i$ parameter adjusts to fit $\log_2(k)$ total weight. With small $k$, only immediate neighbors matter → local focus. With large $k$, distant connections get nonzero weight → global awareness.

Rule of thumb:

• Small data or finding fine clusters: $k \in [5, 15]$
• Large data or preserving global structure: $k \in [30, 100]$

Setup: 500 cells from single-cell RNA-seq, 2000 genes

With min_dist=0.0:

• Points allowed to packightly
• Calculation: Low-D kernel $v_{ij} = \frac{1}{1 + a \cdot d^{2b}}$ can approach 1 even when $d \to 0$
• Result: Dense clusters, clear separation, preserves local density information
• Use case: Identifying tight cell type clusters

With min_dist=0.8:

• Points must maintain spacing
• Calculation: Optimization penalizes $d < 0.8$, forces repulsion
• Result: More "inflated" layout, easier to see individual points, loses some density info
• Use case: Visualization where point overlap hides structure

Why this step? min_dist directly modifies the attractive force in the gradient. Higher values add repulsion at short range.

Given: Point $x_i$ with $k$ neighbors at distances $d_{i1}, d_{i2}, \ldots, d_{ik}$ (sorted). Nearest neighbor distance $\rho_i = d_{i1}$.

Goal: Find $\sigma_i$ such that: $\sum_{j=1}^{k} \exp\left(-\frac{\max(0, d_{ij} - \rho_i)}{\sigma_i}\right) = \log_2(k)$

Why $\log_2(k)$? This comes from information theory: perplexity (effective number of neighbors) should match $k$. In t-SNE terms, $\text{perplexity} = 2^{\text{entropy}}$. UMAP targets entropy = $\log_2(\log_2(k))$ for numerical stability.

Solution via Binary Search:

1. First neighbor: $d_{i1} = \rho_i$, so $w_{i1} = \exp(0) = 1$
2. Other neighbors: $w_{ij} = \exp\left(-\frac{d_{ij} - \rho_i}{\sigma_i}\right)$ for $j > 1$
3. Target: $1 + \sum_{j=2}^{k} \exp\left(-\frac{d_{ij} - \rho_i}{\sigma_i}\right) = \log_2(k)$

For $k=15$: target $= \log_2(15) \approx 3.906$

If $\sigma_i$ too small → weights decay too fast → sum< target → increase $\sigma_i$ If $\sigma_i$ too large → weights decay too slowly → sum > target → decrease $\sigma_i$

Converge via binary search in ~20 iterations.

Example numbers (Manhattan distance on images):

• $k = 15$, $\rho_i = 45.2$ pixels
• Neighbor distances: 45.2, 52.1, 58.3, 67.8, 73.2, ...
• Solved $\sigma_i \approx 18.4$ pixels
• Weights: 1.00, 0.71, 0.49, 0.28, 0.17, ... (sum≈ 3.906 ✓)

The Wrong Idea: UMAP and t-SNE do the same thing, UMAP is simply optimized better.

Why It Feels Right: Both produce2D scatter plots with clear clusters, both use neighbor graphs, both are nonlinear.

The Truth:

1. Mathematical foundation differs:

   • t-SNE: KL-divergence between probability distributions
   • UMAP: Cross-entropy on fuzzy topological structures (category theory basis)

2. Global structure:

   • t-SNE explicitly discards global distances (only preserves local neighborhoods)
   • UMAP balances local + global via the $\sigma_i$ calibration and negative sampling strategy

3. Inverse transform:

   • t-SNE: Cannot embed new points without retraining
   • UMAP: Can learn inverse mapping (new point → low-D) via parametric version

4. Hyperparameter meaning:

   • t-SNE perplexity: "effective number of neighbors to consider"
   • UMAP n_neighbors: "balance local vs global" (affects graph connectivity fundamentally)

The Fix: Think of UMAP as "manifold learning with topological constraints" not "improved clustering visualization."

The Wrong Idea: "My dataset has 100,000 points, I'll use n_neighbors=5to keep computation fast."

Why It Feels Right: Smaller $k$ → sparser graph → faster computation.

The Problem:

• With 100k points and $k=5$, you have 500k edges
• But the data may have natural clusters of size ~10,000
• Each point only "sees" 5 neighbors → only local structure captured
• Result: Large coherent structures fragment into many disconnected pieces
• You get "archipelagos" instead of continents

The Fix:

• For $n$ points, use $k \geq 0.5\sqrt{n}$ as minimum for global structure
• For 100k points: use $k \geq 150$
• UMAP's approximations keep this fast (nearest neighbor search via random projection forests)

Verification: Check graph connectivity:

from umap import UMAP
from scipy.sparsecsgraph import connected_components
 
umap_model = UMAP(n_neighbors=5)
umap_model.fit(X)
graph = umap_model.graph_
n_components, labels = connected_components(graph)
print(f"Disconnected components: {n_components}")  # Should be ~1, not ~1000

Rule 1: Knots that are neighbors in the ball should stay neighbors on the table. If two knots were touching, don't put them on opposite sides of the table!

Rule 2: If two bunches of knots were far apart in the ball, keep them far apart on the table too. Don't make everything smosh into one blob.

UMAP's job is to untangle the yarn following both rules. Here's how:

1. Build a friendship network: Each knot looks at its 15 closest neighbors and says "these are my friends" with different levels of friendship (super close friends get score 1.0, acquaintances get score 0.2).

2. Make a flat map: Put all the knots on the table randomly to start. Now move them around: pull friends closer together, push non-friends farther apart.

3. Keep adjusting: Do this 500 times until the friendship network on the table matches the friendship network in the original tangled ball.

The magic? UMAP doesn't just care about immediate neighbors (like t-SNE). It looks at your15 closest friends, and through them, learns about the whole neighborhood structure. That's why the final flat map shows both tight friend groups AND how those groups relate to each other across the table.

• Unfold: Take curved high-D manifold and flatten it
• Manifolds: Data lies on curved surfaces, not just in Euclidean space
• And: Both local AND global structure (not "or")
• Preserve: Keep topological relationships intact

Alternative: "Use My Awesome Projection" (when your t-SNE is too slow)

Hyperparameter Tuning Guide

Connections to Other Concepts

• t-SNE: UMAP's predecessor for visualization, focuses only on local structure
• PCA: Linear dimensionality reduction, fast but mises manifolds
• Autoencoders: Neural alternative for dimensionality reduction with inverse mapping
• Isomap: Earlier manifold learning method via geodesic distances
• Spectral Clustering: Uses similar graph Laplacian concepts for initialization
• Nearest Neighbors Algorithms: UMAP relies heavily on fast KNN search
• Cross-Entropy Loss: Core optimization objective for matching distributions
• Random Projection: Used internally for approximate nearest neighbor search
• Topological Data Analysis: Provides mathematical foundation for fuzy simplicial sets

When to Use UMAP vs Alternatives

Use UMAP when:

• Dataset size: 1k-10M points (scales well)
• Need both local clusters AND global structure
• Want reproducible results (set random_state)
• Need to embed new points later (parametric UMAP)
• Computational constraints (faster than t-SNE)

Use t-SNE when:

• Dataset size: <10k points
• Only care about local cluster separation for visualization
• Have tried UMAP and clusters blend too much (increase n_neighbors if so)

Use PCA when:

• Need linear interpretability (loadings)
• Data actually is linear (rare!)
• Want deterministic results
• Need fast transforms for millions of points

Use Autoencoders when:

• Have GPU resources
• Need differentiable inverse mapping
• Want to combine with other neural network losses

#flashcards/ai-ml

What does UMAP stand for? :: Uniform Manifold Approximation and Projection

Concept Map

Hinglish (regional understanding)