T-distributed stochastic neighbor embedding explained

t-distributed stochastic neighbor embedding (t-SNE) is a statistical 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 by Geoffrey Hinton and Sam Roweis,^[1] where Laurens van der Maaten proposed the t-distributed variant.^[2] It is a nonlinear 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 a probability 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 the Kullback–Leibler divergence (KL divergence) between the two distributions with respect to the locations of the points in the map. While the original algorithm uses the Euclidean distance between objects as the base of its similarity metric, this can be changed as appropriate. A Riemannian variant is UMAP.

t-SNE has been used for visualization in a wide range of applications, including genomics, 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 with n elements, t-SNE runs in time and requires space.^[11]

Details

Given a set of

N high-dimensional objects x _{1,} ... , x _{N} , t-SNE first computes probabilities p _{ij} that are proportional to the similarity of objects x _{i} and x _{j} , as follows.

For

i ≠ j , define p _{j\mid} = (\exp( - \lVert x _{i} - x ^{2} _{j\rVert} / 2 \sigma ^{2 )} _{i})/(\sum _{k ≠ i} \exp( - \lVert x _{i} - x ^{2} _{k\rVert} / 2 \sigma ^{2 )} _{i}) and set p _{i\mid} = 0 . Note the above denominator ensures \sum _{j} p _{j\mid} = 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} ."^[2]

Now define

p _{ij} = (p _{j\mid} + p _{i\mid})/(2 N)

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\mid} = Np _{ij} and p _{j\mid} = Np _{ji} . Since p _{ij} = p _{ji} , you can obtain previous formula.

Also note that

p _{ii} = 0 and \sum _{i,} p _{ij} = 1 .

The bandwidth of the Gaussian kernels

\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 \sigma _{i} are used in denser parts of the data space.

Since the Gaussian kernel uses the Euclidean distance

\lVert x _{i-x} _{j} \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.^[12]

t-SNE aims to learn a

d -dimensional map y _{1,} ... , y _{N} (with y _{i} \in 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 y _{i} and y _{j} , using a very similar approach. Specifically, for i ≠ j , define q _{ij} asq _{ij} = (( 1 + \lVert y _{i} - y ^{2 )} _{j\rVert} ^{-1})/(\sum _{k} \sum _{l} ( 1 + \lVert y _{k} - y ^{2 )} _{l\rVert} ^{-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

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:KL \left(P \parallel Q\right) = \sum _{i} p _{ij} log (p _{ij})/(q _{ij})

The minimization of the Kullback–Leibler divergence with respect to the points

y _{i} is performed using gradient descent. The result of this optimization is a map that reflects the similarities between the high-dimensional inputs.

Output

While t-SNE plots often seem to display clusters, the visual clusters can be strongly influenced by the chosen parameterization 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 of spectral clustering.^[17]

Software

• The R package 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 (online version)
• The Julia package TSne implements t-SNE

External links

• 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

Notes and References

1. Hinton. Geoffrey. Roweis. Sam. Neural Information Processing Systems. Stochastic neighbor embedding. January 2002 .
2. van der Maaten. L.J.P.. Hinton, G.E. . Visualizing Data Using t-SNE. Journal of Machine Learning Research . 9. Nov 2008. 2579–2605.
3. Gashi. I.. Stankovic, V. . Leita, C. . Thonnard, O. . An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines. Proceedings of the IEEE International Symposium on Network Computing and Applications. 2009. 4–11.
4. Hamel. P.. Eck, D. . Learning Features from Music Audio with Deep Belief Networks. Proceedings of the International Society for Music Information Retrieval Conference. 2010. 339–344.
5. Jamieson. A.R.. Giger, M.L. . Drukker, K. . Lui, H. . Yuan, Y. . Bhooshan, N. . Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE. Medical Physics . 1. 2010. 339–351. 10.1118/1.3267037. 20175497. 37. 2807447.
6. Wallach. I.. Liliean, R. . The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding. Bioinformatics . 2009. 615–620. 10.1093/bioinformatics/btp035. 25. 5. 19153135. free.
7. 2019-04-01. A comparison of t-SNE, SOM and SPADE for identifying material type domains in geological data. Computers & Geosciences. en. 125. 78–89. 10.1016/j.cageo.2019.01.011. 0098-3004. Balamurali. Mehala. Silversides. Katherine L.. Melkumyan. Arman. 2019CG....125...78B . 67926902.
8. Balamurali. Mehala. Melkumyan. Arman. 2016. Hirose. Akira. Ozawa. Seiichi. Doya. Kenji. Ikeda. Kazushi. Lee. Minho. Liu. Derong. t-SNE Based Visualisation and Clustering of Geological Domain. Neural Information Processing. Lecture Notes in Computer Science. 9950. en. Cham. Springer International Publishing. 565–572. 10.1007/978-3-319-46681-1_67. 978-3-319-46681-1.
9. Leung. Raymond. Balamurali. Mehala. Melkumyan. Arman. 2021-01-01. Sample Truncation Strategies for Outlier Removal in Geochemical Data: The MCD Robust Distance Approach Versus t-SNE Ensemble Clustering. Mathematical Geosciences. en. 53. 1. 105–130. 10.1007/s11004-019-09839-z. 2021MaGeo..53..105L . 208329378. 1874-8953.
10. Book: Birjandtalab. J.. Pouyan. M. B.. Nourani. M.. 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI) . Nonlinear dimension reduction for EEG-based epileptic seizure detection . 2016-02-01. 595–598. 10.1109/BHI.2016.7455968. 978-1-5090-2455-1. 8074617.
11. Web site: Approximated and User Steerable tSNE for Progressive Visual Analytics. Pezzotti. Nicola. 31 August 2023.
12. Schubert. Erich. Gertz. Michael. 2017-10-04. Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection. SISAP 2017 – 10th International Conference on Similarity Search and Applications. 188–203. 10.1007/978-3-319-68474-1_13.
13. Web site: K-means clustering on the output of t-SNE . 2018-04-16 . Cross Validated.
14. Wattenberg . Martin . Viégas . Fernanda . Johnson . Ian . 2016-10-13 . How to Use t-SNE Effectively . Distill . en . 1 . 10 . e2 . 10.23915/distill.00002 . 2476-0757. free .
15. Pezzotti . Nicola . Lelieveldt . Boudewijn P. F. . Maaten . Laurens van der . Hollt . Thomas . Eisemann . Elmar . Vilanova . Anna . 2017-07-01 . Approximated and User Steerable tSNE for Progressive Visual Analytics . IEEE Transactions on Visualization and Computer Graphics . en-US . 23 . 7 . 1739–1752 . 1512.01655 . 10.1109/tvcg.2016.2570755 . 1077-2626 . 28113434 . 353336.
16. Wattenberg . Martin . Viégas . Fernanda . Johnson . Ian . 2016-10-13 . How to Use t-SNE Effectively . Distill . en . 1 . 10 . 10.23915/distill.00002 . 4 December 2017 . free.
17. 1706.02582 . cs.LG . George C. . Linderman . Stefan . Steinerberger . Clustering with t-SNE, provably . 2017-06-08.