Understanding t-SNE: Objectives, Uses, and Limitations

Introduction

In our previous lessons on unsupervised learning, we have explored methods for discovering latent structure in data. We began with clustering algorithms like K-means and Gaussian Mixture Models to group similar data points. We then derived the Expectation-Maximization algorithm as a general framework for fitting models with latent variables. Most recently, we examined Principal Component Analysis (PCA) as a linear method for dimensionality reduction, which works by finding orthogonal axes that capture the maximum global variance in the data.

However, what if our primary goal is not just to reduce dimensions, but to visualize the data's structure? While PCA is excellent at preserving global variance, it often fails to capture the intricate, non-linear relationships and local neighborhood structures that define clusters in high-dimensional space. This lesson introduces a powerful non-linear technique designed specifically for this purpose: t-Distributed Stochastic Neighbor Embedding (t-SNE). You will learn the objective of t-SNE, the clever probabilistic reasoning behind its design, its most effective applications, and—critically—its significant limitations and common misinterpretations.

The Objective: Preserving Neighborhoods, Not Distances

The central objective of t-SNE is fundamentally different from that of PCA. Instead of preserving large pairwise distances and global variance, t-SNE aims to create a low-dimensional embedding (typically 2D or 3D) where the neighborhood identity of each point is preserved. That is, if point A is a close neighbor of point B in the original high-dimensional space, their corresponding points in the low-dimensional map should also be close neighbors.

To achieve this, t-SNE models pairwise similarities as probability distributions. The algorithm's goal is to minimize the difference between the probability distribution of similarities in the high-dimensional space and the corresponding distribution in the low-dimensional map.

This process involves three conceptual stages:

1. Measure similarity in high-dimensional space: Convert the high-dimensional Euclidean distances between data points into conditional probabilities that represent similarities.
2. Measure similarity in low-dimensional space: Define a similar probability distribution for the points in the low-dimensional map.
3. Minimize the divergence: Adjust the positions of the points in the map to minimize the Kullback-Leibler (KL) divergence between the two distributions.

Let's explore the theoretical underpinnings of each stage.

Stage 1: Similarities in High-Dimensional Space

First, we need a way to quantify the similarity between two points, $x_i$ and $x_j$, in the original high-dimensional space. t-SNE does this by centering a Gaussian distribution on each point $x_i$ and measuring the density of all other points under that Gaussian. The similarity of $x_j$ to $x_i$ is then defined as the conditional probability $p_{j|i}$ that $x_i$ would pick $x_j$ as its neighbor, assuming neighbors are picked in proportion to their probability density under this Gaussian.

Mathematically, this conditional probability is given by:

$$p_{j|i}=\frac{\exp (-\Vert x_i-x_j{\Vert }^2/2{\sigma }_i^2)}{{\sum }_{k\ne i}\exp (-\Vert x_i-x_k{\Vert }^2/2{\sigma }_i^2)}$$

Here, ${\sigma }_i$ is the variance of the Gaussian centered on data point $x_i$. A crucial aspect of the algorithm is that ${\sigma }_i$ is not fixed. It is determined individually for each data point via a search process. This is controlled by a hyperparameter called perplexity, which can be loosely interpreted as the effective number of neighbors for each point. For denser regions of the data space, a smaller ${\sigma }_i$ is used; for sparser regions, a larger ${\sigma }_i$ is used. This allows the model to adapt to the local density of the data.

Since we are interested in a joint probability distribution over pairs, we define the high-dimensional similarity $p_{ij}$ by symmetrizing the conditional probabilities:

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

where $n$ is the number of data points. This gives us a probability distribution $P$ over all pairs of points, representing the local structure we wish to preserve.

For a clear and concise walkthrough of this process, the following video is highly recommended.

Stage 2: The Crowding Problem and the Student's t-Distribution

Now that we have the target similarities $p_{ij}$, a natural next step might be to define the low-dimensional similarities $q_{ij}$ using a Gaussian as well. However, this leads to a significant issue known as the "crowding problem".

The volume of space available in high dimensions is vastly larger than in low dimensions. For instance, the ratio of the volume of a hypersphere of radius 2 to a hypersphere of radius 1 grows exponentially with the number of dimensions. This means that a set of points that are moderately separated in a high-dimensional space has much more "room" than can be provided in a 2D or 3D map. When we try to project them down while preserving local distances, these moderately distant points get squeezed together, creating a single, crowded clump in the center of the map.

t-SNE's clever solution is to use a different, heavy-tailed probability distribution in the low-dimensional space: the Student's t-distribution with one degree of freedom (also known as the Cauchy distribution). Its probability density falls off much more slowly than a Gaussian's.

The low-dimensional similarities $q_{ij}$ are defined as:

$$q_{ij}=\frac{(1+\Vert y_i-y_j{\Vert }^2{)}^{-1}}{{\sum }_{k\ne l}(1+\Vert y_k-y_l{\Vert }^2{)}^{-1}}$$

where $y_i$ and $y_j$ are the coordinates of the points in the low-dimensional map.

The use of this heavy-tailed distribution means that to achieve a small similarity value $q_{ij}$, the points $y_i$ and $y_j$ must be placed much farther apart than would be required with a Gaussian. This creates more space in the low-dimensional map, allowing dissimilar points to be pushed far apart and alleviating the crowding problem.

The original inventor of t-SNE, Laurens van der Maaten, explains this core concept brilliantly in his talk at Google.

Stage 3: Optimization via KL Divergence

We now have two probability distributions: $P$, representing similarities in the high-D space, and $Q$, representing similarities in the low-D map. The final objective is to arrange the points $y_i$ in the map such that $Q$ is as similar to $P$ as possible.

As we saw in our lesson on the EM algorithm, a natural way to measure the dissimilarity between two probability distributions is the Kullback-Leibler (KL) divergence. t-SNE's cost function is the sum of KL divergences over all points:

$$C=\text{KL}(P||Q)=\sum _i\sum _j{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$$

The algorithm then uses gradient descent to find the locations $y_i$ that minimize this cost function. The gradient for each point $y_i$ has a surprisingly elegant form:

$$\frac{\partial C}{\partial y_i}=4\sum _j(p_{ij}-q_{ij})(y_i-y_j)(1+\Vert y_i-y_j{\Vert }^2{)}^{-1}$$

This can be interpreted as the net force on point $y_i$ from a system of "springs" connecting it to all other points.

• If $p_{ij}>q_{ij}$, the points are farther apart in the map than they should be, creating an attractive force.
• If $p_{ij}<q_{ij}$, the points are closer in the map than they should be, creating a repulsive force.

The algorithm starts with a random arrangement of points $y_i$ and iteratively moves them according to these forces until they settle into a stable configuration that minimizes the KL divergence.

For a comprehensive theoretical explanation, I encourage you to read the original paper that introduced t-SNE. Given your background, the direct derivation will be very insightful.

Primary Use Cases and Critical Limitations

Understanding when and how to use t-SNE is as important as understanding how it works.

Use Cases

t-SNE is primarily a tool for exploratory data analysis and visualization. Its ability to reveal non-linear structures makes it invaluable in many fields:

• Machine Learning: Visualizing high-dimensional feature spaces from neural networks (e.g., word embeddings like Word2Vec, or image features from CNNs) to understand what the model has learned.
• Genomics: Visualizing gene expression data to identify distinct cell types from single-cell RNA sequencing.
• Cybersecurity: Visualizing network traffic data to spot anomalous patterns.
• General Data Science: Getting an initial feel for the cluster structure of a high-dimensional dataset before applying formal clustering algorithms.

Limitations and Common Pitfalls

t-SNE is powerful but frequently misinterpreted. You must be aware of its limitations:

1. It is a visualization tool, not a clustering algorithm. While t-SNE displays clusters, it can sometimes create the illusion of clusters where none exist. The output is a projection, not a definitive partitioning of the data.
2. The global geometry is not preserved. The relative sizes of clusters and the distances between clusters in a t-SNE plot are not meaningful. A large gap between two clusters does not imply they are "more separate" than two clusters with a smaller gap. The algorithm's optimization process can arbitrarily expand or contract these distances.
3. It is computationally expensive. The exact algorithm has a time complexity of $O(N^2)$. For larger datasets, approximations like Barnes-Hut t-SNE are used, reducing complexity to $O(N\log N)$. This is a direct parallel to the n-body problem in physics and astrophysics, where similar tree-based approximations are used to calculate gravitational forces.
4. It is stochastic and sensitive to hyperparameters. Due to its non-convex cost function and random initialization, different runs of t-SNE can produce different-looking plots. It is crucial to set a random_state for reproducibility and experiment with the perplexity parameter, which strongly influences the visualization.
5. t-SNE does not provide an explicit mapping for new data. Unlike PCA, you cannot easily project new, out-of-sample data points into an existing t-SNE embedding. It computes an embedding for a fixed dataset.

The following resources provide excellent discussions on these practical aspects.

Conclusion

In this lesson, we have delved into the theory and practice of t-SNE, a cornerstone of modern data visualization. We've seen that its primary objective is to preserve local neighborhood structures from a high-dimensional space in a low-dimensional map.

Key takeaways include:

• Probabilistic Similarities: t-SNE's core innovation is converting Euclidean distances into probability distributions representing pairwise similarities.
• The Crowding Problem: A fundamental challenge of dimensionality reduction, which t-SNE solves by using a heavy-tailed Student's t-distribution for the low-dimensional map.
• KL Divergence: The objective function minimizes the KL divergence between the high-dimensional and low-dimensional similarity distributions, iteratively arranging the map points using gradient descent.
• Interpret with Caution: t-SNE is a powerful exploratory tool, but the resulting visualizations must be interpreted carefully. Cluster sizes and inter-cluster distances are not meaningful, and the algorithm should not be used for tasks other than visualization.

This lesson concludes our module on unsupervised learning. We have covered key techniques for clustering, density estimation, and dimensionality reduction. We are now prepared to transition into the world of supervised learning with a specific focus on the models that power modern AI: neural networks.

In the next lesson, we will begin our study of deep learning by examining its most fundamental building block: the perceptron. We will describe its simple mathematical model and demonstrate its historical limitation to linearly separable problems, setting the stage for the development of more powerful, multi-layered networks.