Foundations — t-SNE for visualization

Everything else on the parent note is machinery serving that one sentence. Below we unpack every symbol it uses, from absolute zero, in an order where each idea is built only from ones already explained.

1. A "point" and its dimensions — $\mathbf{x}$, $d$, $n$

A point is just a list of numbers. If you measure a flower's petal length, petal width, and stem length, that flower becomes the list $(2.1,0.7,5.4)$. Each number is one feature.

• $d$ = the number of features = how many numbers are in each list. Petal example: $d=3$.
• ${\mathbf{x}}_i$ = the $i$-th point (the bold letter means "this is a whole list, not one number"). The little $i$ is just a name tag: ${\mathbf{x}}_1$ is the first flower, ${\mathbf{x}}_2$ the second.
• $n$ = how many points you have in total. 300 flowers means $n=300$.
• ${\mathbb{R}}^d$ = "the space of all lists of $d$ real numbers." ${\mathbb{R}}^2$ is the flat page (2 numbers = left/right, up/down). ${\mathbb{R}}^{100}$ is a space you cannot picture — but the maths treats it exactly the same.

2. Distance between two points — $\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2$

To say "these two flowers are similar," we need to measure how far apart their lists are.

• ${\mathbf{x}}_i-{\mathbf{x}}_j$ means subtract the lists slot by slot. $(2,7)-(5,3)=(-3,4)$.
• $\Vert \cdots \Vert$ (double bars) = the length of that difference arrow — the straight-line distance. From $(-3,4)$: length $=\sqrt{(-3{)}^2+4^2}=5$.
• $\Vert \cdots {\Vert }^2$ = that length squared ($=25$). We keep it squared because it avoids the square root (faster, and the maths later stays smooth).

3. The Gaussian bump — $\exp (-{\text{distance}}^2/2{\sigma }^2)$

We now turn "distance" into "similarity." We want: distance $0\Rightarrow$ similarity high; big distance $\Rightarrow$ similarity near $0$; and a smooth fall-off in between.

The function that does exactly this is the Gaussian bell curve:

Reading it piece by piece:

• $\exp (\text{something})$ means $e$ raised to that power, where $e\approx 2.718$. When the something is $0$, $\exp (0)=1$ (max similarity). When it is very negative, $\exp$ crashes toward $0$.
• The minus sign flips it: more distance $\to$ more negative exponent $\to$ smaller similarity. Exactly what we wanted.
• ${\sigma }_i$ (sigma) = the width of the bell for point $i$. A wide bell means "I still count faraway points as neighbours"; a narrow bell means "only my closest friends count." The little $i$ says each point gets its own width.

See 1.3.5 KL Divergence later for how these similarities become the thing we minimise.

4. Turning similarities into a probability — $p_{j\mid i}$, $\Sigma$, and normalisation

A single similarity number is not yet a probability. A probability must be between $0$ and $1$, and all of a point's options must add up to $1$. We achieve that by dividing each similarity by the total of all similarities.

• $\sum _{k\ne i}$ (capital sigma) = "add up over every point $k$, except $i$ itself." It is a loop: try $k=1$, then $k=2$, …, skip $k=i$, sum the results.
• $p_{j\mid i}$ = "the probability point $i$ picks $j$ as its neighbour." Read the bar $\mid$ as "given": given that we are standing at $i$, how likely is $j$?

Note $p_{j\mid i}$ is not symmetric: because $i$ and $j$ can have different bell widths ${\sigma }_i\ne {\sigma }_j$, the attention $i$ gives $j$ need not equal the attention $j$ gives $i$.

5. Making it fair both ways — $p_{ij}$

t-SNE prefers a joint probability $p_{ij}$ that treats the pair $(i,j)$ as one thing, with no direction:

• Adding the two directions and averaging removes the bias, so $p_{ij}=p_{ji}$.
• Dividing by $2n$ makes all the $p_{ij}$ across every pair add up to $1$ — now $P$ (the whole collection of $p_{ij}$) is one honest probability distribution over pairs.

6. Perplexity and entropy — the knob for ${\sigma }_i$

How do we choose each ${\sigma }_i$? We don't set it directly; we set a target perplexity — roughly "how many neighbours should each point pay attention to."

• Entropy $H(P_i)=-{\sum }_j{p}_{j\mid i}{\log }_2{p}_{j\mid i}$ measures how spread out point $i$'s attention is. All attention on one neighbour $\Rightarrow H=0$. Attention split evenly over many $\Rightarrow$ large $H$.
• Perplexity $=2^{H(P_i)}$ converts that entropy into an intuitive count: "effective number of neighbours." Perplexity $30$ ≈ each point behaves as if it has about $30$ meaningful neighbours.
• A binary search then tunes ${\sigma }_i$ up or down until the point's perplexity hits your chosen target.

7. The low-D twins — ${\mathbf{y}}_i$ and the t-distribution $q_{ij}$

Now the destination room, ${\mathbb{R}}^2$. Each high-D point ${\mathbf{x}}_i$ gets a partner dot ${\mathbf{y}}_i$ on the page. We define a matching similarity there, but with a different curve:

• $(\cdots {)}^{-1}$ means "one over ..." — a reciprocal.
• This is the Student t-distribution (with 1 degree of freedom). Compared to the Gaussian it has a heavy tail: it falls off gently, so even moderately far dots keep a non-tiny $q_{ij}$.

8. KL divergence — the scorecard $C$

We have two probability collections: $P$ (upstairs, fixed) and $Q$ (downstairs, movable). We need one number saying "how badly does $Q$ disagree with $P$?" That number is the Kullback–Leibler divergence:

• $\log (p_{ij}/q_{ij})$ is $0$ when the two agree, positive when $q$ is too small, and each term is weighted by $p_{ij}$ — so mismatches on true neighbours (large $p_{ij}$) hurt the most.
• $C\ge 0$ always, and $C=0$ only when $Q$ exactly matches $P$. So "minimise $C$" literally means "make the picture faithful."

Full treatment lives in 1.3.5 KL Divergence.

9. Derivative / gradient — $\frac{\partial C}{\partial {\mathbf{y}}_i}$

To reduce $C$ we need to know: if I nudge dot ${\mathbf{y}}_i$ a little, does $C$ go up or down? That question is exactly what a derivative answers — it is the slope of $C$ as a function of ${\mathbf{y}}_i$.

• $\partial$ (curly d) means "rate of change with respect to just this one thing, holding others fixed."
• $\frac{\partial C}{\partial {\mathbf{y}}_i}$ is a 2D arrow (one slope per coordinate) pointing in the direction that increases $C$ fastest. So we step the opposite way — this is gradient descent.

Read it as springs: $(p_{ij}-q_{ij})$ is the spring's sign/strength (want them closer or further), $({\mathbf{y}}_i-{\mathbf{y}}_j)$ is the direction, and the last factor is the t-weight. See 2.4.3 K-Means Clustering for a gentler first taste of iterative point-moving, and 3.2.1 Autoencoders / 2.5.10 UMAP for alternative ways to reach low-D. The manifold idea underneath it all is in 2.5.9 Manifold Learning.

Prerequisite map

Equipment checklist