Generalized Non-metric Multidimensional Scaling

Sameer Agarwal, Josh Wills, Lawrence Cayton, Gert Lanckriet, David Kriegman, Serge Belongie
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:11-18, 2007.

Abstract

We consider the non-metric multidimensional scaling problem: given a set of dissimilarities $\Delta$, find an embedding whose inter-point Euclidean distances have the same ordering as $\Delta$. In this paper, we look at a generalization of this problem in which only a set of order relations of the form $d_{ij} < d_{kl}$ are provided. Unlike the original problem, these order relations can be contradictory and need not be specified for all pairs of dissimilarities. We argue that this setting is more natural in some experimental settings and propose an algorithm based on convex optimization techniques to solve this problem. We apply this algorithm to human subject data from a psychophysics experiment concerning how reflectance properties are perceived. We also look at the standard NMDS problem, where a dissimilarity matrix $\Delta$ is provided as input, and show that we can always find an orderrespecting embedding of $\Delta$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v2-agarwal07a, title = {Generalized Non-metric Multidimensional Scaling}, author = {Agarwal, Sameer and Wills, Josh and Cayton, Lawrence and Lanckriet, Gert and Kriegman, David and Belongie, Serge}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {11--18}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/agarwal07a/agarwal07a.pdf}, url = {https://proceedings.mlr.press/v2/agarwal07a.html}, abstract = {We consider the non-metric multidimensional scaling problem: given a set of dissimilarities $\Delta$, find an embedding whose inter-point Euclidean distances have the same ordering as $\Delta$. In this paper, we look at a generalization of this problem in which only a set of order relations of the form $d_{ij} < d_{kl}$ are provided. Unlike the original problem, these order relations can be contradictory and need not be specified for all pairs of dissimilarities. We argue that this setting is more natural in some experimental settings and propose an algorithm based on convex optimization techniques to solve this problem. We apply this algorithm to human subject data from a psychophysics experiment concerning how reflectance properties are perceived. We also look at the standard NMDS problem, where a dissimilarity matrix $\Delta$ is provided as input, and show that we can always find an orderrespecting embedding of $\Delta$.} }
Endnote
%0 Conference Paper %T Generalized Non-metric Multidimensional Scaling %A Sameer Agarwal %A Josh Wills %A Lawrence Cayton %A Gert Lanckriet %A David Kriegman %A Serge Belongie %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-agarwal07a %I PMLR %P 11--18 %U https://proceedings.mlr.press/v2/agarwal07a.html %V 2 %X We consider the non-metric multidimensional scaling problem: given a set of dissimilarities $\Delta$, find an embedding whose inter-point Euclidean distances have the same ordering as $\Delta$. In this paper, we look at a generalization of this problem in which only a set of order relations of the form $d_{ij} < d_{kl}$ are provided. Unlike the original problem, these order relations can be contradictory and need not be specified for all pairs of dissimilarities. We argue that this setting is more natural in some experimental settings and propose an algorithm based on convex optimization techniques to solve this problem. We apply this algorithm to human subject data from a psychophysics experiment concerning how reflectance properties are perceived. We also look at the standard NMDS problem, where a dissimilarity matrix $\Delta$ is provided as input, and show that we can always find an orderrespecting embedding of $\Delta$.
RIS
TY - CPAPER TI - Generalized Non-metric Multidimensional Scaling AU - Sameer Agarwal AU - Josh Wills AU - Lawrence Cayton AU - Gert Lanckriet AU - David Kriegman AU - Serge Belongie BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-agarwal07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 11 EP - 18 L1 - http://proceedings.mlr.press/v2/agarwal07a/agarwal07a.pdf UR - https://proceedings.mlr.press/v2/agarwal07a.html AB - We consider the non-metric multidimensional scaling problem: given a set of dissimilarities $\Delta$, find an embedding whose inter-point Euclidean distances have the same ordering as $\Delta$. In this paper, we look at a generalization of this problem in which only a set of order relations of the form $d_{ij} < d_{kl}$ are provided. Unlike the original problem, these order relations can be contradictory and need not be specified for all pairs of dissimilarities. We argue that this setting is more natural in some experimental settings and propose an algorithm based on convex optimization techniques to solve this problem. We apply this algorithm to human subject data from a psychophysics experiment concerning how reflectance properties are perceived. We also look at the standard NMDS problem, where a dissimilarity matrix $\Delta$ is provided as input, and show that we can always find an orderrespecting embedding of $\Delta$. ER -
APA
Agarwal, S., Wills, J., Cayton, L., Lanckriet, G., Kriegman, D. & Belongie, S.. (2007). Generalized Non-metric Multidimensional Scaling. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:11-18 Available from https://proceedings.mlr.press/v2/agarwal07a.html.

Related Material