# t-SNE

> Match neighbour probabilities in high and low dimensions by minimizing KL divergence; heavy-tailed t-distributions keep clusters apart.

Source: https://www.mlfoundry.in/learn/t-sne  
Section: ML Algorithms › Unsupervised · Dimensionality Reduction  
Level: core · 17 min read · updated 2026-10-07

**t-SNE (t-distributed Stochastic Neighbour Embedding):** turns the distances between $n$ high-dimensional points into **neighbour probabilities** $p_{ij}$ — "how likely is $j$ to be picked as $i$'s neighbour" — and then places $n$ points in 2-D (or 3-D) so that the same probabilities, measured with a heavy-tailed Student-t kernel, $q_{ij}$, match them as closely as possible in Kullback–Leibler divergence. The output is a map for *looking at* data, not a model.

- **Task:** Nonlinear dimensionality reduction for visualization
- **Input → output:** $n$ points $x_i\in\mathbb{R}^D$ → $n$ map points $y_i\in\mathbb{R}^2$ (one per training point — no function for new points)
- **Learns:** the coordinates $y_1,\dots,y_n$ directly, by gradient descent on $\mathrm{KL}(P\,\|\,Q)$
- **Training:** exact: $O(n^2)$ time and memory per iteration; Barnes–Hut: $O(n\log n)$; FFT-interpolated (FIt-SNE): $\approx O(n)$
- **Prediction:** none — a new point needs a new run (or an out-of-sample extension such as openTSNE's `transform`)
- **Hyperparameters:** perplexity (5–50), learning rate, iterations, early exaggeration, initialization (PCA vs random), metric
- **Assumes:** local Euclidean distances are meaningful (scale features, often PCA to ~50 dims first); only *neighbourhoods* are worth preserving

## The problem

You have 10,000 cells with 20,000 gene counts each, or 70,000 images of handwritten digits, and you want to *see* whether they form groups. **PCA** (see the PCA article) projects onto the directions of largest variance. It is linear, so two clusters that are separated along a curved surface, or along many small directions at once, are often drawn on top of each other. Classical MDS tries to preserve *all* pairwise distances, so it spends its effort on the large distances — which in high dimensions are the least informative — and squashes the local structure.

What a person reading a scatter plot actually wants is: **points that are neighbours in the original space should be neighbours on the screen**, and groups should look like groups. t-SNE optimizes exactly that, and gives up on everything else.

> **The crowding problem:** In 10 dimensions you can place 11 points that are all at the same distance from one another (a simplex); in 2-D at most 3. More generally, the volume at distance $r$ grows like $r^{D}$, so the many *moderately* distant points of a high-D neighbourhood have no room in the plane. If the map uses the same Gaussian kernel as the data (plain SNE), these points are pulled in and everything collapses into one crowded blob in the middle. t-SNE's heavy-tailed kernel is the fix.

## The idea

Put a Gaussian on each data point and ask: if $x_i$ picked a neighbour at random, in proportion to that Gaussian, how likely would it pick $x_j$? That gives a probability $p_{j|i}$ that is large for close points and practically zero for far ones. Do the same in the map, but with a Student-t (Cauchy) kernel. Then move the map points until the two sets of probabilities agree. Pairs that are neighbours in the data but far apart in the map attract; pairs that are close in the map but not neighbours in the data repel.

**Vocabulary**

- **Affinity p(j|i):** conditional probability that $x_i$ picks $x_j$ as its neighbour, from a Gaussian of width $\sigma_i$ centred on $x_i$
- **Joint affinity pᵢⱼ:** symmetrized version $\tfrac{p_{j|i}+p_{i|j}}{2n}$; all $p_{ij}$ sum to 1
- **Bandwidth σᵢ:** the width of point i's Gaussian; chosen separately for every point, small in dense regions, large in sparse ones
- **Perplexity:** $2^{H(P_i)}$ — the *effective number of neighbours* each point has; the user sets it and every $\sigma_i$ is solved to match it
- **Map / embedding:** the low-dimensional points $y_i$ that are optimized
- **Student-t kernel:** $(1+\lVert y_i-y_j\rVert^2)^{-1}$ — a Cauchy density; it decays like $1/d^2$ instead of $e^{-d^2}$
- **Early exaggeration:** multiplying all $p_{ij}$ by $\alpha\approx 4$–$12$ for the first iterations so clusters form tightly before they are positioned
- **Attractive / repulsive force:** the $p_{ij}$ and $q_{ij}$ halves of the gradient: data neighbours pull, every map point pushes

## The math

**Step 1 — affinities in the data.** For each point, a Gaussian turns squared distances into a probability distribution over the other points:

$$
p_{j|i}=\frac{\exp\!\big(-\lVert x_i-x_j\rVert^2/2\sigma_i^2\big)}{\sum_{k\neq i}\exp\!\big(-\lVert x_i-x_k\rVert^2/2\sigma_i^2\big)},\qquad p_{i|i}=0
$$

- $x_i\in\mathbb{R}^D$: the i-th data point
- $\sigma_i$: bandwidth of point i's Gaussian (one per point)
- $p_{j|i}$: probability that $i$ picks $j$ as a neighbour; $\sum_j p_{j|i}=1$

**Step 2 — choose each $\sigma_i$ from the perplexity.** A single global $\sigma$ would give points in dense regions hundreds of neighbours and isolated points none. Instead each $\sigma_i$ is found by **binary search** so that the distribution $P_i$ has a fixed entropy:

$$
\mathrm{Perp}(P_i)=2^{H(P_i)},\qquad H(P_i)=-\sum_{j}p_{j|i}\log_2 p_{j|i}
$$

- $H(P_i)$: Shannon entropy of point i's neighbour distribution, in bits
- $\mathrm{Perp}$: perplexity: a distribution spread evenly over $k$ neighbours has perplexity exactly $k$

$H(P_i)$ increases monotonically with $\sigma_i$ (a wider Gaussian spreads probability over more points), so bisection on $\beta_i=1/2\sigma_i^2$ converges in a few dozen steps. **Effect of perplexity:** it is a smooth version of "$k$" in a $k$-nearest-neighbour graph. Small perplexity (2–5) means each point only cares about its closest few neighbours, so the map shatters into many small clumps; large perplexity (50+) makes $p_{j|i}$ nearly uniform over a big neighbourhood and the map keeps more global layout but blurs small clusters. Perplexity must be smaller than $n-1$, and in practice smaller than the size of the clusters you hope to see.

**Step 3 — symmetrize.** $p_{j|i}\ne p_{i|j}$ in general (an outlier picks its neighbour, but nobody picks the outlier). t-SNE uses joint probabilities

$$
p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n},\qquad \sum_{i\neq j}p_{ij}=1
$$

- $n$: number of points; dividing by $2n$ makes the whole matrix a single distribution, and guarantees every point has $\sum_j p_{ij}\ge 1/2n$, so outliers still get attached to the map

**Step 4 — affinities in the map** use a Student-t distribution with one degree of freedom, normalized over **all** pairs:

$$
q_{ij}=\frac{w_{ij}}{Z},\qquad w_{ij}=\big(1+\lVert y_i-y_j\rVert^2\big)^{-1},\qquad Z=\sum_{k\neq l}w_{kl}
$$

- $y_i\in\mathbb{R}^2$: map position of point i — the only thing being learned
- $w_{ij}$: unnormalized similarity in the map (Cauchy kernel; no bandwidth to tune)
- $Z$: normalizer: sum over all ordered pairs

Why the heavy tail? At map distance 3 the t-kernel is $1/(1+9)=0.1$ while a Gaussian gives $e^{-9}=0.000123$ — about 810 times smaller. To reproduce a *moderate* affinity $p_{ij}$, the t-kernel lets the pair sit much farther apart in the map. That opens up room for the crowded neighbourhoods and pushes separate clusters away from each other.

**Step 5 — the objective** is the Kullback–Leibler divergence from $P$ to $Q$:

$$
C=\mathrm{KL}(P\,\|\,Q)=\sum_{i\neq j}p_{ij}\log\frac{p_{ij}}{q_{ij}}
$$

- $C$: cost to minimize; 0 iff Q = P

KL is **asymmetric**, and that asymmetry is the whole personality of t-SNE. A pair with $p=0.1$ that the map renders with $q=0.01$ costs $0.1\ln 10=0.230$; the reverse error ($p=0.01$, $q=0.1$) contributes only $-0.023$. Tearing neighbours apart is expensive; drawing non-neighbours close is cheap. So t-SNE preserves **local** structure faithfully and is nearly indifferent to large distances.

**Step 6 — derive the gradient.** Since $\sum p_{ij}=1$ and $\log q_{ij}=\log w_{ij}-\log Z$,

$$
C=\text{const}-\sum_{k\neq l}p_{kl}\log w_{kl}+\log Z
$$

Point $y_i$ appears in the pairs $(i,j)$ and $(j,i)$, and $\partial\log w_{ij}/\partial y_i=-2w_{ij}(y_i-y_j)$ because $\log w_{ij}=-\log(1+\lVert y_i-y_j\rVert^2)$. The first sum therefore contributes $+4\sum_j p_{ij}w_{ij}(y_i-y_j)$. For the normalizer, $\partial Z/\partial y_i=-4\sum_j w_{ij}^2(y_i-y_j)$, so $\partial\log Z/\partial y_i=-4\sum_j q_{ij}w_{ij}(y_i-y_j)$. Adding them:

$$
\frac{\partial C}{\partial y_i}=4\sum_{j\neq i}\big(p_{ij}-q_{ij}\big)\,w_{ij}\,\big(y_i-y_j\big)
$$

- $p_{ij}-q_{ij}>0$: pair is under-represented in the map → attraction (gradient descent moves y_i toward y_j)
- $p_{ij}-q_{ij}<0$: pair is too close in the map → repulsion
- $w_{ij}$: damps the force between pairs that are already far apart

It reads like a spring system: each pair is a spring whose stiffness is $(p_{ij}-q_{ij})\,w_{ij}$. With a Gaussian map kernel instead (symmetric SNE) the factor $w_{ij}$ is missing, $\partial C/\partial y_i=4\sum_j(p_{ij}-q_{ij})(y_i-y_j)$, and $q_{ij}\propto e^{-\lVert y_i-y_j\rVert^2}$ vanishes so quickly that clusters cannot repel each other from a distance.

**How each knob changes the math**

- **Perplexity:** sets every $\sigma_i$, hence how many entries of each row of $P$ are non-negligible (≈ perplexity of them)
- **Early exaggeration α:** replaces $p_{ij}$ by $\alpha p_{ij}$ in the gradient for the first ~250 iterations; attraction dominates, so natural clusters contract into tight groups that can then move through each other freely
- **Learning rate η:** step size of $y\leftarrow y-\eta\,\partial C/\partial y$. Too small: the map is still compressed when you stop. Too large: points fly out into a uniform "ball". scikit-learn's "auto" uses $\max(n/(4\alpha),\,50)$
- **Momentum & gains:** velocity accumulates past steps (0.5, then 0.8); per-coordinate gains grow by 0.2 while the gradient keeps its sign and shrink ×0.8 when it flips
- **Degrees of freedom:** generalized kernel $(1+d^2/\nu)^{-(\nu+1)/2}$; $\nu<1$ gives heavier tails and more separated, finer clusters; $\nu\to\infty$ recovers the Gaussian (SNE)

## Worked example: six points in 3-D

Two groups of three points, $\{1,2,3\}$ near the origin and $\{4,5,6\}$ around $(5,5,3)$. We use **perplexity 2** — each point should behave as if it had two neighbours — and start the map from a deliberately scrambled 2-D layout $Y^{(0)}$ in which the groups are interleaved.

The data (3 features) and the starting map. Group A highlighted.

| Point | x₁ | x₂ | x₃ | Group | Y⁽⁰⁾ |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 0 | 0 | A | (0, 0) |
| 2 | 1 | 0 | 0 | A | (2, 0) |
| 3 | 0 | 2 | 0 | A | (1, 1) |
| 4 | 5 | 4 | 2 | B | (1, 0) |
| 5 | 4 | 6 | 2 | B | (0, 1) |
| 6 | 6 | 6 | 4 | B | (2, 1) |

**One t-SNE iteration by hand**

1. **Squared distances from point 1:** to 2, 3, 4, 5, 6 they are $1, 4, 45, 56, 88$.
2. **Find $\sigma_1$.** Bisection on $\beta_1=1/2\sigma_1^2$ for perplexity 2 (entropy 1 bit) stops at $\beta_1=0.1279$, i.e. $\sigma_1=1.977$. (Check: $\beta=0.1$ gives perplexity 2.08, $\beta=0.2$ gives 1.92.)
3. **Row 1 of $P$.** $e^{-0.1279\cdot 1}=0.8800$, $e^{-0.1279\cdot 4}=0.5996$, $e^{-0.1279\cdot 45}=0.0032$, then 0.0008 and 0.00001; their sum is 1.4835. Dividing: $p_{2|1}=0.5932$, $p_{3|1}=0.4042$, $p_{4|1}=0.0021$, $p_{5|1}=0.0005$, $p_{6|1}\approx0$. Entropy $=1.000$ bit ✓.
4. **All six bandwidths:** $\sigma=(1.977,\ 1.912,\ 1.453,\ 1.708,\ 1.755,\ 1.933)$. Point 3 gets the narrowest Gaussian because its two neighbours (distances² 4 and 5) are nearly equidistant — a narrow kernel already splits them about evenly.
5. **Symmetrize:** $p_{12}=(p_{2|1}+p_{1|2})/12=(0.5932+0.6296)/12=0.1019$. The full matrix is below; 99.6% of the probability mass sits on within-group pairs.
6. **Map affinities at $Y^{(0)}$.** Squared map distances from point 1 to 2…6 are $4,2,1,1,5$, so $w_{1j}=0.2,\ 0.333,\ 0.5,\ 0.5,\ 0.167$. Summing $w$ over all 30 ordered pairs gives $Z=11.133$, hence $q_{12}=0.2/11.133=0.0180$, $q_{14}=q_{15}=0.0449$. The cost is $\mathrm{KL}(P\|Q)=1.1962$.
7. **Gradient on point 1** — one term per other point, $4(p_{1j}-q_{1j})\,w_{1j}\,(y_1-y_j)$, in the second table. Points 2 and 3 (its true neighbours, drawn too far away) pull; points 4, 5, 6 (strangers drawn too close) push. Sum: $\partial C/\partial y_1=(-0.0920,\ 0.0327)$.
8. **Step** with $\eta=2$: $y_1\leftarrow(0,0)-2\,(-0.0920,\ 0.0327)=(0.184,\ -0.065)$ — toward point 2 and away from points 4 and 5. Moving all six points at once lowers the cost from 1.1962 to 1.1240.
9. **Keep going.** 300 iterations (momentum, gains, and ×4 exaggeration for the first 50) reach $\mathrm{KL}=0.003$: group A ends near $(-2.6,-6.8)$, group B near $(5.4,7.7)$. Every point's nearest map neighbour equals its nearest data neighbour (1→2, 2→1, 3→1, 4→5, 5→4, 6→5).

Joint affinities $p_{ij}$ (perplexity 2). The two diagonal blocks — the groups — hold almost all the mass.

| pᵢⱼ | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | — | 0.1019 | 0.0802 | 0.0002 | 0.0001 | 0.0000 |
| 2 | 0.1019 | — | 0.0671 | 0.0007 | 0.0001 | 0.0000 |
| 3 | 0.0802 | 0.0671 | — | 0.0005 | 0.0004 | 0.0000 |
| 4 | 0.0002 | 0.0007 | 0.0005 | — | 0.1063 | 0.0665 |
| 5 | 0.0001 | 0.0001 | 0.0004 | 0.1063 | — | 0.0760 |
| 6 | 0.0000 | 0.0000 | 0.0000 | 0.0665 | 0.0760 | — |

Gradient on point 1 at $Y^{(0)}$, term by term. Gradient descent moves $y_1$ by $-\eta$ times the sum, so the negative x-component moves it right, toward point 2.

| j | p₁ⱼ | q₁ⱼ | w₁ⱼ | y₁ − yⱼ | 4(p−q)·w·(y₁−yⱼ) | force |
| --- | --- | --- | --- | --- | --- | --- |
| 2 | 0.1019 | 0.0180 | 0.200 | (−2, 0) | (−0.1343, 0) | attract |
| 3 | 0.0802 | 0.0299 | 0.333 | (−1, −1) | (−0.0670, −0.0670) | attract |
| 4 | 0.0002 | 0.0449 | 0.500 | (−1, 0) | (+0.0893, 0) | repel |
| 5 | 0.0001 | 0.0449 | 0.500 | (0, −1) | (0, +0.0897) | repel |
| 6 | 0.0000 | 0.0150 | 0.167 | (−2, −1) | (+0.0200, +0.0100) | repel |
| **sum** |  |  |  |  | **(−0.0920, +0.0327)** |  |

There is no "prediction" step: the result *is* the map. What we can check is whether it is faithful — here every neighbour relation survived, and scikit-learn's trustworthiness score (below) is 1.0.

## Watch it optimize

> Figure: Exact t-SNE running in your browser. Default: 60 points in 10-D (A wide, sd 1; B 3.3× tighter and 6.9 from A; C 20.9 from A), perplexity 10, ×4 exaggeration for 100 of 400 iterations. Press play to watch the clusters form during exaggeration and then spread; click a point to draw its high-D neighbour probabilities p(j|i). Final KL 0.190 and gap ratio 9.29 — and A, B, C come out the same size (mean within-cluster distances 3.33, 3.24, 3.25) although B is far tighter in 10-D. Switch to the Gaussian kernel (SNE): KL rises to 0.258 and the gap ratio falls to 4.24 — crowding. Perplexity 20 keeps more global layout (A–B 5.13 vs A–C 20.77 map units, like 6.89 vs 20.92 in 10-D). On the worked-example data with exaggeration off, step to iteration 1: point 1 sits at (0.184, −0.065), as computed by hand.

> **Cluster sizes and gaps in a t-SNE plot carry little information:** Because every $\sigma_i$ is tuned to the same perplexity, dense and sparse clusters both end up with about "perplexity" effective neighbours, and are drawn at about the same size — in the figure, B is 3.3× tighter than A in 10-D but identical on screen. Gaps between clusters are set by the balance of weak repulsions and change with perplexity, learning rate and run length; in the six-point example they keep growing for as long as you optimize. Read t-SNE maps for **which points are together**, never for how big a cluster is or how far apart two clusters are.

## The algorithm, step by step

**t-SNE(X, perplexity, η, T)**

1. **Preprocess.** Standardize features; for $D\gtrsim 50$ reduce to ~50 dimensions with PCA (denoises distances, speeds up neighbour search).
2. **Distances.** Compute $\lVert x_i-x_j\rVert^2$ — all pairs (exact), or only the $\lfloor 3\cdot\text{perplexity}\rfloor$ nearest neighbours (Barnes–Hut / FIt-SNE).
3. **Bandwidths.** For each $i$, bisect on $\beta_i$ until $2^{H(P_i)}$ equals the perplexity; store $p_{j|i}$.
4. **Symmetrize** $p_{ij}=(p_{j|i}+p_{i|j})/2n$.
5. **Initialize** $Y$: PCA of the data scaled to small standard deviation (modern default), or $\mathcal{N}(0,10^{-4})$.
6. **Loop $t=1\ldots T$:** compute $q_{ij}$ and the gradient $4\sum_j(\alpha_t p_{ij}-q_{ij})w_{ij}(y_i-y_j)$, with $\alpha_t$ = exaggeration during the early phase, 1 afterwards; update gains; $v\leftarrow m_t v-\eta\,g\odot\nabla$; $y\leftarrow y+v$.
7. **Stop** after $T$ iterations (typically 750–1000) or when the gradient norm is tiny; report $\mathrm{KL}(P\|Q)$.

**Complexity**

- **Exact:** $O(n^2 D)$ to build $P$, then $O(n^2)$ time and memory per iteration — fine up to a few thousand points
- **Barnes–Hut:** sparse $P$ via a vantage-point tree in $O(n\log n)$; repulsion approximated with a quadtree, $O(n\log n)$ per iteration, accuracy set by angle $\theta$ (0.5)
- **FIt-SNE / openTSNE:** repulsion by FFT-accelerated interpolation on a grid, $\approx O(n)$ per iteration — millions of points
- **Memory:** exact: $n^2$ floats (70,000 points ≈ 39 GB); approximate: $O(n\cdot\text{perplexity})$

## Variants and practical tuning

Hyperparameters that matter, and what to do with them.

| Setting | Typical value | Too small | Too large |
| --- | --- | --- | --- |
| perplexity | 30 (5–50); ≈ n/100 for huge n | fragmented map: many tiny clumps, spurious clusters | clusters smaller than the perplexity merge; slower |
| learning rate η | "auto" = max(n/(4α), 50) | map still compressed; clusters overlap | points scatter into a uniform ball |
| iterations | 1000 (≥ 250 after exaggeration) | clusters not separated yet | only time; KL plateaus |
| early exaggeration α | 12 for 250 iters | clusters split into pieces stuck on either side of others | very tight blobs early; rarely harmful |
| init | "pca" | — | random init loses global arrangement between runs |
| metric | Euclidean (cosine for text / embeddings) | — | — |

**Variants**

- **SNE (2002):** Gaussian kernel in the map and asymmetric conditional P: suffers from crowding, hard to optimize
- **Barnes–Hut t-SNE:** the standard implementation (`method="barnes_hut"` in scikit-learn) — 2-D or 3-D only
- **FIt-SNE, openTSNE:** FFT acceleration; openTSNE can also `transform` new points into an existing map
- **Parametric t-SNE:** trains a neural network $f_\theta(x)=y$ on the t-SNE loss, so new points are embedded by a forward pass
- **Multi-scale / heavy-tailed:** mix several perplexities, or use $\nu<1$ degrees of freedom to reveal finer sub-clusters
- **UMAP:** a fuzzy k-NN graph with a different loss (cross-entropy, with explicit negative sampling): faster and keeps more global layout — see the UMAP article

If you need components you can interpret — a direction per source, part or factor — t-SNE is the wrong tool: its axes mean nothing. Use PCA, or the latent-factor models in the ICA, NMF and Factor Analysis articles; t-SNE is for looking at neighbourhoods.

## In code

```python
import numpy as np

def cond_p(D, perplexity, tol=1e-5, steps=100):
    """Row-wise binary search for beta_i = 1/(2 sigma_i^2) so that 2**H(P_i) = perplexity."""
    n = len(D); P = np.zeros((n, n)); beta = np.ones(n); target = np.log(perplexity)
    for i in range(n):
        lo, hi, d = 0.0, np.inf, np.delete(D[i], i)
        for _ in range(steps):
            p = np.exp(-(d - d.min()) * beta[i]); p /= p.sum()
            H = -(p * np.log(np.maximum(p, 1e-300))).sum()   # entropy in nats
            if abs(H - target) < tol: break
            if H > target: lo = beta[i]; beta[i] = beta[i] * 2 if hi == np.inf else (lo + hi) / 2
            else:          hi = beta[i]; beta[i] = (lo + hi) / 2
        P[i, np.arange(n) != i] = p
    return P, beta

def joint_p(X, perplexity):
    D = ((X[:, None] - X[None]) ** 2).sum(-1)              # squared distances
    P, beta = cond_p(D, perplexity)
    return (P + P.T) / (2 * len(X)), beta                 # symmetric, sums to 1

def kl_grad(Y, P):
    d = ((Y[:, None] - Y[None]) ** 2).sum(-1)
    W = 1 / (1 + d); np.fill_diagonal(W, 0)               # Student-t kernel
    Q = W / W.sum()
    G = 4 * (((P - Q) * W)[:, :, None] * (Y[:, None] - Y[None])).sum(1)
    m = P > 0
    return G, (P[m] * np.log(P[m] / Q[m])).sum()

def tsne(X, perplexity=30, n_iter=300, eta=10.0, exag=4.0, exag_iters=50, Y0=None, seed=0):
    P, _ = joint_p(X, perplexity)
    Y = np.array(Y0, float) if Y0 is not None else 1e-2 * np.random.default_rng(seed).standard_normal((len(X), 2))
    V, gains = np.zeros_like(Y), np.ones_like(Y)
    for t in range(n_iter):
        early = t < exag_iters
        G, _ = kl_grad(Y, P * (exag if early else 1.0))
        if t > 0:                                           # delta-bar-delta gains
            gains = np.where(np.sign(G) != np.sign(V), gains + 0.2, gains * 0.8).clip(0.01)
        V = (0.5 if early else 0.8) * V - eta * gains * G
        Y = Y + V
    return Y, kl_grad(Y, P)[1]

X = np.array([[0,0,0],[1,0,0],[0,2,0],[5,4,2],[4,6,2],[6,6,4]], float)
Y0 = np.array([[0,0],[2,0],[1,1],[1,0],[0,1],[2,1]], float)

P, beta = joint_p(X, perplexity=2)
print("sigma:", np.round(np.sqrt(1 / (2 * beta)), 3))
G, kl0 = kl_grad(Y0, P)
print("KL at Y0:", round(kl0, 4), " gradient on point 1:", G[0].round(4))
print("point 1 after one plain step (eta=2):", (Y0[0] - 2 * G[0]).round(4))
Y, kl = tsne(X, perplexity=2, n_iter=300, eta=2.0, Y0=Y0)
print("final KL:", round(kl, 4))
print(np.round(Y, 2))
# sigma: [1.977 1.912 1.453 1.708 1.755 1.933]
# KL at Y0: 1.1962  gradient on point 1: [-0.092   0.0327]
# point 1 after one plain step (eta=2): [ 0.184  -0.0653]
# final KL: 0.003
```

From scratch: perplexity search, joint P, Student-t Q, gradient with momentum, gains and early exaggeration — on the worked example.

```python
import numpy as np
from sklearn.manifold import TSNE, trustworthiness
from sklearn.manifold._t_sne import _joint_probabilities   # private helper, used only to inspect P
from scipy.spatial.distance import squareform

X = np.array([[0,0,0],[1,0,0],[0,2,0],[5,4,2],[4,6,2],[6,6,4]], float)
Y0 = np.array([[0,0],[2,0],[1,1],[1,0],[0,1],[2,1]], float)

D = ((X[:, None] - X[None]) ** 2).sum(-1)
P = squareform(_joint_probabilities(D, 2, 0))
print("p12, p13, p14:", P[0, 1].round(4), P[0, 2].round(4), P[0, 3].round(4))

ts = TSNE(n_components=2, perplexity=2, init=Y0, learning_rate=2.0,
          method="exact", max_iter=500, random_state=0)
Y = ts.fit_transform(X)
print("KL:", round(ts.kl_divergence_, 4))
print(np.round(Y, 2))
d = np.sqrt(((Y[:, None] - Y[None]) ** 2).sum(-1))
print("nearest neighbour in the map:", d.argsort(1)[:, 1] + 1)
print("trustworthiness (k=2):", round(trustworthiness(X, Y, n_neighbors=2), 3))
# p12, p13, p14: 0.1019 0.0802 0.0002
# KL: 0.0027
# nearest neighbour in the map: [2 1 1 5 4 5]
# trustworthiness (k=2): 1.0

# Real data: TSNE(perplexity=30, init="pca", learning_rate="auto").fit_transform(PCA(50).fit_transform(X))
```

scikit-learn on the same six points (exact method, same start). Its P matrix matches the table; it uses its own schedule (exaggeration 12 for 250 iterations), so the final coordinates differ but the neighbour structure is identical.

**Strengths**

- You want to see whether high-dimensional data has cluster structure (cells, images, word or model embeddings).
- Local neighbourhoods matter more than global geometry, and the structure is nonlinear.
- n is up to a few hundred thousand (with Barnes–Hut / FIt-SNE) and you will look at the result, not feed it to a model.

**Limitations**

- You need distances between clusters, cluster sizes or densities to mean something.
- You need to embed new points later, or a deterministic, reproducible projection — use PCA, parametric methods or UMAP.
- You want features for a downstream model: t-SNE coordinates are unstable and have no out-of-sample mapping.
- You need more than 3 output dimensions (Barnes–Hut supports at most 3), or interpretable axes.

- **Single-cell genomics:** t-SNE plots of cells (after PCA to ~50 components) are the standard way to show cell types and states in scRNA-seq studies.
- **Inspecting neural-network embeddings:** Projecting the penultimate-layer activations of a classifier shows which classes it confuses and which it separates.
- **Exploring image and text collections:** Maps of MNIST, CIFAR or document embeddings reveal near-duplicates, sub-styles and mislabelled examples.
- **Cytometry and fraud review:** viSNE-style maps of flow-cytometry data and maps of transaction embeddings let analysts spot rare sub-populations by eye.

> **Do not cluster on (or read distances from) the t-SNE map:** Running k-means on t-SNE coordinates, or claiming two groups are "closer" because their blobs are nearer, mistakes an artefact of perplexity and optimization for structure. Cluster in the original (or PCA) space, then use t-SNE only to display the labels.

> **One run, one perplexity, is not evidence:** Low perplexity can make pure noise look like clusters, and a stopped-too-early run can show clusters that are still overlapping. Try several perplexities (e.g. 5, 30, 100), use PCA initialization, run long enough, and only trust structure that persists.

> **Scale and reduce first:** t-SNE uses raw Euclidean distances, so a feature measured in thousands dominates one measured in units. Standardize, and for $D$ in the hundreds or thousands project to ~50 PCA components first — this removes noise that would otherwise make all distances look alike.

**Question:** Point i's neighbour distribution is spread evenly over 8 points (p = 1/8 each, 0 elsewhere). Its perplexity is…

- A. 3
- B. 8
- C. 1/8
- D. 64

**Answer:** B. 8 — $H=-8\cdot\tfrac18\log_2\tfrac18=3$ bits, and $2^3=8$: perplexity is the effective number of neighbours.

**Question:** At map distance 3, how many times larger is the Student-t similarity (1+d²)⁻¹ than the Gaussian exp(−d²)?

- A. About 3
- B. About 9
- C. About 810
- D. They are equal

**Answer:** C. About 810 — $1/(1+9)=0.1$ versus $e^{-9}=0.000123$: a ratio of about 810. The heavy tail lets moderately similar pairs sit far apart, which relieves crowding and separates clusters.

**Question:** Which mistake does KL(P‖Q) punish most?

- A. Drawing two non-neighbours close together in the map
- B. Drawing two true neighbours far apart in the map
- C. Making all clusters the same size
- D. Rotating the map

**Answer:** B. Drawing two true neighbours far apart in the map — A pair with $p=0.1$ shown with $q=0.01$ costs $0.1\ln10=0.230$; the reverse error ($p=0.01$, $q=0.1$) contributes only $-0.023$. That asymmetry is why t-SNE preserves local structure and not global distances. Rotation does not change any distance, so it costs nothing.

**Question:** You fitted scikit-learn's TSNE on 10,000 images. A new batch of 500 arrives. What can you do?

- A. Call tsne.transform(new_images)
- B. Re-run t-SNE on all 10,500 points (or use an out-of-sample method such as openTSNE or parametric t-SNE)
- C. Multiply the new images by the learned projection matrix
- D. Use the KL divergence to place them

**Answer:** B. Re-run t-SNE on all 10,500 points (or use an out-of-sample method such as openTSNE or parametric t-SNE) — t-SNE optimizes the coordinates of the training points directly; there is no learned mapping or projection matrix, and scikit-learn's TSNE has no transform method.

**Key points**

- t-SNE turns distances into neighbour probabilities $p_{ij}$ (Gaussian, per-point $\sigma_i$) and $q_{ij}$ (Student-t in the map) and minimizes $\mathrm{KL}(P\|Q)$.
- Perplexity $=2^{H(P_i)}$ is the effective number of neighbours; each $\sigma_i$ is found by binary search to match it.
- Gradient: $4\sum_j(p_{ij}-q_{ij})\,w_{ij}(y_i-y_j)$ — data neighbours attract, everything else repels.
- The heavy-tailed kernel solves the crowding problem; KL's asymmetry makes the map faithful locally and unreliable globally.
- Cluster sizes and gaps are not meaningful; there is no transform for new points; use several perplexities and PCA initialization.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
