en>Bazonka: Help needed: Natural boundary

2014-01-26T10:03:14Z

New page

{{primary sources|date=December 2013}}
{{lower case title}}
'''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|date=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 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.

The t-SNE algorithms comprises two main stages. First, t-SNE constructs a [[probability distribution]] over pairs of high-dimensional objects in such a way that similar objects have a high probability of being picked, whilst dissimilar points have an [[infinitesimal]] probability of being picked. Second, t-SNE defines a similar probability distribution over the points in the low-dimensional map, and it minimizes the [[Kullback-Leibler divergence]] between the two distributions with respect to the locations of the points in the map.

t-SNE has been used in a wide range of applications, including [[computer security]] research,<ref>{{cite journal|last=Gashi|first=I.|coauthors=Stankovic, V., Leita, C., 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> [[music analysis]],<ref>{{cite journal|last=Hamel|first=P.|coauthors=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.|coauthors=Giger, M.L., Drukker, K., Lui, H., Yuan, Y., 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(1)|year=2010|pages=339–351|doi=10.1118/1.3267037|volume=37}}</ref> and [[bio-informatics]].<ref>{{cite journal|last=Wallach|first=I.|coauthors=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}}</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:

<math>p_{j|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>

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

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.

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>) 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, <math>q_{ij}</math> is defined as:

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

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.

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>:

<math>KL(P||Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}</math>

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.

== References ==
{{reflist}}

[[Category:Machine learning algorithms]]

Fabry gap theorem - Revision history

en>Bazonka: Help needed: Natural boundary