Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper focuses on computing the exact Bayes error of generative models learned using normalizing flows.

The main contributions are:
1. The paper proposes to compute the exact Bayes error of an approximate distribution instead of computing an approximate Bayes error of the exact distribution.
2. The paper shows that by varying the temperature of a single flow model, they can obtain an entire class of distributions with varying Bayes errors.
main_review: This paper proposes a novel method to design benchmarks for classifiers, where Bayes errors can be efficiently calculated. The method consists of two steps: (1) Approximate the distribution of a given data set by a normalizing flow with the input distributed according to GMM. (2) The Bayes error of the data set generated by the normalizing flow can then be calculated by the Holmes-Diaconis-Ross integration.

The conclusion given by Proposition 1 is very interesting for readers, and is possibly useful for further research on normalizing flows. However, the overall significance is marginal. The major limitation of the benchmarks produced by generative models (including NFs) is: The structure of the generative model will introduce some implicit bias, and the classifier using the same transformations (like convolution operators) could be better than the others.

After rebuttal: First, I disagree with authors that "the same order of magnitude as the error of the same architectures on the original datasets seems to indicate that this is not a substantial issue in practice". For common data sets, the error rates of popular deep learning classifiers are all in the same order of magnitude. Second, I agree with reviewer Q5Ht that better NLL might not lead to better estimates of the Bayes error, especially for normalizing flows. So I do not change my evaluation.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces a new method to estimate the Bayes error for multi-class classification problems with complex feature spaces. The central idea is to estimate for each class a density model based on normalizing flows, and use the estimated densities to compute the Bayes error approximately. The authors present two theoretical results that intend to illustrate that normalizing flows are well suited for this problem. A first theoretical result shows that the Bayes error is invariant under an invertible linear transformation of the raw features, which is typical in normalizing flows. A second theoretical result states that the Bayes error of normalizing flows is monotonically increasing w.r.t. the temperature parameter pi. 

In addition, two types of experimental results are reported. In a first experiment, synthetic data is generated, starting from the Fashion MNIST dataset, and using flow-based models as the ground truth (i.e. the underlying distribution on population level). It is shown that on this data the performance of SOTA neural networks still shows a gap with the Bayes error, confirming that such models don't estimate the Bayes error yet. In a second type of experiments, flow-based models are fitted on classical image classification benchmarks. It is shown that the estimated Bayes error aligns well with the error of SOTA models in the sense that similar rankings of datasets are obtained.    
main_review: I think that this is an interesting paper and I enjoyed reading it. The paper is very well written and easy to follow. As far as I know the proposed methodology is novel, and the presented method is simple yet appealing. The two theoretical results (Proposition 1 and 2) have an added value for the paper. Estimating the Bayes error is also a practically relevant problem, so this paper scores good on the criteria originality, quality, clarity and significance. 

The experimental results are also interesting, but the experimental setup is different from what I expected to read. The authors don't compare their approach to other methods that intend to estimate the Bayes error. I understand that such a comparison is not easy, because the Bayes error is not known for real datasets. However, at least some methods could be compared on synthetic data (I refer to synthetic data that is generated according to a different model than the Glow model, unlike the synthetic data in Section 4.2). In fact there are many baselines that could be tested. The authors argue that divergence-based methods, such as references 7 to 11, don't scale well to high-dimensional data, but there is a recent divergence-based method that is also used on MNIST: https://arxiv.org/pdf/1811.06419.pdf. The authors don't seem to know that work. 

In addition, estimating the Bayes error is very related to uncertainty quantification, which has received a lot of attention recently in the machine learning community. Many simple baselines could be tested. For example, it is very common in deep learning research for uncertainty quantification to first fit a softmax network, followed by density estimation in the penultimate layer. In this scenario, classical density estimation methods can be used, such as linear discriminant analysis, Gaussian mixtures, kernel density estimation, etc. -- see e.g. Lee et al. "A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks" Neurips 2018. In addition, other types of deep generative models such as autoregressive models and autoencoders are also useful baselines -- see e.g. Nalisnick et al. "Do deep generative models know what they don't know?" ICLR 2019.  I would be interested to see how normalizing flows perform w.r.t. such baselines. At least the work of Nalisnick reports some negative results for flow-based models. 

For the experiment in Section 4.2 it is interesting to see that SOTA methods don't come close to the Bayes error. From this it might be concluded that these methods are not good in estimating the Bayes error, but it might also be the case that the error of those methods can be reduced by making architectural changes. It is not unlikely that existing SOTA methods are optimized for classical benchmarks, while having suboptimal architectures for the synthetic data of the authors. 

For the experiment in Section 4.3 it is counterintuitive that for some datasets the estimated Bayes error is lower than the error of SOTA methods. This is of course because the method of the authors only provides an estimate of the Bayes error. In uncertainty quantification for classification models, aleatoric uncertainty corresponds exactly to the Bayes error.  In the introduction, the authors motivate that in their work they only want to focus on this uncertainty component, and not on the epistemic uncertainty component. However, I don't believe that this component can be ignored. Fitting a density model is an estimation process, which leads to epistemic uncertainty. So, this work is very related to papers on uncertainty quantification, where often a distinction between aleatoric and epistemic uncertainty is made.  I believe that the authors ignore that literature too much. 

limitations_and_societal_impact: See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors went on a series of steps to measure how close to theoretical optimal are current deep learning algorithms. They first obtain the optimal misclassification Bayes error under the assumption that features follow a Gaussian distribution conditioned on the j-th class. Next, they fit approximate distributions \hat{p}_j(x) where x=T(z) and T is an invertible transformation and z is Gaussian. Finally, they show (but the proof is missing) that the Bayes error is invariant under invertible transformations. Putting these building blocks creatively together we have the results about the quality of the current deep learning classification methods. 

main_review: I enjoyed reading this paper. In my opinion, they use in an ingenious way known results (such as the Holmes-Diaconis-Ross integration method) to obtain an answer to an important question: just how close to the theoretical optimal Bayer rule misclassification rule are the state-of-art (SOTA) deep learning classification algorithms? Given the ever-present fear of being unknowingly trapped on local minima, far away from the global minimum, discovering that some SOTA algorithms come close to the best possible is reassuring. Indeed, there is a strong linear relationship between the Bayes error and the SOTA error shown in the last two columns of Table 1. A scatterplot of these two columns shows more clearly the discrepancy of the points corresponding to the EMNIST by merge and EMNIST by class datasets from the linear trend produced by the other datasets. 

The paper is not hard to read. It is very well written and it goes on theory in the right depth needed for the ideas discussed in the paper. I was not familiar with the Holmes-Diaconis-Ross method and found that the authors made creative use of this result. Also, it was nice to know about the invariance of the Bayes error under invertible transformations, even non-linear ones. Unfortutenaly, the proof is in Appendix A which has not been provided. At least, I could not find it on the OpenReview website. 

In addition to the points raised by the authors in section 5, I can think of two other points: (1) it would be worthwhile deriving better measures than simply the NLL to measure the discrepancy between p and p-hat. (2) is it possible to expand the methods of this paper by focusing on other performance metrics different from the expected misclassification error? 
limitations_and_societal_impact: The  authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: this paper proposes a simple way to estimate the bayes error of a classification dataset; fit a invertible generative model to the dataset, and use Gaussians in the latent space of the flow model. Since the bayes error is invariant to invertible transformations, the Bayes error can be estimated in the latent space through integration techniques. This is performed for a few real world datasets to investigate how close we are to reaching the Bayes error. 
main_review: After rebuttal: I've made my score slightly higher as the authors convinced me regarding point 1 of my review. However, regarding point 2, I am still not convinced. The argument about convergence of the distribution does not really help in any way; as we cannot really say whether the flow models are converging in any sense. What would really convince me is some example that shows that a better NLL implies a better Bayes error estimate (as the NLL is at least optimized by the flow models). However, as my counterexample suggests, this may be difficult to achieve and may requite further additional assumptions. Unless this is offered, or some other experimental results that show that better NLL really leads to better estimates of the Bayes error, I could further improve my score - as of now, it remains unclear to me whether better flow models really result in better Bayes error estimates, which seem to me one of the essential assumptions of this work. 

Regarding 4; I think I was confused with Variational Auto-Encoders; I will check this further in more detail... Maybe it does not apply to flow models at all. Regarding remark 7; what maybe I didn't write clearly, is why is this remark ever made in the paper? It seems completely off-topic to me, which is what confuse me most.  

I like the paper, but issues 1-5 are problematic for it's acceptance in my eyes. Some statements about computational feasibibility seem contradicting to me or unconvincing. The same goes for the quality of the estimator. Here I think even it is possible to construct examples that contradict the statements in the paper. Finally, there are a few details regarding the experimental setup that are either wrong or incorrect or not carefully described enough. 

Below some information that hopefully could help improve the work. 

Most problematic issues:
1) Claims regarding computational efficiency are not precise enough, too vague and contradictory

"This method is highly  efficient, even in high dimensions." (line 99)
seems to contradict statement in line 166-169. 
"We remark that we observe our Bayes error estimator runs efficiently when the input is of dimension
167 32-by-32-by-3. However it is in general highly memory intensive to run the HDR integration routine
168 on significantly larger datasets, e.g. when the input size grows to 64-by-64-by-3. As a consequence,
169 in our experiments we only work on datasets of dimension no larger than 32-by-32-by-3."

Instead, it would be better if you can give the big O notation complexity. If this is infeasible or not sensible, I think it would be worthwhile to include a graph of computation time + memory used versus  dimensionality, so at least we can judge whether it is really computational feasible. 


2) Claims regarding the accuracy of the estimator are too vague 

"As we can see, it is highly accurate." (line 102). 

This claim is already very difficult to judge. From the figure I cannot see how large the errors are. Please include a table with some numbers (MSE, MAE) so we can judge the size of the errors. It would be good to include the Monte-Carlo baseline (described in 4.4) estimator here, so we can judge whether errors are really small of this estimator. Would be good to mention something about their trade-offs (when to use Monte-Carlo, when to use this integration technique). 

"If in addition the flow model
is a good a approximation for the true class-conditional distribution
then we expect to obtain a good estimate for the true Bayes error." (line 134)

I think this claim is too strong. I would even go in the opposite direction, I think we can quite easily make an example where for example the log likelyhood or other density estimation metric is very 'good' (e.g. small NLL), while the bayes estimator is very poor, and vice versa. 

For example, take 
P_+ = N(0,1), P_- = N(2,1)
Q_+ = N(0,1), Q_- = N(3,1)
R_+ = U(0,1), R_- = U(a,1+a)
where I used N as notation for the normal distribution N(mu, sigma) and U(c1,c2) as the uniform distribution on the interval [c1,c2]

I for sure can find a value a such that R has the exact same bayes error as P. However, in many density estimation metrics R would be a worse approximation of P than Q. This is also in line with "A note on the evaluation of generative models" who find that good performance in one metric generally doesn't lead to good performance in another, for tasks related to density estimation. 

This to me suggests that a good likelyhood model or a good density estimation metric is definitely not sufficient to get a good estimate of the Bayes error. 

As a starter to investigate this, I suggest the authors investigate the synthetic task of Section 2, varying the NLL of the density model versus the error of the estimator. I would not be surprised if the behavior can be non-monotonic. Of course, it is also highly dependent on how the models are obtained in such a small experiment. As two obvious approaches I would consider: 1) taking models from all epochs to get to a series of density models 2) randomly initialising all weights of the model many times 

Other problems

3) lines 175-181. I'm confused, what is now tuned using which splits?? Generally, we cannot tune a parameter using the test set, in that case all the performance metrics on the test set are not thrustworthy anmore! So maybe all the NLL's need to be updated?

4) How is the NLL computed? MNIST is inherently a discrete dataset, while the flow model is continuous. This should be clarified. See also "A note on the evaluation of generative models". 

5) I couldn't find how the \mu's were set for all datasets. I think it could be nice to look at the confusion matrices that we can obtain by models trained on the synthetic datasets, and compare those with confusion matrices on the real datasets. This could maybe give a good idea how to put the \mu's in the latent space to give a more realistic approximation of the true distribution. 

Other minor remarks

6) "components: i) hardness caused by the lack of
samples, and ii) hardness caused by the internal data distribution p. " line 76). 
This in literature is called also the estimation error versus the irreduceable error. Maybe good to cite a text book or chapter from 
"Understanding Machine Learning: From Theory to Algorithms" for example?

7) "The problem of finding the minimal error achievable from a given dataset of size has N been called the optimal experimental design problem [17].
" line 80.

The wording is very confusing here. Trying to find a model with minimal error is typically called machine learning, in general. The authors seem to talk about active learning, where the points (x,y) can be chosen by an active learning algorithm. This latter is indeed called optimal experimental design.

8) line 223. I think the best argument is that all flow models are trained with \tau = 1, and the \tau is changed only after the training, right? This makes \tau = 1 the logical choice. However: I think it MAY be possible that another \tau may actually offer the best fit on the validation data! Especially if the models are overfitted. Maybe this makes even more sense, to tune \tau on validation data? 

9) line 239. Zero error? Are we talking NLL or classification loss?

10) Figure 2: maybe say something about \tau >= 1.4; that these samples do not seem realistic anymore? 

11) Other more interesting experiments could be created by varying the amount of training samples from the synthetic datasets, instead of keeping this number fixed. 

12) Of course, the golden standard to determine the Bayes error could be by doing a large scale experiment where people actually label the datasets. This could be an interesting way to check the reliability of the estimates. But maybe this was already done for MNIST for example? 

13) I think that the proof of proposition 1 can be much simplified, by using a proof by contradiction and using simple invertibility of the mapping. Or maybe I'm simplifying the problem too much.... For a discrete input space I think this should definitely work, but maybe for a continuous space there are some problems with this technique that I cannot foresee now. 

limitations_and_societal_impact: For limitations see above. Regarding societal impact I see no problems.
review_title: null

Meta-review: From the reviews and the discussion, a consensus emerges that the paper contains a valuable contribution, but some claims need more precision and require more throughout empirical comparison. These issues need to be addressed by a proper revision, and would require another round of reviewing.
Decision: Accept (Poster)