Exercises — UMAP for dimensionality reduction

What we compute: plug $d_{ij}={\rho }_i$ into the formula. $w=\exp \left(-\frac{\max (0,4.0-4.0)}{{\sigma }_i}\right)=\exp \left(-\frac{\max (0,0)}{{\sigma }_i}\right)=\exp (0)=1.$ Why it matters: subtracting ${\rho }_i$ guarantees the closest neighbour always gets weight exactly $1$ — no point is ever left isolated. The answer is $\boxed{1}$ for any ${\sigma }_i$.

• (a) ==n_neighbors== ($k$), typical value in $[5,50]$. Larger $k$ → more global structure.
• (b) ==min_dist==, typical value in $[0.0,0.99]$. Larger min_dist → points forced apart.

The fuzzy weights $w_{ij}$ and $v_{ij}$ live in $[0,1]$ and behave like membership probabilities; cross-entropy is the natural "distance between probability distributions," and — crucially — it punishes both a missing connection (attraction term) and a false connection (repulsion term), which squared error blends together.

Step — shift: $\max (0,8.0-3.0)=5.0$. Step — scale: divide by ${\sigma }_i$: $5.0/5.0=1.0$. Step — decay: $w_{ij}=\exp (-1.0)=0.367879\dots \approx \boxed{0.3679}$. What it looks like: on figure s01 this is the height of the curve exactly one $\sigma$ past the foot ${\rho }_i$ — the classic "$1/e$" drop.

Step: $0.8+0.5-(0.8)(0.5)=1.3-0.4=0.9$. Why this formula: it is the fuzzy set union (probabilistic OR): "$i$ connects to $j$" OR "$j$ connects to $i$." The subtracted product stops double-counting. Answer $=\boxed{0.9}$, and it can never exceed $1$.

Step: at distance $1$, $\Vert y_i-y_j{\Vert }^{2b}=1^{2b}=1$. $v_{ij}=\frac{1}{1+1.929\cdot 1}=\frac{1}{2.929}=0.341415\dots \approx \boxed{0.3414}.$ What it looks like: see figure s02 — this heavy-tailed curve stays high near $0$ and fades slowly, which is exactly what lets clusters separate without every point crushing to the origin.

Target: ${\log }_{2}3=1.58496\dots$ Weights at ${\sigma }_i=2.0$:

• $j=1$: $d-\rho =0$ → $w=\exp (0)=1$.
• $j=2$: $d-\rho =1.0$ → $w=\exp (-1.0/2.0)=\exp (-0.5)=0.60653$.
• $j=3$: $d-\rho =3.0$ → $w=\exp (-3.0/2.0)=\exp (-1.5)=0.22313$. Sum: $1+0.60653+0.22313=1.82966$. Compare: $1.82966>1.58496$, so the sum is too big. Direction: the weights decay too slowly ⇒ ==decrease ${\sigma }_i$== to sharpen the decay and shrink the sum. So ${\sigma }_i=2.0$ is not the answer; binary search steps the bandwidth down.

Weights at ${\sigma }_i=1.42$:

• $j=1$: $\exp (0)=1$.
• $j=2$: $\exp (-1.0/1.42)=\exp (-0.70423)=0.49444$.
• $j=3$: $\exp (-3.0/1.42)=\exp (-2.11268)=0.12093$. Sum: $1+0.49444+0.12093=1.61537$, versus target $1.58496$. Comment: the sum $1.6154$ is within $0.03$ of target — binary search would nudge ${\sigma }_i$ down a hair more, but this is already a good approximation. This shows how each point gets its own ${\sigma }_i$ tuned to its local density: dense regions get small $\sigma$, sparse regions get large $\sigma$. That per-point calibration is UMAP's answer to varying data density, and is what distinguishes it from a fixed-radius method like plain Isomap.

The condition at $k=2$: target $={\log }_{2}2=1$. But the nearest neighbour alone already contributes $w=1$. So the sum must equal $1$ with the first term already $=1$ — forcing the second neighbour's weight toward $0$ and ${\sigma }_i\to 0$. Consequence: each point effectively connects to only its single nearest neighbour. The graph becomes a loose collection of near-isolated edges, easily fragmenting one true manifold into many disconnected shards. Visual artefact: the embedding shatters a smooth structure into scattered small clumps that carry no global relationship — you lose exactly the global structure UMAP was chosen to keep.

Method: UMAP.

• PCA is linear — it projects, so a curved manifold (cell-state trajectory) gets flattened and clusters overlap. Rejected for (i).
• t-SNE cannot embed new points without a full re-run — it fails requirement (ii) outright.
• UMAP builds a reusable model, so a new cell can be pushed through — satisfies (ii). n_neighbors: small–moderate, e.g. $k=15$. From Problem 3.2's logic, small $k$ tightens ${\sigma }_i$ and emphasises local structure → sharp, separated clusters as (i) demands. min_dist: small, e.g. $0.1$. In the kernel $v_{ij}=1/(1+a{d}^{2b})$, a small min_dist lets $v_{ij}\to 1$ as $d\to 0$, so points are allowed to pack tightly — preserving within-cluster density. Cross-check: if instead we wanted an airy visualization for a slide, we'd raise min_dist to $\sim 0.5$–$0.8$ to inflate the layout, trading density detail for readability.

The two forces in the loss:

• First term $w_{ij}^{\text{sym}}\log (w/v)$ = attraction between genuinely-connected pairs.
• Second term $(1-w_{ij}^{\text{sym}})\log \frac{1-w}{1-v}$ = repulsion that pushes apart pairs the high-D graph says are not connected. The problem: there are $O(n^2)$ non-edges — computing every repulsion is infeasible. Negative sampling: at each gradient step, sample a handful of random "non-neighbour" pairs and apply only their repulsion. This is an unbiased cheap estimate of the full second term. Why collapse otherwise: with only attraction and no repulsion, every point is pulled toward every neighbour with nothing pushing back — the whole embedding contracts to a single point. Negative sampling supplies the outward pressure that gives clusters room. (Same spirit as the repulsive term you meet in Spectral Clustering eigen-embeddings that spread points across an eigen-axis.)

Stage 1 — Random Projection or PCA (dimension pre-reduction). Cut the ambient dimension $d$ (e.g. $2000\to 50$). By the Johnson–Lindenstrauss idea, random projection approximately preserves pairwise distances, so the neighbour graph UMAP builds next is nearly unchanged — but each distance now costs far less to compute. Stage 2 — approximate Nearest Neighbors Algorithms (e.g. NN-Descent / ANN). UMAP already uses approximate NN internally; ensure the index is the sub-quadratic kind. This produces the $k$-NN graph that feeds ${\rho }_i,{\sigma }_i$. Stage 3 — UMAP with spectral initialization + negative sampling. The spectral init (a Spectral Clustering-style eigen-layout) gives a good starting embedding, cutting the epochs SGD needs. Negative sampling keeps each epoch linear in edges. Stage 4 — reuse the fitted model to transform future streaming points without refitting. Justification thread: every stage attacks one cost — ambient dimension (S1), neighbour search (S2), optimization iterations + repulsion cost (S3) — while each preserves the quantity the next stage relies on (distances, then graph, then layout).

The steel-man: through the ${\sigma }_i$ calibration ($\sum w={\log }_{2}k$) plus a spectral (global) initialization plus negative-sampling repulsion, UMAP retains more large-scale geometry than t-SNE, which explicitly discards it. Empirically, UMAP often lays out related clusters near each other. The bound / failure case: the low-D kernel $v_{ij}=1/(1+a{d}^{2b})$ is heavy-tailed and saturating: once two clusters are "far," pushing them from distance $5$ to $50$ barely changes $v_{ij}$ (both $\approx 0$), so the loss gradient there is nearly flat. Therefore the magnitude of a large inter-cluster gap in the plot is essentially unconstrained — two clusters shown "very far" apart may be only slightly less related than two shown "moderately far." Rule: trust ordering and neighbourhood of clusters, distrust exact distances between distant clusters. (For faithful global distances you'd instead reach for Isomap or Topological Data Analysis summaries.)

Can you, without notes: (1) plug numbers into $w_{ij}$ including the $\max (0,\cdot )$ clamp? (2) symmetrize two weights? (3) say which way ${\sigma }_i$ moves when the sum overshoots? (4) name why UMAP (not t-SNE/PCA) supports inverse transform? (5) state exactly which distances in a UMAP plot are not trustworthy and why? If yes to all five — L5 reached. Which term supplies the outward push that stops collapse? ::: The repulsion (second) cross-entropy term, estimated by negative sampling. If ${\sum }_j{w}_{ij}$ is above ${\log }_{2}k$, does ${\sigma }_i$ go up or down? ::: Down.