UMAP for dimensionality reduction — Hinglish notes

2.5.12 · AI-ML › Unsupervised Learning

Socho jaise ek crumple hua kaagaz ka map banana: tum chahte ho ki neighborhoods saath rahen, lekin overall layout bhi samajh mein aaye.

UMAP Kyun? Motivation

PCA ki Problem: Linear projection manifold structure kho deti hai (sochiye: Swiss roll ka projection).

t-SNE ki Problem:

Sirf local structure optimize karta hai → global distances meaningless ho jaati hain
Computationally expensive: $O (n^{2})$
Runs ke beech non-deterministic layout
Density information preserve nahi karta

UMAP ka Solution:

High-D data ko fuzy topological structure (Riemannian manifold) ki tarah model karo
Low-D mein similar structure construct karo
Woh layout dhundo jo in dono structures ko jitna ho sake utna similar banaye
Use clever approximations to make it fast: $O (n^{1.14})$ instead of $O (n^{2})$

Key Hyperparameters:

n_neighbors ( $k$ ): Local vs global structure balance control karta hai (typical: 5-50)
min_dist: Low-D embedding mein minimum separation (typical: 0.0-0.99)
metric: High-D space mein distance function (Euclidean, cosine, etc.)

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

First Principles se Derivation

Step 1: High-Dimensional Graph Banao

Har point $x_{i}$ ke liye, uske $k$ nearest neighbors dhundo. Hum points ke beech "connectedness" ko fuzy sets ki tarah model karte hain.

Distance-to-Similarity Transform:

Point $x_{i}$ aur uske neighbor $x_{j}$ ke liye, compute karo:

w_{ij} = exp (- \frac{max ( 0 , d _{ij} - ρ _{i} )}{σ _{i}})

Yeh formula kyun?

$d_{ij}$ : Points $i$ aur $j$ ke beech distance
$ρ_{i}$ : $x_{i}$ ke nearest neighbor tak ki distance (isse har point kam se kam ek neighbor ko weight ~1 ke saath "dekhta" hai)
$σ_{i}$ : Local bandwidth jo is tarah choose ki jaati hai ki $\sum_{j \in N (i)} w_{ij} = lo g_{2} (k)$ (consistent local density modeling ensure karta hai)
Exponential decay ek smooth transition banata hai: paas ke neighbors ko high weights milte hain, door wale fade ho jaate hain

$ρ_{i}$ kyun? Yeh "local connectivity" constraint hai. Har point ko apne immediate nearest neighbor se fully connected (weight = 1) dikhna chahiye taaki isolated points na ho. Hum $ρ_{i}$ subtract karte hain taaki decay pehle neighbor ke baad shuru ho.

Symmetrization (fuzy set union):

w_{ij}^{sym} = w_{ij} + w_{j i} - w_{ij} \cdot w_{j i}

Isse ek undirected graph banta hai jahan connection strength fuzy topological membership reflect karti hai.

Step 2: Low-Dimensional Layout Define Karo

Low-D space mein hum similar fuzy connectivity chahte hain. Ek alag kernel use karo:

v_{ij} = \frac{1}{1 + a \cdot ∣∣ y _{i} - y _{j} ∣ ∣ _{2}^{2 b}}

Yeh t-distribution jaisa kernel kyun?

Tight clusters (chhoti distances) aur separated groups (badi distances) dono allow karta hai
Parameters $a, b$ (typically $a = 1.929, b = 0.7915$ fitting se) spread control karte hain
Heavy tails "crowding problem" ko rokti hain jahan bahut saare points chhoti jagah mein compress ho jaate hain

Step 3: Cross-Entropy Loss Optimize Karo

Hum chahte hain ki low-D fuzy structure high-D wale se match kare. Cross-entropy se disagreement measure karo:

L = i, j \sum w_{ij}^{sym} lo g (\frac{w _{ij}^{sym}}{v _{ij}}) + (1 - w_{ij}^{sym}) lo g (\frac{1 - w _{ij}^{sym}}{1 - v _{ij}})

Isko breakdown karte hain:

Pehla term: Agar high-D kehta hai "connected" ( $w_{ij}$ high), toh penalize karo agar low-D disagree kare ( $v_{ij}$ low)
Doosra term: Agar high-D kehta hai "disconnected" ( $w_{ij}$ low), toh penalize karo agar low-D unhe paas rakhe ( $v_{ij}$ high)

Cross-entropy kyun? Yeh probability distributions ke beech difference ka natural measure hai (fuzy sets ko probabilities ki tarah model kiya jaata hai).

Optimization: Stochastic gradient descent use karo:

Negative sampling (repulsion enforce karne ke liye unconnected pairs sample karo)
Initial layout spectral embedding se (speed ke liye)
Typical: 500 epochs, learning rate 1.0 se shuru hoti hai

High-D Edge Weight: $w_{ij} = exp (- \frac{m a x ( 0 , d _{ij} - ρ _{i} )}{σ _{i}})$

Low-D Edge Weight: $v_{ij} = \frac{1}{1 + a \cdot ∣∣ y _{i} - y _{j} ∣ ∣ _{2}^{2 b}}$

Optimization Objective: $min_{Y} \sum_{i, j} w_{ij}^{sym} lo g (\frac{w _{ij}^{sym}}{v _{ij}}) + (1 - w_{ij}^{sym}) lo g (\frac{1 - w _{ij}^{sym}}{1 - v _{ij}})$

Scenario: 1000 MNIST digits ki embeddings

n_neighbors=5 ke saath:

Har point sirf 5 nearest neighbors dekhta hai
High-D graph bahut sparse hai
Low-D embedding local structure emphasize karta hai: tight, well-separated digit clusters
Bade manifolds ko disconnected pieces mein fragment kar sakta hai

n_neighbors=50 ke saath:

Har point 50 neighbors dekhta hai
High-D graph denser hai, broader context capture karta hai
Low-D embedding global structure preserve karta hai: digit groups ke beech relationships visible hain
Clusters boundaries pe zyada blend ho sakte hain

Yeh behavior kyun? $σ_{i}$ parameter adjust hota hai $lo g_{2} (k)$ total weight fit karne ke liye. Chhote $k$ ke saath, sirf immediate neighbors matter karte hain → local focus. Bade $k$ ke saath, door ke connections ko nonzero weight milta hai → global awareness.

Rule of thumb:

Chhota data ya fine clusters dhundne ke liye: $k \in [5, 15]$
Bada data ya global structure preserve karne ke liye: $k \in [30, 100]$

Setup: Single-cell RNA-seq se 500 cells, 2000 genes

min_dist=0.0 ke saath:

Points ko tightly pack hone diya jaata hai
Calculation: Low-D kernel $v_{ij} = \frac{1}{1 + a \cdot d ^{2 b}}$ 1 ke paas aa sakti hai jab bhi $d \to 0$
Result: Dense clusters, clear separation, local density information preserve hoti hai
Use case: Tight cell type clusters identify karna

min_dist=0.8 ke saath:

Points ko spacing maintain karni hogi
Calculation: Optimization $d < 0.8$ ko penalize karta hai, repulsion force karta hai
Result: Zyada "inflated" layout, individual points dekhna aasan, kuch density info kho jaati hai
Use case: Visualization jahan point overlap structure chhupa de

Yeh step kyun? min_dist directly gradient mein attractive force modify karta hai. Zyada values chhoti range par repulsion add karti hain.

Diya gaya: Point $x_{i}$ jiske $k$ neighbors hain distances $d_{i 1}, d_{i 2}, \dots, d_{ik}$ par (sorted). Nearest neighbor distance $ρ_{i} = d_{i 1}$ .

Goal: $σ_{i}$ dhundo aise ki: $\sum_{j = 1}^{k} exp (- \frac{m a x ( 0 , d _{ij} - ρ _{i} )}{σ _{i}}) = lo g_{2} (k)$

$lo g_{2} (k)$ kyun? Yeh information theory se aata hai: perplexity (effective number of neighbors) $k$ se match karni chahiye. t-SNE terms mein, $perplexity = 2^{entropy}$ . UMAP numerical stability ke liye entropy = $lo g_{2} (lo g_{2} (k))$ target karta hai.

Binary Search se Solution:

Pehla neighbor: $d_{i 1} = ρ_{i}$ , toh $w_{i 1} = exp (0) = 1$
Baaki neighbors: $w_{ij} = exp (- \frac{d _{ij} - ρ _{i}}{σ _{i}})$ for $j > 1$
Target: $1 + \sum_{j = 2}^{k} exp (- \frac{d _{ij} - ρ _{i}}{σ _{i}}) = lo g_{2} (k)$

$k = 15$ ke liye: target $= lo g_{2} (15) \approx 3.906$

Agar $σ_{i}$ bahut chhota → weights bahut fast decay karte hain → sum < target → $σ_{i}$ badhao Agar $σ_{i}$ bahut bada → weights bahut slowly decay karte hain → sum > target → $σ_{i}$ ghatao

~20 iterations mein binary search se converge karo.

Example numbers (images par Manhattan distance):

$k = 15$ , $ρ_{i} = 45.2$ pixels
Neighbor distances: 45.2, 52.1, 58.3, 67.8, 73.2, ...
Solved $σ_{i} \approx 18.4$ pixels
Weights: 1.00, 0.71, 0.49, 0.28, 0.17, ... (sum≈ 3.906 ✓)

Galat Idea: UMAP aur t-SNE ek hi kaam karte hain, UMAP sirf better optimize hai.

Kyun Sahi Lagta Hai: Dono clear clusters ke saath 2D scatter plots produce karte hain, dono neighbor graphs use karte hain, dono nonlinear hain.

Sachchi Baat:

Mathematical foundation alag hai:
- t-SNE: Probability distributions ke beech KL-divergence
- UMAP: Fuzzy topological structures par Cross-entropy (category theory basis)
Global structure:
- t-SNE explicitly global distances discard karta hai (sirf local neighborhoods preserve karta hai)
- UMAP $σ_{i}$ calibration aur negative sampling strategy se local + global balance karta hai
Inverse transform:
- t-SNE: Retraining ke bina naye points embed nahi kar sakta
- UMAP: Parametric version se inverse mapping (new point → low-D) seekh sakta hai
Hyperparameter meaning:
- t-SNE perplexity: "consider karne ke liye effective number of neighbors"
- UMAP n_neighbors: "local vs global balance" (graph connectivity fundamentally affect karta hai)

Fix: UMAP ko "improved clustering visualization" nahi, "manifold learning with topological constraints" socho.

Galat Idea: "Mere dataset mein 100,000 points hain, main n_neighbors=5 use karunga computation fast rakhne ke liye."

Kyun Sahi Lagta Hai: Chhota $k$ → sparser graph → faster computation.

Problem:

100k points aur $k = 5$ ke saath, aapke paas 500k edges hain
Lekin data mein natural clusters size ~10,000 ke ho sakte hain
Har point sirf 5 neighbors "dekhta" hai → sirf local structure capture hota hai
Result: Bade coherent structures bahut saare disconnected pieces mein fragment ho jaate hain
"Continents" ki jagah aapko "archipelagos" milte hain

Fix:

$n$ points ke liye, global structure ke liye minimum $k \geq 0.5 n$ use karo
100k points ke liye: $k \geq 150$ use karo
UMAP ki approximations ise fast rakhti hain (random projection forests se nearest neighbor search)

Verification: Graph connectivity check karo:

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

Recall UMAP ko ek 12-saal ke bachche ko explain karo

Socho tumhare paas ek huge crumpled ball of yarn hai jisme 1000 knots hain (tumhare data points). Yarn mein kuch structure hai — kuch knots paas paas hain aur bunches banate hain, kuch door hain. Tum is poori tangled mess ko ek table par flat rakhna chahte ho taaki pattern dikh sake, lekin tumhe do rules follow karne hain:

Rule 1: Knots jo ball mein neighbors the woh table par bhi neighbors rahen. Agar do knots touch kar rahe the, unhe table ke opposite sides par mat rakhna!

Rule 2: Agar knots ke do bunches ball mein door the, toh table par bhi unhe door rakhna. Sab kuch ek blob mein mat smosh karo.

UMAP ka kaam hai yarn ko dono rules follow karte hue sulajaana. Yaise:

Friendship network banao: Har knot apne 15 closest neighbors dekhta hai aur kehta hai "yeh mere dost hain" alag alag friendship levels ke saath (super close friends ko score 1.0 milta hai, acquaintances ko score 0.2).
Flat map banao: Shuru mein sare knots table par randomly rakho. Ab unhe move karo: friends ko paas kheencho, non-friends ko door dhakelo.
Adjust karte raho: Yeh 500 baar karo jab tak table par friendship network original tangled ball ki friendship network se match na kare.

Jaadu? UMAP sirf immediate neighbors ki parwaah nahi karta (jaise t-SNE karta hai). Yeh tumhare 15 closest friends dekhta hai, aur unke through, pure neighborhood structure ke baare mein seekhta hai. Isliye final flat map dono tight friend groups AUR kaise woh groups table par ek doosre se relate karte hain, dono dikhata hai.

Unfold: Curved high-D manifold lo aur use flatten karo
Manifolds: Data curved surfaces par hai, sirf Euclidean space mein nahi
And: Local AND global structure dono (na ki "or")
Preserve: Topological relationships intact rakho

Alternative: "Use My Awesome Projection" (jab tumhara t-SNE bahut slow ho)

Hyperparameter Tuning Guide

Parameter	Embedding par Effect	Typical Range	Zyada Kab Chunna	Kam Kab Chunna
n_neighbors	Local↔ Global balance	5-100	Bada dataset, global structure chahiye	Chhota dataset, tight clusters chahiye
min_dist	Cluster tightness	0.0-0.99	Separated points chahiye, better viz	Accurate local density chahiye
metric	Distance definition	euclidean, cosine, etc.	Data type demand kare (text→cosine)	Euclidean kaam kare (images, tabular)
n_components	Output dimensions	2-100	Downstream ML task	Sirf visualization

Doosre Concepts se Connections

t-SNE: Visualization ke liye UMAP ka predecessor, sirf local structure pe focus karta hai
PCA: Linear dimensionality reduction, fast hai lekin manifolds miss karta hai
Autoencoders: Inverse mapping ke saath dimensionality reduction ka neural alternative
Isomap: Geodesic distances ke zariye earlier manifold learning method
Spectral Clustering: Initialization ke liye similar graph Laplacian concepts use karta hai
Nearest Neighbors Algorithms: UMAP fast KNN search par heavily rely karta hai
Cross-Entropy Loss: Distributions match karne ke liye core optimization objective
Random Projection: Approximate nearest neighbor search ke liye internally use hota hai
Topological Data Analysis: Fuzy simplicial sets ke liye mathematical foundation provide karta hai

UMAP vs Alternatives Kab Use Karein

UMAP use karo jab:

Dataset size: 1k-10M points (acchi tarah scale hota hai)
Local clusters AUR global structure dono chahiye
Reproducible results chahiye (random_state set karo)
Baad mein naye points embed karne hain (parametric UMAP)
Computational constraints hain (t-SNE se faster)

t-SNE use karo jab:

Dataset size: <10k points
Visualization ke liye sirf local cluster separation chahiye
UMAP try kar chuke ho aur clusters zyada blend ho rahe hain (agar aisa ho toh n_neighbors badhao)

PCA use karo jab:

Linear interpretability chahiye (loadings)
Data actually linear hai (rare!)
Deterministic results chahiye
Millions of points ke liye fast transforms chahiye

Autoencoders use karo jab:

GPU resources hain
Differentiable inverse mapping chahiye
Doosre neural network losses ke saath combine karna hai

#flashcards/ai-ml

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

What is the key difference between UMAP and t-SNE in terms of structure preservation?

UMAP local neighborhoods AUR global structure dono preserve karta hai; t-SNE sirf local structure pe focus karta hai aur global distances discard karta hai

What is the role of the parameter ρᵢ in UMAP's edge weight formula?

ρᵢ point xᵢ ke nearest neighbor tak ki distance hai. Yeh local connectivity ensure karta hai ki nearest neighbor ka weight ≈1 ho (exponential decay ρᵢ ke baad shuru hoti hai)

What is the purpose of the σᵢ parameter in UMAP?

σᵢ local bandwidth parameter hai jo is tarah choose hota hai ki edge weights ka sum log₂(k) ke barabar ho, taaki sabhi points par consistent local density modeling ho sake

Why does UMAP use cross-entropy as its loss function?

Cross-entropy probability distributions ke beech difference measure karta hai. UMAP high-D aur low-D structures ko fuzy probability sets ki tarah model karta hai, toh cross-entropy quantify karta hai ki low-D layout high-D topology se kitna match karta hai

What happens if you set n_neighbors too small on a large dataset?

Graph bahut sparse ho jaata hai aur sirf local structure capture karta hai, jisse bade coherent structures bahut saare disconnected components mein fragment ho jaate hain ("archipelagos")

What is the typical computational complexity of UMAP?

O(n^1.14) approximate nearest neighbor search aur sparse graph optimization ki wajah se, t-SNE ke O(n²) ke comparison mein

How does the min_dist parameter affect UMAP embeddings?

min_dist low-D space mein minimum point separation control karta hai. Kam values (→0.0) local density preserve karte hue dense clusters banate hain; zyada values (→0.99) better visualization ke liye zyada spread-out layouts banate hain

What is the fuzy set union formula UMAP uses for symmetrization?

w_ij^sym = w_ij + w_ji - w_ij · w_ji (directed edges combine karne ke liye probabilistic OR operation)

Why does UMAP's low-D kernel use the form 1/(1 + a·d^(2b)) instead of exponential decay?

Heavy-tailed t-distribution jaisa kernel "crowding problem" rokta hai — tight local clusters aur well-separated global groups dono ko bina compression ke allow karta hai

What does it mean that UMAP has a "parametric" version?

Parametric UMAP ek neural network mapping seekhta hai high-D se low-D tak, jisse naye points ko retraining ke bina embed kiya ja sake (standard t-SNE ke unlike)

What is the target value for the sum of edge weights in UMAP and why?

log₂(k) jahan k hai n_neighbors. Yeh perplexity calibration se aata hai jo ensure karta hai ki effective number of neighbors k se match kare, t-SNE ki perplexity jaisa lekin UMAP ke framework ke liye adapted

What initialization does UMAP typically use for the low-D layout?

Spectral embedding (graph Laplacian ke eigenvectors) taaki ek achhe solution ke paas se shuru ho aur convergence fast ho

How does UMAP handle negative sampling in optimization?

SGD ke dauran, UMAP unconnected point pairs sample karta hai aur repulsive forces apply karta hai taaki sare points ek saath collapse na ho jaayein, connected edges ki attractive forces ko balance karte hue

What is a rule of thumb for choosing n_neighbors based on dataset size?

n points ke liye, global structure connectivity maintain karne ke liye minimum k ≥ 0.5√n use karo. 100k points ke liye, iska matlab hai k ≥ 150