Data-driven deep density estimation

Basic models fit parametric functions such as lines or Gaussians to the sample, but real data are typically of a more complex shape and mixtures of parametric curves are required [9]. Another straightforward solution is to construct discrete histograms with finite-sized bins around centers \(c_i\) and counting how many sample points fall into each bin. A high count corresponds to a high value \(p(c_i)\). This does not scale well with the number of dimensions, as it requires exponential memory, does not produce a continuous result as only discrete centers are domained, and choosing the bin size can be difficult [32].

Histogram binning is a special case of KDE, where the hard counting is replaced by a compact and soft (e.g., Gaussian or Epanechnikov) kernel \(K(||x_i- x||/h)\) that weights the contribution of sample point \(x_i\) to a continuous coordinate x. KDE has one control parameter h, called the bandwidth of the kernel. Choosing h can be difficult: if it is too small the result is noisy; if it is too large the result may turn out overly smooth. Picking the optimal h is easy if p is known, but typically we do not have access to p. In practice, the easiest way to choose h is based on heuristics due to Silverman [34] that account for the number of points and the domain dimension. More sophisticated methods were suggested to pick the right bandwidth when making prior assumptions on p such as smoothness or sparsity [17]. These are however only applicable if p fits the assumptions, they struggle with computational efficiency and fail for cases where there is no constant bandwidth h to explain the entire sample. While the time complexity of vanilla KDE is only \({\mathcal {O}}(n)\), it can be as large as \({\mathcal {O}}(n^2)\) for a KDE with sophisticated bandwidth selection algorithms [38]. A more sophisticated method for density estimation is the nonparametric PDF estimator by Farmer and Jacobs [13]. While it can be applied without the need of fine-tuning parameters such as the bandwidth in KDE and produces good results, it is only applicable for 1D distributions.

The most common approach for neural density estimation is the utilization of Gaussian mixture models [10] or their addition the variational Bayesian Gaussian mixture models [4]. However, they require large distributions in order to estimate complex PDFs well enough. Also neural networks have been used to model density estimation for cases where the PDFs p is known and can be used during supervision [2, 24]. Regrettably, we rarely know the PDF of most natural signals: no supervision is available when for instance discovering novel dynamics, group formations, or particle events. Consequently, these methods are limited to estimate density if the PDF is known. While such models are also applied without access to the true PDF [23], the training target for these cases is just generated using KDE or other density estimators, which essentially just shifts the problem from estimating densities to learning KDE, which will hardly ever produce better results than KDE can.

Unsupervised methods that only require access to the sample but not to the PDF, have also been proposed [14, 25, 26]. Here, the network itself represents the PDF, and—while more complex than a linear, Gaussian or parametric mixture model—this essentially is a fit of a network to the data in one sample. This means a new network is trained for every sample. Fortunately, this makes little assumptions, but regrettably, at the expense of quality as it fails to capture the essence of learning: representing previous knowledge relevant for a task; nothing discovered in one sample will ever contribute to density estimation of another sample.

The architecture of our DDE approach is illustrated in Fig. 1. The network takes as input the sample distribution \(S\subset {\mathcal {S}}\) for \({\mathcal {S}}=\prod _{i=1}^d[a_i, b_i]\) with \(a_i, b_i \in {\mathbb {R}}\) and \(a_i \le b_i\) and a set of query points \(Q\subset {\mathcal {S}}\). For the direct density estimation of each point in the distribution, both sets are the same. The first step is then the realization of a finite receptive field by calculating the distances to the k closest non-identical points \(x_i\in S\) to any query point \(x\in Q\) by either using a kd-tree, ball tree, or brute force. The latter is only beneficial because of the possibility of full parallelization on a GPU (graphics processing unit). This first step is what makes the network convolutional, as it convolves over the input with the size of the convolution determined by k. To achieve a model which can be applied to arbitrary datasets, the convolution is of uttermost importance. While a convolution could be realized by feeding the unstructured points by position, without a direct distance encoding, this would require at least a fine-tuning of the model architecture for any given dimensionality, as the complexity of the input will increase with dimensions.

The obtained distances are then fed into an MLP which predicts p(x). As the MLP is shared over all points, this becomes effectively a convolution with the MLP as convolution kernel and the kernel size defined by k. The specific layout of the MLP, i.e., its number and size of hidden layers, is not necessarily fixed but can be determined during each training session, where the resulting estimator is the best model out of an ensemble of trained models. While the value of k could give a bias on the estimate, with highly fluctuating values for small k and overly smoothed estimates for large k, we have found empirically that a value of \(k=128\) gives highly accurate results on a wide range of dimensionalities and sample sizes. The evaluation on the choice of k is discussed in Sect. 3.3. Thus, the most important difference to all prior approaches is that we designed the method such that it does not fit the model to S at hand, but uses only the learned information of the training set to predict p for S. While it would be possible to assign further one-dimensional convolutions on the distance input, we have found empirically that the MLP achieves the better results. For the exact architecture of the MLP we investigated three types of structures. The first started with an input layer with 2048, 1024, 512 or 256 nodes with every consecutive layer being equally large or smaller. The second started with an input layer of size 32, 64, 128 or 256, which extends to a hidden layer with a maximal size of 512, 1024 or 2048 nodes, before reducing to the output size of 1. The last type is similar to the first one, but uses a skip connection between every two consecutive layers, inspired by ResNet [16]. All of these models were tested with different numbers of hidden layers. Testing these along different sizes for k we have achieved the best results using the second type of models with \(k = 128\), 128 input neurons, 9 hidden layers with a maximum size of 512 and a doubling/halving of layer sizes, respectively, between each two consecutive layers.

This architecture results in a time complexity for DDE of \({\mathcal {O}}(n\log n)\), which is governed by the distance search. While the calculations from DDE to get the density estimate from distances are implemented in TensorFlow, and thus highly parallelized on the GPU, the time-wise most complex part, i.e., the distance search, is still implemented on the CPU (central processing unit).

For the training objective we used the mean squared error as loss function. Apart from that, we used conventional building blocks, whereby our model was trained with rectified linear units (RELU) [19] as activation function in every layer, with batch normalization [18] after every but the last layer, and to calculate the parameter update we used the Adam optimizer [21] with default parameters and exponential learning rate decay.

The output of the model in 1D is further smoothed by a univariate spline interpolation with a fixed order of the polynomial and an automated adaptive smoothing factor, making this amendment also fully automated. Such postprocessing is not conducted in higher dimensions, as we know of no existing method which can be automated, allowing for an unbiased way to return smoother but still accurate estimates over all applications.

The parameter for the number of neighbors fed into the network k was empirically found and set. Here, we briefly discuss how we determined \(k = 128\). As the choice of the parameter k is intertwined with the network architecture, especially the size of the first hidden layers, we present here only an example of the empirical analysis we conducted. This can be seen in Fig. 2, where we plot the Kullback–Leibler (KL) divergence against the parameter k for 1D and 3D. Note that these models show slightly poorer estimates in 1D and even poorer ones in 3D than the ones discussed in the rest of this paper, as they were trained much shorter, which also leads to the rather large noise regarding different k. The model trained here differed only in the number of k for the convolutional window, but had the same architecture otherwise, with the first hidden layer of size 128. The significant performance loss for \(k \gtrapprox 135\) for 1D is attributed to this fact, as the lower size of the first hidden layer with respect to the input needs a fast information encoding already in the first layer, while for hidden layers larger than the input, the information can be “passed through” the first layers and be iteratively encoded by the entire network. While the former should be in general possible, in practice the model will be caught too quickly in a local optimum for the first layer. For our investigations we tested a large variety of different architectures with different layer sizes and numbers, which description would be beyond the scope of this paper. For the same reason our tests did not include densely sampled k, but such from a power 2 distribution (i.e., 16, 32, 64, 128, 256). Having that said, the final selection for k involved mainly the error metrics over the validation dataset, but as well the visual quality of the resulting estimates and the fact that k should not be too large, as it sets an ultimate bound on the lowest sample size possible to estimate. Regarding the error metrics we show the KL divergence in Fig. 2 on the top, where we can see first of a strong performance gain for larger k which asymptotically reaches a minimum for \(k \gtrapprox 60\), and as discussed above becomes worse again for \(k \gtrapprox 135\). This indicates that k could be selected as low as 64 according to the larger test series. In the next step, we also assessed the visual quality of the estimates (Fig. 2, bottom). We have analyzed unsmoothed estimates for \(k = 32\) (blue), for \(k = 64\) (orange) and for \(k = 128\) (green) in comparison with the true PDF (black), for 2 sample distributions of size 1000. The reason for choosing \(k = 128\) over \(k = 64\) can be seen in the lower sensitivity to the noise in the data; thus, the estimate for \(k = 128\) is smoother. An explanation to the empirically found constant optimal value for different dimensions is the fact that the model is trained for every dimensionality and takes only the scalar distance as input. Thus any dimension-specific dependency of the distances is inherently encoded by the network.

An additional problem of our estimates becomes visible in Fig. 2 (bottom), where we can see a false zero estimate on the tail of the distributions. Solving this problem requires the longer training times as well as the selection of the final model from a larger set of identical models, where the last step ensures that we rule out models which converged to bad local optima. While this seems like a rather time-intensive training, it should be noted that it is quickly surpassed by the generation of the training data, and that the model has to be trained only once for all future applications on the same domain dimensionality.

The gamma distribution \(p(x) = \frac{1}{\sqrt{\pi x}}e^{-x}\) presents the significant feature of a singularity at \(x\rightarrow 0\), shown in Fig. 6. Going through the estimators \(R_{{\rm nm}}\) fails in estimating the PDF for both tested distribution sizes, which is however not distinctively apparent in the numeric scores, as it finds a good estimate for the actual divergence. KDE can fit the tail of the distribution, but fails for the divergence, which is also represented by the bad scores in all metrics. FJE, while being the slowest method, finds a good estimate for the divergence, but cannot fit the overall shape of the PDF well. While DDE can estimate distribution well for most parts, it fails to fit the divergence for small distribution sizes. The smoothing has only a minor effect on DDE for this distribution.

The sum of two Gaussians distribution \(p(x) = \frac{7}{10}{\mathcal {N}}(x|\mu =5, \sigma =3) + \frac{3}{10}{\mathcal {N}}(x|\mu =0, \sigma =\frac{1}{2})\), where \({\mathcal {N}}\) denotes the Gaussian distribution with mean \(\mu\) and standard deviation \(\sigma\) is a standard multimodal distribution with soft tails, shown in Fig. 7. For this case, \(R_{{\rm nm}}\) finds a good estimate, which follows the general structure of the PDF, with some high-frequency errors. This is also apparent by the significantly small MSE and KL divergence and the large p value. While KDE can also reproduce the general structure of the PDF, both peaks are under-estimated, causing significantly lower scores. The quality of the FJE estimate is both visually and numerically in between those of KDE and \(R_{{\rm nm}}\). While ii recovers the general structure of the PDF also for \(n=500\), the sharp peak is still under-estimated, while the left bump is shifted and narrower than it should be. For \(n=5000\), the sharp peak is estimated well and the left bump is roughly estimated, while the shape here is more akin to actual features, as the bump is split in two, while the errors of \(R_{{\rm nm}}\) are more akin to noise. While DDE can estimate the structure of the PDF correctly, it estimates a wrong feature to the left of the strong peak for \(n=500\) and the tails vanish to quickly for both tested distribution sizes. Hence, the scores on MSE and KL divergence still show both, good results for both n, while the p value for \(n=500\) is quite low. Again the smoothing has only a minor, while visible and measurable effect.

The five fingers distribution \(p(x) = w\sum _{k=1}^5\frac{1}{5}{\mathcal {N}}(x|\mu =\frac{2k-1}{10},\sigma =\frac{1}{100}) + (1-w)\) with \(w=0.5\) contains five sharp Gaussian peaks, shown in Fig. 8. This type of distribution is a good test for estimators, as the sharp peaks and only local expression of the PDF with vanishing probability on large ranges of the domain, pose a difficult challenge for density estimation. In particular \(R_{{\rm nm}}\) fails again for the estimation of this PDF, producing an almost flat line for both distribution sizes. KDE scores similarly poorly, while at least estimating the Gaussian’s to some degree, albeit far to under-expressed. For this distribution FJE does not manage to recover the five peaks, but instead estimates only three, leading to a large KL divergence and a very low p value. We note that this faulty estimate is maybe caused by a faulty estimation in the R package, as the estimate of this distribution in the original paper of Farmer and Jacobs is better. The estimation of DDE for \(n=500\) is not close to a PDF in this example, as the area under the curve is by far too large, but it is the only method able to reproduce the general structure of the PDF with sharp peaks, while the virtual peaks between the actual Gaussians are a wrong feature estimated for small sample sizes, caused by the roughly symmetric distribution of sampled points around them. For \(n=5000\) the shape of the PDF is better estimated, with only the peaks being too high, causing the lowest KL divergence and highest p value. Here the effect of smoothing is again very small.

The Cauchy distribution \(p(x) = \frac{b}{\pi (x^2+b^2)}\) has heavy tails. The extreme statistics of the Cauchy distribution are generally a difficult problem for density estimation, shown in Fig. 9. Here \(R_{{\rm nm}}\) and KDE give visually almost identical estimates with good scores, while for \(n=5000\) the former shows better distance scores, while the latter has a significantly higher p value. Again, the estimate of FJE is far away from the true PDF and by far the worst of the compared estimates, while again, this distribution was better estimated by Farmer and Jacobs. DDE over estimates the tails of the distribution for \(n=500\) with a slightly to high peak in the center. While this also causes bad scores, the estimation becomes much better for larger sample sizes. In this case the effect of smoothing is visually not noticeable for both sample sizes and even causes worse metrics for \(n=5000\).

The discontinuous distributiondefined on the range [0, 1], poses the problem of discontinuities in the PDF with heavy edges, as shown in Fig. 10. While no method can estimate the sharp edges of this distribution well for \(n=500\), almost all methods can estimate the larger bump of the distribution, with only FJE producing one smooth curve offers the entire PDF. DDE and KDE are closer to the valley of the distribution, but \(R_{{\rm nm}}\) can also estimate the second bump as a noticeable feature. For \(n=5000\) KDE still produces an overly smooth estimate, while the unsmoothed result of DDE contains many noisy spikes. Here, the smoothing has the strongest effect, leading to an estimate which is visually similar to that of \(R_{{\rm nm}}\), while showing the best distance scores. FJE does now estimate the larger bump of the distribution, while showing no other features of the true PDF, apart from reproducing the heavy edges on \(x=0\) and \(x=1\) better than KDE, as it does not quickly degrade toward the end of the distributions.

To summarize these five results, we can say that DDE has difficulties both in estimating sharp peaks as well as long tails, where in the former it produces to high estimates and in the latter vanishes to quickly. Still, DDE is the only method which reproduced the functional shape of the target PDF in all tests, which makes it a good method for estimating such.

To compare the actual shape of the density estimates in higher dimensions, we present examples of estimations in 2D and 3D domains in Fig. 11. As a depiction of the estimations becomes sub-optimal already for 3D, where we plot a slice of the volume projected onto the xy-plane, we cannot show them for higher dimensions. In the figure we present the results of \(R_{{\rm pi}}\), \(R_{{\rm ns}}\), \(R_{{\rm nm}}\) and DDE, both with their respective estimate, as well as an error image between the true PDF and the estimate. Both in 2D and 3D, \(R_{{\rm pi}}\) and \(R_{{\rm ns}}\) produce very smooth estimates. While this may be beneficial on areas with a rather flat distribution, it becomes certainly a problem on regions with dominant features, which cannot be estimated well. DDE and \(R_{{\rm nm}}\) on the other hand give closer estimates to the PDF. Especially in 2D the estimates are similar, while \(R_{{\rm nm}}\) appears as a smoother version of DDE, which however seems to be an unwanted feature both regarding the visual quality, as well as the MSE, although only marginally. This is even more so true for 3D, where only DDE manages to estimate the sharp features of the distribution, which becomes also visible in the error image, where all KDE-based estimators still show more distinct structures, while it is more distributed for DDE and akin to noise. Note that these error images are normalized on their own range, not with respect to a common factor and should thus be compared along the actual error value. Thus, although comparable to \(R_{{\rm nm}}\) in the total accuracy, DDE appears to produce an estimate which is visually closer to the real PDF. This is essentially the same result as in 1D, where the metrics were on par or sometimes worse than other estimators, but still the estimate was visually more akin to the PDF.

In this section, we describe our investigations toward the generalization of our proposed models to other data. Therefore, we compared models trained on subsets of the real-world data to the same models trained on synthetic data. During this comparison, we tested all trained models on the real-world test sets as well as different synthetic test sets as visualized in Fig. 12. We have further varied the distribution sizes, whereby all test distributions are disjoint from the training distributions. Note that the PDFs generated from real-world data are expected to be similar among train and test sets with regard to the functional shape. The results of our investigations show that the models trained on synthetic data perform equally or better than the models trained on real-world datasets, except for 3D where the real-world models always score better. We attribute this difference for the 3D case to the specific characteristics of the DeepLesion dataset. The dominant silhouette edges, which occur in the entire dataset, are hard to fit, but inherently learned by the, respectively, trained model, for exactly these type of edges at those positions, thus overfitting it to this kind of data. On the synthetic test distributions however, both types of model score similarly in 2D and 3D, while in 1D again the models trained on synthetic data score significantly better. This indicates that the models show a good generalization capability while also having space for additional specialization. The models trained on real-world data in 3D show comparable results on the synthetic test sets, but perform systematically better on the real-world test sets. We ascribe the fact that the models trained on real-world data perform worse on synthetic data in 1D, to a lacking diversity in the data of the real-world distributions in 1D. As this systematically lower score is also apparent on the real-world data, it could additionally indicate that the models’ capacity was large enough to not only overfit similar functional shapes, but also the specific PDFs. This is possible in that case, as the model does not need to learn information about global shapes, before it can address local features, but instead learns only the local features based on the common global shape of the entire dataset.

For an additional test, we trained models on datasets comprising functions with random, sinusoidal and random with the exclusion of sinusoidal characteristics, with results in Fig. 13. In this test we can see that all models score roughly similar on the monotone dataset, indicating that this specific functional shape can also be well estimated by models trained exclusively on other functional shapes. As expected, the sinusoidal trained models score always significantly better on the sinusoidal datasets. Along this it is important to note that the model trained without sinusoidal functions scores worse on the sinusoidal PDFs in 10D than the one trained on random functions, but significantly better in 30D. This indicates that the specific functional shape must not be apparent in the training data in form of the 1D base functions, but that the important local characteristics can be generated by the random combination of the base functions. Nevertheless, this evaluation also shows that the generation of training data in high dimensions shows great potential for advancement, as the difference of the models trained on sinusoidal data to all other models gets larger with higher dimensions.

Any method used for the process of estimating PDFs of arbitrary distributions has to estimate not only the areas of high probability accurately, but the complete data space. The difficult task in this is the correct estimation of areas with a very faint or zero probability. Examples for this task are presented in Fig. 14 for the same methods as before. For the compared methods we can see that DDE and \(R_{{\rm nm}}\) can extrapolate to the upsampled regions much better than the other methods, caused by the overly smooth estimation of the complete data space by those. Even for the rather large sample sizes shown, \(R_{{\rm ns}}\) predicts much too smooth estimations, missing every feature of the true PDF. Also \(R_{{\rm pi}}\) seems to be unable to correctly estimate the parts of the PDF with a strong gradient, while it is able to correctly estimate the larger regions of zero probability in the bottom example. The estimations of \(R_{{\rm nm}}\) and DDE can hardly be differentiated. Although \(R_{{\rm nm}}\) shows a slightly better score, the visual quality of the estimations appears equivalent, with the only difference that \(R_{{\rm nm}}\) estimates a slightly smoother PDF which can be preferred or not, while DDE again holds the benefit of being much faster than \(R_{{\rm nm}}\). Also FJE cannot correctly estimate the periodic function on the top, where the valleys and peaks are shifted in some cases. While the estimate produced by FJE is still better than of vanilla KDE or \(R_{{\rm ns}}\), it is not as accurate as DDE, \(R_{{\rm pi}}\) or \(R_{{\rm nm}}\). In the lower case its estimate is close to the last mentioned methods, but still shows some distinct variations from these and the true PDF.

We also evaluated the dependency of the different estimators on the local density around a given query point. For this, we constructed a range of PDFs shown in Fig. 15, for which the position t such that \(p(t)=1\) is known. The definition of the respective functions from left to right and top to bottom is given in Table 1. Given distributions with sizes \(n=500\) and \(n=10,000\), every estimator was evaluated on t. We again present the values of the best estimators in Table 1. We show the estimate at the query point t for every estimator and the respective mean value and standard deviations. The estimate as well as the mean value should be close to 1, while the standard deviation should be as low as possible for an estimator who is robust with respect of the local shape. While DDE knows per definition only the information carried by the \(k = 128\) closest points, the other estimators were still fed with the full distribution. As can be seen from the results in row 2 and 4, DDE struggles with correct estimates on heavy edges. The only estimator, out of the ones we compared here, solving this task is FJE, although not in all cases. Additionally, FJE produces significantly bad estimates for query points on a rising slope, visible in rows 7 and 8, which no other estimator does. Other than that, DDE shows results comparable to the other estimators. On average, DDE shows the best results for low sample sizes, but shows worse results for high sample sizes by the same margin. While we cannot deduce any significant advantage or disadvantage of DDE given the results of this analysis, it shows that DDE is on average at least just as resilient to the local shape regarding the estimation accuracy, as other estimators are.