Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity
Year: 2021

Abstract:
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.

heading: 1 Introduction
text: Deep neural networks have been applied to a wide range of artificial intelligence tasks such as computer vision, natural language processing, and signal processing with remarkable performance (Ren et al., 2015; Devlin et al., 2018; Oord et al., 2016). However, it has been shown that neural networks have excessive representation capability and can even fit random data (Zhang et al., 2016). Due to these characteristics, the neural networks can easily overfit to training data and show a large generalization gap when tested on previously unseen data.
To improve the generalization performance of the neural networks, a body of research has been proposed to develop regularizers based on priors or to augment the training data with task-dependent transforms (Bishop, 2006; Cubuk et al., 2019). Recently, a new taskindependent data augmentation technique, called mixup, has been proposed (Zhang et al., 2018). The original mixup, called Input Mixup, linearly interpolates a given pair of input data and can be easily applied to various data and tasks, improving the generalization performance and robustness of neural networks. Other mixup methods, such as manifold mixup (Verma et al., 2019) or CutMix (Yun et al., 2019), have also been proposed addressing different ways to mix a given pair of input data. Puzzle Mix (Kim et al., 2020) utilizes saliency information and local statistics to ensure mixup data to have rich supervisory signals.
However, these approaches only consider mixing a given random pair of input data and do not fully utilize the rich informative supervisory signal in training data including collection of object saliency, relative arrangement, etc. In this work, we simultaneously consider mixmatching different salient regions among all input data so that each generated mixup example accumulates as many salient regions from multiple input data as possible while ensuring
Correspondence to: Hyun Oh Song.
diversity among the generated mixup examples. To this end, we propose a novel optimization problem that maximizes the saliency measure of each individual mixup example while encouraging diversity among them collectively. This formulation results in a novel discrete submodular-supermodular objective. We also propose a practical modular approximation method for the supermodular term and present an efficient iterative submodular minimization algorithm suitable for minibatch-based mixup for neural network training. As illustrated in the Figure 1, while the proposed method, Co-Mixup, mix-matches the collection of salient regions utilizing inter-arrangements among input data, the existing methods do not consider the saliency information (Input Mixup & CutMix) or disassemble salient parts (Puzzle Mix).
We verify the performance of the proposed method by training classifiers on CIFAR-100, Tiny-ImageNet, ImageNet, and the Google commands dataset (Krizhevsky et al., 2009; Chrabaszcz et al., 2017; Deng et al., 2009; Warden, 2017). Our experiments show the models trained with Co-Mixup achieve the state of the performance compared to other mixup baselines. In addition to the generalization experiment, we conduct weakly-supervised object localization and robustness tasks and confirm Co-Mixup outperforms other mixup baselines.

heading: 2 Related works
text: Mixup Data augmentation has been widely used to prevent deep neural networks from over-fitting to the training data (Bishop, 1995). The majority of conventional augmentation methods generate new data by applying transformations depending on the data type or the target task (Cubuk et al., 2019). Zhang et al. (2018) proposed mixup, which can be independently applied to various data types and tasks, and improves generalization and robustness of deep neural networks. Input mixup (Zhang et al., 2018) linearly interpolates between two input data and utilizes the mixed data with the corresponding soft label for training. Following this work, manifold mixup (Verma et al., 2019) applies the mixup in the hidden feature space, and CutMix (Yun et al., 2019) suggests a spatial copy and paste based mixup strategy on images. Guo et al. (2019) trains an additional neural network to optimize a mixing ratio. Puzzle Mix (Kim et al., 2020) proposes a mixup method based on saliency and local statistics of the given data. In this paper, we propose a discrete optimization-based mixup method simultaneously finding the best combination of collections of salient regions among all input data while encouraging diversity among the generated mixup examples.
Saliency The seminal work from Simonyan et al. (2013) generates a saliency map using a pre-trained neural network classifier without any additional training of the network. Following the work, measuring the saliency of data using neural networks has been studied to obtain a more precise saliency map (Zhao et al., 2015; Wang et al., 2015) or to reduce the saliency computation cost (Zhou et al., 2016; Selvaraju et al., 2017). The saliency information is widely applied to the tasks in various domains, such as object segmentation or speech recognition (Jung and Kim, 2011; Kalinli and Narayanan, 2007).
Submodular-Supermodular optimization A submodular (supermodular) function is a set function with diminishing (increasing) returns property (Narasimhan and Bilmes, 2005). It is known that any set function can be expressed as the sum of a submodular and supermodular function (Lovász, 1983), called BP function. Various problems in machine learning can be naturally formulated as BP functions (Fujishige, 2005), but it is known to be NP-hard (Lovász, 1983). Therefore, approximate algorithms based on modular approximations of submodular or supermodular terms have been developed (Iyer and Bilmes, 2012). Our formulation falls into a category of BP function consisting of smoothness function within a mixed output (submodular) and a diversity function among the mixup outputs (supermodular).

heading: 3 Preliminary
text: Existing mixup methods return {h(x1, xi(1)), . . . , h(xm, xi(m))} for given input data {x1, . . . , xm}, where h : X × X → X is a mixup function and (i(1), . . . , i(m)) is a random permutation of the data indices. In the case of input mixup, h(x, x′) is λx+ (1− λ)x′, where λ ∈ [0, 1] is a random mixing ratio. Manifold mixup applies input mixup in the hidden feature space, and CutMix uses h(x, x′) = 1B x + (1 − 1B) x′, where 1B is a binary rectangular-shape mask for an image x and represents the element-wise product. Puzzle Mix defines h(x, x′) as z Πᵀx + (1 − z) Π′ᵀx′, where Π is a transport plan and z is a discrete mask. In detail, for x ∈ Rn, Π ∈ {0, 1}n and z ∈ Ln for L = { lL | l = 0, 1, . . . , L}.
In this work, we extend the existing mixup functions as h : Xm → Xm′ which performs mixup on a collection of input data and returns another collection. Let xB ∈ Rm×n denote the batch of input data in matrix form. Then, our proposed mixup function is
h(xB) = ( g(z1 xB), . . . , g(zm′ xB) ) ,
where zj ∈ Lm×n for j = 1, . . . ,m′ with L = { lL | l = 0, 1, . . . , L} and g : R m×n → Rn returns a column-wise sum of a given matrix. Note that, the kth column of zj , denoted as zj,k ∈ Lm, can be interpreted as the mixing ratio among m inputs at the kth location. Also, we enforce ‖zj,k‖1 = 1 to maintain the overall statistics of the given input batch. Given the one-hot target labels yB ∈ {0, 1}m×C of the input data with C classes, we generate soft target labels for mixup data as yᵀB õj for j = 1, . . . ,m ′, where õj = 1n ∑n k=1 zj,k ∈ [0, 1]m represents the input source ratio of the jth mixup data. We train models to estimate the soft target labels by minimizing the cross-entropy loss.

heading: 4 Method

heading: 4.1 Objective
text: Saliency Our main objective is to maximize the saliency measure of mixup data while maintaining the local smoothness of data, i.e., spatially nearby patches in a natural image look similar, temporally adjacent signals have similar spectrum in speech, etc. (Kim et al., 2020). As we can see from CutMix in Figure 1, disregarding saliency can give a misleading supervisory signal by generating mixup data that does not match with the target soft label. While the existing mixup methods only consider the mixup between two inputs, we generalize the number of inputs m to any positive integer. Note, each kth location of outputs has m candidate sources from the inputs. We model the unary labeling cost as the negative value of the saliency, and denote the cost vector at the kth location as ck ∈ Rm. For the saliency measure, we calculate the gradient values of training loss with respect to the input and measure `2 norm of the gradient values across input channels (Simonyan et al., 2013; Kim et al., 2020). Note that this method does not require any additional architecture dependent modules for saliency calculation. In addition to the unary cost, we encourage adjacent locations to have similar labels for the smoothness of each mixup data. In summary, the objective can be formulated as follows:
m′∑ j=1 n∑ k=1 cᵀkzj,k + β m′∑ j=1 ∑ (k,k′)∈N (1− zᵀj,kzj,k′)− η m′∑ j=1 n∑ k=1 log p(zj,k),
where the prior p is given by zj,k ∼ 1LMulti(L, λ) with λ = (λ1, . . . , λm) ∼ Dirichlet(α, . . . , α), which is a generalization of the mixing ratio distribution of Zhang et al. (2018), and N denotes a set of adjacent locations (i.e., neighboring image patches in vision, subsequent spectrums in speech, etc.).
Diversity Note that the naive generalization above leads to the identical outputs because the objective is separable and identical for each output. In order to obtain diverse mixup outputs, we model a similarity penalty between outputs. First, we represent the input source information of the jth output by aggregating assigned labels as ∑n k=1 zj,k. For simplicity,
let us denote ∑n k=1 zj,k as oj . Then, we measure the similarity between oj ’s by using the inner-product on Rm. In addition to the input source similarity between outputs, we model the compatibility between input sources, represented as a symmetric matrix Ac ∈ Rm×m+ . Specifically, Ac[i1, i2] quantifies the degree to which input i1 and i2 are suitable to be mixed together. In summary, we use inner-product on A = (1 − ω)I + ωAc for ω ∈ [0, 1], resulting in a supermodular penalty term. Note that, by minimizing 〈oj , oj′〉A = oᵀjAoj′ , ∀j 6= j′, we penalize output mixup examples with similar input sources and encourage each individual mixup examples to have high compatibility within. In this work, we measure the distance between locations of salient objects in each input and use the distance matrix Ac[i, j] = ‖argmaxksi[k]− argmaxksj [k]‖1, where si is the saliency map of the ith input and k is a location index (e.g., k is a 2-D index for image data). From now on, we denote this inner-product term as the compatibility term.
Over-penalization The conventional mixup methods perform mixup as many as the number of examples in a given mini-batch. In our setting, this is the case when m = m′. However, the compatibility penalty between outputs is influenced by the pigeonhole principle. For example, suppose the first output consists of two inputs. Then, the inputs must be used again for the remaining m′ − 1 outputs, or only m− 2 inputs can be used. In the latter case, the number of available inputs (m− 2) is less than the outputs (m′ − 1), and thus, the same input must be used more than twice. Empirically, we found that the remaining compatibility term above over-penalizes the optimization so that a substantial portion of outputs are returned as singletons without any mixup. To mitigate the over-penalization issue, we apply clipping to the compatibility penalty term. Specifically, we model the objective so that no extra penalty would occur when the compatibility among outputs is below a certain level.
Now we present our main objective as following:
z∗ = argmin zj,k∈Lm, ‖zj,k‖1=1 f(z),
where
f(z) := m′∑ j=1 n∑ k=1 cᵀkzj,k + β m′∑ j=1 ∑ (k,k′)∈N (1− zᵀj,kzj,k′) (1)
+ γmax τ, m′∑ j=1 m′∑ j′ 6=j ( n∑ k=1 zj,k )ᵀ A ( n∑ k=1 zj′,k )︸ ︷︷ ︸ =fc(z) −η m′∑ j=1 n∑ k=1 log p(zj,k).
In Figure 2, we describe the properties of the BP optimization problem of Equation (1) and statistics of the resulting mixup data. Next, we verify the supermodularity of the compatibility term. We first extend the definition of the submodularity of a multi-label function as follows (Windheuser et al., 2012). Definition 1. For a given label set L, a function s : Lm × Lm → R is pairwise submodular, if ∀x, x′ ∈ Lm, s(x, x) +s(x′, x′) ≤ s(x, x′) +s(x′, x). A function s is pairwise supermodular, if −s is pairwise submodular. Proposition 1. The compatibility term fc in Equation (1) is pairwise supermodular for every pair of (zj1,k, zj2,k) if A is positive semi-definite.
Proof. See Appendix B.1.
Finally note that, A = (1 − ω)I + ωAc, where Ac is a symmetric matrix. By using spectral decomposition, Ac can be represented as UDUᵀ, where D is a diagonal matrix and UᵀU = UUᵀ = I. Then, A = U((1− ω)I + ωD)Uᵀ, and thus for small ω > 0, we can guarantee A to be positive semi-definite.

heading: 4.2 Algorithm
text: Our main objective consists of modular (unary, prior), submodular (smoothness), and supermodular (compatibility) terms. To optimize the main objective, we employ the submodularsupermodular procedure by iteratively approximating the supermodular term as a modular function (Narasimhan and Bilmes, 2005). Note that zj represents the labeling of the jth output and oj represents the aggregated input source information of the jth output, ∑n k=1 zj,k. Before introducing our algorithm, we first inspect the simpler case without clipping. Proposition 2. The compatibility term fc without clipping is modular with respect to zj.
Proof. Note, A is a positive symmetric matrix by the definition. Then, for an index j0, we can represent fc without clipping in terms of oj0 as ∑m′ j=1 ∑m′ j′=1,j′ 6=j o ᵀ jAoj′ =
2 ∑m′ j=1,j 6=j0 o ᵀ jAoj0+ ∑m′ j=1,j 6=j0 ∑m′ j′=1,j′ /∈{j0,j} o ᵀ jAoj′ = (2 ∑m′ j=1,j 6=j0 Aoj) ᵀoj0+c = v ᵀ -j0oj0+ c, where v-j0 ∈ Rm and c ∈ R are values independent with oj0 . Finally, v ᵀ -j0oj0 + c =∑n
k=1 v ᵀ -j0zj0,k + c is a modular function of zj0 .
By Proposition 2, we can apply a submodular minimization algorithm to optimize the objective with respect to zj when there is no clipping. Thus, we can optimize the main objective without clipping in coordinate descent fashion (Wright, 2015). For the case with clipping, we modularize the supermodular compatibility term under the following criteria:
1. The modularized function value should increase as the compatibility across outputs increases.
2. The modularized function should not apply an extra penalty for the compatibility below a certain level.
Borrowing the notation from the proof in Proposition 2, for an index j, fc(z) = max{τ, vᵀ-joj+ c} = max{τ − c, vᵀ-joj}+ c. Note, oj = ∑n k=1 zj,k represents the input source information of
the jth output and v-j = 2 ∑m′ j′=1,j′ 6=j Aoj′ encodes the status of the other outputs. Thus, we can interpret the supermodular term as a penalization of each label of oj in proportion to the corresponding v-j value (criterion 1), but not for the compatibility below τ − c (criterion 2). As a modular function which satisfies the criteria above, we use the following function:
fc(z) ≈ max{τ ′, v-j}ᵀoj for ∃τ ′ ∈ R. (2)
Note that, by satisfying the criteria above, the modular function reflects the diversity and over-penalization desiderata described in Section 4.1. We illustrate the proposed mixup procedure with the modularized diversity penalty in Figure 3. Proposition 3. The modularization given by Equation (2) satisfies the criteria above.
Proof. See Appendix B.2.
Algorithm 1 Iterative submodular minimization Initialize z as z(0). Let z(t) denote a solution of the tth step. Φ: modularization operator based on Equation (2). for t = 1, . . . , T do for j = 1, . . . ,m′ do f (t) j (zj) := f(zj ; z (t) 1:j−1, z (t−1) j+1:m′).
f̃ (t) j = Φ(f (t) j ). Solve z(t)j = argmin f̃ (t) j (zj).
end for end for return z(T ) By applying the modular approximation described in Equation (2) to fc in Equation (1), we can iteratively apply a submodular minimization algorithm to obtain the final solution as described in Algorithm 1. In detail, each step can be performed as follows: 1) Conditioning the main objective f on the current values except zj , denoted as fj(zj) = f(zj ; z1:j−1, zj+1:m′). 2) Modularization of the compatibility term of fj as Equation (2), resulting in a submodular function f̃j . We denote the modularization operator as Φ, i.e., f̃j = Φ(fj). 3) Applying a submodular minimization algorithm to f̃j . Please refer to Appendix C for implementation details.
Analysis Narasimhan and Bilmes (2005) proposed a modularization strategy for general supermodular set functions, and apply a submodular minimization algorithm that can monotonically decrease the original BP objective. However, the proposed Algorithm 1 based on Equation (2) is much more suitable for minibatch based mixup for neural network training than the set modularization proposed by Narasimhan and Bilmes (2005) in terms of complexity and modularization variance due to randomness. For simplicity, let us assume
each zj,k is an m-dimensional one-hot vector. Then, our problem is to optimize m′n one-hot m-dimensional vectors.
To apply the set modularization method, we need to assign each possible value of zj,k as an element of {1, 2, . . . ,m}. Then the supermodular term in Equation (1) can be interpreted as a set function with m′nm elements, and to apply the set modularization, O(m′nm) sequential evaluations of the supermodular term are required. In contrast, Algorithm 1 calculates v-j in Equation (2) in only O(m′) time per each iteration. In addition, each modularization step of the set modularization method requires a random permutation of the m′nm elements. In this case, the optimization can be strongly affected by the randomness from the permutation step. As a result, the optimal labeling of each zj,k from the compatibility term is strongly influenced by the random ordering undermining the interpretability of the algorithm. Please refer to Appendix D for empirical comparison between Algorithm 1 and the method by Narasimhan and Bilmes (2005).

heading: 5 Experiments
text: We evaluate our proposed mixup method on generalization, weakly supervised object localization, calibration, and robustness tasks. First, we compare the generalization performance of the proposed method against baselines by training classifiers on CIFAR-100 (Krizhevsky et al., 2009), Tiny-ImageNet (Chrabaszcz et al., 2017), ImageNet (Deng et al., 2009), and the Google commands speech dataset (Warden, 2017). Next, we test the localization performance of classifiers following the evaluation protocol of Qin and Kim (2019). We also measure calibration error (Guo et al., 2017) of classifiers to verify Co-Mixup successfully alleviates the over-confidence issue by Zhang et al. (2018). In Section 5.4, we evaluate the robustness of the classifiers on the test dataset with background corruption in response to the recent problem raised by Lee et al. (2020) that deep neural network agents often fail to generalize to unseen environments. Finally, we perform a sensitivity analysis of Co-Mixup and provide the results in Appendix F.3.

heading: 5.1 Classification
text: We first train PreActResNet18 (He et al., 2016), WRN16-8 (Zagoruyko and Komodakis, 2016), and ResNeXt29-4-24 (Xie et al., 2017) on CIFAR-100 for 300 epochs. We use stochastic gradient descent with an initial learning rate of 0.2 decayed by factor 0.1 at epochs 100 and 200. We set the momentum as 0.9 and add a weight decay of 0.0001. With this setup, we train a vanilla classifier and reproduce the mixup baselines (Zhang et al., 2018; Verma et al., 2019; Yun et al., 2019; Kim et al., 2020), which we denote as Vanilla, Input, Manifold, CutMix, Puzzle Mix in the experiment tables. Note that we use identical hyperparameters regarding Co-Mixup over all of the experiments with different models and datasets, which are provided in Appendix E.
Table 1 shows Co-Mixup significantly outperforms all other baselines in Top-1 error rate. Co-Mixup achieves 19.87% in Top-1 error rate with PreActResNet18, outperforming the best baseline by 0.75%. We further test Co-Mixup on different models (WRN16-8 & ResNeXt294-24) and verify Co-Mixup improves Top-1 error rate over the best performing baseline.
We further test Co-Mixup on other datasets; Tiny-ImageNet, ImageNet, and the Google commands dataset (Table 1). For Tiny-ImageNet, we train PreActResNet18 for 1200 epochs
following the training protocol of Kim et al. (2020). As a result, Co-Mixup consistently improves Top-1 error rate over baselines by 0.67%. In the ImageNet experiment, we follow the experimental protocol provided in Puzzle Mix (Kim et al., 2020), which trains ResNet-50 (He et al., 2015) for 100 epochs. As a result, Co-Mixup outperforms all of the baselines in Top-1 error rate. We further test Co-Mixup on the speech domain with the Google commands dataset and VGG-11 (Simonyan and Zisserman, 2014). We provide a detailed experimental setting and dataset description in Appendix F.1. From Table 1, we confirm that Co-Mixup is the most effective in the speech domain as well.

heading: 5.2 Localization
text: We compare weakly supervised object localization (WSOL) performance of classifiers trained on ImageNet (in Table 1) to demonstrate that our mixup method better guides a classifier to focus on salient regions. We test the localization performance using CAM (Zhou et al., 2016), a WSOL method using a pre-trained classifier. We evaluate localization performance following the evaluation protocol in Qin and Kim (2019), with binarization threshold 0.25 in CAM. Table 2 summarizes the WSOL performance of various mixup methods, which shows that our proposed mixup method outperforms other baselines.

heading: 5.3 Calibration
text: We evaluate the expected calibration error (ECE) (Guo et al., 2017) of classifiers trained on CIFAR-100. Note, ECE is calculated by the weighted average of the absolute difference between the confidence and accuracy of a classifier. As shown in Table 2, the Co-Mixup classifier has the lowest calibration error among baselines. From Figure 4, we find that other mixup baselines tend to have under-confident predictions resulting in higher ECE values even than Vanilla network (also pointed out by Wen et al. (2020)), whereas Co-Mixup has best-calibrated predictions resulting in relatively 48% less ECE value. We provide more figures and results with other datasets in Appendix F.2.

heading: 5.4 Robustness
text: In response to the recent problem raised by Lee et al. (2020) that deep neural network agents often fail to generalize to unseen environments, we consider the situation where the statistics of the foreground object, such as color or shape, is unchanged, but with the corrupted (or replaced) background. In detail, we consider the following operations: 1) replacement with another image and 2) adding Gaussian noise. We use ground-truth bounding boxes to separate the foreground from the background, and then apply the previous operations independently to obtain test datasets. We provide a detailed description of datasets in Appendix G.
With the test datasets described above, we evaluate the robustness of the pre-trained classifiers. As shown in Table 3, Co-Mixup shows significant performance gains at various background corruption tests compared to the other mixup baselines. For each corruption case, the classifier trained with Co-Mixup outperforms the others in Top-1 error rate with the performance margins of 2.86% and 3.33% over the Vanilla model.

heading: 5.5 Baselines with multiple inputs
text: To further investigate the effect of the number of inputs for the mixup in isolation, we conduct an ablation study on baselines using multiple mixing inputs. For fair comparison, we use Dirichlet(α, . . . , α) prior for the mixing ratio distribution and select the best performing α in {0.2, 1.0, 2.0}. Note that we overlay multiple boxes in the case of CutMix. Table 4 reports the classification test errors on CIFAR-100 with PreActResNet18. From the table, we find that mixing multiple inputs decreases the performance gains of each mixup baseline. These results demonstrate that mixing multiple inputs could lead to possible degradation of the performance and support the necessity of considering saliency information and diversity as in Co-Mixup.

heading: 6 Conclusion
text: We presented Co-Mixup for optimal construction of a batch of mixup examples by finding the best combination of salient regions among a collection of input data while encouraging diversity among the generated mixup examples. This leads to a discrete optimization problem minimizing a novel submodular-supermodular objective. In this respect, we present a practical modular approximation and iterative submodular optimization algorithm suitable for minibatch based neural network training. Our experiments on generalization, weakly supervised object localization, and robustness against background corruption show Co-Mixup achieves the state of the art performance compared to other mixup baseline methods. The proposed generalized mixup framework tackles the important question of ‘what to mix?’ while the existing methods only consider ‘how to mix?’. We believe this work can be applied to new applications where the existing mixup methods have not been applied, such as multi-label classification, multi-object detection, or source separation.

heading: Acknowledgements
text: This research was supported in part by Samsung Advanced Institute of Technology, Samsung Electronics Co., Ltd, Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2020-0-00882, (SW STAR LAB) Development of deployable learning intelligence via self-sustainable and trustworthy machine learning), and Research Resettlement Fund for the new faculty of Seoul National University. Hyun Oh Song is the corresponding author.

heading: A Supplementary notes for objective
text: A.1 Notations
In Table 5, we provide a summary of notations in the main text.
A.2 Interpretation of compatibility
In our main objective Equation (1), we introduce a compatibility matrix A = (1−ω)I +ωAc between inputs. By minimizing 〈oj , oj′〉A for j 6= j′, we encourage each individual mixup examples to have high compatibility within. Figure 5 explains how the compatibility term works by comparing simple cases. Note that our framework can reflect any compatibility measures for the optimal mixup.
1
3 2
1
2 3
$%&
$'& $&'
$%'
Output 1 Output 2 Output 1 Output 2
Figure 5: Let us consider Co-Mixup with three inputs and two outputs. The figure represents two Co-Mixup results. Each input is denoted as a number and color-coded. Let us assume that input 1 and input 2 are more compatible, i.e., A12 A23 and A12 A13. Then, the left Co-Mixup result has a larger inner-product value 〈o1, o2〉A than the right. Thus the mixup result on the right has higher compatibility than the result on the left within each output example.

heading: B Proofs
text: B.1 Proof of proposition 1
Lemma 1. For a positive semi-definite matrix A ∈ Rm×m+ and x, x′ ∈ Rm, s(x, x′) = xᵀAx′ is pairwise supermodular.
Proof. s(x, x) + s(x′, x′)− s(x, x′)− s(x′, x) = xᵀAx+ xᵀAx− 2xᵀAx′ = (x− x′)ᵀA(x− x′), and because A is positive semi-definite, (x− x′)ᵀA(x− x′) ≥ 0.
Proposition 1. The compatibility term fc in Equation (1) is pairwise supermodular for every pair of (zj1,k, zj2,k) if A is positive semi-definite. Proof. For j1 and j2, s.t., j1 6= j2, max { τ, ∑m′ j=1 ∑m′ j′=1,j′ 6=j( ∑n k=1 zj,k) ᵀA( ∑n k=1 zj′,k) } = max{τ, c + 2zᵀj1,kAzj2,k} = −min{−τ,−c − 2z ᵀ j1,k
Azj2,k}, for ∃c ∈ R. By Lemma 1, −zᵀj1,kAzj2,k is pairwise submodular, and because a budget additive function preserves submodularity (Horel and Singer, 2016), min{−τ,−c− 2zᵀj1,kAzj2,k} is pairwise submodular with respect to (zj1,k, zj2,k).
B.2 Proof of proposition 3
Proposition 3. The modularization given by Equation (2) satisfies the criteria.
Proof. Note, by the definition in Equation (1), the compatibility between the jth and j′th outputs is oᵀj′Aoj , and thus, v ᵀ -joj represents the compatibility between the j
th output and the others. In addition, ‖oj‖1 = ‖ ∑n k=1 zj,k‖1 = ∑n k=1 ‖zj,k‖1 = n. In a local view, for the given oj , let us define a vector o′j as o′j [i1] = oj [i1] + α and o′j [i2] = oj [i2] − α for α > 0. Without loss of generality, let us assume v-j is sorted in ascending order. Then, vᵀ-joj ≤ v ᵀ -jo ′ j implies i1 > i2, and because the max function preserves the ordering, max{τ ′, v-j}ᵀoj ≤ max{τ ′, v-j}ᵀo′j . Thus, the criterion 1 is locally satisfied. Next, for τ ′ > 0, ‖max{τ ′, v-j}ᵀoj‖1 ≥ τ ′‖oj‖1 = τ ′n. Let ∃i0 s.t. for i < i0, v-j [i] < τ ′, and for i ≥ i0, v-j [i] ≥ τ ′. Then, for oj containing positive elements only in indices smaller than i0, max{τ ′, v-j}ᵀoj = τ ′n which means there is no extra penalty from the compatibility. In this respect, the proposed modularization satisfies the criterion 2 as well.
C Implementation details
We perform the optimization after down-sampling the given inputs and saliency maps to the specified size (4×4). After the optimization, we up-sample the optimal labeling to match the size of the inputs and then mix inputs according to the up-sampled labeling. For the saliency measure, we calculate the gradient values of training loss with respect to the input data and measure `2 norm of the gradient values across input channels (Simonyan et al., 2013). In classification experiments, we retain the gradient information of network weights obtained from the saliency calculation for regularization. For the distance in the compatibility term, we measure `1-distance between the most salient regions.
For the initialization in Algorithm 1, we use i.i.d. samples from a categorical distribution with equal probabilities. We use alpha-beta swap algorithm from pyGCO1 to solve the minimization step in Algorithm 1, which can find local-minima of a multi-label submodular function. However, the worst-case complexity of alpha-beta swap algorithm with |L| = 2 is O(m2n), and in the case of mini-batch with 100 examples, iteratively applying the algorithm can become a bottleneck during the network training. To mitigate the computational overhead, we partition the mini-batch (each of size 20) and then apply Algorithm 1 independently per each partition.
The worst-case complexity theoretic of the naive implementation of Algorithm 1 increases exponentially as |L| increases. Specifically, the worst-case theoretic complexity of the alphabeta swap algorithm is proportional to the square of the number of possible states of zj,k, which is proportional to m|L|−1. To reduce the number of possible states in a multi-label case, we solve the problem for binary labels (|L| = 2) at the first inner-cycle and then extend to multi labels (|L| = 3) only for the currently assigned indices of each output in the subsequent cycles. This reduces the number of possible states to O(m+ m̄|L|−1) where m̄ m. Here, m̄ means the number of currently assigned indices for each output.
1https://github.com/Borda/pyGCO
Based on the above implementation, we train models with Co-Mixup in a feasible time. For example, in the case of ImageNet training with 16 Intel I9-9980XE CPU cores and 4 NVIDIA RTX 2080Ti GPUs, Co-Mixup training requires 0.964s per batch, whereas the vanilla training without mixup requires 0.374s per batch. Note that Co-Mixup requires saliency computation, and when we compare the algorithm with Puzzle Mix, which performs the same saliency computation, Co-Mixup is only slower about 1.04 times. Besides, as we down-sample the data to the fixed size regardless of the data dimension, the additional computation cost of Co-Mixup relatively decreases as the data dimension increases. Finally, we present the empirical time complexity of Algorithm 1 in Figure 6. As shown in the figure, Algorithm 1 has linear time complexity over |L| empirically. Note that we use |L| = 3 in all of our main experiments, including a classification task.

heading: D Algorithm Analysis
text: In this section, we perform comparison experiments to analyze the proposed Algorithm 1. First, we compare our algorithm with the exact brute force search algorithm to inspect the optimality of the algorithm. Next, we compare our algorithm with the BP algorithm proposed by Narasimhan and Bilmes (2005).
D.1 Comparison with Brute Force
To inspect the optimality of the proposed algorithm, we compare the function values of the solutions of Algorithm 1, brute force search algorithm, and random guess. Due to the exponential time complexity of the brute force search, we compare the algorithms on small scale experiment settings. Specifically, we test algorithms on settings of (m = m′ = 2, n = 4), (m = m′ = 2, n = 9), and (m = m′ = 3, n = 4) varying the number of inputs and outputs (m, m′) and the dimension of data n. We generate unary cost matrix in the objective f by sampling data from uniform distribution.
We perform experiments with 100 different random seeds and summarize the results on Table 6. From the table, we find that the proposed algorithm achieves near optimal solutions over various settings. We also measure relative errors between ours and random guess, (f(zours)− f(zbrute))/(f(zrandom)− f(zbrute)). As a result, our algorithm achieves relative error less than 0.01.
D.2 Comparison with another BP algorithm
We compare the proposed algorithm and the BP algorithm proposed by Narasimhan and Bilmes (2005). We evaluate function values of solutions by each method using a random
unary cost matrix from a uniform distribution. We compare methods over various scales by controlling the number of mixing inputs m.
Table 7 shows the averaged function values with standard deviations in the parenthesis. As we can see from the table, the proposed algorithm achieves much lower function values and deviations than the method by Narasimhan and Bilmes (2005) over various settings. Note that the method by Narasimhan and Bilmes (2005) has high variance due to randomization in the algorithm. We further compare the algorithm convergence time in Table 8. The experiments verify that the proposed algorithm is much faster and effective than the method by Narasimhan and Bilmes (2005).

heading: E Hyperparameter settings
text: We perform Co-Mixup after down-sampling the given inputs and saliency maps to the pre-defined resolutions regardless of the size of the input data. In addition, we normalize the saliency of each input to sum up to 1 and define unary cost using the normalized saliency. As a result, we use an identical hyperparameter setting for various datasets; CIFAR-100, Tiny-ImageNet, and ImageNet. In details, we use (β, γ, η, τ) = (0.32, 1.0, 0.05, 0.83) for all of experiments. Note that τ is normalized according to the size of inputs (n) and the ratio of the number of inputs and outputs (m/m′), and we use an isotropic Dirichlet distribution with α = 2 for prior p. For a compatibility matrix, we use ω = 0.001.
For baselines, we tune the mixing ratio hyperparameter, i.e., the beta distribution parameter (Zhang et al., 2018), among {0.2, 1.0, 2.0} for all of the experiments if the specific setting is not provided in the original papers.

heading: F Additional Experimental Results
text: F.1 Another Domain: Speech
In addition to the image domain, we conduct experiments on the speech domain, verifying Co-Mixup works on various domains. Following (Zhang et al., 2018), we train LeNet (LeCun
F.2 Calibration
In this section, we summarize the expected calibration error (ECE) (Guo et al., 2017) of classifiers trained with various mixup methods. For evaluation, we use the official code provided by the TensorFlow-Probability library2 and set the number of bins as 10. As shown in Table 10, Co-Mixup classifiers have the lowest calibration error on CIFAR-100 and Tiny-ImageNet. As pointed by Guo et al. (2017), the Vanilla networks have overconfident predictions, but however, we find that mixup classifiers tend to have under-confident predictions (Figure 7; Figure 8). As shown in the figures, Co-Mixup successfully alleviates the over-confidence issue and does not suffer from under-confidence predictions.
F.3 Sensitivity analysis
We measure the Top-1 error rate of the model by sweeping the hyperparameter to show the sensitivity using PreActResNet18 on CIFAR-100 dataset. We sweep the label smoothness coefficient β ∈ {0, 0.16, 0.32, 0.48, 0.64}, compatibility coefficient γ ∈ {0.6, 0.8, 1.0, 1.2, 1.4}, clipping level τ ∈ {0.79, 0.81, 0.83, 0.85, 0.87}, compatibility matrix parameter ω ∈ {0, 5 · 10−4, 10−3, 5 · 10−3, 10−2}, and the size of partition m ∈ {2, 4, 10, 20, 50}. Table 11 shows that Co-Mixup outperforms the best baseline (PuzzleMix, 20.62%) with a large pool of
2https://www.tensorflow.org/probability/api_docs/python/tfp/stats/expected_calibration_error
hyperparameters. We also find that Top-1 error rate increases as the partition batch size m increases until m = 20.
F.4 Comparison with non-mixup baselines
We compare the generalization performance of Co-Mixup with non-mixup baselines, verifying the proposed method achieves the state of the art generalization performance not only for the mixup-based methods but for other general regularization based methods. One of the regularization methods called VAT (Miyato et al., 2018) uses virtual adversarial loss, which is defined as the KL-divergence of predictions between input data against local perturbation. We perform the experiment with VAT regularization on CIFAR-100 with PreActResNet18 for 300 epochs in the supervised setting. We tune α (coefficient of VAT regularization term) in {0.001, 0.01, 0.1}, (radius of `-inf ball) in {1, 2}, and the number of noise update steps in {0, 1}. Table 12 shows that Co-Mixup, which achieves Top-1 error rate of 19.87%, outperforms the VAT regularization method.

heading: G Detailed description for background corruption
text: We build the background corrupted test datasets based on ImageNet validation dataset to compare the robustness of the pre-trained classifiers against the background corruption.
ImageNet consists of images {x1, ..., xM}, labels {y1, ..., yM}, and the corresponding groundtruth bounding boxes {b1, ..., bM}. We use the ground-truth bounding boxes to separate the foreground from the background. Let zj be a binary mask of image xj , which has value 1 inside of the ground-truth bounding box bj . Then, we generate two types of background corrupted sample x̃j by considering the following operations:
1. Replacement with another image as x̃j = xj zj + xi(j) (1 − zj) for a random permutation {i(1), ..., i(M)}.
2. Adding Gaussian noise as x̃j = xj zj + (1 − zj), where ∼ N(0, 0.12). We clip pixel values of x̃j to [0, 1].
Figure 10 visualizes subsets of the background corruption test datasets.

heading: H Co-Mixup generated samples
text: In Figure 12, we present Co-Mixup generated image samples by using images from ImageNet. We use an input batch consisting of 24 images, which is visualized in Figure 11. As can be seen from Figure 12, Co-Mixup efficiently mix-matches salient regions of the given inputs maximizing saliency and creates diverse outputs. In Figure 12, inputs with the target objects on the left side are mixed with the objects on the right side, and objects on the top side are mixed with the objects on the bottom side. In Figure 13, we present Co-Mixup generated image samples with larger τ using the same input batch. By increasing τ , we can encourage Co-Mixup to use more inputs to mix per each output.

Review summaries:
This paper proposes a new batch mixup method, co-mixup, to improve the networks’ generalization performance and robustness. It formulates the construction of a batch of mixup data by maximizing the data saliency measure of each individual mixup data and the supermodular diversity among the constructed mixup data. An iterative submodular minimization algorithm is used to solve the proposed problem through approximation. Promising empirical performance is reported on several tasks. 

This paper proposes a new mixup method that encourages diversity among the samples mixed from a minibatch of data in addition to saliency of each mixed sample. The authors formulate two objectives: 1. a BP set function (submodular + supermodular), and 2. a submodular relaxation obtained by modularizing the supermodular component. Then they solve this problem approximately with coordinate descent by modularizing wrt the update coordinate at each step. This approach outperforms mixup baselines on image classification and several other tasks (calibration, object localization, and robustness).