I had heard of t-SNE a while back, but I didn’t have a clear reason to learn about it until I starting playing with Google’s TensorFlow. Specifically, TensorBoard is visualization tool in TensorFlow that is downright beautiful, and t-SNE is one option for visualizing high dimensional data. Googlers really like their artsy design choices – check out this presentation from a Google developer, complete with hat and hoodie. I stuck with some well-trodden ground by creating a neural net to classify MNIST characters. This is all secondary to the point here, however, because I really want to focus on t-SNE. Specifically, I want to know the math behind it while using MNIST and TensorBoard for some pretty visuals. For a purely practical/application perspective of t-SNE, check out this cool article. The original t-SNE paper is here.
Suppose we have points in . The first step of t-distributed stochastic neighbor embedding (t-SNE) is to view each datapoint as the center of a Gaussian distribution, and then ask how likely each remaining point would be chosen according to this distribution. More specifically, centering the Gaussian at say , we use the pdf of the Gaussian to define a probability distribution over the remaining points:
where is the appropriately chosen scalar. We also set . It’s completely possible to continue by using these conditional probability distributions, however, we will eventually need to perform an optimization based on these distributions which can be expensive. It is computationally simpler to work with a single distribution over all pairs of points, so often
is considered instead. We scaled again here to make this a probability distribution. Note may not equal as may not equal . We haven’t actually discussed how to choose the variance for the Gaussian around each point. More on this later. Regardless, clearly , and we have a probability distribution over , call it .
The general idea is then randomly assign points in a low -dimensional space (usually or ), define a similar probability distribution over pairs of points, and move the low dimensional points to make the distributions “close” to one another. Instead of building from Gaussian distributions as before, a t-distribution with a single degree of freedom is used (hence the “t” in t-SNE). In other words we set
where is again the appropriate constant. We set and define similarly to :
The reason for using a t-distribution is that the heavy tails keep the final distribution from being too densely concentrated – as far as I can tell, SNE was a technique using Gaussians for the target distribution, and t-SNE is a later variation that produced better results. There isn’t really a theoretical foundation for using the t-distribution over Gaussians – it’s purely about how the final distribution looks.
Now, if we randomly place in , defines a distribution over pairs of points , call it . Finally, we need to move the points so that is “close” to . The measure of closeness applied is the Kullback-Leibler divergence of from . That is, we minimize
via gradient descent. Note this objective in non-convex so running t-SNE multiple times with the same parameters (such parameters not discussed yet) and data may lead to different results.
We still haven’t discussed how to pick the variances for the conditional distributions denoted previously as . These are chosen via a user-selected parameter. Intuitively, for smaller variance, t-SNE will focus on local structure, and the larger the variance, the more global the t-SNE procedure becomes. It makes sense that you would also like this to depend on your data. If the data is dense around , you would like to be small, and conversely should be large when the data around is more sparse. This is accomplished by choosing each so the perplexity of each conditional distribution is some user-defined constant. Perplexity is a measure of how well a distribution predicts a sample – so this adjusts the variances of the Gaussians around each point so the remaining points fit each chosen Gaussian equally well in some sense. More succinctly, given prescribed perplexity , is chosen so this perplexity is achieved:
You can solve this via your favorite root-finding algorithm.
…and that’s how t-SNE works. Most tools that I know for data visualization serve other purposes too such as dimensionality reduction. t-SNE is different in that it seems purely suited for data visualization. Picking perplexity and interpreting the results can be a bit of an art, but it works very well.