Cost-Effective Testing of a Deep Learning Model through Input Reduction
Authors: Jianyi Zhou
Feng Li
Jinhao Dong
Hongyu Zhang
Dan Hao
Venue:  (2020)
Keywords: Software Testing
Deep Learning
Input Data Reduction

Abstract: With the increasing adoption of Deep Learning (DL) models in various applications, testing DL models is vitally important. However, testing DL models is costly and expensive, especially when developers explore alternative designs of DL models and tune the hyperparameters. To reduce testing cost, we propose to use only a selected subset of testing data, which is small but representative enough for quick estimation of the performance of DL models. Our approach, called DeepReduce, adopts a two-phase strategy. At first, our approach selects testing data for the purpose of satisfying testing adequacy. Then, it selects more testing data in order to approximate the distribution between the whole testing data and the selected data leveraging relative entropy minimization.
Experiments with various DL models and datasets show that our approach can reduce the whole testing data to 4.6\% on average, and can reliably estimate the performance of DL models. Our approach significantly outperforms the random approach, and is more stable and reliable than the state-of-the-art approach.

Under review as a conference paper at ICLR 2020
COST-EFFECTIVE TESTING OF A DEEP LEARNING MODEL THROUGH INPUT REDUCTION
Anonymous authors Paper under double-blind review
ABSTRACT
With the increasing adoption of Deep Learning (DL) models in various appli- cations, testing DL models vitally important. However, testing DL models costly and expensive, especially when developers explore alternative designs of DL. models and tune the hyperparameters. To reduce testing cost, we propose to use only selected subset of testing data, which is small but representative enough for quick estimation the performance of DL models. Our approach, called DeepReduce, adopts two-phase strategy. At first, approach selects testing data for the purpose of satisfying testing adequacy. Then, it selects more testing data in order to approximate the distribution between the whole testing data and the selected data leveraging relative entropy minimization. Experiments with var- ious DL models and datasets show that our approach reduce the whole testing data to 4.6% on average, and can reliably estimate the performance of DL models. Our approach significantly outperforms the random approach, and is more stable and reliable than the state-of-the-ee approach.
INTRODUCTION
In recent years, deep learning (DL) models have been successfully deployed in a variety of appli- cation domains. Erroneous DL models may lead severe consequences. For example, defect in a DL-based autonomous driving system resulted in the death of one pedestrian (Amir 2018). Therefore, sufficient testing for DL models is critical for ensuring system quality. However, the cost for testing deep learning models is not neglectable. For example, DeepFace (Taigman et al.) 2014], the face recognition system of Facebook, used about 0.22 million face images for testing- Tian et al. (2018) generated 254,221 images for testing a Chauffeur-CNi based autonomous driv- ing model and achieved a neuron coverage (the ratio of activated neurons) 88%. The popular ImageNet dataset (Russakovsky al. 2015) contains 100,000 testing images (100 per class) for testing various image classification models. Clearly, it could take a long time to sufficiently test a DL model. Furthermore, in practice, developers always need to evaluate alternative designs of DL models and optimize the models. For example, they need to explore different deep neural network (DNN) structures (such adding/deleting layer) different hyperparameters (such learning rates and dropout rates), which all lead to increased testing cost.
To reduce the testing cost, it is desirable have an early estimation of the performance of DL model by using only a small amount of testing data. After the first end-to-end system is established, developers can quickly the performance of the DL model using small subset of testing data, and start evaluating the design of the model. If the performance is acceptable, the developers can perform full-scale testing. Otherwise, the developers can seek alternative designs of the model (e.g., adjust DNN structures or learning algorithms), or further tune the hyper-parameters (such as the learning rate). In this way, developers can quickly obtain an accurate DL, model without having to perform costly full-scale testing many times.
To achieve an early estimation of the performance of DL model, the key challenge is to select a small yet effective subxet of testing data for testing the model. The selected data should be able to achieve similar testing performance as what the entire testing data achieves, and should be small enough to reduce the testing cost. Random sampling is not ideal solution it tends to select more testing data in order to represent the whole testing data. [i et al. (2019) recently proposed a method to reduce the number of unlabelled instances required by DNN testing through carefully

---

Under review as a conference paper at ICLR 2020
designed sampling strategy. However, they require users specify the number of data instances as the input to their approach. That is, without a proper value of such an input, they have no guarantee that the selected data is sufficient for DNN testing. Furthermore, being based on random sampling, their results could be unstable in different runs.
In this paper, we propose DeepReduce, technique for cost-effective estimation of the performance of a DL. model. DeepReduce can significantly reduce the amount of testing data for testing a DL model but can still achieve comparable performance as the whole testing data achieves. We formu- late the input reduction problem in this work as a multi-objective optimization problem: 1) minimize the amount of testing data selected from the whole testing data; 2) maximize the testing adequacy achieved by the selected testing data; and 3) maximize the similarity of output distributions achieved by the selected and the whole testing data. These objectives take into account the efficiency, com- pleteness, and effectiveness of testing in order to make the performance estimation more reliable. Inspired by the usage of structural coverage in conventional software testing, we use neuron cover- age of a DL model to measure its testing adequacy in this work. We use the outputs of the neurons in the last hidden layer of a DL model to represent the output distribution. In order to maximize the similarity between the output distribution achieved by the selected data and the whole testing data, we design& a heuristic- based algorithm to guide relative-entropy minimization.
To evaluate approach, conduct extensive experiment six DL models and two datasets. The experiment results show that DeepReduce can reduce the amount of testing data required for reliable testing from 10,000 to 455 average, which means that over 95.5% % testing cost can be saved by DeepReduce. Compared with the state-of-the-art approach (Li et al. 2201)). DeepReduce more stable and reliable, and can reduce more testing data. The experiment results also shows that DeepReduce can be used in performance estimation in regression scenarios.
In summary, we make the following contributions in this work:
A novel approach to cost-effective testing of a DL model by considering three different objectives: efficiency, completeness, and effectiveness.
An extensive empirical evaluation to investigate the performance of our approach on real- world DL models. The results have confirmed that the proposed approach can significantly reduce DL testing cost by reducing the amount of input data required for testing a DL model.
RELATED WORK
Cost of deep learning: Achieving the highest accuracy has been the ultimate goal of many DL applications. In recent years. the cost of a DL model has also received considerable attentions. For example, Canziani et al. (2016) described a comprehensive analysis of important metrics in practical DL applications such memory footprint, parameters, inference time and power consumption. Many techniques have also been proposed to reduce DL cost in practice. For example, exarale,Karppath & Fei-Feil (2055) improved the testing time of image description generation from 3,170ms 240ms for each image by designing a new network architecture. Ning et al. (2019) proposed Adaptive Deep Reuse, which can reduce training time for deep learning networks by more than 60 percent without sacrificing accuracy. The cost of constructing DL model could also be reduced through pretrained models and transfer learning (Glorot et al. 2011 Thrun 1996 Yosinski et al.) 2014). In our work, we propose a software engineering approach to reduce testing cost in DL, practice.
Deep learning testing: Successful applications of deep learning techniques require thorough testing of the DL. models. Existing research mainly focuses on generating adversarial examples (Pei et al. 2017 Tian et al. 2018 /Zhang et al.] (018)) and proposing new coverage criteria (Pei et al.) 2017 Ma et al. 2018 Sun et al. (2019) for testing DNNs. However, they ignore the cost of DNN testing, which is also an important problem and cannot be ignored. The costs of DNN testing mainly lie on manual labeling and regression testing. For the former, labeling for those unlabeled data is usually conducted by human, and the costs for labeling is high. Therefore, it is desirable to improve testing efficiency by using reduced subset of testing data.
In general, the input reduction problem can be viewed as an instance of the existing test minimization problem (Harold et al. 1993. Yoo & Harman 2012 in conventional software testing, which aims
2

---

Under review as a conference paper at ICLR 2020
to find the smallest subset of tests satisfying the same test requirements (e.g., structural coverage). Previous work pointed that test reduction is an NP-complete problem (Yoo & Harman 2012). and thus the input reduction problem is also Nocomplee Although large number of test minimization techniques have been proposed in the literature, none of them can be applied directly to solve the input reduction problem, because the former techniques usually focus structural coverage alone.
Recently, Li et al. 2019) proposed a method to reduce the amount of unlabelled testing data required in operational DNN testing through carefully designed sampling for the purpose of reducing the cost of manual labelling. In particular, this approach iteratively constructs several groups with un- labelled data randomly picked from all unlabeled data, and then enlarges the selected set with the group that contributes the most to cross cross-entropy minimization. However, this approach requires users to specify the amount of selected data instances as input, and cannot guarantee that testing is sufficient. Our approach addresses this problem in two ways: 1) ensuring testing adequacy achieved by the selected testing data is the same as the whole testing data; 2) approximating the output distri- bution between the selected and the whole testing data without the need for specifying the number of data instances.
3 PROPOSED APPROACH
3.1 PROBLEM DESCRIPTION
In order to estimate the performance of DL model in cost-effective way, this paper attempts to select a representative subset of testing data from any given set of testing data, which need labelling and are subsequently used for testing process. Considering the usage of the selected data, i.c., estimating the performance of a DL model. they are expected to satisfy at least two objectives. The first one that the selected data are expected to have the same testing adequacy (e.g., structural coverage) as the given set, so as to guarantee that the performance estimation is conducted on the complete learning model, instead of partial learning model. The second one is that the selected data are expected to generate the same output distribution as the given set, so as to guarantee the estimation is correct and precise. In other words, the problem this paper targets can be viewed as an input reduction problem, which is formally defined as below.
Definition 1. Given set of testing data T and its target DL model M, we define function f(T, M) to measure to what extent the testing data T cover the structure of M and function g(T, M) to measure the ouiput distribution of M with T. The problem of input reduction in DL testing is to find the smallest subset of testing data from T. which is denoted as T', satisfying that f(T, M) ) = and 9(T, M) MM).
As the input reduction problem is No-colplete. we tune its definition by relaxing its requirements on the output distribution (T"", .M.. That is, we replace g(T, M) = 9 (MT by g(T, M) = g(T', M). which refers to the output distribution gT, M) is similar to g M). Such require- ment on output distribution guarantees that the estimation using T' is close to or even the same as T on M.
To solve the redefined input reduction problem, we present new technique DeepReduce to select a small set of testing data for cost-effective testing. In particular, we first present the metrics used in DeepReduce to define functions/ ff and (in Section 3.2). and then a two-phase reduction algorithm used in DeepReduce to select testing data (in Section
3.2 INPUT REDUCTION METRICS
Structural coverage is widely used in conventional software testing, which measures to what extent structural elements (e.g., statements, methods, functions) are covered by a test or test suite. There- fore, structural coverage is usually taken as the default testing requirement of test minimization, so is in input reduction. In the literature, there are various structural coverage criteria (e.g., Neuron Coverage (Pei et al. 2017). k-Multisection Neuron Coverage, and Neuron Boundary Coverage (Ma) jtt al. 2018)) proposed for DL models, each of which can be used to define the function f. In this work, use Neuron Coverage (abbreviated
NC) representative structural coverage criterion since it is lightweight. NC (Pei et al., 2017) is defined as the ratio of activated neurons of a DL model, where activated neuron refers to the neuron whose output of input data is larger than
3

---

Under review as a conference paper at ICLR 2020
given coverage threshold B. In particular, NC with various coverage threshold 3 is taken different coverage criteria (Pei et al. 2017). Following the previous work (Pei et al. 2017). we use NCB to represent NC with various coverage threshold B. Note that approach not specific to these criteria, and we will investigate the proposed input-reduction approach by using other structural coverage criterion in the future.
In this paper, we measure the data distribution by leveraging the outputs of the neurons in the last hidden layer. In particular, given set of testing data T and its target DL model M (which consists of m neurons in its last hidden layer), we record the output range of T on each neuron e; (i E [1, ml) and divide each output range into K equal sections De..1, De,,2. ... and De..k. In other words, the output of each testing data (t E ') on e, falls into one of these sections. Therefore, for each e, in the last hidden layer of M, we calculate the percentage of testing data whose corresponding output falls into Dea.1, Dec.2, .... and Ke,,K, and then denote the corresponding results by Pf (PF (1), ..... P.: (K)), where Pf (j) denotes the percentage of input data in T whose corresponding output falls into De. j. Finally, the distribution of the given model M with T' is represented as Pr (PF) pea pem
3.3 TWO-PHASE REDUCTION ALGORITHM
With the structural coverage / and output distribution g mentioned in Section 3.2 two-phase reduction algorithm, which is called DeepReduce, with the purpose of selecting testing data by satisfying f(T, = f(T", .M) and M) ~ g(T", MM.. In particular, our two-phase reduction algorithm first selects set of testing data to guarantee the structural coverage by reusing the existing HGS algorithm (Harrold et al.) 1993), and then selects more testing data with the purpose of maximizing the similarity of output distribution between T and T'.
we propose a
For a learning model M with the given testing data set T, we use Pr to represent its output distribu- tion, which is calculated by the ratio of testing data falling into sections P (i E [1,m], j [1, K)) following Section 3.2 For the selected testing data set T', we calculate its output distribution on the sections De.. E [1, E [L, K)) produced by T' instead of T" for ease of comparison, which is denoted by Pr.. We use relative entropy (Kullback & Leibler, 1951 which is also called Selbback-Leible Divergence, to measure the similarity between them (denoted as KL (L(Pr, Pr: ))
The calculation is defined in Formula
E
Pe (f) * log ()())(()))
KL(Pr, Pr.)
1
Relative entropy is used to measure how one output distribution is different from the other one. Note that the output distribution of T or T" contains m probability distributions, we take their average as the similarity between two output distribution That is, the smaller the value is, the more similar these two output distributions are.
Algorithm presents the overall framework of our two-phase reduction algorithm, i.e., ReepRe In particular, given a testing data set T and its learning model M, DeepReduce aims to produce a reduced subset of testing data by satisfying that (1) neuron coverage of T' is the same as that of T and (2) small relative entropy value between T and T', indicating the similarity between the output distribution of and T' is high. In partieular, we use a to represent the threshold of relative entropy, which is usually set to be a very small value like 0.005 in practice. More discussion on the choice of this value and its influence can be found in Section 4 Besides, to facilitate the selection of testing data, DeepReduce also records the following information before applying it. Cov records the NC coverage of T, TD is a set recording the output distribution of T (i.e., Pr calculated following Section 3.2), and TI is an array, in which each element records the sections of neurons that the corresponding testing data falls into. TI is then used in Algorithm 2 later in this section.
and more details are describe
Note that we do use cross entropy as previous work [Li 2019). because in the special case that T equal to T', their cross-entropy values on some DI. models may differ to large extent. "The average result can be used to represent the similarity between output distribution, because DL. model typically reduces the correlation among the neurons in its last hidden layer (Koller & Friedman 2009).
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Two-Phase Reduction
In the first phase, DeepReduce reuses the HGS (Harrold et al.] 1993) algorithm to select the minimized subset of T with the same NC coverage. In particular, the HGS algorithm is greedy algorithm which tends to select test- ing data covering the activated neurons that are less covered by the existing testing data. In Line 2 of this algorithm, DeepReduce uses represent the output of the HGS algorithm on 7' by satisfying the NC cov-
Input .Input data: T; model: M,, coverage: Coc, output distribution T: TD, output section: T7, and the threshold of relative entropy: 0 Output: Reduced test set 7
// First Phase;
T t HGS(T, Cov);
HGS(T,Con
TD' + UUpdate(TD, T'); REMAIN - T T";
erage recorded by Cov, which is a subset of se-
I/ Second Phase:
lected testing data. In Line 3, DeepReduce uses
while KLITD, TD') 2 do
a function Update TD, T') to calculate the out-
7
t' = geiCandidate():
put distribution of the selected data set 7" (de- noted as TD') by using the section division gen-
T - + {C];
REMAIN < REMAIN' (();
erated by TD, to facilitate the output compari-
TD' <- UpdateeTDD, T');
son between 7 and T" according to Formula In Line 4, DeepReduce put the remaining uns- elected testing data into REMAIN, which are to be selected in the second phase. In the second phase, DeepReduce selects more testing data (ac- cording to Lines 6-11) until the set of selected data is similar to T in output distribution. That is, more testing data are selected until the termination criterion (i.e., the relative entropy value between T and 7' is no larger than the specified threshold a) is satisfid, shown by Line 6.
10
end 12 return T";
To facilitate the selection of testing data to min- imize the relative entropy value between T and selected data, DeepReduce designs function getCandidate() to iteratively select testing data from REMAIN, shown by Algorithm 2 In Lines 2-11, DeepReduce seeks to find the sec- tion in which the output distribution differs the most between T' and T each neuron, and these sections are recorded based on the order of the corresponding neuron by re. In particu- lar. for each neuron e;, DeepReduce calculates the output difference on each section De..k be- tween T' and 7" through TD;,/TD; A. so as to find the section with the largest output dif- ference on each neuron (denoted as kmaz in the algorithm). Note that in this section selec- tion process, DeepReduce uses TDEx/TD l. in- stead of Pr (j) * log P PP. (j) (defined in Formula D because they produce almost the same selection results and the former reduces the computation cost to a large extent. Then Lines 12-26 are to select the testing data t' that may minimize the output difference between T and the selected testing data set. As variable re represents the output distribution difference be- tween T and T", the testing data whose output distribution is similar to re (which is measured by the getSimilarity function) are expected to be selected so as to minimize the output distri- bution difference between T and the selected testing data set. Following this intuition, in Lines 13-20, for each t in REMAIN, DeepRe- duce iteratively calculates the number of neu- rons in 77[1] and re with the same section, and finds the testing data with the largest number of such neurons. diel is an array recording candidate
Algorithm 2: getCandidatel
Input : TD', TI, T", REMAIN, m, K Output: Candidate test: :t'
re +0: 0:
foreach i E {1,m) do
kmax t
mazvalue TTD;,/TD',,
foreach K E {2, K) do if marvalue < x TTI', 1, then
kmax +- k;;
marvalue T
end
re + re U {kmax); 11 end mazsim 0, dict +- 0: 13 foreach t E REMAIN do sim < getSimilarity(7//t)) re);
15
if sim > marsim then mazsim +- sim; dict + {t);
17
else if sim == marsim then 18
dict +- dict U (t);
20 end
ménvalue +- 6o;; 22 foreach 1. E dict do if minwalue KI(T, T" U (t)) then minvalue +- (I T' (1)); t't
24
end 27 return E':
5

---

Under review as a conference paper at ICLR 2020
testing data, each of which has the largest similarity with re. Among all the candidates in dict, in Lines 21-26, DeepReduce determines which testing data should be chosen by iteratively calculating the relative entropy between the given testing data set I and the selected testing data set by including each candidate.
4 EXPERIMENTS
In this section, we present an experimental study to investigate the performance of the proposed approach from three aspects:
RQI: How does our approach perform in reducing testing data?
RQ2: How do different parameters (i.e., coverage criteria and termination criteria) influ- ence our approach?
RQ3: How does our reduction approach perform in regression scenario?
4.1
DATASETS
In this work, we consider two image recognition datasets, MNIST and CIFAR-10, MNIST (eCCun al. 1998) is a typical dataset widely used machine learning research. It contains 60,000 training images and 10,000 testing images in total. We train three LeNet family models (LeNet- -.Net-4 and LeNet-5) (LeCun et al. 1998) and evaluate our approach on them. CIFAR-10 (Krizhessky al.) 2014) is another widely used dataset, which contains 50,000 training images and 10,000 testing im- ages. On this dataset we train three DL models, including NIN (Lin et al. 2013). VGG19 (Simonyan & Zisserman 2014), and ResNet (He et al. 2016). Table shows the detailed information of these models along with their test accuracy obtained by the whole testing data.
CIFAR-10 VGG19
NIN
ResNet
LeNec1
LeNest
LeNet5
Neurons
3,432
50,782
4.138
148
268
Layers
24
65
115
8
9
Accuray
0.9220
0.9884
Table 1: Subject information
4.2 EXPERIMENTAL DESIGN
For RQI, we first collect neuron coverage and output distribution of the testing data from the trained models, and then apply our approach on the whole testing data to obtain subset. In order to investi- gate the effectiveness of our approach (DeepReduce), we compare with both random approach and BOT (Li et al. 2019). BOT is the state-of-the-art approach in DL testing. Different from DeepRe- duce, BOT requires to specify the number of data instances to be selected. Besides, it does not consider satisfying structural coverage in data selection. To enable comparison, variant of BOT, BOT,, by changing the termination criteria to the one used in DeepReduce. That is, BOT, iteratively selects testing data until the relative entropy value is smaller than a. We also implement random reduction approach, which randomly selects testing data from the whole testing data until the relative entropy value is smaller than a. Both BOT, y and random approach are repeated 50 times to reduce the influence of their inherent randomness, and the average values are used for comparison.
implement
For RQ2, we study the influence of two parameters (i.e., coverage criteria and termination criteria) on our approach. The neuron coverage can be changed when different activation thresholds are given. The termination criteria (i.e., the relative entropy value between the output distributions of the selected data and the whole data) also affects the amount of selected data. Thus, we evaluate our reduction approach with different settings in RQ2.
For RQ3, we evaluate our approach on various modified models with the purpose of investigating the effectiveness of our reduction approach in regression scenario. We first modify the original DL models and retrain the models in order to simulate regression scenario. Then, we evaluate our approach on the modified models by comparing the accuracy of the selected data with that of the whole testing data. We expect that the performance of the modified DL models can still be estimated by using the data selected by DeepReduce. In this work, we apply seven changes in total for all

---

Under review as a conference paper at ICLR 2020
the studied models, including adding layer (ADL), deleting layer (DEL), adding neurons (ADN), deleting neurons (DEN), changing learning rate (LR), changing momentum (MO), and changing dropout ratio (DR). Although these changes do not cover all the cases where DL model is modified in regression scenarios, they are typical changes and cover both structural (related to model structure) and non-structural (unrelated to model structure) changes.
4.3
EXPERIMENTAL RESULTS
4.3.1 RESULTS FOR RQ1
In this RQ, we investigate the effectiveness of DeepReduce in reducing testing data for estimating the performance of a DL model. We take the default setting of two parameters, i.c., threshold for neuron coverage and a. For the former, we take the recommended value (0.5) given by Pei et al. (017). For the latter, we assign 0.005 to when the termination criteria is used in the algorithm. 2 presents the results for comparison. In the table, "Acc." represents the test accuracy achieved by the selected data, and "Size" represents the amount of selected data.
Approach
Metris
VOGTO
CIFAR-10
(0.920)
LeNed (0.9357)
LaNew
MNISTT
LeNect (0.933))
DeepReduce
Acc.
0.8316
0.9382
0.877y
0,9757
0,99213
0.995
Size
487
152
827
371
261
233
0,8876
0.9345
0.9221
0.9860
0.9886
0,9007
Randou
Size
3308
3258
4901
3159
2436
2589
DOT
Acc.
0,8571
557
0,9335
438
0,8959
K35
0,9854
0.5905
0.990S
Table 2: The effectiveness of DeepReduce in input reduction
From the table, we find that DeepReduce can reduce the whole testing data significantly, ranging from 261 (2.6%) to 827 (8.3%), with an average of 455 (4.5%). Also, we can find that DeepReduce can achieve an average of 98.19 18.1% the original accuracy (the test accuracy achieved by the whole testing data). In the worst case, the accuracy achieved by the selected data is still over 94.3% (0.8316/0.8811) of the original one. The results show that our approach can save more than 95.5% (1 4.5%) testing cost average. Besides, the selected data of DeepReduce achieve similar test accuracy as the whole testing data achieves, which indicates that DeepReduce is effective in estimating the performance of DL models.
When compared with other approaches, DeepReduce outperforms the random approach. From the table, find that when using the same termination criteria, the random approach performs much worse than ReepReduce as it requires much more testing data in order to obtain a representative reduction result. Notice that the amount of selected data obtained by the random approach ranges from 2,536 (25.4%) to 4,903 (49.0%), with an average of 3,291 (32.9%). That is, DeepReduce outperforms the random approach 8.0X on average size, while providing similar performance estimations.
In order to compare the state-of-the-art approach with our approach, we implement BOT, by using the same termination criteria as the one used in DeepReduce. From the table, we can find that both DeepReduce and BOT, perform well in input reduction. We also find that when using the same termination criteria, BOT,, selects 11.8% more testing data compared with DeepReduce. In extreme cases, BOT, selects 44.6% more testing data for LeNet5. In summary, considering the amount of the selected data, approach outperforms BOT, on five models except VGG19.
Note that BOT, is a random sampling approach with a carefully designed strategy, and tends to perform differently in different executions. Thus, it is not sure whether BOT, can achieve the average performance in practice every time it is used. As an example, we show more results on NIN further illustrate the instability of BOT, On NIN, the test accuracy achieved by the data selected by BOT, ranges from 0.7925 to 0.88, and the number of selected data instances ranges from 525 605. In comparison, DeepReduce is more stable than BOT, it does sampling. Furthermore, BOT, only considers output distribution in reducing testing data, and does not guarantee testing adequacy for testing DL models. In contrast, our approach ensures testing adequacy by selecting data that can cover all neurons covered by the whole testing data. Thus, we believe that DeepReduce is more practical than BOT, as it is more stable and reliable.
random
To sum up, DeepReduce can obtain accurate estimation of the performance of DL models using less testing data. Furthermore, outperforms the random approach and more practical than BOT,

---

Under review as a conference paper at ICLR 2020
4.3.2 RESULTS FOR RQ2
We investigate the performance of our approach under different values of parameters (i.e., B and a). We set a in the termination criteria to 0.05, 0.01, 0.005, and 0.001, and / in the coverage criteria to 0.25, 0.5, and 0.75. We present the results on CIFAR-10 in Table 3 and the results on MNIST are available online (DeepReduce) 2019). Note that our approach is a two-phase reduction algorithm, therefore we also present the number of selected data instances in the first phase (by using HGS) in Column "HGS"" it is interesting to known how much testing data is needed for achieving the same testing adequacy as the whole testing data does.
Subjects
Coverage
JGS
Kl.
KL.
0,005
KL. D.I01
Apc
Sire
Ace
SI9
Acc
Ste
Ase
Sare
NIN
NC0.25
13
0.7002
196
0.8380
358
0.8597
506
0.3633
1
(0.8815)
NC0L
9.6955
0.8011
357
1334
NC0.75
186
0.7764
245
0.8136
381
0,8356
517
0.8033
1436
(0.9346)
VGG19
NC0.25
NC0.5
NC0.5
635
108
24
0.8808
0.5032
0.833
1218
125
0.9279
0.9329
0.8896
2070
313
0.9312
0,9582
0.9035
2425
437
0.340)
09183
3440
1115
1300
ResNer
NC0.25
8
0.7967
305
0.8710
589
0,8835
824
015058
2059
(0.9220)
NCUS
0.7922
308
0.8639
2071
0.7832
285
Table 3: Experiment results using different parameters on CIFAR-10
The results show that only a small number of data instances is required in order to achieve the same coverage as the whole testing data achieves, under different coverage criteria and termination criteria. The results also show that, at the first phase of our approach (HGS), more data is required when a higher 3 used. This is reasonable as the neuron coverage harder to achieve under a higher activation threshold. The approximation of output distribution at the second phase selects more data instance than HGS. That is, testing adequacy can be achieved by selecting a smaller amount of data, while more data are needed in order achieve the similar output distribution. In terms of test accuracy, in most cases, the results achieved when setting /3 to different values are similar when the same is used in the termination criteria. When the termination criterion gets stricter, the accuracy becomes higher. In our experiments, we set a = 0,005 and 3 = 0.5 as default settings.
4.3.3 RESULTS FOR RQ3
In order to evaluate our reduction approach in regression scenarios, we apply seven changes to the studied DL models, re-train the modified models, and then test them using the data selected by DeepReduce (as described in RQI). Table shows the average testing results on the NIN model. The whole results are available online (DeepReduce) 2019). In the table, "Actual" presents the actual accuracy achieved by the whole testing data, "D "DeepReduce" presents the accuracy achieved by the testing data selected by DeepReduce, and "A" presents the difference between the two. The experiment results show that DeepReduce performs well in estimating the performance of DL. models even when they are modified. The average of ranges from 0.0307 to 0.0424, indicating that the difference between the estimated and actual test accuracy small.
Modifications
Model
Metrics
Structural Changes DEL
SonnSSructural Changes
ADL
ADN
DEN
LR
MO
DR
Actual
0.8816
0.8734
0.8857
0.8808
0.8480
0.8700
0.8819
NIN
DeepReduze
0.8490
0.8391
0.8545
0.8447
0.8056
0,8393
0.8434
0.0313
0.0360
0.0424
0.0307
0.0385
Table 4: Effectiveness of our approach in regression scenarios
CONCLUSION
In this paper, we propose DeepReduce, a software engineering approach for cost-effective testing of DL models. Our approach can accurately estimate the performance of a DL model using a small subset of testing data, by considering three different objectives: efficiency, completeness, and ef- fectiveness. We have evaluated DeepReduce on six DL models and two datasets. On average, DeepReduce can reduce the whole testing data 4.6%. The results confirm that the proposed ap- proach can significantly reduce DL testing cost by reducing the amount of testing data required for testing DI. model.
8

---

Under review as a conference paper at ICLR 2020
The implementations of DeepReduce and the data used in experiments available at: http://gghhbbboooo///reeeeccccet
REFERENCES
Efrati Amir. Uber finds deadly accident likely caused by software set to ignore objects on road. The information, 2018.
Alfredo Canziani, Adam Paszke, and Eugenio Culurciello. An analysis of deep neural network models for practical applications. arXiv preprint arXiv:/605.00678, 2016.
DeepReduce. DeepReduce. http://gghhhnnnooooeeeeeeeeeeeee 2019.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Domain adaptation for large-scale sentiment classification: deep learning approach. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 513-520, 2011.
Mary Jean Harrold, Rajiv Gupta, and Mary Lou Soffa. A methodology for controlling the size of test suite. ACM Trans. Softw. Eng. Methodol., 2(3):770-285. 285, 1993. doi: (1114///15338112339999
URL https: /ttttss:/doi..eo httg:/..11145/1111 11012228881111999 152391
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descrip- tions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 31 1138-3137, 2015.
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques Adaptive Computation and Machine Learning. 2009.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. online: http://www. toronto. edukriz/cifar html, 55, 2014.
S. Kullback and R. A. Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22(1):79-86, 1951.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (6(11)):278-23333 1998.
Zenan Li, Xiaoxing Ma, Chang Xu, Chun Cao, Jingwei Xu, and Jian Lü. Boosting operational DNN testing efficiency through conditioning. In Marlon Dumas, Dietmar Pfahl, Sven Apel, and Alessandra Russo (eds.), Proceedings of the ACM Joint Meeting on European Software Engineer-
ing Conference and Symposium on the Foundations of Software Engineering, ESEC/SIGSOFT FSE 2019, Tallinn, Estonia, August 26-30, 2019., pp. 499 509. ACM, 2019. ISBN 978- 1-5033- 5572-8. doi: 10. 00.1145/33890063338899 33:330
/tt.::///ol..orr/001111/55///// URL https: /ttp::::///oooooooo wttp:/00.......0.0000....00000.. http://1111111313888113
Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400. 2013.
Lei Ma, Felix Juefei-Xu, Fuyuan Zhang, Jiyuan Sun, Minhui Xue, Bo Li, Chunyang Chen, Ting Su, Li Li, Yang Liu, Jianjun Zhao, and Yadong Wang. Deepgauge: multi multti-ranuularity testing criteria for deep learning systems. In Marianne Huchard, Christian Kästner, and Gordon Fraser (eds.), Proceedings of the 33rd ACM/IEEE International Conference on Automated Software En- gineering, ASE 2018, Montpellier, France, September 3-7, 2018 pp. 120-131, ACM, 2018. doi: 00.1145/3238144.32380222
httpstt:: doi.
Lin Ning, Hui Guan, and Xipeng Shen. Adaptive deep reuse: Accelerating training the fly. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1538-1549. IEEE, 2019.

---

Under review as a conference paper at ICLR 2020
Kexin Pei, Yinzhi Cao, Junfeng Yang. and Suman Jana. Deepxplore: Automated whitebox testing of deep learning systems. In Proceedings of the 26th Symposium on Operating Systems Principles, doi: 10.1145/1133747.3332755.
Shanghai, China, October 28 31, 2017, pp. 1-18. ACM, 2017.
URL wttphttp: //dpss://oo.. org/ 10. 11 45 32747. 3132785
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Fei- Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vi- sion, 115())211-2522 Dec 2015. ISSN 1573-1405. doi: https://doo /oi. org/ /10.
URL.
015 -15-0666------166- 0816-y
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.1553 2014.
Youcheng Sun, Xiaowei Huang, Daniel Kroening, James Sharp, Matthew Hill, and Rob Ashmore. Structural test coverage criteria for deep neural networks. In Proceedings of the 4/ International Conference on Software Engineering: Companion Proceedings, pp. 320-321. IEEE Press, 2019.
Y. Taigman, M. Yang, M. Ranzato, and L. Wolf. Deepface: Closing the gap to human-level perfor- mance in face verification. In 2014 IEEE Conference on Computer Vision and Pattern Recogni- lion, pp. 1701-1708, June 2014. doi: 10. 1119///VR.2014.220.
Sebastian Thrun. Is learning the n-th thing any easier than learning the first? In Advances in neural information processing systems, pp. 640-646, 1996.
Yuchi Tian, Kexin Pei, Suman Jana, and Baishakhi Ray. Deeptest: Automated testing of deep- neural-networkk-diive autonomous cars. In Proceedings of the 40th international conference on software engineering, pp. 303-3144 ACM, 2018.
Shin Yoo and Mark Harman. Regression testing minimization, selection and prioritization: a survey. Softw. Test., Verif. Reliab., 22(2):67-120, 2012. doi: 10.1002/stv.40. URL nattps://doi:
org /0gg/10.10 100110022200 stv. 430
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? In Advances in neural information processing systems, pp. 3320-3328, 2014.
Mengshi Zhang, Yuqun Zhang, Lingming Zhang, Cong Liu, and Sarfraz Khurshid. Deeproad: Gan- based metamorphic testing and input validation framework for autonomous driving systems. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineer- ing, pp. 132-142, ACM, 2018
10


Reviews:
[{"review_id": "HkxAIib0Fr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 work tries to build a sub-pile of the test data to save the testing time with minimum effect on the test adequacy and the output distribution. In this paper, the work is done by adding a test-sample search algorithm on top of the HGS algorithm to balance the output distribution.\n\nHowever, the novelty of the proposed work is limited, and there is no evidence to show the proposed algorithms can be applied to other related works. Furthermore, the result does not present a strong success: the error of output distribution is much worse than the compared work.\n\nOther comments to the proposed manuscript are:\n\n1. In Definition 1 the authors declare that the goal is to satisfy f(T,M)=f(T’M) and g(T,M)=g(T’M), and then in the following paragraphs they change it to f(T,M)≈f(T’M) and g(T,M)≈g(T’M) with no justification. More explanation is needed.\n\n2. In Table 2, the authors try to compare the output distribution. To better demonstrate the change between raw testing set and proposed subset, I think that it could be better to present the metrics of distribution or the accuracy of each class instead.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HkgaYdV6Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "The paper develops methods to reduce the test data size while maintaining the coverage and the effectiveness on large test data. The paper proposes  a two-phase reduction approach to select representative samples based on heuristics. Extensive experiments have shown the proposed methods can reduce 95% test samples while still obtaining similar measurements. \n\nThe paper targets a very important problem in practice. Effectively selecting small, representative test sets can save many computational resources and greatly accelerate the research and development. Although the developed technique is quite simple, they are meaningful in practice. Overall, the work can be much improved if a theoretical framework is proposed. \n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bylyz7Jstr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The paper presents a new approach to create subsets of the testing examples that are representative of the entire test set so that the model can be tested quickly during the training and leaving the check on the full test set only at the end to validate its validity.\n\nThe key idea is to create the smaller possible subset with the same or similar coverage (in the paper the neurons coverage is considered) and output distribution, maintaining the difference below a (small) threshold.\n\nIn particular, the output distribution is approximated by dividing the output range of each neuron into K intervals. In this way, an estimate of the output distribution is considered during the extraction of the representative subset of the testing data.\n\nThe whole process is divided into two phases, the first is to create a first subset using HGS, the second refines this subset in order to achieve the desired precision in the output distribution.\n\nThe paper also presents a good experimental campaign that shows good performances.\n\nThe paper is really well written and enjoyable, clear in its description and in the objectives it aims to achieve. To improve the readability a bit further, I would suggest trying to move equation 1 after or close to its reference, or at least to describe before it what KL is.\nMoreover, a similar problem is present for TI, which is introduced in Algorithm 1 and described later. I would add, for example in the input section of the algorithm, a sentence stating that TI is used in getCandidate and described later.\n\nThe first sentence on page 5 seems to be incomplete as it is written. I would suggest rephrasing the sentence.\n\nIn Algorithm 2, about the two \"for\" cycles for i in 1,m and foreach k in 2,K, I suggest unifying them and use the same cycle (only for reasons of readability). Moreover, I think that using braces instead of parentheses would be more correct in these cycles.\n\nIt is interesting to note that in the first line for VGG19, last column of Table 3, the accuracy is lower with KL < 0.001 than with KL < 0.005. I would expect monotonicity here. Do the authors have any idea of the reasons for this?\n\nFinally, it would be interesting to know the runtime to obtain the subsets of the test data of Table 2 required by the considered systems.\n\nTypos:\nOn page 6, penultimate paragraph, the word \"the\" is repeated twice in the parentheses.\nOn page 8, at the beginning of the first sentence after Table 3, there is a comma that seems to be useless after the word \"that\".\nOn page 8, \"When the termination crite gets stricter\", crite should be corrected in criterion.\nThere is a typo in the README of the github project linked in the paper: \"coveraeg data\" instead of \"coverage data\".", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method which creates a representative subset of testing examples so that the model can be tested quickly during the training. The procedure makes use of the famous HGS selection algorithm which identifies and then eliminates the redundant and obsolete test cases based on two criteria: (1) structural coverage as measured by the number of neurons activated beyond a certain threshold, and (2) distribution mismatch (as measured by KL divergence) of the last layer activations. The algorithm has two-phases: (1) a greedy subset selection based on the coverage, and (2) an iterative phase were additional test examples are added until the KL divergence (as defined above) falls below some threshold. 
This approach is incremental in nature -- the resulting multi-objective optimisation problem is not a significant improvement over BOT. After the discussion phase, we believe that the advantages over BOT were not clearly demonstrated and that the main drawback of BOT (requiring the number of samples) is not hindering practical applications. Finally, the empirical evaluation is performed on very small data sets and I do not see an efficient way to apply it to larger data sets where this reduction could be significant. Hence, I will recommend the rejection of this paper. To merit acceptance to ICLR the authors need to provide a cleaner presentation (especially of the algorithms), with a focus on the incremental improvements over BOT, an empirical analysis on larger datasets, and a detailed look into the computational aspects of the proposed approach.

Decision: Reject