AI summary by TwinMind
UMAP: Mathematical Details (clearly explained!!!)
StatQuest with Josh Starmer
16m 1s
Introduction and Prerequisites
- StatQuest episode on UMAP mathematical details by Josh Starmer
- Sponsored by Lightning and Grid.ai
- Assumes familiarity with:
- UMAP main ideas
- Gradient descent and stochastic gradient descent
High Dimensional Similarity Score Calculation
- Raw high dimensional data transformed into similarity scores
- Process overview:
- Set number of neighbors (example: 3 neighbors)
- Take log base 2 of neighbor count: log₂(3) = 1.6
- Draw curves for each point where similarity scores sum to 1.6
Similarity Score Equation
- Formula: e^(-(raw distance - distance to nearest neighbor)/σ)
- Example with σ = 1:
- Point B relative to A: distance = 0.5, nearest neighbor distance = 0.5
- Calculation: e^(-(0.5-0.5)/1) = e^0 = 1.0
- Point C relative to A: distance = 2.4, calculation yields 0.15
- Sum of scores: 1.0 + 0.15 = 1.15 (target: 1.6)
Sigma Parameter Optimization
- Sigma adjusted to achieve target sum (1.6):
- σ = 2: scores become 1.0 and 0.39, sum = 1.39
- σ = 3.5: scores become 1.0 and 0.6, sum = 1.6 ✓
- Nearest neighbor similarity score always = 1 (regardless of σ)
- Different points require different σ values for optimal curves
Comparison with t-SNE
- t-SNE uses Gaussian curves for similarity scores
- Perplexity parameter in t-SNE similar to neighbor count in UMAP
- Both determine which points considered neighbors in high dimensional space
Symmetrical Score Calculation
- UMAP creates asymmetrical scores due to different curves per point
- t-SNE averages scores for symmetry
- UMAP uses fuzzy union operation: s₁ + s₂ - s₁ × s₂
- Example: B→C score (0.6) + C→B score (1.0) = 1.0 final symmetrical score
Low Dimensional Initialization and Scoring
- Low dimensional graph initialized using spectral embedding
- Points spread on number line initially
Low Dimensional Similarity Score Equation
- Formula: 1/(1 + α × d^(2β))
- Where d = low dimensional distance between points
- Default parameters: α = 1.577, β = 0.8951
- If α = β = 1, identical to t-SNE low dimensional scores
- Maximum score = 1 when distance = 0
Point Movement and Optimization Process
Random Point Selection
- Pick two points proportionally to high dimensional scores
- Example: points B and A selected, B moves closer to A
- Calculate low dimensional score: B relative to A = 0.14
Neighbor vs Non-Neighbor Scoring
- Neighbor score: 0.14 (B relative to A, same neighborhood)
- Non-neighbor score: 0.23 (B relative to E, different neighborhood)
- B moves closer to neighbors, further from non-neighbors
Cost Function Evaluation
- Uses neighbor and non-neighbor scores in cost function
- Current position cost: 2.23
- Moving B closer to A reduces cost: 1.17 → 0.08
- Moving too far past A increases cost again
Gradient Descent Implementation
- Calculate derivative of cost function
- Use stochastic gradient descent for optimization
- Move points one step at a time
- Randomness in SGD creates slightly different final graphs for same dataset
Key Differences from t-SNE
- Fuzzy union vs averaging for symmetrical scores
- More control over low dimensional point packing (α, β parameters)
- Different theoretical framework (topology and fuzzy sets)
