Local Ordinal Embedding
Local Ordinal Embedding
复制标题
DOI：
--
复制
发表时间：
2014-06
期刊：
影响因子：
--
通讯作者：
Y. Terada;U. V. Luxburg
中科院分区：
文献类型：
--
作者：
Y. Terada;U. V. Luxburg
我们研究了序数嵌入问题：给定一组序数约束，其形式为距离（i，j）<距离（k，l），对于一些四元组（i，j，k，l）的索引，目标是构造一个点配置x1，.，xn在Rp中，尽可能地保持这些约束。我们的第一个贡献是提出了一个简单的新算法，软序嵌入。该算法的主要特点是，它不仅恢复有序约束，但甚至底层数据集的密度结构。作为我们的第二个贡献，我们证明了在大样本的限制，它是足够的知道“本地序信息”，以完美地重建一个给定的点配置。这导致了我们的局部有序嵌入算法，它也可以用于图形绘制。
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 x1,..., xn in Rp 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.