t-distributed stochastic neighbor embedding (t-SNE) is astatistical method for visualizing high-dimensional data by giving each datapoint a location in a two or three-dimensional map. It is based on Stochastic Neighbor Embedding originally developed byGeoffrey Hinton and Sam Roweis,^[1] where Laurens van der Maaten and Hinton proposed thet-distributed variant.^[2] It is anonlinear dimensionality reduction technique for embedding high-dimensional data for visualization in a low-dimensional space of two or three dimensions. Specifically, it models each high-dimensional object by a two- or three-dimensional point in such a way that similar objects are modeled by nearby points and dissimilar objects are modeled by distant points with high probability.

The t-SNE algorithm comprises two main stages. First, t-SNE constructs aprobability distribution over pairs of high-dimensional objects in such a way that similar objects are assigned a higher probability while dissimilar points are assigned a lower probability. Second, t-SNE defines a similar probability distribution over the points in the low-dimensional map, and it minimizes theKullback–Leibler divergence (KL divergence) between the two distributions with respect to the locations of the points in the map. While the original algorithm uses theEuclidean distance between objects as the base of its similarity metric, this can be changed as appropriate. ARiemannian variant isUMAP.

t-SNE has been used for visualization in a wide range of applications, includinggenomics,computer security research,^[3]natural language processing,music analysis,^[4]cancer research,^[5]bioinformatics,^[6] geological domain interpretation,^[7][8][9] and biomedical signal processing.^[10]

For a data set withn elements, t-SNE runs inO(n²) time and requiresO(n²) space.^[11]

Given a set of${\displaystyle N}$ high-dimensional objects${\displaystyle {\mathbf{x}}_1,\dots ,{\mathbf{x}}_N}$, t-SNE first computes probabilities${\displaystyle p_{ij}}$ that are proportional to the similarity of objects${\displaystyle {\mathbf{x}}_i}$ and${\displaystyle {\mathbf{x}}_j}$, as follows.

For${\displaystyle i\ne j}$, define

${\displaystyle p_{j\mid i}=\frac{\exp (-\Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {\mathbf{x}}_i-{\mathbf{x}}_k{\Vert }^2/2{\sigma }_i^2)}}$

and set${\displaystyle p_{i\mid i}=0}$. Note the above denominator ensures${\displaystyle \sum _j{p}_{j\mid i}=1}$ for all${\displaystyle i}$.

As van der Maaten and Hinton explained: "The similarity of datapoint${\displaystyle x_j}$ to datapoint${\displaystyle x_i}$ is the conditional probability,${\displaystyle p_{j|i}}$, that${\displaystyle x_i}$ would pick${\displaystyle x_j}$ as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at${\displaystyle x_i}$."^[2]

Now define

${\displaystyle p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2N}}$

This is motivated because${\displaystyle p_i}$ and${\displaystyle p_j}$ from the N samples are estimated as 1/N, so the conditional probability can be written as${\displaystyle p_{i\mid j}=N{p}_{ij}}$ and${\displaystyle p_{j\mid i}=N{p}_{ji}}$ . Since${\displaystyle p_{ij}=p_{ji}}$, you can obtain previous formula.

Also note that${\displaystyle p_{ii}=0}$ and${\displaystyle \sum _{i,j}{p}_{ij}=1}$.

The bandwidth of theGaussian kernels${\displaystyle {\sigma }_i}$ is set in such a way that theentropy of the conditional distribution equals a predefined entropy using thebisection method. As a result, the bandwidth is adapted to thedensity of the data: smaller values of${\displaystyle {\sigma }_i}$ are used in denser parts of the data space. The entropy increases with theperplexity of this distribution${\displaystyle P_i}$; this relation is seen as

${\displaystyle Perp(P_i)=2^{H(P_i)}}$

where${\displaystyle H(P_i)}$ is the Shannon entropy${\displaystyle H(P_i)=-\sum _j{p}_{j|i}{\log }_2{p}_{j|i}.}$

The perplexity is a hand-chosen parameter of t-SNE, and as the authors state, "perplexity can be interpreted as a smooth measure of the effective number of neighbors. The performance of SNE is fairly robust to changes in the perplexity, and typical values are between 5 and 50.".^[2]

Since the Gaussian kernel uses theEuclidean distance${\displaystyle \Vert x_i-x_j\Vert }$, it is affected by thecurse of dimensionality, and in high dimensional data when distances lose the ability to discriminate, the${\displaystyle p_{ij}}$ become too similar (asymptotically, they would converge to a constant). It has been proposed to adjust the distances with a power transform, based on theintrinsic dimension of each point, to alleviate this.^[12]

t-SNE aims to learn a${\displaystyle d}$-dimensional map${\displaystyle {\mathbf{y}}_1,\dots ,{\mathbf{y}}_N}$ (with${\displaystyle {\mathbf{y}}_i\in {\mathbb{R}}^d}$ and${\displaystyle d}$ typically chosen as 2 or 3) that reflects the similarities${\displaystyle p_{ij}}$ as well as possible. To this end, it measures similarities${\displaystyle q_{ij}}$ between two points in the map${\displaystyle {\mathbf{y}}_i}$ and${\displaystyle {\mathbf{y}}_j}$, using a very similar approach. Specifically, for${\displaystyle i\ne j}$, define${\displaystyle q_{ij}}$ as

${\displaystyle q_{ij}=\frac{(1+\Vert {\mathbf{y}}_i-{\mathbf{y}}_j{\Vert }^2{)}^{-1}}{\sum _k\sum _{l\ne k}(1+\Vert {\mathbf{y}}_k-{\mathbf{y}}_l{\Vert }^2{)}^{-1}}}$

and set${\displaystyle q_{ii}=0}$. Herein a heavy-tailedStudent t-distribution (with one-degree of freedom, which is the same as aCauchy distribution) is used to measure similarities between low-dimensional points in order to allow dissimilar objects to be modeled far apart in the map.

The locations of the points${\displaystyle {\mathbf{y}}_i}$ in the map are determined by minimizing the (non-symmetric)Kullback–Leibler divergence of the distribution${\displaystyle P}$ from the distribution${\displaystyle Q}$, that is:

${\displaystyle \mathrm{K}\mathrm{L}\left(P\parallel Q\right)=\sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}}$

The minimization of the Kullback–Leibler divergence with respect to the points${\displaystyle {\mathbf{y}}_i}$ is performed usinggradient descent. The result of this optimization is a map that reflects the similarities between the high-dimensional inputs.

While t-SNE plots often seem to displayclusters, the visual clusters can be strongly influenced by the chosen parameterization (especially the perplexity) and so a good understanding of the parameters for t-SNE is needed. Such "clusters" can be shown to even appear in structured data with no clear clustering,^[13] and so may be false findings. Similarly, the size of clusters produced by t-SNE is not informative, and neither is the distance between clusters.^[14] Thus, interactive exploration may be needed to choose parameters and validate results.^[15][16] It has been shown that t-SNE can often recover well-separated clusters, and with special parameter choices, approximates a simple form ofspectral clustering.^[17]

• A C++ implementation of Barnes-Hut is available on thegithub account of one of the original authors.
• The R packageRtsne implements t-SNE inR.
• ELKI contains tSNE, also with Barnes-Hut approximation
• scikit-learn, a popular machine learning library in Python implements t-SNE with both exact solutions and the Barnes-Hut approximation.
• Tensorboard, the visualization kit associated withTensorFlow, also implements t-SNE (online version)
• TheJulia packageTSne implements t-SNE

• Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (2016-10-13)."How to Use t-SNE Effectively".Distill.1 (10): e2.doi:10.23915/distill.00002.ISSN 2476-0757.. Interactive demonstration and tutorial.
• Visualizing Data Using t-SNE, Google Tech Talk about t-SNE
• Implementations of t-SNE in various languages, A link collection maintained by Laurens van der Maaten

• Machine learning algorithms
• Dimension reduction

• Articles with short description
• Short description matches Wikidata