Stochastic neighbor embedding

Stochastic neighbor embedding (SNE) is a nonlinear method of dimensionality reduction that represents high-dimensional observations as points in a lower-dimensional space. The method converts pairwise distances into conditional probability distributions and determines an embedding whose corresponding distribution approximates that of the original data. Its objective therefore concerns the preservation of probabilistic neighborhoods rather than the direct preservation of all distances.

SNE belongs to the broader class of manifold learning methods. It differs from linear techniques such as principal component analysis, which describe variation through orthogonal projections, and from metric techniques such as multidimensional scaling, which optimize a global measure of distance distortion. The stochastic terminology refers to the interpretation of neighboring points through probability distributions; it does not imply that the observations themselves arise from a specified stochastic process.

Historical development

The method was introduced in 2002 by Geoffrey Hinton, Sam Roweis, and You Watanabe. Their formulation treated each observation as the center of a locally scaled Gaussian distribution and compared the resulting high-dimensional neighborhoods with analogous distributions in the embedding. This construction linked neighborhood-preserving dimensionality reduction to concepts from information theory.

The original formulation was subsequently modified to address the asymmetry of its objective and the concentration of moderate distances in low-dimensional embeddings. In 2008, Laurens van der Maaten and Geoffrey Hinton introduced t-distributed stochastic neighbor embedding, commonly abbreviated t-SNE. That variant replaced the low-dimensional Gaussian model with a heavy-tailed Student's t-distribution and adopted a symmetric joint-probability objective.

Probabilistic neighborhood model

Let the high-dimensional observations be

[ x_1,x_2,\ldots,x_n \in \mathbb{R}^{D}, ]

and let their low-dimensional representations be

[ y_1,y_2,\ldots,y_n \in \mathbb{R}^{d}, ]

where (d) is generally much smaller than (D). For each high-dimensional point (x_i), SNE defines the conditional probability that (x_i) selects (x_j) as a neighbor:

[ p_{j\mid i}

\frac{ \exp\left(-\lVert x_i-x_j\rVert^2 / 2\sigma_i^2\right) }{ \sum_{k\ne i} \exp\left(-\lVert x_i-x_k\rVert^2 / 2\sigma_i^2\right) }, \qquad p_{i\mid i}=0. ]

The local scale (\sigma_i) varies between observations. Consequently, the probability model adapts to differences in sampling density: a point in a densely populated region generally receives a narrower Gaussian neighborhood than a point in a sparsely populated region.

The embedding defines a second family of conditional probabilities:

[ q_{j\mid i}

\frac{ \exp\left(-\lVert y_i-y_j\rVert^2\right) }{ \sum_{k\ne i} \exp\left(-\lVert y_i-y_k\rVert^2\right) }, \qquad q_{i\mid i}=0. ]

The probabilities (p_{j\mid i}) and (q_{j\mid i}) need not equal their reversed counterparts. A point may assign substantial probability to another point even when the reverse conditional probability is smaller, particularly when the two observations lie in regions with different local densities.

Perplexity and local scale

The scale (\sigma_i) is defined indirectly through the Shannon entropy of the conditional distribution (P_i). With entropy measured in bits,

[ H(P_i)

-\sum_j p_{j\mid i}\log_2 p_{j\mid i}, ]

and the associated perplexity is

[ \operatorname{Perp}(P_i)=2^{H(P_i)}. ]

Perplexity represents the effective number of neighbors receiving appreciable probability mass. A common target perplexity is imposed across observations, while the corresponding bandwidths remain point-dependent. This arrangement produces a uniform probabilistic notion of neighborhood size without requiring a uniform geometric radius.

Perplexity does not define a hard nearest-neighbor boundary. Every distinct pair has a nonzero Gaussian affinity in exact arithmetic, although distant observations contribute negligibly after normalization. The parameter instead controls how rapidly conditional probability is distributed across nearby observations.

Objective function

SNE measures the discrepancy between the high-dimensional and low-dimensional conditional distributions through the Kullback–Leibler divergence:

[ C

\sum_i \operatorname{KL}(P_i\Vert Q_i)

\sum_i\sum_j p_{j\mid i} \log \frac{p_{j\mid i}}{q_{j\mid i}}. ]

This divergence is asymmetric. A pair with large (p_{j\mid i}) and small (q_{j\mid i}) contributes substantially to the objective, because a high-dimensional neighbor has been placed too far away in the embedding. A pair with small (p_{j\mid i}) and relatively large (q_{j\mid i}) generally contributes less. The objective thus places greater numerical emphasis on retaining local neighborhoods than on preventing every unrelated pair from appearing nearby.

The cost is nonconvex as a function of the embedding coordinates. Distinct optimization runs can therefore converge to different local minima, even when they begin from distributions with the same statistical properties. The resulting coordinates have no intrinsic orientation or origin, since translation, rotation, and reflection preserve all pairwise distances and leave the objective unchanged.

Optimization

The embedding is obtained through iterative gradient descent or a related numerical optimization method. The gradient combines attractive terms associated with high-dimensional neighbors and repulsive terms induced by normalization over the low-dimensional distribution. Because every point enters a normalization denominator, the exact objective couples all observations rather than only explicitly selected neighbor pairs.

The original algorithm incorporated momentum to alter the accumulation of successive parameter updates. It also used an early phase in which the effective balance of forces differed from that near convergence. These numerical features concerned the optimization trajectory and did not change the probabilistic definition of the final objective.

Direct computation requires evaluating a quadratic number of pairwise affinities. This cost limits the scale of an exact implementation in both time and memory. Later approximations reduced the computational burden by combining sparse neighborhood graphs with spatial data structures or interpolation schemes, developments most commonly associated with t-SNE rather than the initial SNE formulation.

Crowding and the t-distributed modification

A local neighborhood occupying a moderate volume in high-dimensional space may require more low-dimensional area than a faithful distance-preserving embedding can provide. This geometric mismatch is known as the crowding problem. Under a Gaussian low-dimensional model, moderately separated observations can be forced into a relatively narrow region because the available radial volume grows much more slowly in two or three dimensions.

t-SNE modifies the high-dimensional probabilities into symmetric joint probabilities,

[ p_{ij}

\frac{p_{j\mid i}+p_{i\mid j}}{2n}, ]

and defines the low-dimensional probabilities by

[ q_{ij}

\frac{ \left(1+\lVert y_i-y_j\rVert^2\right)^{-1} }{ \sum_{k\ne l} \left(1+\lVert y_k-y_l\rVert^2\right)^{-1} }. ]

The low-dimensional kernel is a Student distribution with one degree of freedom, equivalent to a Cauchy distribution. Its heavy tail assigns more probability to moderately distant pairs than a Gaussian kernel would assign. The corresponding gradient is

[ \frac{\partial C}{\partial y_i}

4\sum_j (p_{ij}-q_{ij}) \frac{y_i-y_j} {1+\lVert y_i-y_j\rVert^2}. ]

This formulation changes the relative strength of attractive and repulsive interactions across distance. It does not convert the embedding into a global metric reconstruction, because the objective remains dominated by pairwise probability discrepancies associated with local structure.

Interpretation

An SNE embedding represents relationships encoded by its neighborhood probabilities. Nearby points usually correspond to observations with substantial mutual affinity, but the geometric size and separation of larger visible groups do not directly estimate their high-dimensional diameters or intergroup distances. Local density is also transformed because the adaptive high-dimensional bandwidths and normalized low-dimensional affinities do not preserve probability density in a direct manner.

The axes of the embedding are arbitrary coordinate directions rather than learned variables with independent semantic meanings. This distinguishes SNE from factor-based methods in which individual components correspond to ordered directions of variance. The principal mathematical object is the configuration as a whole, considered through its pairwise affinities.

SNE is related to graph-based methods because its high-probability affinities define a weighted neighborhood structure. Its objective nevertheless differs from that of Laplacian eigenmaps, which derive coordinates from the spectrum of a graph Laplacian, and from locally linear embedding, which preserves local reconstruction weights. It is also distinct from Isomap, where estimated geodesic distances are embedded through a global metric criterion.