Information Condensing Active Learning
Authors: Siddhartha Jain
Ge Liu
David Gifford
Venue:  (2021)
Keywords: active learning

Abstract: We introduce Information Condensing Active Learning (ICAL), a batch mode model agnostic Active Learning (AL) method targeted at Deep Bayesian Active Learning that focuses on acquiring labels for points which have as much information as possible about the still unacquired points. ICAL uses the Hilbert Schmidt Independence Criterion (HSIC) to measure the strength of the dependency between a candidate batch of points and the unlabeled set. We develop key optimizations that allow us to scale our method to large unlabeled sets. We show significant improvements in terms of model accuracy and negative log likelihood (NLL) on several image datasets compared to state of the art batch mode AL methods for deep learning.

Under review as a conference paper at ICLR 2021
INFORMATION CONDENSING ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce Information Condensing Active Learning (ICAL), a batch mode model agnostic Active Learning (AL) method targeted at Deep Bayesian Active Learning that focuses on acquiring labels for points which have as much informa- tion as possible about the still unacquired points. ICAL uses the Hilbert Schmidt Independence Criterion (HSIC) measure the strength of the dependency between a candidate batch of points and the unlabeled set. We develop key optimizations that allow us scale our method to large unlabeled sets. We show significant improvements in terms of model accuracy and negative log likelihood (NLL) on several image datasets compared state of the art batch mode AL methods for deep learning.
1
Introduction
Machine learning models widely used for vast array of real world problems. They have been applied successfully in a variety of areas including biology (Ching et al. 2018). chemistry (Sanchez Lengeling and Aspuru- Guzik 2018), physies (Guest al. 2018). and materials engineering (Aspuru Guzik and Persson 2018). Key to the success of modern machine learning methods is access to high quality data for training the model. However such data be expensive to collect for many problems. Active learning (Settles) 2009) is a popular methodology to intelligently select the fewest new data points be labeled while not sacrificing model accuracy. The usual active learning setting is pool- active learning where one has access to large unlabeled dataset Du and uses active learning to iteratively select new points from Dy to label. Our goal in this paper is to develop an active learning acquisition function to select points that maximize the eventual test accuracy which is also one of the most popular criteria used to evaluate an active learning acquisition function.
In active learning, an acquisition function is used to select which new points to label. A large number of acquisition functions have been developed over the years, mostly for classification (Settles) 2009). Acquisition functions use model predictions point locations (in input feature learned representation space) to decide which points would be most helpful to label to improve model accuracy. We then query for the labels of those points and add them to the training set. While the past focus for acquisition functions has been the acquisition of one point at a time, each round of label acquisition and retraining of the MI. model, particularly in the case of deep neural networks, expensive. Furthermore in several applications like biology, it can be much faster to do acquisition of a fixed number of points in parallel versus sequentially. There have been several papers, particularly in the past few years, that try to avoid this issue by acquiring points in batch. As our goal is to apply AL in the context of modern ML models and data, we focus this paper on batch-mode AL.
be
Acquisition functions can be broadly thought of as belonging to two categories. The ones from the first category directly focus on minimizing the error rate post-acquisition A natural choice of such an acquisition function might be to acquire labels for points with the highest uncertainty or points closest to the decision boundary (Uncertainty sampling can be directly linked to minimizing error rate in the context of active learning Mussmann and Liang (2088)). In the other category, the goal is to get as close as possible to the true underlying model. Thus here, acquisition functions select points which give the most amount of knowledge regarding model's parameters where knowledge is defined as the statistical dependency between the parameters of the model and the predictions for the selected points. Mutual information (MI) is the usual choice for the dependency, though other choices are possible. For well well-specified model spaces, e.g. in physics, such a strategy can identify the correct model. In machine learning, however, models usually mis-specified, and thus the

---

Under review as a conference paper at ICLR 2021
metric of evaluation even for model-identification acquisition functions is how successful they are reducing test error. Given this reality, we follow the viewpoint of trying to minimize the error rate of the model post-acquisition.
Our strategy is to select points that we expect would provide substantial information about the labels of the rest of the unlabeled set, thus reducing model uncertainty. We propose acquiring batch of points B such that the model's predictions on B have as high a statistical dependency as possible with the model's predictions on the entire unlabeled set Du. Thus we want batch B that condenses the most amount of information about the model's predictions on Dr. We call our method Information Condensing Active Learning (ICAL).
A key desideratum for our acquisition function is to be model agnostic. This is partly because the model distribution can be very heterogencous. For example, ensembles which are often used as model distribution can consist of just decision trees in random forest or different architectures for a neural network. This means we cannot assume any closed form for the model's s predictive distribution, and have to resort to Monte Carlo sampling of the predictions from the model to estimate the dependency between the model's predictions on the query batch and the unlabeled set. MI, however, is known to be hard to approximate using just samples (Song and Ermon 2019). Thus to scale the Independence Criterion (HSIC), one of
method to larger batch sizes, we use the Hilbert-Schhie the most powerful extant statistical dependency measures for high dimensional settings. Another advantage of HSIC is that it is differentiable, which as we will discuss later, can allow applications of the acquisition function to areas where MI would be difficult to make work.
To summarize, we introduce Information Condensing Active Learning (ICAL) which maximizes the amount of information being gained with respect to the model's predictions on the unlabeled set of points. ICAL is a batch mode acquisition function that is model agnostic and can be applied to both classification and regression tasks. We then develop an algorithm that can scale ICAL to large batch sizes when using HSIC as the dependency measure between random variables. As our method only needs samples from the posterior predictive distribution which can be obtained for both regression and classification tasks, it is applicable to both.
2 Related work
A review of work on acquisition functions for active learning prior to the recent focus on deep learning is given by [Settles] (2009). The BALD (Bayesian Active Learning by Disagreement) (Houlsby et al.. 2011) acquisition function chooses query point which has the highest mutual information about the model parameters. This turns out to be the point on which individual models sampled from the model distribution are confident about in their prediction but the overall predictive distribution for that point has high entropy. In other words this is the point on which the models are individually confident but disagree the most.
In Guo and Schuurmans (2088) which builds on Guo and Greiner 2007), ) they formulate the problem as an integer program where they select batch such that the post acquisition model is highly confident on the training set and has low uncertainty on the unlabeled set. While the latter aspect is related to what we do, they need to retrain their model for every candidate batch they search over in the course of trying to find the optimal batch. As the total number of possible batches is exponential in the size of the unlabeled set, this can get too computationally expensive for neural networks limiting the applicability of this approach. Thus as far as we know, Guo and Schuurmans (2008) has only been applied logistic regression. BMDR (Wang and Ye 2015) queries points that are as close to the classifier decision boundary as possible while still being representative of the overall sample distribution. The representativeness is measured using the maximum mean discrepancy (MMD) (Gretton et al.) 2012) of the input features between the query batch and the set of all points, with a lower MMD indicating a more representative query batch. However this approach is limited to classification problems, it is based on decision boundary. BMAL (Hoi et al. 2006) selects batch such that the Fisher information matrices for the total unlabeled set and the selected batch are as close possible. The Fisher information matrix is however quadratic in the number of parameters and thus infeasible to compute for modern deep neural networks. FASS (Filtered Active Subset Selection) (Wei et al. 20155) picks the most uncertain points and then selects subset of those points
2

---

Under review as a conference paper at ICLR 2021
that are as similar as possible to the whole candidate batch which favors points that can represent the diversity of the initial set of most uncertain points.
Recently active learning methods have been extended to the deep learning setting. Gal et al. (2017) adapts BALD (Houlsby et al., 201T) to the deep learning setting by using Monte Carlo Dropout (Gal and Ghahramani 2016) to do inference for their Bayesian Neural Network. They extend BALD to the batch setting for neural networks with BatchBALD (Kirsch et al. 2019). In Pinsler et al. (2019), they adapt the Bayesian Coreset (Campbell and Broderick 2018) approach for active learning, though their approach requires a batch size that changes for every acquisition. As the neural network decision boundary intractable, DeepFool (Ducoffe and Precioso 2018) uses the concept of adversarial examples (Goodfellow et al.] (014) to find points close to the decision boundary. However this approach is again limited classification tasks. FF-Comp (Geiffman and Yaniv 2017). DAL (Gissin and Shalev-Shwartz, 2019), Sener and Savarese (017)) and BADGE (Ash et al. 2019) operate on the learned representation, as that is the only way the methods incorporate feedback from the training labels into the active learning acquisition function, and they are thus not model-agnostic, as they are not extendable to any model distribution where it difficult to have a notion of a common representation representation is a distribution and not a single point. This is also the case with the model distribution in this paper.
in random forests ensembles, etc. where the learned
MC-dropout
There is also extensive prior work on exploiting Gaussian Processes (GPs) for Active Learn- ing (Houlsby al., 2011 Krause al., 2008). However GPs hard to scale especially for modern image datasets.
3 Background
Statistical background The entropy of a distribution is defined as - Pe log(Pz). where Ps is the probability of the x. Mutual information (MI) between two random variables is pla.y)
defined as [[X;; YJ Exex Eye p(z, v) log( p(t)))))))) where p(z, y) the joint probability of x; y. H(Y) - X( = H(X)- (Y)). By posterior predictive distribution yz mean So (rylar, ()) where is the prediction, the input point, the model parameters, and 'D the training data. .M the distribution of models (parametrized by f) we wish to choose from via active learning. As mentioned before, we use MC-dropout for our model distribution by sampling random dropout masks and use the same set of dropout masks across points to generate joint predictions.
Note that [[;
Independence Criterion (HSIC) Suppose have two (possibly multivariate) distributions X, and we want to measure the dependence between them. A well known way to measure is using distance covariance which intuitively, measures the covariance between the distances of pairs of samples from the joint distribution Pxy and the product of marginal distributions P(X), P(Y) (Székely et al. 2007). HSIC can simply be thought of as distance covariance except in kernel space (Sejdinovic et al. 2013b). A (sample) kernel matrix y-X is matrix whose ijth element k<,,, 2;)) where is the kernel function and I2, are the i, jthh samples from X. Further details are in the Appendix.
Acquisition Function Let the batch to acquire be denoted by B with B = |B). Given model distribution M, training data Dirains unlabeled data Dy, input space X, set of labels y and an acquisition function MMr, we decide which batch of points to query next via:
B arg max MM
4 Motivation
As mentioned previously, our goal is to acquire points that will give us as much information as possible about the still-unlabeled points, thereby increasing the confidence of the model's predictions.
3

---

Under review as a conference paper at ICLR 2021
As will demonstrate shortly, there are situations where modern active learning methods do not select the points that optimally decrease the uncertainty of prediction on the unlabeled data. More formally, the examples below show that the choice of E U that optimizes oft-used acquisition functions may not be optimal for decreasing the entropy of predictions (Ere fi H (yar)) over the remaining points post-acquisition. we wish to optimize test-set accuracy, this can be problematic: for well cell-calibrated models, should expect worse average entropy (uncertainty) to roughly corre- spond to an increase in the number of errors. This is similar to cross entropy loss being good proxy for 0-1 loss. Below we illustrate our points with examples and from results on EMNIST.
Example Suppose have an image dataset which is highly imbalanced with 90% cars, 9% planes, and 1% ships. Then a small increase in accuracy for the car category would lead to a much larger reduction in the overall error rate versus large increase in accuracy for the ships category. However, given the dominance of the cars category in the loss, the uncertainty of prediction on the ships category is likely to be much higher. Thus the max-entropy criterion is more likely to choose points from the pool set that turn out to be ships.
Similar to the previous example, here we demonstrate that picking the point with the most amount of information with respect to the model parameters is not optimal for decreasing the prediction uncertainty on the still unlabeled data. The main idea behind this example is that if you have points which form non- trivial fraction of the dataset and have lot of correlation between their predictive distributions, then while any of the points may not give a lot of information about which underlying model is the best one, getting the labels for of the points will greatly reduce the predictive uncertainty for the labels for the other points given the predictive distribution correlation. As these points are non-trivial fraction of the dataset, reducing the predictive uncertainty on them will have big impact on the error rate. The example in the Appendix formalizes this intuition.
Example 2
Posterior entropy predictionitest
Posterior entropy predictioniunlabeled set)
(CAL(ours)
BatchBALD
13
BeyesCoreset
MaxEEn
11
100
150 Acquired dataset size
100
Acquired dataset size
Figure 1: Mean posterior entropy of the predictions after each acquisition on EMNIST.
These observations motivate our formulation of the Information Condensing Active Learning (ICAL) acquisition function that selects the set of points whose acquisition would maximize the information gained about the predictive distribution on the unlabeled set. As posterior prediction entropy should be minimized by maximizing Mutual Information (MI) between predictions for unlabeled points and prediction for selected points, ideally ICAL would use MI or related criteria to select points.
EMNIST results In Figure show the average posterior entropy of the model's predictions for our method compared to BatchBALD, BayesCoreset, and Random acquisition. As can be seen from the figure, ICAL reduces the average posterior entropy much more effectively compared to the other two. Details of this experiment are in Section 6.2.
5 Information Condensing Active Learning (ICAL)
In this section present acquisition function. As before, let Diroin be the training points, Du the unlabeled points, Yı the random variable denoting the prediction for x by the model trained on D Drrains and d the dependency measure being used. Then
4

---

Under review as a conference paper at ICLR 2021
dIcAL(la)..... zB),0)
Σ D'EDu
D(ya', (V I.... Meu
[Dol
that is, we try to find the batch that has highest average dependency with respect to the unlabeled
points' marginal predictive distribution.
Scaling OICAL estimation
As mentioned in the introduction, we MI as the dependency measure but it is tricky to estimate MI using just samples from the distribution, particularly high-dimensional or continuous variables. Furthermore, MI estimators are usually not differentiable. Thus if we wanted apply ICAL to domains where the pool set is continuous and infinite (for example, if we wanted to query gene expression perturbations for cell), we would run into obstacles. This motivates our choice of HSIC as the dependency measure. In addition to being differentiable, H SIC has better empirical sample complexity for measuring dependency as opposed to estimators for MI. Indeed, popular MI estimators have been found to have variance with respect to ground truth MI that increases exponentially with the MI value Song and Ermon (2019). HSIC has also been successfully used the related context of feature selection via dependency maximization in the past Da Veiga (2015), Song et al. (2012), Furthermore, HSC is the Maximum Mean Discrepancy (MMD) between the joint distribution and the production of marginals. MMD is known to be & 2 KL-divergence Ramdas et al. (0015) and thus HSIC & 1 MI. Thus we HSIC as the dependency measure for the rest of the paper.
Naively implementing oICAL (B, HSSC) would require O( Im3 B C)) steps per candidate batch being evaluated where C is the number of classes, m is the number of samples taken from p(yI.B) (O(m²B) estimate IISIC' which we need do |Dyr times).
However, recall that HSIC is a function of solely the kernel matrices k- corresponding to the random variables (Appendix) in this case yo I Du. Now one can define the matrix k* [Pol ExeD, k²
We can then prove the following propositions (proofs are in the Appendix).
Proposition 1
k is a valid kernel matrix.
Proposition 2 ExED, HSTC(K" L.EB)) = HSSTC Dy htt kZEB)
where A = kzt k"......, kan 148,,2 24 E B and HSIC denotes the sample for HSIC. Using this reformulation, only have to compute ks De Le k" once per acquisition round. This
lowers the computation cost to O( |m2 C + m² B. C). Estimating HSTC would still require m increase very rapidly with B (proportional the dimension of the joint distribution). To get around this but still maintain batch diversity, we try two strategies.
For regular ICAL, we average the kernel matrices of points in the candidate batch. We then subsample r points from Dy every time a point is added to the batch and only compare the dependency with those. This effectively introduces noise in the HIC estimation. We find in practice, that this is sufficient to acquire a diverse batch, as evidenced by Figure 3 This seems to be the case even for very large batches, and has the added benefit of further lowering the computational cost for evaluating a candidate batch to O(rm² C + 2 m² C). We use r 200 for all our experiments.
We develop another strategy we call poittioe which computes the marginal increase in dependence result of adding point to the batch. If point is highly correlated with elements of the current batch, the marginal increase would be negligible, making the point much less likely to be selected. The two variants perform very similarly despite ICAL-pointwise' slight advantage in the early acquisitions. ICAL-pointwise however requires much less time for equivalent performance which discuss briefly in Section 5.2 and more fully in the Appendix. For case of presentation, use ICAL in the Results section and defer the full description and evaluation of ICAL-pointwiss to the Appendix.
5

---

Under review as a conference paper at ICLR 2021
VNIST accuracy
MNST
Repeated accurncy
Repested
0.45
BUCCHAALD
SatchDALD
B6LD
1.50
0.50
1.
Random
landor
0.00
0.85
1.0
0.5
BaceesCormeet
KAAlour))
1.00
BayesCoreset
NASS
CAI (oung)
0.55
06
0.75
0.00
04
0.65
022
0.25
300
200
300
300
300
300
50
100
350
200
250
300
50
100
150
200
250
300
Acquired dataset size
Acquired dataset size
Acquired dataseet size
Acquired dataset size
Figure 2: Performance on MNIST and repeated-MNISTT Accuracy and NLL after each acquisition.
As there are an exponential number of candidate batches, an exhaustive search to find the optimal batch is infeasible. For ICAL we use greedy forward selection strategy to build the batch and find that it performs well empirically. As the arg max over all of DD has to be computed every time a new point is being selected for the batch, and we have to perform this operation for each point that is added to the batch, this gives computation cost of O((r2m²+ + [Dy mm3 B++ m² B)-C) C*) O(Du mm² B .)). is possible that global nonlinear optimization of the batch ICAL criterion would work even better than greedy optimization already does with respect state of the art methods. Efficient techniques for doing this optimization are not obvious and beyond the scope of this work. Even if we used gradient based techniques construct the batch, gradient based optimization for nonlinear problems usually only leads to local and not global optima. We note however that greedy forward selection is popular technique that has been successfully used in large variety of contexts (Da Veiga 2015 Blanchet et al.) 22088) Optimizations to scale ICAL even further as well as the full Algorithm are detailed in the Appendix.
6 Results
We demonstrate the effectiveness of ICAL using standard image datasets including MNIST (LeCun et al. 1998), Repeated MNIST (Kirsch et al. 2019). Extended MNIST (EMNIST) (Cohen et al. 2017). fashion-MNIST. and CIFAR- 10 (Krizhevsky et al. 2009). We compare ICAL with three state of the art methods for batched active learning acquisition BatchBALD, FASS, and BayesCoreset. We also compare against BALD and Max Entropy (MaxEnt) which are not explicitly designed for batched selection, as well as against a Random acquisition baseline. Details of the acquisition functions are in the Appendix. ICAL consistently outperforms BatchBALD, FASS, and BayesCoreset on accuracy and negative log likelihood (NLL).
Throughout our experiments, for each dataset we hold out a fixed test set for evaluating model performance after training and fixed validation set for training purposes. We retrain the model from the beginning after each acquisition to avoid correlation of subsequently trained models, and we use early stopping after 3 (6 for ResNet18) consecutive epochs of validation accuracy drop. Following (Gal et al., 2017), we use Neural Networks with MC dropout (Gal and Ghahramani 2016) as variational approximation for Bayesian Neural Networks. We simply use a mixture of rational quadratic kernels for HSIC, which has been used successfully with kernel based statistical dependency measures in the past, with mixture length scales of (0.2, 0.5, 1, 2, 5) as in (Bińkkoski et al., 2018 All models are optimized with the Adam optimizer (Kingma and Ba 2014) using learning rate of 0.001 and betas 999).. The small batch size experiments are repeated 6 times with different seeds and a different initial training set for each run, with balanced label distribution across all classes. The same set of seeds is used for different methods on the same task. 8 different seeds are used for large batch size experiments using CIFAR datasets.
6.1 MNIST and Repeated MNIST
We first examine ICAL's performance MNIST, which is standard image dataset for handwritten digits. We further test out the scenario where duplicated data points exist (repeated MNIST) as proposed in (Kirsch al. 2019). Each data point in MNIST is replicated three times in repeated-

---

Under review as a conference paper at ICLR 2021
MNIST, and isotropic Gaussian noise with std=0.1 is added after normalizing the image. We use a CNN consists of two convolutional layers with 32 and 64 5x5 convolution filters, each followed by MC dropout, max- max-pooling and ReLU. One fully connected layer with 128 hidden units and MC dropout is used after convolutional layers and the output soft-max layer has dimension of 10. All dropout uses probability of 0.5, and the architecture achieved over 99% accuracy on full MNIST. We use a validation set of size 1024 for MNIST and 3072 for repeated-MNISS and a balanced test set of size 10,000 for both datasets. All models are trained for up to 30 epochs for MNIST and up to 40 epochs for repeated- repeated-MNIST. -NNIST. We sample an initial training set of size 20 (2 per class) and conduct 30 acquisitions of batch size 10 on both datasets, and we use 50 MC dropout samples estimate the posterior.
The test accuracy and negative log-likelihood (NIL) are shown Figure 2 ICAL significantly improves the NL.. and outperforms all other baselines on accuracy, with higher margins on the earlier acquisition rounds. The performance is consistent across all runs (the variance is smaller than other baselines), and is robust even in the repeated-MNIST setup, where all the other greedy methods show worsen performance. We check the frequency that replicas of a single sample were included in acquired batch and as shown in Appendix Figure 8] our method (as well as BatchBALD, BayesCoreset and random) acquired no redundant sample whereas FASS and max entropy acquired up to copies of some samples.
ICALlours)
MaxErt
BoyesCoreset
32%
165
Figure 3: Histogram of the labels of all acquired points using different active learning methods on EMNIST (47 classes). ICAL acquires more diverse and balanced batches while all other methods have overlyyunderr-eppreennted classes.
6.2 EMNIST
We then extend the task to a more sophisticated dataset named Extended- which consists of 47 classes of 28x28 images of both digits and letters. We used the balanced EMNIST where each class has 2400 training examples. We use a validation set of 16384 and test set size 18800 (400 per class), and train for up to 40 epochs. We use CNN consisting of three convolutional layers with 32, 64, and 128 3x3 convolution filters, each followed by MC dropout, 2x2 max max- pooling and ReLU, A fully connected layer with 512 hidden units and MC dropout is used after convolutional layers. We use an initial train set of 47 (1 per class) and make 60 acquisitions of batch size 5. 50 MC dropout samples are used estimate the posterior.
The results are in Figure 4 We do substantially better in terms of both accuracy and NLL compared to all other methods. A clue as to why our method outperforms on EMNIST can be found in Figure ICAL is able to acquire more diversed and balanced batches while all other methods have overlyyunder-reppeeentte classes (note that BatchBALD, Random and MaxEnt each totally miss examples from one of classes). This indicates that our method is much more robust in terms of performance even when the number of classes increases, whereas other alternatives degenerate.
6.3 Fashion-MNIST
We also examine ICAL's performance on fashion-MNIST which consists of 10 classes of 28x28 Zalando's article images. We use a validation set of 3072 and test set of size 10000 (1000 per class), and train for up to 40 epochs. The network architecture is the same the one used in MNIST task. We use an initial train set of 20 (2 per class) and make 30 acquisitions of batch size 10. 100 MC dropout samples
used to estimate the posterior. As shown in Figure 4 we again do significantly better in terms of both accuracy and NLL compared to all other methods. Note that almost all baselines were inferior to random baseline except ICAL,, showing the robustness of method.
7

---

Under review as a conference paper at ICLR 2021
0.6
accurncy
BaCOhSALD BALD
2.00
BeschDALD
SALD
Randiom
0.75
2.75
Random
KALoora!
K'hi (ours)
Boyescoreeet
0.70
250
BayesCoreset
0.4
FASS
125
PASS
0.75
0.50
02
0:50
50
300
150
200
250
300
30
100
150
200
250
300
100
200
300
100
200
300
Acquired dataset size
Acquired dataset size
Acquired datasel size
Acquired dataoet size
Figure 4: Performance on EMNIST and fashion ICAL significantly improves the accuracy and NLL.
6.4 CIFAR
Finally we test our method on the CIFAR- 10 and CIFAR-100 datasets Krizhevsky et al. (2009) in large batch size setting. CIFAR-10 consists of 10 classes with 6000 images per class whereas CIFAR-100 has 100 classes with 600 images per class. We use a validation set of size 1024, and balanced test set of size 10,000 for both datasets. For CIFAR-10, 10, we start with an initial training set of 10000 examples (1000 per class) while for CIFAR- 100, start with 20000 examples (200 per class). We do 10 acquisitions on CIFAR-10 10 and 7 acquisitions on CIFAR-100 100 with batch size of 3000, We use a ResNet18 with additional 2 fully connected layers with MC dropouts, and train for up to 60 epochs with learning rate 0.1 (allow early stopping). We run with 8 different seeds. The results are in unable to compare against BatchBALD for either CIFAR dataset it runs
Figure 5 Note that out of memory.
For CIFAR-10, ICAL dominates all other methods for all acquisitions except two when the acquired dataset size is 19000 and when it is 28000. ICAL also has the highest area under curve (auc) for accuracy compared all other methods; with p-value & 0.007 except for BALD and Max Entropy for which we have better auc with p-value 0.24, 0.15 respectively. ICAL also achieves the highest accuracy at the end of all 10 acquisitions. With CIFAR- 100, on all acquisitions ICAL outperforms a majority of the methods. Furthermore, ICAL again finishes with the highest accuracy by significant margin the end of the acquisition rounds and it again have the highest auc compared all other methods. Detailed comparison results are in the Appendix Table 2.
CIFAR-10 accuracy
CIFAR-100 accuracy
0.400
0.80
0.375
0.75
0.350
BayesCoreset
Random
0.325
0.70
FASS
0.300
ICAL(ours)
0.65
MaxFnt
0.275
BALD
0.250
10000
15000 20000 25000 30000
35000
20000
25000
30000
35000
Acquired dataset
Acquired dataset
Figure 5: Performance on CIFAR-IO and CIFAR- 100 with batch size=3000 using seeds
7 Conclusion
We develop a novel batch mode active learning acquisition function ICAL that is model agnostic and applicable to both classification and regression tasks (as it relies on only samples from the posterior predictive distribution). We develop key optimizations that enable us to scale our method to large acquisition batch and unlabeled set sizes. We show that we robustly able outperform state of the art methods for batch mode active learning on a variety of image classification tasks in a deep neural network setting.
8

---

Under review as a conference paper at ICLR 2021
References
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv: 1at:::9000 1906.0367,, 2019.
Alán Aspuru-Guzik and Kristin Persson. Materials acceleration platform: Accelerating advanced energy materials discovery by integrating high-throughput methods and artificial intelligence. 2018.
Mikotaj Binkkwski, Dougal J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying mmd gans. arXiv preprint arXiv: 0108000101411, 2018.
Guillaume Blanchet, Pierre Legendre, and Daniel Boreard. Forward selection of explanatory variables. Ecology, 89(9):2233-2632 2008.
Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. arXiv preprint arXiv: 180201100..0137,,, 2018.
Travers Ching, Daniel Himmelstein, Brett K Beaulieu-Jones, Alexandr A Kalinin, Brian T Do, Gregory P Way, Enrico Ferrero, Paul-Michael Agapow, Michael Zietz, Michael M Hoffman, et al. Opportunities and obstacles for deep learning in biology and medicine. Journal of The Royal Society Interface, 15(141):2017033) 2018.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. Emnist: extension of mnist to handwritten letters. arXiv preprint 1702.05777 2017.
Sebastien Da Veiga. Global sensitivity analysis with dependence measures. Journal of Statistical Computation and Simulation, (5()):1233-1305, 2015.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint arXiv:1802.0984/ 2018.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pages 1050-1059, 2016.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference Machine Learning- -olluee 70, pages 1193-1192. JMLR. org, 2017.
Yonatan Geifman and Ran El-Yaniv. Deep active learning over the long tail. arXiv preprint arXiv:1711.00941, 2017.
Daniel Gissin and Shai Shalev-Shware Discriminative active learning. arXiv preprint arXiv:1907.06347, 2019.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 142iv:1412.6577 2014.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A
kernel two-sample test. Journal of Machine Learning Research, 13(Maa):7233-73, 2012.
Dan Guest, Kyle Cranmer, and Daniel Whiteson. Deep learning and its application to Ihe physics. Annual Review of Nuclear and Particle Science, 18:1611181, 2018.
Yuhong Guo and Russell Greiner. Optimistic active-learinng using mutual information. In IJCAI, volume 7, pages
2007.
Yuhong Guo and Dale Schuurmans. neural information processing systems, pages 593-600, 2008
Discriminative batch mode active learning. In Advances in
Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Batch mode active learning and its application to medical image classification. Proceedings of the 23rd international conference Machine learning, pages 417-424, ACM, 2006.

---

Under review as a conference paper at ICLR 2021
Neil Houlsby, Ferene Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv: 2011.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6985) 42800, 2014.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Advances in Neural Information Processing Systems, 2019.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies, Journal of Machine Learning Research, 9(Feb):235-28) 284, 2008.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE,
1998.
Stephen Mussmann and Perey Liang. On the relationship between data efficiency and error for uncertainty sampling. arXiv preprint arXiv:/806.006233, 2018.
Hanchuan Peng, Fuhui Long, and Chris Ding. Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy. IEEE Transactions on pattern analysis and machine intelligence. 27(8): 1238, 2005.
Niklas Pfister, Peter Bühlmann, Bernhard Schölkopf, and Jonas Peters. Kernel-based tests for joint independence. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1): 5-31, 2018.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobato. Bayesian batch active learning as sparse subset approximation. In Advances in Neural Information Processing Systems, pages 6356-6367, 2019.
Aaditya Ramdas, Sashank Jakkam Reddi, Barnabás Póczos, Aarti Singh, and Larry Wasserman. On the decreasing power of kernel and distance based nonparametric hypothesis tests in high dimensions. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Benjamin Sanchez-Lengeling and Alán Aspuru-Guzik. Inverse molecular design using machine learning: Generative models for matter engineering. Science, 36 3616600))360-365, 2018.
Dino Sejdinovic, Arthur Gretton, and Wicher Bergsma. A kernel test for three-variable interactions. In Advances Neural Information Processing Systems, pages 1124 1132, 2013a.
Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and rkhs-based statistics in hypothesis testing. The Annals of Statistics, pages 2263-2291, 2013b.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint 170800047) 2017.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Maddisnn Department of Computer Sciences, 2009.
Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual information estimators. arXiv preprint 120.0229/. 2019.
Le Song. Alex Smola, Arthur Gretton, Justin Bedo, and Karsten Borgwardt. Feature selection via dependence maximization. Journal of Machine Learning Research, 134M44):1933-1434, 2012.
Gábbor Szěkely, Maria L Rizzo, Nail K Bakirov, et al. Mcasuring and testing dependence by correlation of distances. The annals of statistics, (5(6))2769-2794) 2007.
10

---

Under review as a conference paper at ICLR 2021
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):17, 2015.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963, 2015.

---

Under review as a conference paper at ICLR 2021
Appendix
Motivating example 2
Suppose we have a model distribution with 10 possible models wi,... .,, wio with equal prior probabil- ity of being the true model (p(w;) 0.1 for Vi). Let the datapoints be ........... 2t with their labels .......
taking 4 possible values. We define pf p(y = j| wx) as the probability of the jth class for the ith datapoint given by the kth model. Let
pi = 1;j = k
pia 1:4 <
p = 1, 1,p2 =,
W1
W22
W33
Wb
W6
Ws
Wy
W/0
3
4
22
1
1
1
2
Table 1:
Labels that the different points x; take with probability under different models. The columns are the different models wk, and the rows are the different points.
Given that have other information about the models, we update the posterior probabilities for the models as follows - a model W/ outputs label for a point x but after acquisition, the label for is not I, then we know that eliminated). Otherwise we have no way of distinguishing between the remaining models so they all have equal posterior probability. Then for x1 the mutual information
the correct model and thus its posterior probability 0 (so is
L w| Dirain]
H [1 ppl (erana))))))))
[y) (21 w] = 0.94
For .2... T[22-1, w. Dtrain] 0.325. However selecting 2ı would decrease the expected posterior entropy H [ 22.. 21, B1. Derain] from 0.325 to only 0.287. Acquiring any of 22.... instead of Fj, however, would decrease that entropy to O, which would cause a much larger decrease in the expected posterior entropy averaged over I.... if L is large enough. The detailed calculations are the later subsection.
While T may not contribute much to the entropy of the joint predictive distribution or to the MI with respect to the model parameters compared to I1, collectively they will be weighted L - 1 times more than 21 when looking at the accuracy. We should thus expect well-calibrated model have a higher uncertainty, and thus make a lot more errors on F2...., if æ1 acquired versus if any of T acquired. For instance, in the above example, L increases, the expected error rate would approach x 0.7 x (1/7 x 6/7) x 2 = 0.17 (0.7 as 0.3 of the times the value of æ would also fix what the true model is reducing error rate on all 0) if 21 is acquired as the errors for 22... correlated, whereas the rate would approach 0 were any of #2... to be acquired.
Derivation for Example
For 31, the mutual information between the predicted label y1 and model parameters is:
I[y w/ w|,r, Dirain]
E Be(w)Derana)) [H [x11,,,,0))
H
p(ul (wpp://
Σ
1
log( 7
= -3 (3
x log(
))
10
10
10
10
12

---

Under review as a conference paper at ICLR 2021
1 x (-(1 log(1) 0 x log(0)))
10 x
10
0.940
For 22... Io
1 L. L.L. 22... Drrain]
--(10 10
x log(
+
x log
10
10
10
10 x 10
(- (1 x log(1) + 0 x log(
0.325
After acquiring T1, assuming the true label for Iı is 1, then we update the posterior over the model
parameter such that o'(wi)ly= 1 and )l(w)))m== for < & 10. Then the expected averaged posterior entropy for 2 is:
H Hlssa:llls
L
1
H Σ
10
(x) (wx) m
L
i-2
k-1
1
x (L
1) (- log(1) + 0 log(0)))
L-1
0
Similarly, could compute the case where the true label for is 2-4:
H U11aa:lln22
M[ 12. 11
L
6 L (L x (- log( ?) + = (og())))
0.41
The expectation of the averaged posterior entropy with respect to predicted label for y1 (since don't 'on't know the true label) is:
I1 [1 w2. L, I1, 21 Derain]
1
Σ
En p(pn Derasn))
1=2
1
7
x 0+
x
0
0
+
x
0.41
10
10
10
10
0.287
Baseline acquisition function details
Max entropy selects the points that maximize the predictive entropy
M) H(yl., Dirain)
Σ p(u c/a, Derain) log(p(y c22, Dirain))
13

---

Under review as a conference paper at ICLR 2021
BatchBALD BatchBALD (Kirsch et al. 2019) tries to find batch of points that has the highest mutual information with respect to the model parameters. BALD is the non non-batched version of BatchBALD. Formally
CBac)BALD((I..... .IB.,(w))
Hyy Bw(w (vi.... y
Filtered active submodular selection (FASS) FASS (Wei et al. 2015) samples the 3 B most uncertain points B' and then subselect B points that representative of B' possible. For the measure of uncertainty, FASS uses entropy Hy|æ Drrain). To measure the representativeness of B B", FASS tries choose B maximize the following function
f(B) Σ Σ
max w(t,s)
YEY VVV sEBnVy
Here V S B' is the set of points in B' with predicted label, and w(i, d- similarity function between points indexed by i, where Iz. 2g E X and d is the maximum distance between two points. The idea here is that if point in B already exists that is close to some point r' E B', then (B3) will favor adding points to the batch that are close points other than x', thus increasing the batch diversity. Note that FASS is equivalent to Max Entropy if
1|=
x. 2 is the
Bayesian Coresets In Pinsler al. (2019). they try to build a batch such that the log posterior after acquiring that batch best approximates the complete data log posterior (i.e. the log posterior after acquiring the entire pool set). Their approach closely follows the general Bayesian Coreset (Campbell) and Broderick] (018)) approach which constructs a weighted subset of data that approximates the full dataset. Crucially (Pinsler et al., 2019) assume that the posterior predictive distribution Y, of a point p is independent of that of the corresponding distribution Y," of another point y' an assumption we do not make. We show in the next section why avoiding such an assumption lets us more effectively minimize the error with respect to the test distribution versus just optimizing for maxmizing information gain for the model posterior. As (Pinsler et al. 2019) require a variable batch size whereas all other methods (including ours) use a fixed batch size, for fairness of comparison, if the batch for this approach is smaller than the batch size being used, we fill the rest of the batch with random points. In practice, we only observe this being necessary for CIFAR.
Random The points are selected uniformly at random from the unlabeled pool. Thus a(x.M) is the uniform distribution.
Further statistical background
divergence A between two distributions is a measure of the discrepancy or difference between two distributions P, Q. A key property of a divergence is that it is 0 if and only if P, Q are the same distribution. In this paper, we will be using the KI. divergence and the MMD, which are respectively defined as
DKL(PIIQ) = Σ P(x) log( ((x)
P(x)
MMD = EX X') + K(YYY' 2K(XY)
where k is kernel in the Reproducing Kernel Hilbert Space (RKHS) H. and μ4 is the mean embedding of the distribution into H. as per the kernel k. We can then use the notion of divergence to define the dependency d between set of random variables X as follows
d o(X1.)) A(Pisn P.P
14

---

Under review as a conference paper at ICLR 2021
where Pi:m is the joint distribution of X1.s. P. the marginal of X, with &P, being the product of marginals. For D the dependency is exactly MI as defined above. For MMD the dependency is the Hilbert-Schmidt Independence Criterion (HSIC).
Hilbert-Schmide Independence Criterion (HSIC)
Formally, if X, Y are drawn from the joint distribution Pxy, then their HSTC is defined as
HSIC(Pxy,k, k, = Ex and [k(r, x' (M,, v)) + Ex [k(2, x' [ [M.. v/) 2F, [gy [k(x, E. [k(y. (.y.))
where (x, v) and (x', y/) are independent pairs drawn from Pxy. Note that HSIC((xx)) 0 if and only Pxy = Px Py, that is, if X, Y are independent, for chracteristic kernels and l.
For the case where HSTC statistic (Sejdinovic et al. 2013a Pfister et al. 2018). The computational complexity of HSIC bounded by the time taken compute the kernel matrix which O(m²d) where the number of samples and the number of random variables. We use HSIC to denote the empirical estimator of the HSTC statistic.
measuring the joint dependence between d variables,
the
Proof of Proposition
k is positive semidefinite (psd) and symmetric as the sum of psd symmetric matrices is also psd symmetric.
Proof of Proposition
We show here that
dHSic ......,,kT) AHSIC k²,....,a)
dHSTC + 12, ..))
but the extension to the arbitrary sums is straightforward. Here dHSIC is the estimator for dHSIC which is the d-variable version of HSIC. It is defined as
dHSIC n Σ h
x(,
Σ
Σ
(x)
Σ rdd 1-1
n2d
nd+1
where 1ú is the kemel of the jth random variable and X² is the ith observation for the jth random variable. The estimator SHSIC is defined as (Sejdinovic et al. 2013a
dHSTC n
Σ
12 (at
2
1 (x)
2
ITd
Σ
(1
W
n 2d
nd
As dHSIC reduces to HSIC when d = 2, the proof for HSIC also follows. Using the definition of dHSTC above,
15

---

Under review as a conference paper at ICLR 2021
dHSIC
,k, K....,,
k*) + dHSIC 12 ,.....,(---
1
2
d
W (cl,. (..))
j=3
(2t 2/
II
k (1r) 2nyy)
12
j-3 b=1
2
nd+1
j-3a-1b=1
n
d
h2
(o
1-3
nd
6=1
3-3
2
nd+1
=
J-3
1 n
n
a=1b-1
j=3
k
2d
1-36-
n
2d
a-1
2
j-30=1b-1
2
nd+1
a=1b-1
j=3a=1b-1
1 n2
(z) [[
n
Σ
R (ot
28
d
13
2 ))
Σ
ka (a)
j-3b-1
2
ΣΣ
(3: (ot,
nd+1
a=1b=1
d ΙΣΣΣ
+ +
x2 (4)
j=
= dHSSC 122 13 , Rd))
16

---

Under review as a conference paper at ICLR 2021
7.1 Further scaling to large batch sizes
To scale to large batch sizes, instead of adding points to the batch to be acquired one at time, we can add points in minibatches of size L. While this comes at the cost of possible diversity in the batch, we find that the tradeoff is acceptable for the datasets we experimented with. This gives a final
computation cost of O (Dulm B-C) where runtime for BatchBALD is O(Dul- -B- -m m') of V1m--1. For all experiments with ICAL, we were able to use L = 1 without any scaling difficulties. For ICAL-pointwise, we used L I5 only for CIFAR- 10 and CIFAR-100 As alluded to previously, ICAL.-pointwiee can accommodate much larger I. compared to ICAL before its performance degrades, allowing for much greater scaling. We evaluate this aspect of -Ciit-poittwise in the Appendix.
the number of classes. By contrast the corresponding
where m' is the number of sampled configurations
The final algorithm is given in Algorithm 1
7.2 Algorithm
Algorithm Information Condensing Active Learning (ICAL) (M, T, Derain, Du. B, K, L)
Train M on Dtrain
repeat
B
=
0
while
[B] B do
yu = =the predictive distribution for x E Dy according to M Set of r randomly selected points from Du
x argmax, OB u {x), HSTC) with the optimizations as specified in Section 5.1
and 5.2
B B Bub {a')
end while D Dtrain Dirain U B Retrain M on Derain until T iterations reached
Return M
ICAL-pointwise
To evaluate the marginal dependency increase if a candidate point x is added to batch B, we sample
set R from the pool set Dú and compute the pairwise dHH.SC of both B and B B ou (x) with respect to each point in R. Let the resulting vectors (each of length [R] with the dHSIC scores be dg and dgr. Then the marginal dependency increase statistic M, for point p is M,
[R| Σ, max g 0j)), 1) where i is the ith element of the vector. When then modify the aICaL as follows a (B [=]) aICAL (B u (a)) (M₃ 1) and use the point with the highest value of a'CAL as the point to acquire. Note that as we want to get as accurate an estimate of M,, as possible, we ideally want to choose as large set as possible. In general, we also want to choose | to be greater than the number of classes. This makes ICAL-pointwise more memory intensive compared to ICAL. We also tried another criterion for batch selection based on the minimal--edundaaey-maaai relevance Peng et al. (2005) but that had significantly worse performance compared to ICAL and ICAL-pointwise.
In Figure 6 we analyze the performance of ICAL versus ICAL-pointwise when their parameters are set such that computational cost is about the same. As can be seen they are broadly similar with ICAL-pointwise having slight advantage in earlier acquisitions and ICAL being slightly better in later ones.
We also analyze the relative performance the mini-batch size L changes in Figure 7 In the Figure, iter = & is the number iterations taken to build the entire acquisition batch (note that the actual acquisition happens after the entire batch has been built). ICAL-pointwise requires computation
17

---

IAL--ooinwwise(ours) Under review as a conference paper at ICLR 2021
fashion MNIST accuracy
EMNIST accuracy
0.55
0.75
0.50
0.45
0.65
0.40
0.35
0.55
0.30
(CAL-pointwisseours)
ICAL(ours)
0.25
ICAL(ours)
100
200
300
50
100
150
200
250
300
Acquired dataset size
Acquired dataset size
MNIST accuracy
CIFAR- accuracy
0.95
0.80
0.85
0.75
0.80
0.70
0.75
0.70
ICAL-pointwise(orrs)
0.65
ICAL-pointwise(urr) ICAL(ours)
0.65
ICAL(ours)
100
200
300
10000
15000 20000 25000 30000 35000 Acquired dataset size
Acquired dataset size
Figure 6: IIS...aAtiO and CIFARIO) with parameters set to equivalent computation cost
Relative performance of ICAL ICAL-pointwise on smaller datasets (EM-
time than ICAL in small setup, however time is the major constraint, ICAL--oinntwse is to be preferred its performance degrades more slowly L,, the size of the minibatch, increases. As the performance usually peaks at = 1, if one is trying to get the best performance or if memory is constraint, then ICAL be preferred.
CIFAR-100 accuracy
ICAL(iter=1)
0.36
(CAL(iter=15)
(CAL(iter=100)
0.34
(CAL(iter=500)
ICAL-pointwise(tter=1]]
0.32
(CAL:pointiise((tee=100)
0.30
0.28
0.26
20000
22000 24000 26000 28000 30000 32000 Acquired dataset size
Figure 7: Relative performance of ICAL and ICAL-pointwise CIFAR 100 with different mini-batch size iter the number of iterations taken build the entire acquisition batch of size B (note that the actual acquisition happens after the entire batch has been built)
18

---

Under review as a conference paper at ICLR 2021
Diversity of acquired samples in repeated-MNIST
To check if ICAL's acquisition batches are diversed enough, we plot the number of times different number of copies of same sample has been acquired by each method. As shown in figure g our method (as well as BatchBALD, BayesCoreset and Random) successfully avoided acquiring redundant copies of the same sample, whereas FASS and Max Entropy acquired up to copies the same replica in most acquisitions. This proves that the batched active learning strategies are better in diversity.
BULL MEALD
Pursker
1ASS
Motti
trpostrrost
19th CESi3 rrplii
Fun sapa elrssii
FATT coptcs ofrssiia
PaI of
ran cables ofrspii
Figure 8: Frequencies where different numbers copies (1-3) same sample has been acquired by each method.
Further CIFAR-10 and CIFAR-100 results
CIFAR-10
CIFAR-100
ICAL outperformance
AUC of
ICAL outperformance
AUC of accuracy curve
p-value
accuracy
p-value
Random BALD
6.0e 05
0.742 + 0.004
0.444
0.338 t 0.007
0.248
0.751 + 0.004
0.124
0.335 + 0.003
FASS
8.7e
0.742 + 0.003
0,053
0.333 0.005
BayesCoresct
0.007
0.744 + 0.003
0.003
0.327 0.007
MaxEnt
0.158
0.751 + 0.003
8.5e - 05
0.321 + 0.007
ICAL (ours)
N/A
0.753 i 0.003
N/A
0.338 i 0.005
Table 2:
Area under curve of the accuracy curve for the different methods CIFAR- and p-values of the ICAL out-performance significance when compared to each of the methods. Highest AUC values of each task are highlighted in bold.
Further CIFAR results are Table 2 For CIFAR-100, Random has a high p-value but that is mainly because it performs bit better in the beginning vs. all other methods but its performance quickly degrades and it is far below ICAL in the final iteration.
Runtime and memory considerations
BatchBALD runs out of memory on CIFAR-I0 10 and CIFAR- 100 and thus we are unable compare against it for those two datasets. For the ANIST-varian datasets, ICAL takes about a minute for building the batch acquire (batch sizes of and 10). For CIFAR-10 (batch size 3000), with L the runtime is about 20 minutes but it scales linearly with 1/L (Figure 10). Thus it is only 5 minutes
30 úier = 100) which already sufficient to give comparable performance to L (Figure 9p. For CIFAR- 100 (batch size 3000), the performance does degrade with high L but holds up a lot better in terms of performance with high L (Figure 7) and thus if time is strong consideration, that variant should be used instead.
mentioned previously, ICAL-pointee
19

---

7.2 Algorithm
20
CIFAR-10 accuracy
0.80
0.75
0.70
(CAL(iter=15)
(CAL(i)er110))
0.65
ICAL(iter=500)
ICAL(iter=3000)
10000 15000 20000 25000 30000 35000
Acquired dataset size
Figure 9: CIFARIO performance with different L. iter & is the number of iterations taken build the entire acquisition batch of size (note that the actual acquisition happens after the entire batch has been built)
Runtime vs minibatch size
1400
1200
Nuntime(seconde
1000
800
600
400
0
500
1000
1500
2000
2500
3000
iter(B/L)
Figure 10: Runtime of ICAL on CIFARIO with different minibatch size L.


Reviews:
[{"review_id": "rdhq-GK1bCO", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a model agnostic active learning technique that maximizes the dependency between a batch and the rest of the unlabeled pool. The dependence is measured via the Hilbert Schmidt Independence Criterion and this paper introduces some approximations/optimizations to speed up the method.\n\nIn terms of novelty, this paper introduces another acquisition function, which to the best of my knowledge is technically novel. However, the reasoning or intuition for the algorithm does not seem very novel. For instance, expected error reduction (EER) is motivated by a similar intuition.\n\nThe significance of this paper rests on its empirical evaluation as there isn't any justification for the heuristic algorithm beyond a conceptual motivation (which isn't unusual). The empirical results are relatively strong, comparing to a variety of recent algorithms an outperforming the others by a small margin (and a larger margin on a couple of datasets).\n\nIt would have been nice to see the model agnosticity used by running experiments with different models beyond CNNs. In fact, if some other methods (which apply to CNNs) are discounted because they are not model agnostic, the experiments should really include these other methods or include more than just CNNs. It would also have been nice to see the learning curves in the higher accuracy range, which may be more practical: for instance, in addition to the current plots, also having plots with larger batches that go up to budgets of 1000 or more.\n\nAFTER READING AUTHOR RESPONSE-----------------------------------------------------------------------------------------\n\nThanks for the response.\n\nIdeally, you would be able to show results for ensembles of decision trees or some model that is very different from neural networks.", "extra_scores": {}, "extra_text": {}}, {"review_id": "mfpO2LaKwh", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a new acquisition function for (batch) active learning that uses a variant of the Hilbert Schmidt Independence Criterion to acquire diverse batches that are informative for the remainder of the unlabeled set. The new acquisition function leads to better calibration, as evidenced by achieving lower NLL (for similar accuracy), as well as better accuracy on EMNIST and FashionMNIST than current baselines.\n\nOverall, I’m scoring the paper with a weak reject. While the paper provides good results on EMNIST and FashionMNIST, it does not seem to scale to CIFAR-10 that well. More importantly, the reviewer had trouble understanding the description of the approach in the paper. The novel idea of using HSIC instead of estimating mutual information terms, which scale badly in batch size, is very interesting and needs to be explored. Sadly, for this reviewer at least, the exposition in the paper is very confusing and hard to follow to the point that this reviewer cannot recommend acceptance in its current form.\n\n### Strengths\n\nThe motivation of the paper is strong: it points out that current methods neglect to look at the effect of sample selection on the unlabelled set and focus instead on informativeness for the current model. This prevents current acquisition functions from taking the distribution of the unlabelled set into account. Section 4 provides two convincing examples for this. The simpler one being a strong class imbalance.\n\nThe paper proposes to estimate a d-variable Hilbert Schmidt Independence Criterion (dHSIC from Pfister 2018) instead of a mutual information term that includes a d-variable joint distribution (like in BatchBALD by Kirsch 2019). Computation of joint entropies does not scale well, and thus using dHSIC seems like a good alternative to capture dependencies and which also scales better.\n\nThe paper provides strong empirical evidence that its approach works much better on EMNIST and FashionMNIST. It provides performance comparable or slightly better to BatchBALD on MNIST and RepeatedMNIST, and it also shows that overall, it seems to pick from different classes more uniformly.\n\n### Concerns\n\n1. This reviewer has had difficulties understanding the method described in the paper as well as its practical implementation. HSIC and dHSIC are not properly introduced in the main paper, whereas mutual information, which is not used, is defined. dHSIC is not even explicitly defined in the appendix. Moreover, the step from having a (MC-Dropout-based) BNN with sampled output probabilities for each pool sample to computing kernels for different variables is not clear. Is consistent MC dropout used? How are the kernels computed?\n2. The paper mentions that the pool set is subsampled for computing the pool kernel matrix (acc to Proposition 1) and this noise helps to acquire diverse batches. From the reviewer’s experience, methods that benefit from noise usually perform worse for imbalanced datasets. Could an ablation be run to show the trade-off? Especially given the examples in the motivation in Section 4, another experiment with imbalanced classes would be helpful to show that the proposed approach helps with the issues detailed in its motivation.\n3. This reviewer is also confused about the runtime complexity of the proposed algorithm. In the appendix, $dHSIC(x_1, \\ldots, x_d)$ has runtime complexity $O(n^2 d)$, where $n$ is the number of samples (the reviewer is guessing this) and $d$ is the number of variables. The number of classes seems to be missing. It has to be linear in the classes and number of MC samples at least as the model outputs need to be used at some point. BatchBALD’s runtime complexity is also stated incorrectly, see Kirsch 2019. \n4. In general, the paper is not clearly written, with a notation that changes between the main paper and appendix and variables whose meaning is not explained in the text: for example, the proof of Proposition 2, or the definition of HSIC in the appendix, which does not explain from which distributions the variables are sampled specifically.\n\nThis reviewer was not well-acquainted with kernel methods and RHKS.\n\n---\nUPDATE: After reading the replies, I have updated my score from 5 to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kHQ5Y8tPiTz", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:** This paper proposes a way to do batch mode model agnostic active learning. In this task, the agent has to query a batch of data points from a set of unlabeled examples for which it will get labels. The paper puts an additional requirement that the algorithm is model-agnostic. The key idea here is to sample a batch of points that provide the most \"information\" about the remaining unlabeled examples.  Authors argue that this will result in higher performance on the unlabeled examples. The proposed approach called ICAL (Information Condensing Active Learning) uses Hilbert-Schmidt Independence Criterion (HSIC) to measure dependence between a chosen batch and the unlabeled examples. The goal is to pick a batch with a maximum value of HSIC which should intuitively give us a batch which is representative of the unlabeled set. HSIC can be easily estimated unlike other dependence measures such as mutual information. Given a batch size $|B|$, a dataset of unlabeled examples $D_u$  and $m$ samples to estimate HSIC, the ICAL algorithm computes a batch for label acquisition in $O(|D_U|m^2|B|)$ steps, where a greedy strategy is used to search over batch.  Results are presented over MNIST, variants of MNIST and CIFA and show improvements over five previous active learning approaches and a random acquisition baseline. \n\n**Strength:**\n1. ICAL makes a useful contribution to the active learning literature which has wide range use. Particularly, experiments are presented on realistic domains, with neural networks, and show gains over a few different baselines.\n2. ICAL is model-agnostic which means it can be applied to decision trees, neural networks, complex ensembles, etc. \n3. Experiments show that ICAL acquires a more diverse batch for acquisition.\n\n**Weakness:**\n1. For HSIC, one has to decide the kernel which may be difficult for some domains.\n2. No comparison with BADGE (Ash et al. 2019) is provided. \n3. Time complexity of $O(|D_U|m^2|B|)$ seems expensive particularly if $m > 1000$. What is the value of $m$ that one should expect in practice?\n\n**Questions:**\n1. For Repeated MNIST task, how do the different baselines compare in terms of the number of times they pick a datapoint and its replica for label acquisition?\n2. Is the set $X$ and $Y$ assumed to be countable in Section 3 since summations are used everywhere. \n\n**Writing:**\nThere are issues with writing in several places. Some are enumerated below:\n1. Grammar error on the second line of the third paragraph of intro in \"directly focus on 'minimize' the error rate\". It should be minimizing.\n2. Unexpected full stop after \"model's parameters\" in the third paragraph of the intro. \n3. No $d \\theta$ in Section 3 when taking integral in the first paragraph.\n4. What is $B_{D_u}$ in the definition of $B^\\star$ in the third paragraph of Section 3. Also, how is the training set used in this definition?", "extra_scores": {}, "extra_text": {}}, {"review_id": "GAg7mIUaB7S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a novel acquisition function for active learning based on the (sample) Hilbert Schmidt Independence Criterion (HSIC) statistic. The authors use several standard approximations (using MC dropout to sample from the posterior, building the pool batches greedily, subsampling other unlabelled points when estimating the value of a candidate batch) as well as useful properties of the HSIC statistic, to make the proposed method computationally tractable. \n\nPros:\n\nThe proposed method is fairly straightforward and uses relatively well studied tools. \n\nSection 4 provides a valuable analysis of existing active learning methods which is of independent interest, and shows how the new method is not as susceptible to the flaws of other methods. This insight can be quite valuable to further develop new active learning algorithms.\n\nFigure 3 suggests a reason for why the proposed method outperforms existing ones on some data sets (although it would be interesting to get statistics which back up the claim that individual batches are more balanced as well as the overall sampling process).\n\nExperiments compare the new method to a reasonable set of SOTA active learning methods. \n\nCons:\n\nThe new method is competitive on all experiments, but can only be claimed to outperform existing methods on EMNIST and fashion-MNIST. \n\nWould be interesting to see things like robustness to some of the approximation choices (number of MC dropout resamples for example). \n\nThe ideas and observations here are a contribution to the active learning community, and experiments still show this method to be competitive with existing methods. Therefore I currently lean towards accepting. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a model-agnostic heuristic for batch active learning.  There was an agreement among the reviewers that it's a good approach to try and report about, but the paper was ultimately rejected after calibration.

There were two concerns raised in the reviews, and the authors are encouraged to address them in a revision:

1) Several reviewers commented on issues with readability, affecting the paper's reproducibility (see reviews for details).  The reviewers would have also liked to see more evidence of empirical robustness to various choices made.

2) For the paper to be compelling, it should either compare with gradient-based approaches like BADGE (Ash et al. 2019) or include experiments with a representation where BADGE can't be applied (to support the model-agnostic distinction the authors are making).  The core motivation is the same, with both approaches trying to explicitly incorporate predictive uncertainty and sample diversity, and it would be interesting to see a comparison.
Decision: Reject