Improving greedy core-set configurations for active learning with uncertainty-scaled distances
Authors: Yuchen Li
Frank Rudzicz
Venue: ICLR 2022 Submitted (2022)
Keywords: Active learning

Abstract: We scale perceived distances of the core-set algorithm by a factor of uncertainty and search for low-confidence configurations, finding significant improvements in sample efficiency across CIFAR10/100 and SVHN image classification, especially in larger acquisition sizes. We show the necessity of our modifications and explain how the improvement is due to a probabilistic quadratic speed-up in the convergence of core-set loss, under assumptions about the relationship of model uncertainty and misclassification.

Under review as a conference paper at ICLR 2022
IMPROVING GREEDY CORE-SET CONFIGURATIONS FOR ACTIVE LEARNING WITH UNCERTAINTY-SCALED) DISTANCES
Anonymous authors Paper under double-blind review
ABSTRACT
We scale perceived distances of the core-set algorithm by factor of uncertainty and search for low-confidence configurations, finding significant improvements in sample efficiency across CIFAR 10/100 and SVHN image classification, espe- cially in larger acquisition sizes. We show the necessity of our modifications and explain how the improvement is due to a probabilistic quadratic speed-up the convergence of core-set loss, under assumptions about the relationship of model uncertainty and misclassification.
INTRODUCTION
Active learning aims to identify the most informative data to label and include in supervised train- ing. Often, these algorithms focus on reducing model variance, representing distributional densities, maximizing expected model change, minimizing expected generalization error (Kirsch et al. 2019 [eener & Savarese 2018 Settles 2009 Shen et al.] 2018 [inha et al., 2019). A unifying theme is efficient data collection, which is measured by the rate in improvement more data are la- belled. This is important when we want to identify only the most promising samples to be labelled.
but also for tasks that require slow or expensive labelling (Ducoffe & Precioso 2018 Ma et al.,
2020 Settles 2009).
We describe active learning with the same notation as Sener & Savarese (018). Suppose wish to classify elements of a compact space X' into labels y {I,.... C³. We collect n data points Pxxy. but only have access the labels of m of these, denoted by their indices (z, Mi Je
8 = () E [e]] We use the learning algorithm A, on the labelled set 8 to return the optimized parameters the classifier, and measure performance with the loss function ((:, : A.) : X'xy + IR The goal of active learning is to produce a set of indices whose cardinality is limited by the la- belling budget b, such that expected loss is minimized upon labelling and training on these elements: arg min., |Sb ExyxPPxx [1z, y: Asuue))) (Sener & Savarese 2018). In practice,
the test set {zt, 34 Weee Pxxx approximate the expectation. The typical way to assess the data- efficiency of any particular active learning algorithm is to compare its trend of test performance across increasing labels compared to random and other sampling baselines (Kirsch al.) 2019
Sener & Savarese 2018: Settles 2009: Shen et al. 2018 Sinha et al. 2019 Ducoffe & Precioso, 2018
Ma et al. 2020).
Sener & Savarese (2018) suggested that we can improve data-efficiency by minimizing the core-set radius, defined as the maximum distance of any unlabelled point from its nearest labelled point: 5 max;e(n) minjes Iz). Given the generalization error Sn of all labelled and unlabelled data, and zero training error, expected error converges linearly with respect to d (Sener & Savarese
2018):
Σ I(,,, S S. + +0 (VA *Ejm]
E Pxexy
[1 yi Ax) S Sn.
(1)
n2
Sener & Savarese (2018) argued that generalization error for neural networks has well-defined bounds, optimizing the rest of Equation I referred to core-set loss, is critical for active leam- ing. Indeed, their algorithms for optimizing core-sets consistently improved over their basclines (Sener & Savarese 2018)

---

Under review as a conference paper at ICLR 2022
Uncertainty- based sampling is particularly valuable for identifying support vectors, leading to finer classification boundaries (Kirsch et al. [2019] Settles 2009). However, these methods may catas-
trophically concentrate their labelling budget difficult, noisy regions between classes, shown in Figure
Gaussian clustering dataset
Random
Least confidence
Greedy core-set
Test result
Random
confidence
Greedy care
5
5-
Test acCEOOY (9)
80
0
0-
-10
-10
-10 0 -10
100 200
300
Labels
Figure 1: A toy demonstration of catastrophic concentration from least confidence acquisition functions. Columns 2, 3 and show the labelling requests made by three different active learning strategies over 5 it- erations on the dataset shown column Each strategy has request budget of labels per iteration. Test results show the mean and I standard deviation 3 random initializations. Whereas least confidence wastes its labelling budget on difficult regions between clusters and performs worse than random acquisition, the greedy core-set strategy covers the input space effectively and achieves superior label efficiency.
We present two-part solution for incorporating uncertainty into core-sets:
1. Scale distances between points by doubt (1) Settles 2009 puting core-set radii:
Shen al. 2018) before com-
8, 8, [(xx), where (xx) 1 max Ply|æ)
(2)
y
2. Apply beam search to greedily identify the core-set configuration among K-candidates with the lowest maximum log-confidence to reduce the variance of core-set trajectories.
BACKGROUND
Greedy versus optimal core-set for active learning. Core-set radius 5 the maximum of all distances between each data point in In {x, Vi [n]] and its closest la- belled point in Ii = {x; Vi E s} (Sener & Savarese 2018). The optimal core-
set achieves linear convergence of core-set loss in respect to by finding the acquisition set $+ with optimal core-set radii 6OPT shown in Equation (Sener & Savarese 2018 Sener and Savarese used lg-ormm between activations of the last layer of VGGT6 A.
Sor = min max min A(xiZ;;)
5 max min A(T, < 2dOPT (4)
xEfa JE
iE JERLUS
Since this problem is NP-hard Cook jet al. 1998). Sener & Savarese (2018)
Algorithm 1: Greedy core-set
(Sener
Savarese 2018)
proposed a greedy version shown Al- gorithm I with acquisitions si bounded above by Equation 4 It returns selec- tion mask over the data pool to signal la- belling requests for elements that greedily minimize the maximum distance between any point and its nearest labelled point.
def greedy core-set (zn. Tt. budget): selection = [0 Vi [[x,]]]:
to 0, budget do
i
arg argmax min A(x of());; selection (+) =1;
5
return selection;
2

---

Under review as a conference paper at ICLR 2022
Figure shows how á varies compared to --maas core-sets, where the core-set consists of the closest points to optimized K-means.
Optizaal core (0 -1.0)
Greedy cure
means set -12)
2-
1-
x
4
0-
x
22
Core-set radii (6) differs between optimal, greedy and closest-K-mean core-sets (K 1). Crosses and dots represent the labelled unlabelled set, respectively, and translucent circles show the d-cover. Sener & Savarese (2018) found a 5-linear upper bound on core-set loss convergence.
Figure 2:
Related techniques for batched acquisition. Batch active learning by diverse gradient embed- dings acquires batches in two steps. First, compute loss gradients in respect to the parameters of the last layer the classifier for each unlabelled point and its most probable label (Ash et al. 2020). Then, sample from clusters of these gradients using, for instance, K-means++ to avoid catastrophic concentration (Ash et al., 2020). We share similar intuitions about classifier confidence and intra-batch diversity being important sources of information that may enhance active learning. but differ in that we do not optimize for model change and use core-sets for diversification because of its theoretical foundations.
BatchBALD acquires batches that maximize the mutual information between the joint data and model parameters and was intended to overcome redundant sampling of repeated BALD (Kirsch) et al. 2019). We tried combining this with a probabilistic technique of estimating likely core-set locations (see Appendix A.2), but appeared that core-sets mainly require 5 minimization for core- set loss convergence.
3 METHODS
Algorithm 2 and its dependence on Algorithm implement doubt- weighte greedy core-set to run on GPU. To incorporate uncertainty information, we make two key changes the original greedy core-set algorithm. First, we compute core-sets in a warped space where distances originating from any unlabelled point diminish to zero with classification confidence.
Algorithm 2: Doubt-weighted core-set
Given inputs F. and xi, which repre- sent the unlabelled and labelled data, Line 2 of Algorithm@calle Algorithm
def doubted (mu, 2t, batch_size, budger):
min 8 = compute. min _ (Na, æt, batch
min [min g80 [(>(()) Vi [[æu]]]]:
3 to pre-compute distances of each unlabelled datum their nearest la- belled data. We scale these distances by the doubt of the classifier on the respective unlabelled data Lines 3 and 11. Each acquisition is removed from the existing unlabelled pool, and Line 12 updates new core-set radii.
2, = melmmmmmryccoo copy (
5 indez = [i Vi E -
selection 00 vi E x.. I]]
for 0, .. budget do
i = arg max min ((9) selection (Indea(()) = 1; (1)
splice out: ( ( min ()) = A(x I(x);
Figure 3 illustrates how core-sets in these spaces preferentially cover re- gions of low confidence.
min min 800) 800) y: : wk e [|>=1]]
12
return selection;
3

---

Under review as a conference paper at ICLR 2022
Core-set, greedy
Core-eet, inconfideen regions
Confidence
Perspective from origin
Purpective from (1., 1]
Figure 3: Quadrant classification of E [,2, represented as translucent dots. The first column shows the initial dataset and model confidence. Columns progress from left to right at rate of 20 label acquisitions step. Solid squares represent current acquisitions, while translucent squares represent previous acquisitions. Row shows that the core-scts maximize uniform coverage of the feature space. contrast, rows 2 and 3 show preferential coverage of class boundarics when we apply the same algorithm to point-wise distances that are scaled by the doubt of the model. Rows and show how this new method maximizes uniform coverage in the uniquely warped space perceived from candidate points in uncertain (origin) versus high-confidence (-1, 1) region. Note how the furthest distances from the origin along the (i.e., the furthest distances from 1) occur along the boundary of the red quadrant with the green and orange quadrants, rather than (1,-1) -1)).
We choose the same A as Sener & Savarese (2018) which is l2-norm between activations of the last layer of VGG16. Given unlabelled data of size U [ru),, labelled data of size L, = | feature size vi Vj E [L], D dim ( dim (7) batch size B & min L} and labelling budget b, Algorithm costs θ (ULD) steps and θ DB2D) memory with the bottleneck line 5. Excluding line 2, Algorithm 2 costs O (b D) in both computation and memory with the bottleneck on line 11. Since both the original core-set algorithm and our modification requires fine-tuning VGG16 per addition to the training set, and computing the class probabilities requires only single linear transformation, the final computational complexity the same as the original core-set search. For core-set sizes 5k to 15k, compute time scales linearly from 25 to 50 NVIDIA Titan GPU.

---

Under review as a conference paper at ICLR 2022
Algorithm 3: Memory-efficient core-set radii
compute min (æa, 3i, b) min = [co Vkk E [ka.]]::
for i = 0,..., [esl do
for j 0, Ix do
613+0.1946 A 1
(1:448) (1
min Amito
ellssto "ata5940" vk E [1, b]
min 5 5(k.e
min g(66+)) min min 80h) min 8 } wi E [.++
return min.
beam search to greedily prune and keep track of the top result- ing core-set configurations with the lowest overall confidence. Since there is no guar- antee for the optimality of greedy core-sets (Sener & Savarese (018). orientation with the most points near classification regions of high uncertainty at the cost of increasing compute and memory complexity by factor of the beam width. We modify maximum normalized log probability (Shen et al. (2018) to rank overall classifier uncertainty U of core-set s:
Second,
seek an
U(s)
log(1 I(x)) (5)
|
Figure 4 shows sample ranking of the configurations found during beam search with width A = 4.
Beam rank 1
Bearn rank
Beam rank 3
Beam rank 4
0.
560
02
8
555
00
0.0
00
0.0
552
0.5
0.0
0.5
X2
Beam rank
Figure 4: A sample acquisition from the toy quadrant dataset in Figure Ream search for the top greedy core-sets ranks configurations by increasing overall confidence (i.c., decreasing negative log confidence). Regions of high uncertainty occur near the æ = 0 and æ2 = 0 axes in this dataset. The left-most configuration (beam rank should be selected for its dual optimality of core-set radii and low overall confidence.
Active learning pipeline. For each active learning experiment, we by randomly partitioning the full training set into an initial pool of labelled data and an unlabelled pool of features. We fine- tune the parameters of a ImageNet-l-pretraal batch size of 64, we optimize for cross-entropy loss using Adam (Kingma & Ba 2015) under default hyperparameters from PyTorch (Paszke et al. 2019) and a learning rate of 0.01 for CIFAR 10/100 and 0.005 for SVHN. We then use either random acquisition, the original greedy core-set algorithm, or variations of Algorithm with the trained model produce selection mask over the unlabelled data. We enforce that the number of selected elements is equal to the labelling budget per iteration. The selected features and their labels join the training set, the model retrains with a re-initialized optimizer, and the process is repeated until the number of the labelled data reaches the specified ceiling for the experiment.
VGG16 on this initial dataset. For each training
Note that do not compare with the other baselines used in the original core-set experiments. Since the original core-set algorithm improved significantly from those baselines, we expect improvement over the original core-set algorithm to imply similar greater improvement well.
5

---

Under review as a conference paper at ICLR 2022
Table 1: Epochs of optimization required to consistently surpass 99% training accuracy.
Table[showw the iterations that found were necessary to roughly meet zero training error on the initial dataset ("First-pass"" and all addi- tions to the dataset per active learning iteration ("Thereafter"). Note that validation error is not required to satisfy the convergence requirement of core-sets, so we ignore it in our experiments.
Training epochs
Dataset
First-pass
Thereafter
CIFARTO CIFARION 100
30
12
80
20
SVHN
50
20
For the ablation studies, we tune hyperparameters and conduct ablation studies on CIFARIO (Krizhevsky 2009) using a budget of 400 labels per active learning iteration and initial dataset size of 1000 samples. We use the same hyperparameters as the ablation studies in the main exper- iments on CIFARI0/100 (Krizhevsky) 2009) and SVHN (Netzer et al. 2011), which uses a budget of 5000 labels per iteration and a starting dataset size of 5000 samples.
4 RESULTS
Figure sshows the results of ablation studies the small-scale version of the main experiments, where we observe that beam search for the core-set configuration with the lowest log confidence yields significant improvements over greedy core-set only if core-set radii are scaled by the uncer- tainty of each unlabelled sample.
81
andoo
geedy
gredy
groddy (beam=1)
73
greddy (beam=20)
undom
greedy (beam-20)
pwviglted (beam=1)
gredyy
andom
pwosigttd (bcam=20)
72
pwoighted (bcam=20)
1980
1600
1890
270
2009
300
300
380
4200
4000
160
1800
2000
3600
3000
4200
5000
400
1900
2000
300
300
420
500
5000
Label
Figure 5: Ablation results on CIFARIO showing the mean and standard deviation derived from 5 random initializations. Left: using beam search (beam=20) to greedily find the core-set configuration with the lowest log confidence has no effect. Middle: weighing pereeived distances by uncertainty (pweighted) results in better performance and beam search reduces variance, resulting in the highest final scores. Note that using a single beam in "pweighted" resulted in occasionally deteriorating performance, which avoided using 20 beams. Right: performance improvement over the original greedy core-set algorithm appears significant.
Figure 6 shows how our contributions significantly improve the label efficiency of greedy core-set on CIFARIO 10 and SVHN on large-scale active learning experiments under the same hyperparame- ters from the ablation studies. Our contributions increase absolute label efficiency above random acquisition.
Theoretical rationale for improved label efficiency using confidence-wiggheee distances. Sener & Savarese (2018) showed that the softmax function over classes is Lipschitz continuous and we denote its constant as Ag- We define confidence to be the max of the softmax output and assume that the confidence of any training point is I. Consider an unspecified unlabelled point æ,, that is located distance away from its closest labelled point z; in the training set Equation 6 shows the bound on doubt (i.e., minus confidence) as a function of distance r from the nearest training example. We interpret this be rising minimum uncertainty with increasing distance from the nearest training example, capped at 1.
((r) S min(1,rdec where min A A(T;, x..)
(6)
'E#

---

Under review as a conference paper at ICLR 2022
CIFAR10
CIFAR100
SVHN
96
80
19
07
57
94
06
55
53
84-
83-
52
91
82-
gredy
... pweighted (beam=10) 10)
ranoom
5000
10000
15000
20000
5000
10000
15000
20000
5000
10000
15000
20000
Labels
Figure 6: Means and standard deviation derived from random initializations on image classification ing the acquisition budgets Sennrr & Savarese (2018) Weighing perceived distances by uncertainty (pweighted) and using beam search (beam=10) find the core-set configuration with the lowest log confidence causes significant active lcarning improvement over vanilla core-sets.
Recall that we scale 8 by doubt obtain new radius, 8. Originally, ô was the minimum distance between each unlabelled point and its nearest labelled point; in our case, we define 8 to be the minimum distance between each unlabelled point and its nearest unlabelled point with 0 error that we know exists with probability B.. Then, Equation hoold with probability B.
{8 if 21 = 5T(6) S Ae iA. <
To clarify, assume that for any unlabelled point, with probability there exists another nearby unlabelled point that behaves as if it exists in the training set already. Instead of using the distance from the nearest labelled point, the core-set loss can use the distance from this unlabelled point instead. Equation&sshow that with probability B, the convergence of the core-set loss for all datasets where 8A. < 1 now depends on a quadratic factor of 5 versus the linear relationship from before.
1a, ui A.) S s +0 t0 (V VE[M]
o (C + (V only if oλ, < (8)
n
Recall that the greedy core-set algorithm minimizes 8 towards per optimization step. This means that larger initial training sets should benefit our algorithm more, since the smaller ó will more likely yield quadratic convergence of core-set loss.
Next, we analyze the probability of such an unlabelled point with error existing in a radius 8 around each unlabelled point. In order to do this, we make 2 key assumptions about the relationship between model confidence and empirical misclassification. Assume that the probability of incorrect classification is equal to the product of doubt with e, which represents the error rate given doubt. We further assume that e equals starting at any training point and is -iiischit continuous for any distance extending away the closest training point, shown in Equation 9 To deduce the probabil- ity 3 of at least one unlabelled point with 0 error existing between the given unlabelled point and a distance ra from its nearest labelled point, subtract from I the probability of non-zero occur- ring in all these unlabelled points, which Equation bounds (see proof in Appendix A.I
Claim
(
8
(r)(r) (()))(()))))) 2 (9)
8 1 II (r) 2
(10)
exp(6 88
r2)
r
Now suppose ra ōz, where z E [0, 1] is scaling factor of 8. Then:
26
(oVAoee
B21- B21-
(see Appendix A.I
Claim
4
(11)
z=

---

Under review as a conference paper at ICLR 2022
We will have information whether our algorithm improves upon vanilla core-sets when B 2 O, when rely on random chance that there exists unlabelled point with 0 error within distance from any unlabelled point of interest. Equation T2 shows the minimum distance 6 such a point would have be from the nearest labelled point:
820 2 ( (
0 Ande
8
(12)
2a
AcAe
Figure shows slices of the lower bound on 3 from Equation When confidence is high (i.e., low for unspecified unlabelled point located from its closest labelled point, expect higher probabilities for an unlabelled point with 0 error to exist between 62 and 6. The figure also illustrates increase in decay rate of this probability with decreasing confidence. This makes sense because we assumed that confidence, to some degree, indicates correctness of the model on unlabelled data.
Proddility (8)
06
0.
02
60
0
necrest mainning data
Figure 7: We fix A A. and observe the probability 3 of our algorithm performing better than the original greedy core-set algorithm across a range distances 8 from the nearest training point different slices of doubt z. All colored regions represent possible values 3. Orange regions occur when 1/Ae. which represent the prohability of quadratic convergence of core-set loss in respect to á (see Equation M All blue regions indicate values of 8 in which algorithm performs at least as well greedy core-set scarch. Pale blue regions
when > 8" (see Equation 12). which represent areas where cannot reason about
There is less information to extract about the surroundings of points with low confidence, so the lower bound on 9 naturally flattens sooner, resulting shorter 8* and a larger space which we cannot infer any benefit of algorithm over vanilla greedy core-sets. The decay of the lower bound close to the origin was also expected, since the space between and rapidly diminishes into 0 when shrinks, which does not allow much opportunity for unlabelled point with error to appear.
DISCUSSION
Sener & Savarese 2018) suspected the potential of incorporating uncertainty information to improve core-sets for active learning and we successfully confirm this in our implementation of greedy core- set search on doubt-scaled distances. Our ablation studies show that doubt-scaling is critical for fast core-set loss convergence while beam search for the core-sets with low overall confidence stabilizes acquisition variance. Assuming that doubt acts as cheap but noisy estimate of the distance to the nearest point with zero error, the theoretical results show that our empirical improvements is caused by probabilistic guadratic-mininizztion of 8 improving the linear order from before.
The difference between core-set loss convergence of the ablation studies versus full experiments on CIFAR10/100 and SVHN is explained by differences in their dataset and budget sizes. Larger core-sets, whose quality consists the diversity of the initial, uniformly-sampled dataset and future acquisitions, have smaller d because the maximal distance between any unlabelled point and its nearest labelled point naturally minimized as the goal any core-set algorithm. Since ó 5-quadratic convergence of core-set еттог only occur when 5 is sufficiently small (i.e., 8 < 1/)c), it is expected that our contributions improved the difference in core-set loss using the larger core-sets of the full experiments. The smaller initial datasets and acquisitions of the ablation studies would have
8

---

Under review as a conference paper at ICLR 2022
large that may exceed the mreshold-criterii for 8-quadratic convergence even 8', for which will have no guarantee of improvement above vanilla greedy core-set set search.
Our theoretical results also explain why the rates of performance improvement from method appear to diminish faster with more data. When the labelled set saturates its coverage the full dis- tribution, å diminishes towards 0. The lower bound the probability of ò-quadratic convergence diminishes to 0 regardless of model confidence in this region (see Figure (7) preventing us from rea- soning about the benefit of our algorithm. Intuitively, when the training is sufficiently large and varied such that it already covers the vast majority of the input distribution, confidence estimations may be too similar distinguish signal about ó from noise.
CONCLUSION
Greedy core-set search in doubt-scaled space empirically and theoretically improves upon the origi- nal algorithm in active learning. We show that the magnitude of improvement is greatest for datasets that are not small already comprehensive of the input distribution, which maximizes the prob- ability of quadratic convergence of core-set loss with respect to core-set radii minimization. Even in cases where the performance of our contribution equates that of the original core-set algorithm, there is no additional computational cost.
The value of our algorithm is strict improvement over the original core-set, such that active learning performance improves with more labels. We suspect that our algorithm would most benefit online, large-scale active learning systems.

---

Under review as a conference paper at ICLR 2022
7
REPRODUCIBILITY STATEMENT
See supplementary code to replicate all results.
REFERENCES
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. International Conference for Learning Representations, 2020.
William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver. Com- binatorial optimization, volume 605. Springer, 1998.
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. International Conference Machine Learming, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. International
Conference for Learning Representations, 2015.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acqui- sition for deep bayesian active learning. Neural Information Processing Systems, 32:7026-7037, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Lin Ma. Bailu Ding, Sudipto Das, and Adith Swaminathan. Active learning for ML enhanced database systems. ACM SIGMOID International Conference on Management of Data, pp. 175- 191, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Detito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Hiigh-Performacce Deep Learning Library. Curran Associates, Inc., 2019.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. Technical Report Computer Sciences Technical Report 1648, University of Wisconsin-Maddsonn 2009.
Yanyao Shen, Hyokun Yun, Zachary C. Lipton, Yakov Kronrod, and Animashree Anandkumar. Deep active learning for named entity recognition. International Conference on Learning Repre- sentations, 2018.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. arXiv preprint:1904.0m 00370, 2019.
10

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1
ROUGH WORK FOR CLAIMS
Claim 1.
8 (Aede)--ro
(
88 2 %/
(13)
exp(6 ro)²
Proof.
(J² In Pemor()dd (r)
B ==
Perool (r)
-exp =1 =1
(14)
2 1 exp
In r
Lower bound from Eq.
(15)
1 exp
r r rIn(Aeder2))
- 2r )
(see Appendix A.1
Claim
(16)
(dcde)
88 2
(see Appendix A.1 Claim 3
(17)
exp(6 ro)
Claim 2.
f In(ax²) dr = x In(ax²)) - 2x C
Proof. Use integration by parts. Let:
f(z) az
In f(z)
du dr V = x
f'(x) 2ax
du f'(x) (z) fx)
Also note:
x fx
2ax²
f(x)
ax.²
So the original problem can be integrated by parts:
J IInaa=)dds=
/ ud
=wv - -f du
x In f(x) (1a)-] f())
dx
f(x)
x Il(axz) - 2x
Claim 3.
exp 1 -2r())
(Aede) 6-
85 2
exp(6 0 )2

---

Under review as a conference paper at ICLR 2022
Proof.
exp (ri((doder)) - -2r 8
- exp (6 no In(AAAer)) 26 + 2no)
ra)
- (A Tm exp (-2(6 - -ro))
(Aede) 526
(Mode) 2no
exp (8 - ro)²
(Mode)
86 2
exp(o )
Claim 4.
(A.2,)0(1-)
85
2
(
(svAnee
1
28
exp(1 1 - 2)26
(dZzōz
e
2²
Proof.
(AoAc)6(1-z)
86
2
Aode
25(1-s)
(861-=1
2
exp(1 (1 - -2)26
Jozz
=
20z
5 Avde
28(1 =)
262
AvAade
1-2
28
E
2²
A.2 NEGATIVE RESULT: PROBABILISTIC CORE-SETS
Instead of using a deterministic algorithm to compute core-sets, we score random batches on their likelihood of being a subset of the optimal core-set. The goal is for the concatenation of the best- scoring batches with the training set to result in a set of elements that are spread out on the feature space and occur in dense regions, minimizing 8 by definition.
Suppose we are interested in classifying whether a real number is positive or not. Figure shows unlabelled data and the result of learning Gaussian mixture model (GMM) over the features. We then use the trained GMM to estimate feature probabilities, which are required for computing mod- ified natch-BALD scores (see Appendix (A.3). Figure 9 shows that higher scores indicate features that are likely spread apart. For random batches sampled from this toy dataset, Figure [0] shows that the distribution of scores form long right tail that contains the most likely core-set centers.
&sowrs the
Collected
randem meons
Histogram samples (50 bins)
GMM with
0.2
Poostaitty 62160)
0.2-
0.13
3.10-
005
800
80
20
20
Sample value
Figure 8: Left: collected data with one feature being the value along the real axis. Middle: the true distribution of the input features. Right: Gaussian mixture with 32 components fit to the collected data. We purposefully overfit the GMM because the distribution of features is not known priori and we would like high resolution for computing joint information later.
12

---

Under review as a conference paper at ICLR 2022
Most probable
Random
Modified batch-BALD
0.30
3.5
3.2
3.5
3.09
3.00
-1557.80 M-bIALL
-495.05 M--HALD
-280.00 000000 M-DUALL
Compenentt gprbablegy
20
Batch SarTipee
Figure 9: Given the trained Gaussian mixture model from Figure 8 we estimate the probability per component for each element. We use the probabilities to compute a modified batch-BALD joint information score (M- bBALD), which is positively correlated with entropy across the components. The batches with the highest scores oceur at dense regions but are spread out across the feature distribution. We want avoid redundant labelling of elements the left column. Top row: each figure contains eight dotted lines that represent locations of elements in three different batches. Bottom row: corresponding probabilities per GMM component for each element.
Distribution modified betch BALD scores
0.044
0003
0.001
3.000
Mozines bakcn thigher more
Figure 10: The distribution of modified batch-BALD scores for randomly sampled batches have long right tail from which mine for likely core-set elements. Range of scores depends on the number of components the Gaussian mixture model.
13

---

Under review as a conference paper at ICLR 2022
In the subsequent iterations, first construct unlabelled data pool that contains features that have low probability to have appeared in the labelled pool, according to a fitted GMM on the labelled pool. Then, we fit algorithm to search for the batch with the highest modified batch-BALD score when combined with the existing training data. We also experiment with interpolating the modified batch-BALD score with the least confidence acquisition metric.
GMM this modified unlabelled pool and repeat the selection
We plot accuracy versus number of labelled points for random acquisition (random), maxi- mum entropy (max-entropy), least certainty (min-max-probs), probabilistic core-set (probabilistic- coreset) and an exploitative version of probabilistic core-set that interpolates with least certainty www.bliitic-ccrrsttteppoiiiii
at 9:1 ratio improvement of the core-set variants from the random baseline in both toy datasets, although its significance is unknown. The entropy and least certainty methods performed poorly.
Figures [1 and 12 show that there is modest
035
0:5
0.75
3.65
RA028
nak encopy
0.25
100
wbb
Figure 11: In the toy experiment with 0.5 standard deviation, clusters were mostly separable and core-set variants dominated all basclines. Shaded area represents one standard deviation.
Figure shows examples data points acquired in the toy experiments by probabilistic core-set the points evaluated to be informative by maximum entropy (Figure [4] and least confidence (Figure 15). Whereas the core-set variants prioritized covering the input space, the uncertainty-basee methods focused of overlapping clusters, which are prone and hard classify.
Orig nal training set
Current training
Acquired data
-5
Figure Batch-BALD effectively maximized the distance between elements of selected batches.
14

---

Under review as a conference paper at ICLR 2022
random
man stocppy
mi mox probo
p700104 soccoreset
prodits wtboccoaataaaleeeeeee
0.80
0.0
065
602
2000
ubbt
Figure 12: In the toy experiment with I standard deviation, clusters overlapped substantially and probabilistic core-set methods formed modest upper bound in accuracy over all baselines. Shaded area represents one standard deviation.
Orig: nal training set
Current trainingsss se:
Acquired dota
10
-10
Figure 14: Maximizing entropy resulted in concentrated sampling in the most uncertain regions.
Original leeining vel
Gurrent lreining we.
Nequieed dela
-20
Figure 15: Least confidence also concentrates sampling along uncertain regions.
The poor performance entropy and uncertainty methods for large batch acquisition in noisy classification dataset agrees with existing work[Settles) (2009); Kirsch et al. (2019); Sener & Savarese (2018). The cause this wasteful labelling requests in uncertain regions of features that turned to be inseparable. In contrast, core-set variants and random acquisition are successful because they covered the majority the input space.
The effect of increasingly difficult separability acquisition function efficiency is clear in the toy data with 0.5 versus standard deviation. When multiple class distributions overlap substantially, their joint distribution density is sampled more frequently under the core-set variants, which is harm-
15

---

Under review as a conference paper at ICLR 2022
ful because those samples do not improve test accuracy for noisy class boundaries. This suggests that class inseparability may play some role in the poor performance of the core-set variants.
Overall, probabilistic core-sets barely improved from random acquisitions and cost more computa- tion than Algorithm 2 Like Sener and Savarese Sener & Savarese (2018). we also conclude with distributional density sampling will have difficulty ceeding random sampling at an unknown test because the obvious fact that i.i.d. samples are already well-represented in the target distribution. Then, the main beneficial effect of these density sampling techniques is to reduce redundancy, but this may be rare phenomenon in the typical high dimensional representations of under-determiied and nonlinear classification tasks.
the belief that any method that depends
A.3 BATCH-BALD EVALUATES THE MUTUAL INFORMATION BATCHES OF DATA
Given distribution of model parameters, Bayesian active learning by disagreement (BALD) evalu- ates the information of a single data point as its marginal entropy penalized with the average entropy across the parameter distribution Kirsch et al. (2019). Intuitively, this selects for samples that elicit low overall certainty from the Bayesian model, but high individual certainty from the competing hypotheses sampled from its parameter distribution. Naive application of BALD to batch of data may lead to the overestimation of mutual information between elements within the batch Kirsch al. 2019). On the other hand, Batch-BALA scores their joint information Kirsch al. (2019).
The Batch-BALD information metric is useful for identifying likely and different core-set centers in two important but different ways from its original setting. First, fit a GMM and sample its means 0 from P(0), which we assume to be uniform. We use these Gaussian means to estimate P x, 0). Second, since there may exist multiple means that cover the same peak, optimizing for batch BALD identifies peaks with high overall certainty that have low likelihood of intersecting with other peaks.
16


Reviews:
[{"review_id": "Z7CA5_TbZl", "reviewer": "Reviewer_qzud", "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": "Overall, the paper is well-written, where the authors provide a clear motivation of the proposed scheme, followed by a logical presentation of an enhanced core-set algorithm based on \"uncertainty-scaled\" distances, supported by experimental results that show the potential advantages of the proposed approach.\n\nDespite the simplicity of the proposed scheme, the authors show that the use of doubt/confidence to scale the distances in evaluating the data points can significantly improve the performance of the original greedy core-set algorithm.\nThe authors provide interesting insights (e.g., in Fig. 3) on how scaling the distances using confidence/doubt can enhance sampling efficiency, and also discuss when such scaling may (or may not) be beneficial (e.g., in Fig. 7).\n\nOne major concern about the current work is that it only considers the original greedy core-set algorithm for comparison, although there has been a large number of algorithms that have been spawned by this original core-set scheme.\nIt would be interesting and also important to compare the performance of the proposed uncertainty-scaled core-set algorithm with other core-set algorithms, in order to demonstrate the proposed algorithm meaningful advances the current state-of-the-art.\n\nOf special interest is the comparison against recent Bayesian core-set algorithms, which are capable of naturally incorporating uncertainties in the predictions into the selection scheme based on a Bayesian paradigm.\n\nCurrently, it appears that the doubt only considers the prediction error although there may be different ways for quantifying this doubt/confidence/uncertainty.\nFor example, we may consider Bayesian beliefs that may be continuously updated during the selection process, and it may be possible to consider the variance of the prediction error (or its confidence interval).\nIt would be meaningful to provide some additional justifications of the choice made in the proposed algorithm and discuss limitations (if any) of the current scheme, as well as alternative ways for quantifying uncertainty and their potential pros/cons.\n\n\n\n", "summary_of_the_paper": "In this paper, the authors enhance the original core-set algorithm proposed in Sener & Savarese (2018) by incorporating distance measures that are weighted by confidence/uncertainty levels.\nBased on CIFAR10/100 and SVHN image classification benchmarks, the authors show that the proposed \"doubt-weighted\" core-set algorithm can improve the active learning performance compared to the original greedy core-set algorithm.\n", "summary_of_the_review": "This paper presents an extension of the original greedy core-set algorithm.\nThe proposed scheme is relatively simple yet well-motivated, and the experimental results show that uncertainty-based distance scaling can improve the sampling efficiency of the resulting active learning scheme.\nHowever, the authors compare the performance of the proposed algorithm only to the original core-set algorithm, although the original algorithm has spawned a large number of more recent algorithms that have been shown to improve performance.\nComparison with more recent coreset algorithms - especially, Bayesian coreset algorithms that naturally incorporate uncertainties into their predictions - would strengthen the paper by demonstrating its potential advantage against the current state-of-the-art.\nFurthermore, it would be beneficial to include further discussions about alternative ways for assessing doubt/confidence/uncertainty and their pros/cons as well as any limitations of the current approach (of estimating doubt).\n\n \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "RhHiurNX0Fn", "reviewer": "Reviewer_FMtn", "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": "Pros:\n-- Paper well written and clear.\n-- Both intuitive and theoretical justifications for why uncertainty-scaled distances could improve upon non-scaled distances.\n\nCons:\n-- The addition of uncertainty based scaling, while interesting is relatively minor. It is not well justified either with respect to results generated.\n-- Experimental results remain very unconvincing, with respect to the improvement compared to normal core-sets. And generally experiments are weak. In almost all figures, the performance with scaling is almost equivalent to greedy core-sets (figure 5, and figure 6 on CIFAR100). Seems like for more complicated datasets (CIFAR100) the already small utility of the method vanishes?\n-- Non standard active learning set-up where initialisation is VGG16 ImageNet weights rather than randomly initialised weights? Would be good to see performance in this setting.\n-- No comparison to other active learning methods. There is significant room for improvement here.\n-- Computational cost of these additional steps were analysed.\n-- Claim in conclusion \"suspect algorithm would most benefit online, large-scale active learning experiment.\" Results and previous statements just above the conclusion suggest otherwise (this method only assists in very small data regimes over greedy core sets).\n-- Why does performance relative to greedy degrade on CIFAR100 (i.e. more difficult task) as compared on CIFAR10 and SVHN? Not much analysis here on that. I suspect something around the usefulness of model's uncertainty with more classes. Some analysis re interaction between uncertainty/model calibration etc. would be useful?\n\nOther questions:\n- Clarity: does model uncertainty come from new model or fine-tuned VGG16?\n- If from new model (I assumed from finetuned VGG16):, if unoptimised perhaps greedy core-set has the same computational complexity as this method; but greedy k does not for example need to have model trained from previous attempt to calculate distances (and points to choose). The method does increase training time overhead as compared to greedy core-sets?\n- If using VGG16 for uncertainty: why? and why not the new model?", "summary_of_the_paper": "This paper attempts to improve upon the greedy core-set for active learning (Sener and Savarese) by employing distances scaled by uncertainty. The proposed method then leverages a beam search algorithm to identify the best core-set configuration among candidates with the lowest log-confidence to yield further improvements. Empirically evaluated on CIFAR10/100 and SVHN.", "summary_of_the_review": "Well written paper. However, method is incremental, which is not necessarily bad, but paper does not assist with a weak experimental section and analysis of results.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R9JLTi8CN2", "reviewer": "Reviewer_4LSV", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "- The paper is not very well structured. It is hard for me to follow what authors want to say, and notations appear without definition.\n- The motivation of adding a probabilistic extension to the existing core set is not well addressed, at least I could not find it.\n- As 'memory-efficient' and 'run on GPU' is stated in the paper, is computation efficiency a part of motivation?\n- Can the main idea of the 'Theoretical rationale' part be summarized in several sentences? What is more favorable than the original method?\n- Moreover, empirical comparison with enough recent methods is lacking. There are methods published after the Sener and Savares paper.", "summary_of_the_paper": "This paper proposes to improve the core set approach to active learning of Sener and Savares by a probabilistic extension.", "summary_of_the_review": "This paper needs major revision for judgement.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "By0gCcpBAh3", "reviewer": "Reviewer_Y5dH", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength\n-\tThe authors propose a straight-forward way to incorporate uncertainty into Coreset, which is a reasonable and natural extension to Coreset.\n-\tThe authors provide thorough theoretical analysis of potential rationales behind the improved performance.\n-\tEmpirical results suggest the proposed method outperform the vanilla coreset solution, and the ablation study informs us that both beam search and uncertainty weighting is needed to achieve good performance and low variance.\n\nWeakness\n-\tThe paper seems to be not ready enough with the lack of content. Specifically, there is significant lack of literature reviews of the recent advances in active learning communities, especially in the family of Bayesian learning (e.g.  Bayesian Coreset is directly relevant to this work, which is ignored in the literature review) which usually provide much more reliable uncertainty measurements then ‘doubt’. In addition, there has been multiple works discussing similar direction (combining uncertainty with Coreset) such as [1][2], it might also worth discussing how the current setup is more advanced than related studies.\n-\tAnother problem is the lack of comparison to recent SOTA baselines. Despite that both BADGE and BatchBALD are mentioned in related work section, the authors only compare to vanilla Coreset which is rather old and non-SOTA. The reasoning that “original core-set algorithm improved significantly from those baselines, we expect improvement over the original core-set algorithm to imply similar or greater improvement as well” does not make sense as the paper was published quite early and only compared to less advanced algorithms at the time.\n-\tThe key assumption that “doubt acts as a cheap but noisy estimate of the distance to the nearest point with zero error” is a bit questionable to this reviewer, as it is known that neural networks tend to be over-confident in some regions despite the error is high. Some discussions on when the assumption might break and perhaps the consequence in that scenario would be appreciated. \n\nReference\n[1] Confident Coreset for Active Learning in Medical Image Analysis, Kim et al\n[2] Bayesian Active Learning by Disagreements: A Geometric Perspective, Cao et al\n", "summary_of_the_paper": "In this paper, the authors propose to improve the vanilla greedy Core-set active learning algorithm by (1) weighting the distance with uncertainty (measured by doubt, $1-\\max_yP(y|x)$) and (2) use beam search instead of greedy search where the beams are selected by average uncertainty. They show with several toy examples that this way the samples are concentrated closer to low-confidence region. They further try to find theoretical groundings for the advantage of the proposed algorithm with several assumptions. Finally they show that the proposed algorithm outperform vanilla coreset on CIFAR and  SVHN, and provide some ablation studies to showcase the effect of beam search and uncertainty weighting.", "summary_of_the_review": "The authors propose an extension to the vanilla Coreset which is novel but relatively straight-forward. They provide some theoretical grounding for the designed algorithm, and show with some preliminary result. However due to the obvious lack of comparison to SOTA and insufficient discussion on related work, this reviewer believe that the work is still premature to be accepted.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an improvement to the core-set active learning algorithm by leveraging distance measures weighted by uncertainty scores and using beam search instead of greedy search. 

The reviewers agreed that the paper provides a nice theoretical analysis as well as motivation for the proposal, as well an ablation that shows the proposal indeed empirically outperforms the original core-set algorithm. However, the reviewers also agreed that additional important comparisons would make the paper more convincing, including Bayesian core-set algorithms as well as other recent proposals based on the original core-set algorithm.
Decision: Reject