M2-060M2: Classical Machine LearningDimensionality ReductionMedium
⚡Flashcard Drill➔Mastery:

Compare t-SNE and UMAP: Manifold Assumptions, Global vs. Local Structure, and Computational Scaling

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-061 →
📐 Mathematical Definition
t-SNE: min⁡KL(P∥Q),qij∝(1+∥yi−yj∥2)−1\text{t-SNE}:\ \min\mathrm{KL}(P\|Q),\quad q_{ij}\propto(1+\|y_i-y_j\|^2)^{-1}
⚡ One-Sentence Core Answer
t-SNE models local neighborhood similarities via Gaussian-Student-t divergences (O(N2)O(N^2)); UMAP models Riemannian manifold topology via fuzzy simplicial sets (O(Nlog⁡N)O(N\log N)), running 10×10\times faster while preserving both global and local structure.

📌 Key Takeaways

  • •
    t-SNE (van der Maaten & Hinton, 2008): Uses Student-t distribution with 1 degree of freedom in low-dimensional space to resolve the 'crowding problem'; preserves local clusters but distorts global distances.
  • •
    UMAP (McInnes et al., 2018): Grounded in Riemannian geometry and algebraic topology; preserves both local clustering and macro global continuum geometry.
  • •
    Computational Speed: UMAP uses approximate nearest neighbor graphs (PyNNDescent) and stochastic gradient descent with negative sampling, scaling to millions of points, while standard t-SNE struggles beyond 50,000 points.
  • •
    Out-of-sample projection: UMAP learns a generalizable parametric mapping (f(xnew)f(x_{\text{new}}) can be transformed without retraining); t-SNE cannot project new points.

📐 Mathematical Derivations

The Crowding Problem in t-SNE: In high dimensions DD, the volume of a sphere of radius rr scales as rDr^D. Ten equidistant points can easily reside in D=100D=100. In d=2d=2 dimensions, the area scales only as r2r^2. If we used a Gaussian distribution in 2D, moderate distances in high-D would be forced to crowd together into the center. t-SNE resolves this by using the heavy-tailed Cauchy (Student-t with df=1\text{df}=1) distribution in the low-dimensional map: qij=(1+∥yi−yj∥2)−1∑k≠l(1+∥yk−yl∥2)−1q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k \ne l}(1 + \|y_k - y_l\|^2)^{-1}}. Because the tail decays as an inverse square 1/r21/r^2 rather than exponential e−r2e^{-r^2}, moderate distances in high dimensions are pushed far apart in the 2D plot, cleanly separating distinct clusters. Objective is minimized via KL divergence: L=∑i≠jpijlog⁡pijqij\mathcal{L} = \sum_{i \ne j} p_{ij} \log\frac{p_{ij}}{q_{ij}}.

🏭 Production Trade-offs

Comparative selection matrix: (1) Visualization: Both produce stunning 2D/3D visualizations. UMAP preserves trajectories and continuum relationships (e.g. Single-cell developmental pseudotime lineages). (2) Feature Engineering for ML: UMAP can be used as a non-linear feature extractor in training pipelines because umap.transform(X_test) projects unseen test data into the embedding space, whereas t-SNE requires non-parametric retraining.
⚠️ Common Interview Pitfalls
  • ✕
    Interpreting distances between separated clusters in t-SNE as meaningful global metrics (t-SNE distances between distant clusters are essentially arbitrary).
  • ✕
    Interpreting cluster sizes or densities in t-SNE as true variance (t-SNE's perplexity parameter forces all clusters to appear with roughly equal visual spread).
🎯 Interviewer Follow-up Inquiries
  • ?
    Why does UMAP preserve global distances substantially better than t-SNE?
  • ?
    How does fuzzy simplicial set union in UMAP prevent disconnected graph components?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-059: Enumerate the Limitations of PCA and Scenarios Where Linear PCA Fails📋 Back to BankNext →M2-061: How to Choose Target Dimensions in Dimensionality Reduction? Variance Ratio Method and Limitations