Hyperbolic Ordinal Embedding

Atsushi Suzuki, Jing Wang, Feng Tian, Atsushi Nitanda, Kenji Yamanishi
Proceedings of The Eleventh Asian Conference on Machine Learning, PMLR 101:1065-1080, 2019.

Abstract

Given ordinal relations such as the object $i$ is more similar to $j$ than $k$ is to $l$, ordinal embedding is to embed these objects into a low-dimensional space with all ordinal constraints preserved. Although existing approaches have preserved ordinal relations in Euclidean space, whether Euclidean space is compatible with true data structure is largely ignored, although it is essential to effective embedding. Since real data often exhibit hierarchical structure, it is hard for Euclidean space approaches to achieve effective embeddings in low dimensionality, which incurs high computational complexity or overfitting. In this paper we propose a novel hyperbolic ordinal embedding (HOE) method to embed objects in hyperbolic space. Due to the hierarchy-friendly property of hyperbolic space, HOE can effectively capture the hierarchy to achieve embeddings in an extremely low-dimensional space. We have not only theoretically proved the superiority of hyperbolic space and the limitations of Euclidean space for embedding hierarchical data, but also experimentally demonstrated that HOE significantly outperforms Euclidean-based methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v101-suzuki19a, title = {Hyperbolic Ordinal Embedding}, author = {Suzuki, Atsushi and Wang, Jing and Tian, Feng and Nitanda, Atsushi and Yamanishi, Kenji}, booktitle = {Proceedings of The Eleventh Asian Conference on Machine Learning}, pages = {1065--1080}, year = {2019}, editor = {Lee, Wee Sun and Suzuki, Taiji}, volume = {101}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v101/suzuki19a/suzuki19a.pdf}, url = {https://proceedings.mlr.press/v101/suzuki19a.html}, abstract = {Given ordinal relations such as the object $i$ is more similar to $j$ than $k$ is to $l$, ordinal embedding is to embed these objects into a low-dimensional space with all ordinal constraints preserved. Although existing approaches have preserved ordinal relations in Euclidean space, whether Euclidean space is compatible with true data structure is largely ignored, although it is essential to effective embedding. Since real data often exhibit hierarchical structure, it is hard for Euclidean space approaches to achieve effective embeddings in low dimensionality, which incurs high computational complexity or overfitting. In this paper we propose a novel hyperbolic ordinal embedding (HOE) method to embed objects in hyperbolic space. Due to the hierarchy-friendly property of hyperbolic space, HOE can effectively capture the hierarchy to achieve embeddings in an extremely low-dimensional space. We have not only theoretically proved the superiority of hyperbolic space and the limitations of Euclidean space for embedding hierarchical data, but also experimentally demonstrated that HOE significantly outperforms Euclidean-based methods.} }
Endnote
%0 Conference Paper %T Hyperbolic Ordinal Embedding %A Atsushi Suzuki %A Jing Wang %A Feng Tian %A Atsushi Nitanda %A Kenji Yamanishi %B Proceedings of The Eleventh Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Wee Sun Lee %E Taiji Suzuki %F pmlr-v101-suzuki19a %I PMLR %P 1065--1080 %U https://proceedings.mlr.press/v101/suzuki19a.html %V 101 %X Given ordinal relations such as the object $i$ is more similar to $j$ than $k$ is to $l$, ordinal embedding is to embed these objects into a low-dimensional space with all ordinal constraints preserved. Although existing approaches have preserved ordinal relations in Euclidean space, whether Euclidean space is compatible with true data structure is largely ignored, although it is essential to effective embedding. Since real data often exhibit hierarchical structure, it is hard for Euclidean space approaches to achieve effective embeddings in low dimensionality, which incurs high computational complexity or overfitting. In this paper we propose a novel hyperbolic ordinal embedding (HOE) method to embed objects in hyperbolic space. Due to the hierarchy-friendly property of hyperbolic space, HOE can effectively capture the hierarchy to achieve embeddings in an extremely low-dimensional space. We have not only theoretically proved the superiority of hyperbolic space and the limitations of Euclidean space for embedding hierarchical data, but also experimentally demonstrated that HOE significantly outperforms Euclidean-based methods.
APA
Suzuki, A., Wang, J., Tian, F., Nitanda, A. & Yamanishi, K.. (2019). Hyperbolic Ordinal Embedding. Proceedings of The Eleventh Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 101:1065-1080 Available from https://proceedings.mlr.press/v101/suzuki19a.html.

Related Material