Source-linked AI summary
No Fuss Distance Metric Learning using Proxies
Yair Movshovitz-Attias, Alexander Toshev, Thomas K. Leung, Sergey Ioffe, Saurabh Singh
TL;DR
Distance metric learning is difficult to optimize because triplet-based losses require selecting informative pairs or triplets from a vast space of possibilities. The paper learns a small set of proxy points, optimizes proxy-based losses that upper-bound the original losses, and reports faster convergence and state-of-the-art zero-shot results on three datasets.
Problem
Triplet-based metric learning requires informative sampling, while the number of possible triplets makes exhaustive coverage impractical and slows optimization.
Method
The method learns a small proxy set that approximates the data and replaces sampled instance triplets with proxy-based losses, which upper-bound the original losses.
Results
The proxy-based approach improves state-of-the-art performance on CUB200, Cars196, and Stanford Products, while converging faster than other metric-learning approaches.
Takeaways & Limitations
Proxies serve as auxiliary variables for more effective embedding optimization and help explain why classifier penultimate-layer embeddings can work well.
Takeaways & Limitations
The stated loss bounds rely on constant proxy and data-point norms, and the experiments enforce this by rescaling embeddings and proxies to the unit sphere.
Abstract
from arXiv · showhide
We address the problem of distance metric learning (DML), defined as learning a distance consistent with a notion of semantic similarity. Traditionally, for this problem supervision is expressed in the form of sets of points that follow an ordinal relationship -- an anchor point $x$ is similar to a set of positive points $Y$, and dissimilar to a set of negative points $Z$, and a loss defined over these distances is minimized. While the specifics of the optimization differ, in this work we collectively call this type of supervision Triplets and all methods that follow this pattern Triplet-Based methods. These methods are challenging to optimize. A main issue is the need for finding informative triplets, which is usually achieved by a variety of tricks such as increasing the batch size, hard or semi-hard triplet mining, etc. Even with these tricks, the convergence rate of such methods is slow. In this paper we propose to optimize the triplet loss on a different space of triplets, consisting of an anchor data point and similar and dissimilar proxy points which are learned as well. These proxies approximate the original data points, so that a triplet loss over the proxies is a tight upper bound of the original loss. This proxy-based loss is empirically better behaved. As a result, the proxy-loss improves on state-of-art results for three standard zero-shot learning datasets, by up to 15% points, while converging three times as fast as other triplet-based losses.
1. Introduction
Distance metric learning supports several computer-vision tasks, but triplet-based formulations are difficult to optimize because informative sampling is crucial. The paper replaces data-point triplets with learned proxy triplets, yielding an easier-to-optimize loss with faster convergence and improved zero-shot results.
- Distance metric learning has been used for image retrieval, near-duplicate detection, clustering, and zero-shot learning.
- Triplet loss learns a distance where an anchor is closer to a similar point than to a dissimilar point.
- Informative pair or triplet sampling is crucial for optimizing traditional losses and improving convergence rates.
- The proposed proxy-based loss replaces data-point triplets with triplets involving learned proxies that approximate the training data.Because the proxy set is smaller, the loss can explicitly include all or most proxy triplets.
- The proxy-based loss is an upper bound on triplet loss, with bound tightness improving empirically as training converges.
- Proxy-based learning improves state-of-the-art zero-shot results on CUB200, Cars196, and Stanford Products, while converging faster than other metric-learning approaches.
2. Related Work
Prior deep metric-learning methods commonly use pairs or sampled triplets, but sampling can be expensive, unstable, or slow. The proxy-based approach compares full example sets while training embeddings and proxies end-to-end without periodically recomputing clusters or class indices.
- Deep metric learning in computer vision has used contrastive, triplet, structured, N-pair, and distribution-based losses.
- Siamese contrastive loss pulls same-class embeddings together and pushes different-class embeddings apart, but does not directly model relative distances between classes.
- Large-margin nearest-neighbor methods define losses over sampled triplets, making sampling prohibitive as classes and training instances grow.
- Semi-hard negative mining improves training stability but requires large mini-batches and remains slow.The cited example used mini-batches of 1800 images.
- Lifted Structured Embedding and N-pair Loss incorporate information beyond a single triplet through batch-wide comparisons.
- Magnet Loss represents classes with multiple k-means cluster centers but periodically pauses training to recompute assignments.
- The proxy-based approach compares full example sets while training embeddings and proxies end-to-end without interrupting training to recompute clusters or class indices.
3. Metric Learning using Proxies
Proxy-based metric learning replaces sampled data triplets with triplets involving a compact learned proxy set, reducing comparisons while preserving the desired ranking relationships through bounded losses.
- Distance metric learning seeks a distance where each anchor is closer to a similar point than to a dissimilar point.
- The ideal ranking loss is difficult to optimize because its Heaviside-based gradient is zero everywhere, motivating surrogate losses such as NCA and margin-based triplet loss.
- Triplet learning faces a sampling bottleneck because datasets generate O(n^3) possible triplets while a batch exposes only O(b^3) samples.
- Proxies form a small set P that approximates the data, with each data point assigned a nearby proxy under the learned distance.
- Figure 2 illustrates a reduction from 48 instance triplets to 8 proxy comparisons.
- Using proxies reduces the number of triplets and implicitly encourages the original training data to satisfy the desired distance relationships.
- Proxy replacement preserves an ordinal relationship when the proxy-distance difference exceeds 2ϵ, supporting bounds on the original ranking loss.
4. Training
Training minimizes proxy-based upper bounds instead of losses over all original triplets. Learned proxies can aggregate many original triplets, with bound quality depending on approximation error and proxy count.
- Proxy-NCA minimizes an upper bound defined over an anchor and proxy positives and negatives rather than the total loss over original triplets.
- Proxy vectors are initialized and optimized with the network by gradient descent as part of Proxy-NCA training.
- Each proxy triplet upper-bounds all original triplets sharing its positive and negative proxies, allowing simple proxy sampling and faster convergence.
- Proxy Assignment and Triplet Selection: Static assignment associates one proxy with each semantic label, eliminating the need to sample triplets when labels define supervision.
- Proxy Assignment and Triplet Selection: Dynamic assignment maps each point to its closest proxy and applies when semantic labels are unavailable.
- Proxy Loss Bounds: The proxy approximation error decreases with more proxies, while the bound contains O(n|P|^2) terms, requiring a balance between accuracy and loss size.
- Proxy Loss Bounds: Under constant-norm assumptions for proxies and data points, the paper establishes proxy bounds for NCA and margin triplet losses.
5. Implementation Details
Experiments use a common pretrained Inception-based implementation with 64-dimensional embeddings and standardized image preprocessing. Results are reported for several proxy and baseline methods under fair-comparison settings.
- The implementation follows prior baseline details and avoids multiple random crops at test time for fair comparison.
- All methods use Inception with batch normalization, pretrained on ILSVRC 2012-CLS and finetuned on the tested datasets.
- The learned embeddings have dimension 64, and inputs are resized to 256 × 256 pixels before random 227 × 227 crops.
- Results remain stable with larger batch sizes for the proposed method.
- Most experiments use Proxy-NCA, with Proxy-Triplet additionally evaluated on one dataset.
6. Evaluation
The evaluation compares proxy-based metric learning with established methods on unseen classes across three datasets, measuring retrieval and clustering quality. Proxy-NCA improves reported state-of-the-art results, converges faster, and remains competitive with reduced proxy-to-label ratios.
- Evaluation protocol: The evaluation measures retrieval at k and clustering quality on unseen classes from CUB200-2011, Cars196, and Stanford Online Products.Clustering quality is measured with Normalized Mutual Information (NMI), which is invariant to label permutation.
- Evaluation protocol: Proxy-based methods are compared with semi-hard Triplet Learning, Lifted Structured Embedding, N-Pairs, and Learnable Structured Clustering using the same data splits.The comparison covers four state-of-the-art deep metric learning approaches.
- Cars196: 15 percentage points in recall@1 and 6% points in NMI separate Proxy-NCA from previous state of the art on Cars196.The recall@1 improvement is also reported as 26% relative.
- Stanford Online Products: Over a 6% gap in recall@1 and an NMI score of 90.6 show Proxy-NCA outperforming the comparison on Stanford Online Products.The top comparison method has an NMI score of 89.48, and the difference is statistically significant.
- CUB200: Proxy-NCA improves state of the art for recall at 1-2 and the clustering metric on CUB200, although all methods perform less well there than on the other datasets.The dataset is challenging because within-class variation is large relative to between-class variation.
- Convergence Rate: Proxy-NCA converges about three times as fast as other metric learning methods by retaining proxies in memory and eliminating tuple sampling and hard-negative mining.The proxies persist between batches, supporting the reported training-speed advantage.
- Proxy assignment: Proxy-NCA compares favorably with previous state of the art when using 0.5 proxies per semantic label or more.The proxy-to-label ratio is varied to examine settings where computational resources do not permit one proxy per label.
7. Discussion
The paper presents proxies as effective auxiliary variables for deep metric learning, reducing training time while achieving state-of-the-art results. Proxy-NCA also explains why classifier-based embedding training can work without retaining the classifier.
- Discussion: Proxies reduce training time and produce models achieving a new state of the art in deep metric learning.The paper stores proxies in memory and trains them using back-propagation.
- Discussion: The method uses static proxy assignment when semantic labels are available and dynamic assignment when supervision consists of similar and dissimilar triplets.
- Discussion: A proxy-defined loss upper bounds the original instance-based loss.
- Discussion: With constant proxy and instance norms, a well-optimized proxy model preserves ordinal relationships between instance pairs.
- Discussion: Proxy-NCA uses proxies as auxiliary variables for optimizing embeddings, then discards them after training rather than treating them as the final classifier.
- Discussion: Proxy-NCA's similarity to cross-entropy offers an explanation for using a classifier's penultimate-layer output as an embedding.
Appendix
The appendix bounds the normalized instance-based NCA loss using proxy-based dot-product bounds and assumptions on instance and proxy norms. The derivation proceeds through Cauchy and Hölder inequalities to obtain the final bound.
- Appendix: Cauchy-based bounds replace normalized instance dot products with corresponding proxy dot products for positive and negative terms.
- Appendix: The resulting bounds upper-bound the original normalized NCA loss using a proxy-defined loss.
- Appendix: Assuming β = 1/(N_xN_p) < 1, Hölder's inequality bounds the sum of exponential terms.
- Appendix: The propositions follow by applying the derived equations to establish the final bound for β = 1/(N_xN_p).
- Appendix: For normalized vectors, the triplet hinge term can be rewritten using dot products as -2x̂ᵀŷ + 2x̂ᵀẑ + M.
- Appendix: The derivation converts the normalized-vector loss to an unnormalized-vector loss under constant-norm assumptions.