T-distributed stochastic neighbor embedding: Difference between revisions

Revision as of 23:29, 24 June 2013

Latest revision as of 01:25, 24 May 2025

(194 intermediate revisions by more than 100 users not shown)

Line 1:

{{short description|Technique for dimensionality reduction}}

{{lower case title}}

{{redirect|TSNE|the Boston-based organization|Third Sector New England}}

'''t-Distributed Stochastic Neighbor Embedding (t-SNE)''' is a [[machine learning]] algorithm for [[dimensionality reduction]] developed by Laurens van der Maaten and [[Geoffrey Hinton]].<ref>{{cite journal|last=van der Maaten|first=L.J.P.|coauthors=Hinton, G.E.|title=Visualizing High-Dimensional Data Using t-SNE|journal=Journal of Machine Learning Research 9|year=2008|month=Nov|pages=2579–2605|url=http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf}}</ref> It is a [[nonlinear dimensionality reduction]] technique that is particularly well suited for embedding high-dimensional data into a space of two or three dimensions, which can then be visualized in a scatter plot. 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.

[[File:T-SNE visualisation of word embeddings generated using 19th century literature.png|thumb|T-SNE visualisation of [[word embedding]]s generated using 19th century literature]]

[[File:T-SNE Embedding of MNIST.png|thumb|T-SNE embeddings of [[MNIST]] dataset]]

{{lower caselowercase title}}

{{Data Visualization}}

'''t-Distributeddistributed Stochasticstochastic Neighborneighbor Embeddingembedding''' ('''t-SNE)''') is a [[machine learningstatistical]] algorithmmethod 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 [[dimensionalityGeoffrey reductionHinton]] developedand bySam Roweis,<ref name="SNE">{{cite conference |date=January 2002 |title=Stochastic neighbor embedding |url=https://papers.nips.cc/paper_files/paper/2002/file/6150ccc6069bea6b5716254057a194ef-Paper.pdf |conference=[[Neural Information Processing Systems]] |author1-last=Hinton |author1-first=Geoffrey |author2-last=Roweis |author2-first=Sam}}</ref> where Laurens van der Maaten and Hinton proposed the [[GeoffreyStudent's Hintont-distribution|''t''-distributed]] variant.<ref name=MaatenHinton>{{cite journal|last=van der Maaten|first=L.J.P.|coauthorsauthor2=Hinton, G.E. |title=Visualizing High-Dimensional Data Using t-SNE|journal=Journal of Machine Learning Research 9|yearvolume=20089|monthdate=Nov 2008|pages=2579–2605|url=http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf}}</ref> It is a [[nonlinear dimensionality reduction]] technique that is particularly well suited for embedding high-dimensional data intofor visualization in a low-dimensional space of two or three dimensions, which can then be visualized in a scatter plot. 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 algorithmsalgorithm comprises two main stages. First, t-SNE constructs a [[probability distribution]] over pairs of high-dimensional objects in such a way that similar objects haveare assigned a highhigher probability of being picked, whilstwhile dissimilar points haveare anassigned [[infinitessimal]] probability ofa beinglower pickedprobability. Second, t-SNE defines a similar probability distribution over the points in the low-dimensional map, and it minimizes the [[Kullback-LeiblerKullback–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 metric|Riemannian]] variant is [[Uniform manifold approximation and projection|UMAP]].

t-SNE has been used for visualization in a wide range of applications, including [[genomics]], [[computer security]] research,<ref>{{cite journal|last=Gashi|first=I.|coauthorsauthor2=Stankovic, V., |author3=Leita, C., |author4=Thonnard, O. |title=An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines|journal=Proceedings of the IEEE International Symposium on Network Computing and Applications|year=2009|pages=4–11}}</ref> [[natural language processing]], [[music analysis]],<ref>{{cite journal|last=Hamel|first=P.|coauthorsauthor2=Eck, D. |title=Learning Features from Music Audio with Deep Belief Networks|journal=Proceedings of the International Society for Music Information Retrieval Conference|year=2010|pages=339–344}}</ref> [[cancer research]],<ref>{{cite journal|last=Jamieson|first=A.R.|coauthorsauthor2=Giger, M.L., |author3=Drukker, K., |author4=Lui, H., |author5=Yuan, Y., |author6=Bhooshan, N. |title=Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE|journal=Medical Physics 37( |issue=1)|year=2010|pages=339–351|doi=10.1118/1.3267037|pmid=20175497|volume=37|pmc=2807447}}</ref> and [[bio-informaticsbioinformatics]].,<ref>{{cite journal|last=Wallach|first=I.|coauthorsauthor2=Liliean, R. |title=The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding|journal=Bioinformatics 25(5)|year=2009|pages=615–620|doi=10.1093/bioinformatics/btp035|volume=25|issue=5|pmid=19153135|doi-access=free}}</ref> geological ___domain interpretation,<ref>{{Cite journal|date=2019-04-01|title=A comparison of t-SNE, SOM and SPADE for identifying material type domains in geological data|url=https://www.sciencedirect.com/science/article/pii/S0098300418306010|journal=Computers & Geosciences|language=en|volume=125|pages=78–89|doi=10.1016/j.cageo.2019.01.011|issn=0098-3004|last1=Balamurali|first1=Mehala|last2=Silversides|first2=Katherine L.|last3=Melkumyan|first3=Arman|bibcode=2019CG....125...78B |s2cid=67926902|url-access=subscription}}</ref><ref>{{Cite book|last1=Balamurali|first1=Mehala|last2=Melkumyan|first2=Arman|date=2016|editor-last=Hirose|editor-first=Akira|editor2-last=Ozawa|editor2-first=Seiichi|editor3-last=Doya|editor3-first=Kenji|editor4-last=Ikeda|editor4-first=Kazushi|editor5-last=Lee|editor5-first=Minho|editor6-last=Liu|editor6-first=Derong|chapter=t-SNE Based Visualisation and Clustering of Geological Domain|chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-46681-1_67|title=Neural Information Processing|series=Lecture Notes in Computer Science|volume=9950|language=en|___location=Cham|publisher=Springer International Publishing|pages=565–572|doi=10.1007/978-3-319-46681-1_67|isbn=978-3-319-46681-1}}</ref><ref>{{Cite journal|last1=Leung|first1=Raymond|last2=Balamurali|first2=Mehala|last3=Melkumyan|first3=Arman|date=2021-01-01|title=Sample Truncation Strategies for Outlier Removal in Geochemical Data: The MCD Robust Distance Approach Versus t-SNE Ensemble Clustering|url=https://doi.org/10.1007/s11004-019-09839-z|journal=Mathematical Geosciences|language=en|volume=53|issue=1|pages=105–130|doi=10.1007/s11004-019-09839-z|bibcode=2021MatGe..53..105L |s2cid=208329378|issn=1874-8953|url-access=subscription}}</ref> and biomedical signal processing.<ref>{{Cite book|last1=Birjandtalab|first1=J.|last2=Pouyan|first2=M. B.|last3=Nourani|first3=M.|title=2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI) |chapter=Nonlinear dimension reduction for EEG-based epileptic seizure detection |date=2016-02-01|pages=595–598|doi=10.1109/BHI.2016.7455968|isbn=978-1-5090-2455-1|s2cid=8074617}}</ref>

For a data set with ''n'' elements, t-SNE runs in {{math|O(''n''²)}} time and requires {{math|O(''n''²)}} space.<ref>{{cite arXiv|title=Approximated and User Steerable tSNE for Progressive Visual Analytics|last=Pezzotti|first=Nicola|date=2015 |class=cs.CV |eprint=1512.01655 }}</ref>

== Details ==

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

For <math>i \neq j</math>, define
: <math>p_{j|\mid i} = \frac{\exp(-\lVert\mathbf{x}_i, - \mathbf{x}_j\rVert^2 / 2\sigma_i^2)}{\sum_{k \neq i} \exp(-\lVert\mathbf{x}_i, - \mathbf{x}_k\rVert^2 / 2\sigma_i^2)},</math>

and set <math>p_{i\mid i} = 0</math>.

Note the above denominator ensures <math>\sum_j p_{j\mid i} = 1</math> for all <math>i</math>.

As van der Maaten and Hinton explained: "The similarity of datapoint <math>x_j</math> to datapoint <math>x_i</math> is the conditional probability, <math>p_{j|i}</math>, that <math>x_i</math> would pick <math>x_j</math> as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at <math>x_i</math>."<ref name=MaatenHinton/>

<math>p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}</math>

Now define

The bandwidth of the Gaussian kernels <math>\sigma_i</math>, is set in such a way that the [[perplexity]] of the conditional distribution equals a predefined perplexity using a [[binary search]]. As a result, the bandwidth is adapted to the [[density]] of the data: smaller values of <math>\sigma_i</math> are used in denser parts of the data space.

: <math>p_{ij} = \frac{p_{j|\mid i} + p_{i|\mid j}}{2N}</math>

t-SNEThis aimsis tomotivated learnbecause a <math>d</math>-dimensional map <math>\mathbf{y}_1, \dots, \mathbfp_{yi}_N</math> (withand <math>\mathbf{y}_i \in \mathbbp_{Rj}^d</math>) that reflectsfrom the similaritiesN samples <math>p_{ij}</math>are estimated as good1/N, asso possible.the Toconditional thisprobability end, itcan be written as measures similarities <math>q_p_{i\mid j} = Np_{ij}</math> between twoand points in the map <math>p_{j\mathbf{ymid i}_i</math> and= <math>\mathbfNp_{yji}_j</math>, using. a very similar approach. Specifically,Since <math>q_ p_{ij} = p_{ji}</math>, isyou definedcan as:obtain previous formula.

Also note that <math>q_p_{ijii} = \frac{(10 +</math> \lVertand \mathbf{y}_i - \mathbf{y}_j\rVert^2)^{-1}}{<math>\sum_{k \neqi, lj} (1 + \lVert \mathbfp_{yij}_k -= \mathbf{y}_l))^{-1}}</math>.

The bandwidth of the [[Gaussian kernelskernel]]s <math>\sigma_i</math>, is set in such a way that the [[perplexityEntropy (information theory)|entropy]] of the conditional distribution equals a predefined perplexityentropy using athe [[binarybisection searchmethod]]. As a result, the bandwidth is adapted to the [[density]] of the data: smaller values of <math>\sigma_i</math> are used in denser parts of the data space. The entropy increases with the [[perplexity]] of this distribution <math>P_i</math>; this relation is seen as

Herein a heavy-tailed [[Student-t distribution]] is used to measure similarities between low-dimensional points in order to allow dissimilar objects to be modeled far apart in the map CITATION.

: <math>Perp(P_i) = 2^{H(P_i)}</math>

The locations of the points <math>\mathbf{y}_i</math> in the map are determined by minimizing the [[Kullback-Leibler divergence]] between the two distributions <math>P</math> and <math>Q</math>:

where <math>KLH(P||QP_i)</math> =is \sum_{ithe \neqShannon j}entropy p_<math>H(P_i)=-\sum_jp_{ijj|i} \log \fraclog_2p_{p_{ij}}{q_{ij}j|i}.</math>

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.".<ref name=MaatenHinton/>

The minimization of the Kullback-Leibler divergence with respect to the points <math>\mathbf{y}_i</math> is performed using [[gradient descent]]. The result of this optimization is a map that reflects the similarities between the high-dimensional inputs well.

Since the Gaussian kernel uses the [[Euclidean distance]] <math>\lVert x_i-x_j \rVert</math>, it is affected by the [[curse of dimensionality]], and in high dimensional data when distances lose the ability to discriminate, the <math>p_{ij}</math> 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.<ref>{{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}}</ref>

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

Specifically, for <math>i \neq j</math>, define <math>q_{ij}</math> as

: <math>q_{ij} = \frac{(1 + \lVert \mathbf{y}_i - \mathbf{y}_j\rVert^2)^{-1}}{\sum_k \sum_{l \neq k} (1 + \lVert \mathbf{y}_k - \mathbf{y}_l\rVert^2)^{-1}}</math>

and set <math> q_{ii} = 0 </math>.

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 CITATION.

The locations of the points <math>\mathbf{y}_i</math> in the map are determined by minimizing the (non-symmetric) [[Kullback-LeiblerKullback–Leibler divergence]] betweenof the two distributionsdistribution <math>P</math> andfrom the distribution <math>Q</math>, that is:

: <math>\mathrm{KL}\left(P \parallel Q\right) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}</math>

The minimization of the Kullback-LeiblerKullback–Leibler divergence with respect to the points <math>\mathbf{y}_i</math> is performed using [[gradient descent]]. The result of this optimization is a map that reflects the similarities between the high-dimensional inputs well.

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 [[cluster analysis|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,<ref>{{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}}</ref> 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.<ref>{{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 }}</ref> Thus, interactive exploration may be needed to choose parameters and validate results.<ref>{{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}}</ref><ref>{{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}}</ref> 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]].<ref>{{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}}</ref>

== Software ==

* 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 (programming language)|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 (programming language)|Julia]] package [https://juliapackages.com/p/tsne TSne] implements t-SNE

== References ==

{{reflist}}

== External links ==

{{Uncategorized|date=June 2013}}

* {{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]]