Accelerating t-SNE using tree-based algorithms

Ускорение t-SNE с использованием алгоритмов на основе деревьев
Laurens van der Maaten
2014-01-01

Barnes-Hut algorithmdual-tree algorithmhigh-dimensional data visualizationt-SNEtree-based algorithms
The paper investigates the acceleration of t-SNE—an embedding technique that is com-monly used for the visualization of high-dimensional data in scatter plots—using two tree-based algorithms. In particular, the paper develops variants of the Barnes-Hut algorithm and of the dual-tree algorithm that approximate the gradient used for learning t-SNE em-beddings in O(N logN). Our experiments show that the resulting algorithms substantially accelerate t-SNE, and that they make it possible to learn embeddings of data sets with millions of objects. Somewhat counterintuitively, the Barnes-Hut variant of t-SNE appears to outperform the dual-tree variant.
1
Both tree-based algorithms substantially accelerate t-SNE compared with the standard approach.
2
Despite expectations, the Barnes–Hut t-SNE variant empirically outperforms the dual-tree variant.
3
The accelerated methods enable learning t-SNE embeddings for datasets containing millions of objects.
4
The paper develops Barnes–Hut and dual-tree variants of t-SNE that approximate its learning gradient in O(N log N).

t-SNE embedding of high-dimensional data

Acceleration of t-SNE gradient computation and embedding learning using tree-based approximation algorithms

Publication Details
Publication Date
2014-01-01
Journal
Publisher
ISSN
Cited by
2226
Access Type
Author Information
Authors
Laurens van der Maaten
Explore further
Open the scid.ai AI chat with a ready-made request: it will find papers on a similar topic and help build a literature review.
Find similar papers in the chat →
Make a presentation
100%