t-Distributed Stochastic Neighbor Embedding

Definition

The t-distributed stochastic neighbor embedding (t-SNE) is a statistical method for visualizing high-dimensional data. 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.

Algorithm

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

Define the conditional probability by Normal Distribution $p_{j|i}=\frac{\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-||{\mathbf{x}}_i-{\mathbf{x}}_k|{|}^2/2{\sigma }_i^2)},\forall i\ne j$ where ${\sigma }_i$ acts as an adaptive bandwidth parameter for each point $i$, and is indirectly determined by the given hyperparameter (perplexity).

And define the probability $p_{ij}=\frac{p_{j|i}+p_{i|j}}{2N}$ where $n$ is the number of data set

2. Defines a similar probability distribution over the points in the low-dimensional map,

Define the similarities between two points in the low-dimensional map. $q_{ij}=\frac{(1+||{\mathbf{y}}_i-{\mathbf{y}}_j|{|}^2{)}^{-1}}{\sum _{k\ne i}(1+||{\mathbf{y}}_k-{\mathbf{y}}_l|{|}^2{)}^{-1}},\forall i\ne j$

3. Minimizes the Kullback-Leibler Divergence between the two distributions with respect to the locations of the points in the low-dimensional map.

$\underset{\mathbf{y}}{\mathrm{argmin}}KL(P||Q)=\sum _{i\ne j}{p}_{ij}\ln \left(\frac{p_{ij}}{q_{ij}}\right)$