Title: DIFFERENTIABLE BAYESIAN NEURAL NETWORK INFERENCE FOR DATA STREAMS Anonymous

Abstract: While deep neural networks (NNs) do not provide the confidence of its prediction, Bayesian neural network (BNN) can estimate the uncertainty of the prediction. However, BNNs have not been widely used in practice due to the computational cost of predictive inference. This prohibitive computational cost is a hindrance especially when processing stream data with low-latency. To address this problem, we propose a novel model which approximate BNNs for data streams. Instead of generating separate prediction for each data sample independently, this model estimates the increments of prediction for a new data sample from the previous predictions. The computational cost of this model is almost the same as that of non-Bayesian deep NNs. Experiments including semantic segmentation on real-world data show that this model performs significantly faster than BNNs, estimating uncertainty comparable to the results of BNNs.

1. INTRODUCTION:

While deterministic neural networks (DNNs) surpass human capability in some area in terms of prediction accuracy (He et al., 2015; Silver et al., 2016; Ardila et al., 2019) , it could not estimate a trustworthy uncertainty of prediction. Since the prediction can not be perfect and the misprediction might result in fatal consequences in areas such as medical analysis and autonomous vehicles control, estimating uncertainty as well as predictions will be crucial for the safer application of machine learning based systems.

Bayesian neural network (BNN), a neural network (NN) that uses probability distributions as weights, estimates not only predictive results but also uncertainties. This allows computer systems to make better decisions by combining uncertainty with prediction. Moreover, BNN can achieve high performance in a variety of fields, e.g. image recognition (Kendall et al., 2015; Kendall & Gal, 2017) , language modeling (Fortunato et al., 2017) , reinforcement learning (Kahn et al., 2017; Osband et al., 2018) , meta-learning (Yoon et al., 2018; Finn et al., 2018) , and multi-task learning (Kendall et al., 2018) , by exploiting uncertainty.

Although BNNs have these theoretical advantages, they have not been used as a practical tool. The predictive inference speed has detained BNNs from wide applications. BNN executes NN inference for dozens of samples from weight distributions. Since sampling and multiple NN executions are difficult to be parallelized, the inference execution takes an order of magnitude more time. Particularly, this is a significant barrier for processing data streams with low-latency.

Most time-varying data streams change continuously, and so do the predictions of BNNs. Thus, we estimate prediction by calculating the increments between two consecutive results, instead of calculating the separate prediction for each input data. This is equivalent to calculating the differentiation of the BNN's prediction for arbitrary data, because the difference of prediction for the new data is the line integration of the gradient of prediction over the new data.

In this work, we propose a differentiable BNN (DBNN) inference with respect to an input data. The prediction of the DBNN is given by a Monte Carlo (MC) estimator for distributions of data streams and weights. We speed up the inference by approximating the distribution using histogram and calculating the gradient for this MC estimator. We show that the time complexity of this model is nearly the same as that of deep DNNs. We evaluate DBNN with semantic segmentation using road scene video sequences and the results show that DBNN has almost no degradation in computational performance compared to deep DNNs. The uncertainty predicted by DBNN is comparable to that of BNN in various situations.

The main contributions of this work are as follows.

• We propose online codevector histogram that estimates the probability of a high-dimensional data stream. Then, we show that this histogram can be used to obtain the MC gradient estimation. • We propose differentiable Bayesian neural network inference with respect to input data as an approximation of Bayesian neural network inference for data streams. DBNN uses the online codevector histogram to approximate probabilities. This model is nonparametric and applied to trained BNN without significant modifications. • We theoretically and empirically show that the computational performance of DBNN is almost the same as that of deep DNNs.

2. BACKGROUND AND RELATED WORK:

BNNs are a state-of-the-art method to estimate predictive uncertainty while DNNs based approaches have been developed recently (Lakshminarayanan et al., 2017; Guo et al., 2017) . BNNs with probability distributions as weights produce probabilistic results. To make prediction, BNNs sample from the weight probabilities and performs DNN for each sample. In this section, we describe the details and challenges of BNNs inference process.

2.1. BAYESIAN NEURAL NETWORK INFERENCE:

Suppose that p(w) is posterior probability of NN weights w and p(y|x, w) is the BNN model for input data x. Then, the inference result of BNN is a predictive distribution:

p(y|x ) = p(y|x , w)p(w)dw (1)

where x is observed input data vector and y is output vector. For simplicity, BNNs are usually modeled to have a probability distribution with the mean of the prediction of DNN, e.g. in Hernández-Lobato & Adams (2015); Gal & Ghahramani (2016) :

EQUATION

where NN(•) is prediction of DNN and τ is a given parameter. (1) can be approximated using MC estimator:

EQUATION

where w ∼ p(w) and N w is the number of samples. The expected value of the obtained predictive distribution is the predictive result of BNN and the variance is the predictive uncertainty. The process of calculating the equation consists of two steps: sampling weights from p(w), e.g. using Markov chain Monte Carlo (MCMC) (Neal et al., 2011; Hoffman & Gelman, 2014) , and executing the DNN for each weight sample. Since real-world data is large and practical NNs are deep, the repetitive computation of NNs is difficult to be fully parallelized due to various problems, such as memory limitations of the GPU (Kendall & Gal, 2017) , and the iterative computation of DNNs results in the decrease of computation speed. MCMCs are slow and, despite recent achievements (Tran et al., 2018) , it is challenging to achieve linearly scaling performance for multi-GPU MCMC. In addition, it is difficult to check for the convergence of MCMCs. To mitigate these problems, we approximate the difference in the prediction for one new data as one NN calculation, and sample the weights from the posterior before testing.

Several sampling-free BNNs, e.g. Hernández-Lobato & Adams (2015) ; Wang et al. (2016); Hwang et al. (2018) ; Wu et al. (2018) , have been proposed recently. The sampling-free BNNs predict results with only one forward pass. These methods, however, have limitations. First, sampling-free BNNs necessitate specific types of weight-distribution with parameters such as Gaussian distribution or exponential family instead of using MC estimator to approximate (1). When a posterior has multimodality or skew, they can give inaccurate approximations. Second, in many cases, sampling-free BNN uses a method other than variational inference to obtain a posterior because evidence lower bound (ELBO) is not amenable. These constraints make it difficult to apply sampling-free BNNs to deep NNs. Therefore, we mainly consider sampling-based BNN for comparison in this paper.

2.2. BAYESIAN NEURAL NETWORK GRADIENT ESTIMATION:

It is standard to use a gradient of MC estimator to optimize the loss function of BNN, e.g. ELBO.

Several direct and indirect methods are used to obtain the MC gradient estimation: reparametrization trick (Kingma & Welling, 2013; Blundell et al., 2015; Fortunato et al., 2017) , score function (Kleijnen & Rubinstein, 1996; Williams, 1992; Glynn, 1990) , dropout (Gal & Ghahramani, 2016; McClure & Kriegeskorte, 2016) , batch normalization (Teye et al., 2018) , expectation propagation (Hernández-Lobato & Adams, 2015) , and smooth transformation for samples (Liu & Wang, 2016; Burda et al., 2015; Maddison et al., 2017; Naesseth et al., 2017; Le et al., 2017; van den Oord et al., 2017) .

However, it is not appropriate to use these techniques to calculate a gradient of MC estimator L = E p(x) f (x) for arbitrary functions f (•) when a data stream is non-stationary and p(x), the distribution of the data stream, is time-variant. For example, the reparameterization trick, one of the most widely used methods for MC gradient estimation, separates the probability p(x) into a deterministic function h(•) and an invariant probability p( ), i.e., x = h( ) and ∂ x p( ) = 0. Then, the L is expectation over the invariant distribution, i.e., L = E p( ) f (x) , and the approximated L becomes differentiable, i.e., ∂ x L = E p( ) ∂ x f (x) . To use this technique, we need to adapt h(•) to the non-stationary data stream. If h(•) is modeled in an NN, we may need to continuously train this NN on the data stream; this leads to a decrease in computational performance. To alleviate this problem, we use histogram to estimate probability with nearest neighbor search, instead of using an NN-based generative model. In addition, the histogram is a linear sum of disjoint bins that is analytically useful while simplifying calculations.

3. ONLINE CODEVECTOR HISTOGRAM:

Vector quantization was introduced in Gersho (1982); Gray (1984) in order to compress a probability distribution to a dozens of samples called codevectors. Kotani et al. (2002) showed that the histogram of codevectors-codevectors augmented with counts-can effectively represent the features of face image dataset. Xu et al. (2012) ; Frezza-Buet (2014); Ghesmoune et al. (2016) have proposed algorithms that changes codevectors depending on the data stream. We introduce online codevector histogram (OCH) to estimate the probability distribution of non-stationary data stream as well as dataset. OCH is a probabilistic algorithm that changes not only codevectors but their counts and calculates the difference in distribution as the data stream changes, at low computational cost. OCH can add a new codevector and delete old ones, while counting the matches of each codevector for the past data stream. OCH maps the input vector to the codevector using nearest neighbor search. It is a high-dimensional histogram where the Voronoi diagram is the boundary and a codevector represents the corresponding bin. DBNN uses OCH to approximate the probability distributions of input and output vector data streams.

Algorithm 1 shows how OCH operates in three steps. (a) Given a new input vector, OCH finds the nearest codevector and increases its count. Then, it divides the corresponding bin by inserting the input vector as a new codevector with probability proportional to the count. (b) OCH decrease all counts by the same rate to reduce the contribution of old data. (c) To keep the number of codevectors small, OCH deletes codevectors with probability in inverse proportion to its counts.

OCH takes three hyperparameters: K, λ, and φ. K is the number of codevectors kept in OCH on average. λ determines how fast OCH depreciates old counts with the rate of γ. φ with counts of each bin regulates the probability of adding and deleting codevectors.

Nearest neighbor search is the most computationally intensive step in alg. 1. To lower the computational complexity, we use locality-sensitive hashing with stable distribution, h = (a • x + b) /w for a vector a and scalars b and w. It requires up to log K hashes for precise search. The upper bound of the computational complexity is O(dim(x) log K). This is faster than continuous training of NN-based generative models for the data stream changing over time.

Algorithm 1: Update OCH input :input vector x , count of input vector n , OCH = {(c i , n i )} where c i is codevector and n i is its count, hyperparameters K, λ, and φ output :updated OCH c i ← Search the nearest codevector to x in OCH

n i ← n i + n where n i is count of c i p ∼ Bernoulli σ(π i -π + φ) where σ(•) is sigmoid, N = i n i , π i = n i /N , and π = 1/K if p = 1 then OCH ← OCH ∪ {(x , (1 -γ) • n i )} where γ = e -λ /N n i ← γ • n i forall (c j , n j ) ∈ OCH do n j ← γ • n j forall (c k , n k ) ∈ OCH do q ∼ Bernoulli σ(π -π k + φ) • π if q = 1 then OCH ← OCH \ {(c k , n k )}

Meanwhile, OCH approximates probability distribution p(x) as:

EQUATION

where

N = i n i , π i = n i /N , and V(x|c) is the bin or neighborhood of c with V(x|c)dx = 1.

The right-hand-side of ( 4) is clearly differentiable with respect to π j , while a set of random samples from p(x) is not differentiable. Given a new input data, OCH changes only one count of the nearest codevector. Therefore, if n N , the difference of OCH for a new input vector is approximately:

δp(x) i δπ i V(x|c i ) (5) αV(x|c ) (6)

where c is the nearest codevector to the input vector, α = δn /N, and δn is the difference of the count of c . When OCH creates a new codevector, δn is n . Here, we used the fact that codevectors are invariant for input data, so V(x|c i ) is also invariant. This property is useful when the linear operator g(•) is applied to p(x). By definition of linear operator, g(p(x)

) = i π i g(V(x|c i )), then its difference is δg(p(x)) = i δπ i g(V(x|c i )) = αg(V(x|c )).

4. DIFFERENTIABLE BAYESIAN NEURAL NETWORK INFERENCE:

When a data stream S = {. . . , x } is given, where each subsequent data sample changes continuously, the prediction of a NN for S also changes continuously, i.e., p(y) → p(y) + δp(y), because a NN (with continuous activation) is a homeomorphism. We show that δp(y) is approximately proportional to the prediction of a NN augmented with OCH to the input and output for the recent data x . Figure 1 shows the structure of DBNN, where DNN is augmented with OCHs as distribution estimator units of input and output stream. DBNN calculates predictive uncertainty as well as the predictive result using the weighted ensemble of output codevectors.

4.1. DIFFERENTIATION OF BAYESIAN NEURAL NETWORK INFERENCE AS DIFFERENCE OF PREDICTION:

It is challenging to calculate the difference of (1) for a new data x from S. The differentiation of p(y|x , w) with respect to x is analytically intractable, because the samples from the probability of the data stream p(x|S) are discrete, although p(x|S) varies continuously. In other words, ∂ x p(y|x , w) = p(y|x, w)∂ x δ(x -x )dx where δ(•) is the delta function, and the delta function is not differentiable. To address this issue, DBNN smoothens the delta function of the data To calculate (8), we use OCH and (4) to represent p(z|S), and call it OCH Z :

p(y|S) i π i p(y|z)V(z|c i )dz (9)

where π i is weight of codevector c i and proportional to the count of the codevector. V(z|c i ) is neighborhood of c i . Then, δp(y|S) can be approximated by changing the weight of the codevector nearest to x as:

EQUATION

according to the (6). This means that p(y|z)V(z|c i )dz is invariant with respect to the change of S, i.e., δ p(y|z)V(z|c i )dz = 0, since histogram only changes its counts, not the codevectors. We approximate V(z|c ) as delta-function distribution at c , i.e., V(z|c ) δ(z -c ):

EQUATION

It is safe to assume that p(y|c ) is dominantly distributed near NN(c ), i.e., p(y|c ) V y|NN(c ) , because the expected value of y should be equal to NN(c ):

EQUATION

where NN(c ) is prediction of DNN for c . This result is equal to the changes of OCH when we update OCH for data, as (6) expresses. In conclusion, the difference of the DBNN prediction contributes only to the neighborhood of the DNN prediction for the codevector in OCH Z approximately. 

w ∼ OCH W z ← (x , w ) OCH Z ← Update OCH Z for z if new codevector c i exists in OCH Z then y i = NN(c i ) T ← T ∪ {c i → y i } c ← Search the nearest neighbor codevector to x in OCH Z y ← T (c ) OCH Y ← Update OCH Y for y with count α 4.2 IMPLEMENTATION OF DIFFERENTIABLE BAYESIAN NEURAL NETWORK INFERENCE

DBNN is composed of three stages and Algorithm 2 describes the DBNN inference process in detail as follows: (a) First, to estimate the probability of the input data stream, the algorithm updates OCH Z for z = (x , w ) where x is an input data and w is a random sample from given approximated posterior distribution OCH Z which represents the given p(w). OCH W consists of weights sampled from trained p(w) using MCMC. OCH Z and OCH Y are initialized to empty sets. (b) Second, if OCH Z generated a new codevector in OCH Z , DBNN generates the prediction for the new codevector using DNN and keeps the prediction in a cache table. As a result, the cache table contains the results of DNN corresponding to all codevectors in OCH Z . (c) Third, DBNN finds the nearest neighbor codevector to x in OCH Z , looks up the corresponding prediction in the cache table and update OCH Y for the prediction for the codevector. In conclusion, OCH Z approximating p(z|S) consists of recent data and weights from posterior. OCH Y approximating p(y|S) consists of recent predictions.

DBNN calculates the difference of prediction for a new data sample from the previous predictions. In the process, it executes DNN once if necessary, which is computationally expensive, in contrast to BNNs' repetitive execution DNNs. Furthermore, DBNN sometimes does not execute DNN, but only updates OCH Z and OCH Y for the input and output vectors, by updating the counts and estimates prediction and uncertainty based on cached results. The dominant part of the computational cost of updating OCH Z is the inner product of a given input vector, i.e., a • z, for nearest neighbor search. Given z = (x, w) and a = (a 0 , a 1 ), a • z = a 0 • x + a 1 • w holds. The codevector samples w from OCH W is fixed and finite, and DBNN caches all a 1 • w. Therefore, the average computational cost on a 1 • w is minuscule, when updating OCH Z . In conclusion, the upper bound of the computational complexity of DBNN inference is O(dim(x) log K Z + NN(•) + dim(y) log K Y ) where O(NN(•)) is computational complexity of NN and K Z and K Y are hyperparameters K of OCH Z and OCH Y , respectively. Modern deep NN performs vector operations dozens of times, if not hundreds, so the computation time of OCH is very small compared to DNN execution.

DBNN uses the flexible parametric probability estimator OCH to represent the distributions of input and output vector streams. Unlike the most BNNs that depend on a parameterized model described in (2), DBNN does not depend on the specific model. OCH represents both continuous and discrete vector spaces, and so does DBNN. If DNN and posterior are given, we can easily convert them to DBNN without significant modifications: just add OCH to the input and output of a DNN to estimate the probability of the input and output vector streams.

5. EXPERIMENTS:

Although DBNN uses assumptions that seem reasonable, it is necessary to measure empirical performances to show that this assumption works for real-world problems. This section evaluates the performance of DBNN in three set of experiments. The first experiment visualizes the characteristics of DBNN by performing simple linear regression on synthetic data. The second experiment classifies various real-world multivariate datasets using shallow and narrow NNs. This experiment shows the difference between computational and predictive performance of BNN and DBNN under various conditions when converting BNN to DBNN using small NN. The third experiment performs semantic segmentation on real-world video sequences. This experiment compares the performances of DBNN with other baselines when using a deep and wide modern NNs in practical situation.

We use the following four methods as baselines:

• DNN. Let Softmax(y ) be probability of NN where y is DNN logits. It is easy to implement, but it differs from the actual classification probability when the NN is deepened, broadened, and regularized well (Guo et al., 2017) .

• Model Uncertainty (MU). BNN is referred to as MU in this section since it introduces model uncertainty to NN. MU have to calculate (3) to predict the result. It is difficult to analytically determine the number of samples that the prediction converges. Instead, in section 5.1 and section 5.2, we experimentally set the number of samples from posterior to 30 so that the accuracy and the negative log-likelihood (NLL) converge. In section 5.3, MU containing MC dropout (Gal & Ghahramani, 2016 ) layers predicts results with 30 forward passes. Appendix E shows the performance of the MU for different numbers of forward passes.

• Data Uncertainty (DU). DU is a method that assigns only data uncertainty to DNN by adding OCHs to input and output of trained DNN. In other words, it uses one weight instead of weight distribution in the DBNN, i.e., (8) with p(w) = δ(w -w ). This method shows the effect of OCH on prediction when it is applied to the NN. Also, it shows that DNNs modified using OCH can achieve higher uncertainty than vanilla DNNs in semantic segmentation experiment.

• DBNN. DBNN takes both data uncertainty and model uncertainty. DBNN adds OCH to the input and output of trained BNN. In section 5.1 and section 5.2, the approximated posterior distribution of this method OCH W consists of 30 samples from the BNN's posterior.

5.1. SIMPLE LINEAR REGRESSION:

A neural network with a linear activation function is a linear regression model y = w 0 x + w 1 . The posterior is given by p(w 0 ) = N (1.0, 0.02 2 ) and p(w 1 ) = N (0.0, 0.2 2 ). The distribution of time-varying input data streams is given by p(x|t) = δ(x -vt) where t is integer timestamp from t = -10. v is 0.3 and 0.03. The top of figs. 2a to 2d are approximated distributions of input and weight samples p(x, w 0 ) and bottom are approximated distributions of output samples with data p(x, y) at t = 0. w 1 is omitted from w in these figures, but it behaves like w 0 . To predict result, DNN uses point-estimated weight and data x = 0, which is the data at t = 0. MU uses weight distribution, instead of point-estimated weight, and data x = 0. DU uses point-estimated weight, which is the same as DNN. However, since DU contains OCHs, it uses not only the most recent data (x = 0 at t = 0) but also past data (x < 0 when t < 0). As a result, DU predicts the distribution of y. DBNN predicts the distribution of y using both weight distribution and data from the past to now. DBNN without distribution of x is equivalent to MU, and DBNN without distribution of w is equivalent to DU. 

5.2. CLASSIFICATION ON MULTIVARIATE DATASETS:

A classification experiment is designed to compare computational and predictive performance changes when converting BNNs to DBNNs using shallow and narrow NNs in various situations. In this experiment, we use three time-series real-world datasets with input dimensions between 4 and 8.

Localization and EMG dataset have relatively large number of classes, eleven and eight respectively while Occupancy dataset has only two classes. The NNs consist of 2 fully-connected hidden layers with 50 units. The distributions of weights are optimized using variational inference. See appendix A for more information about experimental settings and datasets.

Computational Performance. Execution times for one batch of MU and DBNN are 26.7±10.6ms and 19.5±10.0ms, respectively. MU parallelizes execution by using a batch size of 30. This result shows that DBNN is 37% faster than MU even though MU is parallelized and DBNN uses additional OCHs. DBNN improves the computational performance of DBNN by sampling the weights from the posterior before testing. As NN gets deeper and larger, the execution time of the DBNN will be reduced compared to the MU, because the larger the NN, the greater the burden of sampling weights.2 

Predictive Performance. As shown in Table 1 , we compared MU and DBNN in terms of the rootmean-square error (RMSE), RMSE for predictive results with confidence above 90% (RMSE-90), negative log-likelihood (NLL), and the percentage of predictive results with confidence above 90% (Cov-90) of the MU and DBNN for three datasets. DBNN is more accurate than MU and predicts uncertainty better than MU on Localization and EMG datasets. DBNN predicts less accurately than MU on Occupancy dataset with comparable uncertainties. The confidence of DBNN is always less than or equal to that of MU. Overall, DBNN provides predictive performance comparable to BNN on various datasets. (Ronneberger et al., 2015) as the backbone architecture. Bayesian U-Net, similar to Kendall et al. (2015) , contains MC dropout (Gal & Ghahramani, 2016 ) layers. For more information about experimental settings, see appendix A.

Computational Performance. The throughput (Thr) column of table 2 shows the number of video frames processed by each model per second. This table shows that DNN takes 162±12ms on average to process one frame. In comparison, DBNN takes 191±70ms on average to process one frame, which is only 17% higher than DNN. According to the difference between the execution time of DNN and DU, the average execution time of one OCH is 14ms, which is only 7% of the total. Besides, due to GPU memory limitations, the batch size of MU is limited to 1. Thus, the MU predicts results for 30 batches of size 1. In conclusion, the execution time of MU is 5291±69ms, which is 32× higher than that of DNN, and 27× higher than that of DBNN. Moreover, DBNN can increase throughput at the expense of accuracy by adjusting a hyperparameter. See appendix C for more information.

Predictive Performance. The Acc to Cov-90 columns of the table 2 show the quantitative comparison of the predictive performance for each method. We measure global pixel accuracy (Acc), mean intersection over unit (IoU), and negative log-likelihood (NLL). At the same time, we selected only those pixels with confidence greater than 90% and measure the accuracy (Acc-90), i.e., p(accurate|confident), and IoU (IoU-90). We also measure the probability that the pixel is not 90% confident pixel when prediction is incorrect (Unc-90), i.e., p(unconfident|inaccurate), and the percentage of pixels with 90% confidence (Cov-90).

According to this table, the accuracies of DU and DBNN are 0.46% and 0.69% lower than that of DNN and MU, respectively. For pixels with ninety-percent or higher confidence, DNN, MU, DU, and DBNN predicts with 3.8%, 7.6%, 7.1%, and 7.5% higher accuracy, respectively, compared to the accuracy for all pixels. MU, DU and DBNN improves the accuracy more than DNN for confident pixels, which means that MU and DBNN estimates high uncertainty for misclassified region. IoUs for certain pixels increase by 6.8%, 14%, 10%, 16%, respectively, compared to the IoUs for all pixels, which shows the same trend as in accuracy.

As shown in this results, DNN is the most improper way to distinguish uncertain pixels because it has the least performance improvement compared to other methods for pixels with high confidence. On the other hand, MU has the highest performance improvement compared to DNN when considering all pixels, and it also has the highest performance for certain pixels. DBNN has improved performance for certain pixels, similar to MU. The predictive performance of DU for all pixels is similar to the predictive performance of DNN, but for certain pixels, the performance is much better than that of DNN. See appendix D for more information on semantic segmentation experiment. With a small number of forward passes, BNN can reduce computational overhead at the expense of predictive performance. To achieve equivalent performance to DBNN in uncertainty measures, MU requires 10 forward passes. See appendix E for more details.

6. CONCLUSION:

We present a differentiable BNN (DBNN) inference with respect to input data, which is a novel approximation of BNN inference, to improve the computational performance of BNN inference for data streams. The derivative of DBNN predictive inference with respect to input data derives the increment of prediction when one data is newly given from the data stream. However, the inference of vanilla BNN cannot be differentiated with respect to data. To address this issue, DBNN introduce a new term that is the probability of data streams in the BNN inference. Then, it approximate its prediction with a histogram for high-dimensional vector streams. Consequently, the DBNN inference executes DNN only once to calculate the prediction changed by a new data from data streams. This results in an order of magnitude times improvement in computational performance compared to deep BNN. Experiments with semantic segmentation using real-world datasets show that the computational performance of DBNN is almost the same as that of DNN, and uncertainty is comparable to that of BNN. Classification on Multivariate Datasets. In section 5.2, we train BNNs with Adam with a constant learning rate of 0.001 using ELBO loss. We set the batch size to 30. The BNN consist of 2 fullyconnected layers with 50 units using Flipout estimator (Wen et al., 2018) . We set hyperparameters K, λ, and σ(φ) to 10, 1.3, and 1.0, respectively, in all OCHs of DBNN; this is the same configuration in the semantic segmentation experiment.

We use the following time-sequential real-world dataset for classification in section 5.2: Localization Data for Person Activity Dataset (Kaluža et al., 2010) , Occupancy Detection Dataset (Candanedo & Feldheim, 2016) , and EMG Data for Gestures Dataset (Lobov et al., 2018) . If there are no distinction between the test set and the training set, NNs use 90% of the dataset for training and the rest for testing. NNs test the datasets in time-sequential order. See table 3 for more information about datasets.

Semantic Segmentation. In section 5.3 and appendix D, NNs are trained using categorical crossentropy loss, with RMSprop with a constant learning rate of 0.0001 and discounting factor of 0.995. Batch size is limited to 1 because of memory limitations. In these experiments, we use U-Net (Ronneberger et al., 2015) based on VGG-16 (Simonyan & Zisserman, 2014) . Bayesian U-Net, similar to Kendall et al. (2015) , contains six MC dropout (Gal & Ghahramani, 2016) layers behind the layers that receives the smallest input vector sizes. The overhead of dropout layers are negligible and DBNN always uses a new dropout every time it predicts a result. To optimize the predictive performances, we set hyperparameters K, λ, and σ(φ) to 10, 1.3, and 1.0, respectively, in all OCHs of DU and DBNN. See appendix C for the change in NLL with hyperparameters. To improve computational performance, OCH Y executes nearest neighbor search for arg max of y with respect to the classes.

We use CamVid dataset (Brostow et al., 2009) and CityScape dataset (Cordts et al., 2016) 

B COMPUTATIONAL PERFORMANCE FOR NEURAL NETWORK DEPTH:

Figure 3 shows a trend that the execution time of MU and DBNN increases as hidden layers get deeper without changing the input and output dimensions. In this case, as in section 5.2, NN consists of 50 units of fully-connected hidden layers, with input and output dimensions of 4 and 11, respectively. MU and DBNN use batches of size 30 and 1, respectively, but execution time is the same even if MU uses batch size of 1. According to this figure, when the number of hidden layers is 0, the execution time of DBNN is 15.1±6.7ms, which is 4.6ms slower than MU. This is because DBNN uses two additional OCHs compared to MU. However, unlike MU, DBNN does not sample the weight in the posterior when it predicts the result. Therefore, the increase of execution time of DBNN per layer is lower than that of MU. As a result, the execution time of the MU increases by 8.6ms while that of DBNN increases by 3.5ms when one layer is added. When the number of hidden layers is 10, the execution time of MU and DBNN is 98.9±20.1ms and 49.0±23.6ms, respectively-DBNN is 2.02× faster than MU.

C PREDICTIVE PERFORMANCE FOR HYPERPARAMETERS DBNN has three hyperparameters; K, λ, and σ(φ), in the input and output OCHs. The first to third figures in fig. 4 shows how NLL changes over the variuos hyperparameters of the output OCH in semantic segmentation. As shown in this figure, as K increases, NLL decreases, and the NLL stagnates when K goes over 15. The lower the λ, the lower the NLL, until 0.7. The higher the σ(φ), the lower the NLL. The effect of hyperparameters of the input OCH is the similar trend as that of the output OCH.

With high K and and low λ, DBNN maintains more codevectors-recent frames in video sequence and obtains more accurate model uncertainty using more codevectors. As a result, at high K and low λ, DBNN exhibits lower NLL. When K and λ get lower than a certain point (λ = 0.7 in this example), however, the data uncertainty is too high to estimate results. NLL is minimized when model uncertainty and data uncertainty are balanced. On the other hand, if σ(φ) is low, DBNN mostly adjusts the weights of codevectors and occasionally adds new codevectors. This results in the DBNN becoming inaccurate, but the calculation is faster. Predictive Performance of Models for Datasets. Table 4 shows the computational and predictive performance of various methods on the CityScape dataset. We measure the followings as in section 5.3: throughput (Thr), global pixel accuracy (Acc), accuracy for 90% certain pixels (Acc-90), the probability that the pixel is not 90% certain pixel when prediction is incorrect (Unc-90), mean intersection over unit (IoU), IoU for 90% certain pixels (IoU-90), negative log-likelihood (NLL), and the ratio of 90% certain pixels (Cov-90).

Accuracy:

Table 4 implies the followings: First, The computational performance of DNN and DBNN are relatively comparable, and that of DBNN is significantly higher than that of MU. Second, the predictive performances of DU and DBNN for all pixels is lower than that of DNN and BNN, respectively. Third, predictive performances for certain pixels and other measures for uncertainties of MU and DBNN are comparable. These results are consistent with the result of section 5.3.

Extended Analysis of Confidence and Accuracy. Figure 5 shows confidence histograms (Guo et al., 2017) and reliability diagrams (DeGroot & Fienberg, 1983; Niculescu-Mizil & Caruana, 2005; Naeini et al., 2015; Guo et al., 2017) of U-Net on the CamVid dataset. A confidence histogram shows proportion of samples for confidence as a histogram. The reliability diagram is a histogram of accuracy for confidence. We also measure the Expected Calibration Error (ECE) (Naeini et al., 2015; Guo et al., 2017) , which is defined as follows for the reliability diagram:

EQUATION

where |B i | is the number of samples in bin B i , M = i |B i |, acc(B i ) is mean accuracy of samples in B i , and conf(B i ) is mean confidence of samples in B i . ECE stands for the difference between confidence and accuracy. ECEs of DNN, MU, DU, and DBNN are 7.43%, 4.27%, 5.86%, and 5.13%, respectively.

As shown in fig. 5a , DNN is overconfident and miscalibrated; its confidence is generally high and there is significant discrepancy between confidence and accuracy. On the other hand, MU is underconfident and well-calibrated. DBNN is more under-confident than MU, and the confidence of DBNN is calibrated relatively comparable to that of MU. Also, DU calibrates the confidence of DNN. In conclusion, the confidence of DBNN is well-calibrated, whild the confidence of the DNN is relatively unreliabl. These are consistent with the results of the predictive performance.

Qualitative Results. Figure 6 shows the qualitative comparison of the predictions for each method.

According to this figure, DNN is overconfident, i.e., confidence is generally high, and uncertainty is mostly distributed at the boundaries of the classified chunks. Even when DNN generates wrong prediction, the confidence level is very high. The uncertainty of MU is distributed on the boundaries as in the case of the DNN, but is also distributed in the misclassified areas. The uncertainty of DU differs from that of DNN. First, DU is under-confident compared to DNN. Second, although DU does not identify all of the misclassifications compared to MU, it sometimes estimates high uncertainty in the misclassified areas. The uncertainty of DBNN is similar to the MU as we expected.

E PERFORMANCE OF BNN FOR NUMBER OF FORWARD PASSES BNNs, i.e., MUs, in section 5.3 and appendix D contain MC dropout (Gal & Ghahramani, 2016) layers and require multiple forward passes to predict result. Table 5 shows the computational and predictive performance of the Bayesian U-Net for the number of forward passes on the CamVid dataset.

According to table 5, the predictive performance of MU improves up to 30 forward passes. However, there is little difference between the predictive performance for 30 forward passes and for 50 forward passes. MU requires at least 30 forward passes to get the best predictive performance, so we execute 30 predictive inference in section 5.3 and appendix D.

Meanwhile, to achieve the same uncertainty measures as DBNN, MU requires 10 forward passes. In particular, Unc-90 of DBNN has always outperformed that of MU. For the improvement rate from Acc and IoU to Acc-90 and IoU-90, the uncertainty of DBNN is the same as that of MU with 30 forward passes.

:

The delay of the expected value of y over time does not mean that the regression result is biased. DBNN estimates the correct value on average since z is also delayed just as y is delayed.

Execution times of MU and DBNN with 10 fully-connected hidden layer NN are 98.9±20.1ms and 49.0±23.6ms, respectively. In this case, DBNN is 2.02× faster than MU. See appendix B for more information about the relationship between NN depth and execution time.

Code available at https://anonymous.4open.science/r/dbnn/

Figures and Tables:

Figure 1: DBNN Inference. OCHs are added to the DNN to estimate the probabilities of input and output vector streams. Given a new data, OCH Z adjusts the weight (arrows) of the nearest codevector of OCH Z representing the input vector stream. DBNN adjusts weights of the codevectors of the OCH Y representing the predictive distribution based on the results of the inner DNN. DBNN derives predictive result and uncertainty from the weighted ensemble of the codevectors of OCH Y .

Figure 2: Simple linear regression on synthetic dataset. In figs. 2a to 2d, the top is the approximated input probability p(x, w 0 ) and the bottom is the approximated output probability with data p(x, y) at t = 0 with v = 0.3. In these figures, fig. 2a and fig. 2b are samples from the distribution, and fig. 2c and fig. 2d are distributions approximated by OCH Z and OCH Y . The sizes of the circles represents the importance weights of each codevector. Figures 2e to 2f are the expected values and standard deviations of y depending on the timestamp for different v. The black dotted lines represent true values. The error is 90% confidence interval.

The figs. 2e to 2f show expected value and standard deviation of DBNN prediction on time. First, as shown in top of fig.2e, the result of DBNN lags behind since DBNN smoothens its prediction with respect to time. 1 Second, unlike MU uses dozens of samples, DBNN uses a small number of samples, so the error is relatively large. Third, as shown in bottom of fig.2e, the DBNN prediction is under-confident because DBNN considers not only MU but also DU. Fourth, as shown in the comparison of fig.2eand fig.2f, DBNN converges to BNN and DU converges to DNN as the input data stream changes more slowly.

Figure 3: Prediction execution time of MU and DBNN for the number of hidden layers. The execution times increase linearly as the layer increases. If the number of hidden layers is 0, DBNN is slower than MU, but as the number of hidden layers increases, DBNN is faster than MU. The increase rates of execution times of MU and DBNN are 8.6ms/layer and 3.5ms/layer, respectively.

Throughput Trade-off. If σ(φ) is less than 1.0, DBNN occasionally adds a new codevector to the input OCH and executes NN, at the rate of σ(φ) on average. Since NN occupies the most of the execution time of DBNN, throughput decreases when σ(φ) decreases. The fourth figure in fig.4shows the changes in throughput and NLL as σ(φ) changes. According to this figure, DBNN can increase throughput up to 12fps when it achieves same NLL as DNN. In this case, DBNN is 2×

Algorithm 2: DBNN Inference input :input data vector x , deterministic neural network NN(•), posterior distribution OCH W , distribution of input vector OCH Z , distribution of output vector OCH Y , cache table T initialized to empty set output :updated distribution of input vector OCH Z , updated distribution of output vector OCH Y

Table content: <table/>

Predictive performance of MU and DBNN for classification on multivariate datasets.

Table content: <table><tr><td>Dataset</td><td colspan="2">RMSE</td><td colspan="2">RMSE-90</td><td/><td>NLL</td><td>Cov-90</td></tr><tr><td/><td>MU</td><td>DBNN</td><td>MU</td><td>DBNN</td><td>MU</td><td>DBNN MU DBNN</td></tr><tr><td colspan="7">Localization 0.228 0.212 0.118 0.085 1.252 1.084 13.1</td><td>3.11</td></tr><tr><td>EMG</td><td colspan="6">0.260 0.249 0.204 0.203 0.955 0.935 10.8</td><td>9.91</td></tr><tr><td>Occupancy</td><td colspan="6">0.134 0.152 0.071 0.076 0.071 0.081 90.1</td><td>90.1</td></tr></table>

Computational and predictive performance with semantic segmentation for each method.

Table content: <table><tr><td colspan="9">Method Thr (fps) Acc Acc-90 Unc-90 IoU IoU-90 NLL Cov-90</td></tr><tr><td>DNN</td><td>6.14</td><td>85.8</td><td>89.1</td><td>30.4</td><td>58.5</td><td>62.5</td><td>1.22</td><td>93.1</td></tr><tr><td>MU</td><td>0.189</td><td>86.4</td><td>93.0</td><td>60.1</td><td>61.0</td><td>69.9</td><td>0.728</td><td>84.2</td></tr><tr><td>DU</td><td>5.33</td><td>85.4</td><td>91.5</td><td>51.3</td><td>57.3</td><td>63.3</td><td>0.980</td><td>86.0</td></tr><tr><td>DBNN</td><td>5.22</td><td>85.8</td><td>92.3</td><td>63.0</td><td>58.9</td><td>68.6</td><td>0.826</td><td>80.4</td></tr><tr><td colspan="3">5.3 SEMANTIC SEGMENTATION</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="9">Semantic segmentation experiment shows the computational and predictive performance of DBNN</td></tr><tr><td colspan="9">with a modern deep NN in practical situation. We use CamVid dataset (Brostow et al., 2009) consisting</td></tr><tr><td colspan="9">of 30 frame-per-second (fps) video sequences of real-world day and dusk road scenes. We use the</td></tr><tr><td>U-Net</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Input dimensionalities (dim (x)), output dimensionalities (dim (y)), and number of training sets (N ) of dataset used in the experiments. conduct all the experiments with the Intel Xeon W-2123 Processor, 32GB memory, and a single GeForce RTX 2080 Ti. NN models are implemented in TensorFlow(Abadi et al., 2016). 3

Table content: <table><tr><td>Dataset</td><td>dim (x)</td><td>dim (y)</td><td>N</td></tr><tr><td>Localization</td><td>4</td><td>11</td><td>148373</td></tr><tr><td>Occupancy</td><td>5</td><td>2</td><td>8143</td></tr><tr><td>EMG</td><td>8</td><td>8</td><td>3793345</td></tr><tr><td>CamVid</td><td>720×960×3</td><td>720×960×32</td><td>421</td></tr><tr><td>CityScape</td><td colspan="2">512×1024×3 512×1024×35</td><td>2975</td></tr><tr><td colspan="3">A EXPERIMENTAL SETUP AND DATASETS</td><td/></tr></table>

in the semantic segmentation experiments. We feed sequential images to DBNN and DU before evaluation since DU and DBNN use multiple previous images. For the CamVid dataset, we resized images to 720×960 pixel bilinearly from 360×480 pixels. Since some test sets do not have previous sequences, we use only 70 of 168 test sets in the CamVid dataset. For CityScape dataset, we use validation set, which was not used during training, as test set because only the video sequence corresponding to the validation set has been disclosed. See table3for more information about datasets.

Table content: <table/>

Computational and predictive performance with semantic segmentation on the CityScape dataset. Conversely, DBNN can update a batch of two or more sizes instead of one. In this case, throughput of DBNN decreases but NLL increases (not shown in this figure).D EXTENDED INFORMATIONS OF SEMANTIC SEGMENTATION EXPERIMENTSection 5.3 shows the performance with semantic segmentation on the CamVid dataset. This section shows the performance on the CityScape dataset, another real-world road scene video sequence. Furthermore, we analyze the predictive performances of DNN, MU, DU, and DBNN in more detail.

Table content: <table><tr><td colspan="9">Method Thr (fps) Acc Acc-90 Unc-90 IoU IoU-90 NLL Cov-90</td></tr><tr><td>DNN</td><td>7.09</td><td>89.3</td><td>93.8</td><td>55.3</td><td>61.3</td><td>72.6</td><td>0.569</td><td>89.7</td></tr><tr><td>MU</td><td>0.236</td><td>89.2</td><td>95.9</td><td>74.8</td><td>61.5</td><td>79.3</td><td>0.382</td><td>84.2</td></tr><tr><td>DU</td><td>5.88</td><td>87.5</td><td>94.3</td><td>67.5</td><td>56.9</td><td>69.8</td><td>0.567</td><td>82.8</td></tr><tr><td>DBNN</td><td>5.89</td><td>87.2</td><td>95.4</td><td>76.8</td><td>56.4</td><td>72.0</td><td>0.452</td><td>78.2</td></tr><tr><td>faster than DNN.</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Computational and predictive performance of U-Net with semantic segmentation for each method and number of forward passes (N y ) on CamVid dataset.Method Ny Thr (fps) Acc Acc-90 Unc-90 IoU IoU-90 NLL Cov-90

Table content: <table><tr><td/><td>1</td><td>6.06</td><td>85.8</td><td>89.9</td><td>40.1</td><td>59.8</td><td>65.4</td><td>1.00</td><td>90.0</td></tr><tr><td/><td>2</td><td>2.97</td><td>86.1</td><td>91.3</td><td>50.7</td><td>60.3</td><td>67.6</td><td>0.892</td><td>87.0</td></tr><tr><td>MU</td><td>5 10</td><td>1.16 0.580</td><td>86.3 86.4</td><td>92.0 92.4</td><td>56.6 59.5</td><td>60.7 60.9</td><td>68.9 69.6</td><td>0.827 0.768</td><td>84.9 84.3</td></tr><tr><td/><td>30</td><td>0.189</td><td>86.4</td><td>93.0</td><td>60.1</td><td>61.0</td><td>69.9</td><td>0.728</td><td>84.2</td></tr><tr><td/><td>50</td><td>0.115</td><td>86.4</td><td>93.0</td><td>60.3</td><td>61.0</td><td>70.1</td><td>0.721</td><td>84.2</td></tr><tr><td>DBNN</td><td>1.0</td><td>5.22</td><td>85.8</td><td>92.3</td><td>63.0</td><td>58.9</td><td>68.6</td><td>0.826</td><td>80.4</td></tr></table>

Peer review (iclr2020):
This paper proposed differentiable Bayesian neural networks (DBNN) to speed up inference in an online setting. The idea is to combine online vector quantization with Bayesian neural networks (BNN), so that only incremental computation is needed for a new data point. It seems the idea of online codevector histogram, or online vector histogram, is not new, which is not surprising since the original codevector histogram work is from decades ago (1982). A quick search shows several related work in this domain, e.g., ‘An Online Incremental Learning Vector Quantization’. It would be better if the authors could clarify the differences if they want to claim the contribution. One of my major concerns is the fairness in terms of comparison to BNN approaches. For example, in Table 2, BNN (shown as MU) is significantly slower than DU/DBNN and DNN. The authors mentioned that this is because MU predicts results for 10 batches of size 3, and therefore 30 times slower. Since DU and DBNN also uses MC-dropout, why is this not an issue for DU/DBNN. Such large overhead is also inconsistent with the description in Section 5.3, saying that the ‘overhead of sampling weights is negligible’. Could the authors elaborate on this? A related problem for clarification: it is mentioned before Section 5.1 that 30 samples are drawn from the BNN’s posterior. Do you mean 30 feedforward passes of MC-dropout, as done in the MC-dropout paper? Also, the authors should have made it clear that they are using MC-dropout as a BNN. In the introduction, the authors motivate the proposed DBNN by saying that BNN needs dozens of samples from weight distributions and therefore is rather inefficient. However, there are a lot of modern BNN that are both sampling-free and differentiable. For example, natural-parameter networks (NPN) parameterize both the weight and neuron distributions using natural parameters. Even the earlier work, probabilistic BP (PBP), as cited in the current paper, also counts as sampling-free. The claim of ‘being differentiable’ without acknowledging prior work is rather misleading. The point above is also related to the MU baseline in Table 2. The issue of needing 30 passes can be readily resolved if modern BNN such as NPN (or PBP), which takes only one pass, is used. The organization could be improved to make the paper more readable. It would be better if the problem setting of online inference is introduced at the beginning, followed by the overview of DBNN and then the OCH details. Otherwise, it is not clear what the focus of DBNN is, until Section 4. Minor: It might be better to denote the weight as ‘w’ rather than ‘x’, to avoid confusion.