A graph-based N-body approximation with application to stochastic neighbor embedding. (March 2016)

• Record Type: Journal Article
• Authors: Parviainen, Eli
• Is Part Of: Neural networks. Volume 75(2016)
• Page Start: 1
• Page End: 11
• Publication Date: 2016-03
• Subjects: Machine learning -- N-body problem -- Approximation method -- Dimension reduction -- Stochastic neighbor embedding; Neural computers -- Periodicals; Neural networks (Computer science) -- Periodicals; Neural networks (Neurobiology) -- Periodicals; Nervous System -- Periodicals; Ordinateurs neuronaux -- Périodiques; Réseaux neuronaux (Informatique) -- Périodiques; Réseaux neuronaux (Neurobiologie) -- Périodiques; Neural computers; Neural networks (Computer science); Neural networks (Neurobiology); Periodicals; 006.32
• DOI: 10.1016/j.neunet.2015.11.007
• Languages: English
• ISSNs: 0893-6080

Abstract

Abstract: We propose a novel approximation technique, bubble approximation (BA), for repulsion forces in an N-body problem, where attraction has a limited range and repulsion acts between all points. These kinds of systems occur frequently in dimension reduction and graph drawing. Like tree codes, the established N-body approximation method, BA replaces several point-to-point computations by one area-to-point computation. Novelty of BA is to consider not only the magnitudes but also the directions of forces from the area. Therefore, its area-to-point approximations are applicable anywhere in the space. The joint effect of forces from inside the area is calculated analytically, assuming a homogeneous mass of points inside the area. These two features free BA from hierarchical data structures and complicated bookkeeping of interactions, which plague tree codes. Instead, BA uses a simple graph to control the computations. The graph provides a sparse matrix, which, suitably weighted, replaces the full matrix of pairwise comparisons in the N-body problem. As a concrete example, we implement a sparse-matrix version of stochastic neighbor embedding (a dimension reduction method), and demonstrate its good performance by comparisons to full-matrix method, and to three different approximate versions of the same method.