UMAP: Algorithm Components and Construction
What you'll learn: How UMAP constructs its mathematical representation and optimizes it to create meaningful low-dimensional embeddings.
The Three Core Stages
UMAP builds dimensionality reduction in three distinct steps, each transforming your high-dimensional data closer to its final embedded form.
1. Building the Fuzzy Simplicial Set
Think of this as creating a "soft neighborhood graph" where each point is connected to its nearest neighbors with varying degrees of certainty. Unlike a hard graph where edges either exist or don't, UMAP's fuzzy approach assigns membership strengths between 0 and 1 to each connection.
For each point, UMAP finds its k-nearest neighbors and computes how strongly each neighbor belongs to that point's local neighborhood. Closer neighbors get higher membership values (near 1.0), while more distant ones get lower values (closer to 0). This creates a probabilistic view of the data's local structure.
2. Computing Membership Strengths
The membership strength between two points depends on their distance relative to the local neighborhood density. UMAP uses an exponential decay function: nearby points have strong memberships, which smoothly decrease as distance increases. The result is a weighted graph where edge weights represent how confident UMAP is that two points belong together.
3. Cross-Entropy Optimization
Now UMAP has two graphs: the high-dimensional fuzzy set and a similar structure in the low-dimensional space (initially random). The goal? Make them match. UMAP uses cross-entropy as the optimization objective—measuring how different the two probability distributions are—and minimizes this difference through gradient descent, moving points in the embedding until the local neighborhoods align.
Key Takeaway: UMAP constructs a fuzzy simplicial set with membership strengths representing neighborhood relationships, then minimizes cross-entropy between high and low-dimensional representations to preserve local structure while revealing global patterns.