Source-linked AI summary
DeepEMD: Differentiable Earth Mover's Distance for Few-Shot Learning
Chi Zhang, Yujun Cai, Guosheng Lin, Chunhua Shen
TL;DR
Few-shot image classification must compare images using limited labeled data while handling cluttered backgrounds and varying object appearance. DeepEMD matches local image regions with EMD, learns cross-reference weights and a structured classifier, and reports state-of-the-art results across five benchmarks. The method is also presented as end-to-end trainable and applicable to image retrieval.
Problem
Few-shot classification requires recognizing new categories from limited labeled data while reducing the effects of irrelevant regions and intra-class appearance variation.
Method
DeepEMD uses EMD to optimally match local feature sets, cross-reference weighting to reduce irrelevant-region effects, and a structured fully connected layer for k-shot classification.
Results
DeepEMD achieves new state-of-the-art performance on five few-shot classification benchmarks and is demonstrated on image retrieval.
Takeaways & Limitations
The framework directly compares dense image representations through optimal regional matching and supports end-to-end training with EMD.
Takeaways & Limitations
Many-shot inference is very slow compared with methods using a closed-form distance metric.
Abstract
from arXiv · showhide
In this work, we develop methods for few-shot image classification from a new perspective of optimal matching between image regions. We employ the Earth Mover's Distance (EMD) as a metric to compute a structural distance between dense image representations to determine image relevance. The EMD generates the optimal matching flows between structural elements that have the minimum matching cost, which is used to calculate the image distance for classification. To generate the important weights of elements in the EMD formulation, we design a cross-reference mechanism, which can effectively alleviate the adverse impact caused by the cluttered background and large intra-class appearance variations. To implement k-shot classification, we propose to learn a structured fully connected layer that can directly classify dense image representations with the EMD. Based on the implicit function theorem, the EMD can be inserted as a layer into the network for end-to-end training. Our extensive experiments validate the effectiveness of our algorithm which outperforms state-of-the-art methods by a significant margin on five widely used few-shot classification benchmarks, namely, miniImageNet, tieredImageNet, Fewshot-CIFAR100 (FC100), Caltech-UCSD Birds-200-2011 (CUB), and CIFAR-FewShot (CIFAR-FS). We also demonstrate the effectiveness of our method on the image retrieval task in our experiments.
1 INTRODUCTION
The paper frames few-shot image classification as optimal matching between local image regions, using EMD to measure structural distance and support end-to-end learning. It adds cross-reference weighting and a structured classifier, with reported gains across five benchmarks.
- Few-shot classification targets new categories with limited labeled training data, addressing the poor sample efficiency of deep neural networks.
- Cluttered backgrounds and intra-class appearance variation can separate same-category image embeddings, while global representations may lose useful local characteristics.
- The method formulates classification as optimal matching between local feature sets and uses EMD to compute structural dissimilarity from minimum-cost matching flows.
- A cross-reference mechanism assigns element weights by comparing regions with the other image, reducing contributions from irrelevant background regions.
- A structured fully connected layer uses EMD between dense image representations and learned class-specific vector sets for k-shot classification.
- Experiments on miniImagenet, tieredImagenet, FC100, CUB, and CIFAR-FS report significant improvements over baselines and new state-of-the-art performance for 1-shot and 5-shot classification.
2 RELATED WORK
Related work spans metric-based and optimization-based few-shot learning, along with other approaches such as graph, reinforcement-learning, generative, and transductive methods. The paper is most closely related to metric-based methods and builds on EMD and differentiable optimization.
- Few-shot classification literature includes metric-based and optimization-based approaches for learning transferable representations or adapting model parameters.
- Metric-based methods represent samples in feature spaces where categories are distinguished using distance metrics, whereas optimization-based methods adapt model parameters to new tasks.
- Other related approaches use graph theories, reinforcement learning, differentiable SVMs, generative models, transductive learning, recurrent models, self-supervision, and capsule networks.
- EMD originated in color- and texture-based image retrieval and formulates structured comparison as a transportation problem solvable through linear programming.
- Prior work has applied differential or flow-based formulations to tracking and data association tasks.
- Parameterized optimization research studies differentiation through argmin operators and optimization problems with data-dependent objectives or constraints.
3 PRELIMINARY
Few-shot learning evaluates transferable knowledge on tasks with scarce training images, using support sets for training examples and query sets for evaluation. The framework extracts local embeddings before applying EMD to compare images.
- Meta-learning transfers knowledge across tasks so novel categories can be classified with only a small amount of training data.
- A few-shot task contains sampled classes with scarce training images, represented through support and query sets.
- Support examples pair images with labels, while query examples are evaluated against the sampled classes.
- Query-set ground-truth labels provide training supervision, and inference repeatedly samples tasks while recording mean accuracy.
- For one-shot classification, the framework extracts local embeddings, computes minimum-cost EMD matching flows, and derives an image distance for classification.
4 OUR METHOD
DeepEMD formulates few-shot image classification as optimal matching between local image representations, using EMD to measure structural dissimilarity. Cross-referenced node weights, differentiable optimization, and a structured fully connected layer adapt this matching framework for end-to-end and k-shot classification.
- 4.1 Revisiting the Earth Mover’s Distance: EMD finds nonnegative matching flows that minimize transportation cost under equality and inequality constraints.Node weights control the total matching flows generated by each source or destination.
- 4.2 EMD for Few-Shot Classification: DeepEMD represents images with local feature sets and uses their optimal matching cost as a structural distance for classification.The approach emphasizes discriminative local information rather than only image-level embeddings.
- 4.3 End-to-End Training: The implicit function theorem applied to the KKT conditions yields gradients of the optimal matching solution with respect to LP parameters.This enables backpropagation through the optimization process without perturbing initialization or optimization trajectories.
- 4.2 EMD for Few-Shot Classification: Pyramid structures extract local embeddings at multiple scales using feature-map RoI pooling or image patches processed by the CNN.These alternatives correspond to feature-pyramid and image-pyramid constructions.
- 4.4 Weight Generation: The cross-reference mechanism assigns node weights from dot products with average features in the other image, then normalizes both structures’ weights.It gives less weight to high-variance background and non-co-occurring parts while emphasizing co-occurring object regions.
- 4.5 Structured Fully Connected Layer: The structured fully connected layer learns a vector group for each class and uses EMD between an image representation and each class prototype group.It can be interpreted as a prototype feature map generated by a dummy image.
5 EXPERIMENTS
The experiments evaluate DeepEMD across five few-shot classification benchmarks, with ablations examining embedding extraction and EMD weight generation. The reported comparisons include image-level and local-representation baselines, while implementation uses a ResNet12 backbone and differentiable LP solving.
- 5.3 Comparison with State-of-the-Art Methods: Table 1 reports that DeepEMD with EMD significantly outperforms baselines based on image-level and local representations for 1-shot classification.The comparison includes representative metric-based and fine-tuned classifier methods.
- 5.1 Experimental Setup: The network uses a 12-layer ResNet backbone, with DeepEMD-Grid and DeepEMD-Sampling producing vectors for image patches and DeepEMD-FCN producing dense feature maps.The FCN variant removes global average pooling to form a fully convolutional network.
- 5.1 Experimental Setup: Training combines feature pre-training with episodic meta-training, and QPTH solves the LP while computing gradients for back-propagation.The solver is GPU accelerated.
- 5.4 Ablation Study: The cross-reference mechanism improves performance by up to 4.2% over equal EMD weights, whereas clustering-based weights do not improve performance.The reported ablation supports learned relevance weighting rather than weighting by cluster size alone.
5.3 Analysis
The analysis compares DeepEMD’s local, multi-scale, weighting, and k-shot design choices against alternatives. Results favor local optimal matching, pyramid structures, cross-reference weights, and the structured FC layer.
- Image-level representations: Local optimal matching outperforms image-level vector baselines in both 1-shot 5-way and 1-shot 10-way settings.The comparison uses matched backbones and training schemes, with local features replacing global average pooling.
- Local representations: The optimal matching algorithm outperforms alternatives based on local representations by comparing local structures globally rather than relying only on nearest features.Nearest local features may be insufficient for distinguishing images when individually similar parts, such as eyes, occur across species.
- Local embedding extractors: DeepEMD-Sampling outperforms the plain versions of the other local embedding extractors, while feature- and image-level pyramids improve performance.The comparison is conducted on 1-shot tasks; pyramid structures boost both DeepEMD-FCN and DeepEMD-Grid.
- Weights in the EMD: A cross-reference mechanism improves performance by up to 4.2% over equal weights, whereas clustering-based weights do not improve the baseline.The results support weighting regions by task-relevant importance rather than by cluster or pixel count.
- Ablation analysis: The EMD-plus-structured-FC combination yields a significant performance improvement over its component variants.This result supports using EMD as the metric together with the cross-reference mechanism.
- K-shot methods: The structured FC layer consistently outperforms baseline k-shot methods, with its advantage increasing as more support images become available.The comparison also attributes gains over a finetuned cosine classifier to structured prototypes and EMD.
5.4 Cross-Domain Experiments
The cross-domain experiment trains on miniImageNet and evaluates on CUB, testing performance under a large domain gap. DeepEMD outperforms baseline models, with local features and cross-reference weighting supporting transfer across domains.
- Interpretation: Local features provide transferable and discriminative information across domains, while cross-reference matching restricts comparisons to confident co-occurring object regions.The mechanism is described as filtering noise under a large domain shift.
5.5 Visualization of Matching Flows and Weights
Visualization experiments inspect DeepEMD’s matching flows and node weights by reconstructing one image from patches of another. The visualizations show semantic local correspondence, low background weights, and many-to-many matching.
- Visual reconstruction: DeepEMD establishes semantic correspondence between local regions and assigns small weights to background regions.The reconstruction pastes best-matched patches from one image into corresponding positions in the other, with weights controlling brightness.
- Matching flows: One patch can match multiple regions in the other image with different weights, accommodating objects that appear at different sizes.The full optimal matching flows reveal that correspondence is not strictly one-to-one.
5.6 Time Complexity
DeepEMD requires solving an optimization problem during forward passes, making it more computationally expensive than closed-form distance metrics. The reported complexity is driven mainly by the LP solver and optimization-variable count.
- Computation cost: DeepEMD incurs more computation because an LP must be solved for each forward pass.The main costs are KKT-matrix factorization and back-substitution when using an interior-point method.
- Time complexity: KKT-matrix factorization has cubic time complexity and back-substitution has quadratic time complexity in the number of optimization variables.These complexities describe the interior-point solution process for the LP problem.
- Implementation implications: Feature dimension has little influence on EMD-layer computation time, allowing deeper backbones without significantly increasing inference time.After training, the interior-point solver can be replaced with faster solvers for inference.
5.7 Comparison with State-of-the-art Methods
DeepEMD achieves new state-of-the-art few-shot classification performance across five benchmarks without extra data, with especially large gains on miniImageNet and tieredImageNet.
- DeepEMD achieves new state-of-the-art performance on all five evaluated benchmarks without using extra data.The benchmarks are miniImageNet, tieredImageNet, FC100, CUB, and CIFAR-FS.
- 3.47% and 1.43% are the 1-shot and 5-shot gains over state-of-the-art performance on miniImageNet.
- 2.77% and 1.05% are the 1-shot and 5-shot gains over state-of-the-art performance on tieredImageNet.
- DeepEMD-FCN outperforms DeepEMD-Grid and DeepEMD-Sampling on FC100 and CIFAR-FS.The passage contrasts this pattern with observations on the other datasets.
5.8 Experiments on Image Retrieval
The image retrieval experiments test DeepEMD as a local-representation metric complementary to deep metric learning methods. On CUB, the method improves baselines across three evaluation metrics.
- DeepEMD improves high-performing deep metric learning baselines for image retrieval by replacing global representations and metrics with local representations and DeepEMD.
- The CUB retrieval experiment uses classes 1–100 for training and the remaining classes for evaluation, with identical baseline and DeepEMD configurations for fair comparison.The setup uses an ImageNet-pretrained ResNet-50 and evaluates DeepEMD-FCN, DeepEMD-Grid, and DeepEMD-Sampling variants.
- DeepEMD effectively improves baseline performance under Recall@1, R-Precision, and Mean Average Precision at R.
6 CONCLUSION
The paper concludes that DeepEMD enables end-to-end few-shot classification from dense image representations while reducing the impact of irrelevant regions and achieving state-of-the-art results.
- DeepEMD uses Earth Mover’s Distance as the metric in a few-shot classification framework.
- The implicit function theorem makes the network end-to-end trainable with the EMD component.
- The cross-reference mechanism sets node weights and minimizes the negative impact of irrelevant regions in the EMD formulation.
- A learnable structured fully connected layer directly classifies dense image representations in k-shot settings.
- DeepEMD achieves new state-of-the-art performance on multiple datasets.