Search Machine Learning Repository:
**Local Ordinal Embedding**

**Authors:** *Yoshikazu Terada* and *Ulrike V. Luxburg*

**Conference:** Proceedings of the 31st International Conference on Machine Learning (ICML-14)

**Year:** 2014

**Pages:** 847-855

**Abstract:** We study the problem of ordinal embedding: given a set of ordinal constraints of the form $distance(i,j) < distance(k,l)$ for some_quadruples $(i,j,k,l)$ of indices, the goal is to construct a point configuration $\hat{\bm{x}}_1, ..., \hat{\bm{x}}_n$ in $\R^p$ that preserves these constraints as well as possible. Our first contribution is to suggest a simple new algorithm for this problem, Soft Ordinal Embedding. The key feature of the algorithm is that it recovers not only the ordinal constraints, but even the density structure of the underlying data set. As our second contribution we prove that in the large sample limit it is enough to know ``local ordinal information'' in order to perfectly reconstruct a given point configuration. This leads to our Local Ordinal Embedding algorithm, which can also be used for graph drawing.

[pdf] [BibTeX]

authors venues years

Suggest Changes to this paper.

Brought to you by the WUSTL Machine Learning Group. We have open faculty positions (tenured and tenure-track).