Model Validation Using Mutated Training Labels: An Exploratory Study
Authors: Jie Zhang
Mark Harman
Benjamin Guedj
Earl Barr
John Shawe-Taylor
Venue: ICLR 2022 Submitted (2022)

Abstract: For out-of-sample validation, the sample set may be too small to be representative of the data distribution; the accuracy can have a large variance across different runs; excessive reuse of a fixed set of samples can lead to overfitting even if the samples are held out and not used in the training process. This paper introduces an exploratory study on Mutation Validation (MV), a model validation method using mutated training labels for supervised learning. MV mutates training data labels, retrains the model against the mutated data, then uses the metamorphic relation capturing the consequent training performance changes to assess model fit. It uses neither validation nor test set. The intuition underpinning MV is that overfitted models tend to fit noise in the training data. We explore 8 different learning algorithms, 18 datasets, and 5 types of hyperparameter tuning tasks. Our results demonstrate that MV is accurate in model selection: the model recommendation hit rate is 92% for MV and less than 60% for out-of-sample validation. MV also provides more stable hyperparameter tuning results than out-of-sample validation across different runs.

Under review as a conference paper at ICLR 2022
MODEL VALIDATION USING MUTATED TRAINING LA- BELS: AN EXPLORATORY STUDY
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce an exploratory study on Mutation Validation (MV), model validation method using mutated training labels for supervised learning. MV mutates training data labels, retrains the model against the mutated data, then uses the metamorphic relation that captures the consequent training performance changes to assess model fit. It does not use validation set or test set. The intuition underpinning MV is that overfitting models tend to fit noise in the training data. We explore 8 different learning algorithms, 18 datasets, and 5 types of hyperparameter tuning tasks. Our results demonstrate that MV is accurate in model selection: the model recommendation hit rate is 92% for MV and less than 60% for out-of-sample- validation. MV also provides more stable hyperparameter tuning results than tut-of-sampleevalidattoo across different runs.
INTRODUCTION
Out-of-sample validation (such as test accuracy) is arguably the most popular approach adopted by researchers and developers for empirically validating models in applied machine learning. It uses data different from the training data approximate future unseen data. However, out-of-sample validation is widely acknowledged to have limitations: 1) the sample set may be too small to represent the data distribution; 2) the accuracy can have a large variance across different runs (Pham al. 2020); 3) the samples are typically randomly selected from the collected data, and may therefore have similar bias as in the training data, leading to an inflated validation score (Piironen & Vehtari 2017; Gronau & Wagenmakers) 2019); 4) excessive reuse of a fixed set of samples can lead to overfitting even if the samples are held out and not used in the training process (Feldman et al. 2019).
The Mutation Validation (MV) approach we explore is new approach to validating machine learning models relying only upon training data, MV applies Mutation Testing and Metamorphie Testing -two software engineering techniques that validate code correctness. Mutation testing mutates the program by making synthetic changes (e.g., to change a + into a or to remove functional call), then re-executes the tests to monitor the behaviour changes and check the power of a test suite (Papadakis et al. 2019 Jia & Harman 2010). Metamorphic Testing detects program errors by checking metamorphic relations, which the relationship between input changes and output changes (Chen et al.) | SSgura et (016)) Combining these two techniques, MV mutates training data labels and retrains the model using the mutated data, then measures the training performance change. As shown by Figure [ the key intuition is that a learner, if fitting the given training data property, would be less likely be 'fooled' by a small ratio of mutated labels. Consequently, the model trained with the mutated training data would "detect" the mutated labels and still exhibit high predictive performance on the original training data. By contrast, an overfitted learner violates the Occam's 's Razor (Hawkins] 2004), and has extra capacity to fit incorrect noisy labels, and thus will yield model that exhibits poor predictive performance on the original training data, but high performance on the mutated training data. Furthermore, an over-simple learner has poor learnability, and will have low performance on the original training data and the mutated data.
There are significant number of theories proposed to explain model validation and complexity, such as Rademacher complexity and VC dimension. Nevertheless, the prescriptive and descriptive value of these theories remains debated. Zhang al. (2017) found that deep hypothesis spaces can be large enough to memorise random labels. They discussed the limitations of existing measurements in explaining the generalisation ability of large neural networks, and called for new measurements.

---

Under review as a conference paper at ICLR 2022
good leamner
over complex loamer
over simple learnor
original data
o
mutated data
Figure I: The intuition underpinning MV: A better learner less affected by the mutated labels.
In this present work, we do compare MV with these theories. Rather, similar to Zhang al. (2017). we focus on empirical investigation. In Appendix A.1 we provide the theoretical foundations underpinning the metamorphic relation that MV uses.
We report on the performance of MV on 12 open datasets and 6 synthetic datasets with different known data distributions (see Table DT. using widely-adopted classifiers (including both classic learning classifiers and deep learning classifiers). We investigate the effectiveness and stability of MV serving as a complementary measure to the existing practical model validation methods for model selection and parameter tuning. The experimental results provide evidence to support the following conclusions. First, MV captures well the degree of match between decision boundaries and data patterns in model selection. The model recommendation hit rate for MV is 92%, but is 53% for cross validation, and 55% for test accuracy. Second, MV is more responsive to changes in capacity than conventional validation methods. When cross validation (CV) accuracy and test accuracy could not distinguish among large-capacity hyperparameters, MV complements them in hyperparameter tuning. Third, MV is stable in model validation results. Its dropout rate tuning result does not change across five runs; the variance is zero. For validation set and test set, the average variance is 0.003 and 0.007, respectively. The paper also discusses the connections between MV and other noise injection work in the literature, as well as the usage scenarios of MV (Section 5
In summary, we make the following primary contributions:
1) An exploratory study on the performance of Mutation Validation. We explore the effectiveness and stability of MV to validate machine learning (ML) models as complement to the currently used empirical model validation methods. MV requires neither validation nor test sets, but uses the training performance sensitivity to the mutated training labels. We study 18 datasets, different learning algorithms, and 5 hyperparameter tuning tasks.
2) An application of software testing techniques in ML model validation. MV is the first approach that applies mutation testing and metamorphic testing- two widely studied software testing tech- niques- -on model validation tasks.
MUTATION VALIDATION
2.1 GENERAL INTUITION
Figure [illustrates the intuition that underpins MV. For 'good' learner that fits the training data well (first column of Figure M]. the leamer is less likely to be 'fooled' by a small number of mutated labels, and would keep predicting the original labels for the mutated samples. As result, the model trained on the mutated data will still have high predictive accuracy the original training data, but will have decreased predictive accuracy on the mutated data. An overfitted learner tends to noise in the training data (second column of Figure D. With mutated data, the learner will yield model that makes predictions following the incorrect labels, leading to a high training accuracy on the mutated data, but poor accuracy the original data. An over-simple leamerr has poor learnability. The model yields has poor performance with or without the mutated training data. As a result, the model trained on the mutated data has low accuracy with both the original labels and the mutated labels.
2

---

Under review as a conference paper at ICLR 2022
2.2 MUTATION VALIDATION
MV uses mutation testing and metamorphic testing, two software validation techniques, to validate ML models. Mutation testing creates mutants by injecting faults in a program, then re-executes the program to check whether a test suite detects those faults. Metamorphic relation specifies how a change in the input should result in change in the output. It is used to detect errors in software when there are no reliable oracles. For a program f. its input a and x'. Let f(x) and f(a') be the execution outputs of x and x' against f. Let R. be the relationship between r and r', R. is the relationship between fx) and f(x'). A metamorphic relation can be represented as: (2 x') + (f()),, f(x)). If the relation is violated, the program under test contains a bug. For example, when validating the sin mathematical function, one metamorphic relation that correct program should hold is sin(r + σ) = sin(x).
Now consider the scenario of ML model validation. If we treat learner the program under test, the training data as the input, the trained model's behaviours as the output, our intuition introduced in Section 2.1 can be well captured by mutation testing and metamorphic relations. In particular, the input changes are introduced by mutating training data, each mutated data instance is called a mutant; the output changes are defined in terms of performance changes of the trained models. Based on this, we propose Mutation Validation, a new machine learning model validation method that validates ML models based on the relationship between training data changes and training performance changes. good learner is expected to "detect" the mutants and have a certain amount of training performance changes according to the number of input data changes.
There are different metamorphic relations that can be explored to conduct MV, which may depend on the data mutation method, the training performance measurement (e.g., accuracy, precision, loss), and the calculation of performance changes. Let 1) be the mutation degree (i.e., the ratio of randomly mutated labels in the training data). S is the original training data, S. is the mutated training data with mutation degree 1) (π S 0.5). S(S) is the model out- put trained on S, f(r,) is the model output trained on S,, Ts(f(S)), (s() are the accuracy of S(S) and f(S,) based on the original training labels, respectively. Ts, (JS())) the accuracy of f(S,)) based on the mutated labels. In this present work, as the first ex- ploratory study on MV, we study the following MV measurement m to conduct model validation:
m (1 (1- (1)-)))((((Ss)) Ps(S(S)) Ts, (f(S,)) +n.
The above measurement, although derived from theory (Appendix A. matches well with our intuition introduced in Section 2.1 In particular, if the learner is less affected by the mutated labels, the predictive behaviours of the trained model with mutated labels should be closer to that of the model trained with the original labels. This leads to a larger (f,))) and larger difference between (S)) and Ts, (f(S)). as long as the mutation degree r is fixed. The larger m is, the better the learner fits the training data. In the optimal case, the trained model on mutated data has perfect training accuracy on the original training labels (i.e., ((S,) 1), and detects all the mutants (i.e, (f)) Ts, (S,)) = 77). Thus, m Mutation degree n) ranges between 0 and 0.5, but needs to be a fixed value. The theory inspiration of this metric, its metamorphic relation, as well as the influence of 1) on m are provided in our appendix.
EXPERIMENTAL SETUP
The main body of this paper answers four research questions:
RQI: What is the effectiveness of MV in model selection?
RQ2: What is the effectiveness of MV in hyperparameter tuning?
RQ3: What is the stability of MV in validating machine learning models?
RQ4: How does training data size affect MV?
We also explore the efficiency of MV in validating machine learning models, as well as the influence of mutation degree 7) on MV. The details are in the appendix.
To evaluate MV, we choose to use datasets that are diverse in category, size, class number, feature number, and class balance situations. Small datasets are particularly important demonstrate the
3

---

Under review as a conference paper at ICLR 2022
Donaset
abbr.
Atraining
tiest
#class
+fconure
syathelc moon
mocn
100
Ie+6
2,000
syntheli moon (0.2 notse)
moon 0.2
100
16-6
2,000
syathese -cirlle
cisele
100
1606
2,000
syathesk circle (0.2 noise)
ciccle-0.2
100
Ice6
2,000
synthuticciinoo
lincer
100
1o46
2,000
synthenic limea (0.2 notse)
linear 0.2
100
lee5
2,000
2
Idis
Irs
150
Wine
wine
178
13
Breast Cancer Wisconsin
canterr
569
Car Evaluation
1,725
Heart Divease
heart
3013
14
Bank Marketing
bank
45,211
17
Adult
adult
48,842
16.281
14
Connect-4
67.557
MNIST
60.000
10,000
MNIST
fadiion
600800
10,000
CIFAR-10
cifari0
50,000
CIFAR
cidar100
50,000
10,000
Table 1: Details of the datasets.
ability of MV in providing warnings for over-complex learners. Table shows the details of each dataset used to evaluate MV. Column "#training" and Column "#test" show the size of training data and test data, which is presented by the dataset providers. Column "#class" shows the number of classes (or labels) for each dataset. Column "#feature" presents the number of features.
To obtain datasets with known ground-truth decision boundaries for validating model fitting, synthetic datasets with three types of data distributions: moon, circle, and linearly-separaad three data distributions are provided by scikit-learn (Pedregosa et al., 2011) tutorial demonstrate the decision boundaries of different classifiers. To study the influence of original noise in training data on MV, for each type of distribution, we create datasets with noise. We also generate different-size training data ranging from 100 to 1 million data points to study the influence of training data size. These synthetic datasets help check whether MV identifies the right model whose decision boundary matches the data distribution, with and without noise in the original dataset S. We do not expect such synthetic datasets to reflect real-world data, but the degree of control and interpretability they offer allows us to verify the behaviour of MV with a known ground-truth for model selection.
These
We also report results on 12 real-world widely-adopted datasets with different sizes, numbers of features and classes. Eight of them are from the UCI repository (Asuncion & Newman 2007). the remaining four are the most widely used image datasets: MNIST, fashionMNIST, CIFAR-IO, and CIFAR-100 For each dataset, is, under each class of the dataset, we randomly select 20% of the labels to mutate. This guarantees that MV is not affected by the problem of class imbalance. We mutate the labels by label swapping: to replace a label with the next label in the label list, the final label in the label list is replaced with the first label in the label list. For the synthetic datasets and the 8 UCI datasets, we compare with 3-fold CV accuracy and test accuracy. We use 3-fold CV because it has almost identical results to more folds cross validation, but has lower cost, thereby being more conservative to compare with when studying the efficiency of MV. For the three image datasets on deep learning models, we compare with validation accuracy with 20% validation data (split out from the training data) and test accuracy. The next section introduces more configuration details.
calculate MV with 0.2 to answer the research questions. That
RESULTS
4.1
RQI: EFFECTIVENESS OF MV IN MODEL SELECTION
To answer RQL, we use synthetic datasets to explore whether MV recommends the learners whose decision boundaries best match the data patterns. We use synthetic datasets because synthetic datasets have ground-truth data patterns for model selection (more details in Section The data distribution of real-world UCI datasets, however, is often unknown difficult to visualise. To generate synthetic datasets, we use three scikit-learn (Pedregosa et al. 2011) synthetic dataset distributions, which designed as tutorial to illustrate the nature of decision boundaries of different classifiers. This experiment uses the same settings as in the Scikit-learn tutorial (Classifier Comparison 2019). Each dataset has 100 training data points for model selection. We generate another 2,000 points as test sets.
Figure 2 shows the training data points, decision boundaries of each classifier, and measurement values from MV, CV, and test accuracy (on the 2,000 test data points). We have the following
4

---

Under review as a conference paper at ICLR 2022
zero noise
Linear SVM
RBF SVM
Gaussian Process
Decision Tree
Random Forest
AdaBcest
Naive Bayes
MV=0.89 CV-0.88 065
MV=1.00 CV=1.00 Test 00
MV=1.00 CV=0,99 Test=1.00
MV-0.74 CV-0,96
MV=0.69 CV=0,96
MV=0.75 CV-0.95
MV=0.89 CV=0,88 Test=0.B8 89
Test 99
Test 98
Test 98
MV-0.53.
MV=1.00.
MV-0.88.
MV-0.69.
MV-0..1.
MV=00.22
MV-
C4=0.54 33
CV=1.00 1est=1.00
CV=1.00 Test=1.00
CV=100 Test=
CV=0,99 Test=1.ba
CV=1 1000 Test=id399
CV=1.00 Test
MV-0.59 .339 0222 Testt 0.
MV 88
MV=0.91
MV-0.6
MV- 0.66
MV-0.77
MV-0
CV=
CV=0,93 3
CV=0, 9.0
CV=0,91
CV= Test=0.39
CV=0,93 03.3
Tast= 90
0:90
Test sa
Tast= 0.59
Test 90
Bayes
MV=0,86 CV 185
MV=0,70
MV=0,76
CV20.97
Cved.95
CV-0.91
CV=0.88
CV=0.89
Dest=D:96
Test=0:94
Test=:094
Test=0:36
MV=0.55
MV-
MV-0.77
MV-
MV-0.71
MV-0
CV-B.sá
CV-0.90
CV-9.91 Test-037
CV-0.88
CV-0.90
d-
CV-8.91
Test
a6
Test=0:82
T
Test
Test
MV-0 82 CV-0,61 Testa0 a2
MV-0 77
MV-0 86
MV-0 69
66 CV-0,79 Test=0
MV-0 74
MV-0
CV-0,60 Test=0
CV=0,85 Test=
C/-0,74
CV- 0,77
CV-0,81
Test=0 76
Test=0 26.
Test=0 01
Figure 2: Performance of MV in model selection. MV, CV, Test denote MV score, CV accuracy, and Test Accuracy. Red and blue points are the original training data without noise (top-three rows) and with 0.2 noise (bottom-three rows). Areas with different colours show the decision boundaries. We observe that MV captures well the match between decision boundaries and data patterns.
First, MV tends to have large values for cases where the decision boundaries match well the data patterns; provides more discriminating scores for model selection under different datasets, it is easy to pick out the top-2 models that match the data distributions the best based on MV. Second, the recommended models from MV are less affected by the noise in the training data.
observations.
The figure also shows cases where CV and test accuracy have limitations evaluating ML models. For example, in Figure 2 for the circle distribution, Decision Trees and Random Forests (with maximum depth of 10) give obviously ill- fitted rectangle-shaped decision boundaries, yet the cross validation accuracy and test accuracy remain high. In addition, from Ta it is more difficult to select proper models based on CV and test accuracy. because CV and test accuracy are often very similar across different models.
Recorimended sindls top
MV
0.2
RBF SVM, Gamssan Proess
00
KIB NYM, Gamedan Process
SVM, Gaussaa
RBF SVM, Ganesian
0.2
RBF SVM, Gamasaa Prizaa AdaBaos
0.0
RBF SYM, Náive Bases
SVM, Naww Bayas
circle
CV
0.2
RBB SVM, Grescun
Gaesilan Proxsss Naive Bayes
DT, Ri: Adalions, Naive
00
RBI SYM, Garssin Proces, DT. RE, Naire Bayes
SVM, Gauscin
Naive
0.2
Gasncin PrazDs,, Naisa Royex
liscer
CV
00
RBF SVM, Gussiaa Process Naive Bayes
Garacan Provess Naive llaye
For ease of observation, we present Table to show the models recommended by MV, CV. and test accuracy, based on their top-2 scores shown by Figure 2 The ground-truth models in bold based manual observation and widely- adopted ML knowledge. For example, Scikit- learn documentation (Classifier Comparison,
Läteer SVM, RBF SBFSVM, Grassion Process, Naive
0.2
Liaue SYM, Gassizan Prozes, Naise Bages
Table 2: Recommended models by MV, CV, and test accuracy. The models in bold are the ground- truth ones whose decision boundaries match the data patterns. The recommendation hit rate is 92% for MV, 53% for CV, 55% for test accuracy.
5

---

Under review as a conference paper at ICLR 2022
2019) mentions that Naive Bayes and Linear SVM more suitable for linearly-separable data. Overall, we have the following conclusion: among all the model selection tasks we explored, the hit rate (i.e., the ratio of recommended models that match the ground truth model) is 92% for MV, 53% for CV accuracy, and 55% for test accuracy.
4.2 RQ2: EFFECTIVENESS OF MV IN HYPERPARAMETER CONFIGURATION
For models whose capacity increases along with their hyperparameters, we expect their goodness of model fit to first increase, then peak, before decreasing. The peak indicates the best model fit assessed according to MV. In RQ2, we assess whether MV matches this pattern. We study five capacity hyperparameters for several widely-adoptee algorithms: the maximum depth for Decision Tree, C and gamma for a Support Vector Machine (SVM), and the dropout rate and learning rate for Convolutional Neural Networks (CNNs).
Maximum Depth for Decision Tree. Figure 3 shows how MV responds to increases in maximum depth of Decision Tree for the eight real-world UCI datasets. For small datasets (smaller than 2,000), we do not split out test data, but take the whole data as training data. For the bank and connect datasets,
80% of the data as test sets. For adult, we use its original test set. We repeat the experiments 10 times. The yellow shadow in the figure indicates the variance across the 10 runs.
cencer
1.0
1.0
1.0
1.0
1.0
1.0
10
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
25
Figure 3: Changes in MV, CV accuracy, and test accuracy when increasing the maximum depth for Decision Trees. The x-axis ticks for car and connect differ to capture MV's inflection point. We can observe that, while CV and test accuracy agree with MV on the key influence point in most cases, they are less responsive to large depths (which lead to overfitting)
From Figure 3 we make the following observations. First, for 6 out of the 8 datasets, MV increases then decreases as maximum depth increases, and exhibits maximum in each curve. This is consistent with the pattern we expect good measure to exhibit. For small datasets, large depths yield low MV scores, whereas large datasets do not. For adult and bank, MV values remain large when the maximum depth increases. We suspect that this is because, for these two datasets, the training data size is large enough for the model to obtain resilience against mutated labels. We explore the influence of training data size in the appendix.
We also observe that MV, CV and test accuracy have similar inflection points, yet MV is more responsive to depth changes, especially when the model overfits due to large depths. This observation indicates that MV provides further information to help tune maximum depth when CV and test accuracy are less able to distinguish multiple parameters. In particular, if a developer uses grid search to select the best maximum-depth ranged between 5 and 10, we find that grid search suggests depths of 8, 6, 9 in three runs for the cancer dataset, which are over-complex and unstable. Similar results are observed for other small datasets. With MV, its decrease trend in this range indicates that there is a simpler model with comparable predictive accuracy but better resilience to label mutation.
C and gamma for SVM. In SVM, the gamma parameter defines how far the influence of a single training example reaches; the C parameter decides the size of the decision boundary margin, behaving as a regularisation parameter.
a heat map of MV scores as function of C and gamma, the expectation is that good models should be found close to the diagonal of C and gamma (Scikit) Iearn:SVM 2020). Figure f presents the heat map for cross validation and MV for two datasets. We do not use hold out test set to ensure sufficient training data. The upper left triangle in each sub-figure denotes small complexity; the bottom right triangle in each sub-figure denotes large complexity. In both cases, MV gives low scores.
When comparing CV and MV, MV is more responsive to hyperparameter value changes. With MV scores, it is more obvious that good models can be found along the diagonal of C and gamma. When and gamma are both large, the CV score is high but MV score is low, this is an indication that there exists simpler model with similar test accuracy. In practice, stated by Scikit-lear documentation,

---

Under review as a conference paper at ICLR 2022
CV
CV
MV
0.0
64
03
38
wine
07
97
05
655
Led
348
16:09
1000
1000
Figure 4: Influence of SVM parameters on CV and MV. The horizontal/vertical axis gamma/C. Good models expected to be found close the diagonal. As can be seen, CV has broad high- valued (bright) region, while MV's high-valued region (bright) narrower, showing that MV is more responsive parameter changes.
it is interesting to simplify the decision function with lower value of C so as to favour models that use less memory and that are faster to predict SScikit-learnSSV 2020).
Dropout Rate and Learning Rate for CNN. We use CNN models coming from Keras documentation. Validation accuracy is calculated with 80% training data and 20% validation data. Figure shows the results. We observe that when tuning dropout rate for mnist and fashion-mnist, validation and test accuracy are less discriminating and provide different tuning results across different runs (more details in Table 4), yet MV is more discriminating. For dropout rate, MV and test accuracy have different key influence points on cifar 10 (0.4 v.s. 0.2). This is because there is a big capacity jump between 0.2 and 0.4. The result suggests that the optimal dropout rate with comparable validation/test accuracy is between 0.2 and 0.4.
1.00
Tash mest
ctar10
1.0
clar100
1.5
0.8
0.8
0.55
0.0
0.6
0.4
0.2
0.2 0.2 0.6 dropout rote
5.0 O8 0.3 drppнu 1ite
0.0 02 dropoutrgg rate
98 0.5
5.0
62 08
0.6
9.0
0.0 lesming rate
rappoutrste
leaniing rite
Teariing rate
learning rote
Figure 5: Influence of CNN's dropout rate and learning rate MV and validation/test accuracy.
Overall, we observe that MV is responsive to hyperparameter changes on all the hyperparameter tuning tasks we explored. CV and test accuracy are less responsive especially for large-capacity hyperparameters (i.e., large maximum depth for Decision Tree and small dropout rate for CNNs). This leads to the following issues. First, due the large variance of their results across different runs, such low response often leads to unstable hyperparameter recommendation results. We further explore this in Section 4.33 Second, developers may easily choose an over-complex learner, making the learner: 1) easily biased by incorrect training labels; 2) vulnerable to training data attack; 3) computationally and memory intensive; 4) more difficult to interpret.
4.3 RQ3: STABILITY OF MV IN MODEL VALIDATION
For the machine learning experimental design in the literature, data is usually random split. The values of MV, CV, and test accuracy may be easily affected by the randomness in model building (Pham et al. 2020 especially when the overall data set is small, or building deep learning models. As result, with different runs, developers may get completely different recommendations for the best hyperparameter configuration. A good model validation method is expected to be stable in hyperparameter recommendation results, giving developers clear instructions on the best choice.
To explore the stability of MV, CV, and test accuracy, we run the model building process multiple times, each time with a different split training data and validation data (the size of training/validation data is unchanged). We then record the recommended best hyprrparameters during each run under the scenario of hyperparameter configuration. We use the maximum depth for Decision Tree with the 5 small UCI datasets well as the dropout rate for CNN with the image datasets. Table shows the results, which lead to the following conclusion: MV has good stability in recommending hyperparameters. When recommending maximum depth for Decision Tree, the overall variance is
7

---

Under review as a conference paper at ICLR 2022
Method
Reoommended maximamm depth
Variance
Datasct
Method
Recommended dropout rase
Variance
iis
CV
MV
1, 3, 3, 8,888
[3.3 3,3,3,2,,,, 2, 3,
MV
Val.
10.2. 0.2 0.2. 0.2.
10.0.
0.0,
0.2,
0.202.222
0.21
0.000
MV
3.3.2.3.233,44
Test
[0.2. 0.0. D.0,
0.2,
0.0
0.0.
0.0, 0.0 0.2, 0.0]
0.009
CV
134. 2.4,7,83333.4
MV
10.2. 02,
0.2
0.2.
0.2.
0.2,
0.2
0.000
MV
33..3322.3.3,
Vali.
[0.2.
0.2,
cancer
CV
4. 7, 4, 6] 4,,7,3,4,4,4.
Rest
[0.2. 0.0.
0.2,
0.0,
0.0,
O.D.
0.0,
0.2 0.2, 0.0]
0.011
MV
7.
7.
MV
[0.4.
0.4,
0.4,
0.000
CV
cifar10
Vali.
[0.2, 0.2,
0.2.
0.2.
0.2
0.2,
0.2]
0.000
15.6.
Test
10.2. 0.2,
0.2.
0.2 0.2.
0.2. 0.2, 0.2,
0.2, 0.21
0.000
heart
CV
14,4,3,
3,3,3,
MV
0.000
MY
0.200
mecn
Vali.
0.003
4,000
Test
0.007
Table 4: Recommended hyperparameter' across different runs. The third column shows the specific recommended hyperparameters (we run the datasets 10 times); the last column shows the variance (the average of the squared differences from the Mean) across different runs. MV is more stable than CV and test accuracy in recommending hyperparameters.
0.200 for MV. but 4.000 for CV accuracy; when recommending dropout rate for CNN, the overall variance is 0.000 for MV, 0.003 for validation accuracy, and 0.007 for test accuracy.
4.4 RQ4: INFLUENCE OF TRAINING DATA SIZE ON MV
We expect that when a learner is over-complex for the data, adding extra data will improve the learner's 's resilience mutated labels, thus the MV score ought also to increase when training data size increases. Indeed, previously from Fig- 3 we have observed that models trained on large datasets (e.g., bank and adult) tend to be more resilient to mutated labels for large depths. Figure the results for connect and moon datasets, indicating that data size plays role in determining the trained model's 's robustness to incorrect training labels.
0.80
connect
1.00
moon
0.75
0.75
1000
2 0.50
0.65
5000
7000
0.25
9000
500
0.55
0.00
18
Figure 6: Influence of training data size on MV when increasing maximum depths (horizontal axis) of Decision Trees. For given depth, larger datasets tend to yield larger MV values.
These observations indicate another possible value in the use of MV, as complement to CV and test accuracy. Specifically, where MV low, ML engineers have two potential actions to improve the fitting between the learner and the training data: either to optimise the learner (e.g.. search for smaller-capacii models with comparable test accuracy). or to optimise the data (e.g.. increase data size to increase the learner's resilience to incorrect training labels).
DISCUSSION
5.1 CONNECTION WITH RELATED WORK
MV is also connected with several key concepts the literature. This section discusses the connections as well as the differences between MV and these concepts.
Noise injection in training data has long been recognised an approach to complex training data and reduce overfitting (Holmstrom et al. 1992. Greff et al. 2016). There are three main differences between MV and this random noise injection. noise (Greff et al., 20166), and is added into the training inputs (not labels); on the contrary, MV does not use random noise, but uses label swapping. the mutation is applied only on labels. 2) Conventional noise injection changes the training data, then directly uses the model trained on this noisy training data. MV keeps the original training data, but creates another mutated training data to for measurement calculation. This mutated training data will not be used to yield any model for real prediction tasks. 3) Conventional noise injection aims to improve the complexity the training data, to reduce overfitting. MV aims to calculate model validation measurement score, measure
Overfitting prevention noise often Gaussian
8

---

Under review as a conference paper at ICLR 2022
the goodness of model fitting. Zhang et al. (0017) adds noise in training data labels to study the generalisation of DNN, while MV mutates labels to provide model validation measurement.
Noise injection in test data is adopted to evaluate the robustness of model. For example, the generation of adversarial examples (Goodfellow et al., 2014) uses noise injection in the test inputs. Compared this technique, MV 1) mutates training data, not test data; 2) mutates labels, not features; 3) aims to validate model fitting, rather than model robustness to feature perturbations.
Overfitting prevention refers the techniques adopted in the training process to avoid overfitting, especially when training deep neural networks. The key techniques are regularisation, early stopping, ensembling, dropout, and techniques, such as CV or validation accuracy, are often less responsive to overfitting, In practice, developers often conduct the prevention without knowing whether the overfitting happens or not. MV is demonstrated to be discriminating and stable in detecting over-complex learners. It thus provides signals for the adoption and configuration of these overfitting prevention techniques.
However, shown in this paper, conventional overfitting detection
Rademacher complexity. In statistical machine learning. Rademacher complexity has been used to measure the complexity of learner's 's hypothesis space. also mutates training data. It measures how well the learner correlates with randomly generated labels on the training data, but can be difficult to compute (Rosenberg & Bartleti, 2007). Different from Rademacher complexity, MV is an applied tool, not theoretical tool. MV uses label mutations for part of the data. Furthermore, Rademacher complexity cares only about the training accuracy on the mutated data, but MV uses the accuracy changes the original and the mutated data.
5.2 THE USAGE OF MV IN PRACTICE
With our exploratory study, we find that MV is capable of complementing existing model validation techniques. There are two main application scenarios of MV: 1) When out-of-sample validation results are similar or unstable across different models or hyperparameters, MV can help to guide the selection process (see more Section 4.2 and and Section 4.3). 2) When the training data size is limited, MV is a better option than validation accuracy because does not need to split out a validation set, thus reserving more data for training.
The test accuracy, although having limitations shown in the literature and our experiments, is still very important method for developers to learn the generalisation ability of a model, especially when there is data distribution shift between the training data and unseen data. However, as shown in this paper, when test accuracy is high but MV is low, this means that there is a learner with comparable test accuracy, but is simpler.
MV deserves more attention from developers when simplicity, security (e.g.. defending training data attack), and interpretibility of the built models are required. Theoretically, MV can be applied in other MI. tasks which rely on out-of-sample validation, such as feature selection. We will explore the effectiveness of MV in these tasks future work.
CONCLUSION
We introduced an exploratory study on MV, new approach assessing how good learner fits the given training data. MV validates via checking the learner's sensitivity to training labels changes (expressed as label mutants). The sensitivity is captured by metamorphic relations. We show that MV is more effective and stable than the currently adopted CV, validation accuracy, and test accuracy. It also responsive to model capacity and training data characteristics. These results provide evidence that MV complements the existing model validation practises. We hope the present paper will serve as starting point to future contributions.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
Tsong Y Chen, Shing C Cheung, and Shiu Ming Yiu. Metamorphic testing: new approach for generating next test cases. arXiv preprint arXiv:2002.125433 2020.
Classifier Comparison. Classifier Comparison, 2019. URL https://ssskk-ccmmmoookaaabluuub
Saamplesclastficaiionnppoo classliiitassseierreeeee classiterr_ommpaiison comparison.html
Vitaly Feldman, Roy Frostig, and Moritz Hardt. The advantages of multiple classes for reducing overfitting from test set reuse. In International Conference on Machine Learning, pp. 1892-1900. PMLR, 2019.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Klaus Greff, Rupesh K Srivastava, Jan Koutník, Bas R Steunebrink, and Jürgen Schmidluber. Lstm: A search space odyssey. IEEE transactions on neural networks and learning systems, 28(10); 2222-2232, 2016.
Quentin F Gronau and Eric-Jan Wagenmakers. Limitations of bayesian leave-one-out cross-validation for model selection. Computational brain behavior, 2(1):1-11, 2019.
Douglas M Hawkins. The problem of overfitting. Journal of chemical information and computer sciences, 44(1):1-12, 2004.
Lasse Holmstrom, Petri Koistinen, et al. Using additive noise in back pock-propagttion training. IEEE Iransactions on neural networks, 3(1):24-38, 1992.
Yue Jia and Mark Harman. An analysis and survey of the development of mutation testing. IEEE Iransactions on software engineering, 37(5):649-677 6789 2010.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning.
MIT press, 2018. Second edition.
Mike Papadakis, Marinos Kintis, Jie Zhang, Yue Jia, Yves Le Traon, and Mark Harman. Mutation testing advances: analysis and survey. In Advances in Computers, volume 112, pp. 275-378. Elsevier, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
Hung Viet Pham, Shangshu Qian, Jiannan Wang. Thibaud Lutellier, Jonathan Rosenthal, Lin Tan, Yaoliang Yu, and Nachiappan Nagappan. Problems and opportunities in training deep learning software systems: An analysis of variance. In 2020 35th IEFF/ACM International Conference on Automated Software Engineering (ASE), pp. 771-783. IEEE, 2020.
Juho Pürroen and Aki Vehtari. Comparison of bayesian predictive methods for model selection.
Statistics and Computing, 27(3):111-735, 2017.
David S Rosenberg and Peter L Bartlett. The rademacher complexity of co-regularized kernel classes.
In Artificial Intelligence and Statistics, pp. 303-394433,22 2007.
Scikit-leam:SSVM RBF SVM parameters. https:/ssski-llammmrggtttabbleee http////ccoocccccmmmm///////aaoa rbf .amaaa 2020.
Sergio Segura, Gordon Fraser, Ana B Sanchez, and Antonio Ruiz-Cortés. A survey on metamorphic testing. IEEE Transactions on software engineering, 42(9):805-824, 2016.
10

---

Under review as a conference paper at ICLR 2022
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Representations (ICLR), 2017.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 THEORETICAL INSPIRATION
This part introduces the theory that leads metamorphic relation and formula that for conducting MV. The denotations and terms we used are guided by the standard statistical machine learning literature (Mohri al. 2018 Ghosh al. 2017
Theoretical Metamorphic Relation for Model Validation:
Let X' be the feature space from which the data are drawn. Let y [k] (1....,A .b) the class labels. Given training set S = {xx1, 3/xi ...,, (Xm: Ixm }} (X x y) which is independently and identically distributed according to some fixed, but unknown, distribution D of X V. Let classifier be f X'' C,C C R*
loss function is a map L: xx - RR+, We use to denote expectation. Given any loss function L and classifier f, we define the L-risk of by
R2(f) Ex|L(f(x), Mx)1 = Ex,ux [L(f(x),
(2)
Let {(x, {x)] be the mutated data, where
Ux - {
yxx, with probability (1 - 77x)
jE [k] Ws. with probability 7x,
For all x, conditioned ys i, we have Ejti 7xj "/x- The noise is called symmetric uniform if the 17. For uniform or symmetric noise, also have Tx, ~ We consider symmetric loss function T. that satisfies the following equation, where C is constant.
Σ -
Let S., = ((x,, Ix.,), = I,.... m} be the mutated training data. We call v as a mutation degree. Let f be the model trained on S. fn be the model trained on S: ff and fn are from the same learner (with identical hypothesis space). Let r(x)= (x), (xx L(f(x), Mx))/n / be the loss change
rate between f and fn. x E X. For uniform noise, we have:
[(f,(x)) 0x) L(f(x).
Ex|r(x)] Ep
(4)
(1 - ())((()) B&) + 2I Enpr. ((F(())) - L(F()). 8k)
Ep
(5)
Ep
1 (.) 111000)) + 1: k-
Σ ((C(())))
(6)
(r,) 1R(( C- B((5)
k-1
(R((()) 1 -R k-1 77 lo
(8)
k
C
(e((a))
+
(9)
11
1
If we consider L to be error rate C = 1. Now consider the situation for multi-class classification problems, we mutate the labels by label swapping: to mutate the labels by replacing them with the
If is same as f(S in Equation Thhe loss function T. does not have be emror rate (0-1 loss). Any loss function that satisfies Equation 3 can he applicd. In the present work, use enror rate (also accuracy) considering its popularity.
12

---

Under review as a conference paper at ICLR 2022
next label in the label list, the final label in the label list is replaced with the first label in the label list. In this way, we have ?xx.) = 1). Thus, Equation 9 becomes:
Eo[r(x)] = - --)2 1 -R((f)+1 +1
+1.
(10)
Thus, we have:
(f. = (122n) - -n]Do/(xx]] +
(11)
Let T(J) be the accuracy of / over distribution T() 1- (()) Rr) Let
T()) be the empirical accuracy of on training data with size nr: T()) = 4 {(x)) where
1o is the indicator function of event wc We have:
T( = (1 101--2)12 (n) + nBx[r(x)] + n.
(12)
Empirical Model Validation Measurement
Equation 12 specifies theoretical metamorphic relation: Mutation degree 1 defines the relationship between inputs 5 and S,, under each class of S. 1) proportion of the labels are mutated with label swapping (see more in Section A.ID, yielding S, Such input changes lead to the expected output changes reflected by T(f). T(,),, and loss change rate r(z) in the equation.
The calculation of such a theoretical metamorphic relation, however, is impractical, because data distribution is unknown, the expectation calculation is also unrealistic. Inspired by Equation [2] also considering that motivation is to empirically measure how good learner fits the available training data, we change the expectations on data distribution D into empirical observations on the available training data. This leads to the following measurement,
empirically access learner"
m = - (s)) + Tÿ +
(13)
(1 (1-2))(((n)) 1 Ts(f) (fn) 1 1
(14)
(1 - (1-2n) + fs(() - (fn) +
(15)
In Equation 15 S is the original training data, S, is the mutated training data with mutation degree (n S 0. f the model trained on the original training data, fn is the model trained on the mutated data, (s)),, (fn) are the accuracy of f and fa based on the original training labels, respectively. Ts., (fr) is the accuracy of f, based on the mutated training labels.
Connection between m and Our Intuition:
particular, the learner is less affected by the mutated labels, the predictive behaviours of the trained model with mutated labels should be closer to that of the model trained with the original labels. This leads to a larger (f,) and f, as long as the mutation degree is fixed. The matching between m and our intuition provides extra supports for the reliability of MV in validating machine learning models.
Interestingly, Equation 15 matches well with our intuition introduced in Section 2.1
The calculation of m can also be regarded as type of mutation score Jia & Harman (2010): Papadakis al. (201)) for model validation. As explained in Section 2. we expect that a good learner kills more mutants. However, the intuitionistic mutation score (i.c., the proportion of killed mutants) has a limitation in model validation: poor learner that makes random guesses may also kill many mutants.
The purpose of m is not to approximate T(f), but to measure how gond a learner fits the available training data. However, if the training data is sufficiently large, m is expected to he close to T(f).
13

---

Under review as a conference paper at ICLR 2022
Equation 15 covers the mutant killing results (i.e., by calculating accuracy decrease rate r), but also fixes this limitation by also considering the accuracy on the original correct labels (i.e, Ts,f,)). Thus, it can be regarded as mutation score calculation adapted to suit the model validation scenario.
The larger a learner's 's m is, the better the learner fits the training data. Thus, we adapt the concept of metamorphic relation in the scenario of model validation and extend it to a qualitative measurement, rather than a simple binary judgement. However, the value of m can also reflect the metamorphic relation we introduced in Section [.2] let us define that once learner's 's m is below threshold (e.g., 0.8), the metamorphic relation violated. The violation then indicates a fault in model fitring: the learner is either over-complex (with a large (f)) or over-simple (with a small (f()) for the training data.
A.2 INFLUENCE OF MUTATION DEGREE
From Equation 13| it can be seen that the calculation of MV involves a mutation degree, 7/. for generating the mutated training data. The value of needs to be fixed during the calculation. However, Equation [5] is reliable the influence of r on model validation should be minor. This section empirically explores whether this is true.
The first sub- figuuigure in Figure 7 shows the results for UCI datasets. The second sub-figure shows the results for the three large image datasets. It reveals that for most datasets (except for the three smallest datasets, i.e., iris, wine, and heart), the values of MV remain almost identical with different mutation degrees. This is because there is the constant term 1) the end of Equation [5 when calculating MV, which cancels out the decrease of the detected mutants. This observation provides further evidence for the reliability of our calculation formula shown in Equation [5
For the three very small datasets, i.c., iris, wine, and heart, with fewer than 300 data points, we observe that larger noise degree leads to smaller MV. This may be because label mutations have more influence on very small datasets. Nevertheless, with different mutation degrees, we observe that the effectiveness MV in model selection and hyperparameter configuration do not change, because the relative rankings of models/hyperpprameterr remain unchanged. For example, as shown by the third sub-figure in Figure even for the smallest dataset iris, the recommended maximum depths for Decision Tree are identical.
The same as the choice of n in n-fold cross-validation, although we demonstrate that the choice of 7) doest not affect model validation conclusions, there may be best practice for selecting n under different application scenarios. We call for future work and practices to explore this.
iris
1.0
1.0
1.0
0.5
0.5
0.5
0:0.1
0:0.2
heart
wine
wdult
0:0.3
Cance
bant
meist
cifer10
9:0.4
0.0
connect
0.0
fedhion
0.0
n:0.5
0.5
0.2
5
7
mutation degree
mutation degree n
maximum depth
Influence of mutation degree 7 on MV. The results show that different 17 lead to similar MV values and identical model validation conclusions.
Figure 7:
A.3 INFLUENCE OF TRAINING DATA SIZE ON MV
In addition to RQ4, we further investigate what would happen to MV should we deliberately use training data much more than normally expected. That is, we go beyond the assumption that there is no need to increase data when the test accuracy becomes stable. As can see from Figure g MV is more responsive to changes in training data size than test accuracy. For learners that are over-comples to the data, when adding more training data longer increases test accuracy, MV continues to
increase, indicating that the model's 's resilience to incorrect labels continues to increase. The extra training data improve the robustness of the learner training label noise. The pattern that MV no
14

---

Under review as a conference paper at ICLR 2022
longer changes when model complexity increases is also signal developers that the training data is perhaps larger than necessary.
moon
linea
moon
linear
1.0
Test accuracy
PV sescrre
0.5
0.5
0.5
0.5
1000
100000
100000
0.0
0.6
0.0
0.0
0.0
0.0
7
11
15
19
3
31
15
19
11
15
39
11
15
19
3
31
15
19
7
11
15
Figure 8: MV (first row) and test accuracy (second row) on training data of increasing size with different maximum depths (horizontal axis). MV is responsive data size changes; 2) MV no longer decreases for large depths when the training data size is sufficiently large.
A.4 EFFICIENCY OF MV MODEL VALIDATION
In this part, we compare the efficiency of MV, CV (3-fold), and validation accuracy (for image datasets), using the synthetic datasets on classifiers (with the same setup in RQ1), the 8 UCI datasets on Decision Tree (with fixed maximum depth of 5), and the image datasets (with fixed dropout rate of 0.5, and learning rate of 0.0001). The deep learning experiments with the three image datasets were run on Tesla V100, with 16GB Memory and 61GB RAM.
Table 5 shows the results. For brevity, we show only the results for the moon synthetic datasets. Overall, both MV, CV, and validation accuracy have good efficiency on these datasets. Note that in practice developers often use 5-fold or 10-fold CV, which have larger time cost than the 3-fold CV.
The cost of MV mainly comes from data mutation and model training, As observed from Table 5 larger datasets take more time to get MV values. Our results demonstrate that the cost of MV is manageable and comparable to 3-fold CV and validation accuracy both classic learning and deep learning. In particular, for the three large image datasets, MV costs only half the time of 3-fold CV.
What more, as demonstrated by RQI and RQ2, the effectiveness and stability of MV help to conduct model selection and hyperparameter configuration more quickly. Thus, it helps to save cost in selecting the best learners for a given training set. On the other hand, MV sensitive to over-complex models, and can help to select the simplest model with reasonable test accuracy. This will also reduce the model training and maintainability cost in the long run.
Overall, MV has comparable efficiency to 3-fold CV and validation accuracy. For the three deep learning tasks, MV's efficiency doubles that of 3-fold CV.
Dataset
Learner
MV-time
CV-time
Dataset
Learner
MV-time
CV-time
moon
Linear SVM
0.002s
0.003s
iris
Decision Tree
0.021s
0.003s
RBF SVM
0.003s
0.004s
wine
Decision Tree
0.004s
0.007s
moon
Gaussian Process
0.161s
0.157s
cancer
Decision Tree
0.023s
0.017s
Decision Tree
0.001s
0.002s
car
Decision Tree
0.011s
0.014s
moon
Random Forest
0.046s
0.064s
beart
Decision Tree
0.004s
0.008s
moon
AdaBoost
0.1248
0.185s
adult
Decision Tree
0,386s
0,385s
Naive Bayes
0.002s
0.003s
bank
Decision Tree
0.118s
0.109s
connect
Decision Tree
0.195
0. 196s
0.048s
0.060s
0.095s
0.092s
Dataset
Learner
epoch
MV-time
CV-tme
Validation-time
mnist
convolutional neural network convolutional neural network
2.772min
5.296min
1.761min
fashion mnist
10
2,803min
5.352min
1.778min
cifar10
convolutional neural network
12,052min
24.315min
8.072min
mean
5.876min
11.654min
3.870min
Table 5: Efficiency of MV, CV, and validation accuracy. The top/bottom sub-table shows the results for classic/deep learning. We observe that the efficiency of MV is comparable to that of 3-fold CV and validation accuracy.
15

---

Under review as a conference paper at ICLR 2022
A.5 MODEL SELECTION WITH UCI DATASETS (RQ1)
In this part, as an extension to RQI, we present the results of model selection using UCI datasets. Note that do not test accuracy the ground truth for model selection considering the possible limitations of test accuracy we discussed in the introduction. Instead, we present the results to demonstrate how MV differs from CV and test accuracy, as well as how it complements CV and test accuracy in model selection when developers observe similar accuracy results across different learners.
Figure 9 shows the results. It is interesting that we do have observations on MV that are consistent with common machine learning knowledge. In particular, for the four smallest dataset (i.e., iris, wine, cancer, and heart), MV suggest the two simplest learners (i.e., Linear SVM and Naive Bayes).
iris
wine
cancer
car
Linear SVM
RBF SVM
Decision Tree
Random Forest:
AdaBoost
Naive Bayes
Linear SVM
RBF SVM
Decision Tree-
Random Forest
AdaBoost
Naive Bayes
Linear SVM
RBF SVM
Tree
Random Forest
AdaBoost
Naive Bayes
Linear SVM
RBF SVM
Decision Tree
Random Forest
AdaBoost
Naive Bayes
heart
adult
bank
connect
Linear SVM
RBF SVM
Decision Tree
Random Forest:
AdaBoost:
Naive Bayes
RBF SVM
Decision Tree
Random Forest-
AdaBoost
Naive Bayes
Linear SVM
RBF SVM
Random Forest
AdaBoost
Naive Bayes
Linear SVM
RBF SVM
Decision Tree
Random Forest
AdaBoost
Naive Bayes
Dectsion
Figure 9: Model selection results with UCI datasets (extended analysis for RQ1).
16

---

Under review as a conference paper at ICLR 2022
A.6 MODEL SELECTION WITH RANDOM LABEL REPLACEMENT
In the main body of this work, we present empirical results with MV calculated using label swapping. In this part, further explore the effectiveness of another label mutation approach: random label replacement. That is, when conducting label mutation, we replace the original label with a label that randomly chosen from the label list. We compare the performance of these two label mutation approaches in model selection with the ground truth provided by synthetic datasets. Figure 12 shows the results. We observe that random label replacement less accurate than label swapping in model selection, but is still more accurate than CV and test accuracy.
zero noise
Linear SVM
RBF SVM
Gaussian Process
Decision Tree
Random Forest
Boost
Naive Bayes
MV SL
MV SL-1
L.00 MV-RL
MV-04 MV-RL-0.17
MV-SL 0.75 MV-RL-0.77
MY MV-SL=0.75
MV 0.88 NV-RL-0.7
MV-RL20.80
MV-RL-0
MV S150 MV-RL-0.51
MV-SI-1.0
MV-SL-O.88
0V677-0.67
WVVSL_D,.E
My 52.0,72
MV
MV-RL-0.87
MV-RL=0.91
0.73
MV-RL-0.78
MV-RL-0 74
MV-RL-0.93
MV-SL-D 93
MV-S - 0.88
MV-SL 0.91
MV-SL - 0.68
MV-SL 0.67
MV-SI 0
MV-SL- 94 MV MV-RL=0.88
0V-RL=0.79
8V
MV-RL=088
MV-RL=0073
MV-RL=077 0.78
MV-RL= 0.97
Figure 10: Performance MV in model selection with label swapping (MV-SI.) and random label replacement (ML-RL).
A.7
test accuracy
1
0.9
num of trees
0.7
0.6
0.6
0.5
0.5
0.4
0.3
50
50
0.2
depth
depth
Figure 11: Performance of MV in suggesting hyperparameters that follow Occam's Razor on dataset Cancer. The training data has only 300 samples. The low values of MV large depths and number of trees provide warnings to developers that the hyperparameters are over complex and violate the rule of Occam's 's Razor. The unnecessary complexity the complex learner affects the interpretability of the learner, also making it vulnerable to training label attacks.
17

---

Under review as a conference paper at ICLR 2022
A.8
0.25
1.0
pm
labals
0.9
0.15
Accrazy Accuaaydhanges changes
New accuraty
0.05
0.7
-0.05
0.8
-0.10
1.0
3.0
MV
HV
Figure 12: Correlation between MV, training accuracy changes, and the new training accuracy based on the original labels.
18


Reviews:
[{"review_id": "omGFDYCRW-E", "reviewer": "Reviewer_1Tm6", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths\n\nThe paper proposes an interesting new method for model validation/selection, which may be especially useful in low data regimes in which CV partitions a fraction of the training data to use as a validation set, whereas MV can use the entire training set.\n\nAs far as I know, this work is original, and applies techniques of Mutation Testing and Metamorphic Testing from software engineering to develop MV.\n\nThe proposed measurement itself is simple, easy to understand, seems to be technically sound, and has a justifiable theoretical foundation.\n\nThe paper is well-written and easy to read and follow.\n\nExperiments are extensive on 12 real-world datasets, with comparisons to relevant baselines. The paper also characterizes how MV changes in response to changes in data size, and the fraction of examples mutated.\n\nWeaknesses\n\nI think my main concern is how to choose the fraction of training examples to mutate. It seems mutating large fractions of the data (e.g., 0.4, 0.5) would lead to a significant decrease in the detection of mutants. Thus, is there a suggested optimal value for this parameter, or characterization that can help ML practitioners better decide what value to use?\n\nWhy compare against 3-fold cross-validation instead of 5-fold (the default in scikit-learn: https://scikit-learn.org/stable/modules/generated/sklearn.model_selection.GridSearchCV.html?highlight=gridsearch#sklearn.model_selection.GridSearchCV)?\n\nWhy did the authors choose the mutation protocol to be choosing the next label in line, instead of selecting a different label uniformly at random; would the results be significantly different if using the latter?\n\nMV only works for classification tasks; can MV be adapted for regression tasks?\n\n\nMinor Weaknesses\n\nSection 2.2, par. 3: consider using A(S) to represent a model trained on the data subset S; or, rephrase to say f(S) is the OUTPUT of the model for the subset S.\n\nIs AUC used as the performance metric for the binary-classification tasks? AUC is a more sensitive measure of model performance and may lead to different model selections especially for methods such as CV.\n\n\nAdditional Questions\n\nHow does mutating training labels compare with mutating feature values? Can the mutation of both lead to a better measurement of model validation/selection?\n\nHow does MV perform in the context of model generalization, especially when tuning multiple hyperparameters?\n\n\n\n\n", "summary_of_the_paper": "This paper proposes a new form of model validation called Mutation Validation (MV), which analyzes how well a model fits the training data by first training two models: one using the original training labels, and another using training labels in which a fraction of them (<= 0.5) have been mutated (i.e., the next available class label is used); then, a goodness-of-fit measure is computed via the accuracy of these models on the mutated and non-mutated subsets of the training data, with the idea that the model trained using mutated labels should have similar predictive performance to the original model if less affected by the mutated labels. The paper provides a thorough empirical comparison to other model-validation strategies such as cross-validation (CV) and using a validation/test set; the results suggest that MV provides a more sensitive response to changing hyperparameter values and can better detect the unnecessary complexity of the model than any of the other methods. They also find the value of MV tends to increase with addition of more data, signifying a resilience to mutated labels with additional examples; and they show that MV is relatively robust when choosing what fraction of training examples to mutate.", "summary_of_the_review": "The paper proposes a new method for model validation/selection which is simple, makes use of ALL the training data, and appears to be more sensitive to overly complex models; this ultimately leads to simpler models via a more robust selection of hyperparameter values that better fit the true underlying data distribution. My main concerns are how to choose an appropriate fraction of the training examples to mutate, and how this method can be adapted to regression tasks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "lDxfPCBL4D", "reviewer": "Reviewer_11Jy", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "There are several things to like about the paper -\n\nNovelty- \n\n(1) I think the idea presented in the paper is novel and interesting.\n\n(2) I liked the four research questions posed by the paper in section 3 to validate the usefulness of MV. \n\nClarity-\n\n(1) I found that the paper was easy to read \n\n(2) The synthetic experiments in Figure 2 provide an intuitive explanation for the algorithm at known distributions.\n\nI think there several shortcomings detailed as follows - \n\nQuality and Significance -\n\n(1) Evaluation: I did not find the experimental section to be convincing enough. For example - consider Figure 3 in the paper where MV has an increasing and a decreasing trend as one increases the depth of decision trees. The paper mentions here that the decreasing trend is due to overfitting and the existing validation methods like CV show no change.  However the claim of overfitting mentioned here is not justified empirically by showing the generalization error of the model. What does overfitting mean in this context ?  Is the set used for CV very small that it is no longer determining overfitting? Can you show that MV finds the best model compared to CV when the generalization error is evaluated on sufficiently large dataset?  Can you show overfitting in feature space?\n\n(2) It is unclear how useful the method will be as the datasets used are small scale (UCI, MNIST, and CIFAR) and the models used are simple. Moreover the paper describes in Figure 8 that with large scale datasets MV no longer shows similar trends as shown in Figure 3. This makes it difficult to evaluate the significance of this work.\n\n(3) In Table 4 what is the variance in the test accuracy across the different recommended depths?  What does the stability here translate to empirically in terms of model performance? Consider asking similar questions to (1) here.\n\n(4) The paper mentions that the given method is motivated from a software engineering algorithm principle - mutation testing and metamorphic testing. I found this motivation hard to connect. Metamorphic testing is a more definitive test to find bugs in a program (if the relation is violated implies there is a bug) whereas the relation/method proposed by the paper is used in a more relative context (comparing it with nearest hyper-parameters) rather than being a definitive violation of a relation.\n\n(5) How do the two terms - (a) difference in training accuracy of models trained on original data and training accuracy of models trained on mutated data and (b) Accuracy of model trained on mutated data based on the original training data change - change as MV changes empirically? \n\n(6) How is the hit rate in section 4.1 calculated?\n\n", "summary_of_the_paper": "The paper introduces a new method for model validation called Mutation Validation (MV). Briefly, MV mutates training data labels and trains the model on both original and mutated training data. It then uses both these models to get a score that is a function of (1) difference in training accuracy of models trained on original data and training accuracy of models trained on mutated data and (2) Accuracy of model trained on mutated data based on the original training data. The paper explains the larger the score the better the learner fits the training data and hence can be used for model validation.\n\nThe paper provides an empirical study to show the effectiveness of MV by comparing it with Cross Validation (CV). In this study they explore 8 different learning algorithms, 18 datasets and 5 types of hyper-parameter tuning tasks.\n", "summary_of_the_review": "The idea presented in the paper novel and interesting to me. My major concerns are with the experimental sections - I did not find it convincing enough and I am unsure of its use case given the current results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dTp3d1HJw0M", "reviewer": "Reviewer_S95g", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\n\nThe paper is well written and well motivated, and proposes a simple\nmethod for model validation, mutation validation (MV), based on\nchanging the labels of training instances, and measuring how well the\nlearner fits to the new mutated problem, and combining the original and new\naccuracies. Variety of experiments are conducted to show the potential\nof the approach to complement traditional techniques such as\ncross-validation.\n\nHowever, the major shortcoming of the paper is performing the model\nselection experiments on only toy problems with 2 features.  The\nmethod is simple enough (and elegant!)  that I implemented the MV score and compared a\nfew learners on a couple of the authors' UCI datasets (breast cancer\nand Bank) and other datasets.  I double checked my implementation and\nmatched the scores and trends with what the authors have published\n(more details below). I found that unfortunately, the MV score can\npick simple depth-limited decision tree models vs bag of trees (of\nlarger or unlimited depth, so  learners with higher fit capacity) while bag\nof trees has a significant higher test accuracy (simple 10-fold\nvalidation tends to pick the bag of trees).\n\nIt seems to me model selection is the main potential application of\nMV, specially because unlike cross-validation, MV doesn't give you a\nsense of performance on test (beyond training performance). However, if it can fail in these simple\nscenarios, the impact of this work would be very limited (the other attributes\nof MV, such as stability, shown in subsequent experiments in the paper would be minor if it doesn't do a good job\nat model selection...)\n\nMore investigation is required, and I am not sure if this shortcoming\ncan be remedied.  This observation suggests MV has an undue bias\ntowards simpler models, or is not appropriate for comparing across\nlearning algorithms, or fails with committees/ensembles, etc.\n\n\nSuggestion for model selection experiments:\n\nThe model selection experiments are done on toy problems in the paper. I understand\nthe 'true model' is unknown in the real datasets (and one can get  certain \ninsights into algorithm behavior with synthetic data), but what we\ncare about is test/generalization accuracy any way in practice (in a\nsimplest/standard application of supervised machine learning). The\nauthors can keep that section on toy problems (shortened) but also\ninclude a variety of publicly available datasets (UCI, etc) like they\ndid for the other subsections. To evaluate model selection, keep some\nportion for test in each trial (20%, 50%, 80%), and compare\nhead-to-head say 10-fold validation with 10 trials of MV to select a\nmodel (a couple or more learning algorithms) on the training\nportion. How often does MV beat 10fold validation, in selecting the\nbetter model, ie the one with lower test set error, on a particular\nproblem, as well as across problems?  (of course, both the learning\nalgorithms to choose from and problems should have some diversity)\n\n--------\n\nMore details of my experiments:\n\nThe proposed MV measure is simple and elegant, and it was simple enough\nthat I implemented it and compared it to say 10-fold cross-validation,\nhead to head on the breast cancer and Bank (binary class datasets, as I didn't implement\nthe authors' label shifting method for multiclass ). I\nsaw a similar result on another dataset (text classification).  I'll\nfocus on breast cancer.\n\nI first matched scores from my implementation (MV and\ncross-validation) and validations with the author's results on the\nbreast cancer dataset (Figure 3, eg 3rd plot is for Wisconsin breast-cancer). \nSo a single decision tree gets a MV score of around\n0.93 (eta of 0.2 as in paper) and that's the peak of MV for breast-cancer. Higher depths\nprogressively lead to lower MV scores.\n\nUnfortunately MV fails in model selection, when comparing decision\ntrees of say depth 3 to say bagged trees (say 50 trees of depth 20,\neach trained on a bootstrap sample of training): The bag has a better\n accuracy on the test split (generalization), but the MV method substantially\nfavors a single tree of small depth.  The MV scores of the bag of\ntrees (in 0.6 to 0.8 ) are not even close to single trees of small\ndepth (around 0.9 and higher).  For instance, when we random split the\n~600 instances of this data into two halves (half for training, half for\ntest) in each of 50 trials, 10-fold cross-validation picks the model\nwith smaller error ~40 times, while MV picks the better model only ~3\ntimes (both working on the training split to pick between the two models,\na tree of depth 3 vs a bag of trees). The average over trials of\n01-error of a single tree is 0.076, while for the bag it's\n0.055 (significantly better). Changing the training portion or the eta of MV, etc, \ndoes not change this comparison much.\n\nThere are 3 elements in the MV score: the training accuracy (on\noriginal unmuted data), and the accuracy of the model trained on muted\ndata (some labels flipped) on the same (muted) sample it was trained\non and on original data.  The issue is that the bagged tree gets a\nhigh training accuracy on a mutated sample (such as near 1.0), while the\naccuracy on original labels either does not improve or goes down, so\nthe MV score of the committee of trees, which punishes for fitting to\nmuted data, goes down substantially, while a single tree of small\ndepth has a different accuracy profile, in particular lower accuracy\non the mutated sample, so its overall MV score remains relatively\nhigh.  And it may be that a simple combination of these accuracy\nscores is not sufficient for successfully picking a model in practice.\n\n\nThe above observation suggests MV as currently developed has an undue bias towards simpler models,\nor is not appropriate for comparing across learning algorithms, or\nfails with committees/ensembles, etc. To me, currently, the MV score\nhas most potential (possible advantage over cross-validation) for\nparameter selection for a fixed learning algorithm, but that also\nrequires more careful and extensive investigation.\n\nAnother (secondary) issue is class imbalance (eg the Bank dataset is somewhat\nimbalanced at ~10% positive). MV, as developed in this work, is\nappropriate when 01-error is useful. As class imbalance grows (for\nbinary-class problems), the utility of MV further degrades.\n\n\n\n-------------------------\n\n(My review before reviewer discussion and experiments) \n\nI enjoyed reading the paper!\n\nThe paper is  written clearly and provides good motivation,\nexamples/illustrations, and the techniques are understandable and\nnovel to best of my knowledge, and I expect very practical too.\nEspecially, with deep neural networks with high capacity to fit, these\nnew validation techniques are timely.\n\n---------------\n\nDetailed feedback/recommendations (some comments or suggestion\nare based on my reading the paper linearly!  ):\n\npg 1. minor: What is \"mutating a program' mean, in a bit more detail?\nin 'Mutation testing mutates the program, then re-executes the tests\nto monitor ' ...  a few additional words of description (eg to get sense of \nthe extent of change), such as 'it's one or a few\nlines of code change' (or short examples of code mutating could help\nhere)..  (however, changing labels and changing code are pretty\nunderstandable)..\n\npg 1. metamorphic relations is more ambiguous (than mutation) at this\npoint: \"metamorphic relations, which is the relationship between input\nchanges and output change\" but later  on pg3 you do describe it more\nclearly ('Metamorphic relation specifies how a change in the input\nshould result in a change in the output'). Could repeat that point\nhere too in giving a quick description of metamorphic for better\nclarity. (possibly replacing the more general ambiguous description\n\"which is the relationship between..\")\n\n\npg1.  Perhaps replace 'Furthermore, ' by a contrasting phrase such as\n'On the other hand', in 'Furthermore, an over-simple learner ..'\n\n\nsection 1, pg2. Perhaps mentioning the (potential) short comings of MV\nwould be useful when you list the advantages of MV at this point: what\nare potential shortcomings as compared to the typical validation\ntechniques?  (at this point in the paper, without reading the rest of\npaper, I can see it requires a parameter for binary classification,\nie what fraction of labels to flip, but other techniques also require\ndeciding on portion to set aside.. and efficiency of the test could be\nan issue specially if the flip fraction needs to be varied\n.. ).. Perhaps the most notable is that it doesn't give you the\nout-of sample accuracy, \\ie a sense of generalization\nperformance/accuracy. How about other theoretical/conceptual potential\ndrawbacks?\n\npg3:  perhaps replace 'measurement' in 'MV measurement' with 'score'\n(so 'MV score' ) to imply to reader that a higher value is better.\n\npg3. Can eta be above 0.5 for the multiclass case.  perhaps a very brief discussion\nwould be useful.\n\nExperiments:  \n\n-- why eta of 0.2 (mutation fraction)?  How did settings do, such as\n 0.1 and sensitivity to it?  Of course, it's good to see that eta of\n 0.2 was uniformly adequate.  I think you can point to the appendix at\n this point (later I found the appendix to have a section! and earlier\n in the paper, you do state that the effect of eta is studied in\n appendix. Probably it's better to mention it here.).\n\n-- Maybe a better name for label swapping is \"label shifting\"?\n\n-- Why this specific manner of label flipping for multiclass cases (it's intriguing!),  \"label\n swapping\"? ie to replace a label with the next label in the label list\"?\n Why not just randomly pick a label from other classes? (or pick based\n on class proportion, etc..)  this was the one puzzling aspect of the\n experiments!  since the first (simplest) idea that comes to mind is\n random selection from available classes (of course, this question is\n relevant only to the non-binary problems you looked at). It appears\n this label swap generates systematic error, not random noise, but I\n am not sure what the implications are (eg could be easier, than\n random label noise, to fit the training data, since there is a\n pattern to the injected label errors, but generalization degradation\n can be impacted further by this, vs random noise.. ) Later I saw in\n the appendix that the theoretical result from the appendix motivates\n this choice vs simpler random noise. it would be good to mention it\n when you state you are using label swapping, vs uniform random\n .. Also, it would be good to empirically see whether label swapping\n (or \"label-shifting\") vs random uniform selection of labels, makes a\n difference. (I don't think you currently do this comparison, checking the appendix)\n\n* The scores in figure 2 specially are hard to see/read.\n\npg 9.\n\ninsert 'more' in \"We show that MV is effective and stable than the\ncurrently adopted CV, validation accuracy, and test accuracy\"\n\npg 9: (in contrasting with noise injection) perhaps better to replace\n'inputs' with 'features', eg. in \"2) mutates labels, not inputs\" (labels\nare input too, but agreed, labels are inputs to the learner not the model)\n\npg 9: I am not sure if 'model robustness' does not include  or highly overlap with model\nfitting.. (it's a general phase) in 'aims to validate model fitting,\nrather than model robustness.' perhaps make model robustness more\nspecific by adding something like 'robustness to feature\nperturbations'\n\n\nAppendix. Minor: m is used as training set size at one point (while in the rest of the paper, it's the mv score).", "summary_of_the_paper": "\nThe authors propose and explore  a method based on changing (mutating) the labels of training data to do model selection (\nselecting among learning\nalgorithms, or hyper parameters, etc).  The method is very practical and a number of experiments show the properties of the approach\nand its potential to complement  cross validation and other validation techniques.", "summary_of_the_review": "\nThe paper is clearly written and well structured, with good\nmotivation, examples/illustrations, and the techniques are\nunderstandable and novel to the best of my knowledge.  The work\nis mainly empirical, but the experiments need to be substantially\nextended, and the basic approach may need further development, \nto show the benefits of mutation validation.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FT4vWd3qJp0", "reviewer": "Reviewer_FmyF", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n-\tA novel approach in the area of validation techniques, which are very conservative\n-\tHuge empirical validation supported by theoretical basis (see Appendix)\n-\tLarge potential for future studies\n\nWeaknesses:\n-\tThe method looks highly dependent on a particular evaluation metric (performance of a model): for instance, the paper address one case about accuracy (the formula (1), arguments in Sec.2.2, theory in Appendix). It is not clear how to develop a measurement m (analogue of (1)) for other performance techniques\n-\tOverfitting is a very important problem in the industry. The novel approach requires exploration in “real life” (huge industry datasets and models).\n-\tMinors:\n1)\tFig.1 “A better learner is less”: Which ones are better learners?\n2)\tIn Sec.1, 4th paragraph: “The model recommendation hit rate for MV is 92%” model recommendation hit rate is not a clear term for introduction. Can be clarified?\n3)\tIn Sec.1, 4th paragraph: “set, the average variance is 0.004 and 0.008” Is it reasonable to talk about var among 5(?) runs?\n4)\tSec.3, RQ1: how do we define the effectiveness?\n", "summary_of_the_paper": "This paper introduces new approach for validation of ML models which is based on top of ideas imported from software development & QA (so-called mutation and metamorphic techniques). The core claimed advantage consist in the ability to avoid cross-validation and validation and test sets (the famous approach to avoid overfitting while learning a ML model). The work contributes also a huge empirical study with experiments for dozens of datasets and several models and hyperparameter tuning.", "summary_of_the_review": "Nice and clever work. I vote for acceptance due to the “fresh blood” in the so conservative area of validation techniques. This work represents a first empirical study in this new direction, and a lot of future work/studies seem to be followed. So, a lot of things would be nice to check and study to get comprehensive overview of the novel approach, but this first step is enough to be presented at ICLR 2022.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a model selection technique for classification problems, called mutated validation (MV), based on randomizing the labels of the training set. The idea is interesting but not well served by the presentation of the objectives and the experimental results provided in the paper. The discourse is confusing because it is not clear what is the purpose of model selection here. Usually, model selection aims at finding a model with lowest generalization error. This is a well-defined goal, and the performance regarding this goal can be measured by the expected test error that is usually estimated from a test set. In this paper, the goal of model selection is not precisely defined, but it cannot be as usual, since some models that minimize test error are said to overfit. Most experimental results show that models selected by MV differ from the ones selected by cross-validation (CV), without providing an objective measure of the relative merits of MV and CV (see details below). Although the authors do not make this clear in the paper, they argue in the discussion that the merit of their approach is to select a "simple" model that avoids overfitting. Their message should be clearly stated in the paper, and it should be supported by experiments displaying simplicity *and* test error, or by any experimental result showing the objective benefits of the proposed MV, possibly combined with CV as some of the reviewers suggested. I therefore recommend rejection, but with encouragement to pursue this work, by defining precisely the formal objectives pursued in this work with model selection, and by measuring the benefits of MV on these formalized objectives.

Details:
The arguments in Figure 2 and Table 2 are not substantiated and are clearly not applicable to a model selection mechanism that would aim to select the model with the lowest expected error (or complexity). The "obviously ill-fitting rectangle-shaped decision boundaries" are perfect with respect to expected test error and simply described in Occam's razor terms. 
Similarly, most results are subjective:
 - Figure 3 shows that MV and CV are different (on the left), and that CV is a better estimate of the test error (on the right).
 - Figure 4 shows some differences between CV and MV, with no clear way to judge which would be better.
 - Table 4: variance says nothing about relevance; choosing an arbitrary value before seeing the data gives a zero variance.
 - Figure 6, 7: again, subjective result
 - Figure 8: no comparison
 - Figure 10: label swapping or random label replacement is the same in binary classification, there is just a difference in the parameterization (swapping 20% of the labels is the same as randomizing 40% of the labels).
 - Figure 12: I am not sure what is drawn here, but it seems to be related to the training error only.
 - 
Regarding objective test results:
 - Figure 5 is an experimental result that shows objective differences between CV and MV, and appear to be marginally in favor of MV for selecting the model with lowest test error (in 3 out of 8 graphs). However, there is no joint optimization on the 2 hyper-parameters: there is not a single data set for which the best value of the test error is identical in the two graphs (wrt dropout, wrt learning rate). In other words, the graphs for dropout rate and/or learning rate are provided for a suboptimal choice of the other hyperparameter.
- Figure 9: CV is more closely related to the test error than MV.
- Figure 11: MV chooses models that do not achieve the highest test accuracy.

As a side note, I think that the proposition could be also positioned with respect to papers that presented similar ideas, where model selection is based on stability, either with unlabeled examples [1] or by modifying the training set [2].
 
[1] Dale Schuurmans, Finnegan Southey: Metric-Based Methods for Adaptive Model Selection and Regularization. Mach. Learn. 48(1-3): 51-84 (2002)

[2] Olivier Bousquet, André Elisseeff: Stability and Generalization. J. Mach. Learn. Res. 2: 499-526 (2002)
Decision: Reject