Mirror Descent for Metric Learning: A Unified Approach

Gautam Kunapuli, Jude Shavlik

@inproceedings{kunapuli2012mirror,
    author="Kunapuli, Gautam and Shavlik, Jude",
    editor="Flach, Peter A. and De Bie, Tijl and Cristianini, Nello",
    title="Mirror Descent for Metric Learning: A Unified Approach",
    booktitle="Machine Learning and Knowledge Discovery in Databases",
    year="2012",
    publisher="Springer Berlin Heidelberg",
    address="Berlin, Heidelberg",
    pages="859--874",
    isbn="978-3-642-33460-3",
    doi="10.1007/978-3-642-33460-3_60",
    url="https://doi.org/10.1007/978-3-642-33460-3_60"
}

Abstract

“Most metric learning methods are characterized by diverse loss functions and projection methods, which naturally begs the question: is there a wider framework that can generalize many of these methods? In addition, ever persistent issues are those of scalability to large data sets and the question of kernelizability. We propose a unified approach to Mahalanobis metric learning: an online regularized metric learning algorithm based on the ideas of composite objective mirror descent (comid). The metric learning problem is formulated as a regularized positive semi-definite matrix learning problem, whose update rules can be derived using the comid framework. This approach aims to be scalable, kernelizable, and admissible to many different types of Bregman and loss functions, which allows for the tailoring of several different classes of algorithms. The most novel contribution is the use of the trace norm, which yields a sparse metric in its eigenspectrum, thus simultaneously performing feature selection along with metric learning.”

1. Introduction

“In this work, we consider the Mahalanobis metric learning problem applied to -nearest neighbors classification. The Mahalanobis metric is a distance function that is of the form .”

1.1 Problem Setting

“…. We formulate the problem in the spirit of Shalev-Shwartz et al. [9]¹, where the goal is to incrementally learn a metric, given triplets of the form . The label indicates that training point is similar to and indicates dissimilarity.”

“The metric we learn is of the form , where is a linear transformation. Since learning this metric directly is difficult owing to non-convexity, we consider instead:”

“with , the cone of positive semi-definite (psd) matrices. Given labeled pairs of points… we learn …. This condition can be formulated via the constraints”

“which can be written simply as . …. We define the margin function for a pair of instances and , given a label , as”

“This lets us define several loss functions….”

“[W]e also incorporate regularization into the problem so that the resulting metric has sparsity. [M]inimizing the trace-norm of i.e., the sum of the singular values of yields sparsity in the spectrum of , thus minimizing the rank of . Given samples, the overall problem is one of regularized loss minimization, which leads to an optimization problem of the form”

“where the loss function and the regularization function are both convex and is the regularization parameter.”

1.2 Notation and Background

“The Bregman divergence [13]² with respect to a strictly convex function is defined as .”

2. Mirror Descent for Metric Learning

“The mirror descent algorithm [14]³ is an iterative proximal-gradient method for minimizing a convex function, . Based on this approach, an update in the online setting, with function is”

“Recently, Duchi et al. [15]⁴ generalized mirror descent to the case where the functions are composite, consisting of loss and regularization terms:”

“The subtle, yet significant difference between and is that the entire composite function is not linearized. Rather, only is linearized; this leads to the composite mirror descent algorithm (COMID). The reason for this partial linearization is because general mirror descent applied to -regularization does not lead to sparse updates, whereas the COMID update does.”

“[W]e … formulate metric learning as an online problem. …. The goal is to optimize the objective in an online manner i.e. at each iteration… the algorithm receives a labeled pair of points…, which has an associated loss function , and the estimates and are calculated using a composite mirror descent update rule. Since we are interested in sparse updates as well, we use the trace norm, , the effect of which is controlled via a regularization parameter . …. At each step, we compute updates given a learning rate , … according to”

“This metric learning formulation has several advantages:”

1. General framework.
2. Scalable to large data sets.
3. Trace-norm regularization produces sparse metric.
4. Theoretical regret guarantees.
5. Kernelizable for nonlinear metric learning.

2.1 Loss Functions

2.2 Bregman Divergences

3. Deriving Update Rules for and

“The update rule can be broken down into two separate updates:”

“The gradient condition of : , gives us the intermediate solution: , which can be used to solve ”

Proposition 1. The optimal solution to is given by

where

Proposition 2. The optimal solution to is given by

4. Implementing Update Rules for

“At the -th iteration, with we have:”

“The complete algorithm is described below.”

Algorithm 1 Mirror Descent for Metric Learning

1. input: data , parameters
2. choose: Bregman functions ; , loss function
3. initialize:
4. for do
5. let ,
6. compute gradients of loss and
7. write
8. compute symmetric rank-one update
9. shrink the eigenvalues
10. margin update
11. end for

5. Kernel MDML

6. Related Work

7. Experiments

7.1 Benchmark Data Sets

7.2 Digit Recognition

8. Conclusions and Future Work

“Given that the updates are embarrassingly parallelizable, an immediate target is the massive data setting, where we need to learn with millions of data points. In addition, the approach is also amenable to the addition of local geometry constraints in order to learn low-dimensional geometry-aware metrics that lead to representable models. Finally, the kernel-MDML approach is a very powerful extension to linear metric learning, with applications in colored dimensionality reduction and manifold alignment.”

References