GPGPU linear complexity t-SNE optimization

Nicola Pezzotti, Julian Thijssen, Alexander Mordvintsev, Thomas Hollt, Baldur van Lew, Boudewijn P.F. Lelieveldt, Elmar Eisemann, Anna Vilanova

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library.
Original languageEnglish
Article number8811606
Pages (from-to)1172-1181
Number of pages10
JournalIEEE Transactions on Visualization and Computer Graphics
Volume26
Issue number1
Early online date2020
DOIs
Publication statusPublished - Jan 2020

Fingerprint

Computational complexity
Tensors
Scalability
Tuning
Textures
Hardware
Costs

Keywords

  • Approximate Computation
  • Dimensionality Reduction
  • GPGPU
  • High Dimensional Data
  • Progressive Visual Analytics

Cite this

Pezzotti, N., Thijssen, J., Mordvintsev, A., Hollt, T., Lew, B. V., Lelieveldt, B. P. F., ... Vilanova, A. (2020). GPGPU linear complexity t-SNE optimization. IEEE Transactions on Visualization and Computer Graphics, 26(1), 1172-1181. [8811606]. https://doi.org/10.1109/TVCG.2019.2934307
Pezzotti, Nicola ; Thijssen, Julian ; Mordvintsev, Alexander ; Hollt, Thomas ; Lew, Baldur van ; Lelieveldt, Boudewijn P.F. ; Eisemann, Elmar ; Vilanova, Anna. / GPGPU linear complexity t-SNE optimization. In: IEEE Transactions on Visualization and Computer Graphics. 2020 ; Vol. 26, No. 1. pp. 1172-1181.
@article{386bb9cfe82446b0b2baf120e073ee6e,
title = "GPGPU linear complexity t-SNE optimization",
abstract = "In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library.",
keywords = "Approximate Computation, Dimensionality Reduction, GPGPU, High Dimensional Data, Progressive Visual Analytics",
author = "Nicola Pezzotti and Julian Thijssen and Alexander Mordvintsev and Thomas Hollt and Lew, {Baldur van} and Lelieveldt, {Boudewijn P.F.} and Elmar Eisemann and Anna Vilanova",
year = "2020",
month = "1",
doi = "10.1109/TVCG.2019.2934307",
language = "English",
volume = "26",
pages = "1172--1181",
journal = "IEEE Transactions on Visualization and Computer Graphics",
issn = "1077-2626",
publisher = "IEEE Computer Society",
number = "1",

}

Pezzotti, N, Thijssen, J, Mordvintsev, A, Hollt, T, Lew, BV, Lelieveldt, BPF, Eisemann, E & Vilanova, A 2020, 'GPGPU linear complexity t-SNE optimization', IEEE Transactions on Visualization and Computer Graphics, vol. 26, no. 1, 8811606, pp. 1172-1181. https://doi.org/10.1109/TVCG.2019.2934307

GPGPU linear complexity t-SNE optimization. / Pezzotti, Nicola; Thijssen, Julian; Mordvintsev, Alexander; Hollt, Thomas; Lew, Baldur van; Lelieveldt, Boudewijn P.F.; Eisemann, Elmar; Vilanova, Anna.

In: IEEE Transactions on Visualization and Computer Graphics, Vol. 26, No. 1, 8811606, 01.2020, p. 1172-1181.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - GPGPU linear complexity t-SNE optimization

AU - Pezzotti, Nicola

AU - Thijssen, Julian

AU - Mordvintsev, Alexander

AU - Hollt, Thomas

AU - Lew, Baldur van

AU - Lelieveldt, Boudewijn P.F.

AU - Eisemann, Elmar

AU - Vilanova, Anna

PY - 2020/1

Y1 - 2020/1

N2 - In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library.

AB - In recent years the t-distributed Stochastic Neighbor Embedding (t-SNE) algorithm has become one of the most used and insightful techniques for exploratory data analysis of high-dimensional data. It reveals clusters of high-dimensional data points at different scales while only requiring minimal tuning of its parameters. However, the computational complexity of the algorithm limits its application to relatively small datasets. To address this problem, several evolutions of t-SNE have been developed in recent years, mainly focusing on the scalability of the similarity computations between data points. However, these contributions are insufficient to achieve interactive rates when visualizing the evolution of the t-SNE embedding for large datasets. In this work, we present a novel approach to the minimization of the t-SNE objective function that heavily relies on graphics hardware and has linear computational complexity. Our technique decreases the computational cost of running t-SNE on datasets by orders of magnitude and retains or improves on the accuracy of past approximated techniques. We propose to approximate the repulsive forces between data points by splatting kernel textures for each data point. This approximation allows us to reformulate the t-SNE minimization problem as a series of tensor operations that can be efficiently executed on the graphics card. An efficient implementation of our technique is integrated and available for use in the widely used Google TensorFlow.js, and an open-source C++ library.

KW - Approximate Computation

KW - Dimensionality Reduction

KW - GPGPU

KW - High Dimensional Data

KW - Progressive Visual Analytics

UR - http://www.scopus.com/inward/record.url?scp=85075604395&partnerID=8YFLogxK

U2 - 10.1109/TVCG.2019.2934307

DO - 10.1109/TVCG.2019.2934307

M3 - Article

C2 - 31449023

VL - 26

SP - 1172

EP - 1181

JO - IEEE Transactions on Visualization and Computer Graphics

JF - IEEE Transactions on Visualization and Computer Graphics

SN - 1077-2626

IS - 1

M1 - 8811606

ER -

Pezzotti N, Thijssen J, Mordvintsev A, Hollt T, Lew BV, Lelieveldt BPF et al. GPGPU linear complexity t-SNE optimization. IEEE Transactions on Visualization and Computer Graphics. 2020 Jan;26(1):1172-1181. 8811606. https://doi.org/10.1109/TVCG.2019.2934307