Mastering t-SNE for Dimensionality Reduction in Machine Learning

Introduction to t-SNE

In the field of machine learning, we frequently encounter datasets with hundreds or thousands of features. Visualising such high-dimensional data is impossible for the human eye, necessitating dimensionality reduction. While linear techniques like Principal Component Analysis (PCA) are useful for preserving global variance, they often fail to capture complex, non-linear structures. This is where t-Distributed Stochastic Neighbour Embedding (t-SNE) excels.

t-SNE is a non-linear manifold learning technique that excels at preserving local structure, ensuring that points close together in high-dimensional space remain close in a 2D or 3D projection. For your university exams, understanding t-SNE is vital because it represents a shift from global variance preservation to local neighbourhood preservation, a core concept in modern unsupervised learning.

The Mathematical Foundation: Probability Distributions

t-SNE converts Euclidean distances between points in high-dimensional space into conditional probabilities that represent similarities. For a point $x_i$, the probability $p_{j|i}$ that $x_i$ would pick $x_j$ as its neighbour is given by a Gaussian distribution:

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

Here, $\sigma_i$ is the variance of the Gaussian centred at $x_i$. In the low-dimensional space, we use a Student t-distribution with one degree of freedom to model similarities $q_{ij}$, which helps alleviate the crowding problem by having heavier tails than the Gaussian distribution.

Worked Example 1: Calculating Similarity

Consider three points in 1D space: $x_1=0, x_2=1, x_3=5$. Let $\sigma=1$. We calculate the similarity $p_{2|1}$ (the probability that $x_1$ chooses $x_2$):

1. Calculate squared distances: $d_{12}^2 = (0-1)^2 = 1$, $d_{13}^2 = (0-5)^2 = 25$.
2. Calculate unnormalised similarities: $w_{12} = \exp(-1/2) \approx 0.606$, $w_{13} = \exp(-25/2) \approx 0.0000037$.
3. Normalise: $p_{2|1} = 0.606 / (0.606 + 0.0000037) \approx 0.999$.

This shows that $x_1$ has a very high probability of selecting $x_2$ as its neighbour, effectively capturing the local structure.

The Role of Perplexity

Perplexity is a hyperparameter that balances attention between local and global aspects of the data. It can be interpreted as a smooth measure of the effective number of neighbours. Mathematically, it is defined as $2^{H(P_i)}$, where $H(P_i)$ is the Shannon entropy of the distribution $P_i$. A typical range for perplexity is 5 to 50. If the perplexity is too low, the algorithm focuses only on very local clusters; if too high, it may merge distinct clusters into a single blob.

Worked Example 2: Cost Function Minimisation

t-SNE minimises the Kullback-Leibler (KL) divergence between the high-dimensional distribution $P$ and the low-dimensional distribution $Q$:

$$C = KL(P||Q) = \sum_i \sum_j p_{ij} \log \frac{p_{ij}}{q_{ij}}$$

Suppose we have a simple case where $p_{12} = 0.8$ and $q_{12} = 0.4$. The contribution to the cost is $0.8 \log(0.8/0.4) = 0.8 \log(2) \approx 0.554$. The gradient descent process adjusts the positions of $y_i$ in the low-dimensional space to make $q_{ij}$ closer to $p_{ij}$, thereby reducing the cost.

Common Mistakes

1. Interpreting Distances: Do not assume that the distance between clusters in a t-SNE plot represents the true distance in high-dimensional space. t-SNE prioritises local structure over global distances.
2. Ignoring Hyperparameters: Failing to tune perplexity can lead to misleading visualisations. Always test multiple values.
3. Computational Cost: t-SNE is computationally expensive ($O(n^2)$ or $O(n \log n)$). Do not run it on massive datasets without first using PCA to reduce dimensions.
4. Stochastic Nature: t-SNE is non-deterministic. Running it twice with different random seeds will yield different results.

FAQ

Is t-SNE a linear dimensionality reduction technique? No, it is a non-linear manifold learning technique.

Why use the t-distribution in the low-dimensional space? It has heavier tails than the Gaussian distribution, which helps prevent the 'crowding problem' where points get squashed together in the centre.

Can t-SNE be used for feature selection? No, it is a projection technique, not a feature selection method. It creates new coordinates rather than selecting existing features.

Conclusion

t-SNE is an essential tool for any machine learning practitioner, providing deep insights into the structure of complex datasets. To see these concepts in action with interactive visualisations, generate a free animated lesson on this topic at MathInstructor AI.