Scalable Batch-Mode Deep Bayesian Active Learning via Equivalence Class Annealing
Authors: Renyu Zhang
Aly A Khan
Robert L. Grossman
Yuxin Chen
Venue: ICLR 2023 poster (2023)
Keywords: Bayesian Neural Network
Batch-Mode Active Learning
Decision-Centric Data Acquisition
Scalability

Abstract: Active learning has demonstrated data efficiency in many fields. Existing active learning algorithms, especially in the context of batch-mode deep Bayesian active models, rely heavily on the quality of uncertainty estimations of the model, and are often challenging to scale to large batches. In this paper, we propose Batch-BALanCe, a scalable batch-mode active learning algorithm, which combines insights from decision-theoretic active learning, combinatorial information measure, and diversity sampling. At its core, Batch-BALanCe relies on a novel decision-theoretic acquisition function that facilitates differentiation among different equivalence classes. Intuitively, each equivalence class consists of hypotheses (e.g., posterior samples of deep neural networks) with similar predictions, and Batch-BALanCe adaptively adjusts the size of the equivalence classes as learning progresses. To scale up the computation of queries to large batches, we further propose an efficient batch-mode acquisition procedure, which aims to maximize a novel combinatorial information measure defined through the acquisition function. We show that our algorithm can effectively handle realistic multi-class classification tasks, and achieves compelling performance on several benchmark datasets for active learning under both low- and large-batch regimes.

Published as a conference paper at ICLR 2023
SCALABLE BATCH-MODE DEEP BAYESIAN ACTIVE LEARNING VIA EQUIVALENCE CLASS ANNEALING
Renyu Zhang', Aly A. Khan? Robert L. Grossman 'A, Yuxin Chen'
Department of Computer Science, University of Chicago
*Department of Pathology. University of Chicago
*Department of Family Medicine, University of Chicago
*Department of Medicine, University of Chicago (zhangr, aakhan, rgrossmanl, chenyuxin htwp:/iaiinncicccooo.oooo
ABSTRACT
Active learning has demonstrated data efficiency in many fields. Existing active learning algorithms, especially in the context of batch-mode deep Bayesian ac- tive models, rely heavily on the quality of uncertainty estimations of the model, and are often challenging scale to large batches. In this paper, propose BAANC, a scalable batch-mode active learning algorithm, which com- bines insights from decision-theoretic active learning, combinatorial information measure, and diversity sampling. At its core, Batch-BAL BAANCE relies on a novel decision-theorede acquisition function that facilitates differentiation among differ- ent equivalence classes. Intuitively, each equivalence class consists of hypotheses (e-g., posterior samples of deep neural networks) with similar predictions, and Batch-BALANCE adaptively adjusts the size of the equivalence classes as learn- ing progresses. To scale up the computation of queries to large batches, we further propose an efficient batch-mode acquisition procedure, which aims to maximize a novel information measure defined through the acquisition function. We show that our algorithm and achieves compelling performance on several benchmark datasets for active learning under both low- and large-batch regimes. Reference code is released
effectively handle realistic multi-class classification tasks,
INTRODUCTION
Active learning (AL) (Settles, 2012) characterizes collection of techniques that efficiently select data for training machine learning models. In the pool-based setting, an active learner selectively queries the labels of data points from a pool of unlabeled examples and incurs a certain cost for each label obtained. The goal is to minimize the total cost while achieving target level of performance. common practice for AL is to devise efficient surrogates, aka acquisition functions, to assess the effectiveness of unlabeled data points in the pool.
There has been a vast body of literature and empirical studies (Huang et al., 2010; Houlsby et al., 2011: Wang & Ye, 2015; Hsu & Lin, 2015; Huang et al., 2016; Sener & Savarese, 2017; Ducoffe & Precioso, 2018; Ash et al., 2019 Liu et al., 2020; Yan et al., 2020) suggesting a variety of heuris- tics as potential acquisition functions for AL. Among these methods, Bayesian Active Learning by Disagreemens (BALD) (Houlsby et al., 2011) has attained notable success in the context of deep Bayesian AL, while maintaining the expressiveness of Bayesian models (Gal al., 2017; Janz et al., 2017; Shen et al., 2017). Concretely, BALD relies on a most informative selection (MIS) strategy-al classical heuristic that dates back to Lindley (1956)-whic) greedily queries the data point exhibiting the maximal mutual information with the model parameters at each iteration. De- spite the overwhelming popularity of such heuristics due to the algorithmic simplicity (MacKay, 1992; Chen et al., 2015: Gal & Ghahramani, 2016), the performance of these AL algorithms unfor- tunately sensitive the quality of uncertainty estimations of the underlying model, and remains an open problem in deep AL to accurately quantify the model uncertainty, due to limited access to training data and the challenge of posterior estimation.

---

Published as a conference paper at ICLR 2023
In figure 1, we demonstrate the potential issues of MIS- based strategies introduced by inaccurate posterior samples from Bayesian Neural Network (BNN) on a multi-class classification dataset. Here, the samples (i.e. hypotheses) from the model posterior are grouped into equiva- lence classes (ECs) (Golovin et al., 2010) according to the Hamming distance be- tween their predictions as shown in fig- ure la. Informally, an equivalence class contains hypotheses that are close in their predictions for a randomly selected set of examples (See section 2.2 for its formal definition). We note from figure 1b that the probability mass of the models sam- pled from the BNN is centered around the mode of the approximate posterior distri- bution, while little coverage is seen on models of higher accuracy. Consequently, 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.
801 2012
105 6M0
62
165 0724
84
8C34 2.0
1011 8.17
-2
603 130
-2 -1
0.2
5.5
0.61
5.0
0.5e OR3
(a)
(b)
Figure 1: (a) Samples from posterior BNN via MC dropout. The embeddings are generated by applying t-SNE on the hy- potheses' predictions on a random hold-out dataset. Colorbar indicates the (approximate) test accuracy of the sampled neu- ral networks on the MNIST dataset. See section C.2 for de- tails of the experimental setup. (h) Probability mass (y-axis) of equivalence classes (sorted by the average accuracy of the enclosed hypotheses as the x-axis).
In addition the robustness concern, another challenge for deep AL is the scalability large batches of queries. In many real-world applications, fully sequential data acquisition algorithms are often undesirable especially for large models, as model retraining becomes the bottleneck of the learning system (Mittal et al., 2019; Ostapuk et al., 2019). Due to such concerns, batch-mode algorithms are designed to reduce the computational time spent on model retraining and increase labeling efficiency. Unfortunately, for most acquisition functions, computing the optimal batch of queries function is NP-hard (Chen & Krause, 2013); when the evaluation of the acquisition func- tion is expensive or the pool of candidate queries is large, it is even computationally challenging to construct a batch greedily (Gal et al., 2017; Kirsch et al., 2019; Ash et al., 2019). Recently, ef- forts in scaling up batch-mode AL algorithms often involve diversity sampling strategies (Sener & Savarese, 2017; Ash et al., 2019; Citovsky et al., 2021; Kirsch et al., 2021a). Unfortunately, these diversity selection strategies either ignores the downstream learning objective (e.g.. using clustering as by (Citovsky et al., 2021)), or inherit the limitations of the sequential acquisition functions (e.g., sensitivity to uncertainty estimate as elaborated in figure (Kirsch et al., 2021a)).
Motivated by these two challenges, this paper aims to simultancously (1) mitigate the limitations of sncertainty-based deep AL heuristics due to inaccurate uncertainty estimation, and (2) enable effi cient computation of batches of queries at scale. We propose Batch- Batch-BALANCE BAL-BAL-AN-E--- an efficient batch- mode deep Bayesian AL framework-whice employs a decision-theoretic acquisition function in- spired by Golovin et al. (2010); Chen et al. (2016). Concretely, the underlying hypotheses, and uses Monte Carlo (MC) dropout (Gal & Ghahramani, 2016; Kingma et al., 2015) or Stochastic gradient Markov Chain Monte Carlo (SG-MCMC) (Welling & Teh, 2011; Chen et al., 2014; Ding et al., 2014; Li et al., 2016a) to estimate the model posterior. It then se- lects points that can most effectively tell apart hypotheses from different equivalence classes (as illustrated in figure 1). Intuitively, such disagreement structure is induced by the pool of unlaheled data points; therefore our selection criterion takes into account the informativeness of a query with respect to the target models (as done in BALD), while putting less focus on differentiating models with little disagreement on target data distribution. As learning progresses, Batch- Mach-BBALA BALANCE adap- tively anneals the radii of the equivalence classes, resulting in selecting more "difficult examples" that distinguish more similar hypotheses as the model accuracy improves (section 3.
utilizes BNNs as
When computing queries in small batches. Batch-BALANCE BALANCE employs an importance sampling strat- egy to efficiently compute the expected gain in differentiating equivalence classes for a batch of examples and chooses samples within batch in a greedy manner. To scale up the computation of queries to large batches, we further propose an efficient batch-mode acquisition procedure, which aims to maximize novel combinatorial information measure (Kothawade et al., 2021) defined through our novel acquisition function. The resulting algorithm can efficiently scale to realistic batched learning tasks with reasonably large batch sizes (section 3.2, section 3.3, appendix B).
2

---

Published as a conference paper at ICLR 2023
Finally, we demonstrate the effectiveness of variants of cal study, and show that they achieve compelling performance sometimes someeiine by a large margin on several benchmark datasets (section 4, appendix D) for both small and large batch settings.
via extensive empiri-
2 BACKGROUND AND PROBLEM SETUP
In this section, introduce useful notations and formally state the (deep) Bayesian AL problem. We then describe two important classes of existing AL algorithms along with their limitations, as a warm-up discussion before introducing our algorithm in section 3.
2.1 PROBLEM SETUP
Notations We consider pool-based Bayesian AL, where we given unlabelled dataset pool drawn i.idd from some underlying data distribution. Further, assume a labeled dataset Dirain and set of hypotheses H {hi..... hn)) We would like to distinguish set of (unknown) target hypotheses among the ground set of hypotheses H. Let H denote the random variable that represents the target hypotheses. Let p(H) be prior distribution over the hypotheses. In this paper, resort to BNN with parameters w ~ p(w 'Draiin'..
Problem statement An AL algorithm will select samples from Pooo and query labels from ex- perts. The experts will provide label for given query x E pool. We assume labeling each query incurs a unit cost. Our goal is to find an adaptive policy for selecting samples that allows us to find hypotheses with target error rate E [0, 1J while minimizing the total cost of the queries. For- mally, a policy æ is mapping π from the labeled dataset Dtrain to samples in Paoo We use Dirain to denote the set of examples chosen by æ. Given the labeled dataset Dirain we define (E)R( as the expected error probability w.r.t the posterior p(w Diraiu)- Let the cost of policy π be cost(x) - max (Dirsiul i.e., the maximum number of queries made by policy т over all possible realizations of the target hypothesis H E H. Given tolerance parameter a [0, 1]. we seek policy with the minimal cost, such that upon termination, it will get expected error probability less than σ. Formally, we seek arg min, cost(r), s.t. PERR (T) S a.
2.2 THE EQUIVALENCE CLASS-BASED SELECTION CRITERION
As alluded in section 1 and figure 1, the MIS strategy can be ineffective when the samples from the model posterior are heavily biased and cluttered toward sub-optimal hypotheses. We refer the readers to appendix A.1 for details of stylized example where MIS-based strategy (such as BALD) can perform arbitrarily worse than the optimal policy. A "smarter" strategy would instead leverage the structure of the hypothesis space induced by the underlying (unlabeled) pool of data points. In fact, this idea connects to an important problem for approximate AL, which is often cast as learning equivalence classes (Golovin et al., 2010):
Definition 2.1 (Equivalence Class) Let (H, d) be metric space where H is hypothesis class and
is a metric. For a given set V S H and centers S = [s.......5 s&3 S V of size let p : + be a partition function over V and D: := {h E V (h) = i}, such that vi,j E [ki], r (s,) = i
and vh E Di, d(,, 8:) S d(h,,)) 8z). Each D. C called an equivalence class induced by 8; E S.
Consider pool- based AL problem with hypothesis space H. sampled set V C H. and an unlabeled dataset D poon which is drawn i.idd from the underlying data distribution. Each hypothesis be represented by a vector v indicating the predictions of all samples in Ppool. We can construct equivalence classes with the Hamming distance, which is denoted du(h, h'), and equivalence class number on sampled hypotheses V. Let dit (V) == max,, maximal diameter of equivalence classes induced by S. Therefore, the error rates of any unordered pair of hypotheses (h, R') that lie in the same equivalence class are at most (V) away from each other. If we construct the k equivalleee--las--nndcciii the max-diameter clustering problem: C = arg sin di (V), we can obtain the minimal worst- case relative error (i.e. difference in error rate) between hypotheses pair (h, h') that lie in the same
H can
( du du(h, h!) be the
centers (as in definition 2.1) as the solution of
We use the conventional notation w to represent the parameters of a BNN, and use w and h interchangeably denote hypothesis.
3

---

Published as a conference paper at ICLR 2023
equivalence class. We denote & hypotheses (i.e. undirected edges) corresponding to different equivalence classes with centers in C.
[(h,h') } (h) * (hh)) the set of all (unordered) pairs of
Limitation of existing EC-based algorithms Existing EC-based AL algorithms (e.g.. EC² (Golovin et al., 2010) as described in appendix A.2 and ECED (Chen et al., 2016) as in appendix A.3) are directly applicable to deep Bayesian AL tasks. This is because computing the acquisition function (equation 4 and equation 5) needs to integrate over the hypotheses space, which is in- tractable for large models (such as deep BNN). Moreover, is nontrivial to extend to batch-mode setting since the number of possible candidate batches and the number of label configurations for the candidate batch grows exponentially with the batch size. Therefore, we need efficient approaches to approximate the ECED acquisition function when dealing with BNNs in both fully sequential setting and batch-mode setting.
OUR APPROACH
We first introduce our acquisition function for the sequential setting, namely BALANCE (as in Bayesian Active Learning via Equivalence Class Annealing), and then present the batch-mode ex- tension under both small and large batch-mode AL. settings.
3.1 THE BALANCE ACQUISITION FUNCTION
We resort to Monte Carlo method to estimate the acquisition function. Given all available labeled samples Drrain at each iteration, hypotheses w are sampled from the BNN posterior. We instantiate our methods with two different BNN posterior sampling approaches: MC dropout (Gal & Ghahra- mani, 2016) and cSG-MCMC (Zhang et al., 2019). MC dropout is easy to implement and scales well to large models and datasets very efficiently (Kirsch et al., 2019; Gal & Ghahramani, 2016; Gal et al., 2017). However, it is often poorly calibrated (Foong et al., 2020; Fortuin et al., 2021). cSG-MCMC is more practical and indeed has high-fidelity to the true posterior (Zhang et al., 2019; Fortuin et al., 2021; Wenzel al., 2020).
In order to determine if there is an edge (6,6") that connects pair of sampled hypotheses a a/ (i.e.. if they are in different equivalence classes), we calculate the Hamming distance d &') between the predictions of w, @' on the unlabeled dataset Ppool If the distance is greater than some threshold consider the edge {wo W') E E; otherwise not. We define the acquisition function of {311--. (.11,1.;bb))))
BALANCE for set 11:b
ABALANCE(T1Ls (Drrii)) A Egg. Bu..' du (w(w"))>> (1 Aw
(1)
where Awaan.
p(onakummss max ma, p is the likelihood ratio? (Chen et al., 2016), and I (
the indicator function. We can adaptively anneal r by setting T proportional to BNN's validation error rate e in each AL iteration.
In practice, we cannot directly compute equation I; instead we estimate with sampled BNN poste- riors: We first acquire K pairs of BNN posterior samples (wo Ø'). The Hamming distances du (w, w') between these pairs BNN posterior samples are computed. Next, we calculate the weight discount factor 1 Asz.via A for each possible label y and each pair {w, @') where du (w, w/) > т. At last, we take the expectation of the discounted weight over all yı: configurations. In summary, ABALANCe(F1.s) is approximated as
(plvis (xx + p(vLa a() Σ (a (1- Aon
2K
Dtrain omitted for simplicity of notations. Note that in our algorithms we never explicitly con- struct equivalence classes on BNN posterior samples, due to the fact that (1) it is intractable to find the exact solution for the mix-diameter clustering problem and (2) an explicit partitioning of the hypotheses samples tends to introduce "unnecessary" edges where the incident hypotheses are
"The likelihood ratio is used here (instead of the likelihood) so that the contribution of "non-informative examples" (e.g., P(y/. w. x1.) const VyL.s, w) is zeroed out.
4

---

B) Published as a conference paper at ICLR 2023
closeby (e.g., if pair of hypotheses lie the adjacent edge between two hypothesis partitions), and therefore may overly estimate the utility of a query. Nevertheless, we conducted an empirical study of variant of BALANCE with explicit partitioning (which underperforms BALANCE). We
defer detailed discussion on this approach, as well as empirical study, to the appendix D.4.
Algorithm Active selection w/ Batch-BALANCE
input: poot.2 pools aquisition batch size coldness parameter 3, threshold t, and downsam- pling subset size [C].
2: draw K random pairs of BNN posterior samples (4*,, 4 1K
3: if B is sufficiently small (see section 4. then
4: AB + GreedySelection(D (Doool, D poools (Wkke 2/ 1K
# see section 3.2
5: else
6:
downsample subset C C Dpool with p(z) ~ (BLLANCE
7: SL.B, H1.B + CLLLANC--Clustrinne D Dpool, {ūk: W/ LK 7,
# see section 3.3
8: AB M1:B
9:
output: AB
In the fully sequential setting, we choose sample with top (BALANCE(I) in each AL itera- tion. the batch-mode setting, we consider two strategies for selecting samples within a batch: greedy selection strategy for small batches and sawpiiiiiioo-uunntoonniiii clustering strategy for large batches. We refer to our full algorithm as MARch-BALANCE (algorithm 1) and expand on the batch-mode extensions in the following two subsections.
3.2
GREEDY SELECTION STRATEGY
To avoid the combinatorial explosion of possible batch number, the greedy selection strategy selects sample æ with maximum ABALANCE(21:5-1 U {=}) in the b-th step of a batch. However, config- uration Vid6 of a subset Zi.6 cxpands exponentially with subset size b. In order to efficiently estimate ABALANCe(TLa) we employ an importance sampling method. The current M configuration sam- ples of 91:b drawn by concatenating previous drawn M samples of V1:6-1 and MM samples of ys (samples drawn from proposal distribution). The pseudocode for the greedy selection strategy is provided in algorithm 2. We refer the readers appendix B.2 for details of importance sampling and to appendix B.3 for details of efficient implementation.
Algorithm 3 BALANCE CLLLstcc-Clustrinn
Algorithm GreedySelection
1: input: C CDPpool Dpoot. {ak, ( 1= threshold
1
1: input: set of samples 'D, Dppoll
т. coldness parameter 8, and cluster number B
[ak, w 1 k=1. threshold r, and B
2: sample initial centroids O (m4 1 C with
2: Ao = /
p(x) ~ ABALANCK
3: for b E B do
3: while O not converged do
4:
for all x E AD do So + ABALANCE (Ap U{+})
4: for all
do
5:
5: 0g <- arg max, TANALANCE (2,
6:
Øb f arg max AD-1 Su
6: S, {2r C.:: ar j}
7: A + Ar-1 ((rz)
7:
for all j E [B] do
8: output: batch An- ( v
8: My arg max,es, Exes, Innse (I.
output: S1.B, P1.B
3.3 STOCHASTIC BATCH SELECTION WITH POWER SAMPLING AND CALUSTEIIIN
A simple approach to apply our new acquisition function to large batch is stochastic batch se- lection (Kirsch et al., 2021a), where we randomly select a batch with power distribution p(x) (I) We call this algorithm PowerBALANCE.
Next, we sought to further improve PowerBALANCE through novel aequisition-funeti clustering procedure. Inspired by Kothawade et al. (2021), we define a novel information measure
I AApLANCc (x., y) for any two data samples and y based on our acquisition function:
LagALoce (x, ABALANCE(2:) + ABALANCE(U) ABaLANCE ((2,)) y))
(3)

---

Published as a conference paper at ICLR 2023
Intuitively, ASSLLNN (I, y) captures the amount of overlap between and y w.r.t. ABALANCE. There- fore, natural to use it as a similarity measure for clustering, and use the cluster centroids as candidate queries. The BALANCE-Cluste Clustering algorithm is illustrated in algorithm 3.
Concretely, we first sample a subset C C. D pool with p(x) ~ A (2) similar to (Kirsch et al., 2021a). The BALANCE-Clusten
Eunl-iden metric) to find B cluster centroids (see Line 3-8 in algorithm 3): it takes the subset C, {Wt, 06 ] threshold T, coldness parameter 3, and cluster number B input. It first samples initial centroids O with p(r) ~ ABALANCe(2))) Then, it iterates the process of adjusting the clusters and centroids until convergence and outputs B cluster centroids as candidate queries.
then runs an Lloyd's algorithm (with
EXPERIMENTS
In this section, we sought to show the efficacy of Batch-BALANCE on several diverse datasets, under both small batch setting and large batch setting. In the main paper, focus accuracy as the key performance metric as is commonly used in the literature; supplemental results with different evaluation metrics, including macro-average AUC, FI, and NLL, are provided in appendix D.
4.1 EXPERIMENTAL SETUP
Datasets In the main paper, we consider four datasets (i.e. MNIST (LeCun et al., 1998), Repeated- MNIST (Kirsch et al., 2019), Bushion-MNISS (Xiao et al., 2017) and EMNIST (Cohen et al., 2017)) as benchmarks for the small-batch setting, and two datasets (i.e. SVHN (Netzer al., 201 1), CIFAR (Krizhevsky et al., 2009)) as benchmarks for the large-batch setting. The reason for making the splits is that for the more challenging classification tasks on SVHN and CIFAR- 10, the performance improvement for all baseline algorithms from a small batch (e.g.. with batch size < 50) is hardly visible. We split each dataset into unlabeled AL pool D poot. initial training dataset Dirain, validation dataset Daat, test dataset Diest and unlabeled dataset Ppoot DD Ppnot is only used for calculating the Hamming distance between hypotheses and is never used for training BNNs. For more experiment details about datasets, see appendix C.
BNN models At each AL iteration, sample BNN posteriors given the acquired training dataset and select samples from Ppool to query labels according to the acquisition function of a chosen algorithm. To avoid overfitting, we train the BNNs with MC dropout at each iteration with early stopping. for MNIST, Repeated-MNNI MNIST, EMNIST, and FashionMNIST, we terminate the training of BNNs with patience of 3 epochs. For SVHN and CIFAR- 10, terminate the training of BNNs with patience of 20 epochs. The BNN with the highest validation accuracy is picked and used to calculate the acquisition functions. Additionally, BNN to mitigate the bias introduced by imbalanced training data. The BNN models are reinitialized each AL iteration similar Gal et al. (2017); Kirsch al. (2019). decorrelates subsequent acquisitions as the final model performance is dependent on a particular initialization. We use Adam optimizer (Kingma & Ba, 2017) for all the models in the experiments.
use weighted cross-entropy loss for training the
For cGGMMCMC, we use ResNet- 18 (He et al., 2016) and run 400 epochs in each AL iteration. We set the number of cycles to and initial step size to 0.5. samples are collected in each cycle.
under different bach sizes For small AL batch with B < 50, Batch-BALANCE takes the greedy selection approach. For large AL batch with 2 50, BALANCE takes the clustering approach described in section 3.3. In the small batch-mode setting, if < 4, Batch-Bal BALANCE enumerates all yı configurations to compute the acquisition function
Acquisition criterion for
A (Batch--Jtt -BALLNC according to equation 2; otherwise, it uses M 10, 000 MC samples of yıs and importance sampling to estimate ABatch-BAA BALANCE according to equation 6. All our results report the median of 6 trials, with lower and upper quartiles.
Baselines For the small-batch setting, we compare Batch-BALANCE with Random, Variation Ratio (Freeman& & Freeman, 1965), Mean STD (Kendall et al., 2015) and BatchBALD. To the best of the authors' knowledge, Batch-BALD still achieves state-of-the-art performance for deep Bayesian AL with small batches. For large-batch setting, is longer feasible to run BatchBAL.D (Citovsky

---

Published as a conference paper at ICLR 2023
et al., 2021); consider other baseline models both in Bayesian setting, e.g., PowerBALD, and Non-Bayesian setting, e.g., CoreSet and BADGE.
4.2 COMPUTATIONAL COMPLEXITY ANALYSIS
Table I shows the computational complexity of the batch-mode AL algorithms evaluated in this pa- per. Here, C' denotes the number of classes, B denotes the acquisition size, K is the pair number of posterior samples and M is the sample number for y1:b configurations. We assume the number of the hidden units H. T is # iterations for BALANCE- LLLAANC-CCuutrinnggg to converge and usually less than 5. In figure 2 we plot the computation time for single batch (in seconds) by different algo- rithms. As the batch size increases, variants of Batch- BALANCE (including Batch-BALAND PowerB PowerBALANCE ALANCE as its special case) both outperforms CoreSet in run time. In later subsections, we will demonstrate that this gain in computational efficiency does not come at a cost of performance. We refer interested readers to section B.4 for extended discussion of computational complexity.
and
AL algorithms
Complexity
Mean STD
D pool (CK + log B1)
Variation Ratio
pool (CK + log B))
Cardet
PowerBAI.D
pool (CK Ing Ri)
1008
BatchBALD
[[ goal BMK)
3008
CoreSct (2-approx)
O poot HB)
BADGE
O Pual H
600
PowerBALANCE
O ( pooll (C 2K + log Bi)
Balch-BALANCE
O ([Ppol BM-2K
(GreedySelection)
Batch-BALANCE
O(Dprll C-2K 2K (C 2K +2))
(BALeNGI-Clusterinng)
Table I: Computational complexity of AL algorithms.
Figure 2: Run time vs. batch size.
4.3 BATCH-MODE DEEP BAYESIAN AL WITH SMALL BATCH SIZE
We compare 5 different models with acquisition sizes == 1, B and B 10 on MNIST dataset. K = 100 for all the methods. The threshold r for Aatch-BALANCE, is annealed by setting to E/2 in each AL loop. Note that when B 3, we can compute the acquisition function with all V/sh configurations for b 2, When b > 4, we approximate the acquisition function with importance sampling. Figure 3 (a)-(c) show that BaCcCBBALANCE are consistently better than other baseline methods for MNIST dataset.
with other baseline methods on three datasets with balanced Rushion-MNIST and SAMNIST-Balancee The acquisition size B for ReNEated-MNIST and Fashion-MNIST is 10 and is 5 for EMNIST-Balanced dataset. The threshold of
We then compare Meaasss-Repeated--MNMV
is annealed by setting in figure 3 (d)-(f). For Sapeated-MNIS dataset, BALD performs poorly and is worse than random selection. BatchBALD is able cope with the replication after certain number of AL loops, which is aligned with result shown in Kirsch et al. (2019). BRRch-BBLANCE is able to beat all the other methods on this dataset. An ablation study about repetition number and performance can be found in appendix D.2. For Fashion-MNISS dataset, Batch- B BALANCE outperforms random selection but the other methods fail. For EMNIST dataset, Batch- BALANCE is slightly better than BatchBAL.D.
shown e/4 The learning curves of accuracy
We further compare different algorithms with two unbalanced datasets: EMMIST-ByMest EMNIST-ByClass The for Batch- BBAChBBBLANCEEE is set E/4 in each AL loop. B = 5 and K 10 for all the methods. As pointed out by Kirsch et al. (2019), BatchBALD performs poorly in unbalanced dataset settings. BALANCE and Batch-BAL BAACCB can cope with the unbalanced data settings. The result is shown in figure 3 (g) and (h). Further results on other datasets and under different metrics are provided in appendix D.
and
4.4 BATCH-MODE DEEP BAYESIAN AL WITH LARGE BATCH SIZE
BatCh-BALANCE with MC dropout We test different AL models on two larger datasets with larger batch size. The acquisition batch size B is set 1,000 and e/8. We VGG-11 as the BNN and train it on all the labeled data with patience equal to 20 epochs in each AL iteration. The
Empirically we find that E [s/8,e/2] works generally well for all datasets.
7

---

Published as a conference paper at ICLR 2023
Sce
(a) MNIST
(b) MNIST
(C) MNIST
(d) Repeated-MNIST
1, K 100
B = 3, K 100
10, 100
B 10, K 100
(c) MaSSion-MNIST B 10, K = 100
(f) MMMNIST-Balanced B 5, K 10
gg) EMNiST-ByMcrge == 5, K 10
(h) EMNNSTTByCCaa B 5, K 10
Figure 3: Experimental results on MNIST, Repeated-MNIST EMNIST-ByClas and EMNIST-ByMest datasets in the small-batch regime. For all plots, the y- axis represents accuracy and r-axis represents the number queried examples.
100
35
8.0
6:29
845
431
Libiii
(a) ACC, MC dropout, SVHN
(b) ACC, MC dropout, CIFAR-10 (c) ACC, eSG-MCMC, CIFAR-10
Figure 4: Performance on SVHN and CIFAR-10 datasets in the large-batch regime.
VGG-11 is trained using SGD with fixed learning rate 0.001 and momentum 0.9. The size of C for Batch-BALANCE set to 2B. Similar to PowerBALD (Kirsch al., 202 a), we also find that PowerBALance and BAtncB are insensitive to 3 and 3 works generally well. We thus set the coldness parameter 3 for all algorithms.
The performance of different AL models these two datasets is shown in figure 4 (a) and (b). PowerBALD, PowerBALANCE. BADGE, and BatchBALANCE get similar performance on SVHN dataset. For CIFAR- 10 dataset, BatchBALANCE shows compelling performance. Note that PowerBALANCE also performs well compared to other methods.
with cSG-MCMC We test different AL models with cSG-MCMC CIFAR- 10. The acquisition batch size B 5,000. The size of for Batch-BALANCE set to 3B. In the average activations of all posterior samples'
order apply CoreSet algorithm to BNN, final fully- fully-connected layers as the representations. For BADGE, we use the label with maximum average predictive probability as the hallucinated label and use the average loss gradient of the last
8

---

Published as a conference paper at ICLR 2023
layer induced by the hallucinated label as the representation. We can from figure 4 (c) that BAch-BBAAACCE achieve the best performance.
5 RELATED WORK
Pool-based batch-mode active learning Batch-mode AL has shown promising performance for practical AL tasks. Recent works, including both Bayesian (Houlsby et al., 2011; Gal et al., 2017; Kirsch et al., 2019) and non-Bayesian approaches (Sener & Savarese, 2017; Ash et al., 2019; Citovsky et al., 2021; Kothawade et al., 2021; Hacohen et al., 2022; Karanam et al., 2022), have been enormous and we hardly do it justice here. We mention what we believe are most relevant in the following. Among the Bayesian algorithms, Gal et al. (2017) choose a batch of samples with top acquisition functions. These methods can potentially suffer from choosing similar and redun- dant samples inside each batch. Kirsch et (2019) extended Houlsby et al. (2011) and proposed a batch-mode deep Bayesian AL algorithm, namely BatchBALD. Chen & Krause (2013) formal- ized a class of interactive optimization problems as adaptive submodular optimization problems and prove greedy batch-mode approach to these problems is near-optimal
compared to the optimal batch selection policy. ELR (Roy & McCallum, 2001) focuses on a Bayesian estimate of the re- duction in classification error and takes one- mne-step-look-abie
startegy. Inspired by ELR, WMOCU (Zhao et al., 2021) extends MOCU (Yoon et al., 2013) with a theoretical guarantee of convergence. However, none of these algorithms extend the batch setting.
Among the non-Bayesian approaches, Sener & Savarese (2017) proposed a CoreSet approach to select subset of representative points batch. BADGE (Ash al., 2019) selects samples by using the K-MEAMS++ seeding algorithm on the Ppool representations, which are the gradient embeddings of DNN's s last layer induced by hallucinated labels. Contemporary works propose AL algorithms that work for different settings including text classification (Tan et al., 2021), domain shift and outlier (Kirsch et al., 2021b). low-budget regime (Hacohen al., 2022), very large batches (e.g., 100K or 1 1M) (Citovsky et al., 2021), rare classes and OOD data (Kothawade et al., 2021).
Bayesian neural networks Bayesian methods have been shown to improve the generalization performance of DNNs (Hernández-LLobate & Adams, 2015; Blundell et al., 2015; Li al., 2016b; Maddox et al., 2019), while providing principled representations of uncertainty. MCMC methods provides the gold standard of performance with smaller neural networks (Neal, 2012). SG-MCMC methods (Welling & Tch, 2011; Chen et al., 2014; Ding et al., 2014; Li et al., 2016a) provide promising direction for sampling-based approaches in Bayesian deep learning. cSG-MCMC (Zhang et al., 2019) proposes a cyclical stepsize schedule, which indeed generates samples with high fidelity to the true posterior (Fortuin et al., 2021; Izmailov et al., 2021). Another BNN posterior approx- imation is MC dropout (Gal & Ghahramani, 2016; Kingma al., 2015). We investigate both the cSG-MCMC and MC dropout methods as representative BNN models in our empirical study.
Semi-supervised learning Semi-supervised learning leverages both unlabeled and labeled exam- ples in the training process (Kingma et al., 2014; Rasmus et al., 2015). Some work has combined AL and seme-super learning (Wang et al., 2016; Sener & Savarese, 2017; Sinha et al., 2019). Our methods are different from these methods since our methods never leverage unlabeled data to train the models, but rather use the unlabeled pool to inform the selection of data points for AL.
6 CONCLUSION AND DISCUSSION
We have proposed scalable batch-mode deep Bayesian active learning framework, which lever- ages the hypothesis structure captured by equivalence classes without explicitly constructing them. Batch-BALANCE selects batch of samples at each iteration which can reduce the overhead of retraining the model and save labeling effort. By combining insights from decision-theorrtic ac- tive learning and diversity sampling, the proposed algorithms achieve compelling performance ef- ficiently on active learning benchmarks both in small batch- and large batch-mode settings. Given the promising empirical results the standard benchmark datasets explored in this paper, further interested in understanding the theoretical properties of the equivalence annealing algorithm under controlled studies future work.

---

Published as a conference paper at ICLR 2023
Acknowledgement. This work was supported in part by C3.ai DTI Research Award 049755, NSF award 2037026 and an NVIDIA GPU grant. Any opinions, findings, conclusions, or recommenda- tions expressed in this material are those of the authors and do not necessarily reflect the views of any funding agencies.
REFERENCES
Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra Perez, and Jorge Luis Reyes Ortiz. A public domain dataset for human activity recognition using smartphones. In Proceedings of the 21th International European Symposium on Artificial Neural Networks, Computational Intelli- gence and Machine Learning, pp. 437-442, 2013.
Jordan Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv:1906.03677 2019.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks, 2015.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient hamiltonian monte carlo. In International conference machine learning, pp. 1683-1691. PMLR, 2014.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning (ICML), June 2013.
Yuxin Chen, S. Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information maxi- mization: When greedy near-optimal? In Proc. International Conference on Learning Theory (COLT), July 2015.
Yuxin Chen, S. Hamed Hassani, and Andreas Krause. Near-optimal bayesian active learning with correlated and noisy tests, 2016.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Ros- tamizadeh, and Sanjiv Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 34:1:133:1111111 1933-11944, 2021.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: an extension of mnist to handwritten letters. arXiv preprint 1rXiv:1702.05373, 2017.
Luke N Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey, Cinic- is not imagenet or cifar-10. arXiv preprini arXiv: 1810003800003 2018.
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert D Skeel, and Hartmut Neven. Bayesian sampling using stochastic gradient thermostats. Advances in neural information pro- cessing systems, 27, 2014.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv: 2018.
Andrew Foong.
David Burt, Yingzhen Li, and Richard Turner. On the expressiveness of approximate inference in bayesian neural networks. Advances in Neural Information Processing Systems, 33: 15897-15908, 2020.
Vincent Fortuin, Adrià Garriga-Alonso, Florian Wenzel, Gunnar Rätsch, Richard Tumer, Mark van der Wilk, and Laurence Aitchison. Bayesian neural network priors revisited. arXiv preprint 201.::2102.06571, 2021.
I Linton C Freeman and Linton C Freeman. Elementary applied statisties: for students behavioral science. New York: Wiley, 1965.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059. PMLR, 2016.
10

---

Published as a conference paper at ICLR 2023
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183-1192, PMLR, 2017.
Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal bayesian active learning with noisy observations. arXiv preprint arXiv:1010.309/ 2010.
Teofilo Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical com- puter science, 38:293-306, 1985.
Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on budget: Opposite strategies suit high and low budgets. arXiv preprint arXiv:2202.02794. 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
José Miguel Hernández-Lobate and Ryan Adams. Probabilistic backpropagation for scalable learn- ing of bayesian neural networks. In International conference machine learning, pp. 1861- 1869. PMLR, 2015.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:1112.5745 2011.
Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Jiaji Huang, Rewon Child, Vinay Rao, Hairong Liu, Sanjeev Satheesh, and Adam Coates. Active learning for speech recognition: the power gradients. arXiv preprint arXiv:1612.03226, 2016.
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou Active learning by querying informative and representative examples. Advances in neural information processing systems, 23:892-900, 2010.
Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In International conference machine learn- ing, pp. 4629-4640. PMLR, 2021.
David Janz, Jos van der Westhuizen, and José Miguel Hernández-LLobtto. Actively learning what makes discrete sequence valid. arXiv preprint arXiv:1708 04465, 2017.
Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, Drew Bagnell, and Siddhartha Srini- vasa. Near optimal bayesian active learning for decision making. In Artificial Intelligence and Statistics, pp. 430-438. PMLR, 2014.
Athresh Karanam, Krishnateja Killamsetty, Harsha Kokel, and Rishabh K lyer. Orient: Submodular mutual information measures for data subset selection under distribution shift. Advances in neural information processing systems, 2022.
Alex Kendall, Vijay Badrinarayanan, and Roberto Cipolla. Bayesian segnet: Model uncertainty in deep convolutional encoder-decoder architectures for scene understanding. arXiv preprint arXiv:1511.02680 2015.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Diederik Kingma, Danilo J Rezende, Shakir Mohamed, and Max Welling. Semi-supervised learn- ing with deep generative models. arXiv preprint 140.52.400.5298, 2014.
Diederik P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparame- terization trick. arXiv preprint arXiv:1506.0253: 2015.
Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. arXiv preprint arXiv: 08....88/3 158, 2019.
Andreas Kirsch, Sebastian Farquhar, and Yarin Gal. A simple baseline for batch active learning with stochastic acquisition functions. arXiv preprint arXiv:2106. /2059, 2021a

---

Published as a conference paper at ICLR 2023
Andreas Kirsch, Tom Rainforth, and Yarin Gal. Test distribution-aware active learning: A principled approach against distribution shift and outliers. arXiv preprint arXiv:2106.11719 2021b.
Murat Koklu and llker Ali Ozkan. Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174:105507, 2020.
Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh lyer. Similar: Submodular information measures based active learning in realistic scenarios. Advances Neural Information Processing Systems, 1685-18888,,77 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2) 1998.
Chunyuan Li, Changyou Chen, David Carlson, and Lawrence Carin. Preconditioned stochastic gradient langevin dynamics for deep neural networks. In Thirtieth AAAI Conference on Artificial Intelligence, 2016a.
Chunyuan Li, Andrew Stevens, Changyou Chen, Yunehen Pu, Zhe Gan, and Lawrence Carin. Learn- ing weight uncertainty with stochastic gradient meme for shape classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5666-5675, 2016b.
Dennis V Lindley. On measure of the information provided by an experiment. The Annals of Mathematical Statistics, pp. 986-1005, 1956.
Qiang Liu, Zhaocheng Liu, Xiaofang Zhu, Yeliang Xiu, and Jun Zhu. Deep active learning by model interpretability. arXiv preprint arXiv:2007.12100 2020.
David MacKay. Information-base objective functions for active data selection. Neural computa- fion, 4(4):590-66) 1992.
Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson A simple baseline for bayesian uncertainty deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Sudhanshu Mittal, Maxim Tatarchenko, Özgün Çięek, and Thomas Brox. Parting with illusions about deep active learning. arXiv preprint arXiv: 19/2.05661, 2019.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011.
Natalia Ostapuk, Jie Yang, and Philippe
Activelink: deep active learning for link prediction in knowledge graphs. In The World Wide Web Conference, pp. 1398-1408, 2019.
Joaquin Quinonero-Candela, Carl Edward Rasmussen, Fabian Sinz, Olivier Bousquet, and Bern- hard Schölkopf. Evaluating predictive uncertainty challenge. In Machine Learning Challenges Workshop, pp. 1-27. Springer, 2005.
Antti Rasmus, Harri Valpola, Mikko Honkala, Mathias Berglund, and Tapani Raiko. Semi- supervised learning with ladder networks. arXiv preprint arXiv: 1507.02672, 2015.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through monte carlo estima- tion of emror reduction. ICML, Williamstown, 2:441 1488,1448,1 2001.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach, arXiv preprint 1eXiv:/70..004 2017.
Burr Settles. Active learning. Synthesis lectures on artificial intelligence and machine learning, (1):1-114, 2012.
12

---

Published as a conference paper at ICLR 2023
Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-427 423, 1948.
Yanyao Shen, Hyokun Yun, Zachary C Lipton, Yakov Kronrod, and Animashree Anandkumar. Deep active learning for named entity recognition. arXiv preprint arXiv: 2017.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 5972-5981, 2019.
Wei Tan, Lan Du, and Wray Buntine. Diversity enhanced active learning with strictly proper scoring rules. Advances in Neural Information Processing Systems, 34:10906-10918, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1)), 2008.
Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actua- fors B: Chemical, 166:320-324 229,, 2012.
Keze Wang. Dongyu Zhang, Ya Li. Ruimao Zhang, and Liang Lin. Cost-effective active learning for deep image classification. IEEE Transactions on Circuits and Systems for Video Technology, 27(12):2591-2600 2016.
Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Transactions on Knowledge Discovery from Data (TKDD), 9(3):1-23, 2015.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 681-688. Citeseer, 2011.
Florian Wenzel, Kevin Roth, Bastiaan S Veeling, Jakub Swiętkowski, Linh Tran, Stephan Mandt, Jasper Snoek, Tim Salimans, Rodolphe Jenatton, and Sebastian Nowozin. How good the bayes posterior in deep neural networks really? arXiv preprint arXiv:2002.02405, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv: 778.00747, 2017
Yifan Yan, Sheng-Jun Huang, Shaoyi Chen, M. Liao, and J. Xu. Active learning with query genera- tion for cost-effective text classification. In AAAI, 2020.
Byung-Jun Yoon, Xiaoning Qian, and Edward R Dougherty. Quantifying the objective cost of
uncertainty in complex dynamical systems. IEEE Transactions on Signal Processing, 61(9):2256- 2266, 2013.
Ruqi Zhang, Chunyuan Li, Jianyi Zhang, Changyou Chen, and Andrew Gordon Wilson. Cyclical stochastic gradient meme for bayesian deep learning. arXiv preprint wwXiv:1902.03330 00000.0..3222... 2019.
Guang Zhao, Edward Dougherty, Byung-Jun Yoon, Francis Alexander, and Xiaoning Qian. Uncertainty-aware active learning for optimal bayesian classifier. In International Conference on Learning Representations (ICLR 2021), 2021.
13

---

Published as a conference paper at ICLR 2023
CONTENTS
Appendices
Table of Contents
Preliminary works
A.1
The most informative selection criterion
15
A.2 Equivalence class edge cutting
15
A.3 The equivalence class edge discounting algorithm
16
B Algorithmic details
16
B.1
Derivation acquisition functions BALANCE and Mich-BBLAANCE
16
Importance sampling configurations
B.3 Efficient implementation for greedy selection
18
B.4 Detailed computational complexity discussion
18
C Experimental setup: Datasets and implementation details
19
C.I Datasets used in the main paper
19
C.2 Implementation details on the empirical example in figure
20
Supplemental empirical results
20
D.1 Effect of different choices of hyperparameters
20
D.2 Experiments other datasets
21
D.3 Additional evaluation metries
24
D.4 BALANCE via explicit partitioning over the hypothesis posterior samples
25
D.5 Coefficient of variation
26
D.6 Predictive variance..
26
D.7 Batch-BALANCE with multi-chain cSG-MCMC
26
14

---

Published as a conference paper at ICLR 2023
A PRELIMINARY WORKS
A.1 THE MOST INFORMATIVE SELECTION CRITERION
BALD uses mutual information between the model prediction for each sample and parameters the model as the acquisition function. It captures the reduction of model uncertainty by receiving a label y of a data point z: 1 (y:w z, D Purain) = (y æ, Dtrain) - -Ep( Derain)) [H (y 2; w, Purii)) where Hi denotes the Shannon entropy (Shannon, 1948). Kirsch et al. (2019) further proposed BatchBALD as an extension of BALD whereby the mutual information between a joint of multiple data points and the model parameters estimated as
BaschBALDD Durain) - I(y1::1 W
Ti:b: Derain).
Limitation of the BALD algorithm BALD be ineffective when the hypothesis samples heavily biased and cluttered towards sub-optimal hypotheses. Below, we provide a concrete example where such selection criterion may be undesirable.
h
b2
h
hn
Figure 5: A stylized example where the most informative selection criterion underperforms the cquivalence-clas--aseee criterion.
Consider the problem shown figure 5. The hypothesis class Ht = {h1, hn is structured such that
12--i-21- if 21-1 121- -2--1-22-1
du du(h,, h2)
where du(h,, hy) denotes the fraction of labels h4 and h, disagree upon when making predictions on i. samples data points. We further assume that for any subset of hypotheses S S H. there exists data point whose label they agree upon. Assume each hypothesis h; has equal probability and the target error rate a. On the one hand, note that BALD does not consider (u h2), and therefore hand, to achieve a target error rate of σ, one only needs to differentiate all pairs of hypotheses hi, by of distance (ha, hT) a (i.e., by selecting training examples rule out at least one of hi hy). Therefore, a "smarter" AL policy could query examples to sequentially check the consistency of h1, fi...... ., hn until all remaining hypotheses are within distance a. easy check that this requires log(1/ar) examples before reaching the error rate ar. The gap between B BALD and the above could be large increases.
average requires log examples identify any target hypothesis. On the other
policy log log(1/o)
A.2 EQUIVALENCE CLASS EDGE CUTTING
Consider the problem statement in section 2.1. I 0 and tests are noise-free, this problem can be solved near-optimally by the equivalence class edge cutting (EC*) algorithm (Golovin et al., 2010). EC² employs an edge-cutting strategy based on weighted graph G = (H, where vertices represent hypotheses and edges link hypotheses that we want to distinguish between. Here A h',,h') r(h) + r(h')) contains all pairs of hypotheses that have different equivalence classes. We define a weight function W
+ Rzo by W W(fh, h')) & p(h) p(h'). A sample with label is said to "cut" an edge, if at least one hypothesis is inconsistent with y. Denote E(z, y) A {[h, h') E E p(y h) = 0 V p(u I h²) 0} the set of edges cut by labeling y. The E objective is then defined as the total weight of edges cut by the current Drrain: SEO (Drrain) A W (U(r.)) E E v)) EC² algorithm greedily maximizes this objective per iteration. The acquisition function for EC is
A EC2 (x Derain) A E.y [ (Darain U (x,, y)}) ((Dtrain) D Dirain)
(4)
15

---

Published as a conference paper at ICLR 2023
A.3 THE EQUIVALENCE CLASS EDGE DISCOUNTING ALGORITHM
In the noisy setting, the acquisition function of Equivalence Class Edge Discounting algorithm (ECED) (Chen et al., 2016) takes undesired contribution by noise into account. Given data point and its label (ar, v), ECED discounts all model parameters by their likelihood ratio: An. - p(ylh,.) max,, p(y After we get Derain, the value of assigning label y to a data point x is defined as the total amount of edge weight discounted: 8(r, | Derain) (EE P(h, D Ptrain)
(1 AB. at) where & {[h, h') r(h) & r(h(} consists of all unordered pairs of hypothesis corresponding to different equivalence classes. Further, ECED augments the above value function with an offset value such that the value of non-informative test is O. The offset value of labeling
as label y defined as: v(2,y y Dirain) ) _ (h,,eee p(h, Purain)((h' Pursin) (1 max, xh..))
The overall acquisition function of ECED is:
(ECED( (irain) - Ey (ō(x, y Dirain) - v(x, y Derain))
(5)
B ALGORITHMIC DETAILS
B. DERIVATION OF ACQUISITION FUNCTIONS OF BALANCE AND
In each AL loop, the ECED algorithm selects sample from AL pool according to the acquisition function
Waswrr (--AusyAWaan - max 22.w ))
(ECED( Dirain) - By
Σ
[Wis JEE
where & the total edges with adjacent nodes in different equivalence classes and Away max, p(u'laj Wa is the weight for edge {w,w') which is maintained by ECED algorithm. After we observe y of selected æ, we update the weights of all edges with Ww, Www. p(y w)p(y/ w'). In the deep Bayesian AL setting, the offset term max X can be removed when we use deep BNN. However, we can not enumerate all {w, w'} E in this setting since there are an infinite number of hypotheses in the hypothesis space. Moreover, we can not even estimate the acquisition function of ECED on a subset of sampled hypotheses by MC dropouts since building equivalence classes with best is NP-hard.
p(ylw)
we sample {w, w'} according to posterior p(w Derain) and check whether (w.w'} E E by Hamming distance in the way we describe in section 3.1, we will get
AFCED (xr Drraii)
Σ (WE JEE
Wwse (1 dw
Waw
Eur mpp(u) (ppll dd p(w Deraiu )p(w' D Derain)
(1
Aw.
xIE,, [TE (apllw"ppllPaat du(w))))) (1 \wc.Da'.)))]
Inspired by the weight discounting mechanism of ECED, we define the acquisition function of BAL- ANCE ABALANCE(2) Deeain) as
ABALANCE(s 'Dtrain)
A E. [Bw.w// (epla/ da(ww))) (1 - Au..gr-rt.)))
After we get pairs of MC dropouts, the acquisition function ABALANCU( Dirain) can be ap- proximated as follows:
ABALANCE Dursin)
Eppce/DDin (rreat)) (p(()w))
Adu(woo) (1 Awogdwr.oo
1 dd((an)))2 (1 den senrddr
p0 (e) p( ab))
2K
K
k=
16

---

Published as a conference paper at ICLR 2023
In batch-mode setting, the acquisition function of BatCh-BALANCE for batch 21:5 is
Pirain) _
Egns [[w, Purnin) (ds(ww"))) (1 Auy do (nra)))))
Similar to the fully sequential setting, we can approximate Baatthh-BLLNCCEE D Drrain) with K pairs of MC dropouts. The Z1.5 are chosen in a greedy manner. For iteration b inside a batch, the U1:b-1 are fixed and zb is selected according to
A Batch- BALANCE (E1:b Derain)
-Bplw (Derat)) E pp(naa)w) (o Derai)) ddn(ww)) (1 dusio Au Au' swa))
1
(d)(s),0()) (1 (1- don
pius (b6) + p(11:0 w/b)
2K
K
V1.b
B.2 IMPORTANCE SAMPLING OF CONFIGURATIONS
When b becomes large, it is infeasible to enumerate label configurations F1 We use M MC samples of f1:s to estimate the acquisition function and importance sampling to further reduce the computational time*. Given that p(y1:b w) can be factorized as p(31:0-1 w) P(u w). the acquisition function can be written as:
Batch- BALANCE(TI:d
Dtrain)
A Byn Ep(a)Deram) ((llwr)()))))) (1 Auainis Awn mnno
-E -Eplw/ Ep(erok>
((( >rr (1 Awarnis Awr Awrs
-er(w/Denns) Brtens Bp(sslw) NuwuliptulDeesn da(wew))>r (1 desonn
Suppose we have M samples of V/88-1 from p(U1s-1), we perform importance sampling using p()):--) 1) to estimate the acquisition function:
A (F Dirain)
p w)
-Bptw Derai) )
p(y1--1) Ep(usle) bw) [B Deran)) (nll)w))))r Auaan Awr ans)
p w)
= -Bplyno-1) Eeptl- ((ol
(Bu Duain)) - (dnlew))) (1 Ausaars dwr
p(y10-1)
R 1 p(ina- (x) Wa) + p(ina- (p)p(( ak)
1(
1116-1 No
1
(() (1 NomeeoA
K
K [dd(en
)
(1-1
P1ab- 2 Pb
Prr
PLo-1 @ Pb)
PT P...IPP P, + PrT Py
1:0-1
A
A
M 1T (Pio-1 + Br Pio-1
Here we save P(i16-1 (x)) and p(i1.-1 (g) for M samples in Pi.0-1 and Pi. The shape of PIos-1 and Pioa-1 is K x M. @ is element-wise matrix multiplication and @ is the outer- product operator along first dimension. After the outer product operation, we can reshape the matrix by flattening all the dimensions after the Ist dimension. I is a matrix of Is with shape K x 1. PT P.. P, and PIT PiT_,PP P/ are of shape M x C and their sum is reshape to 1 x MC after divided by 1 (P10-1+ P
'A similar importance sampling procedure proposed in Kirsch et al. (2019) to estimate the mutual information. Here, show how adapt the strategy enable efficient estimation of ABatch #Batch-BALANCE:
17

---

Published as a conference paper at ICLR 2023
B.3 EFFICIENT IMPLEMENTATION FOR GREEDY SELECTION
In algorithm 2. we can store P(11.-1 @x) in matrix P1o-1 and p(11:-11 ( in matrix P1:b-1
for iteration b - The shape of Pia-1 and Pi 16-1 is K x Ch-1, p(ū6 (x) can be stored in Pb and p(ús (x/)) in Pg. The shape of Po and P/ is K x C. Then, we compute probability of p(in:)) follows:
P(U1.))
p (x) p(11 (f))
2K
Σ
p Wk)p(0r (xk)) + p(i10-1 4pp( (4))
2K
k=1
(PIT. 111b-1 Po
PI. Pb).
2K
The PT. Po and PIT 11001 P/ can be flattened to shape Oh after matrix multiplication. We store max p(11:0-1 @x) in a matrix A1 and max p(810-1 (f)) in a matrix A
The shape of A1:0-1 and A/.6-1 is K x 1. We can compute A inside edge weight discount expression by
Avs A1.6-1 2 max Po:
P(11:6 (x)) p(01:6011 (p)p wx) = PI.-- 60 Po;
P(iL wik
Pi:b-1 @ Pb
max p(ū1:6 wx)
Av
C is element-wise matrix multiplication and & is the outer-product operator along the first dimen- sion. After the outer product operation, we can reshape the matrix by flattening all the dimensions after 1st dimension to maintain consistency. Similarly, we can compute A1. P(i1: ax) and Aar ihs with matrix operations. The indicator function 11 (W2 can be stored in a matrix with shape K 1. The acquisition function can be computed with all matrix operations as follows:
A Batch BALANCE (A (11. Dtrain)
Dp((s/Deran LL p((noll)) [Bw rp(ol/ ( (1 Auami Ao wno)
1
(in( (1
p(Dno (w) p(01. w6b
2K
K
1=1
K ((o >
)1
P P1.b- 2
pr
Piab
P%
2K (TT (P..-1
+PT
P1.T-111))
AL
B.4 DETAILED COMPUTATIONAL COMPLEXITY DISCUSSION
As demonstrated in figure 2. figure 6, and table 1, the computational complexity of our algorithm ALANNBALANCE shares comparable to PowerBALD. They all need to estimate the acquisition function value for each data point in the AL pool and then choose the top B data points after adding -usteeldistributed noise to the log values. However, the power sampling- limited performance due to the lack of interaction between selected samples and non-selected sam- ples during sampling. We can further improve the performance PowerBALANCE with Batch- BALANCE. The computation complexity of Batch-BALANCE for large batch setting are propor- tional to B when downsampled with subset size [C) = cB and is a small constant. Its computa- tional complexity is similar to that of BADGE and CoreSet.
methods have
18

---

Published as a conference paper at ICLR 2023
BADGE
PowerBALANY
12000
Batch-BALAs BALANCE
PowerBALD
CoreSet
10000
comptattinn time (sccotdds
8000
4000
2000
512
1448
Istch size
Figure Computation time (in seconds) vs. batch size for different AL algorithms
C EXPERIMENTAL SETUP: DATASETS AND IMPLEMENTATION DETAILS
C.I DATASETS USED IN THE MAIN PAPER
MNIST. We randomly split MNIST training dataset into Deal with 10,000 samples, D Dpool with 10,000 samples and D pool with the rest. The initial training dataset contains 20 samples with 2 samples in each class chosen from the AL pool. The BNN model architecture similar Kirsch et al. (2019). It consists of two blocks of [convolution, dropout, max-pooling, relu] followed by two-layer MLP that two-layer MI.P and one dropout between the two layers. The dropout proba- bility is 0.5 in the dropout layers.
Repeated- MNIST. Kirsch et al. (2019) show that applying BALD to a dataset that contains many (near) replicated data points leads to poor performance. We again randomly split the MNIST training dataset similar to the settings used on MNIST dataset. We replicate all the samples in AL pool two times and add isotropic Gaussian noise with standard deviation of 0.1 after normalizing the dataset. The BNN architecture is the same as the one used on MNIST dataset.
EMNIST: We further consider the EMNIST dataset under 3 different settings: EMNIST-Balancee EMNIST-ByClass, and EMNiST-ByMerge. The AMNIST-BBlanced contains 47 classes with bal- anced digits and letters. EMNIST-ByMerge includes digits and letters for total of 47 unbalanced classes. EMNIST-ByClass represents the most useful organization for classification as it contains the segmented digits and characters for 62 classes comprising [0-9].[a-z], and [A-Z]. We randomly split the training set into D with 18,800 images, Doool with 18,800 images and Dpool with the rest of the samples. Similar Kirsch al. (2019), we do use an initial dataset and instead perform the initial acquisition step with the randomly initialized model. The model architecture contains three blocks of [convolution, dropout, max-pooling, relu], with 32, 64, and 128 3x3 convolution filters and 2x2 max pooling. We add two-layer MLP following the three blocks. 4 dropout layers in total are in each block and MLP with dropout probability 0.5.
Mashion-MNIST Fashion-MNIST is dataset of Zalando's article images that consists of training set of 60,000 examples and test set of 10,000 examples. Each example is a 28x28 grayscale image, associated with label from 10 classes. We randomly split Fashion-MNISS training dataset into Dval with 10,000 samples, D pool with 10,000 samples, and D Pooo with the rest samples. We obtain the initial training dataset that contains 20 samples with 2 samples in each class randomly
19

---

Published as a conference paper at ICLR 2023
chosen from the AL pool. The model architecture is similar to the used EMNIST dataset with 10 units in the last MLP.
SVHN. We randomly select initial training dataset with 5,000 samples, D Poool with 2,000 samples, and validation dataset val with 5,000 samples. Similarly for CIFAR- 10 dataset,
CIFAR-1O. random select initial training dataset with 5,000 samples, Dpool with 5,000 samples, and validation dataset Dval with 5,000 samples.
C.2 IMPLEMENTATION DETAILS ON THE EMPIRICAL EXAMPLE FIGURE
We show an empirical example in figure to provide some intuition as to why BALANCE and Batch-BALANCE are effective in practice. We train BNN with imbalanced MNIST training subset that contains 28 images for each digit in [1-8] and 1 image for digits O and 9. The cross- entropy loss is reweighted balance the training dataset during training. We obtain 200 posterior samples of BNN and use them to get the predictions on pool- We compute the Hamming distances for predictions all sample pairs and use these precomputed distances plot the predictions with t-SNE (Van der Maaten & Hinton, 2008). The equivalence classes are approximated by farthest- first traversal algorithm (FFT) (Gonzalez, 1985). figure I, the equivalence classes are highly imbal- anced. The ground truth D dataset labels represent the target hypotheses embedding. This figure highlights the scenario where the equivalence class-based methods, e.g. ECED and BALANCE are better than BALD.
D SUPPLEMENTAL EMPIRICAL RESULTS
In this section, we provide additional experimental details and supplemental results to demonstrate the competing algorithms.
D.1 EFFECT OF DIFFERENT CHOICES OF IYPERPARAMETERS
We compare BALD and BALANCE with batch size B 1 and different K's on an imbalanced MNIST dataset which is created by removing random portion of images for each class in the training dataset. figure (a) shows that BALANCE performs the best with large margin to the curve of BALD. Note that BALANCE with K = 50 is also better than BALD with K = 100.
0.95
0.9
0.55
0.80
0.80
0.75
0.70
0.75
Bedd-BALANCE
Rech-RAl
Badd-BLLLSCE a5
HALD & - 100
BALaNCA
BALANCE
Bacc-BALLASCE:
BALAXCU A 100
RacchRAlliNCC
50
100
150
2000
200
120
120
200
250
Tomber of Inleeled somples
tramler of Inbeleel
(a) ACC vs. samples for different K's.
(b) ACC vs. samples different r's.
Figure 7: Learning curves of different K and for BALANCE.
20

---

Published as a conference paper at ICLR 2023
monecaal s/iiinaaa acqutaaioon
0.80
0:73
0.70
40
30
120
Figure 8: Estimated acquisition function values ABALANCE of BALANCE vs. posterior sample num- ber K
We also study the influence of for BALANCE on MNIST dataset. Denote the validation error rate of BNN model by BALANCE with fixed 0.05, 0.15, 0.3 and annealing run on MNIST dataset and the learning curves are shown in figure 7 (b). The BALANCE robust to T. However, when is set 0.3 and the test accuracy gets around 0.88, the accuracy improvement becomes slow. The reason for this slow improvement that the threshold T too large and all the treated in the same equivalence class and the acquisition functions
E/2, e/ /4, z/8 are
pairs of posterior samples for all the samples in the AL pool are zeros. In another word, the BALANCE degrades to random selection when is too large.
We further pick an data point from this imbalanced MNIST dataset and gradually increase the pos- terior sample number K estimate the acquisition function value ÁBALANCE for this data point. For each posterior sample number K, we estimate the acquisition function ABLLANCe 10 times with 10 sets posterior sample pairs. The mean and std for this K are calculated and shown figure 8.
D.2 EXPERIMENTS ON OTHER DATASETS
We compare different AL algorithms on tabular datasets including Human Activity Recognition Using Smartphones Data Set (Anguita al., 2013) (HAR), Gas Sensor Array Drift (Vergara al., 2012) (DRIFT), and Dry Bean Dataset (Koklu & Ozkan, 2020), as well as a more difficult dataset CINIC-10 (Darlow et al., 2018).
HAR, DRIFT and Dry Bean Dataset We run 6 AL trials for each dataset and algorithm. In each iteration, the BNNs are trained with a learning rate of 0.01 and patience equal epochs. The BNNs all contain three-layer MLP with ReLU activation and dropout layers in between. The datasets are all split into starting training set, validation set, testing set, and AL pool. The AL pool is also used D Ppoot The for Batch-BALANCE is set e/ 4 in each AL loop. See table for more experiment details of these datasets.
dataset val set size
lest set size
hidden unit # sample per epoch
K
B
HAR
2K
2.947
(64,64)
4,096
20
10
DRIFT
2K
2K
(32,32)
4,096
20
10
Dry Bean
2K
2K
(8,8)
8,192
20
10
Table 2: Experment details for HAR, DRIFT and Dry Bean Dataset
21

---

Published as a conference paper at ICLR 2023
The learning curves of all 5 algorithms these 3 tabular datasets are shown in figure 9. Batch- BALANCE outperforms all the other algorithms for these 3 datasets. For HAR dataset, both Batch- BALANCE and BatchBALD work better than random selection. In figure 9 (b) and (c), Mean STD, Variation Ratio and BatchBALD perform worse than random selection. We find similar effect for some other imbalanced datasets.
3.0
4.7
180
Soua 2CD
Moua Vatatii Baco
Vadicias Bullo
Vataria Pate
BALAMO
Bank AS
RAS
(a) ACC, HAR dataset
(b) ACC, DRIFT dataset
(c) ACC, Dry Bean Dataset
Figure 9: Experimental results on 3 tabular datasets. For all plots, the y-axis represents accuracy and a-axis represents the number queried examples.
CINIC-10 CINIC-10 is large dataset with 270K images from two (Krizhevsky et al., 2009) and ImageNet (Rasmus et al., 2015). The training set is split into an AL pool with 120K samples, 40K D Pool samples, 20K validation samples, and 200 starting training samples with 20 samples in each class. We use VGG-11 as the BNN. The number of sampled MC dropout pairs 50 and the acquisition size is 10. We run trials for this experiment. The learning curves of 5 algorithms are shown in figure 10. We can see from figure 10 that BatCC-BALANCE performs better than all the other algorithms by a large margin this setting.
CIFAR-10 10
0.42
0.40
0.38
0.34
0.32
Random
0.30
BatchBALD
Moan STD
Variation Ratio
Batch-BAL BE
200
400
600
800
1000
1200
1400
samples
Figure 10: ACC vs. samples on the CINIC-10 dataset.
Repeated-MNISST with different amounts of repetitions In order to show the effect redundant data points Bath and Batch-BALANCE, experiments Repeated-MNIST with
22

---

Published as a conference paper at ICLR 2023
increasing number of repetitions. The learning curves of accuracy for Repeated-MNIST with different repetition numbers can be seen in figure 11. A detailed model accuracy on the test dataset when the acquired training dataset size is 130 is shown in table 3. Even though Batch-BALAND can improve data efficiency (Kirsch et al., 2019), there are still large gaps between the learning curves of Batch-BALD and Batch-BALANCE and the gaps become larger when the number of repetitions increases.
050
0.0
0.55
0.70
0.63
0.70
Beazies
BAIGIRALD
Teach BALANCE
Bands BALANCE
0.62
300
sradier labeleed smapphe
seaabor Libided
(a) repeat time
(h) repeat times
0.35
0.50
0.50
Bacdien
Turskon
0.7
Barch BARRSSO
Tucck IEAL ANCK
labeled
(c) repeat times
(d) repeat times
Figure 11: Performance of Random selection, BatchBALD, and
on Repeated- MNIST for an increasing number of repetitions. For plots, the y-axis represents accuracy and r-axis represents the number of queried examples. We can see that BatchBALD also performs worse as the number of repetitions increased. Batch-BALANCS outperforms BatchBALD with large margins and remains similar performance across different numbers of repetitions.
In order to compare our algorithms with other AI. algorithms in this small batch size regime, we fur- ther run PowerBA ALANCE, PowerBAL.D, BADGE and CoreSet on the Repeated-MNIS" with repeat number 3. As shown in figure 12, BAach-BALANC achieves the best performance. Note that both PowerBALD and compared to BADGE algorithm.
are efficient to select AL batch and show similar performance
CIFAR-100 For CIFAR-100, 100, use 100 fine-grained labels. The dataset is split into initial train-
ing dataset with 5,000 samples, 2 Dpool with 5,000 samples, and validation dataset Dval with 5,000 samples. Experiment is conducted with batch size B = 5, 000 and budget 25,000. The cSG-MCMC used for BNN with epoch number 200, initial step size 0.5, and cycle number We can see in figure 13 that both PowerBALANCE and Batch-BALANEE perform well in this dataset.
23

---

Published as a conference paper at ICLR 2023
0.95
0.90
0.85
ACC
0.75
Random
BatchBALD
0.70
CoreSet
BADGE
PowerBALD
0.65
PowerBA BANACC
Batch- Maiel-BATTNCC
50
150
200
250
uumber of labeled camples
Figure 12: ACC vs. # samples on RepeatedMNISST dataset with repeat number
Raudom
CoreSet
RADGE
PowerBALL
0.70
PowerBBALL LANCE
Batch-BALes BLLANCE
0.65
ACC
0.55
0.50
0.0
0.15
5000
7500
10000
12500
15000
17500
20000
22500
25000
rumber of labeled samples
Figure 13: ACC vs. # samples, cSG-MCMC, CIFAR-100
D.3 ADDITIONAL EVALUATION METRICS
Besides accuracy, compared macro-average AUC, macro-average F1, and NLL for different methods on EMNIST-Balanced and EMNIST-ByMerge datasets in figure 14. The acquisition size for all the AL algorithms is 5. Batch-BALANCE, is annealed by setting AUC computes the AUC independently for each class and then takes the average. Both macro- average AUC and macro-average F1 take class imbalance into account. As shown in figure 14, Batch-BALANE BALANCE attains better data efficiency compared with baseline models on both balanced and imbalanced datasets.
s/4. A macro-average
24

---

Published as a conference paper at ICLR 2023
SANNIST-Bllnnce
20
EMNIST Mergrg
(a) Macro-average AUC
(b) Macro-average F1
(c) NLL
Figure 14: Compare different metrics for EMNIST-Balanen and EMNIST-Bymerge
We also evaluated the negative log-likelihood (NLL) for different AL algorithms. NLL is a popular metric for evaluating predictive uncertainty (Quinonero- Candela et al., 2005). As shown in figure 14, Buch-BALANCE maintains better or comparable quality of predictive uncertainty over data.
Counonner-Candella
D.4 BALANCE VIA EXPLICIT PARTITIONING OVER THE HYPOTHESIS POSTERIOR SAMPLES
Another way of estimating the acquisition function is construct the equivalence classes explicitly first (e.g. by partitioning the hypothesis spaces into & Voronoi cells via max-diameter clustering and calculate the weight discounts of edges that connect different equivalence classes. Intuitively, explic- itly constructing equivalence classes may introduce unnecessary edges as two closeby hypotheses can be partitioned into different equivalence classes; therefore leading an overestimate of the edge LaLAACE--arrttiin
weight discounted. We call this algorithm
In order to compare with BALANCE and Batch BAlch-B,LANCE, we sampled K pairs of MC dropouts to estimate the acquisition function of BALANCE-Parittion. All the representations of 2K MC dropouts on Pooo are generated. We run FFT (Gonzalez, 1985) with Hamming distances and thresh- old on these representations to get approximated ECs. Fach data point has at most Hamming distance to the corresponding cluster center. FFT a 2-approx algorithm and the optimal solution with the same cluster number has cluster diameter 5. After equivalence classes are returned, BALANCE-Partinne calculates the edges discounts of edges that connect different equivalence classes and estimates the acquisition function values of each data sample in the AL pool.
Although a faster method that utilizes complete homogeneous symmetric polynomials (Javdani al., 2014) can be implemented estimate the acquisition function values for BALANCF-Parrition experiments figure 15 show that BALANCF--Prttite can not achieve better performance than BALANCE and increasing the MC dropout number does improve performance significantly.
Method
repeat time
repeat times
repeat times
repeat 4 times
Random
0.887 = 0.017
0.883 = 0.012
0.881 = 0.013
0.895 = 0.009
BatchBALD
0.917 + 0.005
0.892 + 0.023
0.883 + 0.025
0.881 + 0.014
Batch-BALANCE
0.926 + 0.008
0.923 + 0.008
0.929 + 0.004
0.927 + 0.010
Table 3: STD of test accuracies when acquired training set size is 130
25

---

Published as a conference paper at ICLR 2023
0.93
0.90
0.53
0.85
0.80
0.80
0.70
0.70
0.63
0.63
BALANCE N - 50
BALasCrs Paritlio K -
BAL Partition K
BALaaCC Corttittioon K
0.00
BALan
0.00
BALasCC-Fartttia
Parttino
100
103
230
labsled scmpiix
Labeled semp
(a) Compare BALANCE--Prrition with BAL-
(b) BALANCE-Partiton with different K
ANCE
Figure 15: ACC vs. # samples for BALANCE-Pattitee and BALANCE.
D.5 COEFFICIENT OF VARIATION
To gain more insight into why BALANCE and Batch-BALANCE work consistently better than BALD and BatchBALD, we further investigate the dispersion the estimated acquisition function values for those methods. Since BALACB and BatchBALD extend their fully sequential algorithms similarly in greedy manner, we only compare the acquisition functions of BALANCE and BALD
The coefficient variation (CV) is chosen for the comparison of dispersion. It is defined as the ratio of the standard deviation the mean. CV is a standardized measure the dispersion of probability distribution or frequency distribution. The value of CV is independent of the unit in which it is taken.
We conduct the experiment on the imbalanced MNIST dataset in the setting of appendix C.2. We estimate the acquisition function values of BALANCE and BALD 5 times with sets of K MC dropouts for each sample in the AL pool. Then, the CVs are calculated for these estimations. In figure 16, we show histograms of CVs for both methods. The estimated acquisition function values of BALANCE are less dispersed, which shows potential for better performance.
D.6 PREDICTIVE VARIANCE
In order to directly compare the accuracy improvement of batches selected by differrnt algorithms, instead of along the course of an AI trial, we conduct experiments with training of various sizes and compare the accuracy improvement of batches selected by AL. algorithmss with the same training The initial training has 10 sampled randomly from Repeated-MNIST. In each step, select 10 random samples and add them to training set. Hypotheses are drawn from BNN posterior given the current training set. We perform different AL algorithms and select batches with batch size 20. After each batch is added to training set, we can estimate the accuracy improvement of the batch. In each step, perform each AL algorithm 20 times and estimate the mean and std of accuracy improvement. The mean and std of BNNs accuracy are shown in figure 17. We can see in figure that our algorithms consistently select batches that have high accuracy improvement and low variance.
D.7
WITH MULTI-CHAIN CSG-MCMC
cSG-MCMC can improved by sampling with multiple chains (Zhang et al., 2019). In order evaluate different AI. algorithms with this improved parallel cSG-MCMC method, conduct
26

---

Published as a conference paper at ICLR 2023
BALANCE
BALL
1.5
1.0-
0.0
6.00
0.36
0.50
0.76
1.00
1.25
1.90
1.75
2.00
contliciona of vartanioo
Figure 16: Histograms for coefficient of variation.
SaCBBALD
Toasken
SackkBAl BALACC
Variarionn Ratio
Mina STTI
0.075
0.0.0
BALOSB
0003
Hindonly Traltiing
(a) Mean of models' accuracy on test
(b) STD of models' accuracy on test set
Figure 17: We empirically show AL. algorithms' predictive variance.
experiment on CIFAR-10 10 dataset with batch size B 5, 000. We sample posteriors with chains. Each chain trains the model 200 epochs. The cycle number for each chain is 4 and 3 posterior samples are collected each cycle. The result shown in figure 18, Batch- BALANCE achieves better performance than BADGE.
27

---

Published as a conference paper at ICLR 2023
0:96
0.91
ACC
0.90
040
0.88
140
Random
CoreSet
BADGE
PoweHBALD
LANCE
105
200
Batcl-AALNC
6000
8000
10000
12000
14000
16000
18000
20000
22000
number of labeled compless
Figure 18: ACC vs. samples, multi-chain MCM-M CIFAR-10
28


Reviews:
[{"review_id": "xGPg-YVjTew", "reviewer": "Reviewer_CBRc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "summary_of_the_review": "The proposed method is novel and sound. But adding some theoretical underpinnings is prefered.", "strength_and_weaknesses": "Strength\nThe 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.\nThe 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.\n\nWeakness\nThe 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?\nThe partition of the ECs is intuitive and lacks validation. Why is the Hamming distance used as a measurement and what are the alternative measures?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gv5iDEy00FS", "reviewer": "Reviewer_wGy4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strengths:\n- understandable and relevant motivation\n- well and neatly written, consistent presentation of theory and results\n- significant and detailed elaboration of related work, each used claim is supported\n- the quality is presented in several metrics\n- experiments are done in several domains\n\nWeaknesses:\n- Not clear why the particular criterion is used, i.e. the motivation behind the log-likelihood ration is not clear\n- the usage of the particular distance (Hamming) is not explained - multiple distance can be considered\n- 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", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1JbAnGKwuEv", "reviewer": "Reviewer_RVjP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. ", "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.\n\nWeaknesses: 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.\n\nMoreover, 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.\n\nA 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0f4npB5CYW", "reviewer": "Reviewer_xKhG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel active learning (AL) algorithm for deep Bayesian neural networks (BNN).\nTowards 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.\nBy 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.\n.\n", "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.\n\n. . .\n\nThe reviewer confirms that (s)he has reviewed the authors' rebuttal, which has been reflected in the above review comments and the overall evaluation scores\n", "strength_and_weaknesses": "OVERALL COMMENTS\n\nOverall, the paper is well-written in a clear and logical manner.\nThe 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.\nEvaluations 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.\nBatch-BALANCE is shown to work well in both small and large batch regimes, providing effective and scalable means for Bayesian active learning.\n\n\nDETAILED COMMENTS\n\n1. 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.\"\nWhile 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.\nA 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.\nIt 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.\n\n2. Although the overall technical presentation in the paper is good, there are some minor suggestions for improving it further. For example:\n\n- Please define ECED (page 4) before using the term, since it only appears in the appendix\n\n- 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'.\n\n- 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.\n\n- 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.\n\n- Instead of calling I_Deltah_Balance(x,y) as a combinatorial information measure, it would be better to conceptually relate it to mutual information\n\n\n3. The acquisition function of Batch-BALANCE is obtained through sampling using either MC dropout or  Stochastic gradient Markov Chain Monte Carlo (SG-MCMC).\nHowever, there is currently no discussion on any pros/cons of the respective methods when used with Batch-BALANCE.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster