Non-linear dimensionality reduction: t-SNE

Two true pairs, $P_1$/$P_2$ and $P_3$/$P_4$, start jumbled together at random. After training, the pairs pull apart from each other and tighten internally — nothing here promises where each pair ends up, only that points that were neighbors stay neighbors.

t-SNE converts distances into probabilities in both spaces, then makes the low-dimensional probabilities match the high-dimensional ones as closely as possible.

• $p_{ij}$ — how similar points $i,j$ are in the original high-dimensional space, from a Gaussian centered on each point.
• $q_{ij}$ — how similar their images $y_i, y_j$ are in the low-dimensional embedding, from a heavier-tailed Student-t distribution.
• $\sigma$ — the Gaussian's bandwidth (fixed here; real t-SNE solves for it per point to hit a target "perplexity").

1. A heavier-tailed kernel in low dimensions, on purpose

   Squeezing high-dimensional neighborhoods into 2D leaves less room for everyone — the Student-t kernel's heavy tails let moderately-distant points spread out further in the embedding without being punished, easing that crowding.

2. Minimize how much Q disagrees with P

   Gradient descent adjusts every embedded point $y_i$ to make $q_{ij}$ track $p_{ij}$ as closely as possible — the KL divergence between the two distributions is what's actually being minimized.

3. Only local structure is preserved

   Nothing in this objective cares about the absolute distance between two far-apart points, or which direction a cluster lands in — only whether true neighbors stay neighbors survives the compression.

Drag the steps slider. KL divergence doesn't fall smoothly — early on it can briefly get worse before the optimizer finds a better arrangement, the same way loss curves elsewhere in this course occasionally tick upward before a bigger drop. Given enough steps, it settles low and stays there.

Two tight pairs, $(0,0)$–$(1,0)$ and $(20,0)$–$(21,0)$, twenty units apart from each other:

1. Within-pair affinity

   With $\sigma=1$, $P_1$'s unnormalized Gaussian weights on $P_2$, $P_3$, $P_4$ are $e^{-1^2/2}\approx0.607$, $e^{-20^2/2}\approx0$, $e^{-21^2/2}\approx0$ — the far points contribute nothing measurable. Normalizing: $p_{2\mid1} = 0.607/0.607 \approx 1$, and the same reasoning from $P_2$'s side gives $p_{1\mid2}\approx1$. Symmetrizing over $n=4$ points:

   $$p_{12} = \frac{p_{2\mid1}+p_{1\mid2}}{2n} \approx \frac{1+1}{2\times4} = 0.25$$

   and symmetrically $p_{34} \approx 0.25$.

2. Cross-pair affinity is essentially zero

   $p_{13}$, between the two far-apart pairs, comes out indistinguishable from $0$ — high-dimensional space has already declared these pairs unrelated.

3. Training pulls each true pair together, blind to the original coordinates

   Neither $P_1$ nor $P_2$'s training process ever sees the numbers $0$, $1$, $20$, or $21$ again once $p_{ij}$ is computed — only the affinities. Yet gradient descent still finds an embedding where each pair ends up close and the two pairs end up apart, purely by matching $q_{ij}$ to $p_{ij}$.