Source-linked AI summary
Approximated and User Steerable tSNE for Progressive Visual Analytics
Nicola Pezzotti, Boudewijn P. F. Lelieveldt, Laurens van der Maaten, Thomas Höllt, Elmar Eisemann, Anna Vilanova
TL;DR
tSNE produces useful embeddings but its slow initialization and scalability constrain interactive Progressive Visual Analytics. A-tSNE uses controllable approximate similarities, interactive refinement, and visual feedback to support rapid exploration; the authors report meaningful embeddings two orders of magnitude faster than BH-SNE, while noting that iterative minimization slows beyond one million points.
Problem
tSNE can produce meaningful intermediate results, but slow initialization and scalability constrain its use for interactive Progressive Visual Analytics.
Method
A-tSNE uses fast approximated KNN similarities, user-controlled precision, concurrent refinement, and interactive high-dimensional data updates.
Results
Meaningful A-tSNE embeddings are generated two orders of magnitude faster than state-of-the-art BH-SNE, with density-based visualization and coordinated interaction for data exploration.
Takeaways & Limitations
Users can preview data quickly, inspect approximation levels, refine interesting regions, and manipulate high-dimensional data during analysis.
Takeaways & Limitations
For datasets with more than a million data-points, iterative minimization becomes slower.
Abstract
from arXiv · showhide
Progressive Visual Analytics aims at improving the interactivity in existing analytics techniques by means of visualization as well as interaction with intermediate results. One key method for data analysis is dimensionality reduction, for example, to produce 2D embeddings that can be visualized and analyzed efficiently. t-Distributed Stochastic Neighbor Embedding (tSNE) is a well-suited technique for the visualization of several high-dimensional data. tSNE can create meaningful intermediate results but suffers from a slow initialization that constrains its application in Progressive Visual Analytics. We introduce a controllable tSNE approximation (A-tSNE), which trades off speed and accuracy, to enable interactive data exploration. We offer real-time visualization techniques, including a density-based solution and a Magic Lens to inspect the degree of approximation. With this feedback, the user can decide on local refinements and steer the approximation level during the analysis. We demonstrate our technique with several datasets, in a real-world research scenario and for the real-time analysis of high-dimensional streams to illustrate its effectiveness for interactive data analysis.
1 INTRODUCTION
A-tSNE adapts the tSNE pipeline for Progressive Visual Analytics by reducing initialization delay and supporting interactive data changes, approximation control, and refinement.
- A-tSNE adapts the complete tSNE pipeline, including distance computation, for Progressive Visual Analytics.
- Approximate embeddings trade speed for precision while allowing users to inspect intermediate results and steer refinement toward interesting regions.
- A-tSNE minimizes initialization time, enabling immediate inspection of preliminary computation results.
- The method supports interactive modification, removal, or addition of high-dimensional data without disrupting visual analysis.
- Benchmark datasets show large performance increases over the state of the art while maintaining high precision.
2 RELATED WORK
Related work frames tSNE as powerful but difficult to use interactively because of scalability and initialization costs. A-tSNE extends approximation and steerability to dense high-dimensional analysis with interactive visual feedback.
- tSNE preserves local structure in 2D or 3D embeddings while showing global information such as clusters at several scales.
- Barnes-Hut-SNE reduces tSNE complexity to O(N log(N)) computationally and O(N) in memory, but remains unsuitable for interactive desktop exploration.
- Progressive Visual Analytics uses intermediate results to support analysis, parameter selection, and data filtering, but tSNE initialization does not readily provide useful intermediate results.
- A-tSNE approximates initialization and lets analysts refine approximation levels based on user input.
- Unlike related steerable methods, A-tSNE combines approximation with visualization of approximation degree and interactive manipulation of dense high-dimensional data.
3 TSNE
tSNE represents high-dimensional similarities with probability distributions and optimizes a low-dimensional embedding. Barnes-Hut approximations reduce computational cost by sparsifying neighborhoods and accelerating force computation.
- The symmetric joint distribution P combines conditional similarities as pij = (pi|j + pj|i) / 2N.
- For each point, tSNE models high-dimensional similarity with conditional probabilities based on a locally scaled Gaussian kernel.
- A Student’s t-distribution defines low-dimensional similarities, and gradient descent adjusts point positions to minimize divergence between P and Q.
- Barnes-Hut-SNE keeps only nearest-neighbor similarities and uses Barnes-Hut force approximation to reduce computation to O(N log(N)).
- A Vantage-Point Tree computes K-nearest-neighbor queries in high-dimensional metric space in O(log(N)) time.
4 A-TSNE FOR PROGRESSIVE VISUAL ANALYTICS
A-tSNE adapts tSNE for Progressive Visual Analytics by replacing slow exact initialization with controllable approximations that produce inspectable intermediate embeddings. Users can refine approximations during optimization while trading computation time against embedding precision.
- Motivation: tSNE serializes a slow similarity-computation module before gradient descent, creating a speed bump without meaningful intermediate results.
- Method: A-tSNE uses approximated KNN queries to build an approximated high-dimensional distribution and start iterative minimization nearly instantly.
- Method: The user controls approximation precision ρ, with larger values making the approximated joint-probability distribution more similar to the exact one.
- Steerability: A-tSNE refines individual neighborhoods during gradient descent, allowing approximation updates and embedding optimization to proceed in parallel.
- Evaluation: A-tSNE evaluates performance and accuracy across MNIST, NORB, CIFAR-10, and TIMIT using randomized KD-tree parameterizations.
- Results: A small reduction in precision can greatly reduce computation time, while reasonable MNIST approximations produce nearly identical embeddings two orders of magnitude faster than BH-SNE.
- Results: With increasing data size, approximation error decreases, and the authors report rapidly generated accurate embeddings that support immediate interaction.
5 INTERACTIVE ANALYSIS SYSTEM
A-tSNE supports immediate analysis from approximated embeddings, while users can refine approximation levels, inspect them visually, and manipulate high-dimensional data interactively.
- A-tSNE lets users begin analyzing data without waiting for exact high-dimensional similarities.
- Users can apply refinement strategies that produce progressively more precise embeddings from approximated information.
- The system visualizes approximation levels while accommodating larger embeddings generated interactively.
- Users can add or remove points and change high-dimensional representations without disrupting the visual analysis process.
- The techniques are implemented in a coordinated multiple-views framework for direct inspection of embedded data.
5.1 User Driven Refinement
User-driven refinement selects which neighborhoods to improve, balancing local detail against global overview according to analytical priorities and available computational resources.
- User Driven Refinement: The refinement process operates per point and offers three strategies for selecting points to refine.
- User Driven Refinement: Random refinement processes all points, while analyst-guided refinement focuses computation on visually interesting embedding areas.
- User Driven Refinement: Brushing lets users select points for immediate refinement, but refining only a few points can leave neighboring forces approximated.
- User Driven Refinement: Breadth-first traversal can extend refinement from selected points through KNN neighborhoods, with priority queues supporting alternative ordering criteria.
- User Driven Refinement: Density-based refinement orders points by high-dimensional density to improve global relationships, either within a selection or across the dataset.
5.2 Visualization and Interaction
The system combines density-based embedding views with approximation cues so users can inspect clusters, outliers, and refinement progress at multiple scales.
- Visualization and Interaction: Density-based visualization helps reveal embedding features at different scales when many points make simple point views visually cluttered.
- Visualization and Interaction: Users can change KDE bandwidth, transfer function, and opacity interactively to inspect clusters and selection outliers.
- Visualization and Interaction: In MNIST, changing bandwidth reveals clusters at different levels, while label-based selection exposes outlier distributions.
- Visualization and Interaction: The approximation visualization encodes per-point precision ρ_i, which changes during refinement and is mapped into a value between zero and one.
- Visualization and Interaction: A Magic Lens uses approximation values to control transparency, while full-view encoding shows refined and still-approximated regions across the embedding.
- Visualization and Interaction: Removing color information inside contours reduces cluster perception in the approximation visualization.
5.3 Data Manipulation
A-tSNE allows embeddings to evolve as high-dimensional data changes, supporting point insertion, deletion, representation changes, and incremental neighborhood updates.
- Data Manipulation: The system exploits dynamically updated similarities to let analysts manipulate points in high-dimensional feature space.
- Data Manipulation: Embeddings evolve dynamically as data changes instead of being recomputed from scratch.
- Data Manipulation: Adding a point computes and refines its neighborhood, updates affected KNN relationships, and initializes its embedding position from neighboring points.
- Data Manipulation: Neighborhood updates for point insertion run in O(N) when dMax_i is cached, while randomized KD-tree insertion runs in O(log(N)).
- Data Manipulation: Removing a point updates every neighborhood in O(N), decreases estimated precision by 1/K when a replacement is omitted, and updates the KD-tree in O(log(N)).
- Data Manipulation: Changes to one point’s representation combine removal and addition, whereas adding or removing dimensions recomputes an approximated joint-probability distribution.
5.4 Visual Analysis Tool
A-tSNE is integrated into an interactive multi-view system that links embeddings, data, and refinement status. Users can inspect selections, manipulate data, and steer refinement processes through coordinated views and controls.
- The system combines embedding, data, and refinement-status views with controls for gradient descent, density visualization, data manipulation, and refinements.The interface organizes these views at the top and controls at the bottom.
- Selections in embeddings are reflected in data-specific views, including anatomical planes and a 3D volume viewer for voxel data.Selections can change hue and the volume viewer’s transfer function, and can be based on data-driven criteria.
- Switchable heatmap and image widgets allow the Data View to support different data types and combined visual analyses.Multiple and different views can be combined when necessary.
- The Refinement-Status View records each user-triggered refinement with an embedding snapshot, description, and progress over selected data-points.Users can steer embedding evolution by refining selected areas.
6 IMPLEMENTATION
The implementation combines native, GPU, and approximate-neighborhood components to support interactive A-tSNE visualization and refinement.
- The system uses C++ and Qt together with OpenGL and custom GLSL shaders for embedding visualization.The implementation exploits parallelizability where possible.
- Approximated neighborhoods are computed with FLANN, which implements KNN algorithms.
- The density visualization is computed on the GPU using Gaussian-kernel textures, geometry shaders, frame-buffer rendering, and additive blending.The kernel texture colors point-generated quads, producing KDE through additive blending.
7 CASE STUDY I: EXPLORATORY ANALYSIS OF GENE EXPRESSION IN THE MOUSE BRAIN
The mouse-brain case study uses A-tSNE to validate gene-expression data, refine approximate neighborhoods, alter the high-dimensional representation, and identify anatomical structure interactively.
- The dataset contains 61,164 voxels represented by 4,345-dimensional gene-expression vectors, without using spatial information in the high-dimensional space.
- A-tSNE supports early validation by producing intermediate embeddings from approximate similarities while the analyst inspects visible clusters and their spatial locations.The workflow begins with a low desired precision, such as ρ = 0.2, to estimate KNN parameters.
- Approximately 51 seconds are required for the first A-tSNE embedding, compared with 3 hours and 50 minutes for BH-SNE.
- Clusters remain after neighborhood refinement, allowing the analyst to check that they are not artifacts of approximated similarities.The interactive lens indicates approximated and refined regions in the embedding.
- A-tSNE separates anatomical structures using gene expression, while interactive analysis helps identify a suitable number of principal components.The embedding places voxels from the same anatomical structure close together.
HIGH-DIMENSIONAL STREAMS
A-tSNE enables real-time analysis of high-dimensional streams by maintaining a recent sliding window, inserting new readings, and allowing high-dimensional features to be changed during analysis.
- Standard tSNE cannot compute a new embedding every 100 ms when data arrive faster than map computation, motivating A-tSNE for streams.
- The stream analysis retains readings from the previous 10 minutes, averaging about 6,000 data-points and updating the embedding every 100 ms.
- New readings are displayed as colored, fading points over the density visualization, exposing recent trends while preserving the longer-window overview.Colors encode the subject’s activity classification, and points fade after F seconds.
- New readings form evolving clusters whose activity changes can be confirmed through point colors in the embedding.
- Removing features from a miscalibrated sensor causes the cluster of affected readings to disappear and move near the normal lying-down cluster.
- The study concludes that fast high-dimensional similarity computation and direct data manipulation are necessary for real-time stream analysis with A-tSNE.
9 CONCLUSIONS
A-tSNE provides rapid approximate tSNE embeddings for interactive analysis, with visual feedback that lets users inspect and steer approximation. Its interactivity is limited for datasets exceeding one million points because iterative minimization becomes slower.
- Fast approximate embeddings support interactive analysis, including real-time density visualization and coordinated views for steering relevant regions.
- Users can inspect the embedding’s approximation level through two dedicated visualizations.
- A-tSNE generates meaningful tSNE embeddings two orders of magnitude faster than BH-SNE.
- For datasets exceeding one million points, slower iterative minimization limits A-tSNE’s interactivity.
- The authors identify heterogeneous data and additional high-dimensional streams, including climate readings, as future application scenarios.