Workshop: Subset Selection in Machine Learning: From Theory to Applications

Ordinal Embedding for Sets

Aissatou Diallo · Johannes Fürnkranz


Ordinal embedding is the task of computing a meaningful multi-dimensional representation of objects, for which only qualitative constraints on their distance functions are known. In particular, we consider comparisons of the form “Which object from the pair (j, k) is more similar to object i?”. In this paper, we generalize this framework to the case where the ordinal constraints are not given at the level of individual points, but at the level of sets, and propose a distributional triplet embedding approach in a scalable learning framework. We show that the query complexity of our approach is on par with the single item approach. Without having access to features of the items to be embedded, we show the applicability of our model on toy datasets for the task of reconstruction, and demonstrate the validity of the obtained embeddings in experiments on synthetic and real-world datasets.