# Confidence intervals for performance estimates in 3D medical image
segmentation

Rosana El Jurdi, Gaël Varoquaux and Olivier Colliot  The research leading to
these results has received funding from the French government under management
of Agence Nationale de la Recherche as part of the “Investissements d’avenir”
program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute) and reference
ANR-10-IAHU-0006 (Agence Nationale de la Recherche-10-IA Institut Hospitalo-
Universitaire-6)”. Rosana El Jurdi and Olivier Colliot are with Sorbonne
Université, Institut du Cerveau – Paris Brain Institute - ICM, CNRS, Inria,
Inserm, AP-HP, Hôpital de la Pitié-Salpêtrière, F-75013, Paris, France.Gaël
Varoquaux is with the Soda team, Inria, Saclay, France. Corresponding author:
Rosana El Jurdi (eljurdi.rosana@gmail.com).

###### Abstract

Medical segmentation models are evaluated empirically. As such an evaluation
is based on a limited set of example images, it is unavoidably noisy. Beyond a
mean performance measure, reporting confidence intervals is thus crucial.
However, this is rarely done in medical image segmentation. The width of the
confidence interval depends on the test set size and on the spread of the
performance measure (its standard-deviation across of the test set). For
classification, many test images are needed to avoid wide confidence
intervals. Segmentation, however, has not been studied, and it differs by the
amount of information brought by a given test image. In this paper, we study
the typical confidence intervals in medical image segmentation. We carry
experiments on 3D image segmentation using the standard nnU-net framework, two
datasets from the Medical Decathlon challenge and two performance measures:
the Dice accuracy and the Hausdorff distance. We show that the parametric
confidence intervals are reasonable approximations of the bootstrap estimates
for varying test set sizes and spread of the performance metric. Importantly,
we show that the test size needed to achieve a given precision is often much
lower than for classification tasks. Typically, a 1% wide confidence interval
requires about 100-200 test samples when the spread is low (standard-deviation
around 3%). More difficult segmentation tasks may lead to higher spreads and
require over 1000 samples.

###### Index Terms:

Segmentation, Performance measure, Validation, Statistical analysis,
Confidence interval, Standard error.

##  I Introduction

Solid evaluation is crucial for automatic tools used to process medical
images, as medical professionals must trust the automated system’s output.
Most modern segmentation tools rely on deep learning [1], and their
performance depends on details of the training run. Trained models are
evaluated by using unseen data to estimate their expected performance.
Evaluation is harder than it seems. First, it requires an adequate choice of
metric [2, 3, 4]. Second, it is inevitably noisy, if only because it uses a
finite number of samples. It is thus crucial to quantify the uncertainty on an
estimated performance, for instance using confidence intervals111Here we use
confidence interval in its broader meaning; in terms of strict statistical
definitions, this encompasses the notion of credible intervals. (CIs). Indeed,
model developers can easily fall into the trap of apparent model improvements
due to evaluation noise, that do not generalize to new data, as in some
medical-imaging competitions [5, 6].

And yet, evaluation uncertainty or CIs are seldom reported in the medical
image segmentation literature (including in our own previous papers, e.g. [7,
8, 9]). To illustrate how prevalent the problem is, we conducted a survey of
all papers on 3D medical image segmentation published in 2022 in the following
three journals: IEEE Transactions on Medical Imaging, Medical Image Analysis
and Journal of Medical Imaging. As reported in Table I, only 11 of the
corresponding 133 paper reported CIs. Such quick survey, in no way exhaustive,
does suggest that, across three representative journals of the community, the
vast majority ($>90\%$) of recent papers do not report confidence intervals
for their trained models.

Two main factors affect the precision of model evaluation: the size of the
test set, and how much the performance metric varies across test-set samples.
Given a high spread of the metric across the test set, the precision will be
low and the confidence interval will be wider. Alternatively, increasing the
sample size of the test set leads to tighter confidence intervals. In 3D
medical image segmentation, the size of the set used to evaluate the
performance is often of small to moderate size, typically in the order of
dozens of subjects, at best hundreds, as obtaining the ground truth requires
voxel-wise annotation by trained raters. One fear is thus that most
segmentation performances assessments will be associated to large error bars.
For image classification, studies have shown that large sample sizes are
needed for a precise estimation of the prediction accuracy (typically 10,000
samples to achieve a $1\%$-wide confidence interval) [10, 11]. Surprisingly,
this question has not yet been addressed for medical image segmentation.

This paper addresses the following questions. What precision can be expected
in 3D medical image segmentation for typical test set sizes? How trustworthy
are the average performance estimates (for instance Dice coefficients or
Hausdorff distance) reported in medical image segmentation papers? The main
objectives are: i) to raise awareness on the importance of reporting
confidence interval on independent test sets; ii) to provide the community
with typical values of CI that can be expected for various sample sizes and
performance variability.

To this end, we present in this paper a series of experiments that deploy nnU-
net [12] –a standard framework for medical image segmentation– on two
classical segmentation tasks from the Segmentation Decathlon Challenge [13] in
order to estimate confidence intervals that are obtained for test sets of
variable size. For each task, we study the following performance measures: the
Dice accuracy and the Hausdorff distance. We then report CIs using both
bootstrap (which is the most general approach) and a parametric estimation,
and varying the test set size. We find that the parametric estimation is in
general reasonable, even for small test sets and for metrics which
distribution is far from being Gaussian. Building on this, we perform
simulations for other sizes and spreads. We demonstrate that the test size
needed to achieve a given precision is lower for segmentation than for
classification. This is due to the continuous nature of the evaluation metrics
[14]. Indeed, segmentation algorithms are evaluated with continuous metrics
that aggregate multiple observations at the level of a single image. As each
image brings more information to characterize the errors of the algorithm,
tight confidence intervals can often be obtained with a moderate number of
images.

The remaining sections of this paper are organized as follows. In section II,
we describe the statistical tools that we use in this paper to conduct our
analysis. In section III, we present the datasets examined and the
experimental setup. Section IV reports results on the whole test sets. In
Section V, we then experimentally study how the precision varies when varying
the test set size. In Section VI, we provide a table of confidence intervals
when varying the test set sizes and the performance spread (as measured by
$\sigma$). Finally, we discuss our findings and conclude in sections VII and
VIII

Journal | Nb papers | Nb exp. | Nb (%) papers
---|---|---|---
|  |  | reporting CI (or SEM)
TMI | 51 | 107 | 3 (6%)
MedIA | 70 | 171 | 7 (10%)
JMI | 12 | 22 | 1 (8%)
Total | 133 | 300 | 11 (8%)
TABLE I: Papers reporting precision of segmentation-performance estimates.
Summary of the survey conducted on papers tackling 3D medical image
segmentation via machine/deep learning published in 2022 in the journals IEEE
Transactions on Medical Imaging (IEEE TMI), Medical Image Analysis (MedIA) and
Journal of Medical Imaging (JMI). We report the number of papers and
experiments and the number and proportion of papers that reported the
precision of their estimates (we counted both papers reporting confidence
intervals (CI) and those reporting standard error of the mean (SEM), since it
is very often possible to derive a reasonable estimate of CI from SEM).

##  II Computing Confidence Intervals

In this paper, we are interested in computing confidence intervals for the
mean of a given performance metric (e.g. Dice, Hausdorff). We will consider
$95\%$ confidence intervals, which are the most common, but everything could
be done similarly for other confidence levels.

A general way to compute confidence intervals is through the bootstrap [15,
16]. It has the advantage that it does not make any assumption on the
distribution of the metric nor on the sampling distribution of the mean. Let
us briefly remind the corresponding procedure. Given a test set of size $n$,
$M$ bootstrap samples of size $n$ are drawn with replacement from the test
set. Each bootstrap sample is denoted as $S^{*}_{m}$ where
$m\in\\{1,\ldots,M\\}$. In our experiments, we use $M=15000$. We denote
$\mu_{m}^{*}$222Throughout the paper, the bootstrap estimate of a given $x$ is
always denoted as $x^{*}$ the mean of $S^{*}_{m}$. The $95\%$ confidence
interval $[a^{*},b^{*}]$ is the set of values between the $2.5\%$ and $97.5\%$
percentiles of the sorted bootstrap means
$\\{\mu_{1}^{*},\mu_{2}^{*},\ldots,\mu_{m}^{*},\ldots,\mu_{M}^{*}\\}$. The
standard error of the mean $\mu^{*}$ obtained via bootstrapping
($\text{SEM}^{*}$) is the standard deviation of the means of all bootstrap
samples:
$\text{SEM}^{*}=\sqrt{\frac{1}{M}\sum_{m=1}^{M}{\left(\mu_{m}^{*}-\mu^{*}\right)^{2}}}$
where $\mu^{*}$ is the mean of the bootstrap sample means $\mu_{m}^{*}$.

While the bootstrap is easy to perform, it must be performed by the researcher
evaluating the model, since it requires to have the performance value for each
subject of the test set. Knowing typical confidence intervals to expect given
a test size can help evaluating the precision of a result reported without
bootstrap. To build such charts, we perform simulations to gauge the following
classical approximation:

$\displaystyle\begin{split}&\text{SEM}=\frac{\sigma}{\sqrt{n}}\\\
&[a,b]=[\mu-1.96\times\text{SEM},\mu+1.96\times\text{SEM}]\end{split}$ (1)

where $\mu$ and $\sigma$ respectively denote the mean and standard deviation
of the metric over the test set, $n$ the test set size, SEM the standard error
of the mean and $a$ (resp. $b$) are the lower (resp. upper) bounds of the 95%
confidence interval. This approximation relies on the assumption that the
sampling distribution of the mean follows a normal distribution. It holds
asymptotically with only weak assumptions on the metric distribution (finite
expected value and variance) and thus should be valid for sufficiently large
samples. However, in practice, it is unknown under which test size this
approximation is reasonable. This will be assessed through the experiments in
the paper. If the metric distribution is close to normal, the approximation is
more likely to be correct even for relatively small samples (the sampling
distribution of the mean would thus follow a Student’s distribution which
becomes quickly close to a normal distribution when $n$ increases). In the
following, we will refer to estimations derived from Equations 1 as parametric
estimations to distinguish them from bootstrap estimations.

Finally, we derive the following quantities from the confidence intervals.
First, we are not interested in the absolute values of the boundaries of the
confidence interval. Thus, we report confidence intervals independently of the
mean, as follows:

$\text{CI}=[a-\mu,b-\mu]$ (2)

and we also define the width of CI as $w=b-a$. When the parametric estimation
is used, $w=2\times 1.96\times\text{SEM}$. Moreover, different performance
measures have different ranges of values (for instance Dice is between $0\%$
and $100\%$ while the Hausdorff distance can be arbitrarily large). For the
reader to have a better intuition of the precision of the estimate, we thus
normalize the width by the mean value of the metric. To this end, we define
the normalized width:

Normalized width $\displaystyle\nu=\frac{w}{\mu}$ (3)

where $\mu$ is the average performance metric mean across the test set. In the
case of bootstrap estimation, the above quantities are denoted as
$\text{CI}^{*}$, $w^{*}$ and $\nu^{*}$.

##  III Datasets and Segmentation Method

###  III-A Datasets

We used the Hippocampus and Brain Tumor datasets from the Medical Decathlon
challenge [13]. The Hippocampus dataset is mono-modal and composed of 260 3D
T1-weighted (T1-w) MPRAGE brain images. The task is to segment the anterior
and posterior parts of the hippocampus (denoted respectively as L1 and L2
according to the challenge annotations). The Brain Tumor dataset is a multi-
modal dataset comprising T1w preconstrast, T1w postcontrast, fluid-attenuated
inversion recovery (FLAIR), and T2-weighted images. It is composed of 484
samples and dedicated to glioma segmentation. The regions to segment are the
edema (L1), the non-enhancing tumor (L2), and the enhancing tumor (L3),
according to the Decathlon annotations. The data contains a subset of the data
used in the 2016 and 2017 Brain Tumor Segmentation (BraTS) challenges [17].
The brain tumor task is considered difficult (best Dice is around $70\%$)
while the Hippocampus is easier in comparison (best Dice around $90\%$).

From the 260 and 484 samples of the Hippocampus and Brain Tumor dataset
respectively, 100 patients were randomly selected for training, 50 for
validation and the remaining samples constituted the test set. The size of the
training and validation subsets were the same for both datasets to ensure that
the number of training samples has no impact on the model performances.

###  III-B Segmentation Methods

We used the Decathlon Challenge winner’s nnU-net, as a framework to perform
our experiments. nnU-net [12] is a fully automated segmentation framework that
makes use of typical 2D and 3D U-Net architectures by dynamically and
automatically adapting the hyper-parameters to a particular dataset. Given an
arbitrary dataset, the nnU-net pipeline first extracts data fingerprints (e.g.
voxel spacing, intensity distribution, modalities, class ratios etc.). Pre-
processing of the datasets is conducted automatically via cropping to non-zero
volumes to reduce the computational burden, resampling relative to voxel
spacing to allow spatial semantics, and z-score normalization, if need be. We
allowed nnU-Net to automatically determine the best configuration of
parameters. In nnU-net, one can either predetermine which architecture to
train on the given dataset or allow nnU-net to choose the best configuration.
In the present paper, we conducted our experiments using the 3D full-
resolution U-Net and the 2D U-Net. It is possible that even better
performances could have been obtained using the cascade approach or letting
nnU-net choose the best approach. However, the aim of the present paper is not
achieve the highest possible performance but to obtain a set of results which
are representative of the state-of-the-art. All networks are trained via a
combined Dice and cross-entropy loss and the Adam optimizer. Further
information concerning model parameters and the training scheme can be found
in [12].

###  III-C Performance Metrics and Setup

We have conducted our study for two common performance metrics: the Dice
similarity coefficient computed for each class separately and the $95\%$
Hausdorff distance111Performance metrics were computed using this code:
https://github.com/deepmind/surface-distance. For sake of conciseness, we only
reported results for the first region of each task (L1). In the Hippocampus
dataset, it is the anterior part. In the Brain Tumor dataset, it corresponds
to the edema. Note nevertheless that the training was done simultaneously on
all regions. The full code in Python and Jupyter notebooks to reproduce our
experiments are available on GitHub222
https://github.com/rosanajurdi/SegVal.git

(a)

(b)

(c)

(d)

Figure 1: Histogram of Dice accuracy over the entire test set, shown together
with a kernel density estimation (KDE) which smoothes the observations with a
Gaussian kernel. (a) Hippocampus dataset, 3D U-Net. (b) Hippocampus dataset,
2D U-Net. (c) Brain Tumor dataset, 3D U-Net. (d) Brain Tumor dataset, 2D
U-Net.

(a)

(b)

(c)

(d)

Figure 2: Histogram of 95% Hausdorff distance over the entire test set, shown together with a kernel density estimation (KDE) which smoothes the observations with a Gaussian kernel. (a) Hippocampus dataset, 3D U-Net. (b) Hippocampus dataset, 2D U-Net. (c) Brain Tumor dataset, 3D U-Net. (d) Brain Tumor dataset, 2D U-Net. |  |  | Parametric | Bootstrap
---|---|---|---|---
|  |  | $\mu$ | $\sigma$ | $SEM$ | $CI$ | $\nu$ | $\mu^{*}$ | $SEM^{*}$ | $CI^{*}$ | $\nu^{*}$
Hippocampus | 3D U-Net | Dice | 89.714 | 2.797 | 0.267 | [-0.52, 0.52] | 0.012 | 89.715 | 0.263 | [-0.53, 0.51] | 0.012
95 % HD | 1.205 | 0.472 | 0.045 | [-0.08, 0.08] | 0.149 | 1.205 | 0.045 | [-0.08, 0.09] | 0.149
($n=110$) | 2D U-Net | Dice | 88.197 | 3.267 | 0.311 | [-0.61, 0.61] | 0.014 | 88.199 | 0.313 | [-0.64, 0.59] | 0.014
95% HD | 1.311 | 0.806 | 0.077 | [-0.15, 0.15] | 0.229 | 1.31 | 0.077 | [-0.13, 0.17] | 0.229
Brain Tumor | 3D U-Net | Dice | 80.265 | 11.947 | 0.654 | [-1.28, 1.28] | 0.032 | 80.268 | 0.659 | [-1.31, 1.24] | 0.032
95 % HD | 7.726 | 10.634 | 0.582 | [-1.14, 1.14] | 0.294 | 7.73 | 0.581 | [-1.08, 1.18] | 0.294
($n=334$) | 2D U-Net | Dice | $77.489$ | $13.115$ | $0.718$ | [-1.41, 1.41] | 0.036 | $77.488$ | $0.717$ | [-1.43, 1.38] | 0.036
95 % HD | 8.855 | 11.262 | 0.616 | [-1.21, 1.21] | 0.272 | 8.862 | 0.62 | [-1.22, 1.22] | 0.272
TABLE II: Results on the full test set ($n=110$ for Hippocampus and $n=334$
for Brain Tumor) for region $L_{1}$. $\mu$ and $\sigma$ are the empirical mean
and standard deviation of the Dice accuracy (Dice) and 95 % volumetric
Hausdorff distance (HD) across all patients in the test set. $SEM$ is the
standard error of the mean, $CI$ is the $95\%$ confidence interval independent
of the mean calculated using the parametric estimation, $\nu$ is the
normalized CI. $\mu^{*}$, $SEM^{*}$, $CI^{*}$ and $\nu^{*}$ are the bootstrap
estimates.

##  IV Experimental Study on the Whole Test Sets

In this section, we study the precision of the performance evaluation using
the full test sets (test set sizes are 110 for the Hippocampus and 334 for the
Brain Tumor, respectively).

The distribution of Dice accuracy and Hausdorff distance values over the test
set are shown in Figure 1. One can observe that the Dice accuracy’s
distribution is not very far from Gaussian despite outliers and skewness in
the histogram plots. It is not the case for the Hausdorff distance (Figure 2).
First, this measure is lower-bounded by one and a lot of values lie to one,
which makes the distribution highly skewed. Also, due to the discrete nature
of the images, some values will never occur hence histograms are sparse.

We then compute, for both metrics and for both 2D and 3D networks, the test
sample mean $\mu$, the test sample standard deviation $\sigma$, SEM, CI and
$\nu$. The computations are done as described in Section II, using both
parametric and bootstrap estimations. Results are reported in Table II. One
can see that, under such test set sizes, the computations using parametric
estimation are close to those obtained with the bootstrap, even for the
Hausdorff distance. This indicates that it is a reasonable approximation under
this size regime. In the next section, we will study if this still holds for
smaller test set sizes.

##  V Experimental Study on Sub-samples of the Test Sets

In this section, we study experimentally the relationship between the test set
size and the precision of the estimation of the segmentation performance. To
that end, we draw subsamples of variable size

$k\in K=\\{10,20,30,50,100,\ldots,n\\}$

where $n$ is the whole test set size. For the Hippocampus dataset $n=110$ and
$K=\\{10,20,30,50,100,110\\}$ and for the Brain Tumor dataset, $n=334$ and
$K=\\{10,20,30,50,100,200,300,334\\}$.

For small subsamples, the estimates can vary substantially from one drawing to
another. In order not to depend on a particular drawing, which may be lucky or
unlucky, we repeat the procedure 100 times for each value of $k$. We denote
the subsamples as $(S_{k,j})$ where $k$ is the subsample size and
$j\in\\{1,\ldots,100\\}$ is the index of a particular drawing. We then compute
the precision measures (SEM, CI, $\nu$ and bootstrap counterparts) for the
subsamples of different sizes. The exact formulas for the estimation of the
different measures are detailed in appendix -A.

$\sigma\downarrow$ | $k\rightarrow$ | 10 | 20 | 30 | 50 | 100 | 200 | 300 | 500 | 1000 | 1500 | 2000 | 2500 | 3000
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0.47 | $SEM$ | 0.15 | 0.11 | 0.09 | 0.07 | 0.05 | 0.03 | 0.03 | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
$CI$ | [-0.29, 0.29] | [-0.21, 0.21] | [-0.17, 0.17] | [-0.13, 0.13] | [-0.09, 0.09] | [-0.07, 0.07] | [-0.05, 0.05] | [-0.04, 0.04] | [-0.03, 0.03] | [-0.02, 0.02] | [-0.02, 0.02] | [-0.02, 0.02] | [-0.02, 0.02]
0.81 | $SEM$ | 0.26 | 0.18 | 0.15 | 0.11 | 0.08 | 0.06 | 0.05 | 0.04 | 0.03 | 0.02 | 0.02 | 0.02 | 0.01
$CI$ | [-0.5, 0.5] | [-0.35, 0.35] | [-0.29, 0.29] | [-0.22, 0.22] | [-0.16, 0.16] | [-0.11, 0.11] | [-0.09, 0.09] | [-0.07, 0.07] | [-0.05, 0.05] | [-0.04, 0.04] | [-0.04, 0.04] | [-0.03, 0.03] | [-0.03, 0.03]
1 | $SEM$ | 0.32 | 0.22 | 0.18 | 0.14 | 0.1 | 0.07 | 0.06 | 0.04 | 0.03 | 0.03 | 0.02 | 0.02 | 0.02
$CI$ | [-0.62, 0.62] | [-0.44, 0.44] | [-0.36, 0.36] | [-0.28, 0.28] | [-0.2, 0.2] | [-0.14, 0.14] | [-0.11, 0.11] | [-0.09, 0.09] | [-0.06, 0.06] | [-0.05, 0.05] | [-0.04, 0.04] | [-0.04, 0.04] | [-0.04, 0.04]
2.79 | $SEM$ | 0.88 | 0.62 | 0.51 | 0.39 | 0.28 | 0.2 | 0.16 | 0.12 | 0.09 | 0.07 | 0.06 | 0.06 | 0.05
$CI$ | [-1.73, 1.73] | [-1.22, 1.22] | [-1.0, 1.0] | [-0.77, 0.77] | [-0.55, 0.55] | [-0.39, 0.39] | [-0.32, 0.32] | [-0.24, 0.24] | [-0.17, 0.17] | [-0.14, 0.14] | [-0.12, 0.12] | [-0.11, 0.11] | [-0.1, 0.1]
3.26 | $SEM$ | 1.03 | 0.73 | 0.6 | 0.46 | 0.33 | 0.23 | 0.19 | 0.15 | 0.1 | 0.08 | 0.07 | 0.07 | 0.06
$CI$ | [-2.02, 2.02] | [-1.43, 1.43] | [-1.17, 1.17] | [-0.9, 0.9] | [-0.64, 0.64] | [-0.45, 0.45] | [-0.37, 0.37] | [-0.29, 0.29] | [-0.2, 0.2] | [-0.16, 0.16] | [-0.14, 0.14] | [-0.13, 0.13] | [-0.12, 0.12]
5 | $SEM$ | 1.58 | 1.12 | 0.91 | 0.71 | 0.5 | 0.35 | 0.29 | 0.22 | 0.16 | 0.13 | 0.11 | 0.1 | 0.09
$CI$ | [-3.1, 3.1] | [-2.19, 2.19] | [-1.79, 1.79] | [-1.39, 1.39] | [-0.98, 0.98] | [-0.69, 0.69] | [-0.57, 0.57] | [-0.44, 0.44] | [-0.31, 0.31] | [-0.25, 0.25] | [-0.22, 0.22] | [-0.2, 0.2] | [-0.18, 0.18]
10.63 | $SEM$ | 3.36 | 2.38 | 1.94 | 1.5 | 1.06 | 0.75 | 0.61 | 0.48 | 0.34 | 0.27 | 0.24 | 0.21 | 0.19
$CI$ | [-6.59, 6.59] | [-4.66, 4.66] | [-3.8, 3.8] | [-2.95, 2.95] | [-2.08, 2.08] | [-1.47, 1.47] | [-1.2, 1.2] | [-0.93, 0.93] | [-0.66, 0.66] | [-0.54, 0.54] | [-0.47, 0.47] | [-0.42, 0.42] | [-0.38, 0.38]
11.26 | $SEM$ | 3.56 | 2.52 | 2.06 | 1.59 | 1.13 | 0.8 | 0.65 | 0.5 | 0.36 | 0.29 | 0.25 | 0.23 | 0.21
$CI$ | [-6.98, 6.98] | [-4.93, 4.93] | [-4.03, 4.03] | [-3.12, 3.12] | [-2.21, 2.21] | [-1.56, 1.56] | [-1.27, 1.27] | [-0.99, 0.99] | [-0.7, 0.7] | [-0.57, 0.57] | [-0.49, 0.49] | [-0.44, 0.44] | [-0.4, 0.4]
12 | $SEM$ | 3.79 | 2.68 | 2.19 | 1.7 | 1.2 | 0.85 | 0.69 | 0.54 | 0.38 | 0.31 | 0.27 | 0.24 | 0.22
$CI$ | [-7.44, 7.44] | [-5.26, 5.26] | [-4.29, 4.29] | [-3.33, 3.33] | [-2.35, 2.35] | [-1.66, 1.66] | [-1.36, 1.36] | [-1.05, 1.05] | [-0.74, 0.74] | [-0.61, 0.61] | [-0.53, 0.53] | [-0.47, 0.47] | [-0.43, 0.43]
13.12 | $SEM$ | 4.15 | 2.94 | 2.4 | 1.86 | 1.31 | 0.93 | 0.76 | 0.59 | 0.41 | 0.34 | 0.29 | 0.26 | 0.24
$CI$ | [-8.13, 8.13] | [-5.75, 5.75] | [-4.69, 4.69] | [-3.64, 3.64] | [-2.57, 2.57] | [-1.82, 1.82] | [-1.48, 1.48] | [-1.15, 1.15] | [-0.81, 0.81] | [-0.66, 0.66] | [-0.58, 0.58] | [-0.51, 0.51] | [-0.47, 0.47]
20 | $SEM$ | 6.32 | 4.47 | 3.65 | 2.83 | 2.0 | 1.41 | 1.15 | 0.89 | 0.63 | 0.52 | 0.45 | 0.4 | 0.37
$CI$ | [-12.4, 12.4] | [-8.77, 8.77] | [-7.16, 7.16] | [-5.54, 5.54] | [-3.92, 3.92] | [-2.77, 2.77] | [-2.26, 2.26] | [-1.75, 1.75] | [-1.24, 1.24] | [-1.01, 1.01] | [-0.88, 0.88] | [-0.78, 0.78] | [-0.72, 0.72]
30 | $SEM$ | 9.49 | 6.71 | 5.48 | 4.24 | 3.0 | 2.12 | 1.73 | 1.34 | 0.95 | 0.77 | 0.67 | 0.6 | 0.55
$CI$ | [-18.59, 18.59] | [-13.15, 13.15] | [-10.74, 10.74] | [-8.32, 8.32] | [-5.88, 5.88] | [-4.16, 4.16] | [-3.39, 3.39] | [-2.63, 2.63] | [-1.86, 1.86] | [-1.52, 1.52] | [-1.31, 1.31] | [-1.18, 1.18] | [-1.07, 1.07]
50 | $SEM$ | 15.81 | 11.18 | 9.13 | 7.07 | 5.0 | 3.54 | 2.89 | 2.24 | 1.58 | 1.29 | 1.12 | 1.0 | 0.91
$CI$ | [-30.99, 30.99] | [-21.91, 21.91] | [-17.89, 17.89] | [-13.86, 13.86] | [-9.8, 9.8] | [-6.93, 6.93] | [-5.66, 5.66] | [-4.38, 4.38] | [-3.1, 3.1] | [-2.53, 2.53] | [-2.19, 2.19] | [-1.96, 1.96] | [-1.79, 1.79]

TABLE III: Table of SEM and confidence intervals $CI$ for different sizes $k$
of the test set and for different values of $\sigma$ including the
experimental values obtained in Table II.

###  V-A Dice Accuracy Performance Measure

Results for the Dice accuracy for different sample sizes $k$ are reported in
Figure 3 (details in Tables IV, V, VI and VII). As expected, as the sample
size decreases, the estimates become less precise (the standard error
increases, the confidence interval widens). Moreover, the confidence intervals
obtained via parametric estimation are very close, though slightly below, to
the ones obtained via bootstrapping. Overall, since the CI obtained via the
parametric estimates are slightly narrower than that of the bootstap values,
one can assume that the parametric estimates could serve as a lower bound to
the test set size needed to insure a particular precision. Finally, one can
observe that bootstrap confidence intervals are slightly skewed. However, this
skewness rapidly fades away as the test set sample size $k$ decreases.

Figure 3: Parametric and boostrap CIs: Dice accuracy (detailed results in
Tables IV, V, VI, VII)

Figure 4: Parametric and boostrap CIs: Hausdorff Distance (detailed results in
Tables VIII, IX, X, XI)

###  V-B Hausdorff Distance Performance Measure

Results for the Hausdorff distance metric are reported in Figure 3 (details in
Tables VIII, IX, XI and X). Even though we saw that the Hausdorff distance is
far from being Gaussian distributed, it is interesting to note that obtained
parametric estimates are actually close to bootstrap ones. It thus seems
reasonable to assume that parametric estimates can, as in the case of the Dice
accuracy, be used to derive a lower bound on the minimal test set size needed
to achieve a given precision.

Inspecting the normalized width $\nu$ (reported in appendix -B) shows that it
is much larger for the Hausdorff distance than for the Dice accuracy for the
same model and the same dataset. This indicates that more test samples are
required to achieve a particular precision. Possible explanations include the
discontinuity of the Hausdorff distance and the fact that it corresponds to a
maximum rather than an average.

##  VI A table of Gaussian confidence intervals

The previous section shows that parametric estimates match well bootstrap
confidence intervals. Confidence intervals can be useful even before running
an experiment, to give a lower bound for the dataset size needed to achieve a
given precision. To facilitate the use of confidence intervals, Table III list
them for different values of test set size $k$ and $\sigma$ (which reflects
how variable is the performance across test samples), computed via Equations
1. Some values of $\sigma$ match those experimentally measured in our
experiences in Table II (0.47, 0.81, 2.79, 3.26, 10.63, 11.26, 13.12). We
recall that the value of $\mu$, in itself, has no impact on the width of the
confidence interval nor on the SEM –even though it is usually observed that
lower performing models, thus associated with a lower value of $\mu$, also
have a more variable performance and thus a larger value of $\sigma$.

##  VII Discussion

We have studied the precision with which segmentation performance can be
estimated in typical medical imaging studies. We provided typical values for
confidence intervals of the performance of trained models. Such values can be
useful to authors and reviewers, _e.g._ to roughly estimate confidence
intervals that can be expected for a given study. Finally, we have shown that,
under typical performance spreads, the sample size needed to achieve a given
confidence interval is smaller than for classification tasks. To that purpose,
we have conducted an extensive set of experiments using both parametric and
bootstrap estimates. Results show that parametric estimates give reasonable
results even when the performance metric substantially deviates from a
Gaussian distribution.

#### Confidence intervals cannot be computed post-hoc

The width of the confidence interval depends on two factors: the size of the
test set ($n$) and the variability of the performance ($\sigma$). In
classification, a binomial distribution gives parametric confidence intervals
–though slightly conservative [10, 11]. Confidence intervals can be computed
post-hoc as a function of the accuracy, _e.g._ when reading a manuscript. This
is not the case in image segmentation: for a given metric, $\sigma$ is highly
task dependent and not directly linked to the performance (in practice, lower
performing models are often associated to higher standard deviations). Hence,
$\sigma$ must be computed during model evaluation, and studies should report
confidence intervals and potentially $\sigma$.

#### A table for confidence intervals

As parametric estimates give reasonable results, one can compute typical
confidence intervals for given $n$ and $\sigma$ and we provide this
information in Table III. These values can be useful to researchers preparing
a segmentation study, to help them choose the size of the test set.
Investigators must then make an hypothesis on the expected value of $\sigma$
(as when doing a power analysis), for example using previously published
studies on similar segmentation tasks (given that these report $\sigma$). The
values can also be useful to reviewers who can use these to gauge plausible
confidence intervals, should these not be reported in the paper. Again, if
$\sigma$ is not reported in the paper, one will need to make an hypothesis on
its expected value.

#### Test-set size for statistical control

Classification tasks need large test-set sizes for tight confidence intervals
(though higher-performing models lead to less uncertainty). Typically, for
classification a 1%-wide confidence interval requires about $10\,000$ samples
for models with over 90% accuracy [11].

Our results show that the typical test size needed for a given confidence
interval is smaller for segmentation than for classification. This is good
news as it is arguably more difficult to obtain a large test set in the case
of segmentation as it requires voxel-wise annotation by a trained rater.
However, smaller does not mean small. When dispersion is low ($\sigma\leq 3$
for Dice accuracy), hundreds of samples may suffice for tight confidence
intervals (e.g. 1%-wide). When the dispersion is larger (for example
$\sigma\approx 15$), as often for more difficult tasks, a $1\%$-wide
confidence interval may require more than 1 000 test samples. More relaxed
confidence intervals (_e.g._ $4\%$-wide) may still require about 200 test
samples.

Figure 5: Histogram of the test-set size of different experiments from
segmentation papers published in JMI, TMI, and MedIA in 2022. The red line
represents the median test size ($n=25$).

#### A call for larger test sets

Are the practices of medical-imaging studies in line with such test set sizes?
As mentioned in the introduction, we surveyed papers published in 2022 in
three medical imaging journals: IEEE Transactions on Medical Imaging (IEEE
TMI), Medical Image Analysis (MedIA), and SPIE’s Journal of Medical Imaging
(JMI) dealing with segmentation of 3D images. This survey, though not
exhaustive, sheds light on current practices in recent medical-imaging papers.
Figure 5 shows that the test set size is in general small and highly variable
across studies (median, 25; minimum: 1; maximum: 1543). Thus, with the
exception of a few studies, there is a need to increase the size of test sets
to obtain reasonably precise estimates of the performance.

#### Reporting confidence intervals is important

Trustworthy evidence on segmentation tools is important for their clinical
adoption. Confidence intervals and bootstrapping are classic statistical
practice; and yet medical image segmentation papers seldom report confidence
intervals: we found them in only 10% of papers of our survey (Table I). Beyond
immediate clinical adoption, controlled statistical evidence is a component of
reproducibility, needed for scientific progress [18, 19]. Statistical
reproducibility is suited to reason on generalization to unseen data: results
need to be statistically compatible rather than identical. Reporting
confidence intervals is central to asserting statistical reproducibility of
studies. Awareness about this issue has risen, as can been seen for example in
reproducibility checklists (e.g. MICCAI
2021333https://miccai2021.org/files/downloads/MICCAI2021-Reproducibility-
Checklist.pdf). However, the fact that confidence intervals are so rarely
reported in recent papers indicates yet more awareness is needed.

Reporting confidence intervals enables progress at the level of the community.
To disseminate a trained model (for use by clinical researchers,
neuroscientists …), the users should understand expected variances in the
performance of the model. Confidence intervals also enable comparing
performance to inter-rater (or intra-rater) variability. When computing inter-
rater variability on the test set used to evaluate the trained model, one can
obtain confidence intervals for the trained model and for the inter-rater and
check if they overlap.

#### Recommendations

We recommend that authors systematically report confidence intervals for
trained models. Even though we showed that parametric approximations can yield
reasonable estimates, we recommend to use the bootstrap method as it makes
much fewer assumptions and is easy to perform since it only requires to
resample performance metrics obtained on the test set (without recomputing
them). Finally, confidence intervals should be complemented by displaying the
distribution of the performance metrics (e.g. as a violin plot or a box plot)
on the test set and reporting its standard deviation.

#### More work to benchmark learning procedures

We investigated the sampling noise in the test set, the only source of
variance when evaluating a trained model. However evaluating a learning
procedure –as when comparing two methods– comes with other sources of variance
such as hyperparameters or random seeds [20, 11]. Methods to build confidence
intervals for learning procedures typically involve running multiple trainings
with different data splits (to account for sampling noise in training and
testing sets) but also different hyperparameters or random seeds [20, 11].
They require much more computing power and lead to wider confidence intervals.

#### Limitations

While we studied the two most widely used performance metrics, there are many
other metrics, some being more appropriate for certain settings [3]. Also, due
to space constraints, we only studied two datasets. We have chosen them to
include both a relatively easy and a more difficult segmentation task.
However, conducting similar experiments on other datasets would be ground for
more general conclusions.

##  VIII Conclusion

Confidence intervals are needed to characterize the uncertainty on the
performance of image-segmentation tools. We have shown that simple parametric
estimates can serve as a reasonable reference to guide researchers on the test
set size needed for a target precision. Importantly, results show that the
test set size needed to achieve a given precision is lower for segmentation
than for classification tasks. Confidence intervals can be computed easily; we
hope that they will be used more in image-segmentation studies.

## References

  * [1] M. H. Hesamian, W. Jia, X. He, and P. Kennedy, “Deep learning techniques for medical image segmentation: achievements and challenges,” _Journal of digital imaging_ , vol. 32, pp. 582–596, 2019.
  * [2] A. Reinke, E. Christodoulou, B. Glocker, P. Scholz, F. Isensee, and et al, “Metrics reloaded - a new recommendation framework for biomedical image analysis validation,” in _Medical Imaging with Deep Learning_ , 2022. [Online]. Available: https://openreview.net/forum?id=24kBqy8rcB_
  * [3] L. Maier-Hein, A. Reinke, P. Godau, M. D. Tizabi, E. Christodoulou, B. Glocker, and et al, “Metrics reloaded: Pitfalls and recommendations for image analysis validation,” _arXiv preprint_ , vol. arXiv:2206.01653, 2022. [Online]. Available: https://arxiv.org/abs/2206.01653
  * [4] A. Reinke, M. D. Tizabi, M. Baumgartner, M. Eisenmann, D. Heckmann-Nötzel, A. E. Kavu, T. Rädsch, C. H. Sudre, L. Acion, M. Antonelli _et al._ , “Understanding metric-related pitfalls in image analysis validation,” _arXiv preprint arXiv:2302.01790_ , 2023. [Online]. Available: https://arxiv.org/abs/2302.01790
  * [5] L. Maier-Hein, M. Eisenmann, A. Reinke, S. Onogur, M. Stankovic, P. Scholz, T. Arbel, H. Bogunovic, A. P. Bradley, A. Carass _et al._ , “Why rankings of biomedical image analysis competitions should be interpreted with care,” _Nature communications_ , vol. 9, no. 1, p. 5217, 2018.
  * [6] G. Varoquaux and V. Cheplygina, “Machine learning for medical imaging: methodological failures and recommendations for the future,” _NPJ digital medicine_ , vol. 5, no. 1, p. 48, 2022.
  * [7] M. Chupin, E. Gérardin, R. Cuingnet, C. Boutet, L. Lemieux, S. Lehéricy, H. Benali, L. Garnero, and O. Colliot, “Fully automatic hippocampus segmentation and classification in Alzheimer’s disease and mild cognitive impairment applied on data from ADNI,” _Hippocampus_ , vol. 19, no. 6, pp. 579–587, 2009.
  * [8] T. Samaille, L. Fillon, R. Cuingnet, E. Jouvent, H. Chabriat, D. Dormont, O. Colliot, and M. Chupin, “Contrast-based fully automatic segmentation of white matter hyperintensities: method and validation,” _PLoS one_ , vol. 7, no. 11, p. e48953, 2012.
  * [9] R. El Jurdi, C. Petitjean, P. Honeine, V. Cheplygina, and F. Abdallah, “A surprisingly effective perimeter-based loss for medical image segmentation,” in _Medical Imaging with Deep Learning_ , 2021, pp. 158–167.
  * [10] G. Varoquaux, “Cross-validation failure: Small sample sizes lead to large error bars,” _NeuroImage_ , vol. 180, pp. 68–77, 2018.
  * [11] G. Varoquaux and O. Colliot, “Evaluating machine learning models and their diagnostic value,” _HAL preprint_ , vol. hal-03682454, 2022. [Online]. Available: https://hal.archives-ouvertes.fr/hal-03682454
  * [12] F. Isensee, P. F. Jaeger, S. A. A. Kohl, J. Petersen, and K. H. Maier-Hein, “nnU-Net: a self-configuring method for deep learning-based biomedical image segmentation,” _Nature Methods_ , vol. 18, no. 2, pp. 203–211, Feb 2021.
  * [13] M. Antonelli, A. Reinke, S. Bakas, K. Farahani, A. Kopp-Schneider, B. A. Landman, G. Litjens, B. Menze, O. Ronneberger _et al._ , “The medical segmentation decathlon,” _Nature Communications_ , vol. 13, no. 1, p. 4128, 2022.
  * [14] D. G. Altman and P. Royston, “The cost of dichotomising continuous variables,” _BMJ_ , vol. 332, no. 7549, p. 1080, May 2006.
  * [15] B. Efron and R. J. Tibshirani, _An introduction to the bootstrap_. CRC press, 1993.
  * [16] R. W. Platt, J. A. Hanley, and H. Yang, “Bootstrap confidence intervals for the sensitivity of a quantitative diagnostic test,” _Statistics in medicine_ , vol. 19, no. 3, pp. 313–322, 2000.
  * [17] B. H. Menze, A. Jakab, S. Bauer, J. Kalpathy-Cramer, K. Farahani, and et al, “The multimodal Brain Tumor Image Segmentation benchmark (BRATS),” _IEEE Transactions on Medical Imaging_ , vol. 34, no. 10, pp. 1993–2024, 2015\.
  * [18] M. McDermott, S. Wang, N. Marinsek, R. Ranganath, M. Ghassemi, and L. Foschini, “Reproducibility in machine learning for health,” _arXiv preprint arXiv:1907.01463_ , 2019.
  * [19] O. Colliot, E. Thibeau-Sutre, and N. Burgos, “Reproducibility in machine learning for medical imaging,” _arXiv preprint arXiv:2209.05097_ , 2022.
  * [20] X. Bouthillier, P. Delaunay, M. Bronzi, A. Trofimov, B. Nichyporuk, J. Szeto, N. Mohammadi Sepahvand, E. Raff, K. Madan, V. Voleti _et al._ , “Accounting for variance in machine learning benchmarks,” _Proceedings of Machine Learning and Systems_ , vol. 3, pp. 747–769, 2021.

###  -A Details on the estimated measures on subsamples of the test sets

#### Parametric estimates

For the parametric estimation, we denote as

$\mu_{k,j}=\frac{1}{k}\sum_{l=1}^{k}P_{j,k,l},\quad\sigma_{k,j}=\sqrt{\frac{1}{k}\sum_{l=1}^{k}{\left(P_{j,k,l}-\mu_{k,j}\right)^{2}}}$

the empirical mean and standard deviation for the subsample $S_{k,j}$ where
$P_{j,k,l}$ is the performance metric (in our case either Dice accuracy or
Hausdorff distance) of a given subject in the sub-sample $S_{k,j}$. Similarly,
we use the notations

$\text{SEM}_{k,j}=\frac{\sigma_{k,j}}{\sqrt{k}},\quad\nu_{k,j}=\frac{2*1.96*\text{SEM}_{k,j}}{\mu_{k,j}}.$

We then compute the average of $\mu_{k,j}$, $\sigma_{k,j}$,
$\text{SEM}_{k,j}$, $\nu_{k,j}$ across the different subsamples $S_{k,j}$ for
$k$ fixed and $j\in\\{1,\ldots,100\\}$. This provides the following estimates
$\mu_{k}$, $\sigma_{k}$, $\text{SEM}_{k}$ and $\nu_{k}$. Similarly, we define
$\text{CI}_{k}=[-1.96\times\text{SEM}_{k},1.96\times\text{SEM}_{k}]$.

#### Bootstrap estimates

Bootstrap estimations are performed as follows. For a given subsample
$S_{k,j}$ of size $k$ and index $j$, $M=15\,000$ bootstrap samples of size $k$
are drawn with replacement. We denote a given bootstrap sample as
$S^{*}_{k,j,m}$ and its mean as $\mu^{*}_{k,j,m}$ where $m\in\\{1,\ldots,M\\}$
is the index of the $m^{th}$ bootstrap sample of subsample $S_{k,j}$. The
bootstrap mean $\mu^{*}_{k,j}$ of $S_{k,j}$ is the mean of the bootstrap
sample means $\mu^{*}_{k,j,m}$:

$\mu^{*}_{k,j}=\frac{1}{M}\sum_{m=1}\mu^{*}_{k,j,m}$

The standard error of the mean $\mu^{*}_{k,j}$ (denoted as
$\text{SEM}^{*}_{k,j}$) obtained via bootstrapping is the standard deviation
of the means of all bootstrap samples of subsample $S_{k,j}$:

$\text{SEM}^{*}_{k,j}=\sqrt{\frac{1}{M}\sum_{m=1}^{M}{\left(\mu^{*}_{k,j,m}-\mu^{*}_{k,j}\right)^{2}}}.$

The $95\%$ confidence interval of the sample $S_{k,j}$ is denoted as
$[a^{*}_{k,j},b^{*}_{k,j}]$ and is the set of values between the $2.5\%$ and
$97.5\%$ percentile of the sorted bootstrap means of subsample $S_{k,j}$. We
then compute the average of $\mu^{*}_{k,j}$, and $\text{SEM}^{*}_{k,j}$ across
the different subsamples $S_{k,j}$ for $k$ fixed and $j\in\\{1,...,100\\}$ and
denote the results as $\mu^{*}_{k}$ and $\text{SEM}^{*}_{k}$. For the
confidence intervals, we compute the average values
$a^{*}_{k}=\frac{1}{100}\sum_{j=1}^{100}{a^{*}_{k,j}}$ and
$b^{*}_{k}=\frac{1}{100}\sum_{j=1}^{100}{b^{*}_{k,j}}$ to obtain the average
confidence interval independent of the mean
$\text{CI}^{*}_{k}=[a^{*}_{k}-\mu^{*}_{k},b^{*}_{k}-\mu^{*}_{k}]$. We finally
compute the normalized width of the confidence interval as:
$\nu^{*}_{k}=\frac{b^{*}_{k}-a^{*}_{k}}{\mu^{*}_{k}}$.

###  -B Detailed results on subsamples of the test sets

Detailed results on subsamples of the test set, which were summarized in
Figures 3 and 4, are presented in Tables IV, V, VI, VII, VIII, IX, X and XI.

| Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $89.751$ | $2.578$ | $0.815$ | [-1.6, 1.6] | 0.036 | $89.752$ | $0.815$ | $[-1.647,1.525]$ | 0.035
20 | $89.723$ | $2.666$ | $0.596$ | [-1.17, 1.17] | 0.026 | $89.724$ | $0.597$ | $[-1.204,1.128]$ | 0.026
30 | $89.681$ | $2.785$ | $0.508$ | [-0.995, 0.995] | 0.022 | $89.682$ | $0.508$ | $[-1.023,0.968]$ | 0.022
50 | $89.768$ | $2.707$ | $0.383$ | [-0.75, 0.75] | 0.017 | $89.768$ | $0.383$ | $[-0.766,0.734]$ | 0.017
100 | $89.721$ | $2.788$ | $0.279$ | [-0.545, 0.545] | 0.012 | $89.721$ | $0.279$ | $[-0.557,0.536]$ | 0.012
110 | $89.714$ | $2.784$ | $0.265$ | [-0.52, 0.52] | 0.012 | $89.714$ | $0.266$ | $[-0.529,0.512]$ | 0.012
TABLE IV: Hippocampus dataset, 3D U-net, Dice accuracy. Results on sub-samples of size $k\leq 110$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $88.334$ | $2.759$ | $0.872$ | [-1.71, 1.71] | 0.039 | $88.335$ | $0.872$ | $[-1.78,1.608]$ | 0.038
20 | $88.189$ | $3.082$ | $0.689$ | [-1.35, 1.35] | 0.031 | $88.19$ | $0.689$ | $[-1.425,1.263]$ | 0.030
30 | $88.126$ | $3.281$ | $0.599$ | [-1.175, 1.175] | 0.027 | $88.126$ | $0.599$ | $[-1.24,1.102]$ | 0.027
50 | $88.254$ | $3.12$ | $0.441$ | [-0.865, 0.865] | 0.020 | $88.255$ | $0.441$ | $[-0.905,0.822]$ | 0.020
100 | $88.212$ | $3.261$ | $0.326$ | [-0.64, 0.64] | 0.015 | $88.212$ | $0.326$ | $[-0.664,0.612]$ | 0.014
110 | $88.197$ | $3.252$ | $0.31$ | [-0.61, 0.61] | 0.014 | $88.197$ | $0.31$ | $[-0.631,0.584]$ | 0.014
TABLE V: Hippocampus dataset, 2D U-net, Dice Accuracy. Results on subsamples of size $k\leq 110$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $80.457$ | $10.612$ | $3.356$ | [-6.58, 6.58] | 0.164 | $80.461$ | $3.356$ | $[-7.051,5.853]$ | 0.160
20 | $80.188$ | $11.281$ | $2.522$ | [-4.945, 4.945] | 0.123 | $80.189$ | $2.523$ | $[-5.28,4.541]$ | 0.122
30 | $79.925$ | $11.839$ | $2.162$ | [-4.235, 4.235] | 0.106 | $79.924$ | $2.162$ | $[-4.512,3.925]$ | 0.106
50 | $80.375$ | $11.593$ | $1.64$ | [-3.215, 3.215] | 0.080 | $80.374$ | $1.639$ | $[-3.384,3.015]$ | 0.080
100 | $80.388$ | $11.389$ | $1.139$ | [-2.23, 2.23] | 0.055 | $80.388$ | $1.139$ | $[-2.321,2.137]$ | 0.055
150 | $80.329$ | $11.788$ | $0.962$ | [-1.885, 1.885] | 0.047 | $80.328$ | $0.963$ | $[-1.954,1.817]$ | 0.047
200 | $80.253$ | $11.936$ | $0.844$ | [-1.655, 1.655] | 0.041 | $80.252$ | $0.844$ | $[-1.709,1.601]$ | 0.041
250 | $80.295$ | $11.919$ | $0.754$ | [-1.475, 1.475] | 0.037 | $80.296$ | $0.754$ | $[-1.521,1.431]$ | 0.037
300 | $80.28$ | $11.924$ | $0.688$ | [-1.35, 1.35] | 0.034 | $80.281$ | $0.688$ | $[-1.386,1.311]$ | 0.034
334 | $80.265$ | $11.929$ | $0.653$ | [-1.28, 1.28] | 0.032 | $80.264$ | $0.653$ | $[-1.313,1.245]$ | 0.032
TABLE VI: Brain Tumor dataset, 3D U-net, Dice Accuracy. Results on subsamples of size $k\leq 334$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $77.811$ | $11.799$ | $3.731$ | [-7.315, 7.315] | 0.188 | $77.815$ | $3.731$ | $[-7.856,6.566]$ | 0.185
20 | $77.334$ | $12.631$ | $2.824$ | [-5.535, 5.535] | 0.143 | $77.334$ | $2.825$ | $[-5.879,5.137]$ | 0.142
30 | $77.101$ | $13.084$ | $2.389$ | [-4.68, 4.68] | 0.121 | $77.101$ | $2.389$ | $[-4.94,4.389]$ | 0.121
50 | $77.607$ | $12.897$ | $1.824$ | [-3.575, 3.575] | 0.092 | $77.606$ | $1.823$ | $[-3.736,3.39]$ | 0.092
100 | $77.564$ | $12.797$ | $1.28$ | [-2.51, 2.51] | 0.065 | $77.564$ | $1.279$ | $[-2.588,2.42]$ | 0.065
150 | $77.583$ | $13.01$ | $1.062$ | [-2.08, 2.08] | 0.054 | $77.582$ | $1.063$ | $[-2.139,2.023]$ | 0.054
200 | $77.468$ | $13.182$ | $0.932$ | [-1.825, 1.825] | 0.047 | $77.467$ | $0.932$ | $[-1.871,1.778]$ | 0.047
250 | $77.549$ | $13.056$ | $0.826$ | [-1.62, 1.62] | 0.042 | $77.549$ | $0.826$ | $[-1.654,1.582]$ | 0.042
300 | $77.501$ | $13.104$ | $0.757$ | [-1.485, 1.485] | 0.038 | $77.502$ | $0.756$ | $[-1.511,1.448]$ | 0.038
334 | $77.489$ | $13.115$ | $0.718$ | [-1.405, 1.405] | 0.036 | $77.488$ | $0.717$ | $[-1.43,1.376]$ | 0.036
TABLE VII: Brain Tumor dataset, 2D U-net, Dice Accuracy. Results on subsamples of size $k\leq 334$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $1.214$ | $0.416$ | $0.132$ | [-0.26, 0.26] | 0.428 | $1.214$ | $0.131$ | $[-0.205,0.286]$ | 0.404
20 | $1.206$ | $0.435$ | $0.097$ | [-0.19, 0.19] | 0.315 | $1.206$ | $0.097$ | $[-0.165,0.21]$ | 0.310
30 | $1.221$ | $0.468$ | $0.086$ | [-0.17, 0.17] | 0.278 | $1.22$ | $0.086$ | $[-0.149,0.183]$ | 0.271
50 | $1.203$ | $0.46$ | $0.065$ | [-0.125, 0.125] | 0.208 | $1.203$ | $0.065$ | $[-0.116,0.137]$ | 0.211
100 | $1.205$ | $0.47$ | $0.047$ | [-0.09, 0.09] | 0.149 | $1.205$ | $0.047$ | $[-0.086,0.097]$ | 0.152
110 | $1.205$ | $0.47$ | $0.045$ | [-0.09, 0.09] | 0.149 | $1.205$ | $0.045$ | $[-0.08,0.09]$ | 0.149
TABLE VIII: Hippocampus dataset, 3D U-net, Hausdorff Distance. Results on sub-samples of size $k\leq 110$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $1.296$ | $0.538$ | $0.17$ | [-0.335, 0.335] | 0.517 | $1.296$ | $0.17$ | $[-0.267,0.367]$ | 0.490
20 | $1.302$ | $0.599$ | $0.134$ | [-0.265, 0.265] | 0.407 | $1.302$ | $0.134$ | $[-0.219,0.289]$ | 0.391
30 | $1.331$ | $0.718$ | $0.131$ | [-0.255, 0.255] | 0.383 | $1.331$ | $0.131$ | $[-0.211,0.288]$ | 0.375
50 | $1.31$ | $0.729$ | $0.103$ | [-0.2, 0.2] | 0.305 | $1.31$ | $0.103$ | $[-0.168,0.228]$ | 0.303
100 | $1.31$ | $0.793$ | $0.079$ | [-0.155, 0.155] | 0.237 | $1.31$ | $0.079$ | $[-0.133,0.175]$ | 0.234
110 | $1.311$ | $0.803$ | $0.077$ | [-0.15, 0.15] | 0.229 | $1.311$ | $0.077$ | $[-0.13,0.17]$ | 0.229
TABLE IX: Hippocampus dataset, 2D U-net, Hausdorff Distance. Results on subsamples of size $k\leq 110$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $8.171$ | $8.806$ | $2.785$ | [-5.46, 5.46] | 1.336 | $8.168$ | $2.784$ | $[-4.278,6.046]$ | 1.264
20 | $7.635$ | $9.098$ | $2.034$ | [-3.985, 3.985] | 1.044 | $7.634$ | $2.034$ | $[-3.268,4.459]$ | 1.012
30 | $7.95$ | $9.782$ | $1.786$ | [-3.5, 3.5] | 0.881 | $7.95$ | $1.787$ | $[-2.98,3.909]$ | 0.866
50 | $7.563$ | $9.791$ | $1.385$ | [-2.715, 2.715] | 0.718 | $7.563$ | $1.383$ | $[-2.36,3.002]$ | 0.709
100 | $7.702$ | $10.468$ | $1.047$ | [-2.05, 2.05] | 0.532 | $7.702$ | $1.046$ | $[-1.848,2.228]$ | 0.529
150 | $7.691$ | $10.339$ | $0.844$ | [-1.655, 1.655] | 0.430 | $7.693$ | $0.844$ | $[-1.522,1.775]$ | 0.428
200 | $7.698$ | $10.413$ | $0.736$ | [-1.445, 1.445] | 0.375 | $7.697$ | $0.736$ | $[-1.341,1.535]$ | 0.374
250 | $7.758$ | $10.663$ | $0.674$ | [-1.32, 1.32] | 0.340 | $7.757$ | $0.674$ | $[-1.238,1.397]$ | 0.340
300 | $7.695$ | $10.513$ | $0.607$ | [-1.19, 1.19] | 0.309 | $7.694$ | $0.607$ | $[-1.12,1.257]$ | 0.309
334 | $7.726$ | $10.618$ | $0.581$ | [-1.14, 1.14] | 0.295 | $7.726$ | $0.581$ | $[-1.076,1.196]$ | 0.294
TABLE X: Brain Tumor dataset, 3D U-net, Hausdorff Distance. Results on subsamples of size $k\leq 334$. We show the mean over all the sub-samples $S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$). | Parametric | Bootstrap
---|---|---
Subsample size $k$ | $\mu_{k}$ | $\sigma_{k}$ | $SEM_{k}$ | $CI_{k}$ | $\nu_{k}$ | $\mu^{*}_{k}$ | $SEM^{*}_{k}$ | $CI^{*}_{k}$ | $\nu^{*}_{k}$
10 | $9.544$ | $10.409$ | $3.292$ | [-6.45, 6.45] | 1.352 | $9.544\pm 3.441$ | $3.294$ | $[-5.099,7.152]$ | 1.284
20 | $8.454$ | $9.178$ | $2.052$ | [-4.02, 4.02] | 0.951 | $8.453\pm 2.302$ | $2.05$ | $[-3.454,4.441]$ | 0.934
30 | $9.204$ | $10.794$ | $1.971$ | [-3.86, 3.86] | 0.839 | $9.205\pm 1.786$ | $1.973$ | $[-3.374,4.269]$ | 0.830
50 | $8.836$ | $10.86$ | $1.536$ | [-3.01, 3.01] | 0.681 | $8.837\pm 1.359$ | $1.537$ | $[-2.696,3.282]$ | 0.676
100 | $8.758$ | $10.966$ | $1.097$ | [-2.15, 2.15] | 0.491 | $8.756\pm 0.938$ | $1.096$ | $[-1.974,2.307]$ | 0.489
150 | $8.886$ | $11.158$ | $0.911$ | [-1.785, 1.785] | 0.402 | $8.885\pm 0.673$ | $0.912$ | $[-1.671,1.894]$ | 0.401
200 | $8.806$ | $11.068$ | $0.783$ | [-1.535, 1.535] | 0.349 | $8.806\pm 0.471$ | $0.783$ | $[-1.445,1.617]$ | 0.348
250 | $8.873$ | $11.32$ | $0.716$ | [-1.405, 1.405] | 0.317 | $8.873\pm 0.357$ | $0.715$ | $[-1.33,1.469]$ | 0.315
300 | $8.83$ | $11.173$ | $0.645$ | [-1.265, 1.265] | 0.287 | $8.831\pm 0.214$ | $0.645$ | $[-1.204,1.32]$ | 0.286
334 | $8.855$ | $11.245$ | $0.615$ | [-1.205, 1.205] | 0.272 | $8.856$ | $0.615$ | $[-1.154,1.257]$ | 0.272
TABLE XI: Brain Tumor dataset, 2D U-net, Hausdorff Distance. Results on sub-
samples of size $k\leq 334$. We show the mean over all the sub-samples
$S_{k,j}$ of a given size $k$ ($k$ is fixed and $j\in\\{1,\ldots,100\\}$).


# SampleFix: Learning to Correct Programs by Sampling Diverse Fixes

Hossein Hajipour1, Apratim Bhattacharya 2, Mario Fritz1
1CISPA Helmholtz Center for Information Security, Saarland Informatics Campus
2 Max Planck Institute for Informatics, Saarland Informatics Campus
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Automatic program correction is an active topic of research, which holds the
potential of dramatically improving productivity of programmers during the
software development process and correctness of software in general. Recent
advances in machine learning, deep learning and NLP have rekindled the hope to
eventually fully automate the process of repairing programs. A key challenge
is ambiguity, as multiple codes – or fixes – can implement the same
functionality. In addition, datasets by nature fail to capture the variance
introduced by such ambiguities. Therefore, we propose a deep generative model
to automatically correct programming errors by learning a distribution of
potential fixes. Our model is formulated as a deep conditional variational
autoencoder that samples diverse fixes for the given erroneous programs. In
order to account for ambiguity and inherent lack of representative datasets,
we propose a novel regularizer to encourage the model to generate diverse
fixes. Our evaluations on common programming errors show for the first time
the generation of diverse fixes and strong improvements over the state-of-the-
art approaches by fixing up to $65\%$ of the mistakes.

##  1 Introduction

Software development is a time-consuming and expensive process. Unfortunately,
programs written by humans typically come with bugs, so that significant
effort needs to be invested to obtain code that is only likely to be correct.
Debugging is typically performed by humans and therefore tedious and can also
contain mistakes. This is neither desirable nor acceptable in many critical
applications. Therefore, automatically locating and correcting program errors
offers the potential to increase productivity as well as improve correctness
of software.

Advances in machine learning, deep learning (?; ?; ?), computer vision (?; ?)
and NLP (?; ?) has dramatically boosted the machine’s ability to automatically
learn representations of natural data such as images and natural language
contents for various tasks. Deep learning models also have been successful in
learning the distribution over continuous (?; ?) and discrete data (?; ?), to
generate new and diverse data points (?). These advances in machine learning
and the advent of large corpora of source code (?) provide new opportunities
toward harnessing deep learning methods to understand, generate or debug
programs.

Figure 1: An example highlighting inherent ambiguity of possible fixes of
erroneous programs.

There has been an increasing interest to carry over the success stories of
deep learning in NLP and related techniques to employed deep learning-based
approaches to tackle the “common programming errors” problem (?; ?). Such
investigations have included compile-time errors such as missing scope
delimiters, adding extraneous symbols, using incompatible operators as “common
programming errors”. Novice programmers and even experienced developers often
struggled with these type of errors (?), which is usually due to lack of
attention to the details of programs and/or programmer’s inexperience (?).

Recently, ? proposes a deep sequence to sequence model called Deepfix where,
given an erroneous program, the model predicts the locations of the errors and
a potential fix for each predicted location. The problem is formulated as a
one-to-one mapping task, where the model is trained to predict a single fix
for each location with an error. No ambiguity is taken into account. However,
different codes – and therefore also their fixes – can express the same
functionality (Figure 1). The inherent ambiguity argues for a one-to-many
mapping in order to account for ambiguity as well as uncertainty of the model
and limited training data.

Hence, we propose a deep generative framework to automatically correct
programming errors by learning the distribution of potential fixes. At the
core of our approach is a conditional variational autoencoder that is trained
to sample accurate and diverse fixes for the given erroneous programs, and
interacts with a compiler that evaluates the sampled candidate fixes in the
context of the given programs. The interplay of sampler and compiler allows
for an iterative refinement procedure. A key contribution of our approach is a
novel regularizer which encourages diversity by penalizing the distance among
candidate samples, which thereby significantly increases the effectiveness by
producing more diverse samples.

To summarize, the contributions of this paper are as follows,  1. We propose a
generative framework to automatically correct common programming errors by
learning the distribution over potential fixes and interacting with a compiler
in an iterative procedure.  2. We propose a novel regularizer to encourage the
model to generate diverse fixes.  3. Our conditional generative model together
with the diversity regularizer shows an increase in the diversity of samples
and strong improvement over the state-of-the-art approaches on real world
scenarios.

##  2 Related Work

Our work builds on the general idea of sequence to sequence models as well as
ideas from neural machine translation. We phrase our approach as a variational
auto-encoder and compare it to prior work learning-based program repair. We
review the related work in order below

#### Neural Machine Translation.

? introduces neural machine translation and casts it as a sequence to sequence
learning problem. The popular encoder-decoder architecture is introduced to
map the source sentences into target sentences. One the major drawback of this
model is that the sequence encoder needs to compress all of the extracted
information into a fixed length vector. (?) addresses this issue by using
attention mechanism in the encoder-decoder architecture, where it focuses on
the most relevant part of encoded information by learning to search over the
encoded vector. In our work, we employ sequence to sequence model with
attention to parameterize our generative model. This model gets an incorrect
program as input, and maps it to many potential fixes by drawing samples on
estimated distribution of the fixes.

#### Variational Autoencoders.

The variational autoencoder (?; ?) is a generative model designed to learn
deep directed latent variable based graphical models of large datasets. The
model is trained on the data distribution by maximizing the variational lower
bound of the log-likelihood as the objective function. ? extends this
framework by introducing a RNN-based variational autoencoder to enable the
learning of latent variable based generative models on text data. The proposed
model is successful at generating diverse and coherent sentences. To model
conditional distributions for the structured output representation ? extended
variational autoencoders by introducing an objective which maximizes the
conditional data log-likelihood. In our approach, we use an RNN-based
conditional variational autoencoder to model the distribution of the potential
fixes given erroneous programs.

#### Learning-based Program Repair.

Recently there has been a growing interest in using learning-based approaches
to automatically repair the programs (?). ? proposed a probabilistic model by
explicitly designing code features to rank potential fixes for a given
program. ? employ an encoder-decoder neural architecture to automatically
correct programs, where they use beam search to generate candidate programs.
In these works, and many learning-based programming repair approaches,
enumerative search over programs is required to resolve all errors. However,
our proposed framework is capable of predicting the location and potential
fixes by passing the whole program to the model. Besides this, unlike our
approach, which only generates fixes for the given erroneous program, ? need
to predict whole program statements to resolve bugs.

DeepFix (?) and RLAssist (?) uses neural representations to repair syntax
errors in programs. In detail, DeepFix uses a sequence to sequence model to
directly predict a fix for incorrect programs. In contrast, our generative
framework is able to generate and evaluate multiple fixes by learning the
distribution of potential correctness. Therefore, our model does not penalize,
but rather encourages diverse fixes. RLAssist repairs the programs by
employing a reinforcement learning approach. They train an agent which
navigate over the program to locate and resolve the syntax errors. In this
work, they only address the typographic errors, rely on a hand designed action
space and meet problems due to the increasing size of the action space. In
contrast, our method shows improved performance on typographic errors and also
generalizes to issues with missing variable declaration errors.

? use generative adversarial networks to repair software vulnerabilities. They
propose an adversarial approach to map from bad code domain to the correct
code domain in an unsupervised fashion. They propose an unsupervised approach
to repair the programs, however, there is no guarantee that their outputs do
not introduce more errors to the input programs. In contrast, our generative
framework automatically reject the sampled fixes which are introducing more
errors to the input programs by using a compiler during inference time and
directly models the distribution over potential fixes.

##  3 SampleFix: Generative Model for Code Fixes

Repairing the common program errors is a challenging task due to ambiguity in
potential corrections and lack of representative data. Given a single broken
program, there are multiple ways to fix the program. Therefore, alternative
correct solutions – that do not appear in the training set – should not be
penalized during training but rather encouraged. Therefore, we propose a deep
generative framework to automatically repair common programming errors by
learning the distribution of potential fixes – rather than a single fix –
given the broken program. In other words, we model the problem of repairing
programs as a one-to-many problem, where, our model learns the distribution of
potential fixes through a generative model conditioned on the erroneous input
program.

We model the distribution of fixes using a conditional latent variable model,
where the latent variables are learned using pairs of erroneous programs and
the corresponding fixes. As mentioned before, to resolve programming errors,
the generation of diverse fixes is crucial. The main reason is that by nature
programs and their potential fixes are redundant and ambiguous. In addition,
datasets are deprived of the large diversity of potential mistakes that can
occur in programs. Hence, we need to model and encourage diverse samples. In
order to address this issue, we propose a novel regularizer which encourages
the model to generate diverse samples by penalizing the distance among drawn
fixes.

Figure 2 provides an overview of our proposed approach. For a given errorous
program, the generative model draws $T$ candidate fixes $\hat{y}$ ($T=4$ in
Figure 2) from the learned conditional distribution. In order to select one
out of $T$ candidate fixes, we employ an compiler which evaluate the candidate
fixes. The compiler evaluates each fix by compiling the updated program. Out
of $T$ drawn fixes, the compiler selects the fix which resolves the largest
number of error messages. In Figure 2, compiler selects $\hat{y_{2}}$, as the
best fix for the given program. After updating the program, to resolve the
remaining error(s), we follow ? and iteratively input the updated program to
our generative model. In the following, we formulate our generative model
using the Conditional Variational Autoencoder framework and describe in detail
our proposed novel regularizer. Finally, we provide details of our training
and inference process.

Figure 2: Overview of SampleFix at inference time, highlighting the generation
of diverse fixes.

###  3.1 Conditional Variational Autoencoders for Generating Fixes

Conditional Variational Autoencoders (CVAE) (?), model conditional
distributions $p_{\theta}(\textbf{y}|\textbf{x})$ using latent variables z.
The conditioning introduced through z enables the modelling of complex multi-
model distributions. As powerful transformations can be learned using neural
networks, z itself can have a simple distribution which allows for efficient
sampling. This model allows for sampling from
$p_{\theta}(\textbf{y}|\textbf{x})$ given an input sequence x, by first
sampling latent variables $\hat{\textbf{z}}$ from the prior distribution
$p({\textbf{z}})$. During training, amortized variational inference is used
and the latent variables z are learned using a recognition network
$q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})$, parametrized by $\phi$. In
detail, the variational lower bound of the model (Equation 3.1) is maximized,

$\displaystyle\log(p(\textbf{y}|\textbf{x}))\geq\mathbb{E}_{q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})}$
$\displaystyle\log(p_{\theta}(\textbf{y}|\textbf{z},\textbf{x}))$
$\displaystyle-
D_{\text{KL}}({q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})}\mid\mid{p(\textbf{z}|\textbf{x})}).$

Penalizing the divergence of $q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})$ to
the prior in Equation 3.1 allows for sampling from the prior $p({\textbf{z}})$
during inference. In practice, the variational lower bound is estimated using
Monte-Carlo integration,

$\displaystyle\hat{\mathcal{L}}_{\text{CVAE}}=\frac{1}{T}\sum\limits_{\text{i}=1}^{T}$
$\displaystyle\log(p_{\theta}(\textbf{y}|\hat{\textbf{z}}_{\text{i}},\textbf{x}))$
(2) $\displaystyle-
D_{\text{KL}}({q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})},{p(\textbf{z}|\textbf{x})})\enspace{.}$

where, $\hat{\textbf{z}}_{\text{i}}\sim
q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})$, and $T$ is the number of samples.
We cast our generative model for resolving program errors in the Conditional
Variational Autoencoder framework. In our formulation, the input x is the
erroneous program and y is the potential fix. Note that
$\textbf{x},\textbf{y}$ are sequences in our formulation. However, the plain
CVAE as described in (?) suffers from diversity issues. Usually, the drawn
samples do not reflect the true variance of the posterior
$p(\textbf{y}|\textbf{x})$. This would amount to the correct fix potentially
missing from our candidate fixes. To mitigate this problem, next we introduce
a novel objective that aims to enhance the diversity of our candidate fixes.

###  3.2 DS-SampleFix: Encouraging Diversity with a Diversity-sensitive
Regularizer

Casting our model in the Conditional Variational Autoencoder framework would
enable us to sample a set of candidate fixes for a given erroneous program.
However as pointed out in (?), the standard variational lower bound objective
does not encourage diversity in the candidate fixes. This is because the
average likelihood of the candidate fixes is considered. In detail, as the
average likelihood is considered, all candidate fixes must explain the “true”
fix in training set well. This discourages diversity and severely constrains
the recognition network, which is already constrained to maintain a Gaussian
latent variable distribution. In practice, the learned distribution is pushed
to the mean and fails to fully capture the variance of the true distribution.
To encourage diversity, we employ the lower bound proposed by (?) and further
include a novel regularizer. Our novel regularizer further encourages
diversity and does not require a large number of candidate fixes $T$ to be
drawn at training time. In practice, we observe considerable gains even with
the use of only $T=2$ candidate fixes,

$\displaystyle\log(p(\textbf{y}|\textbf{x}))\geq$
$\displaystyle\log\Big{(}\int
p_{\theta}(\textbf{y}|\textbf{z},\textbf{x})q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})\,dz\,\,\Big{)}$
$\displaystyle-
D_{\text{KL}}({q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})}\mid\mid{p(\textbf{z}|\textbf{x})}).$

In comparison to Equation 3.1, this lower bound (Equation 3.2) encourages
diversity in the model by allowing for multiple chances to draw highly likely
candidate fixes. This enables the model to generate diverse candidate fixes,
while maintaining high likelihood. In practice, due to numerical stability
issues, the $\log$-sum-exp on the right of (Equation 3.2) is approximated
using the $\max$ (Equation 4). This approximate objective retains the
diversity enhancing nature of Equation 3.2 while being easy to train,

$\displaystyle\hat{\mathcal{L}}_{\text{BMS}}=\max_{\text{i}}\big{(}$
$\displaystyle\log(p_{\theta}(\textbf{y}|\hat{\textbf{z}}_{\text{i}},\textbf{x}))\big{)}$
(4) $\displaystyle-
D_{\text{KL}}({q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})},{p(\textbf{z}|\textbf{x})})\enspace{.}$

While prior work uses around $T=10$ samples during training, this is
computationally prohibitive especially for large models, as it requires $10$
times the memory or $10$ times the number of forward passes. If $T$ is
decreased, the objective behaves similarly to the standard CVAE objective as
the recognition network has fewer and fewer chances to draw highly likely
samples/candidate fixes, thus limiting diversity. Therefore, in order to
encourage the model to generate diverse fixes even when high values of $T$ are
computationally prohibitive, we propose a novel regularizer which penalizes
the distance of two closest candidate fixes (Equation 3.2), thus forcing the
candidate fixes to be diverse.

$\displaystyle\hat{\mathcal{L}}_{\text{DS-
BMS}}=\max_{\text{i}}\big{(}\log(p_{\theta}(\textbf{y}|\hat{\textbf{z}}_{\text{i}},\textbf{x}))\big{)}+\min_{\text{i},\text{j}}d(\hat{\textbf{y}}^{\text{i}},\hat{\textbf{y}}^{\text{j}})$
$\displaystyle-
D_{\text{KL}}({q_{\phi}(\textbf{z}|\textbf{x},\textbf{y})},{p(\textbf{z}|\textbf{x})})\enspace{.}$

Distance Metric. Here, we discuss the distance metric $d$ in Equation 3.2.
Note, that the samples
$\left\\{\hat{\textbf{y}}^{\text{i}},\hat{\textbf{y}}^{\text{j}}\right\\}$ can
be of different lengths. Therefore, we consider the distance over the maximum
length of the two samples and pad the shorter sample to equalize lengths.
Next, we assume that our predicted distributions are point masses over each
token. Under this assumption, the Euclidean distance is equivalent to the
Wasserstein distance between the distributions. We also experimented with the
commonly used cosine similarity. However, our approach performed better using
the Euclidean (Wasserstein) distance. This is mainly because, in practice,
Euclidean distance is easier to optimize.

###  3.3 Model Architecture and Implementation Details

Figure 3: Overview of network architecture.

To ensure fair comparison, our generative model is based on the popular
sequence to sequence architecture with attention, similar to (?). We employ
LSTMs encoders and decoders. Figure 3 shows the architecture of our model in
detail. Note that the recognition network is available to encode the fixes to
latent variables z only during training. Another LSTM encoder is used to
encode the conditioning input erroneous program x to a code vector v. The
decoder is conditioned on the code vector v and a sample of distribution with
latent variables z.

All of the networks in our framework consists of 4-layers of LSTM cells with
300 units. We apply dropout at rate 0.2 for each of these layers. To process
the program through the networks, we tokenize the programs similar to the
setting which used by ? and process them into 50-dimensional vectors using an
embedding layer. The network is optimized using ADAM optimizer (?) with the
default learning rate and weight decay. We train the network up to 20 epochs
and select the model with best validation performance. For the evaluation and
comparisons we train two models, one for repairing the typographic errors, and
another one for missing variable declaration errors. We use $T=2$ samples to
train our models, and $T=100$ samples during inference time. All of these
experiments are conducted on a Nvidia Tesla P40 with 22GB memory.

During inference, the conditioning erroneous program x is input to the
encoder, which encodes the program to the vector v. To generate multiple fixes
using our decoder, the code vector v along with a sample of z from the prior
$p(\textbf{z})$ is input to the decoder. For simplicity, we use a standard
Gaussian $\mathcal{N}(0,\textbf{I})$ prior, although more complex priors can
be easily leveraged. The decoder is unrolled in time and output logits
($p_{\theta}(\textbf{y}|\hat{\textbf{z}}_{\text{i}},\textbf{x})$). To sample
from these logits we use computationally efficient Gibbs sampling strategy. We
approximate a Gumbel distribution over the predicted logits (?; ?) and predict
each token by sampling over this distribution. We additionally experiment with
a Beam search decoding scheme (?) to further enhance performance.

###  3.4 Iterative Repair

We adopt the iterative repair procedure (?) in the context of our proposed
generative model, where the iterative procedure now leverages multiple
candidate fixes. Given an erroneous program, each of our $T$ candidate fixes
contain a line number and the corresponding fix for that line. To select the
best fix, we take the candidate fixes and the input erroneous program,
reconcile them to create $T$ updated programs. Our oracle which is a compiler
takes these programs and selects a fix out of $T$ candidate fixes which have a
lowest number of error messages. After applying a fix on the input program, we
feed the updated program to the network to resolve the other errors. This
procedure is shown in Figure 2. In order to allow for a fair comparison to the
state-of-the-art methods, we use the same setting for applying iterative
repair strategy as it is described in ?.

##  4 Experiments

We evaluate our approach on the task of repairing common programming errors.
We evaluate the diversity and accuracy of our sampled error corrections as
well as compare our proposed method with the state-of-the-art.

Dataset Details. Unfortunately, the choice of dataset in this domain is still
quite limited. We use the dataset published by ? as it’s sizable and also
includes real-world data for test. It contains programs written in C. The
dataset consists of 93 different tasks which were written by students in an
introductory programming course. The programs were collected using a web-based
tutoring system (?). The collected programs have token lengths in the range
$\left[75,450\right]$, and contain typographic and missing variable
declaration errors. To tokenize the programs and generate training and test
data we follow the procedure which is used by ?, where they tokenized programs
by considering different type of tokens, such as types, keywords, special
characters, functions, literals and variables. Furthermore, the dataset
contains two sets of data which are called synthetic and real-world data. The
synthetic data contains the erroneous program which are synthesized by
mutating correct programs written by students. The real-world data contains
the real-world erroneous programs written by students. In line with prior
work, we use the synthetic data to train and test our model, and use real-
world data to evaluate the performance of our model in repairing the real-
world erroneous programs.

In order to stay comparable with prior work, we follow the same training and
evaluation procedure as in ?. The dataset is divided into 5 cross-validation
folds. In each fold, $\nicefrac{{1}}{{5}}^{th}$ of the programming tasks are
held out as the test set, and the training data is generated by mutating the
correct programs from the remaining $\nicefrac{{4}}{{5}}^{th}$ of the
programming tasks. To generate the training pairs, correct programs are
mutated to introduce the errors. Mutated programs are then paired with the fix
for the first incorrect line, where each fix contains the line number and the
corrected line for that program. We refer the reader to ? for more details
about the dataset.

###  4.1 Evaluation

Table 1: Results of performance comparison of DeepFix, SampleFix and DS-SampleFix on synthetic data. Typo , Miss Dec and All refer to typographic, missing variable declarations, and all of the errors respectively. Models | Typo | Miss Dec | All
---|---|---|---
DeepFix | 86.5% | 81.3% | 84.1%
Our SampleFix | 87.1% | 90.8% | 88.7%
Our DS-SampleFix | 96.1% | 85.6% | 90.4%
Table 2: Top: Results of performance comparison of DeepFix, RLAssist, SampleFix and DS-SampleFix. Bottom: Results of performance comparison of DeepFix and DS-SampleFix with beam search decoding. Typo, Miss Dec and All refer to, typographic, missing variable declarations, and all of the errors respectively. and $\circlelefthalfblack$ denote completely fixed programs and partially fixed programs, while denote resolved error messages. Models | Typo | Miss Dec | All
---|---|---|---
|  |  $\circlelefthalfblack$ |  |  |  $\circlelefthalfblack$ |  |  |  $\circlelefthalfblack$ |
DeepFix (?) | 23.3% | 16.2% | 30.8% | 10.1% | 12.2% | 12.9% | 33.4% | 22.3% | 40.8%
RLAssist (?) |  26.6% |  20.4% |  39.7% | - | - | - | - | - | -
Our SampleFix | 24.8% | 22.3% | 38.8% | 16.1% | 19.0% | 22.8% | 40.9% | 33.4% | 56.3%
Our DS-SampleFix | 27.7% | 21.5% | 40.9% | 16.7% | 21.2% | 24.7% | 44.4% | 35.5% | 61.0%
Our DeepFix + Beam Search | 25.9% | 22.7% | 42.2% | 20.3% | 34.5% | 47.0% | 44.7% | 36.8% | 63.9%
Our DS-SampleFix + Beam Search | 27.8% |  24.9% | 45.6% | 19.2% | 35.6% | 47.9% | 45.2% | 37.6% | 65.2%

We evaluate our approach on synthetic and real-world erroneous programs. To
evaluate our approach on the synthetic test set we randomly select 10k pairs
of the data for resolving typographic and missing variable declaration errors.
This data contains pairs of erroneous programs with the intended fixes for the
first incorrect line in programs. To evaluate our approach on real-world data
we use a real-world set of erroneous programs which contains 6975 erroneous
programs with 16766 error messages. Unlike synthetic test set, we don’t have
access to intended fix(es) in the real-world data.

Synthetic Data. Table 1 shows the comparison of our proposed approaches,
SampleFix and DS-SampleFix, with DeepFix (?) on synthetic data in the first
iteration. In this table (Table 1), we can see that our approaches outperform
DeepFix in generating intended fixes for the typographic and missing variable
declaration errors. SampleFix and DS-SampleFix generate 88.7% and 90.4% of the
intended fixes for typographic and missing variable declaration errors
respectively. This (Table 1) shows that DS-SampleFix outperforms SampleFix in
generating fixes for typographic errors. However, DS-SampleFix is not as
effective as SampleFix in correcting the missing variable declaration errors,
this is mainly due to the lack of diversity of this dataset. In other words,
DeepFix and SampleFix (without our diversity regularizer) memorizes the fixes
from the training set. However, as we demonstrate in the following, this
performance advantage does not translate to real world scenarios.

Real-World Data. In Table 2 (top four rows) we show the comparison of our
approaches, SampleFix and DS-SampleFix, with DeepFix (?) and RLAssist (?) on
the real-world test set . We also refer to the results of RLAssist, however,
it has to be noted that it is not directly comparable as this approach relies
on handcrafted actions. Furthermore, it has only been shown to resolve
typographic errors.

Table 2 (top four rows) shows that our approaches (with 100 samples obtained
using Gumbel sampling) outperform DeepFix in resolving both typographic and
missing variable declaration error messages. This shows that generating
multiple diverse fixes can lead to substantial improvement in performance.
SampleFix and DS-SampleFix resolve 38.8% and 40.9% of all of the typographic
error messages and 22.8%, and 24.7% of missing variable declaration
respectively. These results show that DS-SampleFix outperforms DeepFix by a
large margin of 32.7% and 91.4% (relative improvement) in resolving
typographic and missing variable declaration errors – almost double the
performance of the latter. We also competitive with RLAssist approach while
our approach does not require any additional supervision in term of actions.
Overall, DS-SampleFix is able to fix $61.0\%$ of all errors - a $20\%$
improvement over DeepFix. Furthermore, the performance advantage of DS-
SampleFix over SampleFix shows the effectiveness of our novel regularizer.

Beam Search Decoding. So far we have considered only the Top-1 sample of
DeepFix (as in (?)). For fairness, in Table 2 we consider sampling multiple
fixes also from DeepFix (this setting was not considered by (?)). We use beam
search to estimate the Top-100 (unique) samples from DeepFix with the highest
posterior probability (?). However, also note that beam search is
computationally expensive algorithm and its significantly slower than
generative models (?). In Table 2 (bottom two rows) we show that our proposed
approach (DS-SampleFix) can also employ beam search to improve performance. In
order to employ beam search decoding with DS-SampleFix, we consider beam width
of size 5 for each sample $z$ and in total 20 $z$ samples. Again we see that
DS-SampleFix outperforms DeepFix, showing that our DS-SampleFix not only
samples diverse but also accurate fixes.

Qualitative Examples. We provide qualitative examples in Figure 4. We
illustrate diverse fixes generated by our DS-SampleFix in Figure 4(a) with a
code example with typograhic errors, with the corresponding outputs of DeepFix
and 5 output samples of 100 drawn samples of DS-SampleFix. We see that DS-
SampleFix generates multiple correct fixes for the given program and in
contrast to DeepFix - which only predicts a single fix - our model is able to
generate multiple diverse fixes. This indicate that our approach is capable of
handling inherent ambiguity and uncertainty in predicting fixes for the
erroneous programs. Note that DeepFix and DS-SampleFix output a program
location along with the corresponding fix, and these models output _eos_
whenever they could not provide any fix for the given erroneous program.
Figure 4(b) shows a code example where DS-SampleFix repairs the typographic
and missing variable declaration errors. In Figure 4(b), we can see that our
approach resolves one missing variable declaration error, by defining variable
value at line 3, and remove a bracket at line 11, and insert a bracket at line
15 to resolve typographic errors. More code examples can be found in the
Appendix A.

(a) Diverse fixes generated by our DS-SampleFix.

(b) Iterative repair.

Figure 4: (a) Left: Example program with a typographic error. The error is
highlighted at line 19. (a) Right: Our DS-SampleFix generates multiple correct
fixes (line number and fix), highlighting the ability of DS-SampleFix to
generate diverse fixes (correct fixes with green tick). DeepFix is unable to
generate any fix. (b) Examples of resolving typographic errors, and missing
variable declaration errors using our approach (DS-SampleFix).

###  4.2 Effectiveness of Sampling Strategy

(a) Sampling strategy.

(b) Iterative repair.

Figure 5: (a) Number of resolved error messages with drawing 1, 10 and 100
samples for SampleFix , DS-SampleFix , DS-SampleFix + beam search, and DeepFix
+ beam search in comparison to number of resolved error messages by DeepFix.
(b) Number of error messages after each iterations for DeepFix, DeepFix + beam
search, SampleFix, DS-SampleFix, and DS-SampleFix + beam search.

We further analyze the effectiveness of our proposed DS-SampleFix in drawing
multiple diverse samples for a given incorrect program. Figure 5(a) shows in
detail the effectiveness of drawing multiple samples for repairing 1426 unseen
programs from a held out fold of real-world data. In Figure 5(a) x and y axis
refer to number of drawn samples and number of resolved error messages
respectively. These programs contain typographic and missing variable
declaration errors. We see that although DeepFix outperforms SampleFix and DS-
SampleFix when we only one sample is drawn to resolve each program, by drawing
more samples SampleFix and DS-SampleFix are able to resolve larger number
error messages, and both of our approaches outperform DeepFix after drawing
100 samples. Furthermore, Figure 5(a) also further illustrates the
effectiveness of our novel regularizer, as DS-SampleFix outperforms SampleFix
at every step. Figure 5(a) also shows the effectiveness of using beam search
with DeepFix and DS-SampleFix . We see that using beam search on top the
models improve the performance of DeepFix and DS-SampleFix by finding top and
unique fixes. This figure shows that after drawing 100 fixes DS-SampleFix with
beam search outperforms DeepFix + beam search. This shows that our proposed
regularizer not only enables the model to draw more diverse fixes but also
more accurate fixes.

###  4.3 Effectiveness of Iterative Repair

To resolve the multiple errors in a program we use the iterative repair
strategy as introduced by (?). Here, we analyze the effectiveness of our
proposed approaches in resolving multiple errors in a program using iterative
repair strategy. Figure 5(b) show the number of remaining errors messages in 5
iterations for DeepFix, DeepFix with beam search, SampleFix , DS-SampleFix,
and DS-SampleFix with beam search. This figure shows the original number of
error messages for 1426 programs (a held out fold of real-world data) marked
as iteration 0, and then shows the number of remaining error messages after
end of every iteration for different approaches. We use up to 5 iterations to
resolve multiple error messages. We can see that after 5 iterations, SampleFix
and DS-SampleFix resolve more error messages than DeepFix, and DS-SampleFix
with beam search outperforms all of the other approaches. One of the reason
that our approaches outperform DeepFix over the different iterations is that,
DeepFix is only capable of predicting one fix for a given program, and if the
network fails to produce a fix for a program in an iteration, then feeding the
same program into the network in the subsequent iterations will not change the
outcome. However, our proposed approaches are capable of drawing multiple
fixes in each iteration, which means that our methods can resolve more error
messages in each iteration, and we will have larger number of programs to feed
it to the network in next iteration.

##  5 Conclusion

We propose a novel framework to correct common programming errors. We
recognize and model the inherent ambiguity and uncertainty when predicting
fixes. In contrast to previous approaches, our novel framework is able to
learn the distribution of candidate fixes rather than the most likely fix. The
key to our success is a novel diversity-sensitive regularizer. This helps us
overcome the inherent limitations of supervised datasets in this challenging
domain and generalize to unseen real world test sets. Furthermore, our
experiments show that the steady increase in discovery of correct programs as
we draw more candidate fixes is a strong indication that our proposed model
can be the basis of further advances in debugging by sampling based
approaches.

## References

  * [Allamanis et al. 2018] Allamanis, M.; Barr, E. T.; Devanbu, P.; and Sutton, C.  2018\.  A survey of machine learning for big code and naturalness.
  * [Bahdanau, Cho, and Bengio 2015] Bahdanau, D.; Cho, K.; and Bengio, Y.  2015\.  Neural machine translation by jointly learning to align and translate.
  * [Bhattacharyya, Schiele, and Fritz 2018] Bhattacharyya, A.; Schiele, B.; and Fritz, M.  2018\.  Accurate and diverse sampling of sequences based on a ”best of many” sample objective.  In CVPR.
  * [Bowman et al. 2016] Bowman, S. R.; Vilnis, L.; Vinyals, O.; Dai, A. M.; Jozefowicz, R.; and Bengio, S.  2016\.  Generating sentences from a continuous space.  In SIGNLL Conference on Computational Natural Language Learning (CoNLL).
  * [Das et al. ] Das, R.; Ahmed, U. Z.; Karkare, A.; and Gulwani, S.  Prutor: A system for tutoring CS1 and collecting student programs for analysis.  abs/1608.03828.
  * [Deshpande et al. 2019] Deshpande, A.; Aneja, J.; Wang, L.; Schwing, A. G.; and Forsyth, D.  2019\.  Fast, diverse and accurate image captioning guided by part-of-speech.  In CVPR, 10695–10704.
  * [Girshick 2015] Girshick, R.  2015\.  Fast r-cnn.  In ICCV.
  * [Gottschlich et al. 2018] Gottschlich, J.; Solar-Lezama, A.; Tatbul, N.; Carbin, M.; Rinard, M.; Barzilay, R.; Amarasinghe, S.; Tenenbaum, J. B.; and Mattson, T.  2018\.  The three pillars of machine programming.
  * [Gupta et al. 2017] Gupta, R. R.; Pal, S.; Kanade, A.; and Shevade, S. K.  2017\.  Deepfix: Fixing common c language errors by deep learning.  In AAAI.
  * [Gupta, Kanade, and Shevade 2019] Gupta, R.; Kanade, A.; and Shevade, S.  2019\.  Deep reinforcement learning for programming language correction.  In AAAI.
  * [Harer et al. 2018] Harer, J.; Ozdemir, O.; Lazovich, T.; Reale, C.; Russell, R.; Kim, L.; and chin, p.  2018\.  Learning to repair software vulnerabilities with generative adversarial networks.  In NIPS.
  * [Jang, Gu, and Poole 2017] Jang, E.; Gu, S.; and Poole, B.  2017\.  Categorical reparameterization with gumbel-softmax.  In ICLR.
  * [Kingma and Ba 2015] Kingma, D. P., and Ba, J.  2015\.  Adam: A method for stochastic optimization.  In ICLR.
  * [Kingma and Welling 2014] Kingma, D. P., and Welling, M.  2014\.  Auto-encoding variational bayes.  In ICLR.
  * [Krizhevsky, Sutskever, and Hinton 2012] Krizhevsky, A.; Sutskever, I.; and Hinton, G. E.  2012\.  Imagenet classification with deep convolutional neural networks.  In NIPS.
  * [Lecun et al. 1998] Lecun, Y.; Bottou, L.; Bengio, Y.; and Haffner, P.  1998\.  Gradient-based learning applied to document recognition.  In Proceedings of the IEEE.
  * [Lee et al. 2011] Lee, H.; Grosse, R.; Ranganath, R.; and Ng, A. Y.  2011\.  Unsupervised learning of hierarchical representations with convolutional deep belief networks.
  * [Long and Rinard 2016] Long, F., and Rinard, M.  2016\.  Automatic patch generation by learning correct code.  In ACM SIGPLAN Notices.
  * [Maddison, Mnih, and Teh ] Maddison, C. J.; Mnih, A.; and Teh, Y. W.  The concrete distribution: A continuous relaxation of discrete random variables.  abs/1611.00712.
  * [Monperrus 2018] Monperrus, M.  2018\.  Automatic software repair: a bibliography.  ACM Computing Surveys (CSUR).
  * [Pu et al. 2016] Pu, Y.; Narasimhan, K.; Solar-Lezama, A.; and Barzilay, R.  2016\.  sk_p: a neural program corrector for moocs.  In ACM SIGPLAN.
  * [Rezende and Mohamed 2015] Rezende, D. J., and Mohamed, S.  2015\.  Variational inference with normalizing flows.  In ICML.
  * [Seo et al. 2014] Seo, H.; Sadowski, C.; Elbaum, S.; Aftandilian, E.; and Bowdidge, R.  2014\.  Programmers’ build errors: a case study (at google).  In ICSE.
  * [Simonyan and Zisserman 2015] Simonyan, K., and Zisserman, A.  2015\.  Very deep convolutional networks for large-scale image recognition.  In ICLR.
  * [Sohn, Lee, and Yan 2015] Sohn, K.; Lee, H.; and Yan, X.  2015\.  Learning structured output representation using deep conditional generative models.  In NIPS.
  * [Sutskever, Vinyals, and Le 2014] Sutskever, I.; Vinyals, O.; and Le, Q. V.  2014\.  Sequence to sequence learning with neural networks.  In NIPS.

## Appendix A. Additional Qualitative Examples

Figure 6: Additional example of resolving missing variable declaration errors
using our approach (DS-SampleFix).

Here we provide additional examples of correcting erroneous programs using our
proposed method. Figure 6 shows a code example which indicate our approach is
capable of resolving multiple missing variable declaration errors. Figures 7
and 8 shows code examples with typographic errors and missing variable
declaration errors, with the corresponding outputs of DeepFix and DS-SampleFix
given these erroneous programs. In these examples, DeepFix fails to resolve
these errors. However, our proposed approach (DS-SampleFix) is able to
successfully resolve the errors by sampling diverse fixes. Here we show 5
samples out of 100 drawn samples. Note that each model outputs a program
location along with the corresponding fix, and a model outputs _eos_ whenever
it could not provide any fix for the given erroneous program. Figure 7 shows
an example of erroneous program with typographic errors, and the corresponding
outputs of DeepFix and DS-SampleFix given that program.

Figure 7: Example program with a typographic error. The error is highlighted
at line 5. Our DS-SampleFix generates multiple candidate fixes (line number
and fix) which attempt the fix the correct bug (correct fix with green tick).

(a)

(b)

Figure 8: Example programs with missing variable declaration errors. The
potential location of the error is highlighted. Our DS-SampleFix generates
multiple candidate fixes which attempt to declare variables (correct fix with
green tick). DeepFix is unable to generate any fix.

Figures 9 and 10 show two examples of resolving multiple errors using
itrerative repair strategy, here we show 5 samples out of 100 drawn samples.
In Figure 9(a) we can see that in the first iteration our approach resolves a
typographic error at line 9, and in the second iteration (Figure 9(b)), after
updating the program, it resolves another typographic error at line 11. Figure
10, show an example of iteratively resolving multiple missing variable
declaration errors. Figures 10(a) and 10(b) show resolving multiple errors by
defining variables x and i respectively.

(a)

(b)

Figure 9: An example of iteratively resolving multiple typographic errors
using our approach (DS-SampleFix).

(a)

(b)

Figure 10: An example of iteratively resolving multiple missing variable
declaration errors using our approach (DS-SampleFix).