PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Metric Learning for Feature Vectors and Structured Data

Aurélien Bellet, Amaury Habrard, Marc Sebban

arXiv:1306.6709v4cs.LGcs.AIstat.ML

TL;DR

Choosing a metric that captures task-specific similarity is difficult, while scalability and structured data remain important challenges. This survey reviews metric-learning methods and concludes that numerical-data approaches are mature and increasingly scalable, whereas structured-data research remains comparatively limited and difficult to scale.

  • Problem

    Task-specific metrics are difficult to handcraft, while metric-learning methods face scalability challenges and structured-data applications remain less developed.

  • Method

    The paper systematically reviews metric-learning methods spanning Mahalanobis, nonlinear, similarity, local, semi-supervised, histogram, generalization, and structured-data approaches.

  • Results

    Metric learning for numerical data has reached maturity, with scalable methods covering online, nonlinear, local, ranking, multi-task, domain-adaptation, and generalization settings.

  • Takeaways & Limitations

    Structured-data metric learning remains a promising direction, but advances from numerical data have not yet broadly propagated because many methods remain difficult to scale and analyze.

  • Takeaways & Limitations

    The reviewed sparse metric-learning method has O(d3) iteration complexity and cannot be applied to high-dimensional problems.

Abstract

from arXiv · show

The need for appropriate ways to measure the distance or similarity between data is ubiquitous in machine learning, pattern recognition and data mining, but handcrafting such good metrics for specific problems is generally difficult. This has led to the emergence of metric learning, which aims at automatically learning a metric from data and has attracted a lot of interest in machine learning and related fields for the past ten years. This survey paper proposes a systematic review of the metric learning literature, highlighting the pros and cons of each approach. We pay particular attention to Mahalanobis distance metric learning, a well-studied and successful framework, but additionally present a wide range of methods that have recently emerged as powerful alternatives, including nonlinear metric learning, similarity learning and local metric learning. Recent trends and extensions, such as semi-supervised metric learning, metric learning for histogram data and the derivation of generalization guarantees, are also covered. Finally, this survey addresses metric learning for structured data, in particular edit distance learning, and attempts to give an overview of the remaining challenges in metric learning for the years to come.

1. Introduction

Metric learning adapts pairwise metrics to data and task-specific information because metric quality affects metric-based learning methods across diverse applications. This survey reviews general-purpose approaches, their strengths and limitations, and recent extensions for feature vectors and structured data.

  • Motivation: Pairwise metrics underpin methods including k-Nearest Neighbor classification, K-Means clustering, and document ranking, whose performance depends on identifying semantically similar or dissimilar instances.General-purpose choices include Euclidean distance, cosine similarity, and Levenshtein distance.
  • Research landscape: Metric learning emerged as a major research topic with Xing et al. (2002), which formulated it as a convex optimization problem, and subsequently reached considerable practical and theoretical maturity.The survey reports that more than 75% of its references postdate the earlier Yang and Jin (2006) review.
  • Metric learning framework: Metric learning adapts a real-valued pairwise function to a target problem using training information, typically by learning a Mahalanobis matrix from pairwise or triplet-based constraints.Algorithms optimize constraint violations with a loss and regularization, then use the learned metric in k-NN, clustering, ranking, or related algorithms.
  • Applications: Applications span link prediction, reinforcement learning, music recommendation, identity verification, information retrieval, computer vision, and bioinformatics, where learned metrics support comparisons or rankings.Bioinformatics uses structured metrics such as edit distance and Dynamic Time Warping distance for sequences and temporal series.
  • Survey scope and contribution: The survey emphasizes general-purpose methods and aims to help readers understand each method’s pros and cons, current research strengths and limitations, and practical applicability.Computer-vision-specific metric-learning literature is excluded because it requires substantial domain background and is considered suitable for a separate survey.

2. Key Properties of Metric Learning Algorithms

Metric learning algorithms are organized by five key properties that guide method selection: learning paradigm, metric form, scalability, solution optimality, and dimensionality reduction. These properties distinguish trade-offs in supervision, expressiveness, optimization, overfitting, computational scale, and representation compactness.

  • Learning Paradigm: Learning paradigms are fully supervised, weakly supervised, or semi-supervised, depending on access to labels, constraint side information, and unlabeled instances.Fully supervised methods use labeled examples to generate pair or triplet constraints, whereas semi-supervised methods additionally use unlabeled data to help avoid overfitting when supervision is scarce.
  • Form of Metric: Metric forms comprise linear, nonlinear, and local families, trading optimization simplicity and reduced overfitting against expressive power and flexibility for complex data.Linear metrics usually yield convex formulations, nonlinear metrics can capture nonlinear variation but may overfit, and local metrics learn multiple metrics but use many parameters.
  • Scalability: Scalability requires handling both the number of training examples or constraints n and data dimensionality d, with online learning offering one solution for the former.The survey identifies rapidly growing data as motivating scalability concerns across both sample count and feature dimensionality.
  • Optimality of the Solution: Convex metric-learning formulations can guarantee a global optimum, whereas nonconvex formulations may find only a local optimum.This property concerns how well learned metric parameters satisfy the chosen criterion.
  • Dimensionality Reduction: Low-rank metric matrices can produce lower-dimensional projected spaces, enabling faster computations and more compact representations.Dimensionality reduction is treated as a byproduct of learning a projection into a new feature space.

3. Supervised Mahalanobis Distance Learning

Supervised Mahalanobis metric learning is attractive for its simplicity and linear-projection interpretation, but learning scalable, low-dimensional, and positive-semidefinite metrics presents central challenges. The section surveys regularized, multitask, robust, and dimensionality-reducing approaches that address these issues with varying constraints and optimization trade-offs.

  • Learning challenges: Projected-gradient optimization enforces positive semidefiniteness by projecting onto the PSD cone, but eigenvalue decomposition costs O(d^3) in high dimensions.The method alternates gradient and projection steps, setting negative eigenvalues to zero.
  • Learning challenges: Feature-weighting methods are convex and efficient but learn less general metrics and require manually choosing the feature-weighting matrix A.They optimize a weighting W rather than a full Mahalanobis metric, with slack variables controlled by C.
  • Multi-task metric learning: Multi-task Mahalanobis learning combines a shared metric with task-specific metrics, while regularization parameters control shared information and task-specific adaptation.Extreme parameter settings recover either independent LMNN models or LMNN on the union of all data.
  • Multi-task metric learning: GPML uses von Neumann divergence to preserve geometry between task metrics while automatically enforcing positive-semidefiniteness and retaining convexity when the underlying task algorithm is convex.The divergence is also described as rank-preserving.

4. Other Advances in Metric Learning

This section reviews advances and trends beyond linear Mahalanobis metric learning, focusing mainly on fully and weakly supervised methods. It covers similarity, nonlinear, local, histogram-based, generalization, and semi-supervised metric learning.

  • Overview: The section shifts from linear Mahalanobis metric learning to other advances and trends for feature vectors, emphasizing fully and weakly supervised methods.Linear Mahalanobis metric learning is presented as the focus of the preceding discussion.
  • Supervised advances: It covers linear similarity learning, nonlinear metric learning, and local metric learning, including kernelization of linear methods.These topics are organized in Sections 4.1 through 4.3.
  • Extensions and trends: The section also addresses metric learning for histogram data, generalization guarantees for supervised learning, and semi-supervised metric learning.These topics appear in Sections 4.4 through 4.6.

4.1 Linear Similarity Learning

Linear similarity learning broadens metric learning beyond Mahalanobis distances by removing the PSD constraint, often enabling more scalable algorithms. The section reviews generalized cosine, bilinear, classification-oriented, and cross-domain pair-matching similarities.

  • 4.1 Linear Similarity Learning: Linear similarity methods often omit the PSD constraint, motivating their development as potentially more scalable alternatives to Mahalanobis metric learning.The surveyed approaches use general similarity functions rather than restricting the learned matrix to be positive semidefinite.
  • 4.1 Linear Similarity Learning: SiLA learns a possibly nonsymmetric similarity with normalization, generalizing cosine similarity while optimizing online from LMNN-style target-neighbor constraints.Its online algorithm is based on a voted perceptron.
  • 4.1 Linear Similarity Learning: OASIS learns an unnormalized bilinear similarity that is efficient for sparse inputs, with computation taking O(k1k2) time when the inputs have k1 and k2 nonzero features.Its matrix need not be PSD or symmetric, and the identity matrix yields an unnormalized cosine similarity.
  • 4.1 Linear Similarity Learning: OASIS achieves competitive medium-scale results and scales to problems with millions of training instances, but cannot incorporate complex regularizers.The method uses a simple closed-form update when the current example pair violates the relevant condition.
  • 4.1 Linear Similarity Learning: SLLC optimizes similarity for linear classification and is competitive with traditional metric learning while inducing extremely sparse classifiers.It makes examples more similar on average to same-class than opposite-class reference points by margin γ.
  • 4.1 Linear Similarity Learning: RSL learns a rectangular bilinear matrix for pair matching across potentially different-dimensional domains, using low-rank factorization and Riemannian optimization to reach a local minimum.The setting includes matching images with different resolutions or queries with documents.

4.2 Nonlinear Methods

Nonlinear metric learning captures structure that linear metrics miss through kernelization or direct nonlinear mappings. These methods can improve performance on highly nonlinear data, but kernelization may become intractable and nonlinear objectives are more prone to overfitting and local optima.

  • Kernelization: Kernelization learns a linear metric in a kernel-induced nonlinear feature space, combining nonlinear representation with linear metric optimization.General kernelization methods use KPCA to project data into a potentially infinite-dimensional feature space before applying the unchanged metric-learning algorithm.
  • Kernelization: Kernelization can require learning an n×n matrix, making the problem intractable as the number of training examples n grows large.Kernelizing a particular metric algorithm may also require a new formulation and different implementation.
  • Kernelization: Kernelized metric learning may drastically improve highly nonlinear problems but can overfit because nonlinear high-dimensional spaces make pair or triplet constraints easier to satisfy.This can lead to poor generalization performance.
  • Direct nonlinear methods: Direct nonlinear methods optimize nonlinear metric forms and can significantly outperform linear methods on some problems, but they are subject to local optima and greater overfitting.Examples include LSMD, which learns an arbitrarily complex convolutional-neural-network projection, and NNCA, which learns a nonlinear low-dimensional representation with a deep belief network before fine-tuning the NCA objective.
  • Direct nonlinear methods: Gradient-Boosted LMNN efficiently learns a nonlinear transformation by adding limited-depth gradient-boosted regression trees to the mapping learned by linear LMNN.Each selected tree divides the space into 2^p regions whose instances receive the same translation vector.
  • Direct nonlinear methods: HDML learns binary codes so Hamming distance supports metric learning, enabling small storage cost and exact neighbor search in sublinear time.Its nonconvex, discontinuous objective is optimized through a continuous upper bound computable in O(q^2) time when code length q remains small.

4.3 Local Metric Learning

Local metric learning addresses heterogeneous data by allowing metrics to vary across the space, approximating location-dependent geometric structure. The surveyed methods trade flexibility and nonlinear adaptation for computational cost, scalability limits, or overfitting risks.

  • Motivation: Local metrics vary across heterogeneous data spaces, potentially using one metric per class, instance, or region instead of a single global metric.This approach can approximate the geodesic distance induced by a metric tensor.
  • M2-LMNN: M2-LMNN partitions training data into C clusters and jointly learns one Mahalanobis metric per cluster using supervised or unsupervised clustering.It can significantly improve over standard LMNN, especially with supervised clustering, but increases computational cost and risks overfitting without a large validation set.
  • Bk-means: Bk-means learns Bregman distances whose Hessian-dependent parameterization corresponds to an infinite number of local Mahalanobis distances.Its nonparametric formulation has n + 1 variables and linear-complexity subgradient iterations, but distance evaluation requires n kernel evaluations.
  • PLML: PLML learns an instance-specific Mahalanobis metric as a nonnegative combination of basis metrics, with weights encouraging locality and smoothness over the data manifold.Basis learning requires eigen-decomposition scaling in O(d3), making PLML intractable for high-dimensional problems despite strong evaluated-dataset performance.
  • RFD: RFD formulates metric learning as pair classification and uses random forests to obtain a highly nonlinear metric that adapts implicitly across the space.Its pair representation encodes both relative and absolute positions, while training is efficient because trees take O(n log n) time and can be built in parallel.

4.4 Metric Learning for Histogram Data

This section reviews metric learning methods for histogram data, including χ2-LMNN for bin-to-bin distances and GML and EMDL for learning cross-bin Earth Mover’s Distance metrics. These approaches improve on standard histogram metrics and Mahalanobis distance learning, while involving constraints or optimization procedures that may introduce local optima.

  • Overview: Histograms lie on the probability simplex and commonly represent objects as feature-frequency vectors, including bag-of-words and bag-of-visual-words representations.Such data arise in natural language processing, computer vision, and bioinformatics.
  • χ2-LMNN: χ2-LMNN generalizes the nonlinear χ2 histogram distance with a linear transformation constrained to map inputs onto the simplex.It uses the LMNN objective and standard subgradient descent; experiments report improvements over standard histogram metrics and Mahalanobis learning, including dimensionality reduction when r < d.
  • GML: GML learns an EMD ground matrix from weighted training triplets, optimizing a criterion based on weighted Earth Mover’s Distances between histogram pairs.EMD is a cross-bin distance that models transporting earth between bins rather than matching corresponding bins directly.
  • EMDL: EMDL learns the EMD ground matrix from relative constraints with a large margin, using alternating optimization over flow matrices and the ground matrix.The bi-convex procedure can reach local optima and uses aggressive but less stable updates; face-verification experiments show improvements over standard histogram distances and Mahalanobis learning.

4.5 Generalization Guarantees for Metric Learning

The section frames generalization in metric learning as two-fold: consistency between training and unseen-data performance, and the downstream predictor’s performance. It reviews guarantees for supervised and online methods while noting that classifier-level links remain largely open.

  • Two-fold generalization question: Metric-learning generalization has two aspects: metric consistency and relating the learned metric’s performance to that of a downstream predictor.The predictor may be k-NN or a linear classifier.
  • Metric consistency bounds: Supervised metric learning admits generalization analysis through regularized losses on training pairs or triplets, but their dependence violates the i.i.d. assumption.The section describes establishing such guarantees as challenging and only recently investigated theoretically.
  • Regret bound conversion for online methods: Online analyses derive pairwise-loss generalization frameworks because standard regret-to-generalization conversions apply only to univariate loss functions.The online algorithm pairs each new instance with all previously seen data points.
  • Link between learned metric and classification performance: Classifier-level generalization remains largely open, with guarantees established for learned similarities and linear classifiers under (ε, γ, τ)-goodness.Guo and Ying extend these results to several matrix norms using Rademacher complexity analysis.

4.6 Semi-Supervised Metric Learning Methods

Semi-supervised metric learning incorporates unlabeled pairs through manifold, auxiliary-metric, or information-theoretic regularization, and extends to domain adaptation when source and target distributions differ. These methods can improve performance under scarce side information or covariate shift, but may incur computational or optimization difficulties.

  • Standard semi-supervised metric learning: LRML uses a graph-Laplacian regularizer built from Euclidean-neighborhood similarities to keep nearby points close in the learned metric.The regularizer favors an affinity-preserving metric by penalizing distances between points considered similar according to the weight matrix W.
  • Standard semi-supervised metric learning: LRML significantly outperforms supervised methods when side information is scarce, but computing its similarity matrix W is intractable for large-scale datasets.Several extensions refine W or replace the manifold regularizer with related formulations.
  • Standard semi-supervised metric learning: M-DML combines Laplacian regularizers from auxiliary metrics and learns their weights jointly with the target metric through alternating optimization.Experiments on face recognition show that auxiliary datasets can improve performance over LRML, although the alternating procedure converges only to a local minimum.
  • Standard semi-supervised metric learning: SERAPH maximizes entropy on labeled pairs and minimizes it on unlabeled pairs, while trace-norm regularization encourages a low-rank projection.Its resulting nonconvex problem is solved with an EM-like procedure whose M-step projects onto the positive semidefinite cone.
  • Semi-supervised domain adaptation: CDML adapts metric learning to covariate shift by weighting pairs according to source-target importance weights estimated from unlabeled data.The adapted ITML outperforms regular ITML under real or simulated covariate shift.
  • Semi-supervised domain adaptation: DAML regularizes kernelized metric learning with empirical MMD to reduce the discrepancy between source and target distributions while satisfying labeled source constraints.MMD is efficiently computed with the kernel trick and yields a convex regularizer in kernelized metric learning algorithms.

5. Metric Learning for Structured Data

Metric learning for structured data uses learned similarities to access strings, trees, and graphs through metric-based algorithms without directly manipulating complex objects. The survey focuses on string edit-distance learning, including stochastic and optimization-based methods, while noting computational and metric-property limitations.

  • Structured data: Structured metrics provide proxies for accessing strings, trees, and graphs, enabling metric-based algorithms designed for feature vectors to operate on complex data.Examples include words, documents, DNA sequences, XML documents, RNA structures, parse trees, networks, 3D objects, and molecules.
  • String edit distance: Standard Levenshtein distance assigns unit costs to insertion, deletion, and substitution, which may poorly reflect task-specific error probabilities or domain knowledge.Hand-tuned cost matrices may be available for protein alignment and handwritten digit recognition.
  • String edit distance: Stochastic edit-distance methods define probability distributions over edit operations and estimate parameters with EM, but the resulting edit similarity is often asymmetric and non-metric.Posterior-probability similarities rarely satisfy the triangular inequality.
  • Learning methods: EM-based learning may converge to a local optimum and repeatedly recompute parameter estimates and distances, making it costly for large alphabets or long strings.Optimization-based methods instead formulate learning as an efficiently solvable gradient-descent problem.
  • Learning methods: GESL learns the edit-cost matrix to optimize the (ε, γ, τ)-goodness of an edit similarity, providing generalization guarantees for the similarity and its resulting linear classifier.The approach optimizes a simplified edit-distance variant and can be adapted to tree or graph edit distances.

6. Conclusion and Discussion

The survey finds that metric learning for numerical feature vectors has matured, while structured-data metric learning remains less developed and often intractable at scale. It identifies scalability, theory, unsupervised learning, structural bias, adaptation to changing data, and richer notions of similarity as important future directions.

  • Conclusion: Metric learning for numerical feature vectors has reached maturity, with scalable methods covering online learning, nonlinear and local metrics, and difficult settings.Online approaches improve scalability, while nonlinear or local learning addresses complex tasks.
  • Conclusion: Structured-data metric learning remains less developed because advances for numerical data have not propagated, and EM-like methods are often intractable and difficult to analyze.Recent methods such as GESL show that feature-vector formulations can inspire progress for structured data.
  • Scalability with both n and d: Most methods learn O(d2) parameters, making high-dimensional metric learning intractable for thousands of features unless dimensionality reduction is applied beforehand.Kernelized methods instead use O(n2) parameters, which is infeasible when the dataset is large.
  • More theoretical understanding: Theoretical understanding remains limited: results exist for linear classification, but none are known for k-NN classification, clustering, or information retrieval.An open problem is linking learned-metric consistency to performance in a particular algorithm.
  • Future directions: Future work should develop unsupervised criteria, exploit data structure, and create metrics robust to noise, transformations, and changing distributions.Lifelong learning requires detecting concept drift and adapting the metric to different changes; structural bias has already improved histogram-data performance.
  • Learning richer metrics: Existing algorithms should model multimodal similarity and varying similarity degrees while making the reasons for similarity interpretable.Current methods largely use a binary similar/dissimilar view and ignore multiple feature-based ways that instances may be similar.
Loading 1306.6709v4…