The goal of ordinal embedding is to represent items as points in a
low-dimensional Euclidean space given a set of constraints in the form of
distance comparisons like "item $i$ is closer to item $j$ than item $k$".
Ordinal constraints like this often come from human judgments. To account for
errors and variation in judgments, we consider the noisy situation in which the
given constraints are independently corrupted by reversing the correct
constraint with some probability. This paper makes several new contributions to
this problem. First, we derive prediction error bounds for ordinal embedding
with noise by exploiting the fact that the rank of a distance matrix of points
in $\mathbb{R}^d$ is at most $d+2$. These bounds characterize how well a
learned embedding predicts new comparative judgments. Second, we investigate
the special case of a known noise model and study the Maximum Likelihood
estimator. Third, knowledge of the noise model enables us to relate prediction
errors to embedding accuracy. This relationship is highly non-trivial since we
show that the linear map corresponding to distance comparisons is
non-invertible, but there exists a nonlinear map that is invertible. Fourth,
two new algorithms for ordinal embedding are proposed and evaluated in
experiments.

本文研究基于距离比较的序列嵌入问题，考虑给定的限制条件因人类判断而产生误差和变异性，提出了新的算法来预测和优化嵌入结果。

有序嵌入的有限样本预测和恢复界限

Finite Sample Prediction and Recovery Bounds for Ordinal Embedding

Motivated by recent work on ordinal embedding (Kleindessner and von Luxburg,
2014), we derive large sample consistency results and rates of convergence for
the problem of embedding points based on triple or quadruple distance
comparisons. We also consider a variant of this problem where only local
comparisons are provided. Finally, inspired by (Jamieson and Nowak, 2011), we
bound the number of such comparisons needed to achieve consistency.

针对基于三元或四元距离比较嵌入点的问题，以及只提供局部比较的变体问题，本文在最近关于序数嵌入的研究基础上，得出了大样本一致性结果和收敛速率，并受到其他相关研究的启发，对需要实现一致性所需的比较次数进行了限制。

序数嵌入的一些理论

Some theory for ordinal embedding

Deep learning has proven itself as a successful set of models for learning
useful semantic representations of data. These, however, are mostly implicitly
learned as part of a classification task. In this paper we propose the triplet
network model, which aims to learn useful representations by distance
comparisons. A similar model was defined by Wang et al. (2014), tailor made for
learning a ranking for image information retrieval. Here we demonstrate using
various datasets that our model learns a better representation than that of its
immediate competitor, the Siamese network. We also discuss future possible
usage as a framework for unsupervised learning.

本文提出了三元组网络模型，通过距离比较来学习有用的表示方法，在多个数据集上的结果显示其比竞争对手孪生网络学习了更好的表示方法，而且还探讨了其作为无监督学习框架的未来可能用途。