Metric learning methods for dimensionality reduction in combination with k-Nearest Neighbors (kNN) have been extensively deployed in many classification, data embedding, and information retrieval applications. However, most of these approaches involve pairwise training data comparisons, and thus have quadratic computational complexity with respect to the size of training set, preventing them from scaling to fairly big datasets. Moreover, during testing, comparing test data against all the training data points is also expensive in terms of both computational cost and resources required. Furthermore, previous metrics are either too constrained or too expressive to be well learned. To effectively solve these issues, we present an exemplar-centered supervised shallow parametric data embedding model, using a Maximally Collapsing Metric Learning (MCML) objective. Our strategy learns a shallow high-order parametric embedding function and compares training/test data only with learned or precomputed exemplars, resulting in a cost function with linear computational complexity for both training and testing. We also empirically demonstrate, using several benchmark datasets, that for classification in two-dimensional embedding space, our approach not only gains speedup of kNN by hundreds of times, but also outperforms state-of-the-art supervised embedding approaches.

我们提出了一个基于最大坍塌度度量学习（MCML）目标的标本中心监督浅层参数化数据嵌入模型，它可以在训练和测试时具有线性计算复杂度，并可以通过使用学习或预计算的样本来将测试数据与所有训练数据点作比较。对于二维嵌入空间的分类，我们的方法不仅可以将kNN的速度提升数百倍，而且还优于最先进的监督嵌入方法。

示例中心的监督浅层参数数据嵌入