Bayes DistNet - A Robust Neural Network for
Algorithm Runtime Distribution Predictions

Problems such as CSP and SAT are NP-complete, meaning that there is currently no guarantee there is a polynomial time solution technique. The dominant solver technique for these types of problems is backtrack search, in which heuristics pick an unbound variable, assign a value to it, and the search proceeds recursively. If an inconsistency is detected, the algorithm backtracks and tries another assignment to that variable.

A consequence of using backtrack-based solvers is that early mistakes can cause long searches down branches of the search tree which eventually need to be backtracked. This leads to the so-called “heavy-tail” phenomenon, in which the runtime of these algorithms exhibit tails which are not exponentially bounded. Harvey (1995) was the first to show that adding randomization and restarts into the backtracking algorithm can alleviate the issue of wasting time on eventual dead-ends. Gomes, Selman, and Kautz (1998) presented general methods for introducing controlled randomization, and showed that speedups of several orders of magnitude could be achieved for state-of-the-art algorithms.

Introducing randomness into algorithms means that a given algorithm run on the same input problem instance has a runtime which follows some initially unknown distribution. There are many reasons why one would want the ability to predict such runtime distributions (RTDs). Luby, Sinclair, and Zuckerman (1993) showed that if one knows the underlying RTD, then it’s possible to construct a fixed cutoff-time restart strategy that is optimal among all possible universal strategies, up to a constant factor. Other popular CSP and SAT solvers use a portfolio of various algorithms, such as SATzilla (Xu et al. 2008) and ArgoSmArT (Nikolić, Marić, and Janičić 2009). Knowing the RTDs of each algorithm in the portfolio allows such solvers to choose the best algorithm for a given problem instance.

The majority of the early work for predicting algorithm runtimes involved predicting mean instance runtimes, given the instance’s features. Many of these methods were based on regression variants, such as ridge regression used in SATzilla (Xu et al. 2008).

Gagliolo and Schmidhuber (2005) investigated using a neural network to predict the time remaining before an algorithm reaches the solution on a given problem instance, in the context of algorithm portfolio time allocation. Previous methods for predicting RTDs had separate models for each distribution parameter. DistNet (Eggensperger, Lindauer, and Hutter 2018) established a new state-of-the-art RTD prediction model which jointly learns the parameters of the RTD by using a neural network. Each output node of the neural network corresponds to a parameter for the given distribution. The neural network’s loss function directly minimizes the negative log-likelihood (NLLH) of the distribution parameters, given the observed runtimes.

Traditional neural networks can be viewed as a probabilistic model: given a dataset $\mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{N}$, the parameterized model $P(\mathbf{y}|\mathbf{x},\mathbf{w})$ takes in a $d$-dimensional input $\mathbf{x}\in\mathbb{R}^{d}$ and computes a point estimate for each output $\mathbf{y}\in\mathcal{Y}$. Training most commonly involves finding the set of weights $\mathbf{w}$ which maximizes the likelihood of the data.

These networks can be prone to overfitting, especially when the number of model parameters is sufficiently greater than the number of training samples. Regularization techniques like using weight priors and dropout (Srivastava et al. 2014) have been proposed to mitigate overfitting.

Bayesian neural networks (BNNs) (MacKay 1992; Neal 2012) extended traditional neural networks by replacing the network’s deterministic weights with a prior distribution over these weights, and using posterior inference. The full posterior distribution of the model’s parameters $\mathbf{w}$ is used when making predictions of unseen data. Prediction for this separate probabilistic model involves taking the expectation over the optimized posterior distribution $P(\mathbf{w}|\mathcal{D})$. The posterior predictive distribution of unseen data $(\hat{\mathbf{x}},\hat{\mathbf{y}})$ is given by

	$\displaystyle P(\hat{\mathbf{y}}|\hat{\mathbf{x}})$	$\displaystyle=\mathbb{E}_{P(\mathbf{w}|\mathcal{D})}\left[P(\hat{\mathbf{y}}|\hat{\mathbf{x}},\mathbf{w})\right]$
		$\displaystyle=\int P(\hat{\mathbf{y}}|\hat{\mathbf{x}},\mathbf{w})P(\mathbf{w}|\mathcal{D})\ d\mathbf{w}.$

Bayesian neural networks can help with overfitting as the model implicitly involves using an ensemble of an infinite number of neural networks by averaging over all possible weight values, while adding a constant multiple number of network parameters, determined by how many parameters the parametric distribution has. Bayesian neural networks are also able to capture both aleatoric uncertainty and epistemic uncertainty in its predictions. Aleatoric uncertainty captures uncertainties which are inherent to running statistical trials, like the outcome of a dice toss. This type of uncertainty cannot be reduced, no matter how much data is collected. Epistemic uncertainty captures the uncertainty in the model being used, which is due to limited data and/or knowledge. This type of uncertainty can be reduced with more data.

Both inference and prediction for BNNs involve calculating the posterior

$$P(\mathbf{w}|\mathcal{D})=\frac{P(\mathcal{D}|\mathbf{w})P(\mathbf{w})}{P(\mathcal{D})}=\frac{P(\mathcal{D}|\mathbf{w})P(\mathbf{w})}{\int P(\mathcal{D}|\mathbf{w^{\prime}})P(\mathbf{w^{\prime}})\ d\mathbf{w^{\prime}}}.$$

The prior $P(\mathbf{w})$ is something we can choose, but the integral involved in the posterior is often computationally intractable. While the above posterior can be approximated using sampling-based inference algorithms like Markov Chain Monte Carlo (MCMC) methods (Gelfand and Smith 1990), these do not scale well as the number of samples and/or parameters increase (Blei, Kucukelbir, and McAuliffe 2017), as is the case in neural networks. An alternative, suggested by Hinton and Van Camp (1993) and Graves (2011), is to use a variational approximation for the posterior $P(\mathbf{w}|\mathcal{D})$. Variational methods construct a new distribution $q(\mathbf{w}|\bm{\theta})$, parameterized by $\bm{\theta}$, that approximates the true posterior $P(\mathbf{w}|\mathcal{D})$ by minimizing the Kullback-Leibler (KL) divergence between the two:

	$\displaystyle\bm{\theta}_{\text{VI}}$	$\displaystyle=\operatorname*{arg\ min}_{\bm{\theta}}KL\left[q(\mathbf{w}|\bm{\theta})||P(\mathbf{w}|\mathcal{D})\right]$
		$\displaystyle=\operatorname*{arg\ min}_{\bm{\theta}}\int q(\mathbf{w}|\bm{\theta})\log\frac{q(\mathbf{w}|\bm{\theta})}{P(\mathbf{w})P(\mathcal{D}|\mathbf{w})}\ d\mathbf{w}$
		$\displaystyle=\operatorname*{arg\ min}_{\bm{\theta}}KL\left[q(\mathbf{w}|\bm{\theta})||P(\mathbf{w})\right]-\mathbb{E}_{q(\mathbf{w}|\bm{\theta})}\left[\log P(\mathcal{D}|\mathbf{w})\right].$

We denote $\bm{\theta}_{\text{VI}}$ as the parameters found from variational inference methods. Bayes by Backprop (Blundell et al. 2015) uses the above to form the cost function

$$J_{\text{BBB}}(\mathcal{D},\bm{\theta})=KL\left[q(\mathbf{w}|\bm{\theta})\ ||\ P(\mathbf{w})\right]\\ -\mathbb{E}_{q(\mathbf{w}|\bm{\theta})}\left[\log P(\mathcal{D}|\mathbf{w})\right].$$

(1)

The intuition for the above cost function is that there is a tradeoff between having a variational posterior that is close to the prior we choose yet also able to explain the likelihood of the data. Despite the simple formulation of the above, the cost $J_{\text{BBB}}(\mathcal{D},\bm{\theta})$ is still intractable as it involves calculating posteriors over high-dimensional spaces. While neural networks would seem like an appropriate tool to find a function which minimizes $J_{\text{BBB}}$, we cannot naively apply backpropagation through nodes which involve stochastity. By applying a generalization of the re-parameterization trick (Opper and Archambeau 2009; Kingma and Welling 2014), Bayes by Backprop (Blundell et al. 2015) then provides an approximation to the cost (Eq. 1) as

$$J_{\text{BBB}}(\mathcal{D},\bm{\theta})\approx\sum_{i=1}^{n}\log q(\mathbf{w}^{(i)}|\bm{\theta})-\log P(\mathbf{w}^{(i)})\\ -\log P(\mathcal{D}|\mathbf{w}^{(i)}),$$

(2)

where $\mathbf{w}^{(i)}$ is the set of weights drawn from the $i$-th Monte Carlo sample of the variational posterior $q(\mathbf{w}|\bm{\theta})$. Having a computational efficient way of training BNNs has allowed extensions to other network architectures like RNNs (Fortunato, Blundell, and Vinyals 2017) and CNNs (Shridhar, Laumann, and Liwicki 2019), as well as studies into utilizing the uncertainty measures the BNNs provide (Amodei et al. 2016; Kendall and Gal 2017).

Before we introduce our extensions, we give an overview of the DistNet model (Eggensperger, Lindauer, and Hutter 2018). DistNet is a simple feed-forward network for a given distribution $\mathcal{F}$ with distribution parameter vector $\bm{\beta}$. There is one input neuron for each instance feature, and one output neuron for each distribution parameter $\beta_{i}$. The novelty of DistNet is that it directly minimizes the NLLH of the chosen distribution $\mathcal{F}$. The loss function used in DistNet is

$$J_{\text{DN}}(\mathbf{w})=-\sum_{\xi\in\Xi_{\text{train}}}\sum_{i=1}^{k}\log\mathcal{L}_{\mathcal{F}}(\hat{\bm{\beta}}_{\mathbf{w},f(\xi)}|t(\xi)_{i}),$$

(3)

where $\mathcal{L}_{\mathcal{F}}$ is the likelihood function of the parametric distribution $\mathcal{F}$, and $\hat{\bm{\beta}}_{\mathbf{w},f(\xi)}$ are the parameters of the distribution from the network output, with current weights $\mathbf{w}$.

To extend DistNet with Bayesian inference, which we will refer to as Bayes DistNet, a few changes need to be made to the network. We start from the same base network, which has one input neuron for each input feature, and uses simple feed-forward layers.

While the straightforward choice for the Bayesian network output would be the parameters $\bm{\beta}$ of the chosen distribution $\mathcal{F}$, the actual implementation is non-trivial and is computationally expensive. The network would produce a posterior over distribution parameters by sampling the network repeatedly, and these parameters would then be used in the likelihood $\mathcal{L}_{\mathcal{F}}(\hat{\bm{\beta}}_{\mathbf{w},f(\xi)}|t(\xi)_{i})$, with the likelihood weighted by the posterior, resulting in a posterior predictive distribution. However, this requires a density estimation method using the set of network samples $\hat{\bm{\beta}}_{\mathbf{w},f(\xi)}$, such that the gradient information can still be tracked from the loss function.

Instead, we choose to have the Bayesian network directly output predicted runtimes $\hat{y}$. By sampling the network, a sequence of runtimes is produced which is assumed to follow $\mathcal{F}$. The parameters of $\mathcal{F}$ can then be approximated by computing their maximum likelihood estimates (MLEs), denoted $\hat{\bm{\beta}}^{\text{MLE}}$. The choice of $\mathcal{F}$ can ensure that we have analytical formulations of $\hat{\bm{\beta}}^{\text{MLE}}$, which are fast to compute using deep-learning framework intrinsics, and whose gradients can be tracked from the loss function.

To make the network Bayesian, we need to define a variational posterior $q(\mathbf{w}|\bm{\theta})$, the prior of the network weights $P(\mathbf{w})$, and the likelihood of the training data. Following Blundell et al. (2015), we assume that the variational posterior $q(\mathbf{w}|\bm{\theta})$ is a diagonal Gaussian distribution with mean $\bm{\mu}$ and standard deviation $\bm{\sigma}$. While it is possible to use a multivariate Gaussian, a diagonal Guassian allows for simple computations without major numerical issues. To be able to use backpropagation, we use the re-parameterization given by Blundell et al. (2015), which obtains a sample of weights $\mathbf{w}$ for each layer by the following procedure: Sample the parameter-free noise $\bm{\epsilon}\sim\mathcal{N}(\bm{0},\mathbf{I})$, and let $\bm{\sigma}=\log(\bm{1}+\exp(\bm{\rho}))$. We can then denote $\bm{\theta}=(\bm{\mu},\bm{\rho})$, and the parameterization of $\bm{\sigma}$ ensures that the values are always $>0$. The weights $\mathbf{w}$ can then be sampled by $\mathbf{w}=\bm{\mu}+\bm{\sigma}\circ\bm{\epsilon}$, where $\circ$ is point-wise multiplication. Once a particular set of point-wise weights is sampled for each of the layers of the network, those weights are then used as in the traditional feed-forward layers.

Since the network’s task is to predict runtimes directly, it has a single output neuron. The network output $\hat{y}$ represents the predicted runtime for a particular set of point-wise weights which were sampled from each layer. To get a predictive distribution, Monte Carlo sampling is used, in which the same input to the network will be used $N$ times to produce $N$ separate output values.

From Eq. 2, the term $\log P(\mathcal{D}|\mathbf{w})$ is replaced with the likelihood from $J_{\text{DN}}$, which measures the likelihood of the data in our new model. The variational approximated cost function for the network now becomes

$$J(\mathcal{D},\bm{\theta})_{\text{BDN}}=\sum_{i=1}^{N}\log q(\mathbf{w}^{(i)}|\bm{\theta})-\log P(\mathbf{w}^{(i)})\\ -\sum_{\xi\in\Xi_{\text{train}}}\sum_{j=1}^{k}\log\mathcal{L}_{\mathcal{F}}\big{(}\hat{\bm{\beta}}^{\text{MLE}}|t(\xi)_{j}\big{)},$$

(4)

where $\hat{\bm{\beta}}^{\text{MLE}}$ is $\mathcal{F}$’s distribution parameter vector computed by MLE using the $N$ predicted runtimes $\hat{y}_{i}$, and each $\hat{y}_{i}$ is produced by the network using weights $\mathbf{w}^{(i)}$ from the $i$-th Monte Carlo sample.

In our application domain, censoring occurs when an algorithm needs to be stopped before completion, i.e., we only know a lower bound on the time it takes to actually complete the algorithm. There is a rich history in survival analysis on handling different types of censored data, and we recommend Klein and Moeschberger (2003) for background reading. Gagliolo and Schmidhuber (2006) first introduced handling Type I censored sampling in the context of algorithm runtime prediction, and we give the explanation for clarity.

If censoring time of $t_{c}$ is used, then $t_{c}$ is the maximum time an algorithm can run before being terminated. The dataset $\mathcal{D}=\{(\bm{f}(\xi)_{i},t(\xi)_{i})\}_{i=1}^{N}$ from before now becomes $\mathcal{D}=\{(\bm{f}(\xi)_{i},t_{i},\delta_{i})\}_{i=1}^{N}$, where $t_{i}=\min(t(\xi)_{i},t_{c})$, and $\delta_{i}$ is a Boolean variable indicating that an individual sample was not censored (i.e., $\delta_{i}=1$ indicates that $t(\xi)_{i}\leq t_{c}$).

Let $f_{\mathcal{F}}$ denote the density of distribution $\mathcal{F}$ with parameters $\bm{\beta}$, and let $\mathcal{S}_{\mathcal{F}}$ denote the survival function of distribution $\mathcal{F}$. If the runtime is not censored, then we observe $\delta_{i}=1$, and its contribution to the likelihood function is the density function at that time as it normally would be,

$$\mathcal{L}_{\mathcal{F}}\big{(}\hat{\bm{\beta}}^{\text{MLE}}|t_{j}\big{)}=f_{\mathcal{F}}\big{(}t_{j}|\hat{\bm{\beta}}^{\text{MLE}}\big{)}.$$

If the runtime is censored, then we observe $\delta_{i}=0$, and all we can say under censoring is that the runtime exceeds the cutoff $t_{c}$. This is equivalent to the survival function, and so its contribution to the likelihood function when censored is

$$\mathcal{L}_{\mathcal{F}}\big{(}\hat{\bm{\beta}}^{\text{MLE}}|t_{j}\big{)}=\mathcal{S}_{\mathcal{F}}\big{(}t_{j}|\hat{\bm{\beta}}^{\text{MLE}}\big{)}.$$

Combining the above, we get

$$\mathcal{L}_{\mathcal{F}}\big{(}\hat{\bm{\beta}}^{\text{MLE}}|t_{j}\big{)}=f_{\mathcal{F}}\big{(}t_{j}|\hat{\bm{\beta}}^{\text{MLE}}\big{)}^{\delta_{j}}\mathcal{S}_{\mathcal{F}}\big{(}t_{j}|\hat{\bm{\beta}}^{\text{MLE}}\big{)}^{1-\delta_{j}},$$

(5)

which is then used to replace the likelihood term in the Bayesian cost function (Eq. 4) from above.

For comparative results, we follow the same preprocessing steps from Eggensperger, Lindauer, and Hutter (2018). Input instance features are standardized to mean 0 and standard deviation 1, and observed runtimes are scaled into the range of $[0,1]$. For a level of censoring $c$, where $c$ is the fraction of censored runtimes from a total of $N$, the cutoff time $t_{c}$ is the $u$-th fastest runtime, where $u=\left\lfloor N(1-c)\right\rfloor$. The runtimes are then set to $\min(t(\xi)_{i},t_{c})$, and the observations include whether censoring occurred or not.

Both the reference DistNet model and our new Bayesian variant share the majority of the network architecture proposed by Eggensperger, Lindauer, and Hutter. The input layer has a neuron for each instance feature. This is then followed by two hidden fully connected layers, each of which has 16 neurons. DistNet has a fully connected output layer with one neuron per parameter for the specific parametric distribution, whereas Bayes DistNet has a single output.

The Bayes DistNet architecture also has a prior $P(\mathbf{w})$ and a variational posterior $q(\mathbf{w}|\bm{\theta})$ that needs to be specified. As previously noted, we use a diagonal Gaussian variational posterior, with initial parameters $\bm{\theta}_{\text{init}}=(\bm{\mu}_{\text{init}},\bm{\rho}_{\text{init}})$, $\bm{\mu}_{\text{init}}\sim\mathcal{N}(0,0.1)$ and $\bm{\rho}_{\text{init}}\sim\mathcal{N}(-3,0.1)$. The chosen $\bm{\mu}_{\text{init}}$ ensures weights are initialized around 0 (just as we would for a standard neural network), and $\bm{\rho}_{\text{init}}$ is initialized to a small value, as we found learning is not as stable otherwise (Shridhar, Laumann, and Liwicki 2019). For the prior, we follow the proposal from Blundell et al. (2015) of using a mixture of two Gaussian distributions

$$P(\mathbf{w})=\prod_{i}\alpha\mathcal{N}(\mathbf{w}_{i};0,\sigma_{1}^{2})+(1-\alpha)\mathcal{N}(\mathbf{w}_{i};0,\sigma_{2}^{2}),$$

where $\mathcal{N}(x;\mu,\sigma^{2})$ is the Gaussian density evaluated at $x$ with mean $\mu$ and variance $\sigma^{2}$, with $\alpha=0.5$, $\sigma_{1}=0.3$, and $\sigma_{2}=0.01$. The choice of these parameters did not have a noticeable difference so long as $\sigma_{1}>\sigma_{2}$ and $\sigma_{2}\ll 1$, as per Blundell et al. (2015). When performing inference and prediction, we use 16 Monte Carlo samples. As with previous studies (Fortunato, Blundell, and Vinyals 2017; Shridhar, Laumann, and Liwicki 2019), a large number of samples gives marginally better results at the cost of computation time. We did not find much improvements beyond 16 samples.

DistNet uses the tanh activation function, with the exception of the exponential activation function on the output layer to ensure the output distribution parameters are $>0$. Bayes DistNet, on the other hand, uses softplus (Glorot, Bordes, and Bengio 2011) on all layers which is a smooth approximation to the recitifer activation function, as we want to ensure that activations for variational posterior variances never become $\leq 0$. We then largely follow the hyperparameter choices from Eggensperger, Lindauer, and Hutter (2018), whose DistNet model we are basing our Bayes DistNet model from. Both network architectures use stochastic gradient descent (SGD), with batch normalization (Ioffe and Szegedy 2015), L₂-regularization of $1e^{-4}$, a learning rate of $1e^{-3}$ which exponentially decays to $1e^{-5}$ over 500 expected epochs, and gradient clipping of $1e^{-2}$. Early stoppage (Prechelt 1998) is used on a separate validation set to reduce overfitting.

We evaluated the performance of our Bayes DistNet model by varying the number of observed runtimes per instance. Every instance starts with 100 observed runtimes, and a random subset of those 100 are selected. Having a smaller number of observed runtimes per instance means that the total training set is reduced. For testing, we keep all 100 observed runtimes for every instance in the test set. The evaluation is performed using a 10-fold cross-validation, repeated with multiple seeds, and aggregating the results.

Figure 1 reports several metrics to evaluate the goodness-of-fit of each model, compared to the empirical observed runtimes of the test set. The likelihood is a way to measure how probable a model is, given the observed data. A lower negative log likelihood (NLLH) thus indicates that one particular model gives the observed data a higher probability of occurring. For both scenarios of Clasp-factoring and LPG-Zenotravel, Bayes DistNet achieves a lower negative log likelihood across various levels of samples per instance. Given enough data, both DistNet and Bayes DistNet converge to having an equal likelihood score.

While the likelihood is a way to measure how probable a model is given the data, it does not indicate the shape of the predicted runtime distribution. We thus looked at two metrics to quantity how dissimilar the model’s predictive distribution shape is compared to the empirical distribution, namely KL-Divergence and the Kolmogorov-Smirnov statistic (KS-Distance). The KL-Divergence quantifies the amount of information lost if the model’s distribution is used instead of the empirical distribution. The KS-Distance measures the maximal distance in height from the model’s CDF to the empirical CDF. For both metrics, lower is better.

Our Bayesian model achieves lower KL-Divergence and lower KS-Distance with respect to the empirical distribution, as compared to the DistNet model across various levels of samples per instance. This indicates that our Bayesian model is able to produce predictive RTDs which are closer in shape to the empirical RTD. Again, given enough data, both DistNet and our Bayesian model converge to predicting RTDs which on average are equally close to the empirical RTDs.

We also evaluated our Bayes DistNet model by keeping the number of samples per instance constant, but varying the percentage of censoring in the training data. We decided to use 8 samples per instance, as this was the number of samples we start to see both DistNet and our Bayesian variant perform similarly without censoring. To have an accurate comparison, we modified the DistNet loss function to include censored samples as well, following Eq. 5. Figure 2 reports similar metrics as before to evaluate the goodness-of-fit for both DistNet and our Bayesian variant, as compared to the empirical RTDs.

The NLLH of both the best DistNet model and Bayes DistNet are identical under no censoring. As the censoring percentage increases, both models are trained on less fully observable data, and we expect the NLLH to increase. Interestingly, we see that while both models have their NLLH increase, Bayes DistNet increases at a slower rate than DistNet. This indicates that our Bayesian model is better able to capture the uncertainty that comes with using censored data.

Using the distance metrics again, we can see how similar our Bayesian model is to the empirical RTD, as compared to DistNet. We expect both the KL-Divergence and the KS-Distance to increase as the percentage of censored data increases. Both the best DistNet model and our Bayesian model start roughly with similar distance metrics. As the percentage of censored data increases, our Bayesian model’s distance metrics increase at a slower rate compared to DistNet. We see that our Bayesian model is able to produce distributions which are more similar to the empirical RTDs under censoring, as compared to DistNet.

A known issue with standard neural networks, which use point estimates for weights, is that they tend to be overconfident in regions which had little or no data during training. Neural networks fit a function to training data which minimizes the chosen loss function. If deterministic weights are used, then a single particular function of many possible ones is chosen for the data. This function is then extrapolated to make predictions for inputs which may be far from the data used to train the network, resulting in overconfident predictions. As a result, adversarial and out-of-distribution inputs can be given to the network, and the network would give predictions which it is confident in, which can be exploited by attackers.

Instead of using point estimates for weights, Bayesian neural networks make predictions using all possible weight values, weighted by their posterior probability. We can think of this as a type of model averaging. When predictions are made for inputs which are far from the data used to train the network, the model averaging considers that there are many possible extrapolations, which result in the confidence regions diverging.

Figure 3 shows the result of traditional neural networks, as is the case for the original DistNet model, of being overconfident in its predictions for adversarial inputs. Both networks were trained on the Clasp-factoring dataset, except for a held out sample, and both models use the lognormal distribution in the loss function. The held out sample then had all its features shifted by values in the range [-8,8] to produce a spectrum adversarial samples.

The predictive distribution mean and interquartile ranges were then plotted for these samples. DistNet has small interquartile ranges for adversarial samples, which suggests it does not see adversarial samples any different than the ones it was trained on. This can be problematic if we were to use DistNet in sensitive applications, or scenarios where computation is expensive. On the other hand, Bayes DistNet has interquartile ranges which diverge on adversarial samples. This suggests that Bayes DistNet has the capability to indicate when it is not confident in its predictions. In sensitive or computationaly expensive scenarios, a fallback measure can then be used when the predictive distribution’s interquartile range falls outside a given threshold.

We have shown that in scenarios featuring a low number of instances or censored observations, our Bayesian model is able to generate distributions which give higher likelihoods of the data, and better match the empirical RTD’s shape.

Both DistNet and Bayes DistNet require a parametric distribution. Both use this distribution in the loss function for the likelihood, but DistNet also restricts the output distribution to directly be a member of that parametric distribution class. From Figures 1 and 2, we can see that the choice of the parametric distribution used has a greater impact on the predictive performance on DistNet, than it does for the Bayesian models. It’s almost certain that RTDs do not perfectly match known parametric distributions. From the data, we can see that putting a restriction on the type of distributions the model can predict can have a negative impact, as is the case for DistNet.

We finally give some insight as to why we believe our Bayesian models outperform DistNet, even when the same parametric distribution is used. For low samples per instance and various levels of censoring, Figures 1 and 2 respectively show where the density of the predicted RTDs lie. We plot the percentage of total area under the RTDs outside the range $[0,T]$, where $T$ is 1.5 times the maximum observed runtime for each instance. We expect that it should be improbable to see many runtimes outside this range, and thus predicted RTDs should give little density outside this range if the density is to be informative. When a low number of samples is used, we can see from Figure 1 that in some cases, DistNet is unable to give an informative predictive RTD, as a significant amount of density is outside the predictable range. For the censored cases, Figure 2 shows similar results.

We summarize in that both DistNet and our Bayesian variant perform similarly if given enough non-censored data. As the level of censoring increases and as the number of samples per instance decreases, our Bayesian model starts to outperform DistNet and better matches the empirical RTDs. It appears from our results that the discrepancy in performance between the Bayesian and non-Bayesian versions is more affected by the number of samples used.