Theoretical Foundations of t-SNE (t-Distributed Stochastic Neighbor Embedding)

t-Distributed Stochastic Neighbor Embedding (t-SNE) is a non-linear dimensionality reduction technique that has become a standard tool for visualizing high-dimensional data. Developed by Laurens van der Maaten and Geoffrey Hinton in 2008, t-SNE is particularly effective at revealing the structure of data by reducing its dimensions to two or three, which can then be easily visualized. This article explores the mathematical foundations of t-SNE, providing an in-depth understanding of how the algorithm works and why it is so effective.

1. Understanding the Problem

High-dimensional datasets are difficult to visualize. PCA provides a linear projection, while t-SNE emphasizes local probability neighborhoods through a non-linear map. That objective supports exploration but does not identify clusters or faithfully preserve global geometry.

2. Mathematical Formulation

t-SNE builds on the idea that similar points in high-dimensional space should remain close in the lower-dimensional representation, while dissimilar points should be far apart. This is achieved through the following steps:

2.1. Pairwise Similarities in High Dimensions

Given a high-dimensional dataset, t-SNE starts by converting the pairwise Euclidean distances between data points into conditional probabilities that represent similarities. For two data points $x_i$ and $x_j$, the similarity of $x_j$ to $x_i$ is given by:

$$P_{j|i} = \frac{\exp\left(-\|x_i - x_j\|^2 / 2\sigma_i^2\right)}{\sum_{k \neq i} \exp\left(-\|x_i - x_k\|^2 / 2\sigma_i^2\right)}$$

Where:

• $\|x_i - x_j\|^2$ is the squared Euclidean distance between points $x_i$ and $x_j$.
• $\sigma_i$ is a Gaussian kernel bandwidth parameter specific to point $x_i$.

The joint probability distribution for the pair $(x_i, x_j)$ is then defined as:

$$P_{ij} = \frac{P_{j|i} + P_{i|j}}{2n}$$

Where $n$ is the total number of points in the dataset.

2.2. Pairwise Similarities in Low Dimensions

In the lower-dimensional space, t-SNE aims to create a similar probability distribution for the points. For the low-dimensional counterparts $y_i$ and $y_j$ of the original points $x_i$ and $x_j$, the similarity is modeled using a Student's t-distribution with one degree of freedom (which has heavier tails than a Gaussian distribution):

$$Q_{ij} = \frac{\left(1 + \|y_i - y_j\|^2\right)^{-1}}{\sum_{k \neq l} \left(1 + \|y_k - y_l\|^2\right)^{-1}}$$

The use of the t-distribution instead of a Gaussian distribution helps t-SNE to place dissimilar points further apart in the lower-dimensional space, reducing the "crowding problem" common in dimensionality reduction.

2.3. Kullback-Leibler Divergence

To measure how well the lower-dimensional distribution $Q_{ij}$ matches the high-dimensional distribution $P_{ij}$, t-SNE uses the Kullback-Leibler (KL) divergence:

$$\text{KL}(P \| Q) = \sum_{i \neq j} P_{ij} \log \frac{P_{ij}}{Q_{ij}}$$

t-SNE attempts to minimize this divergence, adjusting the positions of the points in the low-dimensional space to make the two distributions as similar as possible.

2.4. Optimization

Minimizing the KL divergence is a non-convex optimization problem, typically solved using gradient descent. The gradients of the cost function with respect to the point positions $y_i$ are computed as follows:

$$\frac{\partial C}{\partial y_i} = 4 \sum_{j} \left(P_{ij} - Q_{ij}\right) \left(y_i - y_j\right) \left(1 + \|y_i - y_j\|^2\right)^{-1}$$

This gradient is used to iteratively update the positions of the points in the lower-dimensional space until the cost function converges.

3. Perplexity and Bandwidth

One of the key parameters in t-SNE is the perplexity, which influences the choice of the bandwidth $\sigma_i$ of the Gaussian kernels. The perplexity is a measure of the effective number of neighbors and is typically set between 5 and 50. It is defined as:

$$\text{Perplexity}(P_i) = 2^{H(P_i)}$$

Where $H(P_i)$ is the Shannon entropy of the conditional probability distribution $P_i$:

$$H(P_i) = - \sum_{j} P_{j|i} \log_2 P_{j|i}$$

The bandwidth $\sigma_i$ is adjusted iteratively so that the perplexity of $P_i$ matches the requested value. Perplexity is a smooth effective neighborhood size, not a literal fixed neighbor count, and perplexity must be smaller than the number of samples.

4. Computational Complexity

Exact t-SNE has $O(n^2)$ time and memory. Barnes-Hut t-SNE approximates repulsive forces and reduces time toward $O(n\log n)$ for low-dimensional outputs; it does not remove all memory and neighbor-search costs. In scikit-learn, method='barnes_hut' supports at most three output dimensions, while method='exact' is needed for four or more.

5. Best Practices for Using t-SNE

5.1. Parameter Tuning

Choosing the right parameters, especially perplexity, is crucial for getting meaningful results from t-SNE. It is advisable to experiment with different perplexity values and observe how they affect the visualization.

5.2. Data Preprocessing

Preprocessing the data by normalizing or standardizing it can significantly impact the results. It is essential to ensure that the data is appropriately scaled before applying t-SNE.

5.3. Interpretation of Results

Interpreting t-SNE plots requires caution. Distances between islands, relative positions, apparent density, and island size may be artifacts of perplexity, optimization, and the heavy-tailed output distribution. Check multiple seeds and perplexities and validate hypotheses in the original feature space.

5.4 Current scikit-learn API

In scikit-learn 1.9.1 the iteration parameter is max_iter (n_iter was renamed in 1.5), and the default learning rate is 'auto'. random_state makes a fixed configuration reproducible, but agreement across seeds and parameter choices is more informative than one repeatable map. The estimator exposes fit_transform only and has no transform method for unseen observations.

6. Conclusion

t-SNE is a powerful tool for visualizing high-dimensional data, enabling the discovery of patterns, clusters, and relationships that may not be apparent with other techniques. Its mathematical foundation, based on preserving local neighborhoods, makes it particularly effective for exploring the underlying structure of complex datasets. However, its computational demands and sensitivity to parameter settings require careful consideration and understanding to achieve optimal results.