PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometric Mean Metric Learning

Pourya Habib Zadeh, Reshad Hosseini, Suvrit Sra

arXiv:1607.05002v1stat.MLcs.LG

TL;DR

The paper addresses how to learn a Euclidean metric from weakly supervised data. It introduces GMML as a geometrically motivated smooth strictly convex optimization problem with a closed-form solution, and reports faster computation with equal or higher classification accuracy than competing methods.

  • Problem

    Euclidean metric learning must select a distance function from weakly supervised information such as similar and dissimilar point pairs.

  • Method

    GMML formulates learning an SPD matrix as a smooth, strictly convex optimization problem and obtains a closed-form matrix geometric-mean solution.

  • Results

    GMML consistently delivers equal or higher classification accuracy while running up to three orders of magnitude faster than widely used metric learning methods.

  • Takeaways & Limitations

    The method provides a fast, scalable metric-learning solution with geometric interpretation and closed-form computation.

Abstract

from arXiv · show

We revisit the task of learning a Euclidean metric from data. We approach this problem from first principles and formulate it as a surprisingly simple optimization problem. Indeed, our formulation even admits a closed form solution. This solution possesses several very attractive properties: (i) an innate geometric appeal through the Riemannian geometry of positive definite matrices; (ii) ease of interpretability; and (iii) computational speed several orders of magnitude faster than the widely used LMNN and ITML methods. Furthermore, on standard benchmark datasets, our closed-form solution consistently attains higher classification accuracy.

I. INTRODUCTION

The paper revisits Euclidean metric learning under weak supervision and introduces GMML as a simple, geometrically motivated alternative. Its closed-form solution is reported to be substantially faster while matching or improving classification accuracy against established methods.

  • Metric learning selects a task-specific distance function from supervised or weakly supervised data.
  • The paper learns a Mahalanobis distance represented by an SPD matrix A from pairs of similar and dissimilar points.
  • GMML formulates Euclidean metric learning from geometric reasoning as an unconstrained, smooth, strictly convex optimization problem.
  • The formulation has a closed-form solution connected to the Riemannian geometry of SPD matrices, explaining the GMML name.
  • GMML runs up to three orders of magnitude faster while consistently delivering equal or higher classification accuracy than widely used metric learning methods.

A. Related work

Related work includes constraint-based, divergence-based, and Riemannian approaches to Euclidean metric learning. GMML differs by emphasizing a new formulation with a closed-form solution and reported scalability benefits.

  • Earlier metric learning methods such as MMC minimize distances among similar points while encouraging dissimilar points to remain far apart.
  • MMC optimizes with gradient descent and projection onto the positive semi-definite cone, while related costs also appear in LMNN and MCML.
  • ITML satisfies similarity and dissimilarity constraints while remaining close to a predefined matrix under LogDet divergence.
  • Another formulation uses Riemannian techniques and reports good classification performance without a regularizer.
  • GMML focuses on formulating Euclidean metric learning and has a closed-form solution reported as three orders of magnitude faster than established competitors.

II. GMML: FORMULATION AND SOLUTION

GMML incorporates dissimilar points through inverse-metric distances, yielding a geometrically motivated objective whose gradients and monotonicity explain the design. The formulation supports a smooth optimization treatment.

  • II. GMML: FORMULATION AND SOLUTION: Euclidean metric learning seeks small distances for similar points and large distances for dissimilar points.
  • II. GMML: FORMULATION AND SOLUTION: GMML decreases distances among similar points while incorporating dissimilar points through distances measured with A^-1.
  • II. GMML: FORMULATION AND SOLUTION: The inverse-distance notation ˆd_A abbreviates d_A−1 in the subsequent derivation.
  • A. Insights: The objective is motivated by increasing Mahalanobis distances between dissimilar points by decreasing their inverse-metric distances.
  • A. Insights: Because d_A increases monotonically with A while ˆd_A decreases monotonically, reducing the latter supports enlarging the former.
  • A. Insights: The inverse-order relation A ≻ B implies A^-1 ≺ B^-1 for positive definite matrices.
  • A. Insights: The gradients of d_A and ˆd_A point in nearly opposite directions, so infinitesimally decreasing d_A increases ˆd_A.

B. Optimization problem and its solution

GMML rewrites metric learning as an optimization over SPD matrices whose cost is strictly convex in both ordinary and geodesic senses. Its unique minimizer is the matrix geometric mean, equivalently the geodesic midpoint between S^-1 and D.

  • Optimization problem: GMML rewrites the Mahalanobis metric-learning objective as an optimization problem over SPD matrices using similarity and dissimilarity second-moment matrices.S and D are scaled second sample moments of differences between similar and dissimilar points, respectively.
  • Geometric structure: The SPD matrices form a geodesically convex Riemannian manifold, allowing convexity to be analyzed along geodesics.Geodesic convexity generalizes ordinary convexity to nonlinear manifolds, and the SPD manifold has nonpositive curvature.
  • Convexity: The GMML cost function is both strictly convex and strictly geodesically convex on the SPD manifold.Strict convexity ensures that any stationary point is the global minimizer.
  • Closed-form solution: The stationary condition ∇h(A)=0 yields the Riccati equation ASA=D.Because the optimization constraint set is open and the objective is strictly convex, solving the zero-gradient condition identifies the global minimum.
  • Closed-form solution: The unique solution is the midpoint of the geodesic joining S^-1 and D, namely their matrix geometric mean.The resulting solution is SPD and therefore satisfies the optimization constraint.

C. Regularized version

The regularized GMML variant addresses non-invertible or near-singular S and can incorporate a prior SPD matrix. It retains a closed-form solution, with stronger regularization moving the result toward the prior.

  • Motivation: Regularization addresses cases where the similarity matrix S is non-invertible or near-singular and can incorporate prior knowledge about the distance function.The prior is represented by an SPD matrix A0.
  • Solution: The regularized optimization problem also has a closed-form solution.The solution is obtained after applying the symmetrized LogDet divergence as the regularizer.
  • Solution: The solution is a regularized geometric mean of suitably modified S and D matrices.The regularization parameter is λ ≥ 0.
  • Effect of regularization: As λ increases, Areg becomes more similar to the prior matrix A0.This gives the regularizer a direct effect on the balance between the learned metric and prior knowledge.
  • Geometric interpretation: Figure 1 places the GMML solution on the geodesic between S^-1 and D on the SPD manifold.

D. Extension to weighted geometric mean

The weighted GMML formulation uses a geodesic parameter t to balance similarity and dissimilarity costs, yielding a weighted geometric-mean solution on the SPD manifold. The method also provides regularization and an algorithmic procedure for computing the resulting distance matrix.

  • D. Extension to weighted geometric mean: The geodesic viewpoint introduces t to control the balance between similarity and dissimilarity matrices.Simply rescaling the cost does not provide a meaningful balance because it only scales A by a constant.
  • D. Extension to weighted geometric mean: The weighted objective is geodesically convex even though it is not Euclidean convex.This preserves the optimization structure needed for the weighted formulation.
  • D. Extension to weighted geometric mean: The unique solution is the weighted geometric mean, a point on the geodesic from S−1 to D.For t = 1/2, the generalized solution reduces to the ordinary midpoint solution.
  • D. Extension to weighted geometric mean: The practical method includes regularization for non-invertible or near-singular S and can incorporate a prior distance matrix.The algorithm takes S, D, t, λ, and prior knowledge A0 as inputs before computing the distance matrix.
  • D. Extension to weighted geometric mean: The generalized solution with free t can significantly outperform the ordinary solution empirically.The paper summarizes the complete procedure in Algorithm 1 and uses the Cholesky-Schur method to expedite geodesic computation.

III. RESULTS

The results section evaluates GMML against established metric-learning methods using k-nearest-neighbor classification error and full-rank learned matrices. The comparison includes GMML, FlatGeo, and other well-known approaches.

  • III. RESULTS: GMML is evaluated against well-known metric-learning algorithms using k-NN classification error on different datasets.The experiments use k = 5 and estimate a full-rank matrix A for all methods.

A. Experiment 1

Experiment 1 compares GMML with ITML, FlatGeo, LMNN, and Euclidean distance on small UCI datasets. GMML outperforms the other metric-learning methods, while tuning t can substantially improve its performance on some datasets.

  • A. Experiment 1: The experiment uses 40c(c −1) randomly selected pair constraints for GMML, ITML, and FlatGeo, while LMNN uses Bayesian hyper-parameter optimization.ITML regularization is selected by cross-validation, and FlatGeo uses a minimum-iteration setting.
  • A. Experiment 1: GMML outperforms the other three metric-learning methods on the smaller UCI datasets.The comparison includes Euclidean distance as a classification baseline and reports results over 40 random two-fold splits.
  • A. Experiment 1: The parameter t is selected by five-fold cross-validation from 18 tested values.A coarse search uses {0.1, 0.3, 0.5, 0.7, 0.9}, followed by a local search over 12 values near the best candidate.
  • A. Experiment 1: Varying t from the ordinary to the extended GMML formulation can substantially improve performance on some datasets.The accuracy curves are convex-like with some wiggling, motivating the two-stage parameter search.

B. Experiment 2

Experiment 2 evaluates GMML on larger datasets, including Isolet, Letters, MNIST, and USPS, using repeated random splits and cross-validation. GMML matches LMNN on two datasets, significantly outperforms it on one, and is significantly outperformed on one, while retaining a major computational-speed advantage.

  • B. Experiment 2: The large-dataset experiment uses Isolet, Letters, MNIST, and USPS.Figure 4 reports average classification error over five random data splits, with three-fold cross-validation for t.
  • B. Experiment 2: GMML matches LMNN on Letters and USPS, significantly outperforms it on one dataset, and is significantly outperformed on another.The passage reports the comparison at the dataset level without specifying the corresponding dataset names for the latter two outcomes.
  • B. Experiment 2: Using more data pairs improves GMML accuracy by about 1 percent on Isolet and about 0.5 percent on MNIST.The Isolet result yields slightly better performance than FlatGeo, while MNIST also improves with the larger pair set.
  • B. Experiment 2: GMML is several orders of magnitude faster than the other methods in the reported running-time comparison.The running times exclude hyper-parameter-selection time and support GMML as a candidate for large-scale metric learning.

IV. CONCLUSION AND FUTURE WORK

The paper formulates weakly supervised Euclidean metric learning through geometric optimization over SPD matrices, yielding closed-form solutions with strong practical properties. Experiments report good classification accuracy, global optimality, speed, and scalability.

  • The method learns an SPD matrix through a smooth, strictly convex optimization problem, ensuring a unique solution.
  • Riemannian geometry of the SPD manifold enables weighted and regularized formulations whose solutions are closed-form matrix geometric means.
  • Experiments compare k-NN classification accuracy across several datasets using metrics learned by the proposed and competing methods.
  • The proposed method combines good classification accuracy and global optimality with speed and scalability in dimensionality d and sample count n.
  • The formulation’s simplicity, interpretability, and speedup over widely used methods make it attractive for metric-learning applications.

A. Future work

The paper identifies future work extending its geometric metric-learning framework and applying it beyond the current setting.

  • A. Future work: Future work includes interpreting the metric-learning methods as a dimensionality-reduction method.
  • A. Future work: The framework could be extended to learn nonlinear and local metrics.
  • A. Future work: Another direction is applying concurrent use of dA and its counterpart ˆdA to other machine-learning problems.
Loading 1607.05002v1…