Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Active learning  is widely used for selecting data efficiently for machine learning models. Performance of existing methods is largely dictated by the quality of uncertainty estimates of the model which may make it challenging to scale up to large batches. The authors propose a technique known as Batch Balance based on decision-theoretic active learning to characterise and distinguish between equivalence classes with similar predictions. They subsequently use a combinatorial information measure to define an acquisition procedure that enables the procedure to be scaled to large batches. Through several experiments the authors  try show their algorithm can effectively handle multi-class classification tasks, while having reasonable performance on both low and large batch settings.
strength_and_weaknesses: Strengths: Overall I think the paper describes the problem of focus in a lot of detail in the introduction and clearly provides algorithms for each of the strategies used ie stochastic batch selection and greedy selection. The authors also compare the proposed approach to several active learning algorithms and variants of the balancing procedure in small and large batch settings.

Weaknesses: The overall aim of the paper is to use make active learning scalable by learning equivalence classes in settings where large batches of queries are common like many applications in reality. In the experiments, though the authors present several baselines on MNIST, EMNIST, CIFAR etc we never get a sense of how the approach would work on a large scale real application or what the challenges would be in a real setting. This is severe limitation. In fact,  the authors don't describe in any detail what the limitations of the proposed approach is.

Moreover, the focus is on learning and characterising equivalence classes with similar predictions but there is no analysis presented on what these equivalence classes between hypotheses are in the experimental section nor a sense of why these equivalence classes make sense. I would have liked to have seen some qualitative analysis of these.

A minor comment would also be to clearly label all axes. The authors state the axis labels in the caption but not consistently for all images which is confusing.

clarity,_quality,_novelty_and_reproducibility: I think the paper is fairly clearly written and the approach is fairly novel. Yet the experiments are not very convincing. 
summary_of_the_review: Overall I recommend a weak reject of the paper mainly because there are many claims made in the motivation and introduction of the paper that are not demonstrated empirically.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors presented a scalable batch Bayesian active learning algorithm and its different variations, which works equally well on large and small batches. The authors support their results with experiments on image datasets as well as with tabular data. By combining Hamming distance and combinatorial information measure, the algorithm is able to select samples for labelling based on both uncertainty and diversity, while spending a reasonable amount of computational time.
strength_and_weaknesses: Strengths:
- understandable and relevant motivation
- well and neatly written, consistent presentation of theory and results
- significant and detailed elaboration of related work, each used claim is supported
- the quality is presented in several metrics
- experiments are done in several domains

Weaknesses:
- Not clear why the particular criterion is used, i.e. the motivation behind the log-likelihood ration is not clear
- the usage of the particular distance (Hamming) is not explained - multiple distance can be considered
- importance sampling of configurations y_{1:b} was used and described in BatchBALD paper to calculate joint mutual information, so the novelty of adaptation of previous work on this step is questionable
clarity,_quality,_novelty_and_reproducibility: The article is written in a clear and consistent manner; the proposed method is an amalgamation of previously published works, but uses their results as an adaptation. Experimental study in different domains looks promising.

It is interesting to see how the proposed algorithms will work on CIFAR-100, which is considered a rather challenging dataset and requires large batches for active learning. It is also interesting to see how the proposed algorithms will behave when using deep ensembles to estimate uncertainty. While this is a more resource-intensive approach, it also yields more successful results compared to MC-dropout (Beluch et al. 2018).

Rather peculiar figure of the running time of the algorithms. We can see from Table 2 that PowerBALD shows top results with respect to alternatives with respect to computational complexity.  At the same time, in figure 2 this advantage is almost not visible due to the scale of the y-axis. I would suggest adding more points to this graph, or at least a zoom for the existing graph, similar to graph 4 (c). I think it is important to reflect this difference correctly, since at first glance PowerBALD on the graphs in most cases has comparable quality to the BALanCe algorithms, spending less computational resources.
Moreover, if on small datasets like Repeated-MNIST the difference in performance is noticeable, then on SVHN and CIFAR-10 it is practically not visible. It would also be interesting to see a comparison of BALanCE with PowerBALD and on small batches.
Also, it would be interesting to see a more extensive discussion of the results presented. Namely, why Power BALD has a comparable performance despite its disadvantages?
The same applies to the analysis of the complexity of the algorithms in Table 2 and the discussion on this.
summary_of_the_review: The paper is well written but the main technical part is too rushed - the design choices should be better explained. The results presented seem convincing. Generally, the paper in the current state is borderline, I current put it above the threshold, though very interested to see the authors response.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a novel active learning (AL) algorithm for deep Bayesian neural networks (BNN).
Towards this goal, the paper proposes a novel acquisition function that is aimed at selecting data points that can improve the differentiation of models that belong to different equivalence classes.
By defining a decision-theoretic acquisition function that focuses on predictive accuracy and incorporating diversity sampling across equivalence classes, the paper shows that the resulting AL algorithm, referred to as Batch-BALANCE, is scalable and leads to AL performance improvement compared to existing alternatives.
.

strength_and_weaknesses: OVERALL COMMENTS

Overall, the paper is well-written in a clear and logical manner.
The authors provide a brief yet informative review of the existing state-of-the-art relevant to the proposed batch AL algorithm, motivate and present their proposed approach, and assess the performance of the resulting AL algorithm Batch-BALANCE using several widely used benchmarks.
Evaluations based on different models and benchmarks with various batch sizes show that Batch-BALANCE generally outperforms other popular batch AL methods, including BatchBALD, BADGE, and PowerBALD.
Batch-BALANCE is shown to work well in both small and large batch regimes, providing effective and scalable means for Bayesian active learning.


DETAILED COMMENTS

1. The authors mention the downside of MIS (most informative selection) methods as "MIS tends to select data points that reveal the maximal information w.r.t. the sampled distribution, rather than guiding the active learner towards learning high accuracy models."
While this is a fair statement, the authors do not mention other AL schemes that focus on data acquisition that is expected to reduce model uncertainty that affects the model accuracy.
A well-known category is ELR (expected loss reduction), where an ELR-based Bayesian AL method tries to select unlabeled data points whose labeling is expected to reduce the loss most effectively.
It would be useful to briefly review representative and/or recent ELR-based Bayesian AL methods and discuss their relevance to the proposed algorithm, since at a high-level, they both take a "decision-theoretic" approach that focuses on the model accuracy.

2. Although the overall technical presentation in the paper is good, there are some minor suggestions for improving it further. For example:

- Please define ECED (page 4) before using the term, since it only appears in the appendix

- Please describe how the "Hamming distance" is computed between different hypotheses (or model parameters). Since Hamming distance is typically used to compare the difference between two symbol sequences by counting the number of locations with different symbols, it is not entirely clear how it is being used in this work for measuring the distance between two BNN parameters w and w'.

- While the authors present the definition of d_H in the appendix, it is still unclear how it applies to computing the distance between BNN parameters. Furthermore, it would be better if the definition of h_H is referred to in the main text.

- While the pseudocode of Algorithms 1-3 is helpful, it would make the pseudocode more readable for future readers if the code is (at least briefly) commented.

- Instead of calling I_Deltah_Balance(x,y) as a combinatorial information measure, it would be better to conceptually relate it to mutual information


3. The acquisition function of Batch-BALANCE is obtained through sampling using either MC dropout or  Stochastic gradient Markov Chain Monte Carlo (SG-MCMC).
However, there is currently no discussion on any pros/cons of the respective methods when used with Batch-BALANCE.




clarity,_quality,_novelty_and_reproducibility: Overall, the paper is clearly written making the proposed Bayesian AL method easy to follow and understand.
However, further improvement could be made as suggested in "Strength and Weakness".
The proposed method is relatively novel, rationally building on existing work on decision-theoretic AL schemes that adopt diversity sampling across equivalent classes and taking advantage of MC sampling schemes used for posterior estimation of BNNs.
The evaluation results clearly demonstrate the practical advantages and potential scalability of the proposed Batch-BALANCE algorithm.



summary_of_the_review: This is a well-written paper that proposes a novel AL method that builds on a decision-theoretic principle and diversity sampling and aims to improve the performance and scalability of AL for deep BNN. The authors provide a brief review of relevant existing work to provide the right context for the proposed method, clearly motivating the work. Mostly, the technical details are elaborated clearly and the performance assessment results demonstrate the merits of the proposed Batch-BALANCE algorithm under a number of different AL scenarios.

. . .

The reviewer confirms that (s)he has reviewed the authors' rebuttal, which has been reflected in the above review comments and the overall evaluation scores
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a batch-mode active learning method for deep Bayesian Neural Networks. The sampling is based on the intuition of partitioning the equivalent classes optimally and puts less weight on the hypothesis that does not disagree with the true data distribution much. 

strength_and_weaknesses: Strength
The paper is well-written and well-motivated. I agree that the uncertainty estimation quality of deep neural networks, especially BNN poses a big challenge for modern active learning. I think the proposed method provides a new point of view for sampling based on the concept of equivalent classes. According to my understanding, the sampling strategy has the flexibility to put less focus on differentiating the hypothesis with little disagreement when the uncertainty estimation is not accurate in the early stage of active learning.
The proposed method is practical to real-world problems. The proposed active learning strategy avoids listing the full set of equivalence classes exhaustively by leveraging MC sampling.

Weakness
The paper lacks some theoretical discussion to draw the connection between the sampling strategy and learning performance. For example, what are the expected gain results from adding a new annotated sample selected by the proposed method? How fast would eq2 converge to eq1 as K increases?
The partition of the ECs is intuitive and lacks validation. Why is the Hamming distance used as a measurement and what are the alternative measures?

clarity,_quality,_novelty_and_reproducibility: I think the proposed AL method for BNN is novel and the motivation, intuition, as well as methodology, are clearly described in the paper. I have some concerns listed as follows:
The demonstration in figure 1 is not very clear to me. How the probability mass in figure b is computed given the EC is a set of N posterior distributions? How can we tell BALD samples are suboptimal from figure b? 
Even though the proposed method does not require to construct ECs explicitly, I still think the number of ECs (i.e, k) is critical to the active sampling performance. The threshold \tau seems to reflect the number of k indirectly. Could the author further elaborate on the relationship between k and \tau and how should \tau be set intuitively?

summary_of_the_review: The proposed method is novel and sound. But adding some theoretical underpinnings is prefered.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work presents a novel batch active learning algorithm set in a Bayesian framework, focused on training Bayesian Neural Networks (BNN).  The algorithm is motivated by labeling examples that are most useful in differentiating hypotheses from different equivalence classes, while reducing labels wasted on differentiating similar hypotheses. Furthermore, the authors provide a practical algorithm that scales efficiently with batch size by first clustering the sampling pool and executing independent sampling within each cluster. The empirical evaluation considers small (e.g. MNIST) and larger (e.g. SVHN) with small (e.g. 10) and larger (e.g. 1000) batch sizes, demonstrating improvements or comparable performance with a couple Baysian and non-Baysian active learning baselines in some cases with significantly less computation.

The majority of reviewers agree the paper provides a novel approach presented clearly with convincing enough empirical backing.  In the rebuttal the authors answer or clarify several concerns that were raised, including providing an additional more challenging empirical benchmark (CIFAR-100).  The strongest remaining reviewer comment is regarding the lack of a stronger theoretical motivation for the (implicit) equivalence hypothesis classes used to motivate the sampling approach.  However, given the contributions and appreciating the use of equivalence classes as a heuristic, I will recommend a weak accept.

I strongly encourage authors to incorporate all clarification into the final work.  Also, although not raised by reviewers, the AC strongly recommends including the simple but effective uncertainty (e.g. margin) sampling baseline to be included in the paper. Although simple and not tailored to the Bayesian setting necessarily, uncertainty sampling often provides strong performance.

justification_for_why_not_higher_score: I find that missing comparison to margin sampling, which is often competitive in many AL scenarios, a weakness.  Apart from intuition, there isn't much in terms of theoretical justification for the suggested appraoch.
justification_for_why_not_lower_score: After discussion and revision by the authors, reviewers tend to agree that there is enough empirical evidence to accept the paper.
Decision: Accept: poster