t-Distributed Stochastic Neighbor Embedding (t-SNE)

In 2008, Laurens van der Maaten and Geoffrey Hinton published a paper that would fundamentally transform how we visualize high-dimensional data. Their algorithm, t-Distributed Stochastic Neighbor Embedding (t-SNE), solved a problem that had plagued dimensionality reduction for decades: how do you faithfully represent the local structure of high-dimensional data in two or three dimensions?

The answer lies in a beautifully elegant objective function that frames dimensionality reduction as a problem of matching probability distributions. Rather than preserving distances (like PCA or MDS), t-SNE preserves the probabilities that points are neighbors—a subtle but profound distinction that makes t-SNE extraordinarily effective at revealing cluster structure.

This page develops a complete, rigorous understanding of the t-SNE objective function. We will derive every component from first principles, understand the mathematical intuitions, and see exactly why this formulation produces such compelling visualizations.

Traditional dimensionality reduction methods like PCA and MDS attempt to preserve distances between points. While mathematically natural, this approach has a fundamental limitation: distances in high dimensions behave counterintuitively due to the curse of dimensionality.

In high-dimensional spaces, distances between points become increasingly similar. A consequence of measure concentration is that, for uniformly distributed points in high dimensions, the difference between the nearest and farthest neighbor shrinks relative to the absolute distances. This makes distance-based methods less effective at distinguishing meaningful structure.

t-SNE takes a radically different approach: instead of preserving distances, it preserves neighborhood probabilities. The key insight is to convert distances into probabilities that quantify "the likelihood that point i would pick point j as its neighbor."

Why probabilities instead of distances?

Probabilities offer several advantages over raw distances:

1. Automatic normalization: Probabilities naturally sum to 1, providing a scale-invariant measure of relative proximity
2. Information-theoretic framework: We can use KL divergence to measure distribution mismatches, which has well-understood properties
3. Focus on local structure: The probability formulation naturally emphasizes nearby points over distant ones
4. Robustness to curse of dimensionality: By converting to probabilities conditioned on each point's local neighborhood, we sidestep issues of measure concentration

The probabilistic formulation transforms dimensionality reduction from a geometric problem into a statistical inference problem: finding a low-dimensional configuration whose neighborhood probabilities best match those in high dimensions.

We begin by defining neighborhood relationships in the original high-dimensional space. Given N data points X = {x₁, x₂, ..., xₙ} in ℝᴰ, we need to quantify the probability that point xᵢ would "choose" point xⱼ as its neighbor.

Conditional Probabilities

t-SNE models this using a Gaussian distribution centered at each point. The conditional probability that xᵢ picks xⱼ as a neighbor is:

Understanding the Gaussian kernel:

The Gaussian kernel has several desirable properties for defining neighborhood probabilities:

1. Monotonic decay: As points get farther apart, the probability decreases smoothly
2. Rapidly vanishing tails: Very distant points contribute negligibly
3. Smooth gradients: The function is infinitely differentiable, enabling gradient-based optimization
4. Natural probabilistic interpretation: Related to the probability density of a Gaussian distribution

The bandwidth parameter σᵢ:

Notice that each point i has its own bandwidth σᵢ. This is crucial because data density varies across the manifold. In dense regions, we need smaller σᵢ to distinguish between many nearby points. In sparse regions, larger σᵢ ensures points still have meaningful neighbors.

The bandwidth is determined by a user-specified perplexity (discussed in detail on the next page), which effectively controls how many neighbors each point considers.

Symmetrization: Joint Probabilities

To eliminate asymmetry and simplify the optimization, t-SNE converts conditional probabilities to symmetric joint probabilities:

The division by 2N ensures the joint distribution sums to 1. This symmetrization has a nice interpretation: pᵢⱼ represents the probability that points i and j are neighbors when we sample pairs uniformly at random and then select according to their conditional probabilities.

Handling outliers:

An important benefit of this symmetrization is robustness to outliers. If point i is an outlier (far from all other points), P(j|i) will be spread relatively uniformly over all j (since all points are similarly far). But other points j will assign very low P(i|j) to the outlier. The average smooths this, ensuring outliers don't dominate the objective but still have meaningful embeddings.

Now we define neighborhood relationships in the low-dimensional embedding space. Given the map points Y = {y₁, y₂, ..., yₙ} in ℝᵈ (typically d = 2 or 3), we define joint probabilities qᵢⱼ analogously—but with a crucial difference.

The Crowding Problem

Using a Gaussian kernel in the low-dimensional space leads to a fundamental problem that van der Maaten and Hinton termed the crowding problem.

Consider a moderately large number of points in D dimensions that are mutual neighbors (all within similar distance of each other). When we try to embed these into 2D while preserving distances, we run into a geometric impossibility: the 2D space doesn't have "room" for all points to maintain their high-dimensional relative positions.

Mathematically, the volume of a d-dimensional ball scales as rᵈ. In D dimensions, there's ample room for many points at similar distances; in 2 dimensions, points get "crowded" together. To accommodate moderately distant points, truly nearby points must be crushed together, destroying local structure.

The Student-t Solution

t-SNE's key innovation is using a Student-t distribution with one degree of freedom (equivalently, a Cauchy distribution) in the low-dimensional space:

Why heavy tails solve the crowding problem:

The Student-t distribution has heavier tails than the Gaussian, meaning it assigns relatively more probability to distant points and relatively less to nearby points. This seemingly counterintuitive choice is exactly what's needed:

1. Nearby points: The numerator (1 + d²)⁻¹ remains close to 1 for small distances d, so nearby points still have high probability
2. Moderately distant points: The polynomial decay (versus exponential for Gaussian) allows moderately distant points to be pushed further apart without catastrophically reducing their probability
3. Net effect: There's "room" in the probability budget for moderately distant points to spread out, relieving pressure on truly nearby points

The heavy tails effectively create more space in the probability distribution for intermediate distances, alleviating the crowding problem.

The t-distribution as a limiting case:

The choice of ν = 1 degree of freedom emerges naturally. Van der Maaten and Hinton showed empirically that ν = 1 works well across many datasets. Theoretically, lower degrees of freedom give heavier tails (more spreading), while higher degrees approach the Gaussian (less spreading). The value ν = 1 provides a balance that works well for typical 2D visualizations.

Recent work on parametric t-SNE variants has explored learning the degrees of freedom, but ν = 1 remains the default for its robustness and simplicity.

With probability distributions P (from high-dimensional affinities) and Q (from low-dimensional affinities), we need an objective function that measures their similarity. t-SNE uses the Kullback-Leibler (KL) divergence, a fundamental information-theoretic measure.

The Cost Function

t-SNE minimizes the KL divergence from P to Q over the embedding coordinates Y:

Properties of KL Divergence:

1. Non-negativity: KL(P || Q) ≥ 0, with equality if and only if P = Q (Gibbs' inequality)
2. Asymmetry: KL(P || Q) ≠ KL(Q || P) in general—this asymmetry has important implications
3. Not a metric: Doesn't satisfy the triangle inequality
4. Information-theoretic interpretation: Expected number of extra bits needed to encode samples from P using a code optimal for Q

The Critical Asymmetry:

The direction of KL divergence—KL(P || Q) rather than KL(Q || P)—fundamentally shapes t-SNE's behavior:

Mathematical Consequence:

When qᵢⱼ is small but pᵢⱼ is large, the term pᵢⱼ log(pᵢⱼ/qᵢⱼ) contributes a large positive value to the cost. The log(1/qᵢⱼ) term can grow without bound as qᵢⱼ → 0, creating strong pressure to maintain high qᵢⱼ for pairs with high pᵢⱼ.

Conversely, when pᵢⱼ is small, even if qᵢⱼ is large, the multiplicative factor pᵢⱼ keeps the contribution small. This is why t-SNE can place globally distant points near each other in the embedding—there's little cost to doing so if they weren't neighbors in high dimensions.

To minimize the KL divergence, t-SNE uses gradient descent on the embedding coordinates. The gradient with respect to each embedding point yᵢ reveals a beautiful physical interpretation.

Deriving the Gradient:

The gradient of the cost function with respect to yᵢ is:

Physical Interpretation: Springs and Repulsion

The gradient has an elegant interpretation as a system of forces acting on each point:

Attractive Forces (pᵢⱼ > qᵢⱼ): When two points should be neighbors (high pᵢⱼ) but are currently too far apart in the embedding (low qᵢⱼ), the term (pᵢⱼ - qᵢⱼ) is positive. This creates an attractive force that pulls yᵢ toward yⱼ, like a spring connecting neighborhood points.

Repulsive Forces (pᵢⱼ < qᵢⱼ): When two points shouldn't be close neighbors (low pᵢⱼ) but are currently too close in the embedding (high qᵢⱼ), the term (pᵢⱼ - qᵢⱼ) is negative. This creates a repulsive force that pushes yᵢ away from yⱼ.

The Attenuation Factor (1 + ||yᵢ - yⱼ||²)⁻¹: This factor, coming from the Student-t kernel, attenuates forces for distant pairs. Points far apart in the embedding exert weaker forces on each other, allowing local neighborhoods to settle without interference from distant points.

Equilibrium and Cluster Formation:

At equilibrium (when the gradient is near zero for all points), each point experiences balanced attractive and repulsive forces:

1. Within clusters: Points with high mutual pᵢⱼ values settle at distances where qᵢⱼ ≈ pᵢⱼ, forming tight groups
2. Between clusters: Points from different clusters have low pᵢⱼ, so repulsive forces dominate, pushing clusters apart
3. Global arrangement: The heavy tails of the Student-t distribution allow clusters to spread out, using the full embedding space

This force-based view explains why t-SNE produces separated clusters: the combination of local attraction and global repulsion naturally creates discrete, well-separated groups from continuous high-dimensional manifolds.

t-SNE evolved from the original Stochastic Neighbor Embedding (SNE) algorithm proposed by Hinton and Roweis in 2002. Understanding the differences illuminates why t-SNE's modifications are essential.

Original SNE Formulation:

SNE used Gaussian kernels in both high-dimensional and low-dimensional spaces:

Why the Student-t Distribution Works:

The original SNE suffered severely from the crowding problem because Gaussian kernels in both spaces meant that any spreading of moderately distant points would cause their probabilities to plummet, incurring huge cost. Points were forced into a compromised state where neither local nor global structure was well-preserved.

The Student-t distribution's polynomial tails (versus the Gaussian's exponential tails) change the game:

• At d = 2 units apart:

  • Gaussian: exp(-4) ≈ 0.018 (1.8% of maximum)
  • Student-t: (1+4)⁻¹ = 0.2 (20% of maximum)

• At d = 5 units apart:

  • Gaussian: exp(-25) ≈ 10⁻¹¹ (essentially zero)
  • Student-t: (1+25)⁻¹ ≈ 0.04 (4% of maximum)

The Student-t distribution maintains meaningful probability for moderately distant points, giving the embedding "room to breathe" and place clusters at appropriate distances.

We have developed a complete understanding of the t-SNE objective function, its mathematical foundations, and the design choices that make it effective for visualization.

What's Next:

The objective function provides the mathematical foundation. But t-SNE's behavior in practice depends critically on the perplexity parameter, which controls the effective number of neighbors considered for each point. On the next page, we'll dive deep into perplexity—how it's defined, how it determines the bandwidths σᵢ, and how to choose it appropriately for different datasets.