57  t-SNE, UMAP, and Non-Linear Dimensionality Reduction

High-dimensional spaces pose visualization and computational challenges. Linear techniques like PCA project data onto variance-maximizing orthogonal axes (Jolliffe 2002). However, non-linear manifolds require methods preserving local topological relationships (Maaten and Hinton 2008; McInnes et al. 2018).

1 t-SNE (t-Distributed Stochastic Neighbor Embedding)

t-SNE models high-dimensional pairwise conditional similarities via Gaussian distributions and low-dimensional similarities via heavy-tailed Student-\(t\) distributions (Maaten and Hinton 2008).

High-dimensional conditional similarity:

\[ p_{j|i} = \frac{\exp\left(-\|\mathbf{x}_i-\mathbf{x}_j\|^2/(2\sigma_i^2)\right)}{\sum_{k\neq i}\exp\left(-\|\mathbf{x}_i-\mathbf{x}_k\|^2/(2\sigma_i^2)\right)} \tag{1}\]

Symmetric joint probability: \(p_{ij} = (p_{j|i}+p_{i|j})/(2n)\).

Low-dimensional Student-\(t\) Cauchy similarity:

\[ q_{ij} = \frac{(1+\|\mathbf{y}_i-\mathbf{y}_j\|^2)^{-1}}{\sum_{k\neq l}(1+\|\mathbf{y}_k-\mathbf{y}_l\|^2)^{-1}} \tag{2}\]

Kullback-Leibler divergence objective:

\[ C = \text{KL}(P\|Q) = \sum_{i\neq j} p_{ij}\log\frac{p_{ij}}{q_{ij}} \tag{3}\]

t-SNE: Effect of Perplexity
Simulate how perplexity influences neighborhood distribution and cluster separation

Perplexity = 30

Clusters in data = 3

2 UMAP (Uniform Manifold Approximation and Projection)

UMAP preserves local and global manifold structure via fuzzy simplicial sets (McInnes et al. 2018):

\[ v_{j|i} = \exp\left(-\frac{d(\mathbf{x}_i,\mathbf{x}_j)-\rho_i}{\sigma_i}\right) \tag{4}\]

3 Summary

t-SNE and UMAP compress high-dimensional feature spaces for low-dimensional non-linear visualization. UMAP preserves global topological relationships better and scales computationally to large datasets (Maaten and Hinton 2008; McInnes et al. 2018).

4 References

Jolliffe, Ian T. 2002. Principal Component Analysis. 2nd ed. Springer.

Maaten, Laurens van der, and Geoffrey Hinton. 2008. “Visualizing Data Using t-SNE.” Journal of Machine Learning Research 9: 2579–605.

McInnes, Leland, John Healy, and James Melville. 2018. “UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction.” arXiv Preprint arXiv:1802.03426.