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) [Davis et al. 2007] and Large Margin Nearest Neighbor (LMNN) classification [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 nearly-linear 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. Our algorithm is fully parallelizable and performs favorably in the presence of adversarial noise. Learning metric spaces is a fundamental computational primitive that has found numerous applications and has received significant attention in the literature. We refer the reader to Kulis et al. (2013) ; Li and Tian (2018) for detailed exposition and discussion of previous work. At the high level, the input to a metric learning problem consists of some universe of objects X, together with some similarity information on subsets of these objects. Here, we focus on pairwise similarity and dissimilarity constraints. Specifically, we are given S, D Ă`X 2˘, which are sets of pairs of objects that are labeled as similar and dissimilar respectively. We are also given some u, ą 0, and we seek to find a mapping f : X Ñ Y , into some target metric space pY, ρq, such that for all x, y P S, ρpf pxq, f pyqq ď u, and for all x, y P D, ρpf pxq, f pyqq ě . In the case of Mahalanobis metric learning, we have X Ă R d , with |X| " n, for some d P N, and the mapping f : R d Ñ R d is linear. Specifically, we seek to find a matrix G P R dˆd , such that for all tp, qu P S, we have and for all tp, qu P D, we have 1.1 OUR CONTRIBUTION In general, there might not exist any G that satisfies all constraints of type 1 and 2. We are thus interested in finding a solution that minimizes the fraction of violated constraints, which corresponds to maximizing the accuracy of the mapping. We develop a p1`εq-approximation algorithm for optimization problem of computing a Mahalanobis metric space of maximum accuracy, that runs in near-linear time for any fixed ambient dimension d P N. This algorithm is obtained using tools from geometric approximation algorithms and the theory of linear programming in small dimension. The following summarizes our result. Theorem 1.1. For any d P N, ε ą 0, there exists a randomized algorithm for learning d-dimensional Mahalanobis metric spaces, which given an instance that admits a mapping with accuracy r˚, computes a mapping with accuracy at least r˚´ε, in time d Op1q nplog n{εq Opdq , with high probability. The above algorithm can be extended to handle various forms of regularization. We also propose several modifications of our algorithm that lead to significant performance improvements in practice. The final algorithm is evaluated experimentally on both synthetic and real-world data sets, and is compared against the currently best-known algorithms for the problem.
Fully parallelizable and adversarial-noise resistant metric learning algorithm with theoretical guarantees.
{"src": "scitldr-AIC_train", "paper_id": "SkluFgrFwH"}