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.
Metric learning methods and their applications have been comprehensively surveyed in @cite_13 @cite_20 . Among them, our proposed method en-HOPE is closely related to the ones that can be used for dimensionality reduction and data visualization, including MCML @cite_12 , NCA @cite_5 , LMNN @cite_8 , nonlinear LMNN @cite_21 , and their deep learning extensions such as dt-MCML @cite_0 , dt-NCA @cite_0 , and DNet-kNN @cite_3 . en-HOPE is also related to neighborhood-modeling dimensionality reduction methods such as LPP @cite_10 , t-SNE @cite_2 , its parametric implementation SNE-encoder @cite_14 and deep parametric implementation pt-SNE @cite_15 . The objective functions of all these related methods have at least quadratic computational complexity with respect to the size of training set due to pairwise training data comparisons required for either loss evaluations or target neighborhood constructions. Our work is also closely related to the RVML method @cite_17 , which suffers scalability issues as MCML does.
@cite_14 @cite_8 @cite_10 @cite_21 @cite_3 @cite_0 @cite_2 @cite_5 @cite_15 @cite_20 @cite_13 @cite_12 @cite_17
2010990026 2962887033 2270409809 2605102252
The objective of sparse metric learning is to learn a distance measure from a set of data in addition to finding a low-dimensional representation. Despite demonstrated success, the performance of existing sparse metric learning approaches is usually limited because the methods assumes certain problem relaxations or they target the SML objective indirectly. In this paper, we propose a Generalized Sparse Metric Learning method. This novel framework offers a unified view for understanding many existing sparse metric learning algorithms including the Sparse Metric Learning framework proposed in (Rosales and Fung ACM International conference on knowledge discovery and data mining (KDD), pp 367–373, 2006), the Large Margin Nearest Neighbor ( in Advances in neural information processing systems (NIPS), 2006; Weinberger and Saul in Proceedings of the twenty-fifth international conference on machine learning (ICML-2008), 2008), and the D-ranking Vector Machine (D-ranking VM) (Ouyang and Gray in Proceedings of the twenty-fifth international conference on machine learning (ICML-2008), 2008). Moreover, GSML also establishes a close relationship with the Pairwise Support Vector Machine ( in BMC Bioinform, 8, 2007). Furthermore, the proposed framework is capable of extending many current non-sparse metric learning models to their sparse versions including Relevant Component Analysis (Bar- in J Mach Learn Res, 6:937–965, 2005) and a state-of-the-art method proposed in ( Advances in neural information processing systems (NIPS), 2002). We present the detailed framework, provide theoretical justifications, build various connections with other models, and propose an iterative optimization method, making the framework both theoretically important and practically scalable for medium or large datasets. Experimental results show that this generalized framework outperforms six state-of-the-art methods with higher accuracy and significantly smaller dimensionality for seven publicly available datasets. Abstract: Distance metric learning (DML) approaches learn a transformation to a representation space where distance is in correspondence with a predefined notion of similarity. While such models offer a number of compelling benefits, it has been difficult for these to compete with modern classification algorithms in performance and even in feature extraction. In this work, we propose a novel approach explicitly designed to address a number of subtle yet important issues which have stymied earlier DML algorithms. It maintains an explicit model of the distributions of the different classes in representation space. It then employs this knowledge to adaptively assess similarity, and achieve local discrimination by penalizing class distribution overlap. We demonstrate the effectiveness of this idea on several tasks. Our approach achieves state-of-the-art classification results on a number of fine-grained visual recognition datasets, surpassing the standard softmax classifier and outperforming triplet loss by a relative margin of 30-40 . In terms of computational performance, it alleviates training inefficiencies in the traditional triplet loss, reaching the same error in 5-30 times fewer iterations. Beyond classification, we further validate the saliency of the learnt representations via their attribute concentration and hierarchy recovery properties, achieving 10-25 relative gains on the softmax classifier and 25-50 on triplet loss in these tasks. Distance metric learning (DML) approaches learn a transformation to a representation space where distance is in correspondence with a predefined notion of similarity. While such models offer a number of compelling benefits, it has been difficult for these to compete with modern classification algorithms in performance and even in feature extraction. In this work, we propose a novel approach explicitly designed to address a number of subtle yet important issues which have stymied earlier DML algorithms. It maintains an explicit model of the distributions of the different classes in representation space. It then employs this knowledge to adaptively assess similarity, and achieve local discrimination by penalizing class distribution overlap. We demonstrate the effectiveness of this idea on several tasks. Our approach achieves state-of-the-art classification results on a number of fine-grained visual recognition datasets, surpassing the standard softmax classifier and outperforming triplet loss by a relative margin of 30-40 . In terms of computational performance, it alleviates training inefficiencies in the traditional triplet loss, reaching the same error in 5-30 times fewer iterations. Beyond classification, we further validate the saliency of the learnt representations via their attribute concentration and hierarchy recovery properties, achieving 10-25 relative gains on the softmax classifier and 25-50 on triplet loss in these tasks. 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.