Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity

Jang-Hyun Kim; Wonho Choo; Hosan Jeong; Hyun Oh Song

Source-linked AI summary

Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity

Jang-Hyun Kim, Wonho Choo, Hosan Jeong, Hyun Oh Song

arXiv:2102.03065v1Feb 5, 2021cs.LGcs.AIcs.CVstat.ML

TL;DR

Co-Mixup addresses the unresolved question of how to use supervisory information when constructing mixup data for neural-network generalization and robustness. It jointly selects salient regions across a batch, promotes diversity through discrete optimization, and uses an efficient iterative algorithm; experiments report state-of-the-art results across several tasks compared with mixup baselines.

Problem
Mixup improves generalization and robustness, but it remains unclear how to best use supervisory signals within each input when constructing mixup data.
Method
Co-Mixup optimizes batch mixup by maximizing each example's saliency and encouraging diversity with a submodular-supermodular objective and modular-approximation-based iterative minimization.
Results
Co-Mixup achieves state-of-the-art performance compared with mixup baselines across generalization, calibration, weakly supervised localization, and robustness evaluations.
Takeaways & Limitations
The generalized mixup framework addresses what to mix by combining salient regions across inputs rather than considering only how to mix them.
Takeaways & Limitations
The compatibility penalty can over-penalize optimization when outputs reuse inputs, causing some outputs to become singletons without mixup.

Abstract

from arXiv · show

While deep neural networks show great performance on fitting to the training distribution, improving the networks' generalization performance to the test distribution and robustness to the sensitivity to input perturbations still remain as a challenge. Although a number of mixup based augmentation strategies have been proposed to partially address them, it remains unclear as to how to best utilize the supervisory signal within each input data for mixup from the optimization perspective. We propose a new perspective on batch mixup and formulate the optimal construction of a batch of mixup data maximizing the data saliency measure of each individual mixup data and encouraging the supermodular diversity among the constructed mixup data. This leads to a novel discrete optimization problem minimizing the difference between submodular functions. We also propose an efficient modular approximation based iterative submodular minimization algorithm for efficient mixup computation per each minibatch suitable for minibatch based neural network training. Our experiments show the proposed method achieves the state of the art generalization, calibration, and weakly supervised localization results compared to other mixup methods. The source code is available at https://github.com/snu-mllab/Co-Mixup.

1 Introduction

Deep neural networks can overfit training data, motivating augmentation methods that improve generalization and robustness. Co-Mixup constructs minibatch mixup examples by combining salient regions across inputs while promoting diversity, and reports improvements over existing mixup baselines.

Neural networks can fit random data, leading to overfitting and a generalization gap on unseen data.
Existing mixup methods do not fully use supervisory signals such as object saliency and relative arrangement.
Co-Mixup jointly mix-matches salient regions across inputs so each example accumulates salient regions while generated examples remain diverse.
The method formulates mixup construction as a discrete submodular-supermodular optimization problem and solves it with modular approximation and iterative submodular minimization.
Experiments on CIFAR-100, Tiny-ImageNet, ImageNet, and Google commands report state-of-the-art performance against mixup baselines across generalization, localization, and robustness tasks.

2 Related works

Mixup provides task-independent augmentation for improving neural-network generalization and robustness, while saliency methods supply information about important input regions. Co-Mixup's optimization is related to submodular-supermodular formulations that combine smoothness and diversity terms.

Mixup linearly interpolates input pairs and can improve neural-network generalization and robustness across data types and tasks.
Saliency maps estimate informative regions using neural-network-based gradients or related methods and are applied across domains.
Submodular-Supermodular optimization: Submodular and supermodular functions model diminishing and increasing returns, respectively, and their difference forms a BP function.
Submodular-Supermodular optimization: Co-Mixup's BP formulation combines a submodular smoothness function for mixed outputs with a supermodular diversity function among outputs.

3 Preliminary

Existing methods mix paired inputs using functions such as interpolation, masking, or transport-based rearrangement. Co-Mixup extends this setup to collections of inputs, using location-wise source assignments and corresponding soft labels.

Existing mixup methods pair each input with a randomly permuted input and apply a mixup function h to produce the outputs.
Input Mixup uses λx + (1 − λ)x′, while CutMix uses a binary rectangular mask and Puzzle Mix uses transport plans with discrete masks.
Co-Mixup extends h from two inputs to a collection, mapping a batch xB ∈ Rm×n to a collection of m′ mixed outputs.
Each location-wise assignment zj,k specifies mixing ratios among the m inputs, with ||zj,k||1 = 1 preserving overall batch statistics.
Soft target labels are generated from the input one-hot labels and input-source ratios, then learned by minimizing cross-entropy loss.

4 Method

Co-Mixup constructs each mixup example from salient regions while jointly encouraging diversity across outputs. Its objective combines saliency, smoothness, prior, and compatibility terms, optimized through iterative modular approximation and submodular minimization.

Saliency and diversity: Co-Mixup generalizes pairwise mixup by selecting salient regions from multiple inputs while maintaining diversity among generated examples.Saliency is measured from training-loss gradients, and adjacent locations are encouraged to share similar source labels.
Objective: Compatibility clipping prevents over-penalization that can cause many outputs to become singletons without mixup.The clipped objective adds no extra penalty when compatibility across outputs is below a specified level.
Objective: The compatibility term is pairwise supermodular when A is positive semi-definite, which can be guaranteed for sufficiently small positive ω.A is formed as A = (1 −ω)I + ωAc, with Ac symmetric and analyzed through spectral decomposition.
Objective: The objective combines modular unary and prior terms, a submodular smoothness term, and a supermodular compatibility term.The compatibility matrix quantifies which input sources are suitable to mix and penalizes outputs with similar source information.
Optimization algorithm: The supermodular term is iteratively approximated by a modular function, enabling submodular minimization for minibatch-based mixup.The proposed modularization computes the approximation in O(m′) time per iteration instead of requiring O(m′nm) sequential evaluations.
Optimization algorithm: Figure 3 depicts mix-matching salient regions across a batch while preserving diversity, with histograms showing each output’s input-source composition.The output source information is represented by aggregating assigned labels across locations.

5 Experiments

Co-Mixup is evaluated across classification, localization, calibration, and robustness tasks using multiple datasets and model architectures. It outperforms mixup baselines across these evaluations, with reported gains in classification error, calibration, localization, and background-corruption robustness.

Experimental setup: Experiments cover generalization, weakly supervised object localization, calibration, and robustness across CIFAR-100, Tiny-ImageNet, ImageNet, and Google commands.The evaluation uses multiple architectures and follows task-specific protocols, including CAM for localization and ECE for calibration.
5.1 Classification: 19.87% Top-1 error rate on CIFAR-100 with PreActResNet18 outperforms the best baseline by 0.75%.Co-Mixup also improves Top-1 error rate over the best-performing baseline with WRN16-8 and ResNeXt29-4-24.
5.1 Classification: 0.67% improvement in Top-1 error rate over baselines is reported on Tiny-ImageNet, while Co-Mixup outperforms all baselines on ImageNet and is most effective in the speech-domain experiment.The ImageNet experiment uses ResNet-50 for 100 epochs, and the speech experiment uses Google commands with VGG-11.
5.2 Localization / 5.4 Robustness: Co-Mixup outperforms other baselines in ImageNet weakly supervised object localization and in background-corruption robustness tests.For background corruption, the reported Top-1 error-rate margins over Vanilla are 2.86% and 3.33%.
5.3 Calibration: 48% less ECE value is reported for Co-Mixup on CIFAR-100, which has the lowest calibration error among baselines.Other mixup baselines tend toward under-confident predictions, whereas Co-Mixup is described as best calibrated.
5.5 Baselines with multiple inputs: Mixing multiple inputs decreases the performance gains of each mixup baseline, supporting Co-Mixup’s use of saliency information and diversity.Table 4 reports CIFAR-100 Top-1 error rates for multiple-input baselines, while Co-Mixup optimally determines the number of inputs for each output.

6 Conclusion

Co-Mixup constructs batches by combining salient regions from multiple inputs while encouraging diversity among generated examples. Its optimization framework and practical algorithm support minibatch training, with experiments reporting state-of-the-art performance across several tasks.

Co-Mixup selects salient-region combinations across input data while encouraging diversity among the generated mixup examples.
The construction is formulated as discrete optimization minimizing a submodular-supermodular objective.
A modular approximation and iterative submodular optimization algorithm make the framework suitable for minibatch-based neural network training.
Co-Mixup achieves state-of-the-art performance in generalization, weakly supervised object localization, and robustness against background corruption compared with mixup baselines.
The framework addresses what to mix, whereas existing methods primarily address how to mix, and is proposed for applications such as multi-label classification and multi-object detection.
The compatibility term uses a matrix A between inputs and minimizes pairwise output compatibility, while Figure 5 illustrates how compatibility distinguishes alternative mixup results.

B Proofs

The proofs establish the submodularity and supermodularity properties needed for Co-Mixup's optimization formulation. They also show that the proposed modularization satisfies its stated criteria under the construction's assumptions.

For positive semidefinite A, the pairwise compatibility function s(x, x′) = x^⊺Ax′ is supermodular.The proof reduces the required expression to (x − x′)^⊺A(x − x′), which is nonnegative.
When A is positive semidefinite, the compatibility term in Equation (1) is pairwise supermodular for every output pair.
The bounded compatibility component is pairwise submodular because the relevant transformed quadratic term is submodular and budget addition preserves submodularity.
The modularization in Equation (2) satisfies the prescribed criteria for compatibility approximation.The proof analyzes local changes to output assignments and shows the required ordering and penalty properties.
For positive thresholds, the modularized compatibility has no extra penalty when output support lies among indices below the threshold.

C Implementation details

Co-Mixup reduces optimization cost by operating on down-sampled inputs and saliency maps, then upsamples the labeling for mixing. The resulting implementation is feasible for minibatch training despite added computation.

The optimization runs at 4×4 resolution, after which the optimal labeling is up-sampled to the original input size for mixing.
Saliency is measured using the ℓ2 norm of input-channel gradients of the training loss.
The alpha-beta swap minimization step has worst-case complexity O(m^2n) for two labels and can bottleneck training on large minibatches.
Naive multi-label complexity grows exponentially with the number of labels, motivating binary optimization before extension to multiple labels.
ImageNet Co-Mixup training takes 0.964s per batch versus 0.374s for vanilla training, and is only about 1.04 times slower than Puzzle Mix.
Algorithm 1 exhibits linear empirical time complexity over |L|, with |L| = 3 used in the main experiments.

D.1 Comparison with Brute Force

The proposed optimization algorithm is evaluated against brute-force search and prior optimization methods, while experiments also examine its use across domains and calibration. Results report near-optimal solutions, lower objective values, feasible convergence, speech-domain effectiveness, and improved calibration.

D.1 Comparison with Brute Force: Across small-scale settings, Algorithm 1 achieves near-optimal solutions relative to brute-force search over 100 random seeds.
D.1 Comparison with Brute Force: Relative error between Algorithm 1 and brute-force solutions is less than 0.01.
Compared with the Narasimhan–Bilmes method, the proposed algorithm obtains lower function values and deviations across varied numbers of mixing inputs.
The convergence-time experiments show that the proposed algorithm is much faster than the Narasimhan–Bilmes method.
Co-Mixup remains effective on the Google Commands speech dataset using normalized utterance spectrograms.
Co-Mixup classifiers have the lowest calibration error on CIFAR-100 and Tiny-ImageNet and avoid the under-confidence observed for other mixup classifiers.
Across CIFAR-100, Tiny-ImageNet, and ImageNet, Co-Mixup outperforms all baselines in Top-1 accuracy.

F.3 Sensitivity analysis

The sensitivity analysis examines Co-Mixup across hyperparameter settings and compares it with VAT regularization on CIFAR-100. Co-Mixup remains competitive across a broad hyperparameter pool and achieves a lower reported Top-1 error rate than VAT.

Hyperparameter sensitivity: Co-Mixup outperforms the best baseline, PuzzleMix at 20.62%, across a broad hyperparameter search on CIFAR-100.The sweep varies β, γ, τ, ω, and partition size m.
Hyperparameter sensitivity: Top-1 error rate increases as the partition batch size m increases until m = 20.
Comparison with non-mixup baselines: 19.87% Top-1 error rate: Co-Mixup outperforms VAT regularization on CIFAR-100 with PreActResNet18.

G Detailed description for background corruption

The background-corruption evaluation constructs ImageNet validation samples by preserving annotated foreground regions while corrupting their backgrounds. It uses either another image or Gaussian noise for the background and visualizes examples of the resulting datasets.

Dataset construction: ImageNet validation images are corrupted by separating foreground and background with ground-truth bounding-box masks.The binary mask z_j equals 1 inside the ground-truth bounding box.
Corruption operations: Background replacement uses a randomly permuted image while retaining the original foreground.The construction is x̃_j = x_j ⊙ z_j + x_i(j) ⊙ (1 − z_j).
Corruption operations: Gaussian-noise corruption replaces the background with ϵ ∼ N(0, 0.12), then clips pixel values to [0, 1].
Visualization: Figure 10 visualizes subsets of the background-corruption datasets, including image replacement and Gaussian-noise conditions.

H Co-Mixup generated samples

Co-Mixup combines salient regions across an input batch to produce diverse mixed outputs. Increasing τ encourages each output to mix more inputs.

Input and output batches: Co-Mixup uses an input batch of 24 ImageNet images to generate mixed output samples.
Mixing behavior: The generated outputs mix salient regions while promoting diversity across samples.Objects on left are mixed with right-side objects, and top-side objects with bottom-side objects.
Effect of τ: Larger τ encourages Co-Mixup to use more inputs in each mixed output.Figure 13 shows samples generated with larger τ using the same input batch.