A Systematic Evaluation of Ordinal Embedding Algorithms
Leena Chennuru Vankadara, Michael Lohaus, Siavash Haghiri, Faiz Ul Wahab, Ulrike von Luxburg; 24(191):1−83, 2023.
Abstract
Ordinal embedding aims to find a Euclidean representation of abstract items using triplet comparisons. Despite the numerous algorithms proposed to solve this problem, a fair and thorough assessment of these methods is lacking. This has left several key questions unanswered, such as the performance of algorithms under constrained embedding dimensions or limited triplet comparisons, and their scalability with increasing sample size or dimension. In this paper, we address these questions through an extensive and systematic empirical evaluation of existing algorithms, including a new neural network approach. Surprisingly, we find that simple and relatively unknown non-convex methods consistently outperform more recent and elaborate methods based on neural networks or landmark approaches across various tasks. This can be attributed to the insight that many non-convex optimization approaches are not affected by local optima. Our comprehensive assessment is made possible by a unified library of popular embedding algorithms, which utilizes GPU resources and enables fast and accurate embeddings of millions of data points.
[abs]