Learning Mahalanobis Metric Spaces via Geometric Approximation Algorithms
Learning Mahalanobis Metric Spaces via Geometric Approximation Algorithms
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Diego Ihara;N. Mohammadi;Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
Diego Ihara;N. Mohammadi;Anastasios Sidiropoulos
学习马氏度量空间是一个重要问题，它已经有了大量应用。针对这个问题已经设计了几种算法，包括[Davis等人，2007]提出的信息理论度量学习（ITML）以及[Weinberger和Saul，2009]提出的大间隔最近邻（LMNN）分类算法。我们将马氏度量学习的一种表述视为一个优化问题，其目标是最小化违反相似性/相异性约束的数量。我们表明，对于任何固定的环境维度，存在一个具有近似线性运行时间的完全多项式时间近似方案（FPTAS）。这个结果是利用低维线性规划理论中的工具得到的。我们还讨论了该算法在实践中的改进，并展示了在合成数据集和真实世界数据集上的实验结果。
Learning Mahalanobis metric spaces is an important problem that has found numerous applications. Several algorithms have been designed for this problem, including Information Theoretic Metric Learning (ITML) by [Davis et al. 2007] and Large Margin Nearest Neighbor (LMNN) classification by [Weinberger and Saul 2009]. We consider a formulation of Mahalanobis metric learning as an optimization problem, where the objective is to minimize the number of violated similarity/dissimilarity constraints. We show that for any fixed ambient dimension, there exists a fully polynomial-time approximation scheme (FPTAS) with nearlylinear running time. This result is obtained using tools from the theory of linear programming in low dimensions. We also discuss improvements of the algorithm in practice, and present experimental results on synthetic and real-world data sets.