Abstract
Ordinal data analysis is an interesting direction in machine learning. It mainly deals with data for which only the relationships ‘\(<\)’, ‘\(=\)’, ‘\(>\)’ between pairs of points are known. We do an attempt of formalizing structures behind ordinal data analysis by introducing the notion of ordinal spaces on the base of a strict axiomatic approach. For these spaces we study general properties as isomorphism conditions, connections with metric spaces, embeddability in Euclidean spaces, topological properties etc.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
S. Agarwal, J. Wills, L. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie, Generalized non-metric multidimensional scaling, in: Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, vol. 2, Proceedings of Machine Learning Research (San Juan, Puerto Rico, 2007), pp. 11–18
P. S. Aleksandrov, Introduction to the Set Theory and General Topology, Nauka (Moscow, 1977) (in Russian)
Aronov, B., Pach, J., Sharir, M., Tardos, G.: Distinct distances in three and higher dimensions. Combin. Probab. Comput. 13, 283–293 (2004)
L. M. Blumenthal, Theory and Applications of Distance Geometry, Clarendon Press (Oxford, 1953)
I. Borg and P. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer (New York, 2005)
N. Bourbaki, General Topology 1–4, Springer (Berlin, 1995)
Brass, P.: The maximum number of second smallest distances in finite planar sets. Discrete Comput. Geom. 7, 371–379 (1992)
P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry, Springer (New York, 2005)
Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry, Graduate Studies in Mathematics, vol. 33. American Mathematical Society (Providence, RI (2001)
Cardoso, J.S., Pinto da Costa, J.F.: Learning to classify ordinal data: The data replication method. J. Mach. Learn. Res. 8, 1393–1429 (2007)
Chung, F.R.K., Szemerédi, E., Trotter, W.T.: The number of different distances determined by a set of points in the Euclidean plane. Discrete Comput. Geom. 7, 1–11 (1992)
M. M. Deza and E. Deza, Encyclopedia of Distances, fourth edition, Springer (Berlin, 2016)
Dovgoshey, O., Petrov, E.: Weak similarities of metric and semimetric spaces. Acta Math. Hungar. 141, 301–319 (2013)
Dovgoshey, O., Petrov, E., Teichert, H.-M.: How rigid the finite ultrametric spaces can be? J. Fixed Point Theory Appl. 19, 1083–1102 (2017)
Erdös, P.: On sets of distances of \(n\) points. Amer. Math. Monthly 53, 248–250 (1946)
Grünbaum, B.: A proof of Vazonyi's conjecture. Bull. Res. Council Israel. Sect. A 6, 77–78 (1956)
Harborth, H.: Solution to problem 664A. Elem. Math. 29, 14–15 (1974)
E. Harzheim, Ordered Sets, Advances in Mathematics, vol. 7, Springer (New York, 2005)
Heckmann, R.: Approximation of metric spaces by partial metric spaces. Appl. Categ. Structures 7, 71–83 (1999)
A. Heppes, Beweis einer Vermutung von A. Vázsonyi, Acta Math. Acad. Sci. Hungar., 7 (1956), 463–466
Isbell, J.R.: Uniform spaces, AMS. Providence, RI (1964)
K. Jamieson and R. Nowak, Active ranking using pairwise comparisons, in: Proceedings of the 24th International Conference on Neural Information Processing Systems, Curran Associates, Inc. (USA, 2011), pp. 2240–2248
M. Kleindessner and U. von Luxburg, Uniqueness of ordinal embedding, in: Proceedings of the 27th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 35, Proceedings of Machine Learning Research (Barcelona, Spain, 2014), pp. 40–67
M. Kleindessner and U. von Luxburg, Dimensionality estimation without distances, in Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, vol. 38, Proceedings of Machine Learning Research (San Diego, California, USA, 2015), pp. 471–479
M. Kleindessner and U. von Luxburg, Kernel functions based on triplet comparisons, in: Advances in Neural Information Processing Systems 30, Curran Associates, Inc. (2017), pp. 6807–6817
Kleindessner, M., von Luxburg, U.: Lens depth function and \(k\)-relative neighborhood graph: Versatile tools for ordinal data analysis. J. Mach. Learn. Res. 18, 1–52 (2017)
Kruskal, J.B.: Nonmetric multidimensional scaling: A numerical method. Psychometrika 29, 115–129 (1964)
S. G. Matthews, Partial metric topology, in: Papers on General Topology and Applications (Flushing, NY, 1992), Annals of the New York Academy of Sciences, vol. 728, New York Acad. Sci. (New York, 1994), pp. 183–197
Menger, K.: Untersuchungen über allgemeine Metrik. Math. Ann. 100, 75–163 (1928)
S. J. O’Neill, Two topologies are better than one, Technical report, University of Warwick (1995)
E. A. Petrov, Ball-preserving mappings of finite ulrametric spaces, Proc. Inst. Appl. Math. Mech. Natl. Acad. Sci. Ukraine, 26 (2013), 150–158 (in Russian)
Petrov, E.: Weak similarities of finite ultrametric and semimetric spaces, p-Adic Numbers Ultrametric Anal. Appl. 10, 108–117 (2018)
Quist, M., Yona, G.: Distributional scaling: An algorithm for structure-preserving embedding of metric and nonmetric spaces. J. Mach. Learn. Res. 5, 399–420 (2004)
R. Rosales and G. Fung, Learning sparse metrics via linear programming, in: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Association for Computing Machinery (New York, NY, 2006), pp. 367–373
Shepard, R.: The analysis of proximities: multidimensional scaling with an unknown distance function. II, Psychometrika 27, 219–246 (1962)
Shepard, R.: Metric structures in ordinal data. J. Math. Psychol. 3, 287–315 (1966)
Y. Shi, W. Li, and F. Sha, Metric learning for ordinal data, in: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI Press (2016), pp. 2030–2036
N. J. A. Sloane, editor, The On-line Encyclopedia of Integer Sequences, published electronically at https://oeis.org
S. Straszewicz, Sur un problème géométrique de P. Erdös, Bull. Acad. Polon. Sci. Cl. III., 5 (1957), 39–40
Vesztergombi, K.: On large distances in planar sets. Discrete Math. 67, 191–198 (1987)
F. Wauthier, M. Jordan, and N. Jojic, Efficient ranking from pairwise comparisons, in: Proceedings of the 30th International Conference on Machine Learning, vol. 28, Proceedings of Machine Learning Research (Atlanta, Georgia, USA, 2013), pp. 109–117
Acknowledgement
The authors are grateful to the anonymous referee whose numerous remarks helped them to improve the article.
Author information
Authors and Affiliations
Corresponding author
Additional information
The second author was supported by H2020-MSCA-RISE-2014, Project number 645672 (AMMODIT: “Approximation Methods for Molecular Modelling and Diagnosis Tools”). The research of the second author was also partially supported by Project 0117U006353 from the Department of Targeted Training of Taras Shevchenko National University of Kyiv at the NAS of Ukraine and by the National Academy of Sciences of Ukraine within scientific research works for young scientists, Project 0117U006050.
Rights and permissions
About this article
Cite this article
Keller, K., Petrov, E. Ordinal spaces. Acta Math. Hungar. 160, 119–152 (2020). https://doi.org/10.1007/s10474-019-00972-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-019-00972-z