Shift-invariant similarities circumvent distance concentration in stochastic neighbor embedding and variants

By John Aldo Lee, Michel Verleysen. 2011

40 citations recorded by the source corpus.

Dimensionality reduction aims at representing high-dimensional data in low-dimensional spaces, mainly for visualization and exploratory purposes. As an alternative to projections on linear subspaces, nonlinear dimensionality reduction, also known as manifold learning, can provide data representations that preserve structural properties such as pairwise distances or local neighborhoods. Very recently, similarity preservation emerged as a new paradigm for dimensionality reduction, with methods such as stochastic neighbor embedding and its variants. Experimentally, these methods significantly outperform the more classical methods based on distance or transformed distance preservation. This paper explains both theoretically and experimentally the reasons for these performances. In particular, it details why the phenonomenon of distance concentration is an impediment towards effcient dimensionality reduction and how SNE and its variants circumvent this diffculty by using similarities that are invariant to shifts with respect to squared distances. The paper also proposes a generalized definition of shift-invariant similarities that extend the applicability of SNE to noisy data.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Media Technology, Statistics and Probability, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. John Aldo Lee
2. Michel Verleysen
3. P. Dupont
4. Leland McInnes

In Computer Vision and Pattern Recognition

1. John Aldo Lee
2. Michel Verleysen
3. P. Dupont
4. Guillaume Bernard
5. Emilie Renard
6. Leland McInnes

In Media Technology

1. Michel Verleysen
2. John Aldo Lee

In Statistics and Probability

1. Michel Verleysen
2. John Aldo Lee

In Representation & Self-Supervised Learning

1. P. Dupont
2. Michel Verleysen
3. John Aldo Lee
4. Guillaume Bernard
5. Emilie Renard
6. Leland McInnes

Citations in the corpus

• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, neutral): “We note that this has a similar practical effect to the truncated similarity approach of Lee and Verleysen [13], but derives naturally from the assumption of local connectivity of the manifold.”
• Type 1 and 2 mixtures of Kullback-Leibler divergences as cost functions in dimensionality reduction based on similarity preservation (2013, background): “The COIL-20 and MNIST images are just vectorized ught. only two distributions in this case).”