Source-linked AI summary
Deep Metric Learning via Lifted Structured Feature Embedding
Hyun Oh Song, Yu Xiang, Stefanie Jegelka, Silvio Savarese
TL;DR
Extreme classification makes conventional approaches impractical because the number of classes is enormous and training data per class is scarce. The paper lifts within-batch pairwise distances into a matrix, applies a structured loss, and reports significant improvements over existing methods across tested embedding dimensions and datasets.
Problem
Extreme classification involves enormous numbers of classes, making linear learning and inference impractical while leaving little training data per class.
Method
The method lifts O(m) pairwise distances within a batch to an O(m2) distance matrix and optimizes a novel structured loss objective.
Results
The proposed embedding significantly outperforms existing methods across experimented embedding dimensions and improves clustering and retrieval quality on previously unseen classes.
Takeaways & Limitations
The paper contributes a deep metric-learning embedding and the Online Products dataset, containing approximately 120k images across 23k product classes.
Takeaways & Limitations
The objective is non-smooth, and evaluating it or computing its subgradient requires mining all example pairs several times.
Abstract
from arXiv · showhide
Learning the distance metric between pairs of examples is of great importance for learning and visual recognition. With the remarkable success from the state of the art convolutional neural networks, recent works have shown promising results on discriminatively training the networks to learn semantic feature embeddings where similar examples are mapped close to each other and dissimilar examples are mapped farther apart. In this paper, we describe an algorithm for taking full advantage of the training batches in the neural network training by lifting the vector of pairwise distances within the batch to the matrix of pairwise distances. This step enables the algorithm to learn the state of the art feature embedding by optimizing a novel structured prediction objective on the lifted problem. Additionally, we collected Online Products dataset: 120k images of 23k classes of online products for metric learning. Our experiments on the CUB-200-2011, CARS196, and Online Products datasets demonstrate significant improvement over existing deep feature embedding methods on all experimented embedding sizes with the GoogLeNet network.
1. Introduction
Metric learning aims to map similar objects nearby and dissimilar objects apart, supporting recognition tasks through learned distance measures. The paper proposes a batch-level structured objective and evaluates it across established and newly collected datasets.
- Metric learning learns semantic distance measures that place similar inputs nearby and dissimilar inputs apart.Such measures can simplify classification through nearest-neighbor inference and support clustering through similarity matrices.
- Metric learning is appealing for extreme classification because it learns generic distance concepts and supports efficient nearest-neighbor inference.Extreme classification also faces impractical class-linear complexity and scarce training data per class.
- Existing deep embedding methods train networks to pull same-class examples together and push different-class examples apart, but do not fully exploit mini-batches.The proposed method lifts O(m) pairwise distances to an O(m^2) distance matrix and applies a structured loss objective.
- The evaluation uses CUB200-2011, CARS196, and a collected Online Products dataset containing approximately 120k images across 23k product classes.The Online Products dataset was collected from online e-commerce websites and is described as one of the largest publicly available datasets by class number and variety.
- On unseen classes, the proposed embedding achieves significantly better clustering and retrieval quality than existing methods.Clustering is measured with F1 and NMI, while retrieval uses Recall@K; the conceptual lifting contribution is presented as applicable to embedding-based learning and recognition tasks.
2. Related works
The paper builds on deep metric learning, convolutional-network feature embedding, and zero-shot learning or ranking. Its distinction from prior embedding methods is a structured loss computed on a dense batchwise distance matrix.
- Zero shot learning and ranking: The paper identifies zero-shot learning and ranking as a third related research line alongside deep metric learning and convolutional feature embedding.
- Deep metric learning: Prior deep metric learning work includes Siamese networks, discriminative face-verification networks, triplet-loss ranking, and metric learning over precomputed features.
- Deep feature embedding with convolutional neural networks: Convolutional-network embedding methods learn visual-search, face-recognition, and joint 2D-image/3D-shape representations.
- Deep feature embedding with convolutional neural networks: Unlike the cited existing approaches, this method computes a structured loss and gradient on a lifted dense pairwise distance matrix to use the full training batch.
3. Review
The review contrasts contrastive and triplet embeddings, which optimize sampled pair or triplet relationships. Their shared goal is to shape distances so same-class examples are close and different-class examples are separated by a margin.
- Contrastive embedding: Contrastive embedding trains on paired examples, minimizing same-class distances and penalizing different-class distances below margin α.
- Contrastive embedding: For contrastive embedding, D_i,j is the network embedding distance between examples, while y_i,j indicates whether they share a class.
- Triplet embedding: Triplet embedding uses an anchor, a same-class positive, and a different-class negative to enforce a margin-separated distance ordering.The training encourages the negative distance to exceed the positive distance by margin α.
- Batch relationships: The reviewed approaches construct training batches from sampled pairs or triplets rather than explicitly accounting for every pairwise edge in the batch.Figure 2 contrasts sampled relationships with a fully connected view of batch relationships.
4. Deep metric learning via lifted structured feature embedding
The lifted structured embedding uses all pairwise distances in a mini-batch, combines difficult-negative mining with a smooth structured objective, and provides gradients from multiple informative negative pairs. It addresses failure modes of randomly sampled contrastive and triplet training by exploiting dense batch structure.
- Structured objective: The structured objective is defined over positive and negative pairs, with P denoting positive pairs and N denoting negative pairs.The method computes backpropagation gradients for the input feature embeddings from this batch-level objective.
- Optimization: The approach replaces the non-smooth structured objective with a smooth upper bound and uses stochastic optimization to address computational challenges.The original objective requires mining all pairs several times for evaluation and subgradient computation.
- Difficult-negative mining: The method biases sampling toward difficult pairs and uses the full mini-batch rather than optimizing only independently sampled pairs or triplets.Hard negatives are mined for both examples in each positive pair, rather than only within a rigid triplet structure.
- Lifted structured embedding: The method lifts O(m) pairwise distances in a batch to an O(m^2) distance matrix and optimizes a structured loss over the lifted problem.The dense matrix uses all pairwise relationships among the m embedded examples.
- Gradient behavior: The smooth objective provides informative gradients for all negative pairs within the margin of any positive pair, rather than updating only the hardest negative.This is described as making optimization more stable.
- Failure modes: Randomly sampled contrastive and triplet training can fail when sampled negatives are poorly positioned or provide insufficient margin-bound information.The proposed embedding uses hard negatives within the margin to push positives in the correct direction when sufficiently large random samples are available.
5. Implementation details
The experiments use fixed training settings across embedding methods, including 20,000 iterations, a margin of 1.0, and method-specific batch sizes.
- 20,000 maximum training iterations were used for all experiments.
- The margin parameter α was set to 1.0.
- Batch sizes were 128 for contrastive and the proposed method, and 120 for triplet embedding.
- Convolutional layers were initialized from an ImageNet-pretrained network, while the final fully connected layer was initialized separately.
6. Evaluation
Evaluation measures clustering with F1 and NMI and retrieval with Recall@K on benchmark test splits, using the metrics shown for CUB200-2011 and CARS196.
- F1 and NMI measure clustering quality, while Recall@K measures retrieval quality.Recall@K gives a score of 1 when a same-class image appears among the K nearest neighbors, then averages over queries.
- CUB200-2011: Figure 6 reports F1, NMI, and Recall@K on the CUB200-2011 test split with GoogLeNet.
- CARS196: Figure 7 reports F1, NMI, and Recall@K on the CARS196 test split with GoogLeNet.
7. Experiments
Experiments evaluate embeddings on unseen classes across CUB-200-2011, CARS196, and Online Products, combining clustering, retrieval, qualitative queries, and t-SNE visualizations.
- The evaluation uses the first half of classes for training and the remaining classes for testing, with embedding sizes 64, 128, 256, and 512.Clustering uses affinity propagation with the number of clusters set to the number of test classes.
- CUB-200-2011: The proposed embedding shows a significant margin on F1, NMI, and Recall@K for all tested embedding sizes on CUB-200-2011.CUB-200-2011 contains 200 bird classes and 11,788 images, split into 100 training and 100 testing classes.
- CARS196: The proposed embedding shows a significant margin on F1, NMI, and Recall@K for all tested embedding sizes on CARS196.CARS196 contains 198 car classes and 16,185 images, split into 98 training and 98 testing classes.
- Online Products: Online Products contains 120,053 images from 22,634 product classes, split into 59,551 training images and 60,502 testing images.
- Online Products: Qualitative Online Products results include successful queries with 512-dimensional embeddings and failures involving fine-grained differences among similar products.The paper also visualizes the Online Products test embedding with Barnes-Hut t-SNE.
8. Conclusion
The paper concludes with a structured objective over lifted dense pairwise distances and reports state-of-the-art performance across three datasets, while showing fine-grained product differences as a failure case.
- The method defines a novel structured prediction objective on the lifted dense pairwise distance matrix within each training batch.
- Online Products failures mainly involve fine-grained subtle differences among similar products.