Visual walkthrough — t-SNE for visualization

We will keep one running mental image: dots on a table (2D) that we are allowed to slide around, trying to copy the friendship pattern of dots living in a room we cannot see (high-D).

Step 1 — Turn "distance" into "how surprised am I to see you as a neighbor"

WHAT. We start with points ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n$ living in a high-dimensional space. A point ${\mathbf{x}}_i$ is just a list of numbers (a data sample); the bold letter means "a whole arrow of coordinates," not one number. The squared distance between two of them is

Read $\Vert \cdot \Vert$ as "the length of the arrow between them," and squaring it just avoids a square root — it grows fast when points are far. That is all the raw material we have.

WHY. Raw distance is not comparable across a dataset: near a dense clump, "5 units away" is far; in a sparse region it is close. So instead of distance we ask a softer question: "If point $i$ threw a dart, how likely is it to land on $j$?" Nearby points should be hit often, far ones rarely.

PICTURE. In figure s01 the bell curve is centered on point $i$; its height at $j$ is the similarity. Two things live here:

• $\exp (-{\text{distance}}^2/2{\sigma }_i^2)$ — the bell: tall for close $j$, tiny for far $j$. The minus sign flips "far" into "small."
• ${\sigma }_i$ — the width of the bell around point $i$ (why it uses the Gaussian shape: it is the smoothest, maximum-entropy bump that only cares about distance). Wide bell = many neighbors count; narrow = only the very closest.
• The bottom sum over all other $k$ — normalization: it forces $p_{j|i}$ to be a genuine probability that adds to $1$ across all $j$.
• The bar in $p_{j|i}$ reads "$j$ given $i$" — this bell belongs to $i$ alone.

Step 2 — Make the friendship two-way (symmetrize)

WHAT. Point $i$'s bell may be narrow while $j$'s is wide, so $p_{j|i}\ne p_{i|j}$. We blend them:

• $p_{j|i}+p_{i|j}$ — average the two one-sided views so friendship is mutual.
• $2n$ — divide so that all $p_{ij}$ together sum to $1$ ($n$ is the number of points). Now $P=\{p_{ij}\}$ is a single joint distribution over pairs.

WHY. Two reasons. (1) An outlier with a huge bell would otherwise get ignored — averaging guarantees every point has at least some voice in the joint table. (2) A symmetric $p_{ij}=p_{ji}$ makes the later gradient clean and force-like (Newton's third law: the pull of $i$ on $j$ equals the pull of $j$ on $i$).

PICTURE. In figure s02, two overlapping bells of different widths; the final $p_{ij}$ is the shared, symmetric bridge between the two peaks.

Step 3 — Choose the bell's width by perplexity, not by hand

WHAT. We never set ${\sigma }_i$ directly. Instead we pick one number, perplexity, and let each point find its own ${\sigma }_i$ to match it. Perplexity is

• $H(P_i)$ — the entropy (in bits) of point $i$'s neighbor distribution: how "spread out" its friendships are. All weight on one neighbor → $H=0$; weight spread evenly over $m$ neighbors → $H={\log }_{2}m$.
• $2^H$ — undoes the ${\log }_2$, so perplexity reads as "effective number of neighbors." Perplexity 30 ≈ "each point cares about roughly 30 friends."

WHY. Density varies across data. A fixed $\sigma$ would drown dense regions and starve sparse ones. Fixing the number of neighbors instead adapts the width automatically. A binary search shrinks or grows ${\sigma }_i$ until the entropy hits the target.

PICTURE. Figure s03: same point, three bell widths, three entropy readings — see how a wider bell raises entropy and thus perplexity.

Step 4 — Copy the pattern on the table with a heavier-tailed curve

WHAT. Now the low-D dots ${\mathbf{y}}_1,\dots ,{\mathbf{y}}_n$ on our 2D table. We need their pair-probability $q_{ij}$. Crucially, $q_{ij}$ is built to be a single symmetric joint distribution — one number per pair $(i,j)$ that, summed over all ordered pairs $k\ne l$, equals $1$ — so it can sit next to the joint $P$ from Step 2 inside the KL cost. We do not reuse the Gaussian; we use the Student t-distribution with 1 degree of freedom:

• $(1+{\text{distance}}^2{)}^{-1}$ — the t-kernel for the pair $(i,j)$: near distance $0$ it is $1$; as distance grows it fades, but far more slowly than the Gaussian's exponential drop.
• The bottom sum runs over every ordered pair $k\ne l$ (not just neighbors of one point). Call this single number the partition constant

Because the same $Z$ divides every $q_{ij}$, the whole table $Q=\{q_{ij}\}$ is one joint distribution with ${\sum }_{i\ne j}{q}_{ij}=1$ and $q_{ij}=q_{ji}$ — exactly the shape needed to compare against $P$. (Contrast Step 1's $p_{j|i}$, which was conditional: normalized per point $i$. Here there is only one global normalizer.)

WHY — the crowding problem. In high-D you can pack many points all equally near a center; in 2D there simply isn't room, so they get crushed together. Using a curve with a heavy tail means moderately-far points still register meaningful similarity, so the optimizer is content to leave them spread out instead of piling them on top of each other.

PICTURE. Figure s04 overlays the Gaussian $e^{-d^2}$ and the t-kernel $(1+d^2{)}^{-1}$. Watch the t-curve refuse to hit zero — that stubborn tail is what buys empty space between clusters.

Step 5 — Measure the mismatch with KL divergence

WHAT. We want $Q$ (table) to look like $P$ (room). Their disagreement is scored by the cost

• $\log \frac{p_{ij}}{q_{ij}}$ — per-pair surprise: $0$ when $q_{ij}=p_{ij}$, positive when the table under-represents a true friendship.
• $p_{ij}\times (\cdots )$ — each surprise is weighted by how important the true pair is. Weak true pairs ($p_{ij}\approx 0$) barely matter.

WHY this direction, not $\mathrm{KL}(Q\Vert P)$? Look at the two failure modes:

• A true-close pair placed far apart ($p_{ij}$ big, $q_{ij}$ tiny) → $\log (\text{big}/\text{tiny})$ is huge → heavily punished.
• A true-far pair placed close ($p_{ij}$ tiny, $q_{ij}$ big) → the leading $p_{ij}\approx 0$ mutes it → barely punished.

That asymmetry is exactly the priority we want: never tear neighbors apart; tolerate a little accidental crowding. This is why KL divergence — a directional comparison of distributions — is the right tool instead of a symmetric distance.

PICTURE. Figure s05 plots the per-pair penalty $p_{ij}\log (p_{ij}/q_{ij})$ against the ratio $q_{ij}/p_{ij}$: a steep cliff on the "torn apart" side ($q\ll p$), a gentle slope on the "too close" side ($q\gg p$).

Step 6 — Turn the cost into a force (the gradient)

WHAT. Differentiating $C$ with respect to each dot's position gives the direction to slide it:

WHY does this exact form appear — including the normalizer $Z$? Moving one dot ${\mathbf{y}}_i$ changes every low-D distance it takes part in, and — because $Z$ (Step 4) sums over all pairs — it also nudges the single global normalizer. Figure s06 traces this dependency chain. It is cleanest to write the un-normalized kernel $w_{ij}=(1+\Vert {\mathbf{y}}_i-{\mathbf{y}}_j{\Vert }^2{)}^{-1}$, so $q_{ij}=w_{ij}/Z$ with $Z={\sum }_{k\ne l}{w}_{kl}$. Then

• The first term $-p_{ij}/w_{ij}$ comes from the numerator $w_{ij}$ inside its own $\log q_{ij}$.
• The second term is the contribution of the shared $Z$: since $w_{ij}$ appears in every $q_{ab}$'s denominator, its derivative collects a piece from all pairs. But ${\sum }_{a\ne b}{p}_{ab}=1$ (both $P$ and $Q$ are joint distributions), so that whole sum collapses to the clean constant $1/Z$.

Feeding this back and using $\partial w_{ij}/\partial {\mathbf{y}}_i=-2w_{ij}^2({\mathbf{y}}_i-{\mathbf{y}}_j)$, the $1/Z$ pieces recombine into $q_{ij}=w_{ij}/Z$, and the algebra folds into the boxed result. So the normalizer does not vanish by magic — it is exactly what turns the raw numerator term into the difference $(p_{ij}-q_{ij})$. Read term by term the result is a spring:

• $(p_{ij}-q_{ij})$ — sign of the force. Positive ($p>q$: friends too far) → pull together. Negative ($p<q$: strangers too close) → push apart.
• $({\mathbf{y}}_i-{\mathbf{y}}_j)$ — direction along the joining line.
• $(1+\Vert \cdots {\Vert }^2{)}^{-1}$ — the t-weight, softening the force for distant pairs so nothing explodes.
• The $4$ — the two factors of $2$ (one from $\partial w/\partial \mathbf{y}$, one because each pair appears twice in the symmetric sum) combined; it only scales the step.

WHY. Gradient descent slides each ${\mathbf{y}}_i$ a little opposite to this force each iteration; repeat and the table settles into the shape whose $Q$ best matches $P$. Early exaggeration temporarily multiplies every $p_{ij}$ by ~4, over-inflating true friendships so clusters snap apart cleanly early on, then relaxes for fine tuning.

Step 7 — Degenerate & edge cases you must expect

WHAT / WHY / PICTURE, all gathered in figure s07, because these are the traps:

1. Identical points (${\mathbf{x}}_i={\mathbf{x}}_j$): distance $0$, bell height $1$, so $p_{j|i}$ is maximal — fine. In 2D the t-kernel is also $1$ (finite!), so no division by zero — a hidden gift of the $(1+d^2)$ form.
2. A lone outlier far from everyone: every bell height is tiny, but normalization renormalizes them, so its $p_{j|i}$ still sums to 1. Symmetrization (Step 2) then rescues it from being ignored.
3. Between-cluster gaps are meaningless. Because only $(p-q)$ near neighbors drives the layout, the width of empty space between two clusters is set by the t-tail and initialization, not by true distance. Never read global distances off a t-SNE plot (see parent [!mistake] notes).
4. Very low-D input (say 3–5 features): there is no crowding to fix, so t-SNE mostly adds noise — prefer scatter plots or clustering directly.

The one-picture summary

Figure s08 compresses the whole pipeline into one annotated diagram: distances → Gaussian $p_{ij}$ in high-D → random dots on table → t-kernel $q_{ij}$ (one global $Z$) → KL mismatch → spring forces → repeat, with the two data-worlds (unseen room vs. touchable table) drawn side by side and the feedback loop of forces shown as a curved arrow.

See also: 2.5.10 UMAP (faster, preserves more global structure), 3.2.1 Autoencoders and 2.5.9 Manifold Learning (parametric alternatives), Hinglish version.