How can classical multidimensional scaling go wrong?
Dec 6, 2021
Speakers
Rishi Sonthalia
Speaker · 0 followers
Greg Van Buskirk
Speaker · 0 followers
Benjamin Raichel
Speaker · 0 followers
Anna C. Gilbert
Speaker · 0 followers
About
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…
Organizer
NeurIPS 2021
Account · 1.9k followers
About 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.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Safe Reinforcement Learning by Imagining the Near Future
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
Watch later
Shuai Zhang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Closing remarks by the organizers
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Natural and Artificial Reinforcement Learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Consistent Non-Parametric Methods for Maximizing Robustness
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Frank Wolfe in Probability Space
Watch later
Carson Kent, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%