Local Ordinal Embedding

Yoshikazu Terada, Ulrike Luxburg
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):847-855, 2014.

Abstract

We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i,j) < distance(k,l) for some_quadruples (i,j,k,l) of indices, the goal is to construct a point configuration \hat\bmx_1, ..., \hat\bmx_n in \R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know “local ordinal information” in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-terada14, title = {Local Ordinal Embedding}, author = {Terada, Yoshikazu and Luxburg, Ulrike}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {847--855}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/terada14.pdf}, url = {https://proceedings.mlr.press/v32/terada14.html}, abstract = {We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i,j) < distance(k,l) for some_quadruples (i,j,k,l) of indices, the goal is to construct a point configuration \hat\bmx_1, ..., \hat\bmx_n in \R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know “local ordinal information” in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.} }
Endnote
%0 Conference Paper %T Local Ordinal Embedding %A Yoshikazu Terada %A Ulrike Luxburg %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-terada14 %I PMLR %P 847--855 %U https://proceedings.mlr.press/v32/terada14.html %V 32 %N 2 %X We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i,j) < distance(k,l) for some_quadruples (i,j,k,l) of indices, the goal is to construct a point configuration \hat\bmx_1, ..., \hat\bmx_n in \R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know “local ordinal information” in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.
RIS
TY - CPAPER TI - Local Ordinal Embedding AU - Yoshikazu Terada AU - Ulrike Luxburg BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-terada14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 847 EP - 855 L1 - http://proceedings.mlr.press/v32/terada14.pdf UR - https://proceedings.mlr.press/v32/terada14.html AB - We study the problem of ordinal embedding: given a set of ordinal constraints of the form distance(i,j) < distance(k,l) for some_quadruples (i,j,k,l) of indices, the goal is to construct a point configuration \hat\bmx_1, ..., \hat\bmx_n in \R^p that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know “local ordinal information” in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing. ER -
APA
Terada, Y. & Luxburg, U.. (2014). Local Ordinal Embedding. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):847-855 Available from https://proceedings.mlr.press/v32/terada14.html.

Related Material