Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity
Authors: JangHyun Kim
Wonho Choo
Hosan Jeong
Hyun Oh Song
Venue: ICLR 2021 Oral (2021)
Keywords: Data Augmentation
Deep Learning
Supervised Learning
Discrete Optimization

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.

Published as a conference paper at ICLR 2021
Co- CO-MIXUP: SALIENCY GUIDED JOINT MIXUP WITH SUPERMODULAR DIVERSITY
Jang-Hyun Kim, Wonho Choo, Hosan Jeong, Hyun Oh Song Department of Computer Science and Enginecring. Scoul National University Neural Processing Rescarch Center {janghyun, wonho. choo, grazinglion, hyunoh suu.b..snuacc.. ac. kr
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 a challenge. Although number of mixup based augmentation strategies have been proposed to partially address them, it remains unclear 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 novel discrete optimization problem minimizing the difference between submodular functions. We also propose an efficient modular approximation based itcrative 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 ion, calibralion, and weakly super- vised localization results compared to other mixup methods. The source code is available at https://github: hww.hu...oomeeeeeeeeeeeeeeeeeeee s/sssmu Batp//suumlaaa/oMMMMaaa
INTRODUCTION
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 casily overfit to training data and show a large gencralization gap when tested on previously unseen data.
To improve the generalization performance of the neural networks, 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, new task- independent data augmentation technique, called micup. has been proposed (Zhang et al.] 2018). The original mixup, called Input Micup, linearly interpolates 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 manifold mixup (Verma) let al. 2019) or CutMix (Yun et al. 2019), have also been proposed addressing different ways to mix a given pair of input data. Puzzle Mir (Kim el al. 2020) utilizes saliency information and local statistics to ensure mixup data to have rich supervisory signals.
However, these approaches only consider mixing 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 simultaneousl consider mix- matching different salient regions among all input data that each generated mixup example accumulates as many salient regions from multiple input data as possible while ensuring
Correspondence to: Hyun Oh Song.

---

Published as a conference paper at ICLR 2021
Input batch
Random sampled pair
Input Mixup
CuiMix
Puzzle Mix
Co- Co-Mixup
Wessel (0.6) Deer (0.4)
Wreel 10 81 Deet (0.2)
Weesel (0.5) Deer (0.3)
Bird (0.0) Fiah (u
Bizd (0:4) Dog (0.8)
Shack 1b.ck
(0.3) Fasi
Bizd (0
Figure 1: Example comparison of existing mixup methods and the proposed Co-Mixup. We provide more samples in Appendix H
diversity among the generated mixup examples. To this end, we propose novel optimization problem that maximizes the saliency measure of each individual mixup example while encouraging diversity among them collectively. This formulation results in novel discrete objective. We also propose 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 [ while the proposed method, Co-Mirup, mix-matches the collection of salient regions utilizing anter-araangemenss among input data, the cxisting mothods do not consider the saliency information (Input Mixup & CutMix) disassemble salient parts (Puzzle Mix).
submodular-superneee
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 Chrabaszzz et al., 2017 Deng et al. 2009 Warden 2017). Our experiments show the models trained with Co- Co-Mixup achieve the state of the perlormance 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.
2 RELATED WORKS
Mixup Data augmentation has been widely used to prevent. deep neural nerksrks from over-fitting to the training data (Bishop) 1995). The majority of conventional augmentation methods generate new data by applying transformations depending the data type or the target task (Cubuk et al. 2019). Zhang et al. (2018) proposed miaup, which can be independently applied to various data types and tasks, and improves generalization and robustness of deep noural networks. Input mixup (Zhang et al.) 2018) lincarly interpolates between two input data and utilizes the mixed data with the corresponding soft label for training. Following this work, manifold mirup (Verma el al. 2019) applies the mixup in the hidden feature space, and OulMic Yunn al. 2019) suggests a spatial copy and paste based mixup strategy on images. Guo et al. (0019) trains an additional neural network to optimize mixing ratio. Puzzle Mix (Kim
2020) proposes mixup method based on saliency and local statistics of the given data. In this paper, we propose a discrcte optimization- mixup method simultancously 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. (003) 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 al.) 2015 Wang al. 2015) or to reduce the saliency computation cost ęZhou et al.) 2016: Sel Selvaraju et al.] 2017). The saliency information widely applied to the tasks various domains, such as object segmentation speech
recognition (Jung and Kim 2011 Kalinli and Narayanan, 2007
2

---

Published as a conference paper at ICLR 2021
Submocuuar-Superroodie optimization A submodular (supermodular function is 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 (lyer 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).
PRELIMINARY
Existing mixup methods return (1()),, h(am, Zs(m)) for given imput data f2i....,Tmm} J. where h X x X - X is a mixup function and (i(1)....,df 1(m)) is a ran- dom permutation of the data indices. In the case of input mixup, h(xx,²²) Ax (1 A)a', where À E [0, 1] is a random mixing ratio. Manifold mixup applies input mixup in the hidden feature space, and CutMix uses h(xr,=')
1 + (1 B) o x', where B is binary rectangular-shape mask for an image and C represents the dlement-wise product. Puzzle Mix defines h(2, x') as O aTT (1 2) @ Il'T'', where II is transport plan and a discrete mask. In detail, for R", IE E {0, 1) and L for
( 1 0, 1, ...., L).
In this work, we extend the cxisting mixup functions as h h x + x which performs mixup on collection of input data and returns another collection. Let xn E Rm denote the batch of input data in matrix form. Then, our proposed mixup function is
h(#B) = (9(2) FB), .............................. ... (2m @ xB)),
where 2j E L for j = 1,..,, m' with L = E 1 0, 0,,, returns column-wiss sum of a given matrix. Note that, the 1th column of 2j, denoted as Zj,h E L can be interpreted as the mixing ratio among m inputs at the hth location. Also, we enforce ||z 1 to maintain the overall statistics of the given input batch. Given the one-hot target labels yB {0, m of the input data with C classes, we generate soft target labels for mixup data as 0Bō5 for j 1,.... m', where o = Eh= ²j, E [0. 1j 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.
(....:.) L} and g R=xn + R=
4 METHOD
4.1 OBJECTIVE
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 see from CutMix in Figure [ disregarding saliency can give misleading supervisory signal by generating mixup data that does not match with the target soft label. While the existing mixup met hods only consider the mixup between two inputs, we generalize the number of inputs m to any positive integer. Note, each bthh 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 4th location as E IR"". For the saliency measure, we calculate the gradient values of training loss with respect measure & norm of the gradient values across input channels (Simonyan et al.] [2033] Kim et. al., 2020). Note that this method does not require any additional architecture dependent modules for saliency caleulation. 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:
the input and
m
m
Σ
Σ
(1- -
(1
log ((2,,),,
1=1 (EN
3

---

Published as a conference paper at ICLR 2021
80
small r large
Batch salienty
2.36
1.0
1.5
60
Diversity
Objective
Counte
0.8
1.0
40
1.2
0.6
basdinna
0.5
unaty
20
1.0
0.4
but not salient but not diverse
Diverse
Salient
Number of mixed inputs
2
3
5
6
Ro-maxx
Ioput PuzsleMix
CutMix Co-Mixup
0.4
(a)
(b)
(c)
(d)
Figure 2: (a) Analysis of our BP optimization problem. The x-axis is onc-dimensional arrangement of solutions: The mixed output is more salient but not diverse towards the right and less salient but diverse on the left. The unary term (red) decreases lowards the right side of the axis, while the supermodular lerm (green) increases. By optimizing the sum of the two terms (brown), of imputs mixed for each output given a batch of 100 examples from the ImageNet dataset. As increases, more inputs are used to create cach output average. (c) Mean batch saliency measurement the saliency measure of each input to sum up to 1. (d) Diversity measurement of a batch of mixup data. We calculate the diversity as 1 - E, E5'es 0J of0.//m where oj 0j/[|o//ıı. We can control the diversity among Co-Mixup data (red) and find the optimum by controlling r.
obtain the balanced output 2". (b) A histogram of the number
a batch of mixup data using the ImageNet dataset. We normalize
where the prior p is given by 2j,6 Dirichlet(a, a), which is generalization of the mixing ratio distribution of Zhang ct al. 2018). and N denotes a set of adjacent locations (i.e., neighboring image patches in vision, subsequent spectrums in speech, etc.).
T. ).Multi(L,A) with À == -A Ama)
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 similarity penalty between outputs. First, we represent the input source information of the jth output by aggregating assigned labels as E 2j,k- For simplicity, let us denote Σn= Zj,6 as Oj. Then, we measure the similarity between 0y's by using the inner-produce on RT. In addition to the imput source similarity between outputs, we model the compatibility between input sources, represented as a symmetric matrix Ag E RT Rmx Specifically, Aclh1 i2] quantifies the degree to which input in and iz suitable to be mixed together. In summary, we use inner-product on A = (1 - w) + WAg for w E [0, 1], resulting in a supermodular penalty term. Note that, by minimizing (oj,0y)
Aoy, Vj * 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 Acli,j] = ||argmax,
8,(k), argmax, [k]]|,, where is the saliency map of the 7th input and location index (e.g., is 2-D index for image data). From now on, we denote this inner-product term as the compatibility term
Aver-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' - 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 singletons without any mixup. To mitigate the over 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 certain level.
4

---

is pairwise supermodular for Published as a conference paper at ICLR 2021
Now present our main objective following:
argmin f(z),
S. || 1 =1
where
m n f(2) Σ
m
2 +
Σ
Σ (1- 2T,23),0))
(1)
==1 km
j=1 (K.A))N
m
Y72
+ y max
T,
Jj.k
3j
log 1o,,(z;;)))
=f((s)
In Figure 2 we describe the properties of the BP optimization problem of Equation and statistics of the resulting mixup data. Nexi, we verify the supermodularity of the compatibility term. We first extend the definition of the submodularity a multi-label function follows (Windheuser et al. 2012).
Definition 1. For given label set f., function 8: L L + R is poirwise submodular, if Vx, x' E f s(x, ( + s(x', ,x) S a(x, x'), ss0', A function is pairwise supermodular, if -s is pairwise submodular.
Proposition 1. The compatibility term fe in Equation every pair of (2) =jz,k) if A positive semi-definite.
Proof. See Appendix B.1
Finally note that, A = (1 w)l + WAe, where A. is a symmetric matrix. By using spectral decomposition, As can be represented as UDUT, where is diagonal matrix and UT = UUT = I. Then, A = U(( w)I + wD)UT, and thus for small w >> O, we can guarantee to be positive semi-definite.
4.2 ALCORITHM
Our main objective consists of modular (wnary, prior), submodular (smoothness). and super- modular (compatibility) terms. To optimize the main objective, we employ the submodular- supermodular procedure by iteratively approximating the supermodular term modular function (Narasimhan and Bilmes 2005). Note that represents the labeling of the jth out- put and 0j represents the aggregated input source information of the jth output, Σ Pj.k- Before introducing our algorithm, we first inspect the simpler case without clipping.
Proposition 2. The compatibility term fo without clipping is modular with respect to 2j.
Proof. Note, A is a positive symmetric matrix by the definition. Then, for an index jo, represent fo without clipping in terms of Ojo Σ D AoA 2 Ey= + Ey=L/ A0 = (2 Ei= Ao, +c v %
C, where U.jo E R and c E R are values independent with of.. Finally, UI oj tc Σl= "I 3jok + c is modular function of žju-
By Proposition 2 we apply submodular minimization algorithm to optimize the
objective with respect to žj 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 certain level.
5

---

Published as a conference paper at ICLR 2021
modularization Eguation (1) with respoct to
3. Solve moduuacted Equation (1) For 25
Compute modulee approdimated diveriity for 2,
Input batch
Mixedd ourpat batch
Figure 3: Visualization of the proposed mixup procedure. For given batch of input data (left), batch mixup data (right) generated, which mix-matches different salient regions among the input data while preserving the diversity among the mixup examples. The histograms on the right represent the input source information of each mixup data (0z).
Borrowing the notation from the proof in Proposition 2 for an index j. fo(=) = max (T, v' + c} = max(7 c, o
} + Note, = = Zj,h represents the input source information of the 5th output and æ, EF Aoj- encodes the status of the other outputs. Thus, we can interpret the supermodular term as a penalization of each label of oy in proportion to (criterion 2). As a modular function which satisfies the criteria above, we use the following function:
the corresponding v., value (criterion 1), but not for the compatibility below
fe(z) x max{7', U.y)Too for E
Note that, by satisfying the criteria above, the modular function reflects the diversity and perrpennliiaaton 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
By applying the modular approximation de-
Algorithm 1 Iterative submodular minimiza-
scribed in Equation (2) to fe in Equation [ we can iteratively apply a submodular min- imization algorithm
tion
obtain the final so- lution described in Algorithm [ In de- tail, each step can be performed as follows: 1) Conditioning the main objective f on the current values except Zj, denoted as fz,)) f(zy 21:j-1, 21:j-12 Zz+1:m²).. 2) Modu- larization of the compatibility term f Equation ( resulting in submodular function J5- We denote the modularization operator as & i.e., f, Φ(f)). 3) Applying a submodular minimization algorithm to f/ Please refer to Appendix C for implementa- tion details.
Initialize = as 20)
Let 2(1) denote solution of the tth step.
4: modularization operator based on Equa- tion (2)
for t == 1...., do
for j = 1,...,, do
(1-1) (1) (2)) = f(zj; 1ig 1:5-11 2 2++lmm²
1 4( ((f,²))
Solve 2,
(t) argmin F/ (zy).
end for end for return (T)
Analysis Narasimhan and Bilmes (2005) proposed a modularization strategy for general supermodular set functions, and apply submodular mininization algorithm that can monotonically decrease the original BP objective. However, the proposed Algorithm [ 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 assume

---

Published as a conference paper at ICLR 2021
each 2j,6 is m-dimensional one-hot vector. Then, our problem is to optimize m' one-hot m-ddimensional vectors.
To apply the set modularization method, need to assign each possible value of 2G
element {1, .....,.......................... Then the supermodular term in Equation (1) can be interpreted as m'nm nm elements, and to apply the set modularization, (m' nm) sequential evaluations of the supermodular term are required. In contrast, Algorithm calculates vij 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 2,,6 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)
set function with m'
EXPERIMENTS
We evaluate our proposed mixup method on generalization, weakly supervised object local- ization, calibration, and robustness tasks. First, we compare the generalization performance of the proposed method against basclines by training classifiers on CIFAR-100 (Krizhevsky
let al. 2009). Eny-ImmgeNet (Chrabaszez et al. 2017 ImageNet (Deng et al. 2009), and the Google commands speech dataset (Warden 2017 Nexi, we Lest the localization performance of classifiers following the evaluation protocol of Qin and Kim (2019). We also measure calibration error (Guo et al.) (017)) 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 ct al. (2020) that deep neural network agents often fail to generalize to unseen environments. Finally, we perform sensitivity analysis of Co-Mixup and provide the results in Appendix F.3
5.1 CLASSIFICATION
We first train PreActResNet188 (He ct al. 2016), WRN16-8 (Zagoruyko and Komodakis 2016), and ResNeXt2994222 (Xic al. 2017 on CIFAR-100 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 mnmentun 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
let al. 2019 Yun et al. 2019 Kim et al. 2020), which we denote as Variilaa, Input, Manifold, CutMiz, Puzzle Mir in the experiment tables. Note that use identical hyperparameters regarding Co-Mixup over all of the experiments with different models and datasets, which are provided in Appendix
Table I shows Co-Mixup significantly outperforms all other basclines in Top-1 error rate. Co-Mixup achieves 19.87% in Top-1 error rate with PreActResNet18 oulperforming the best baseline by 0.75%. We further lest Co-Mixup on different models (WRN16-8 & ResNeXi22 4-24) and verify Co-Mixup improves Top-1 error rate over the best performing baseline.
Dataset (Model)
Vanilla
Input
Manifold
CutMix
Puzale Mix
Co-Mixup
CIPAR- (e)
23.59
22.43
20.62
19.87
CIFAR-100 (WRN16-8)
21.70
20.08
20.55
20.14
19.24
19.15
CIFAR-100 (ResNeXe29-t-24))
21.79
21.70
22 28
21.86
21.12
19.78
Tiny- ImageNet (PreActllesNeet1))
43.40
43.48
40.76
43.11
36.52
35.85
ImageNet (ResNet-50. 100 epochs)
21.03
22.97
23.30
22 92
22.19
22.39
Google commands (VGG-11)
4.84
3.91
3.76
3.70
3.54
Table Top-1 error rate on various datasets and models. For CIFAR-100, we train each model with three different random seeds and report the mean error.
We further test Co-Mixup on other datasets; Enageem ImageNet, and the Google commands dataset. (Table I. For Timy-ImageNet, train PreAct Nes 18 for 1200 epochs
7

---

Published as a conference paper at ICLR 2021
Vanilla
Input
Manifold
CutMix
Puzzle
Co-Mixup
Accuracy
Confidence
Figure 4: Confidence-Accuracc plots for classifiers on CIFAR-100. From the figure, the Vanilla network shows over-confident predictions, whereas other mixup baselines tend to have under-confident predictions. We can find that Co-Mixup has best-calibrated predictions.
following the training protocol of Kim al. (2020). As result, Co-Mixup consistently improves Top-1 error rate over baselines by 0.67% %.. In the ImageNet experiment, we follow the experimental prolocol provided in Puzzle Mix (Kim et al. 2020), which trains Nes.ett-5 (He et al. 2015) for 100 epochs. As result, Co-Mixup outperlorms 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 detailed experimental setting and dataset description in Appendix [..1 From Table we confirm that Co-Mixup is the most effective in the speech domain as well.
5.2 LOCALIZATION
We compare weakly supervised object localization (WSOL) performance classifiers trained on ImageNet (in Table to demonstrate that mixup method better guides classifier to focus on salient regions. We test the localization performance using CAM (Zhou et al.] 2016), 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 summarizes the WSOL performance of various mixup methods, which shows that our proposed mixup method outperforms other baselines.
5.3 CALIBRATION
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 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 lend have wnder-confadent 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
Task
Vanilla
Input
Manifold
CutMix
Puzzle Mix Co-Mixup
Localization (Acc. %) (t)
54.36
55.07
54.86
54.91
55.22 7.5
55.32
Calibration (ECE %) (4)
3.9
17.7
13.1
5.6
1.9
Table 2: WSOL results on ImageNet and ECE (%) measurements of CIFAR-100 classifiers.
5.4 ROBUSTNESS
In response the recent problem raised by Loe 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, consider the following operations: 1) replacement
unchanged, but with the corrupted
(or replaced) background. In detail, with another image and 2) adding Gaussian noise. We use ground-trun -ouuh 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
8

---

Published as a conference paper at ICLR 2021
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.
Corruption type
Vanilla
Input
Manifold
CutMix
Puzzle Mix
Co-Mixup
Random replacement
41.63
39.41
39.72
46.20
39.23
38.77
(+17.62)
(+16.47)
(4-16.47)
(+223.16
(+16.69)
(+16.38)
Gaussian noise
29.22
26.29
26.79
27.
26.11
25.89
(+5.21)
(+3.35)
(+3.54)
(+-4.09)
(+3.57)
(+3.49)
Table 3: Top-1 error rates of various mixup methods for background corrupted ImageNet validation set. The values in the parentheses indicate the error rate increment by corrupted inputs compared to clean inputs.
5.5 BASELINES WITH MULTIPLE INPUTS
To further investigate the effect of the number of inputs for the mixup in isolation, conduct an ablation study on basclines using multiple mixing inputs. For fair comparison, we Dirichlet(a, a)) prior for the mixing ratio distribution and select the best performing in {0.2, 1.0, 2.03. Note that we overlay multiple boxes in the case of CutMix. Table reports the classification test errors on CIFAR-100 with PreActResNet1S. From the table, we find that mixing multiple imputs 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.
inputs for mixup
Input
Manifold
CutMix Co-Mixup
inputs 2
22.43
21.64
21.29
inputs = 3
23.03
22.13
22.01
19.87
inputs = 4
23.12
22.07
22.20
Table 4: Top-1 rates of mixup baselines with multiple mixing inputs CIFAR-100 and PreActResNet18.. We report the mean values of three different random seeds. Note that Co-Mixup optimally determines the number of inputs for each output by solving the optimization problem.
CONCLUSION
We presented Co-Mixup for optimal construction of 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 problem minimizing a novel nubnodular--upperoooo 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 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.
discrete optimization objective. In this respect, we present

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
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 Reset Fund for the new faculty of Seoul National Universily. Hyun Oh Song is the corresponding author.
REFERENCES
C. M. Bishop. Training with noise is equivalent to tikhonov regularization. Newral compulation, 7(1):108-14) 116, 1995.
C. M. Bishop. Pattern recognition and machine learning. springer, 2006.
P. Chrabaszez, I. Loshchilov, and F. Hutter. downsampled variant of imagenet as an alternative to the eifar datasets. Xiv preprint arXiv: 00000707.88899 2017.
E. D. Cubuk, B. Zoph, D. Manc, V. Vasudevan, and Q. V. Le. Autoaugment: Learning augmentation strategies from data. In CVPR, 2019.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and F. F. Li. Imagenet: a large-scale hierarchical image database. In CVPR, 2009.
Devlin, M.W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.00 04805, 2018
S. Fujishige. Submodular functions and optimization. Elsevier, 2005.
C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In ICML, 2017.
H. Guo, Y. Mao, and R. Zhang. Mixup as locally linear out-of-manifold regularization. In AAAI, 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2015.
K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In ECCV, 2016.
T. Horel and Y. Singer. Maximization of approximately submodular functions. In NewrIPS, 2016.
R. Tyer and J. Bilmes. Algorithms for approximate minimization of the difference between submodular functions, with applications. arXiv preprint arXiv:1207.0500 056000 2012.
C. Jung and C. Kim. unified spectral-domain approach for saliency detection and its application to automatic object segmentation. IEEE Transactions on Image Processing, 21(3):1272-125) 2011.
O. Kalinli and S. S. Narayanan. saliency- auditory attention model with applications to unsupervised prominent syllable detection in speech. In Eighth Annuul Conference of the International Speech Communication Association, 2007.
J. Kim, W. Choo, and H. O. Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In ICML, 2020.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. Citesoer, 2009.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- learning applied to document recognition. Proceedings of the IEFF,
2324, 1998.
10

---

Published as a conference paper at ICLR 2021
K. Lee, K. Lee, J. Shin, and H. Lec. Network randomization: A simple technique for generalization in deep reinforcement learning. In ICLR, 2020.
L. Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art, pages 235 257. Springer, 1983.
T. Miyato, S.-i. Maeda, M. Koyama, and S. Ishii Virtual adversarial training: a regularization method for supervised and semi-supervised learning, IEEE transactions on pottern analysis and machine intelligence, 41 (189))1979-1993 2018.
M. Narasimhan and Bilmes. A submod submodular-supenne suw.s--uueeoooularr procedure with applications to discriminative structure learning. UAT, 2005.
A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, and K. Kavukeuoghu. Wavenet: A generative model for raw audio. arXw preprint Xrv:v:1609.00 03499, 2016.
Z. Qin and D. Kim. Rethinking softmax with cross-entropy: Neural network classifier as mutual information estimator. arXie preprint
2019.
S. Ren, K. He, R. Girshick, and J. Sun. Faster r-cmn: Towards real-time object detection with region proposal networks. In NewrIPS, 2015.
R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, and D. Batra. Grad-cam: Visual explanations from deep networks via gradient-based localization. In ICCV, 2017.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprinl Xi:: 1596. 2014.
K. Simonyan, A. Vedaldi, and A. Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312 6034, 2013.
V. Verma, A. Lamb, C. Beckham, A. Najafi, I. Mitliagkas, A. Courville, D. Lopez-Paz, and Y. Bengio. Manifold mixup: Better represontations by interpolating hidden states. In ICML, 2019.
L. Wang, H. Lu, X. Ruan, and M.-H. Yang. Deep networks for saliency detection via local estimation and global search. In CVPR, 2015.
P. Warden, URL dataset.html, himl, 2017.
/2011//////aumccingggg Sounching-speech-coom comeendd-
Y. Wen, G. Jerfel, R. Muller, M. W. Dusenberry, Snoek, B. Lakshminaraaanann, and D. Tran. Improving calibration of batchensemble with data augmentation. In ICML Workshop on Uncertainty and Robustness in Deep Learning, 2020.
T. Windheuser, H. Ishikawa, and D. Cremers. Generalized roof duality for multi-label optimization: Optimal lower bounds and persistency. In ECCV, 2012.
S. J. Wright. Coordinate descent algorithms. Mathematical Programming, 151(1):3-34, 2015.
S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. pages 1492-1500 2017.
S. Yun, D. Han, S. J. Oh, S. Chun, J. Choe, and Y. Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In ICCV, 2019.
Zagoruyko and N. Komodakis. Wide residual networks. orXio preprint arXi::1605.0711 07166.....666.. 2016.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint trXiv:1611.03550 2016.
H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR, 2018.
11

---

Published as a conference paper at ICLR 2021
R. Zhao, W. Ouyang, H. Li, and X. Wang. Saliency detection by multi-context deep learning. In CVPR, 2015.
B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba. Learning deep features discriminative localization. In CVPR, 2016.
A
SUPPLEMENTARY NOTES FOR OBJECTIVE
A.1 NOTATIONS
In Table we provide a summary of notations in the main text.
S
Notation
Meaning
mI, m',
imputs, # outpuls, dimension of data labeling cost for m input sources at the k*th location input source ratio at the A location of the jth output labeling of the 7th output
CK E Rd (15k5m)
2yA n (1S} 1
2j E m
Oj E R
aggregation of the labeling the 1th output compatibility between inputs
A E pm
Table summary of notations.
A.2 INTERPRETTIION OF COMPATIBILITY
In our main objective Equation (1), we introduce a compatibility matrix A wI- + WAe between imputs. By minimizing (o,, 0y) for # j', we encourage each individual mixup examples to have high compatibility within. Figure b explains how the compatibility term works by comparing simple cases. Note that our framework can reflect any compatibility measures for the optimal mixup.
A12
A13
2
3
Asz
Az3
Output
Output 2
Output 1
Output
Figure Let us consider Co-Mixup with three inputs and two outputs. The figure represents two Co-Mixup results. Each input is denoted as number and color-coded. Let assume that input 1 and input are more compatible, i.e., A12 >> A23 and A12 > A13- Then, the left Co-Mixup result has larger inner-produt value (01,02) 02) than the right. Thus the mixup result on the right has higher compatibility than the result on the left within each output example.
B PROOFS
B.1 PROOF OF PROPOSITION
Lemma 1. For positive semi-definite matrir R Rm and x, x E Rmm s(x, )= x Ax' is pairwise supermodular.
Proof. s(x, x) + s(x', x') - s(x, x') s(x',x) x Ax + AT 2r Ax' = (x x²)T A(T I²),
and because A is positive semi-definite, (x'x')
T A(r
x') 0.
12

---

Published as a conference paper at ICLR 2021
Proposition 1. The compatibility term fo in Equation (1) is pairwise supermodular for every pair of (2), kz2,k) if A is positive semi- definite
mm Proof. For ji and j2, s.b,, J1 # j2, max (T. -/= 2 Ey= TT 2
- (-, - c- 2z & Azja,tt for Ee E R. By Lemma -2 A2jz. is pairwise submodular, and because budget additive function preserves submodularity (Horel and Singer 2016). minf-r, -c -- A } is pairwise submodular with respect to (Z 22a,))
max c + 22 22 A2
B.2 PROOF OF PROPOSITION 3
Proposition 3. The modularization given by Equation (2) satisfies the criteria.
Proof. Note, by the definition in Equation (I), the compatibility between the 5th and jmhh outputs is Ao,, and thus, v.j0, represents the compatibility between the jth output and the others. In addition, ||,y]| = =1E و = -==11=zaall for the given oj, let us define a vector of as o/(in] 03(b1] + and d3 = oj [ for a > 0. Without loss of generality, let us assume t. is sorted in ascending order. Then, o0 S Edjo,, implies i i2, and because the max function preserves the ordering, max(r', 2. Toj I maxff',
|| n. In a local view,
T' 0, mmx(rr (T', ",;y)Too max No, Thus, the criterion 1 is locally satisfied. Next, for r'|10y|11 = r'n. Let 7ip s.f. for < io; v.j(1] < and for i 12 U. 2 T'. Then, for containing positive elements only in indices smaller than io. max(T' (T', &.j] ) = I'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 imput data and measure f2 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 fi-distance between the most salient regions.
For the initialization in Algorithm 1, we use i. samples from categorical distribution with equal probabilities. We use alpha-beta swap algorithm from PyGCO 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 [C] = is O(mån), 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 independently per each partition.
The worst-case complexity theoretic of the naive implementation of Algorithm 1 increases exponentially as [C] increases. Specifically, the worst-case thcoretic complexity of the alpha- beta swap algorithm is proportional to the square of the number of possible states of zj,ks which is proportional we solve the problem for binary labels (|C) = 2) at the first inner-cycle and then extend to multi labels (lC) = 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 mlI)-l) where m & m. Here, m mcans the number of currently assigned indices for each output.
ml To reduce the number of possible states in a multi-label case,
'htrps///gthhu..com/ wwwiccooom//ooooooeeee GCCO
13

---

Published as a conference paper at ICLR 2021
Based on the above implementation, train models with Co-Mixup in feasible time. For example, the case of ImageNet training with 16 Intel 19-9980XE CPU cores and 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 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 the data dimension increases. Finally, we present the empirical time complexity of Algorithm in Figure 6 As shown in the figure, Algorithm has linear time complexity over [C] empirically. Note that we use [ 3 in all of our main experiments, including classification lask.
Average Exccution Time (ms))
Avurage Exccation Time (ms))
1.1
2
10 20
50
100
m
Figure 6: Mean execution time (ms) of Algorithm 1 per each batch of data over 100 trials. The left figure shows the time complexity of the algorithm over [C] and the right figure shows the time complexity over the number imputs m. Note that the other parameters are fixed equal to the classification experiments setting, m 20, 16, and [C] = 3.
D ALGORITHM ANALYSIS
In this section, 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, compare 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, 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, = 9), and (m m' 3, = 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 Table 0 From the table, we find that the proposed algorithu achieves near optimal solutions various settings. We also measure relative errors between ours and random guess, (f(2our) - (Zbrutt) (f ((brute)). 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 random
14

---

Published as a conference paper at ICLR 2021
Configuration
Ours
Brute force (optimal)
Random guess
Rel. error
(m m' = =2, n == 4)
1.91
1.90
3.54
0.004
(m m' 2, 9)
1.93
1.91
3.66
0.01
(m- m' = 3, n = 4)
2.89
2.85
22.02
0.002
Table Mean function values of the solutions over 100 different. random seeds. Rel. error means the relative error wetween ours and random guess.
unary cost matrix from a uniform distribution. We compare methods over various scales by controlling the number of mixing inputs
Table 7 shows the averaged function values with standard deviations in the parenthesis. As see from the table, the proposed algorithm achieves much lower function values and deviations than the method by Narasimhan and Bilmes (2055) 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 g The experiments verify that the proposed algorithm is much faster and effective than the method by Narasimhan and Bilmes (2005).
Algorithm
5
10
20
50
100
Ours 3.1 (1.7)
15 (6.6)
54 (15)
205 (26)
469 (31)
Narasimhan
269 (58)
1071 (174)
4344 (701)
24955 (4439)
85782 (14337)
Random
809 (22)
7269 (92)
60964 (413)
980973 (2462)
7925650 (10381)
Table 7: Mean function values of the solutions over 100 different random seeds. We report the standard deviations the parenthesis. Random represents the random guess algorithm.
Algorithm
m = 5
m
10
m
20
=
50
m
100
Ours
0.02
0.04
0.11
0.54
2.71
Narasimhan
0.06
0.09
0.27
1.27
7.08
Table 8: Convergence time (s) of the algorithms.
E HYPERPARAMETER SETTINGS
We perform Co-Mixup after down-sampling the given inputs and saliency maps to the pre-defined resolutions regardless 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-TmageNet, and ImageNet. In details, experiments. Note that 7 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 a = 2 for prior For a compatibility matrix, we use w 0.001.
(8, (1,77
(0.32, 1.0, 0.05, 0.83) for all of
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 the original papers.
F
ADDITIONAL EXPERIMENTAL RESULTS
F.1 ANOTHER DOMAIN: SPEECH
In addition to the image domain, we conduct experiments on the speech domain, verifying Co-Mixup works various domains. Following (Zhang et. al. 2018), we train LeNet (LeCun
15

---

Published as a conference paper at ICLR 2021
Vanilla
Input
Manifold
CutMix
Puzzle
Co-Mixup
Accuracy
Confidence
Figure 7: Confidence-Acurraae plots for classifiers on CIFAR-100. Note, ECE is calculated by the mean absolute difference between the two values.
et al. 1998 and VGG-11 (Simonyan and Zissorman, 2014) on the Google commands dataset Warden 2017). The dataset consists of 65,000 utterances, and each utterance is about onc-sccond-long belonging to one out of 30 classes. We train cach classifier for 30 epochs with the same training setting and data pre-processing Zhang et al. (2018). In more detail, we use 160 100 normalized spectrograms of ulterances for training. As shown in Table g
we verify that Co-Mixup is still effective in the speech domain.
Model
Vanilla
Input
Manifold
CutMix
Puzzle Mix
Co-Mixup
LeNet
11.24
10.83
12.33
12.80
10.89 3.70
10.67
VGG-11
4.84
3.91
3.67
3.76
3.57
Table 9: Top-1 classification test error the Google commands dataset. We stop training if validation accuracy does not increase for consecutive epochs.
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, use the official code provided by the TensorFlow-Probabiitt library and set the mumber of bins as 10. As shown in Table 10 Co-Mixup classifiers have the lowest calibration error CIFAR-100 and Tiny-ImageNe confident predictions, but however,
As pointed by Guo et al. (2017), the Vanilla networks have over- 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.
Dataset
Vanilla
Input
Manifold
CutMix
Puzzle Mix
Co-Mixup
CIFAR-100
3.9
17.7
13.1
5.6
7.5
1.9
4.5
6.2
6.8
12.0
5.6
2.5
ImageNet 5.9
1.2
1.7
4.3
2.1
2.1
Table 10: Expected calibration error (%) of classifiers trained with various mixup mothods on CIFAR-100, Tiny-ImageNet and ImageNet. Note that, at all of three datascts, Co-Mixup outperforms all of the basclines in Top-1 accuracy.
F.3 SENSITIVITY ANALYSIS
We measure the Top-1 error rate of the model by sweeping the hyperparameter show the sensitivity using PreActResNet18 on CIFAR-100 dataset. We sweep the label smoothness coefficient, 3 E (0, 0.16,, 0.32, 0.48, 0.64), compatibility coefficient. 7 E (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 E (0.5 5 10-1, 1,10-3,5 10-3 10-2), and the size of partition m E (2, 4, 10, 20, 50). Table 11 shows
that Co-Mixup outperforms the best baseline (PuzzleMix, 20.62%) with large pool of
Phttps:/ httrss::/wwwwwttt
Phttpe//wwww.tensoffooo.c http:/wwwwwsorfoworrrro www.rrrggggglittoorroooro api docs/ focs/python// wttyttho/ttp////tt ttp httpsttts//att expeeteddeeeeeeeeeeeeeeeeddeeeee calibration error
16

---

Published as a conference paper at ICLR 2021
Vanilla
Input
Manifold
CutMix
Puzzle
Co-Mixup
Accurse
Confidence
Figure Aoncure plots for classifiers on
Vanilla
Input
Manifold
CutMix
Puzzle
Co-Mixup
Accuracy
Confidence
Figure 9: Confidence-Accuracy plots for classifiers on ImageNet.
hyperparameters. We also find that Top-1 error rate increases as the partition batch size m increases until m 20.
Smoothness coefficient,
8
8 0.16
[ = 0.32
B 0.48
0,64
3
20.29
20.18
19.87
20.35
21.24
Compatibility coefficient,
? 0.6
? 0.8
1.0
1.2 20.09
? 1.4 20.13
20.3
19.99
19.87
Clipping parameter,
0.79
0.81
0.83 19.87
0.85
0.87
20.45
20.14
20.15
20.23
Compatibility matrix parameter, w
w = 20.51
w 5 10
10
5- 10
w
20.42
19.87
20.18
20.14
Partition size,
m = 2
m 4
m 10
m 20
m =
m
20.3
20.22
20.15
19.87
19.96
Table 11: Hyperparameter sensitivity results (Top-1 error rates) CIFAR-100 with PreAc- Net11. We report the mean values of three different random seeds.
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 meth called VAT (Miyalo el al. 2018) uses virtual adversarial loss, which defined as the KL-divergence of predictions between input data againsl. local perturbation. CIFAR- 100 with PreActResNet18 for 300 epochs in the supervised setting. We tune a (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 crror rate of 19.87%, outperforms the VAT regularization method.
We perform the experiment with VAT regularization
G DETAILED DESCRIPTION FOR BACKGROUND CORRUPTION
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.
17

---

Published as a conference paper at ICLR 2021
#
update=0
# update=
VAT loss coefficient
E 2
6
2
0.001
23.38
23.62
24.76
26.22
a 0.01
23.14
23.67
28.33
31.95
a 0.1
23.65
23.88
34.75
39.82
Table 12: Top-1 error rates of VAT on CIFAR-100 dataset with PreActResNet18.
ImageNet consists of images {z1...., Tash labels (y1.....yys and the corresponding ground- truth bounding boxes (bi,..., bMr. We use the ground-truth bounding boxes to separate the foreground from the background. Let be a binary mask of image Ij, which has value 1 inside of the ground-truth bounding box b,. Then, we generate two types of background corrupted sample ž, by considering the following operations:
1. Replacement with another image as ž = Iy ① 2j + Ii()) 2 (1 - 29) for a random permutation {i(1)...,;(MI)
2. Adding Gaussian noise as žz O2 + (1 2z), where N(0,0.13) We clip pixel values of žj to 10, 11.
Figure
10 visualizes subsets of the background corruption test datasets.
(b)
Figure 10: Each subfigure shows background corrupted samples used in the robustness experiment. (a) Replacement with another image in ImageNet. (b) Adding Gaussian noise. The red boxes on the images represent ground-truth bounding boxes.
H CO-MIXUP GENERATED SAMPLES
In Figure 12 we present Co-Mixup generated image samples by using images from ImageNet. We use an imput batch consisting of 24 images, which is visualized in Figure [1] 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- Co-Mixup to use more inputs mix per each output.
18

---

Published as a conference paper at ICLR 2021
Figure 11: Input batch.
19

---

Published as a conference paper at ICLR 2021
Figure 12: Mixed output batch.
20

---

Published as a conference paper at ICLR 2021
Figure 13: Another mixed output batch with larger
21


Reviews:
[{"review_id": "wta5tdLlwLN", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1) Summary\n- Mixup is one of the representative data augmentation techniques to improve the generalization of the network.\n- The authors proposed the co-mixup technique which is novel.\n- Especially, the technique can mix several images with z, and the z is found by optimizing their objective function.\n- It is novel, and the experimental results are convincing. \n\n2) Strong points\n- co-mixup approach was formulated well\n- clearly outperforms the other mixup-like technique such as CutMix and Puzzle Mix\n\n3) Weak points\n- Training is slower than others, even if computing z is fast.\n- Can we mix more than three images? How about 1000 images?\n\n\nThis paper is a good one, and I look forward to acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WLSpecz00uh", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\n\nThe paper presents interesting ideas with impressive accuracy results. My biggest concerns with this work are clarity, thoroughness of experiments, and whether it is too computationally expensive to be used in practice.\n\n\nSignificance:\n- The proposed algorithm's running time may be prohibitive for some applications. In the appendix the authors mention partitioning each minibatch and running the algorithm on each partition to make running time feasible, which suggests that accuracy improves at the expense of running time. Section 4.2 presents the algorithm as having linear running time, the exponential dependence on the number of labels $|\\mathcal{L}|$ should be mentioned here\n\nExperiments:\n- The results sections compare against good baselines across several tasks, but this would be stronger if it compared to non-mixup baselines. \n- A more thorough ablation study would analyze each term in the proposed objective function, compare to the mixup baselines applied to m>2 inputs, and compare to the original set modularization method.\n- The paper proposes an alternative heuristic to the set modularization method of Narshiman and Bilmes 2005. The claim that Algorithm 1 is faster and produces better solutions would be stronger with a thorough empirical comparison to set modularization.\n\nClarity:\n- Saliency is described at a high level several times, but it's unclear how these values are actually computed in experiments\n- Notation for $z$ is somewhat difficult to parse in the statements/proofs of Propositions 1 and 2. $f(z)$ is pairwise supermodular when considering the same column index across 2 different matrices of output coefficients $(z_{j_1,k},z_{j_2,k})$ (Proposition 1), but $f(z)$ is modular when considering the full output label matrix $z_j$ (Proposition 2). What does this mean when the optimization is over all matrices $z$? Do the ground set and constraints change in each case?\n- typo: In section 4.2, \"proposition 1\" should be \"Proposition 2\"\n\nOrganization:\n- Sections 5.4 (5.5) on robustness (sensitivity) as written in the main text are not informative. They should either contain more concrete statements about results or be moved entirely to the supplementary material. \n- Also, discussion of the ground set would be much clearer if it appeared before the bottom of page 6\n\nPros\n- Improves over previous strong mixup baselines\n- The proposed method outperforms baselines even when m=2 (it's worth mentioning this in the main text even if there is not enough room for a full ablation)\n\nCons\n- Running time of the algorithm may be prohibitive in certain applications, this should be analyzed an discussed\n- Several issues with clarity and organization (see above)\n\n\nQuestions:\n- Does larger m always improve accuracy, or does this eventually decrease?\n- Exactly how is saliency computed in the experiments? Is it the same pretrained map or does it vary with architecture?\n- How much time does co-mixup take compared to training the network?\n- Are Algorithm 1 and applying mixup ideas to m>2 samples novel contribution?\n\n\nEDIT: The author response addressed all my concerns and answered all my questions, in particular that the exponential running time is a worst-case bound that is indeed loose in practice. I believe that the revised version will be much clearer and am therefore increasing my score\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ULaoVjmDSY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nAll previous mixup methods are limited to mixup example generation between a pair of input examples. This paper can be viewed as an extension of the Puzzle mixup, and it generates a mixup example over multiple input examples. The optimization problem formulated seems to be very reasonable by maximizing the saliency and diversity of the mixup data. The proposed method also demonstrates slightly better performance than other mixup methods.  Overall, this is an interesting paper.\n\nThere are however several issues that are not clear. The authors can clarify the following questions: \n\n1.\tHow are the labels of the mixup examples determined?  Will each generated example become a multi-label example? How to perform training with the generated data?\n\n2.\tAs the proposed method requires additional process to produce information such as the saliency information and compatibility information (the matrix A), won’t this induce additional computational cost?\n3.\tAs stated in the paper, the A_c matrix measures the distances between locations of salient objects in the input examples. Does this require object localization? Or it simply computes the distances between the feature locations? \n4.\tHow much does the \\omega value (to compute A) affect the performance of the proposed approach?\n\n5.\tIn Section 4.2, two criteria are described and then an approximation is proposed based on the two criteria.  Although there is nothing wrong about the criteria, it is unclear how good can an approximation be by simply satisfying these two criteria? That is, what is the quality of the approximation to the original problem?  Can the approximation guarantee an optimal solution to the original problem?\n\n6.\tIn the experiments, although the proposed approach demonstrates promising results, the differences between the proposed method and the comparison method, Puzzle Mix, are very small. The paper claims Co-Mixup significantly outperforms all other baselines. How significant are the differences in Table 1?\n\n7.\tThe paper limits the comparison to mixup methods. How is the performance level of the co-mixup by comparing with other regularization based methods? For example, VAT regularizaiton based methods.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a type of Mixup-style data augmentation that works at the batch level rather than simply between pairs of examples. Each generated example accumulates salient images from potentially many other examples while ensuring diversity across the generated examples. This is achieved through a 4-part objective with submodular and supermodular components. The paper demonstrates the method using extensive experiments, including generalization performance on CIFAR-100, Tiny ImageNet, ImageNet and GoogleCommands. It also explores weakly supervised object localization, expected calibration error, and robustness to random replacement and Gaussian noise.

Reviewer 1 thought the approach was interesting but raised some concerns with clarity, thoroughness of experiments and whether the approach was computationally prohibitive to be used in practice. I was surprised myself that a discussion on the trade-off between computational expense and accuracy gain was not discussed in the submission. The authors responded to the review, adding a comparison to the BP algorithm (Narshiman and Bilmes 2005). The empirical result seems to back up the claim that the proposed algorithm finds a better solution and with less variance. It also appears to run much faster. The authors also responded to minor issues raised with respect to clarity and organization. In their response, the authors provided considerable detail with respect to running time and time complexity, and show that models trained with co-mixup are practical, though they do come with a significant added cost. The authors added the requested comparisons to non-mixup baselines and enhanced the ablation study. In my opinion, this is a comprehensive and satisfying response, and the paper has improved in many respects since submission.

The review from R2 was largely positive, though limited in its scope. They also expressed concerns with training time (addressed in the response to R1). Clearly the approach extends to an arbitrary (m) number of images; this was explicit in the paper/formulation and clarified by the authors. I have some concern that R2 may have skimmed the paper if they missed this point.

Reviewer 4 thought the paper was interesting and asked several clarifying questions. They expressed concern with the significance of the reported gains. Similar to R1, they asked about non-mixup baselines (VAT specifically). This was addressed in the response to R1. The authors responded to the clarifying questions and addressed the issue of significance.

Like the reviewers, I think that this is an intriguing, fresh, and elegant way to perform data augmentation. I appreciate that it has been evaluated just not from the pure generalization setting, but from other angles like robustness and calibration. There are still some outstanding concerns regarding the computational effort required to use Co-Mixup, so this would be nice to see in follow-up work.
Decision: Accept (Oral)