Metric learning aims to embed one metric space into another to benefit tasks like classification and clustering. Although a greatly distorted metric space has a high degree of freedom to fit training data, it is prone to overfitting and numerical inaccuracy. This paper presents bounded-distortion metric learning (BDML), a new metric learning framework which amounts to finding an optimal Mahalanobis metric space with a bounded-distortion constraint. An efficient solver based on the multiplicative weights update method is proposed. Moreover, we generalize BDML to pseudo-metric learning and devise the semidefinite relaxation and a randomized algorithm to approximately solve it. We further provide theoretical analysis to show that distortion is a key ingredient for stability and generalization ability of our BDML algorithm. Extensive experiments on several benchmark datasets yield promising results.
Based on the type of constraints, we can also classify them into pairwise and triplet-wise ones. Pairwise methods @cite_21 @cite_3 often adds constraints to enforce distances between pairs of dissimilar points are larger than a given threshold. Representative methods in the triplet group are the large-margin nearest neighbor @cite_28 and its variants @cite_36 . They exploit the local triplet constraints to assure that the distance between any point and its different-class neighbour should be at least one unit margin further than the distance between it and its same-class neighbour. Intuitively, if these triplet constraints are well satisfied, the empirical loss of kNN would be small.
@cite_28 @cite_21 @cite_36 @cite_3
2605102252 2106053110 2077904202 2130556178
We address the problem of distance metric learning (DML), defined as learning a distance consistent with a notion of semantic similarity. Traditionally, for this problem supervision is expressed in the form of sets of points that follow an ordinal relationship – an anchor point x is similar to a set of positive points Y , and dissimilar to a set of negative points Z, and a loss defined over these distances is minimized. While the specifics of the optimization differ, in this work we collectively call this type of supervision Triplets and all methods that follow this pattern Triplet-Based methods. These methods are challenging to optimize. A main issue is the need for finding informative triplets, which is usually achieved by a variety of tricks such as increasing the batch size, hard or semi-hard triplet mining, etc. Even with these tricks, the convergence rate of such methods is slow. In this paper we propose to optimize the triplet loss on a different space of triplets, consisting of an anchor data point and similar and dissimilar proxy points which are learned as well. These proxies approximate the original data points, so that a triplet loss over the proxies is a tight upper bound of the original loss. This proxy-based loss is empirically better behaved. As a result, the proxy-loss improves on state-of-art results for three standard zero-shot learning datasets, by up to 15 points, while converging three times as fast as other triplet-based losses. The accuracy of k-nearest neighbor (kNN) classification depends significantly on the metric used to compute distances between different examples. In this paper, we show how to learn a Mahalanobis distance metric for kNN classification from labeled examples. The Mahalanobis metric can equivalently be viewed as a global linear transformation of the input space that precedes kNN classification using Euclidean distances. In our approach, the metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. As in support vector machines (SVMs), the margin criterion leads to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our approach requires no modification or extension for problems in multiway (as opposed to binary) classification. In our framework, the Mahalanobis distance metric is obtained as the solution to a semidefinite program. On several data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification. Sometimes these results can be further improved by clustering the training examples and learning an individual metric within each cluster. We show how to learn and combine these local metrics in a globally integrated manner. The effectiveness of nearest neighbor search heavily relies on the definition of distance function. Unfortunately, the meaningfulness of the frequently used distance, such as Euclidean distance, fractional distance and so on, will degrade with the increasing dimensionality. This problem, which is called distance concentration or instability, makes NN method perform poorly in a proximity query. The most popular distance function for time series, dynamic time warping(DTW), also concentrates when it is used in high-dimensional space. We learn the exponent p of the norm based on nearest neighbor large margin criterion for time series classification. The distance concentration is countered by maximum discrimination instead of maximum variance of distance distribution. The empirical results we presented demonstrate that the proposed approach shows a uniformly behavior, with results comparable to classic 1NN-Euclidean and 1NN-DTW. We show how to learn a Mahanalobis distance metric for k-nearest neighbor (kNN) classification by semidefinite programming. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin. On seven data sets of varying size and difficulty, we find that metrics trained in this way lead to significant improvements in kNN classification—for example, achieving a test error rate of 1.3 on the MNIST handwritten digits. As in support vector machines (SVMs), the learning problem reduces to a convex optimization based on the hinge loss. Unlike learning in SVMs, however, our framework requires no modification or extension for problems in multiway (as opposed to binary) classification.