How can classical multidimensional scaling go wrong?
Dez 6, 2021
Sprecher:innen
Rishi Sonthalia
Sprecher:in · 0 Follower:innen
Greg Van Buskirk
Sprecher:in · 0 Follower:innen
Benjamin Raichel
Sprecher:in · 0 Follower:innen
Anna C. Gilbert
Sprecher:in · 0 Follower:innen
Über
Given a matrix D describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of its performance on non-Euclidean metrics is lacking. In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from D, for the Frobenius norm of the difference between D and the metric D_ returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has a significant number of negative eigenvalues, then D-D__F, after initially decreasing, willeventually increase as we increase the dimension. Hence, counterintuitively, the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases as we increase the dimension for a variety of non-Euclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1-nearest neighbor) and complex (e.g., multi-layer neural nets) classifiers decreasing as we increase the embedding dimension.Finally, our analysis leads us to a new efficiently computable algorithm that returns a matrix D_l that is at least as close to the original distances as D_t (the Euclidean metric closest in ℓ_2 distance). While D_l is not metric, when given as input to cMDS instead of D, it empirically results in solutions whose distance to D does not increase when we increase the dimension and the classification accuracy degrades less than the cMDS solution.Given a matrix D describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an in-depth analysis of its performance on non-Euclidean metrics is lacking. In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from D, for the Frobenius norm of the differe…
Organisator
NeurIPS 2021
Konto · 1,9k Follower:innen
Über NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
Just Mix Once: Mixing Samples with Implicit Group Distribution
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks
Später ansehen
R. Lieck, …
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Learning Robust Hierarchical Patterns of Human Brain across Many fMRI Studies
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Integrating single-cell multi-omic datasets with optimal transport
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Towards a Shared Rubric for Dataset Annotation
Später ansehen
Ewigspeicher-Fortschrittswert: 0 = 0.0%
Ground-Truth, Whose Truth?: Examining the Challenges with Annotating Toxic Text Datasets
Später ansehen
Kofi Arhin, …
Ewigspeicher-Fortschrittswert: 0 = 0.0%