An Analysis of the t-SNE Algorithm for Data Visualization

Abstract

A first line of attack in exploratory data analysis is data visualization, i.e., generating a 2-dimensional representation of data that makes clusters of similar points visually identifiable. Standard Johnson-Lindenstrauss dimensionality reduction does not produce data visualizations. The t-SNE heuristic of van der Maaten and Hinton, which is based on non-convex optimization, has become the de facto standard for visualization in a wide range of applications. This work gives a formal framework for the problem of data visualization - finding a 2-dimensional embedding of clusterable data that correctly separates individual clusters to make them visually identifiable. We then give a rigorous analysis of the performance of t-SNE under a natural, deterministic condition on the "ground-truth" clusters (similar to conditions assumed in earlier analyses of clustering) in the underlying data. These are the first provable guarantees on t-SNE for constructing good data visualizations. We show that our deterministic condition is satisfied by considerably general probabilistic generative models for clusterable data such as mixtures of well-separated log-concave distributions. Finally, we give theoretical evidence that t-SNE provably succeeds in partially recovering cluster structure even when the above deterministic condition is not met.

In Conference on Learning Theory (COLT) 2018

References in corpus (7)

• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Polynomial Learning of Distribution Families
• Learning mixtures of separated nonspherical Gaussians
• Better Agnostic Clustering Via Relaxed Tensor Norms
• Learning Mixtures of Gaussians in High Dimensions
• Stochastic Neighbor Embedding separates well-separated clusters
• Mixture Models, Robustness, and Sum of Squares Proofs

Cited by in corpus (11)

• Theoretical Foundations of t-SNE for Visualizing High-Dimensional Clustered Data
• Revisiting Dimensionality Reduction Techniques for Visual Cluster Analysis: An Empirical Study
• Authentication and integrity of smartphone videos through multimedia container structure analysis
• Manifold Learning in Atomistic Simulations: A Conceptual Review
• t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data
• Improving the Effectiveness and Efficiency of Stochastic Neighbour Embedding with Isolation Kernel
• A Probabilistic Graph Coupling View of Dimension Reduction
• T-SNE Is Not Optimized to Reveal Clusters in Data
• Reconstruction of manifold embeddings into Euclidean spaces via intrinsic distances
• bigMap: Big Data Mapping with Parallelized t-SNE
• CO-SNE: Dimensionality Reduction and Visualization for Hyperbolic Data