bellet@usc.edu Department of Computer Science …

1 [ ] 12 Feb 2014 Technical reportA Survey on Metric Learning for Feature Vectors andStructured DataAur elien bellet of Computer ScienceUniversity of Southern CaliforniaLos Angeles, CA 90089, USAA maury Hubert Curien UMR 5516 Universit e de Saint-Etienne18 rue Benoit Lauras, 42000 St-Etienne, FranceAbstractThe need for appropriate ways to measure the distance or similaritybetween data is ubiq-uitous in machine learning, pattern recognition and data mining, but handcrafting suchgood metrics for specific problems is generally difficult. This has led to the emergence ofmetric learning, which aims at automatically learning a metric from dataand has attracteda lot of interest in machine learning and related fields for the past tenyears. This surveypaper proposes a systematic review of the metric learning literature, highlighting the prosand cons of each approach. We pay particular attention to Mahalanobis distance metriclearning, a well-studied and successful framework, but additionallypresent a wide range ofmethods that have recently emerged as powerful alternatives, including nonlinear metriclearning, similarity learning and local metric learning.

2 Recent trends and extensions, suchas semi-supervised metric learning, metric learning for histogram data and the derivation ofgeneralization guarantees, are also covered. Finally, this survey addresses metric learningfor structured data, in particular edit distance learning, and attempts to give an overviewof the remaining challenges in metric learning for the years to :Metric Learning, Similarity Learning, Mahalanobis Distance, Edit Distance1. IntroductionThe notion ofpairwise metric used throughout this survey as a generic term for distance,similarity or dissimilarity function between data pointsplays an important role in manymachine learning, pattern recognition and data mining instance, in classi-fication, thek-Nearest Neighbor classifier (Cover and Hart,1967) uses a metric to identifythe nearest neighbors; many clustering algorithms, such asthe prominentK-Means (Lloyd,1982), rely on distance measurements between data points; in information retrieval, doc.

3 Most of the work in this paper was carried out while the author was affiliated with Laboratoire HubertCurien UMR 5516, Universit e de Saint-Etienne, Metric-based learning methods were the focus of the recent SIMBAD European project (ICT 2008-FET2008-2011). Website: Aur elien bellet , Amaury Habrard and Marc , Habrard and Sebbanuments are often ranked according to their relevance to a given query based on similarityscores. Clearly, the performance of these methods depends on the quality of the metric:as in the saying birds of a feather flock together , we hope that it identifies as similar(resp. dissimilar) the pairs of instances that are indeed semantically close (resp. different).General-purpose metrics exist ( , the Euclidean distance and the cosine similarity forfeature vectors or the Levenshtein distance for strings) but they often fail to capture theidiosyncrasies of the data of interest. Improved results are expected when the metric isdesigned specifically for the task at hand.

4 Since manual tuning is difficult and tedious, a lotof effort has gone intometric learning, the research topic devoted to automatically learningmetrics from Metric Learning in a NutshellAlthough its origins can be traced back to some earlier work ( ,Short and Fukunaga,1981;Fukunaga,1990;Friedman,199 4;Hastie and Tibshirani,1996;Baxter and Bartlett,1997), metric learning really emerged in 2002 with the pioneering work ofXing et al.(2002)that formulates it as a convex optimization problem. It has since been a hot research topic,being the subject of tutorials at ICML 20102and ECCV 20103and workshops at ICCV2011,4 NIPS 20115and ICML goal of metric learning is to adapt some pairwise real-valued metric function, saythe Mahalanobis distancedM(x,x ) =p(x x )TM(x x ), to the problem of interestusing the information brought by training examples. Most methods learn the metric (here,the positive semi-definite matrixMindM) in a weakly-supervised way from pair or triplet-based constraints of the following form: Must-link / cannot-link constraints (sometimes called positive / negative pairs):S={(xi,xj) :xiandxjshould be similar},D={(xi,xj) :xiandxjshould be dissimilar}.

5 Relative constraints (sometimes called training triplets):R={(xi,xj,xk) :xishould be more similar toxjthan toxk}.A metric learning algorithm basically aims at finding the parameters of the metric suchthat it best agrees with these constraints (see Figure1for an illustration), in an effort toapproximate the underlying semantic metric. This is typically formulated as an optimizationproblem that has the following general form:minM (M,S,D,R) + R(M)where (M,S,D,R) is a loss function that incurs a penalty when training constraintsare violated,R(M) is some regularizer on the parametersMof the learned metric Survey on Metric Learning for Feature Vectors and Structured DataMetric LearningFigure 1: Illustration of metric learning applied to a face recognition task. For simplicity,images are represented as points in 2 dimensions. Pairwise constraints, shownin the left pane, are composed of images representing the same person (must-link, shown in green) or different persons (cannot-link, shown in red).

6 We wishto adapt the metric so that there are fewer constraint violations (right pane).Images are taken from the Caltech Faces learningalgorithmMetric-basedalgorithmDa tasampleLearnedmetricLearnedpredictorPre dictionFigure 2: The common process in metric learning. A metric is learned from training dataand plugged into an algorithm that outputs a predictor ( , a classifier, a regres-sor, a recommender ) which hopefully performs better than a predictorinduced by a standard (non-learned) metric. 0 is the regularization parameter. As we will see in this survey, state-of-the-art metriclearning formulations essentially differ by their choice of metric, constraints, loss functionand the metric learning phase, the resulting function is used to improve the perfor-mance of a metric-based algorithm, which is most oftenk-Nearest Neighbors (k-NN), butmay also be a clustering algorithm such asK-Means, a ranking algorithm, etc. The commonprocess in metric learning is summarized in ApplicationsMetric learning can potentially be beneficial whenever the notion of metric between in-stances plays an important role.

7 Recently, it has been applied to problems as diverse aslink prediction in networks (Shaw et al.,2011), state representation in reinforcement learn-ing (Taylor et al.,2011), music recommendation (McFee et al.,2012), partitioning , Habrard and Sebban(Lajugie et al.,2014), identity verification (Ben et al.,2012), webpage archiving (Law et al.,2012), cartoon synthesis (Yu et al.,2012) and even assessing the efficacy of acupuncture(Liang et al.,2012), to name a few. In the following, we list three large fields ofapplicationwhere metric learning has been shown to be very visionThere is a great need of appropriate metrics in Computer vision, notonly to compare images or videos in ad-hoc representations such as bags-of-visual-words(Li and Perona,2005) but also in the pre-processing step consisting in building this veryrepresentation (for instance, visual words are usually obtained by means of clustering). Forthis reason, there exists a large body of metric learning literature dealing specifically withcomputer vision problems, such as image classification (Mensink et al.)

8 ,2012), object recog-nition (Frome et al.,2007;Verma et al.,2012), face recognition (Guillaumin et al.,2009b;Lu et al.,2012), visual tracking (Li et al.,2012;Jiang et al.,2012) or image annotation(Guillaumin et al.,2009a).Information retrievalThe objective of many information retrieval systems, such assearch engines, is to provide the user with the most relevantdocuments according to his/herquery. This ranking is often achieved by using a metric between two documents or betweena document and a query. Applications of metric learning to these settings include the workofLebanon(2006);Lee et al.(2008);McFee and Lanckriet(2010);Lim et al.(2013).BioinformaticsMany problems in bioinformatics involve comparing sequences such asDNA, protein or temporal series. These comparisons are based on structured metrics suchas edit distance measures (or related string alignment scores) for strings or Dynamic TimeWarping distance for temporal series.

9 Learning these metrics to adapt them to the taskof interest can greatly improve the results. Examples include the work ofXiong and Chen(2006);Saigo et al.(2006);Kato and Nagano(2010);Wang et al.(2012a). Related TopicsWe mention here three research topics that are related to metric learning but outside thescope of this learningWhile metric learning is parametric (one learns the parameters of agiven form of metric, such as a Mahalanobis distance), kernel learning is usually nonpara-metric: one learns the kernel matrix without any assumptionon the form of the kernelthat implicitly generated it. These approaches are thus very powerful but limited to thetransductive setting and can hardly be applied to new data. The interested reader mayrefer to the recent survey on kernel learning byAbbasnejad et al.(2012).Multiple kernel learningUnlike kernel learning, Multiple Kernel Learning (MKL) isparametric: it learns a combination of predefined base kernels.

10 In this regard, it can be seenas more restrictive than metric or kernel learning, but as opposed to kernel learning, MKLhas very efficient formulations and can be applied in the inductive setting. The interestedreader may refer to the recent survey on MKL byG onen and Alpaydin(2011).Dimensionality reductionSupervised dimensionality reduction aims at finding a low-dimensional representation that maximizes the separationof labeled data and in this respect4A Survey on Metric Learning for Feature Vectors and Structured Datahas connections with metric learning,9although the primary objective is quite dimensionality reduction, or manifold learning, usually assume that the (un-labeled) data lie on an embedded low-dimensional manifold within the higher-dimensionalspace and aim at unfolding it. These methods aim at capturing or preserving some prop-erties of the original data (such as the variance or local distance measurements) in thelow-dimensional interested reader may refer to the surveys byFodor(2002) andvan der Maaten et al.