Exercises — t-SNE for visualization

Answer: (b). t-SNE minimizes the cost $C=\text{KL}(P\Vert Q)={\sum }_{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$. Making this number small forces the 2D neighbor-probabilities $q_{ij}$ to imitate the high-D neighbor-probabilities $p_{ij}$, so points that were neighbors in high-D stay neighbors in the picture. (a) is what PCA maximizes; (c) is what an autoencoder minimizes; (d) is a K-Means idea, see 2.4.3 K-Means Clustering.

False. t-SNE only preserves local structure. The KL objective barely penalizes far-apart points being placed at any particular far distance, so the size of the gap between clusters is essentially arbitrary. Read gaps as "these are separate groups", never as "twice as far = twice as different".

• t-distribution: $(1+3{)}^{-1}=\frac{1}{4}=0.25$.
• Gaussian: $e^{-3}\approx 0.0498$.

The t-value (0.25) is about 5× larger. This is the whole point of the heavy tail: moderately distant points still get a non-tiny affinity, so they are allowed to sit further apart in 2D without their similarity "vanishing". This directly fights the crowding problem described in the parent note. See the tail comparison in the figure below.

$H(P_i)=-\left(\frac{1}{2}{\log }_2\frac{1}{2}+\frac{1}{2}{\log }_2\frac{1}{2}\right)=-\left(\frac{1}{2}(-1)+\frac{1}{2}(-1)\right)=1\text{ bit}.$ Perplexity $=2^{H(P_i)}=2^1=2$. Interpretation: perplexity is the effective number of neighbors. Here two equally-weighted neighbors give perplexity exactly 2 — the formula returns the honest count. This is why perplexity is set as a target and ${\sigma }_i$ is binary-searched to hit it.

$H=-4\cdot \frac{1}{4}{\log }_2\frac{1}{4}=-{\log }_2\frac{1}{4}=2\text{ bits},\text{Perplexity}=2^2=4.$ A uniform distribution over $k$ neighbors always has perplexity exactly $k$. Perplexity is literally "how many neighbors am I effectively looking at".

$p_{ij}-q_{ij}=0.02-0.005=+0.015>0$. Gradient descent moves against the gradient: ${\mathbf{y}}_i\leftarrow {\mathbf{y}}_i-\eta \partial C/\partial {\mathbf{y}}_i$. The term $({\mathbf{y}}_i-{\mathbf{y}}_j)$ points away from $j$; a positive coefficient means the gradient points away from $j$, so stepping against it moves ${\mathbf{y}}_i$ toward $j$. → Attractive. Meaning: $p>q$ says "these two are more similar in high-D than the map currently shows", so the map is too spread out here → pull them together. The figure shows both force directions.

Write $\text{KL}(P\Vert Q)=\sum p_{ij}\log \frac{p_{ij}}{q_{ij}}$. Each term is weighted by $p_{ij}$ (the true similarity).

• When $p_{ij}$ is large (true neighbors) but $q_{ij}$ is small (map put them far), $\log \frac{p_{ij}}{q_{ij}}$ blows up and the large weight $p_{ij}$ amplifies it → huge penalty. So true neighbors are strongly protected.
• When $p_{ij}$ is near 0 (unrelated points) but $q_{ij}$ is large (map put them close), the weight $p_{ij}\approx 0$ makes the penalty tiny → cheap mistake.

This asymmetry says: "never tear apart real neighbors; occasionally letting strangers sit close is fine." That is exactly the local-structure priority we want. $\text{KL}(Q\Vert P)$ would flip these priorities (weight by $q$), protecting empty space instead of neighborhoods. See 1.3.5 KL Divergence for the general asymmetry.

With every ${\mathbf{y}}_i$ crammed near the origin, all pairwise distances $\Vert {\mathbf{y}}_i-{\mathbf{y}}_j{\Vert }^2\approx 0$, so every unnormalized affinity $(1+0{)}^{-1}=1$. After normalizing over $N(N-1)$ pairs, every $q_{ij}$ is nearly identical and tiny, $q_{ij}\approx \frac{1}{N(N-1)}$. Therefore $p_{ij}-q_{ij}\approx p_{ij}-\text{const}$. Pairs with large $p_{ij}$ (true neighbors) get a strong positive coefficient → strong attraction; unrelated pairs get $\approx 0$. So the early motion is driven almost entirely by the high-D structure $P$, which is precisely why the layout organizes into meaningful clumps first. Early exaggeration (multiply all $p_{ij}$ by 4) supercharges exactly this phase.

• Perplexity 2: each point effectively looks at ~2 neighbors. The Gaussian ${\sigma }_i$ shrinks so only the 1–2 nearest points matter. Result: many tiny fragmented sub-clusters, broken threads, lots of noise-driven micro-structure. Global digit clusters may shatter.
• Perplexity 500: each point averages over ~500 neighbors, ${\sigma }_i$ grows large, so $p_{j|i}$ becomes smooth and broad. Local detail is washed out; you get a few big diffuse blobs with digits smeared together, closer to a PCA-like global view.
• Sweet spot (~30): enough neighbors to define genuine local manifolds without drowning them — this is why 5–50 is the standard range. Perplexity is a smoothness / scale knob, tied directly to $H(P_i)$ and thus ${\sigma }_i$.

t-SNE is overkill / risky here.

• The crowding problem (heavy-tail t-distribution) is a cure for high-D geometry, where huge numbers of points can be near-equidistant. In 5D there is no severe crowding, so the heavy tail can invent separation that isn't real, distorting simple structure.
• t-SNE is stochastic and slow ($O(n^2)$ ish); for 5D you can just plot pairs of features, run PCA, or use 2.5.10 UMAP if a smoother/faster embedding is desired.
• t-SNE's strength (rescuing local structure from 50+ dimensions) has nothing to buy you at 5D. Match the tool to the dimensionality.

$p_{12}=\frac{p_{2|1}+p_{1|2}}{2n}=\frac{0.6+0.2}{2\cdot 3}=\frac{0.8}{6}\approx \mathrm{0.1333.}$ Guaranteed properties:

1. Symmetry: $p_{12}=p_{21}$ (no arbitrary direction of "who chose whom").
2. Valid joint distribution: ${\sum }_{i\ne j}{p}_{ij}=1$, and crucially every point contributes at least $\frac{1}{2n}$ of total mass, so no outlier gets ignored (a raw conditional could leave a lonely point invisible).

Why it breaks:

1. Non-parametric: t-SNE learns positions for these specific points, not a function $f(\mathbf{x})$. There is no way to map a new $\mathbf{x}$ into the existing map without re-running everything.
2. Stochastic: random init + gradient descent means two runs give different (rotated, reshaped) layouts, so "feature 1" and "feature 2" have no stable meaning.
3. Distorted global geometry: distances are unreliable, so a linear classifier on them learns artifacts.
4. Cost: $O(n^2)$ per fit; you cannot cheaply embed streaming data.

Correct replacements: use a parametric embedder — PCA (deterministic, projects new data instantly), an autoencoder (learns a reusable encoder $f$), or 2.5.10 UMAP (has a transform for new points and is faster). Reserve t-SNE for one-off visualization only.

Data: Generate three Gaussian blobs in high-D with equal spread, but place them at very different mutual distances — e.g. A–B far apart, A–C and B–C moderate. Also make one blob denser (smaller $\sigma$) than the others. Run: t-SNE at a fixed perplexity. Expected plot: Three well-separated clusters, but the gaps between them will NOT reflect the true ratio of high-D distances, and the on-screen cluster sizes will look roughly comparable regardless of the true density differences — because the t-distribution normalizes each region's spread locally. Takeaway: Re-running with a different seed or perplexity shuffles gaps and sizes while keeping membership stable. This visually proves: trust which points group together; distrust how big or how far apart the groups appear. Ties directly to 2.5.9 Manifold Learning — t-SNE recovers the neighborhood graph, not a metric embedding.

• Underestimate: $0.10\cdot \ln \frac{0.10}{0.01}=0.10\cdot \ln (10)=0.10\cdot 2.302585=0.2302585$.
• Overestimate: $0.10\cdot \ln \frac{0.10}{0.50}=0.10\cdot \ln (0.2)=0.10\cdot (-1.609438)=-0.1609438$.

The underestimate penalty (+0.230) is a large positive cost; the overestimate term is negative (it actually reduces this pair's contribution). Concretely, t-SNE pays dearly for tearing true neighbors apart and pays little (or is even rewarded per-term) for keeping them slightly too close. This is the same asymmetry from Exercise 3.2, now with numbers — the mechanism that makes t-SNE guard local neighborhoods above all else.

What is the single quantity t-SNE minimizes, and what one thing should you never read off its plot? ::: It minimizes $\text{KL}(P\Vert Q)$; never read quantitative meaning into cluster gaps or sizes — only trust which points cluster together.