Source-linked AI summary
Ground Metric Learning
Marco Cuturi, David Avis
TL;DR
Transportation distances compare histograms, but their feature-space ground metric has typically depended on prior knowledge, limiting where they can be applied. This paper learns that metric from labeled histogram training data, and reports superior average performance on GIST-based image classification tasks. The approach uses a projected subgradient method and can find only local minimizers.
Problem
Transportation distances depend on a ground metric between features, but prior applications relied on a metric motivated by prior knowledge, limiting their scope.
Source: §1 · pp. 1–2Method
The paper learns a ground metric from labeled histograms by minimizing a difference of convex functions over distance matrices using projected subgradient descent.
Source: §1 · p. 2, §8.1 · p. 24Results
GML-EMD provides the best average performance across the reported binary classifications, and the approach outperforms competing distances on a large set of GIST-based image classification tasks.
Source: §7.5 · p. 23, §8.1 · p. 24Takeaways & Limitations
The techniques may be useful for studying histograms of latent features, such as topics or dictionaries, where natural metrics are not always available.
Source: §8.3 · p. 28The computationally intensive part repeatedly computes O(n^2) optimal transportations between training-histogram pairs.
Source: §8.2 · p. 28
Abstract
from arXiv · showhide
Transportation distances have been used for more than a decade now in machine learning to compare histograms of features. They have one parameter: the ground metric, which can be any metric between the features themselves. As is the case for all parameterized distances, transportation distances can only prove useful in practice when this parameter is carefully chosen. To date, the only option available to practitioners to set the ground metric parameter was to rely on a priori knowledge of the features, which limited considerably the scope of application of transportation distances. We propose to lift this limitation and consider instead algorithms that can learn the ground metric using only a training set of labeled histograms. We call this approach ground metric learning. We formulate the problem of learning the ground metric as the minimization of the difference of two polyhedral convex functions over a convex set of distance matrices. We follow the presentation of our algorithms with promising experimental results on binary classification tasks using GIST descriptors of images taken in the Caltech-256 set.
1 Introduction
The paper addresses how to choose the feature metric that parameterizes transportation distances between histograms, proposing to learn it from labeled training data. It positions this as a way to move beyond applications where prior knowledge already supplies a suitable metric.
1 Introduction
- Histograms represent feature frequencies in objects such as images, texts, sequences, and graphs, and transportation distances compare such histograms.The paper focuses on transportation distances, also known as Earth Mover’s Distances in computer vision.Source: §1 · pp. 1–2
- The ground metric is the unique feature-space parameter of transportation distances, but prior applications relied on a metric justified by prior knowledge.The authors argue that this restricts applications and that no universal ground metric suits every histogram-learning problem.Source: §1 · p. 2
- The paper proposes criteria and subgradient descent algorithms to learn a ground metric from labeled histograms, reporting favorable comparisons with competing distances.It also considers initialization strategies and reviews related distances and metric-learning techniques.Source: §1 · pp. 2–3
Notations
- The paper uses “metric” for distances between features and “distance” for the resulting transportation distance between histograms.Matrices use uppercase letters, vectors lowercase letters, and the Frobenius dot product is used for matrix and vector representations.Source: §1 · p. 2, Notations · p. 3
2 Optimal Transportation Between Histograms
The section defines transportation between normalized histograms through feasible transport plans and a cost determined by a feature metric. It then describes the resulting histogram distance and properties used in later optimization.
2 Optimal Transportation Between Histograms
- The section reviews mass transportation, pointing to theoretical introductions, practical machine-learning motivation, and reviews of EMD extensions.It cites Villani (2003), Rubner et al. (2000), and Pele and Werman (2009) for these perspectives.Source: §2 · p. 3
2.1 Transportation Polytopes
- U(r, c) is the polytope of nonnegative transport plans whose row and column marginals equal the two normalized histograms.When both histograms have positive coordinates, its dimension is d^2 − 2d + 1.Source: §2.1 · pp. 3–4
2.2 Transportation Distances
- The transportation distance is the minimum linear transport cost over plans constrained by the histograms’ marginals, with the cost parameterized by a feature metric.The distance can be computed as a linear program; the constraints encode row and column sums, and network simplex or specialized network-flow algorithms can solve it.Source: §2.1 · p. 4, §2.2 · p. 5
2.3 Properties of Grc
- For a metric matrix, the transportation distance is symmetric and nonnegative, and it is zero between identical histograms.The transport objective is piecewise linear and concave in its cost matrix; any optimal transport plan is a subgradient, which is used in later optimization.Source: §2.2 · p. 4, §2.3 · p. 5
3 Criteria for Ground Metric Learning
The section defines ground-metric criteria from histogram training data and side information, then develops global and neighborhood-based ways to score candidate metrics. It also constrains the metric search to avoid degenerate minimization.
3 Criteria for Ground Metric Learning
- The section introduces criteria that assess a ground metric for a task using training histograms and additional information.The paper frames metric selection around pairwise histogram similarities and induced transportation distances.Source: §3 · p. 5, §3.1 · p. 6
3.1 Training Set: Histograms and Side Information
- Pairwise weights encode similarity: positive values can mark same-class pairs and negative values different-class pairs, as in the experiments.The weights are symmetric, and self-similarity weights are set to zero.Source: §3.1 · p. 6
3.2 A Local Criterion to Select the Ground Metric
- The proposed criteria include an average of weighted pairwise distances and a restriction of that average to neighboring points.The pairwise criterion is symmetric so that histogram ordering does not affect it; the local criteria use k nearest neighbors selected by the induced distance.Source: §3.2 · p. 7
3.3 Metrics of Interest
- Because Ck is positively homogeneous, minimizing it over the metric cone can be unbounded or attain the trivial zero metric, so the search is restricted to a unit-norm slice.The resulting feasible set is closed, convex, and bounded, and the piecewise-linear criterion admits an optimum.Source: §3.3 · pp. 7–8
4 Ck as a Difference of Convex Functions
The section casts Ck as a difference of convex functions and describes a local-minimization algorithm using subgradients and localized linearization. Its local-minimum quality depends directly on the initialization.
4 Ck as a Difference of Convex Functions
- The proposed algorithm uses the difference-of-convex decomposition of Ck to obtain a local minimizer of Problem (P1).The decomposition follows because the Gij functions are concave and their weighted terms make the relevant components convex.Source: §4 · p. 8
4.1 Subdifferentiability of Ck
- Optimal solutions to the transportation linear programs provide subgradients of Gij, including when the solutions or nearest neighbors are not unique.When the solutions and each histogram’s k nearest neighbors are unique, the relevant solutions are unique; the algorithm computes objective values and subgradients.Source: §4.1 · p. 9
4.2 Localized Linearization of the Concave Part of Ck
- The algorithm repeatedly linearizes Ck’s concave part and minimizes a convex upper approximation with projected gradient descent.It uses nested loops, returns a metric after sufficient outer-loop progress, and the quality of the resulting local minimum is directly linked to the initial metric M0.Source: §4.2 · pp. 9–10
5 Initial Points
The initial-point strategy matters because subgradient descent converges to a local minimum whose quality depends on the starting point. The paper proposes linear approximations to choose an initialization, using representative transportation tables to construct them.
5 Initial Points
- Algorithm (2) converges to a local minimum, and its approximation of the global minimum depends on M0 being a good initial guess near the optimum.Source: §5 · p. 10
5.1 The l1 Distance as a Transportation Distance
- The l1 histogram distance supplies a starting point via the uniform ground metric, but this initialization does not use the training histograms or their weights.Source: §5.1 · pp. 10, 12
5.2 Linear Approximations to Ck
- The linear approximation χk is minimized over M1; for finite k, each histogram’s nearest neighbors must first be selected using M1.Source: §5.2 · p. 12
5.3 Representative Tables
- The method approximates each transportation distance using a dot product with a representative table from its transportation polytope, then approximates Ck by a linear function.Source: §5.3 · pp. 13–14, §5.3.2 · p. 16
5.3.1 Independence Table
- The independence table rcT is an easy-to-compute maximal-entropy table in U(r,c), but its approximation can substantially overestimate distances between similar histograms.Source: §5.3.1 · p. 14
5.3.2 Typical Table
- Typical tables provide an alternative representative point; the resulting initialization minimizes the linear approximation over the Frobenius-norm unit ball intersected with the metric cone.Source: §5.3.2 · pp. 14, 16
6 Related Work
The related work distinguishes histogram distances that compare bins independently from those that account for cross-bin relationships. It also separates ground metric learning from Mahalanobis and simplex metric-learning approaches.
6.1 Metrics on the Probability Simplex
- Bin-to-bin distances compare corresponding bin counts independently, while cross-bin distances account for relationships between different bins; bin-to-bin comparisons may be inadequate when features are similar.Source: §6.1 · p. 17
6.2 Mahalanobis Metric Learning
- Mahalanobis learning estimates a positive-semidefinite matrix or linear map, whereas ground metric learning produces a metric matrix, making them conceptually different approaches.Source: §6.2 · p. 18
6.3 Metric Learning in Σd−1
- Lebanon’s approach learns a simplex-distance perturbation from observed histograms without side information, so the paper excludes it from experiments focused on a different setting.Source: §6.3 · pp. 18–19
7 Experiments
The experiments section reports that ground metric learning improves on other state-of-the-art metric-learning techniques for normalized histograms. It also describes the optimization tools used to implement the algorithms.
7 Experiments
- The experiments report that ground metric learning improves upon other state-of-the-art metric-learning techniques on normalized histograms.Source: §7 · p. 19
7.1 Implementation Notes
- The implementation uses CPLEX network flows with warm starts for transportation problems, metricNearness for projections, and fminunc to compute typical tables.Source: §7.1 · p. 19
- When fminunc returns typical-table parameters that violate positivity constraints, the implementation switches to a slower constrained Newton method.Source: §7.1 · p. 19
7.2 Images Classification Datasets
The image-classification dataset uses normalized GIST-feature histograms from randomly sampled Caltech-256 classes. The evaluation forms binary tasks across two class groups and holds out images for testing.
7.2 Images Classification Datasets
- The dataset samples 2N Caltech-256 classes and uses 70 images from each class.Source: §7.2 · p. 19
- Each image is represented by a normalized, 128-dimensional histogram of GIST features.Source: §7.2 · pp. 19–20
- The classes are split into two groups of N, producing N² binary tasks across the groups, each with 30 images per class for training and 40 for testing.Source: §7.2 · p. 20
7.3 Distances used in this benchmark
The benchmark compares bin-to-bin distances, Mahalanobis distances learned on Hellinger representations, and ground metrics learned from labeled histogram pairs. GML uses same-class and different-class pair weights and tests several initial points and neighborhood settings.
7.3.1 Bin-to-bin distances
- The bin-to-bin comparison uses l1, l2, and Hellinger distances on GIST feature vectors.The supplied text names these distances but does not give complete formulas for all three.Source: §7.3.1 · p. 20
7.3.2 Mahalanobis distances
- LMNN and ITML learn Mahalanobis distances from Hellinger representations of the training histograms.The authors motivate this representation because Euclidean distance after the Hellinger map equals Hellinger distance.Source: §7.3.2 · p. 20
7.3.3 Ground Metric Learning
- GML weights same-class histogram pairs positively and different-class pairs negatively, then normalizes the weights and learns from multiple initial points.The neighborhood parameter is set to k = 3 for comparison with ITML and LMNN; the experiments vary initialization choices.Source: §7.3.3 · pp. 20–21
7.4 Comparison with the SVM baseline
The comparison evaluates distance-based SVM kernels alongside κ-nearest-neighbor results across 625 binary classification tasks. SVM parameters are selected by cross-validation on the training fold.
7.4 Comparison with the SVM baseline
- SVMs use exponentiated distance kernels, exp(−d/σ), with regularization and bandwidth selected by four-fold, two-repeat cross-validation.The bandwidth grid scales the training-set median distance, and the test fold contains 80 points against 60 training points.Source: §7.4 · p. 21
- The SVM training Gram matrices receive diagonal regularization sufficient to offset their smallest negative eigenvalue.The paper notes that transportation distances are not negative definite in general.Source: §7.4 · p. 21
- Figure 1 reports κ-NN classification error and same-class neighbor accuracy averaged over 625 tasks.Each task uses 30 + 30 training points and 40 + 40 test points; learned metrics are trained separately within each task.Source: Figure 1 · p. 22
7.5 Results
Across 625 binary classifications, GML-EMD provides the strongest reported neighbor-recall and κ-NN performance among the considered distances. Results also show sensitivity to neighborhood size and initialization, with typical tables tending to outperform independence tables as starting points.
7.5 Results
- GML-EMD gives the best average same-class neighbor recall and κ-NN performance among the considered distances across 625 tasks.Its κ-NN performance is directly comparable to SVMs using l1 or l2 kernels.Source: §7.5 · p. 23
- On these datasets, l2 performs worse than l1 and Hellinger, while Mahalanobis learning performs significantly better with Hellinger representations.The paper presents the latter comparison in Figure 2.Source: §7.5 · p. 23
- GML performance varies significantly with neighborhood parameter k, and descent improves on using the typical-table initialization alone.The typical-table-only curves are far below the GML-EMD curves using k = 3 with that initialization.Source: §7.5 · p. 23
- Barvinok’s typical tables tend to provide better initial points than independence tables in average performance, despite their computational overhead.Figures 3 and 4 use N = 10, compared with N = 25 in Figures 1 and 2.Source: §7.5 · pp. 23–24
8 Conclusion and Future Work
The paper learns transportation distances’ ground metrics from histogram training data and reports superior average performance on GIST image binary-classification tasks. It also identifies computational costs and proposes latent-feature histograms as a future application.
8.1 Overview
- Learned distances achieve superior average performance against competing distances on image binary-classification tasks using GIST feature histograms.The optimization finds only local minimizers.Source: §8.1 · p. 24
- The proposed approach adaptively tunes transportation distances’ ground metric from histogram training data, using projected subgradient descent on a difference of convex functions.It can use histograms with side-information, typically labels, and finds only local minimizers.Source: §8.1 · p. 24
8.2 Ground Metric and Computational Speed
- Mahalanobis learning methods perform better with Hellinger-represented histograms than with their straightforward simplex representation.Figure 2 compares two versions each of LMNN and ITML with the Hellinger distance.Source: Figure 2 · p. 25
- GML-EMD performance varies significantly with neighborhood parameter k; the k = 3 method improves over EMD using the typical-table initialization alone.The performance curves also suggest an advantage when the classifier’s κ is close to the metric’s k.Source: Figure 3 · p. 26
- For GML-EMD at k = 3, typical-table initialization performs better on average than independence-table initialization despite its computational overhead.Figure 4 reports distance accuracy and κ-nearest-neighbor performance.Source: Figure 4 · p. 27
- Algorithm 2’s repeated calls to Algorithm 1 are computationally intensive; each call computes O(n^2) optimal transportations for n training histograms.The paper notes that faster alternatives and efficient lower bounds could reduce this cost.Source: §8.2 · p. 28
8.3 Future Applications
- Learned ground metrics may help study histograms of latent features such as topics or dictionaries, for which natural metrics are not always available.The paper presents this as a future application.Source: §8.3 · p. 28