Fast solvers and efficient implementations for distance metric learning
Fast solvers and efficient implementations for distance metric learning
复制标题
DOI：
10.1145/1390156.1390302
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Kilian Q. Weinberger;L. Saul
中科院分区：
文献类型：
--
作者：
Kilian Q. Weinberger;L. Saul
在本文中，我们研究如何通过学习马氏距离度量来改进最近邻分类。我们建立在最近提出的距离度量学习框架的基础上，称为大边缘最近邻（LMNN）分类。我们的论文做出了三个贡献。首先，我们描述了一个针对 LMNN 分类中出现的半定规划特定实例的高效求解器；我们的求解器可以在几个小时内处理具有数十亿大边距约束的问题。其次，我们展示了如何使用公制球树来减少训练和测试时间；通过学习输入空间的低维表示，球树的加速进一步放大。第三，我们展示了如何在输入空间的不同部分学习不同的马氏距离度量。对于大型数据集，使用局部自适应距离度量可以降低错误率。
In this paper we study how to improve nearest neighbor classification by learning a Mahalanobis distance metric. We build on a recently proposed framework for distance metric learning known as large margin nearest neighbor (LMNN) classification. Our paper makes three contributions. First, we describe a highly efficient solver for the particular instance of semidefinite programming that arises in LMNN classification; our solver can handle problems with billions of large margin constraints in a few hours. Second, we show how to reduce both training and testing times using metric ball trees; the speedups from ball trees are further magnified by learning low dimensional representations of the input space. Third, we show how to learn different Mahalanobis distance metrics in different parts of the input space. For large data sets, the use of locally adaptive distance metrics leads to even lower error rates.