T-SNE Explained with Example

t-Distributed Stochastic Neighbour Embedding (t-SNE)

Photo by metropolitanmuseum on Unsplash

⬅️ Previous: [Demystifying Principal Component Analysis]

t-SNE

t-Distributed Stochastic Neighbour Embedding is a statistical method for visualizing high-dimensional data by reducing it to lower-dimensional spaces (or, simply, a Dimensionality Reduction Technique), typically two or three dimensions. This makes it easier to visualize and interpret the data, especially when dealing with complex datasets like those in machine learning and data science.

Visualizing the MNIST dataset from 784 dimensions to 2 dimensions

Why learn t-SNE, when we already have PCA?

Because

• PCA is a simple Dimensionality reduction technique and only applies to linear datasets. It performs very badly on non-linear datasets, like the Swiss Roll dataset example below. But, t-SNE can work on all kinds of datasets.

PCA causes overlapping when visualizing the Swiss Roll dataset from 3D to 2D

• t-SNE graphs are better at visualization because they are beautiful and easy to interpret.

MNIST dataset can be better visualized with t-SNE

Mathematical Formulation

t-SNE preserves the local structure of the data instead of the global structure. It calculates pairwise similarities for all points. We cannot use distance as similarity score due to the curse of dimensionality. It calculates the similarity score for a point x by plotting a Gaussian distribution with mean=0 (which is where x lies in the distribution) and standard deviation = density near the point x. The similarity score (probability that x believes x_1 is its neighbour) will be the probability density of point x_i on the Gaussian distribution. This provides the pairwise similarity matrix for high dimension.

NOTE: The similarity score between two points a and b is not the same as between b and a because the probability density of a is not equal to the probability density of b.

Randomly place all points in lower dimensions, then calculate similarity scores using the above methods. This will also give the pairwise similarity matrix for lower dimensions.

Since the pairwise similarity matrix contains the local structure of the entire dataset. We move a point x in the lower dimension such that the similarity score in lower dimensions tends towards the similarity score in higher dimensions.

We repeat this until the two pairwise similarity matrices look similar.

NOTE: Different runs of t-SNE can result in different results because of the random initialization of Pairwise similarity matrix.

Here, probability is calculated by normalizing the PDF of the normal distribution. Then probabilities are symmetrized so that the probability of a given b equals the probability of b given a. Also, it is divided by N to normalize the values of the whole similarity score matrix.

For low-dimensional similarities, we use t-distribution instead of normal distribution to calculate similarities or probabilities.

The two similarity score matrices above follow a joint probability distribution that is why we use KL Divergence to calculate cost function as KL Divergence also uses a joint probability distribution. We then optimize the cost function using gradient descent.

# Example 1:

from sklearn.datasets import make_swiss_roll
from sklearn.datasets import fetch_openml
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
import plotly.express as px
import pandas as pd
import numpy as np

# Load MNIST dataset
mnist = fetch_openml('mnist_784', version=1)
X = mnist.data / 255.0
y = mnist.target

print(X.shape) # (70000, 784)
print(y.shape) # (70000, )

# max_iter is the max iteration for gradient descent
tsne = TSNE(n_components=2, perplexity=30, max_iter=1000, random_state=42)
X_tsne = tsne.fit_transform(X)

# tsne.embedding_
# tsne.kl_divergence_
# tsne.learning_rate_
# tsne.n_iter_

# Plot the result
plt.figure(figsize=(12, 8))
scatter = plt.scatter(X_tsne[:, 0], X_tsne[:, 1], c=y.astype(int), cmap='tab10', s=1)
plt.legend(*scatter.legend_elements(), title="Digits")
plt.title('t-SNE of MNIST')
plt.show()

Some Questions!

Q1. Why use probabilities instead of distances to calculate similarity?

Answer. Relying on raw absolute distances is problematic in high-dimensional datasets because of the curse of dimensionality and varying data densities.

• Scale Invariance: Absolute distances lose their meaning across different datasets or even within different regions of the same dataset. Converting distances into conditional probabilities normalizes them, ensuring all similarities scale between 0 and 1.
• Relative Relationships: Probabilities allow the algorithm to focus on relative similarity. Instead of asking “how many units apart are these points?”, it asks, “given all the points around point xi, how likely is it to pick point xj as its neighbour?”

Q2. Why use a Gaussian distribution to calculate similarity in high
dimensions?

Answer.

• Differentiable
• Converts distance to probability as output.
• Control of density with the variance parameter
• Exponential Decay: In a Gaussian distribution, the probability drops off exponentially as the distance increases.
• Ignoring Global Structure: By centering a Gaussian over a data point, its nearest neighbours receive a high similarity score, while points even a moderate distance away receive a score infinitesimally close to zero. This allows t-SNE to focus strictly on modeling local neighbourhoods and essentially ignore the meaningless distances between distant clusters.

Q3. How is variance calculated for each Gaussian distribution?

Get Mr. Vivek Kumar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Answer. The variance (σ²i) is not a fixed, global value. It is calculated dynamically for every single data point xi based on the local density of its neighbourhood.

• The Perplexity Parameter: The user provides a hyperparameter called perplexity, which can be thought of as the target number of effective nearest neighbours for each point.
• Density Adaptation: In dense regions, points are packed closely together, so the algorithm assigns a small variance (narrow Gaussian). In sparse regions, points are far apart, so it assigns a larger variance (wide Gaussian).
• Binary Search: The algorithm performs a binary search to find the exact variance σ²i for point xi that makes the Shannon entropy of its probability distribution perfectly match the user-defined perplexity.

NOTE: low σ means low entropy and low perplexity and high σ means high entropy and high perplexity.

Q4. Why use a t-distribution in lower dimensions?

Answer. The Student’s t-distribution is the solution to the crowding problem.

• Volume Mismatch: A high-dimensional space has exponentially more “room” than a 2D or 3D space. When you squash high-dimensional data down to 2D, there simply isn’t enough surface area to accommodate all the points at their original relative distances. If you mapped them directly, points would crush together in the center of the map, collapsing your distinct clusters.
• Heavier Tails: The Student’s t-distribution (specifically with one degree of freedom, also known as a Cauchy distribution) has “heavier tails” than a Gaussian.
• Pushing Clusters Apart: Because of these heavy tails, a point must be placed much further away in the low-dimensional space to represent a moderate distance in the high-dimensional space. This effectively acts like a repulsive force between distinct clusters, giving them the breathing room needed to remain separate and visually distinct on your 2D plot.

Hyperparameters

1. Perplexity:
   • Perplexity is perhaps the most important hyperparameter in t-SNE. It can be thought of as a measure of the effective number of neighbours for each point.
   • The value of perplexity affects the balance between local and global aspects of your data. A small perplexity emphasizes local structure, while a larger perplexity brings more of the global structure into play.
   • Typical values for perplexity range between 5 and 50, but this can vary depending on the dataset. It’s often recommended to experiment with different values to see how they affect the results.

# Generate a 3D Swiss Roll dataset
X, color = make_swiss_roll(n_samples=1000)

# Perplexity values to try
perplexities = [5, 10, 25, 50, 100]

# Prepare the plot grid
fig, axes = plt.subplots(2, 3, figsize=(15, 10))
axes = axes.flatten()

# Apply t-SNE with different perplexity values and plot
for i, perplexity in enumerate(perplexities):
    tsne = TSNE(n_components=2, perplexity=perplexity, random_state=42, learning_rate='auto')
    X_tsne = tsne.fit_transform(X)

    ax = axes[i]
    scatter = ax.scatter(X_tsne[:, 0], X_tsne[:, 1], c=color, cmap='jet', s=10)
    ax.set_title(f't-SNE with Perplexity = {perplexity}')
    ax.axis('off')

# Remove the empty subplot (if any)
for i in range(len(perplexities), len(axes)):
    fig.delaxes(axes[i])

plt.tight_layout()
plt.show()

2. Number of Iterations:
• This hyperparameter controls how many iterations the algorithm runs before it terminates.
• If the number is too low, the algorithm might not fully converge. If it’s too high, you might waste computational resources without gaining much in terms of the quality of the embedding.
• The default number of iterations is often set to a value like 1000, but this might need to be increased for larger datasets.

# Generate a 3D Swiss Roll dataset
X, color = make_swiss_roll(n_samples=1000)

# Perplexity value
perplexity = 50

# Different max_iter values to try
max_iter_values = [250, 500, 1000, 5000]

# Prepare the plot grid
fig, axes = plt.subplots(2, 2, figsize=(15, 10))
axes = axes.flatten()

# Apply t-SNE with different max_iter values and plot
for i, max_iter in enumerate(max_iter_values):
    tsne = TSNE(n_components=2, perplexity=perplexity, max_iter=max_iter, random_state=42)
    X_tsne = tsne.fit_transform(X)

    ax = axes[i]
    scatter = ax.scatter(X_tsne[:, 0], X_tsne[:, 1], c=color, cmap='jet', s=10)
    ax.set_title(f't-SNE with max_iter = {max_iter}')
    ax.axis('off')

# Remove the empty subplot (if any)
for i in range(len(max_iter_values), len(axes)):
    fig.delaxes(axes[i])

plt.tight_layout()
plt.show()

3. Learning Rate:
• The learning rate determines the step size at each iteration while moving toward a minimum of the cost function.
• A too high learning rate might cause the algorithm to oscillate and miss the global minimum, while a too low learning rate can result in a long training process that might get stuck in a local minimum.
• Common values for the learning rate are between 10 and 1000. Again, experimenting with different values is key to finding the best setting for a given dataset.

# Generate a 3D Swiss Roll dataset
X, color = make_swiss_roll(n_samples=1000)

# Perplexity value
perplexity = 50

# Different max_iter values to try
lr_values = [10, 50, 100, 1000]

# Prepare the plot grid
fig, axes = plt.subplots(2, 2, figsize=(15, 10))
axes = axes.flatten()

# Apply t-SNE with different max_iter values and plot
for i, lr in enumerate(lr_values):
    tsne = TSNE(n_components=2, perplexity=perplexity, max_iter=5000, learning_rate=lr, random_state=42)
    X_tsne = tsne.fit_transform(X)

    ax = axes[i]
    scatter = ax.scatter(X_tsne[:, 0], X_tsne[:, 1], c=color, cmap='jet', s=10)
    ax.set_title(f't-SNE with learning rate = {lr}')
    ax.axis('off')

# Remove the empty subplot (if any)
for i in range(len(lr_values), len(axes)):
    fig.delaxes(axes[i])

plt.tight_layout()
plt.show()

Points of Wisdom

1. Interpreting Clusters: t-SNE can reveal clusters and local structures very effectively. However, the distance between clusters or the relative position of clusters in the plot may not have a meaningful interpretation. Avoid over-interpreting global relationships.
2. Axes have no meaning: Axes in t-SNE have no interpretable meaning. Thus, they cannot be used to train ML models, unlike what we can do after applying PCA.
3. Perplexity Matters: Perplexity is a crucial hyperparameter in t-SNE. It roughly corresponds to the number of effective nearest neighbours. There’s no one-size-fits-all value; different values can reveal different structures, so experiment with a range of values. Common values are between 5 and 50.
4. Reproducibility: t-SNE starts with a random initialization, leading to different results each time you run it. If reproducibility is important, set a random seed. Also, multiple runs with different initializations can give a fuller picture of your data’s structure.
5. Scaling the Data: Pre-processing steps like scaling or normalizing your data, especially if features are on different scales, can have a significant impact on the results of t-SNE.
6. Curse of Dimensionality: t-SNE can mitigate but not completely overcome the curse of dimensionality. Very high-dimensional data might require other steps, like initial dimensionality reduction with PCA, before applying t-SNE.
7. Learning Rate and Number of Iterations: Beyond perplexity, other parameters like the learning rate and the number of iterations also impact the results. A learning rate that’s too high or too low can lead to poor embeddings, and insufficient iterations might mean the algorithm doesn’t fully converge.
8. It’s Not a Silver Bullet: While t-SNE is a powerful tool, it’s not suitable for every kind of dataset or analysis. Sometimes other dimensionality reduction techniques like PCA, UMAP, or MDS might be more appropriate.

Advantages

• If done correctly, can give very intuitive visualizations as it preserves the local structure of the data in the lower dimensions

Disadvantages

• Computationally Expensive
• Not very good at preserving global structure
• Sensitive to hyperparameters
• Can get stuck in local minima
• Interpretation is challenging

Research Paper

1. Blog 1 — https://distill.pub/2016/misread-tsne/
2. Research Paper — https://www.jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf
3. Blog 2 — https://colah.github.io/posts/2014-10-Visualizing-MNIST

If you found value in this content, I invite you to stay connected for more insightful posts. Your time and interest are greatly appreciated. Thank you for reading!