Skip to yearly menu bar Skip to main content


Scaling Up Ordinal Embedding: A Landmark Approach

Jesse Anderton · Javed Aslam

Pacific Ballroom #227

Keywords: [ Representation Learning ] [ Ranking and Preference Learning ] [ Metric Learning ] [ Large Scale Learning and Big Data ] [ Dimensionality Reduction ]


Ordinal Embedding is the problem of placing n objects into R^d to satisfy constraints like "object a is closer to b than to c." It can accommodate data that embeddings from features or distances cannot, but is a more difficult problem. We propose a novel landmark-based method as a partial solution. At small to medium scales, we present a novel combination of existing methods with some new theoretical justification. For very large values of n optimizing over an entire embedding breaks down, so we propose a novel method which first embeds a subset of m << n objects and then embeds the remaining objects independently and in parallel. We prove a distance error bound for our method in terms of m and that it has O(dn log m) time complexity, and show empirically that it is able to produce high quality embeddings in a fraction of the time needed for any published method.

Live content is unavailable. Log in and register to view live content