Prepare Data

tsne first removes each row of the input data X that contains any NaN values. Then, if the Standardize name-value pair is true, tsne centers X by subtracting the mean of each column, and scales X by dividing its columns by their standard deviations.

The original authors van der Maaten and Hinton [1] recommend reducing the original data X to a lower-dimensional version using Principal Component Analysis (PCA). You can set the tsne NumPCAComponents name-value pair to the number of dimensions you like, perhaps 50. To exercise more control over this step, preprocess the data using the pca function.

Compute Distances, Gaussian Variances, and Similarities

After the preprocessing, tsne calculates the distance d(x_i,x_j) between each pair of points x_i and x_j in X. You can choose various distance metrics using the Distance name-value pair. By default, tsne uses the standard Euclidean metric. tsne uses the square of the distance metric in its subsequent calculations.

Then for each row i of X, tsne calculates a standard deviation σ_i so that the perplexity of row i is equal to the Perplexity name-value pair. The perplexity is defined in terms of a model Gaussian distribution as follows. As van der Maaten and Hinton [1] describe, “The similarity of data point x_j to data point 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. For nearby data points, $$p_{j|i}$$ is relatively high, whereas for widely separated data points, $$p_{j|i}$$ will be almost infinitesimal (for reasonable values of the variance of the Gaussian, σ_i).”

Define the conditional probability of j given i as

Then define the joint probability p_ij by symmetrizing the conditional probabilities:

where N is the number of rows of X.

The distributions still do not have their standard deviations σ_i defined in terms of the Perplexity name-value pair. Let P_i represents the conditional probability distribution over all other data points given data point x_i. The perplexity of the distribution is

where H(P_i) is the Shannon entropy of P_i:

The perplexity measures the effective number of neighbors of point i. tsne performs a binary search over the σ_i to achieve a fixed perplexity for each point i.

Initialize the Embedding and Divergence

To embed the points in X into a low-dimensional space, tsne performs an optimization. tsne attempts to minimize the Kullback-Leibler divergence between the model Gaussian distribution of the points in X and a Student t distribution of points Y in the low-dimensional space.

The minimization procedure begins with an initial set of points Y. tsne create the points by default as random Gaussian-distributed points. You can also create these points yourself and include them in the 'InitialY' name-value pair for tsne. tsne then calculates the similarities between each pair of points in Y.

The probability model q_ij of the distribution of the distances between points y_i and y_j is

Using this definition and the model of distances in X given by Equation 1, the Kullback-Leibler divergence between the joint distribution P and Q is

For consequences of this definition, see Helpful Nonlinear Distortion.

Gradient Descent of Kullback-Leibler Divergence

To minimize the Kullback-Leibler divergence, the 'exact' algorithm uses a modified gradient descent procedure. The gradient with respect to the points in Y of the divergence is

where the normalization term

The modified gradient descent algorithm uses a few tuning parameters to attempt to reach a good local minimum.

Cannot Use Embedding to Classify New Data

Because t-SNE often separates data clusters well, it can seem that t-SNE can classify new data points. However, t-SNE cannot classify new points. The t-SNE embedding is a nonlinear map that is data-dependent. To embed a new point in the low-dimensional space, you cannot use the previous embedding as a map. Instead, run the entire algorithm again.

Performance Depends on Data Sizes and Algorithm

t-SNE can take a good deal of time to process data. If you have N data points in D dimensions that you want to map to Y dimensions, then

So for large data sets, where N is greater than 1000 or so, and where the embedding dimension Y is 2 or 3, the Barnes-Hut algorithm can be faster than the exact algorithm.

Helpful Nonlinear Distortion

T-SNE maps high-dimensional distances to distorted low-dimensional analogues. Because of the fatter tail of the Student t distribution in the low-dimensional space, tsne often moves close points closer together, and moves far points farther apart than in the high-dimensional space, as illustrated in the following figure. The figure shows both Gaussian and Student t distributions at the points where the densities are at 0.25 and 0.025. The Gaussian density relates to high-dimensional distances, and the t density relates to low-dimensional distances. The t density corresponds to close points being closer, and far points being farther, compared to the Gaussian density.

t = linspace(0,5);
y1 = normpdf(t,0,1);
y2 = tpdf(t,1);
plot(t,y1,'k',t,y2,'r')
hold on
x1 = fzero(@(x)normpdf(x,0,1)-0.25,[0,2]);
x2 = fzero(@(x)tpdf(x,1)-0.25,[0,2]);
z1 = fzero(@(x)normpdf(x,0,1)-0.025,[0,5]);
z2 = fzero(@(x)tpdf(x,1)-0.025,[0,5]);
plot([0,x1],[0.25,0.25],'k-.')
plot([0,z2],[0.025,0.025],'k-.')
plot([x1,x1],[0,0.25],'g-',[x2,x2],[0,0.25],'g-')
plot([z1,z1],[0,0.025],'g-',[z2,z2],[0,0.025],'g-')
text(1.1,.25,'Close points are closer in low-D')
text(2.4,.05,'Far points are farther in low-D')
legend('Gaussian(0,1)','Student t (df = 1)')
xlabel('x')
ylabel('Density')
title('Density of Gaussian(0,1) and Student t (df = 1)')
hold off

This distortion is helpful when it applies. It does not apply in cases such as when the Gaussian variance is high, which lowers the Gaussian peak and flattens the distribution. In such a case, tsne can move close points farther apart than in the original space. To achieve a helpful distortion,

If you can achieve this range of variances, then the diagram applies, and the tsne distortion is helpful.

For effective ways to tune tsne, see Wattenberg, Viégas and Johnson [4].