References

• How exactly UMAP works: very mathematical description of t-SNE and its limitations, comparison with UMAP, how UMAP works — Towards Data Science
• Notes on implementation and parameters for t-SNE
• Tips on avoiding misinterpretation of t-SNE — Distill
• How UMAP works — PAIR
• Deeper dive into the math behind UMAP — PAIR

---

t-Distributed Stochastic Neighbor Embedding (t-SNE)

Nonlinear dimensionality reduction technique for visualization in 2/3D space: models each high-dimensional object as a 2/3D point such that similar objects are nearby and dissimilar objects are far apart.

Algorithm

1. Construct probability distribution across all high-D objects so that similar objects have a high likelihood of being picked and dissimilar objects a low likelihood
2. Define similar probability distribution over points in 2/3D space
3. Minimize Kullback-Leibler divergence (KL-divergence — measure of how two probability distributions differ) between the distributions to "respect the mapping"

Interpretation and precautions

• TL;DR: be careful — high flexibility means lots of room for misinterpretation
• Highly influenced by hyperparameter choice (esp. perplexity) → can easily lead to false discovery of clustering
• Does not preserve global data structure: only within-cluster distances are meaningful; others are influenced by perplexity — lower perplexity "spreads out" data with little preservation of high-D structure; preserving structure requires very high perplexity, which is slow
• Does not scale well computationally for large datasets; cannot work directly with high-dimensional data (requires autoencoder or PCA first)
• Stochastic → can produce very different results across runs

---

Uniform Manifold Approximation and Projection (UMAP)

Non-linear dimensionality reduction. Fast and scalable (to both dataset size and dimensionality).

Algorithm

• Construct high-dimensional graph with fuzzy simplicial complex — a weighted graph where edge weights represent likelihood of connection
  • Determine connectedness by extending a radius from each point and connecting those in the neighborhood; radius chosen based on number of nearest neighbors (n)
  • Fuzziness = decreasing likelihood of connection as radius increases
  • Ensures both local and global structure are preserved by connecting each point to at least one nearest neighbor
• Construct optimal low-dimensional layout based on the above mapping (similar to t-SNE but with better efficiency)
• Parameters — control balance between local and global structure:
  1. n_neighbors — number of neighbors used to construct the initial high-D graph; lower = more local structure, higher = more global structure with some loss of fine detail
  2. min_dist — minimum distance between points in the low-D graph; lower = tighter clumping, higher = looser with better preservation of global topology

Other considerations

• Better efficiency/speed than t-SNE
• Better preservation of global data structure → more meaningful inter-cluster distances (though still potentially arbitrary)
• Relative cluster size still doesn't mean anything
• Still stochastic, but gives more consistent results across repeated runs
• Still highly affected by hyperparameter choice → need to test various combinations