t-distributed stochastic neighbor embedding

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

For $i\; \backslash neq\; j$, define

: $p\_\{j\backslash mid\; i\}\; =\; \backslash frac\{\backslash exp(-\backslash lVert\backslash mathbf\{x\}\_i\; -\; \backslash mathbf\{x\}\_j\backslash rVert^2\; /\; 2\backslash sigma\_i^2)\}\{\backslash sum\_\{k\; \backslash neq\; i\}\; \backslash exp(-\backslash lVert\backslash mathbf\{x\}\_i\; -\; \backslash mathbf\{x\}\_k\backslash rVert^2\; /\; 2\backslash sigma\_i^2)\}$

and set $p\_\{i\backslash mid\; i\}\; =\; 0$.

Note the above denominator ensures $\backslash sum\_j\; p\_\{j\backslash mid\; i\}\; =\; 1$ for all $i$.

As van der Maaten and Hinton explained: "The similarity of datapoint $x\_j$ to datapoint $x\_i$ is the conditional probability, $p\_\{j|i\}$, that $x\_i$ would pick $x\_j$ as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at $x\_i$."

Now define

: $p\_\{ij\}\; =\; \backslash frac\{p\_\{j\backslash mid\; i\}\; +\; p\_\{i\backslash mid\; j\}\}\{2N\}$

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

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

The bandwidth of the Gaussian kernels $\backslash sigma\_i$ is set in such a way that the entropy of the conditional distribution equals a predefined entropy using the bisection method. As a result, the bandwidth is adapted to the density of the data: smaller values of $\backslash sigma\_i$ are used in denser parts of the data space. The entropy increases with the perplexity of this distribution $P\_i$; this relation is seen as

: $Perp(P\_i)\; =\; 2^\{H(P\_i)\}$

where $H(P\_i)$ is the Shannon entropy $H(P\_i)=-\backslash sum\_jp\_\{j|i\}\backslash log\_2p\_\{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.".

Since the Gaussian kernel uses the Euclidean distance $\backslash lVert\; x\_i-x\_j\; \backslash rVert$, it is affected by the curse of dimensionality, and in high dimensional data when distances lose the ability to discriminate, the $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 the intrinsic dimension of each point, to alleviate this.{{Cite conference|last1=Schubert|first1=Erich|last2=Gertz|first2=Michael|date=2017-10-04|title=Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection|conference=SISAP 2017 – 10th International Conference on Similarity Search and Applications|pages=188–203|doi=10.1007/978-3-319-68474-1_13}}

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

Specifically, for $i\; \backslash neq\; j$, define $q\_\{ij\}$ as

: $q\_\{ij\}\; =\; \backslash frac\{(1\; +\; \backslash lVert\; \backslash mathbf\{y\}\_i\; -\; \backslash mathbf\{y\}\_j\backslash rVert^2)^\{-1\}\}\{\backslash sum\_k\; \backslash sum\_\{l\; \backslash neq\; k\}\; (1\; +\; \backslash lVert\; \backslash mathbf\{y\}\_k\; -\; \backslash mathbf\{y\}\_l\backslash rVert^2)^\{-1\}\}$

and set $q\_\{ii\}\; =\; 0$.

Herein a heavy-tailed Student t-distribution (with one-degree of freedom, which is the same as a Cauchy 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 $\backslash mathbf\{y\}\_i$ in the map are determined by minimizing the (non-symmetric) Kullback–Leibler divergence of the distribution $P$ from the distribution $Q$, that is:

: $\backslash mathrm\{KL\}\backslash left(P\; \backslash parallel\; Q\backslash right)\; =\; \backslash sum\_\{i\; \backslash neq\; j\}\; p\_\{ij\}\; \backslash log\; \backslash frac\{p\_\{ij\}\}\{q\_\{ij\}\}$

The minimization of the Kullback–Leibler divergence with respect to the points $\backslash mathbf\{y\}\_i$ is performed using gradient 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 display clusters, 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,{{Cite web |title=K-means clustering on the output of t-SNE |url=https://stats.stackexchange.com/a/264647 |access-date=2018-04-16 |website=Cross Validated}} 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.{{Cite journal |last1=Wattenberg |first1=Martin |last2=Viégas |first2=Fernanda |last3=Johnson |first3=Ian |date=2016-10-13 |title=How to Use t-SNE Effectively |url=http://distill.pub/2016/misread-tsne |journal=Distill |language=en |volume=1 |issue=10 |pages=e2 |doi=10.23915/distill.00002 |issn=2476-0757|doi-access=free }} Thus, interactive exploration may be needed to choose parameters and validate results.{{Cite journal |last1=Pezzotti |first1=Nicola |last2=Lelieveldt |first2=Boudewijn P. F. |last3=Maaten |first3=Laurens van der |last4=Hollt |first4=Thomas |last5=Eisemann |first5=Elmar |last6=Vilanova |first6=Anna |date=2017-07-01 |title=Approximated and User Steerable tSNE for Progressive Visual Analytics |journal=IEEE Transactions on Visualization and Computer Graphics |language=en-US |volume=23 |issue=7 |pages=1739–1752 |arxiv=1512.01655 |doi=10.1109/tvcg.2016.2570755 |issn=1077-2626 |pmid=28113434 |s2cid=353336}}{{cite journal |last1=Wattenberg |first1=Martin |last2=Viégas |first2=Fernanda |last3=Johnson |first3=Ian |date=2016-10-13 |title=How to Use t-SNE Effectively |url=https://distill.pub/2016/misread-tsne/ |journal=Distill |language=en |volume=1 |issue=10 |doi=10.23915/distill.00002 |access-date=4 December 2017 |doi-access=free}} It has been shown that t-SNE can often recover well-separated clusters, and with special parameter choices, approximates a simple form of spectral clustering.{{cite arXiv |eprint=1706.02582 |class=cs.LG |first1=George C. |last1=Linderman |first2=Stefan |last2=Steinerberger |title=Clustering with t-SNE, provably |date=2017-06-08}}

• A C++ implementation of Barnes-Hut is available on the [https://github.com/lvdmaaten/bhtsne github account] of one of the original authors.
• The R package [https://CRAN.R-project.org/package=Rtsne Rtsne] implements t-SNE in R.
• 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 with TensorFlow, also implements t-SNE ([https://projector.tensorflow.org/ online version])
• The Julia package [https://juliapackages.com/p/tsne TSne] implements t-SNE

{{reflist}}

• {{Cite journal |last1=Wattenberg |first1=Martin |last2=Viégas |first2=Fernanda |last3=Johnson |first3=Ian |date=2016-10-13 |title=How to Use t-SNE Effectively |url=https://distill.pub/2016/misread-tsne/ |journal=Distill |language=en |volume=1 |issue=10 |pages=e2 |doi=10.23915/distill.00002 |issn=2476-0757|doi-access=free }}. Interactive demonstration and tutorial.
• [https://www.youtube.com/watch?v=RJVL80Gg3lA Visualizing Data Using t-SNE], Google Tech Talk about t-SNE
• [https://lvdmaaten.github.io/tsne/ Implementations of t-SNE in various languages], A link collection maintained by Laurens van der Maaten

Category:Machine learning algorithms

Category:Dimension reduction