Source-linked AI summary
Barnes-Hut-SNE
Laurens van der Maaten
TL;DR
t-SNE visualization is limited by quadratic computation and memory costs. The paper introduces Barnes-Hut-SNE, combining sparse similarity approximation with Barnes-Hut force approximation, and reports substantially faster embeddings that scale to millions of objects, while noting important scope limitations.
Problem
t-SNE commonly supports low-dimensional visualization, but its O(N^2) computation and memory complexity limits practical use to data sets with only a few thousand objects.
Method
Barnes-Hut-SNE uses vantage-point or metric trees for sparse input similarities and a Barnes-Hut approximation for embedding forces, requiring O(N log N) computation and O(N) memory.
Results
Barnes-Hut-SNE is orders of magnitude faster than standard t-SNE with negligible nearest-neighbor-error differences, including a 70,000-image MNIST embedding completed in 645 seconds at θ=0.5.
Takeaways & Limitations
Barnes-Hut-SNE makes it practical to visualize data sets with millions of objects, including a 1,105,455-point TIMIT embedding constructed in less than four hours.
Takeaways & Limitations
Barnes-Hut-SNE provides no error bounds and is limited to embeddings in two or three dimensions because higher-dimensional trees grow exponentially.
Abstract
from arXiv · showhide
The paper presents an O(N log N)-implementation of t-SNE -- an embedding technique that is commonly used for the visualization of high-dimensional data in scatter plots and that normally runs in O(N^2). The new implementation uses vantage-point trees to compute sparse pairwise similarities between the input data objects, and it uses a variant of the Barnes-Hut algorithm - an algorithm used by astronomers to perform N-body simulations - to approximate the forces between the corresponding points in the embedding. Our experiments show that the new algorithm, called Barnes-Hut-SNE, leads to substantial computational advantages over standard t-SNE, and that it makes it possible to learn embeddings of data sets with millions of objects.
1 Introduction
High-dimensional data visualization often requires learning low-dimensional embeddings, but SNE-based methods become impractical as dataset size grows because their computation and memory scale quadratically.
- Motivation: Traditional plots show only one or a few variables at a time, motivating low-dimensional embeddings that represent similar objects with nearby points.Embeddings support visual exploration of the structure across all variables.
- SNE background: SNE-based techniques learn two- or three-dimensional embeddings by comparing pairwise similarity distributions in the original and embedding spaces.High probabilities represent similar objects or points in the respective spaces.
- Computational bottleneck: O(N^2) computational and memory complexity limits SNE applicability to data sets with only a few thousand points.Landmark implementations can visualize larger data sets, but the paper describes this as unsatisfactory.
- Proposed approach: Barnes-Hut-SNE reduces t-SNE computation to O(N log N) and memory to O(N) using sparse input similarities and Barnes-Hut force approximation.Vantage-point trees compute sparse similarities, while Barnes-Hut groups distant points whose forces are similar.
2 Related work
Prior work accelerates quadratic algorithms mainly through space-partitioning trees, locality-sensitive hashing, or alternative approaches to N-body computation; this paper chooses metric trees and Barnes-Hut for t-SNE.
- Nearest-neighbor acceleration: Earlier methods reduce quadratic costs by accelerating nearest-neighbor searches with metric trees or locality-sensitive hashing.Examples of metric trees include B-trees, cover trees, and vantage-point trees.
- Method choice: The paper uses metric trees to approximate input similarities, motivated by their strong performance in earlier work.This choice targets the similarity-computation component of the algorithm.
- N-body acceleration: Prior N-body acceleration includes dual-tree algorithms, which consider interactions between groups of points rather than single points and groups.Preliminary experiments found dual-tree and Barnes-Hut methods performed on par in t-SNE, but the paper adopts Barnes-Hut.
3 t-Distributed Stochastic Neighbor Embedding
t-SNE learns an embedding by matching pairwise similarities between original objects and embedded points, using a heavy-tailed Student-t distribution in the embedding and gradient-based optimization.
- Objective: t-SNE minimizes divergence between pairwise-similarity distributions defined in the original data space and the embedding space.The data objects are represented as points in an s-dimensional embedding.
- Input similarities: Gaussian-kernel bandwidths are selected per object by binary search so each conditional distribution reaches a predefined perplexity.The bandwidth σ_i varies across objects.
- Embedding similarities: A normalized Student-t kernel measures similarities between embedding points to account for volume differences between high- and low-dimensional spaces.The embedding similarity distribution is heavy-tailed rather than Gaussian.
- Optimization: The embedding locations are learned by minimizing the Kullback-Leibler divergence between joint distributions P and Q.The cost function is non-convex and is typically minimized by descending along its gradient.
- Computational limitation: O(N^2) evaluation of the joint distributions makes t-SNE very slow beyond data sets containing a few thousand objects.The quadratic cost arises because normalization terms sum over all N^2 pairs.
4 Barnes-Hut-SNE
Barnes-Hut-SNE accelerates t-SNE by sparsifying input similarities with metric trees and approximating embedding-space repulsive forces with a quadtree-based Barnes-Hut method.
- Sparse similarities and gradient decomposition: O(uN) non-zero similarities approximate the input distribution P, while Barnes-Hut approximates the gradient's repulsive component.The sparse distribution is built from nearest neighbors, and the repulsive force sum is otherwise quadratic.
- Sparse similarities and gradient decomposition: ⌊3u⌋ nearest neighbors define each object's sparse similarities, found in O(uN log N) time using a vantage-point tree.The tree stores objects within or outside recursively defined hyperspheres to support nearest-neighbor search.
- Quadtree force approximation: The Barnes-Hut procedure builds a quadtree, traverses it depth-first, and summarizes sufficiently distant cells when their points exert similar forces.Each cell stores its center of mass and point count, enabling grouped force approximations.
- Quadtree force approximation: The cell-summary test compares point-to-cell distance with cell size using ||y_i−y_cell||^2/r_cell < θ.Here r_cell is the cell diagonal, and larger θ increases speed while producing poorer approximations.
- Speed-accuracy trade-off: Dual-tree interactions can provide additional speed-ups, but their computational advantages may disappear because assigning cell interactions to points is costly.The authors found dual-tree and Barnes-Hut approaches performed on par in preliminary t-SNE experiments.
5 Experiments
Experiments on four data sets evaluate Barnes-Hut-SNE’s speed, embedding quality, and scalability. The results show substantial speed gains while preserving quality and enabling million-point visualizations.
- Experimental setup: The experiments cover MNIST, CIFAR-10, NORB, and TIMIT, using embeddings constructed with θ = 0.5.TIMIT contains 1,105,455 training frames, while MNIST and CIFAR-10 each contain 70,000 objects.
- Speed-accuracy trade-off: 645 seconds is sufficient to embed all 70,000 MNIST digits at θ = 0.5 without negatively affecting embedding quality.The quality measure is the 1-nearest neighbor error of the embedding.
- Comparison with standard t-SNE: Barnes-Hut-SNE is orders of magnitude faster than standard t-SNE, with negligible differences in 1-nearest neighbor error.The computational advantage increases rapidly as the data set size N grows; computation time is plotted logarithmically.
- Large-scale embeddings: The method constructs high-quality embeddings of 70,000 MNIST images in just over 10 minutes.Figure 4 visualizes all four data sets with class-colored points and reports the construction time in each plot title.
- Large-scale embeddings: The TIMIT embedding contains 1,105,455 data points and was constructed in less than four hours.This demonstrates the method’s ability to visualize a data set with more than one million objects.
- Embedding quality: The MNIST visualization preserves local structure, including orientation as a major source of variation within the cluster of ones.The corresponding embedding displays the original digit images for detailed inspection.
6 Conclusion and Future Work
Barnes-Hut-SNE combines sparse input similarities with Barnes-Hut gradient approximation to reduce t-SNE’s computational and memory costs. The paper reports faster visualization at million-object scale, while noting missing error bounds and a two- or three-dimensional scope.
- Conclusion: Barnes-Hut-SNE uses vantage-point trees for sparse input similarities and a Barnes-Hut variant to approximate the t-SNE gradient.These components reduce the algorithm’s computational complexity to O(N log N) and memory use to O(N).
- Conclusion: The algorithm is substantially faster than standard t-SNE and facilitates scatter-plot visualization of data sets with millions of objects.The paper’s large-scale result includes a TIMIT embedding containing more than one million data points.
- Limitations: Barnes-Hut-SNE does not provide error bounds for its gradient computations or final embeddings.The authors identify alternative error-bounded algorithms as a direction for future work.
- Limitations: Barnes-Hut-SNE is limited to two- or three-dimensional embeddings because the tree size grows exponentially with embedding dimensionality.The paper notes that metric trees may offer a route to higher-dimensional generalizations.
- Future work: Future work targets parallel implementations, varying θ during optimization, and metric-tree adaptations for relational embedding.The parallelized versions are intended for data sets too large to fit fully in memory.
A Experiments with Dual-Tree t-SNE
Dual-tree t-SNE trades faster computation against more rapid embedding-quality deterioration as ρ increases, while at ρ=0.25 it performs roughly on par with Barnes-Hut-SNE across data-set sizes.
- Method: Dual-tree t-SNE uses cell-cell interactions, traversing the quadtree twice to summarize interactions between pairs of cells.The method decides whether each pair of nodes can represent all point interactions in their corresponding cells.
- Method: ρ is a speed-accuracy trade-off parameter analogous to θ in Barnes-Hut-SNE.
- Results: Increasing ρ provides additional speed-ups over Barnes-Hut-SNE but causes embedding quality to deteriorate faster.
- Results: At ρ = 0.25, dual-tree and Barnes-Hut embeddings have roughly equal quality and take approximately 650–700 seconds to construct.
- Results: With ρ=0.25, dual-tree t-SNE performs roughly on par with Barnes-Hut-SNE irrespective of the data-set size N.