Active Learning Through a Covering Lens
Authors: Ofer Yehuda
Avihu Dekel
Guy Hacohen
Daphna Weinshall
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active learning
AL
low budget
probability cover
max cover
ProbCover
Deep active learning
Active learning theory

Abstract: Deep active learning aims to reduce the annotation cost for the training of deep models, which is notoriously data-hungry. Until recently, deep active learning methods were ineffectual in the low-budget regime, where only a small number of examples are annotated. The situation has been alleviated by recent advances in representation and self-supervised learning, which impart the geometry of the data representation with rich information about the points. Taking advantage of this progress, we study the problem of subset selection for annotation through a “covering” lens, proposing ProbCover – a new active learning algorithm for the low budget regime, which seeks to maximize Probability Coverage. We then describe a dual way to view the proposed formulation, from which one can derive strategies suitable for the high budget regime of active learning, related to existing methods like Coreset. We conclude with extensive experiments, evaluating ProbCover in the low-budget regime. We show that our principled active learning strategy improves the state-of-the-art in the low-budget regime in several image recognition benchmarks. This method is especially beneficial in the semi-supervised setting, allowing state-of-the-art semi-supervised methods to match the performance of fully supervised methods, while using much fewer labels nonetheless. Code is available at https://github.com/avihu111/TypiClust.

Active Learning Through a Covering Lens
Ofer Yehudat, Avihu Dekel', Guy Hacohen 11 Daphna Weinshall School of Computer Science & Engineering
Edmond and Lily Safra Center for Brain Sciences
The Hebrew University of Jerusalem Jerusalem 91904, Israel
foter. yehuda, wekeh, guy hacohen, (aaaphaaammaal... www..uii.ee... aa.jj.cc.... ac.
Abstract
Deep active learning aims to reduce the annotation cost for the training of deep models, which is notoriously data-hungry. Until recently, deep active learning methods were ineffectual the low-budget regime, where only a small number of examples annotated. The situation has been alleviated by recent advances in representation and self-supervised learning, which impart the geometry of the data representation with rich information about the points. Taking advantage of this progress, we study the problem of subset selection for annotation through a "covering" lens, proposing ProbCover new active learning algorithm for the low budget regime, which seeks to maximize Probubility Coverage. We then describe dual way to view the proposed formulation, from which one can derive strategies suitable for the high budget regime of active learning, related to existing methods like Coreset. We conclude with extensive experiments, evaluating ProbCover in the low-budget regime. We show that our principled active learning strategy improves the state-of-the-art in the low-budget regime several image recognition benchmarks. This method is especially beneficial in the semi-supervised setting, allowing state-of-the-an fully supervised methods, while using much fewer labels nonetheless. Code is available hutps://ittub..om/aa I
supervisd methods match the performance
Introduction
For the most part, deep learning technology critically depends access large amounts of annotated data. Yet annotations are costly and remain so even in our era of Big Data, Deep active learning (AL) aims to alleviate this problem by improving the utility of the annotated data. Specifically, given fixed budget of examples that can be annotated, and some deep learner, AL algorithms aim to query those b examples that will most benefit this learner.
In order to optimally choose unlabeled examples to annotated, most deep AL strategies follow
some combination of two main principles: 1) Uncertainty sampling [e.g.. 26, 48, 3, 14, 15, 36, 25], in which examples that the learner most uncertain about are picked, to maximize the added value of the new annotations. 2) Diversity Sampling [c.g.. 1, 22, 16, 38, 18, 40, 37, 17, 47, 42, 46], in which examples are chosen from diverse regions the data distribution, to represent it wholly and reduce redundancy in the annotation.
Most AL methods fail improve over random selection when the annotation budget is very small [35, 39, 7, 32, 55, 21, 2]. phenomenon sometimes termed "cold start" [8, 49, 16, 50, 23]. When the budget contains only a few examples, they struggle to improve the model's performance, and even fail to reach the accuracy of the random baseline. Recently, it was shown that uncertainty sampling is inherently unsuited for the low-budget regime, which may explain cold start phenomenon [19]. The low-budget scenario is relevant in many applications, especially those requiring expert tagger
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ProbCover selection
Coreset selection
Low
(a) Samples
(b) 20 Samples
(c) 50 Samples
Figure I: ProbCover selection (top) vs Coreset selection (bottom) of 5/20/50 samples (out of 600). Selected points are marked by which is color-coded by density (sce color code bar the right). Density is measured using Gaussian Kemel Density Estimation, and the covered area is marked light blue. Coreset attempts to minimize ball size, constrained by complete coverage, while ProbCover attempts to maximize coverage, constrained by a fixed ball size. Note that especially in low budgets, such as 5 samples, Coreset only selects outliers of the distribution (yellow), while ProbCover selects from dense regions of the distribution (red).
whose time is expensive (e.g., a radiologist tagger for tumor detection). If we want to expand deep learning to new domains, overcoming the cold start problem is an ever-important task.
In this work, we focus on understanding the very low budget regime of AL, where the budget of b examples cannot dependably represent the annotated data distribution. To face up to this challenge, in Sections 2.1-2.2 we model the problem as Max Probability Cover, defined follows: given some data distribution, and a radius select the b examples that maximize the probability of the union of balls with radius 8 around each example. We further show that under a separation assumption that realistic in semantic embedding spaces, Max Probability Cover is befitting the nearest-neighbor classification model, in that it minimizes upper bound on its generalization error.
In Section 2.4 we show a connection with existing deep AL methods, like Coreset [37], and explain why those methods are more suitable for the bighet regime than the low-budget regime. This phenomenon visualized Fig. where we see that with only a few examples to choose, Coreset an AL strategy that employs the principle of diversity sampling chooses distant and often abnormal points, while ProbCover chooses representative examples.
When using the empirical data distribution, we further show that Max Probability Cover can be reduced to Max Coverage - known classical NP-hard problem [34] (see Section 2.2). To obtain practical AL strategy, in Section 3 we adapt greedy algorithm for the selection of examples from fixed finite training set of unlabeled examples (the training set), which guarantees approximation to the problem. We call this new method ProbCover.
In Section 4 we empirically evaluate the performance of ProbCover on several computer vision datasets, including CIFAR-10, CIFAR-100, Tiny-ImageNe ImageNet and its subsets. ProbCover is thus shown significantly outperform all alternative deep AL methods in the very low-budget regime. Additionally, ProbCover improves the performance of state-of srate-of-the-at semi-supervisee methods, which were thought until recently to make AL redundant [6], allowing for the learning of computer vision tasks with very few annotated examples.
Relation to prior art Recent work investigated AL methods based on an approximation to a facility location problem [45, 30, 54, 37, 43], which variant of the covering problem. In the minimax facility location problem [13]. the entire distribution is covered with a fixed number of balls, which can vary in size, whereas in ProbCover the size the balls is fixed, and we are allowed to cover only part of the total distribution. While this difference may seem minor, in the low-budget regime, when the budget not large enough to represent the data, examples chosen by the facility location problem not representative (as illustrated in Fig. 1), which leads to poor performance (as shown in Fig. 10).

---

Summary of contribution
(i) Develop theoretical framework to analyze AL strategies in embedding spaces, with "dual" low and high-budget interpretations.
(ii) Introduce ProbCover, a low-budget AL strategy motivated by our framework, which signifi- cantly outperforms other methods in the low-budget regime.
(iii Demonstrate the outstanding competence of ProbCover in semi-supervised learning with very few labeled examples.
2 Theoretical Analysis
To address the challenge of active learning in low budgets, we adopt a point coverage framework. Computationally. we analyze the generalization of the Nearest Neighbor (NN) classification model, as this model depends exclusively on distances from a set of training examples and does not involve any additional inductive bias. Thus in Section 2.1 we develop a bound on the generalization error in I-NN models. It follows from the analysis (see discussion below) that if full coverage is required, which is only practical in the high budget regime, the minimization of this bound translates to the optimal minimax facility location problem. which is known to be NP-hard and which the AL Coreset algorithm by Sener and Savarese [37] is designed to approximate.
In contrast, in the low budget regime, the aforementioned bound can best be optimized by seeking labeled set I, whose probability of covering the unlabeled set is maximal. In Section 2.2 we show that this problem is also NP-hard. Furthermore, when the data distribution is not known and is being approximated by the empirical distribution, we show that it is equivalent to the classical Max Coverage problem. ProbCover described in Section 3, designed to solve this problem. In Section 2.4 we discuss a sense in which the high budget and low budget problems are dual.
2.1 Bounding the Generalization Error
We shall now derive bound the generalization error of the 1 Nearest Neighbor (1-NN) classifier. We start with some necessary notations and definitions. Most important is the assumption of 6-purity, which states that most of the time, points that are less than ô apart have the same label. We then prove a lemma, showing that given a labeled set L and the coverage it achieves, and given the ō-purity assumption, the probability of point being inside this cover and still being falsely labeled is small. From this, we finally derive bound on the generalization error, which is stated in Thm. 1.
Notations Let X denote the input domain whose underlying probability function is denoted P, and let Y = [k] denote the target domain. Assume that true labeling function f : X + exists. Let X = { denote an unlabeled set of points, and b < the annotation budget. Let L C X denote the labeled set, where L = b. Let Bs (x) = (x' || - x|I2 S 8) denote a ball centered at of radius 5. Let C C(L, 8) = UpeL Bs(z) denote the region covered by 8-balls centered at the labeled examples in L. We call C(T, 8) the covered region and P (C) the coverage.
Definition 2.1. We say that ball (z)x)) is pure if Vx BB(x): f(x') f(x).
Definition 2.2. We define the purity as
π (5) = (fx: : Bs (x) is pure))
Notice that (8) is monotonically decreasing.
Let f denote the 1-NN classifier based on L. We split the covered region C(L, 8) into two sets:
Cright = {- O: f(x) = f())}, Curong C Cright.
Lemma 1. Cwrong C {z: Bx(x) is not pure).
Proof. Let & E Curong. Let E L denote the nearest neighbor to æ. Then they have the same predicted label, f(x) f(c), and f(c) f(c) because c is labeled. Since is wrongly labeled, ((x) A f(x), which implies that
f(c) f(c) f(x) # f(z).
3

---

Finally, since E Owrong S. C' is in the coverage, d(z,, c) < 6, which means that e E Bs(x) with different label and so (x) not pure.
Corollary 1.
p(Curong) I P({x: Bz(x) is not pure)) T(8).
Theorem 1. The generalization error of the I-NN classifier f bounded as follows
E + s (L-P(CCL,,)) + (1 (()).
Proof.
E
f(x) # f(x)]
=E[1 fw) + B[1 (1)) f(x) fan
S & C) B[1 fx xeCriaal + El1 f())+(()) 1 wEOurong
s P(x + P(x E Curong)
s PICC((()))
(()))
Note that (1) gives different bound for different 8 values, which also depends on the labeled set L. This bound introduces trade-off: as 5 increases, the coverage increases, but the purity decreases. Ideally, we should seek a pair {6, }} that achieves the tightest bound.
Discussion We can interpret (1) in the context of two boundary conditions of AL: high-budget feasible as we
and low-budget. In the high-budget regime, achieving full coverage P(C) have many points, and the remaining challenge is to reduce 1 (0). Accordingly, since (o) is monotonically decreasing, we seek to minimize subject to the constraint P(C) = 1. This is similar to Coreset [37]. In the low-budget regime, full coverage entails very low purity, which (if sufficiently low) makes the bound trivially 1. Thus, instead of insisting on full coverage, we fix a 5 that yields "large enough" purity (6)) 0, and then seek labeled set that maximizes the coverage P(C). We call this problem Max Probability Cover.
2.2 Max Probability Cover
Definition 2.3 (Max Probability Cover). Fix 8 > O, and obtain subset I. C X, [T] maximizes the probability of the covered area P(C(L, 8))
b, that
argmax PU Bs(r)) LEX:14==6
(2)
FEL
An optimal solution to (2) would minimize the bound in (1), when is fixed.
Unfortunately, when moving to practical settings there are two obstacles. The first is complexity: Theorem 2. Max Probability Cover is NP-hard.
Proof. (Sketch, see full proof in App. B) We construct reduction from an established NP-hard problem (Max Coverage, see Def. A. to Max Probability Cover. For the collection of subsets S = ( (S,,... Sm), consider the space RT' and collection of 5-balls (Bs(::)) with the exhaustive intersection property. This means that any subset of the balls has at least one point that is contained in all the balls in the subset, but not contained in any other ball (see example in Fig. 2). The existence of such collection balls in R" Vm, is proved in Lemma (see App. B). We then assign each S, Bx(x)). and each element in S is mapped to point in the intersection of all the balls assigned to subsets that contain it. Each such point then defines a Dirac measure, the normalized sum of which determines probability distribution the Max Probability Cover can be translated back to a selection of subsets, which is the solution to the original Max Coverage problem.
m The selection of 8-balls that is the solution to

---

(a)
(b)
Figure 2: Illustration in I of exhaustive intersection (see Def. B.2). (a) With 3 balls, every subset of balls has point that is contained only the specific subset. Thus this of 3 balls the exhaustive intersection property. (b) With balls, any point in the intersection of two opposite balls also contained in at least one other ball. Thus this set of 4 balls does not have the exhaustive intersection property. In the drawing, the region of intersection between the red and blue balls is outlined in purple, while the points within the region that are unique this pair are marked in light purple. Note that in example (b), this set empty.
2.3 Using the Empirical Distribution
When employing Max Probability Cover, the second practical problem concerns the data distribution, which is hardly ever known apriori. In fact, even when known, the subsequent probabilistic computa- tions are often intractable and hard to approximate. Instead, we may use the empirical distribution P(A) - E L,,EA an approximation, which gives the following useful result:
Proposition. When P is the empirical distribution P. the Max Probability Cover objective function equivalent to the Max Coverage objective, with (B,( X as the collection of subsets.
Proof. Given a labeled set = ffxe)i- we show equality objectives up to constant
P
Bo(as) 1=1
= P (1v E
R"
3i ||x; yll < 8))
100 - x1| < <8H
((B(()))
2.4 The "Duality" of Max Probability Cover and Coreset
The Coresel AL method by Sener and Savarese [37] minimizes the objective
8(L) max min d(x,, c) minf8 R_: X U B,(c))
wex
We can rewrite the above in the language of distributions
(L) min E R4: P( P(U Bs(c)) =}
CEL
use the empirical distribution then 6(L) = (L). In this framework we can say that Max Probability Cover and Coresel are dual problems in the following loose sense:
Max Probability Cover minimizes the generalization enror bound (1) when we fix and seek to maximize the coverage, which is suitable for the low budget regime.
2. Coreset minimizes the generalization error bound (1) when we fix the coverage to 1 and minimize which is suitable for the high budget regime because only then can we the coverage
This duality is visualized in Fig. 1.
5

---

3 Method: ProbCover
To deliver a practical method, we first note that our approach implicitly relies on the existence of good embedding space [4, 10, 53], where distance is correlated with semantic similarity, and where similar points are likely to bunch together in high-density regions, As is now customary [e.g., 30, 19], we use embedding space derived by training a self-supervised task over the large unlabeled pool. In such a space similar labels often correspond to short distances, making 1 1-NN classification suitable, and also providing for the existence of large enough ò balls with good purity and coverage properties.
Secondly, we note that Max Coverage is NP-hard and cannot be solved efficiently. Instead, as its objective is submodular and monotone [27]. we use the greedy approximate algorithm that achieves (1 -approximation [27]. A better approximation is impractical, shown in App. D.1. See App. for additional time and space complexity analysis.
Below, we describe the greedy algorithm in Section 3.1, and the estimation of ball size in Section 3.2.
3.1
Greedy Algorithm
Algorithm 1 ProbCover
Input: unlabeled pool U, labeled pool L, budget 6, ball-size 6, Output: set of points to query
X < Embedding of representation learning algorithm on U
G (V X, E ((x, : Bs (+)))
for all E L do
Remove the incoming edges to covered vertices, ((x',x) E E: (c,z)) E}, from E
end for
Queries
for all i do
Add e U with the highest out-de in G to Queries
Remove the incoming edges to covered vertices, xxx E E: (c,x) E E}, from E end for return Queries
The algorithm (see Alg. below for pseudo-code) goes as follows: First, construct directed graph G = (V, (VV.) E), with V = X the embedding of the data space, and (z, E > x' E BB (z) + d(x,,') S In G, each vertex represents specific example, and there is an edge between two vertices (rr, x') af is covered by the 5-ball centered at æ (distances are measured in the embedding space). The algorithm then performs b iterations of the following two steps:
(i) Pick the vertex Zmaz with the highest out-degree for annotation;
iii) Remove all incoming edges to Tmar and its neighbors.
As ProbCover uses sparse representation of the adjacency graph, it is able to scale to large datasets while requiring limited space resources. The complexity analysis of the algorithm, and specifically the complexity of constructing the adjacency graph and of the sample selection, are discussed in the Appendix F.
3.2 Estimating
Our algorithm requires the specification of Alyper-paramenn 8, the ball radius, whose value depends on details of the embedding space (see App. C. for embeddings used). In choosing 6, we need to consider the trade-off between large coverage P(C") and high purity T0)). We resolve this trade-off with the following heuristic, where we pick the largest å possible, while maintaining purity above a certain threshold E (0, 1). Specifically,
max (0: (0) 2 a
Importantly, a is more intuitive to tune, and is kept constant across different datasets (unlike d). We still need to estimate the purity (8), which depends on the labels, from unlabeled data. To this end, we estimate purity using unsupervised representation learning and clustering, First, we cluster

---

self-supervised features using k- k-maans with & equal to the number of classes. For given 6, we compute the purity x68 using the clustering labels as pseudo-labels for each example. Searching for the best 6, we repeat the process and pick the largest 8 so that at least 0.95 of the balls are pure.
In Fig. 3, we plot the percentage of pure balls across different datasets function of 6, where the dashed line represents the 8 chosen by ProbCover.
Purlty
Purtyy
Punty
00
08
(a) CIFAR-10
(b)
CIFAR-100
(c) Tiny-ImageNet
(d) ImageNet
Figure 3: Ball purity, as a function of 6, estimated from the unlabeled data (see text). The dashed line marks the
highest 6, after which purity drops below = 0.95.
4 Empirical Results
We report a set of empirical results, comparing ProbCover to other AL strategies in a variety of settings. We focus on the very low budget regime, with a budget size b of similar order of magnitude as the number of classes. Note that since the data is picked from an unlabeled pool, chances are that the initial labeled set not going to be balanced across classes, and the early stages of training some classes will almost always be missing. ProbCover's s excellent performance nevertheless, as seen below, demonstrates its robustness in the presence of this hurdle.
4.1 Methodology
Three deep AL frameworks are evaluated:
Fully supervised: train a ResNet-18 only on the annotated data, fully supervised task. (ii) Semi-supervised by transfer learning: create representation of the data by training with self sudervueeee task on the unlabeled data, then construct a 1-NN classifier using the ensuing representation in supervised manner. This framework is intended to capture the basic benefits of remi-supervised learning, regardless the added benefits provided by modern semi-supervised learning methods and the sophisticated derivation of pseudo-labels.
(iii) Fully semi-supervised: train a competitive semi-supervised model on both the annotated and unlabeled data. In our experiments we use FlexMatch by Zhang et al. [51]-
In frameworks (i) and (ii) adopt the evaluation kit created by Munjal et al. [33], in which can compare multiple deep AL strategies in a principled way. In framework (ii), we adopt the code and hyper-parameters provided by FlexMathh.
When evaluating frameworks and (ii), we compare ProbCover deep AL strategies baselines. (1) Random query uniformly. (2)-(4) query examples with the lowest score, using the following
basic scores: (2) Uncertainty max softmax output, (3) Margin margin between the two highest softmax outputs, (4) Entropy- inverse entropy of softmax outputs. (5) BADGE [1]. (6) DBAL
[15]. (7) TypiClust [19]. (8) BALD [26]. (9) W-Dist [30], see also App. D.4. (10) Coreset [37]. We note that while most baseline methods are suitable for the high budget regime, TypiClust and W-Dist are also suitable for the low budget regime. Similarly to ProbCover, TypiClust requires a good embedding space work properly. When comparing ProbCover and TypiClust, and in order to avoid possible confounds, we use the same embedding space for both methods.
These AL methods are evaluated on the following classification datasets: CIFAR-10/100 [28]. TinylmageNet, [29], ImageNet [12] and its subsets (following Van Gansbeke et al. [41]). When considering CIFAR-10/100 and IinylmageNet, we use as input the embedding of SimCLR [9] across all methods. When considering ImageNet we use as input the embedding of DINO [5] throughout. Results on NetgeNet-50/100 are deferred to App. D.I. Details concerning specific networks and hyper-parameters can be found in App. C, and in the attached code in the supplementary material. When evaluating frameworks (i) and (ii), we perform active learning rounds, querying a fixed
7

---

budget of b examples in each round. In framework (iii), as FlexMatch is computationally demanding. we only evaluate methods on their initial pool selection capabilities.
4.2
Main Results
(i) Fully supervised framework. We evaluate different AL methods based on the performance of deep neural network trained directly on the raw queried data. In each round, we query samples where b is equal to the number of classes in each dataset, and train ResNet- 18 on the accumulated queried set. We repeat this for 5 active learning rounds, and plot the mean accuracy of 5 repetitions (3 for ImageNet) in Fig. 4 (see App. D.1 for additional results).
ProbCover BADGE BALD CoreSct DBAL Entropy Marg TypiClust Uncertainty W-Dist Random
Accuracy 1%6
Accuracy 1%))
Accuracy 1%)
18
Cumulative Budget
Budget
Cumulative Dudget
Budget
(a) CIFAR-I0
(b) CIFAR-100
(c) Tin-- ImageNet
(d) ImageNet
Figure 4: Framework (i), fully supervised: The performance of ProbCover is compared with baseline AL strategies in image classification tasks in the low budget regime. Budget b guarantees average sample per class, thus the initial sample may be imbalanced. The final average test accuracy in each iteration reported, using repetitions (3 ImageNet). The shaded area reflects standard error across repetitions.
(ii) Semi-supervised by transfer learning. In this framework, we make use of pretrained self- supervised features, and measure classification performance using the 1-NN classifier. Accordingly, each point is classified by the label of nearest neighbor (within the selected labeled set T.) in the self-supervised features space. In low budgets, this framework outperforms the fully-supervised framework (i), though is not as effective as the full-blown semi-supervised lcarning framework (iii). This supports the generality of our findings, not limited to any specific semi-supervised method. Similarly to Fig. 4, in Fig. we plot the mean accuracy of repetitions for the different tasks.
ProbCover BADGE
Entropy Marg TypiClust Uncertainty
Accuracy (9)
Accuracy (9%)
3
Accuracy (%)
Accurscy (%)
40
12
seca Cumulative Budget
200
Cumulative Budget
Budget
Budget
(n) CIFAR-10
(b) CIFAR-100
(c)
Tiay-mmageNer
(d) ImageNet
Figure 5: Comparative evaluation of framework (ii) semi-supervised by transfer learning, caption of Fig. 4.
(iil) Semi-supervised framework. We compare the performance of different AL strategies used prior to running FlexMatch, a state-of-the- art semi-supervised method. In Fig. 6 we show results with repetitions of FlexMatch, using the labeled sets provided by different AL strategies and budget b equal to the number of classes. We see that ProbCover outperforms random sampling and other AL baselines by large margin. We note that in agreement with previous works [6, 19], AL strategies that are suited for high budgets do not improve the results of random sampling, while AL strategies that are suited for low budgets achieve large improvements.
4.3 Ablation Study
We report set of ablation studies, evaluating the added value of each step of ProbCover.

---

100
32,48
92,19
44.10
30-
Accuracy (%)
Accuracy (%6
10
22,56
Accuracy
7.29
20
15.76
2.74
M0.57
Random
Coresct
Typiciust ProbiCovr
Random
Coresot
Typiclust PropCover
Random
Corceet
Topiclust ProbCover
(2) CIFAR-10
(b) CIFAR-100
-mngeeeeeNNet
Figure 6: Framework (iii) Semi-supervised: comparison AL strategies in semi-supervised task. Each bar shows the mean lest accuracy after repetitions of FlexMatch trained using labeled examples. where equal to the number of classes in each task. Error bars denote the standard error.
Random initial selection When following the uncertainty sampling principle, many AL methods do, a trained learner needed. Any such method requires therefore a non-empty initial pool of labeled examples to train rudimentary learner, from which uncertainty selection can be bootstrapped. In the set of methods evaluated here (see Section 4. 4) only two ProbCover and TypiClust are not affected by this problem. This be seen in Fig. 4, noting that only these methods do better than random in the initial step. Is this the only reason they outperform other methods in low budgets?
To address this question, repeat the experiments reported in Fig. 4a-4b, using initial random set of annotated examples across the board and by methods. Results are reported in Fig. 7. When comparing Fig. 4a-4b and Fig. 7,
that the advantage of ProbCover and TypiClust goes beyond the initial set selection, and remains in effect even this factor is eliminated.
ProbCover + BALD DBAL
Margin
Uncerlain.y
Entrapy
TypiClust
ProbCover SGB--p ProbCover Random
Accuracy (96)
Accuracy (%6
20
Accuracy (%)
Accuracy
10
103
200
483
200
22
102
35
40 600
Cumulative Budget
Cumulative Budget
Curulaatvve Budget
Cumulstive Budget
(a) CIFAR-10
(b) CIFAR-100
CIFAR-10
CIFAR-I00
Figure 7: Random Initial pool in the supervised frame- work, an average of sample per class.
Figure Comparison ProbCover when applied the raw data vs the embedding space.
RGB space distances As discussed in Section our approach relies on the existence of a good embedding space, where distance is correlated with semantic similarity. We now verify this claim by repeating the basic fully-supervised experiments (Fig. 4) with one difference: ProbCover can only use the original RGB space representation to compute distances. Results are shown in Fig. 8. When comparing the original ProbCover with its variant using RGB space, significant drop in performance is seen expected, demonstrating the importance of the semantic embedding space.
The interaction between 5 and budget size To understand the interaction between the hyper- parameter 8 and budget we repeat our basic experiments (Fig. 4) with different choices of å and using CIFAR-10. For each pair (6, b). select an initial pool of 6 examples using ProbCover with d balls, and report the difference in accuracy from the selection of b random points. Average results across repetitions are shown in Fig. 9 as a function of b. We see that the budget b increases, smaller 5's are preferred.
Coreset vs. ProbCover. In Section 2.4 we argue that ProbCover is suitable for low budgets, while Coreset is suitable for high budgets. To verify this claim, compare their performance under the following setups while using the same embedding space, and report results on CIFAR-10:
Low budget Select initial pool of 100 samples using the SimCLR representation.

---

+5-34 +did
Dif Random
Accurace (%)
(%
00,54
(96
$3.00
$1,04
22,03
11
In Pool Size Sogsscale
Conseet
Prccower
fancor
Corneet
Fandom
Coneeet
Procoverr
Rondon
(a) Low budget
(b) Mid budget
(c) High Budget
Figure 9: The accuracy difference between ProbCover when using different values, and the outcome of b random samples (average over 3 repetitions).
Figure 10: Comparing the performance under the supervised framework of ProbCover and Coresel on different budget regimes. The low budget shows initial pool selection of 100 samples. Mid/HHigh budget start with IK/5K samples and query additional IK/SK samples (see text).
High budget- Train model on 5K randomly selected examples. Then select an additional set of 5K examples using the learner's latent representation. This the setup used by Sener and Savarese [37].
Mid budget- Same as high budget, except the initial pool size and added budget are IK.
Results are reported in Fig. 10. the low budget regime, ProbCover outperforms Coreset as would be expected. In the mid-budget regime, where the feature space of the learner is informative, only ProbCover achieves significant improvement over random selection. In the high budget regime, Coreset improves over random selection, while ProbCover is least effective.
5 Summary and Discussion
We study the problem of AL in the low-budget regime. We model the problem as Max Probability Cover, showing that under certain assumptions on the data distribution. which are likely to hold in self-supervised embedding spaces, it optimizes an upper-bound on the generalization error of 1-NN classifier. We devise an AL strategy termed ProbCover, which approximates the optimal solution. We empirically evaluate in supervised and sumi-supervised frameworks across different datasets, showing that ProbCover significantly outperforms other methods in the low-budget regime.
In future work intend to investigate: (i) possible avenues for improving the choice by making use of already known labels, or inferring a score for ô through the topology of the resulting covering graph; (ii) extensions of the current formulation of Max Probability Cover, by making the radius of the balls dependent on the samples rather than uniform; (iii) soft-coverage approaches, where the covering notion binary but some continuous measure, which may allow us to do away with 5.
Acknowledgments
This work was supported by Israeli Ministry Science and Technology, and by the Gatsby Charitable Foundations. We grateful to our dedicated NeurIPS AC, who acted upon the lengthy discussion between us and the reviewers, as seen on OpenReview.
References
[1] Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 30-30, 2020. OpenReview.net, 2020.
[2] Josh Attenberg and Foster Provost. Why label when you can search? alternatives to active learning for applying human resources to build classification models under extreme class imbalance. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 423-432, 2010.
10

---

[3] William H Beluch, Tim Genewein, Andreas Nürnberger. and Jan M Köhler. The power of ensembles for active learning image classification. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9368-93777 2018
[4] Javad Zolfaghari Bengar, Joost van de Weijer, Bartlomiej Twardowski, and Bogdan Raducanu. Reducing label effort: Self-supervised meets active learning. In Proceedings of the TEEE/CVF International Conference Computer Vision, pages 1631-1639, 2021.
[5] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. arXiv preprint httl:2104.14244 2021.
[6] Yao-Chun Chan, Mingehen Li, and Samet Oymak. On the marginal benefit of active learning: Does sulf-supervision eat its cake? In ICASSP 202/-202/ I IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3455-3459, IEEE, 2021.
[7] Akshay L Chandra, Sai Vikas Desai, Chaitanya Devaguptapu, and Vineeth N Balasubramanian. On initial pools for deep active learning. In NeurlPS 2020 Workshop on Pre-registration in Machine Learning, pages 14-32. PMLR, 2021.
[8] Liangyu Chen, Yutong Bai, Siyu Huang, Yongyi Lu, Bihan Wen, Alan L Yuille, and Zongwei Zhou. Making your first choice: To address cold start problem in vision active learning. arXiv preprint arXiv:2210.02244. 10.02442, 2022.
[9] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607. PMLR, 2020.
[10] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self-supervised models are strong semi- suni-supee learners. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florins Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
Balcan, and Hsuan-Tiee Lin, editors, Advances in Neural
[11] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 702-703, 2020.
[12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages
Icee, 2009.
[13] Reza Zanjirani Farahani and Masoud Hekmatfar. Facility location: concepts, models, algorithms and case studies. Springer Science & Business Media, 2009.
[14] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference machine learning, pages 1050-1059. PMLR, 2016
[15] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pages 1 183-1192. PMLR, 2017.
[16] Mingfei Gao, Zizhao Zhang, Guo Yu, Sercan Ö Arik, Larry S Davis, and Tomas Pfister. Consistency- semi-supervised active learning: Towards minimizing labeling cost. In European Conference on Computer Vision, pages 510-526. Springer, 2020.
[17] Yonatan Geifman and Ran El-Yaniv, Deep active learning over the long tail. arXiv preprint arXiv: 2017.
[18] Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv preprint 2019.
[19] Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on a budget: Opposite strategies suit high and low budgets. arXiv preprint 2202:2200.0029. 2022.
11

---

[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[21] Tao He, Xiaoming Jin, Guiguang Ding, Lan Yi, and Chenggang Yan. Towards better uncertainty sampling: Active learning with multiple views for deep convolutional neural network. In 2019 IEEE International Conference Multimedia and Expo (ICME), pages 1360-1365. IEEE, 2019.
[22] SeulGi Hong, Heonjin Ha, Junmo Kim, and augmentation-based consistency estimation. arXiv preprint arXiv:201 1.00666, 2020.
Choi. Deep active learning with
[23] Neil Houlsby, José Miguel Hernández-Lobato, and Zoubin Ghahramani. Cold-start active learning with robust ordinal matrix factorization. In International Conference on Machine Learning, pages 766-774. PMLR, 2014.
[24] Harry B III Hunt, Madhav V Marathe, Venkatesh Radhakrishnan, Shankar S Ravi, Daniel J Rosenkrantz, and Richard Stearns. Nc-approximation schemes for np-and pspace-hard problems for geometric graphs. Journal of algorithms, 26(2):238-25) 274, 1998.
[25] Ajay J Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 2372-2379. IEEE, 2009.
[26] Andreas Kirsch, Joost Van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. Advances in neural information processing systems, 32:7026-7037, 2019.
[27] Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3: 71-104, 2014.
[28] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Online, 2009.
[29] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N. 7(7):3, 2015.
[30] Rafid Mahmood, Sanja Fidler, and Mare T Law. Low budget active learning via wasserstein distance: An integer programming approach. arXiv preprint arXiv:2106.02966 2021.
[31] Dániel Marx. Efficient approximation schemes for geometric problems? European Sympo- sium on Algorithms, pages 448-459. Springer, 2005.
[32] Sudhanshu Mittal, Maxim Tatarchenko, Özglin Çiçek, and Thomas Brox. Parting with illusions about deep active learning. arXiv preprint arXiv: 19120056., 2019.
[33] Prateek Munjal, N. Hayat, Munawar Hayat, Sourati, and Khan. Towards robust and reproducible active learning using neural networks. ArXiv, abs/2002.09564, 2020.
[34] George I. Nemhauser, Laurence A Wolsey, and Marshall I. Fisher. An analysis of approximations for maximizing submodular set functions Mathematical programming, 14(1):265-29) 1978.
[35] Kossar Pourahmadi, Parsa Nooralinejad, and Hamed Pirsiavash. A simple baseline for low- budget active learning. arXiv preprint arXiv:21 10. 12033, 2021.
[36] Hirammayi Ranganathan, Hemanth Venkateswara, Shayok Chakraborty, and Sethuraman Pan- chanathan. Deep active learning for image classification. In 2017 IEEE International Conference on Image Processing (ICIP), pages 3934-3938. IEEE, 2017.
[37] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. In International Conference Learning Representations, 2018.
[38] Changjian Shui, Fan Zhou, Christian Gagné, and Boyu Wang. Deep active learning: Unified and principled method for query and training. International Conference on Artificial Intelligence and Statistics, pages 13181318. PMLR, 2020.
12

---

[39] Oriane Siméoni, Mateusz Budnik, Yannis Avrithis, and Guillaume Gravier. Rethinking deep active learning: Using unlabeled data at model training. In 2020 25th International Conference on Puttern Recognition (ICPR), pages 1220-1222 1227. IEEE, 2021.
[40] Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5972-5981, 2019.
[41] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Mare Proesmans, and Luc Van Gool. Scan: Learning to classify images without labels. In European Conference on Computer Vision, pages 268-208800 285. Springer, 2020.
[42] Zengmao Wang. Bo Du, Lefei Zhang, and Liangpei Zhang. A batch-mode active learning framework by querying discriminative and representative samples for hyperspectral image classification. Neurocomputing, 179:88-100, 2016.
[43] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963. PMLR, 2015,
[44] Daphna Weinshall, Hynek Hermansky, Alon Zweig, Jie Luo, Holly Jimison, Frank Ohl, and Misha Pavel. Beyond novelty detection: Incongruent events, when general and specific classi- fiers disagree. Advances in Neural Information Processing Systems, 21, 2008.
[45] Ziting Wen, Oscar Pizarro, and Stefan Williams. Active seff-semi-supervised learning for few labeled samples fast training. arXiv preprint Stti:::22030456000 2022.
[46] Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, 113()):13-122)) 2015.
[47] Changchang Yin, Buyue Qian, Shilei Cao, Xiaoyu Li, Jishang Wei, Qinghua Zheng, and lan Davidson. Deep similarity-based batch mode active learning with exploration-exploitaiin In 2017 IEFE International Conference on Data Mining (ICDM), pages 575-584. IEEE, 2017.
[48] Donggeun Yoo and In So Kweon. Learning loss for active learning, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 93-102, 2019.
[49] Yue Yu, Rongzhi Zhang, Ran Xu, Jieyu Zhang, Jiaming Shen, and Chao Zhang. Cold-start data selection for few-shot language model fine-tuning: A prompt-based uncertainty propagation approach. arXiv preprint arXiv:2209. 22990, 2022.
[50] Michelle Yuan, Hsuan-Ties Lin, and Jordan L. Boyd-Graber. Cold-start active learning through self-supervised language modeling. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 7935-7948. Association for Computational Linguistics, 2020.
[51] Bowen Zhang, Yidong Wang. Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting supersupe learning with curriculum pseudo labeling. CoRR, abs/2110.08220 2021.
[52] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 107-115, 2021.
[53] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unrea- sonable effectiveness of deep features perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 586-593 2018.
[54] Fedor Zhdanov. Diverse mini-batch active learning. arXiv preprint arviv 00..9011595444 2019.
[55] Yu Zhu, Jinghao Lin, Shibi He, Beidou Wang, Ziyu Guan, Haifeng Liu, and Deng Cai. Address- ing the item cold-start problem by attribute-driven active learning. IEEE Trans. Knowl. Data Eng., 32(4):631 1--33-1-6600 664,, 2020. doi: 10. 10.1099/TKDE..2192299..
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Throughout the entire paper.
(c) Did you discuss any potential negative societal impacts of your work? [No] Irrelevant for this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) Section 2.1
(b) Did you include complete proofs of all theoretical results? [Yes] Section 2, and App. B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes]] We included the necessary information for reproducibility. Furthermore, the code will published upon acceptance.
(b) Did you specify all the training details (c.g.. data splits, hyper- paperr-arameters how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]] 4.1
(b) Did you mention the license of the assets? [Yes] All assets are publicly available.
(c) Did you include any assets either in the supplemental material
URL? [No]
(d) Did you discuss whether and how consent
obtained from people whose data you's 're
using/curating? [Yes] The data is publicly available.
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] Irrelevant.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "ImM5Hh8Rlr5", "reviewer": "Reviewer_eB6a", "summary": "This work introduces a new active learning algorithm for the low-budget regime. The main idea is to maximize probability coverage. The method is demonstrated in both low-budget and high-budget regimes. Moreover, the author also conducts experiments on fully/semi-supervised settings to demonstrate the effectiveness of the method.", "questions": "1. Please illustrate the data selection process with the proposed method. Using the feature of each data point or just the RGB image?  What are the points of the graph in the specific experiment?\n2. The building process of the graph and data selection is time-consuming. Please elaborate on the cost of these two processes.\n3. Please conduct experiments on a larger dataset or other tasks to demonstrate the method, especially for realistic applications. Like the full ImageNet or detection on the COCO dataset.\n4. Comparing Fig.3(a) of this work with Fig.4(a) of TypiClust, the performance of TypiClust reported in this paper is lower than the result in TypiClust. Please clarify the difference between these two curves. Compared with the performance reported in TypiClust Fig.4(a), the improvement is marginal.\n\nI would like to change the score if the concerns could be resolved in the rebuttal.", "limitations": "None", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n- The task is important and fundamental in the research community.\n- The low-budget regime is challenging for the realistic scenario.\n- The experiments seem extensive and well-designed.\n\nCons:\n- The training details are missing and making it difficult to follow.\n- The experiments are only conducted in a small dataset.\n- The comparison with TypiClust is confusing.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EYqg16EFMg", "reviewer": "Reviewer_G2iF", "summary": "The authors propose Max Probability Cover which is the optimal strategy for 1-NN model in that it minimizes an upper bound on their generalization error.\nAs a data distribution is not known in practice, they use empirical data distribution which converts Max Probability Cover to Max Coverage.\nTo work around NP-hard nature of Max Coverage, they propose a greedy algorithm for the Max Coverage named ProbCover.\nFor 1-NN model, Max Probability Cover and Coreset are in “dual” relationship in that Max Probability Cover seek to maximize the coverage for a fixed \\delta whereas Coreset seek to minimize \\delta for the fixed coverage to 1.\nIn the low budget regime where the budget is not enough to cover the unlabeled set, the proposed ProbCover is effective than the existing AL methods most of which are designed for high budget regime. \nThe authors demonstrate it using 3 different frameworks compared to 9 different baseline AL models.\n", "questions": "1. As discussed in Sec 3, the authors mentioned that their approach relies on the existence of a good embedding space. In Sec 4.3, although the authors demonstrated that being in a bad embedding space indeed makes the performance worse, I am not convinced that ResNet-18 trained on few hundreds of images would provide good representations for high dimensional inputs like images. \nIt seems like being in the low budget regime and being in a good embedding space are controversial for over-parameterized neural networks. So, I think either the statement in Sec 3 is wrong or somehow ResNet-18 is in a good embedding space, which I don’t think is clearly demonstrated or justified. Could the authors elaborate it?\n\n2. The authors clearly specify that the proposed method is for low budget regime. However, in practice, the budget $b$ would increase as time goes and so does the covered region. Then, there must be a point where a given problem transits from low budget regime to high budget regime. In that case, what do the authors think would be an efficient way (measurement) to detect the transit? ", "limitations": "Limitations have been mentioned throughout the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n1. This works is one of the first few works addressing the low budget regime problem in AL.\n2. It theoretically demonstrates the close relationship (loose duality) between Max Probability Cover and Coreset in 1-NN model case. \n3. Hyperparameter tuning step is often ignored in AL but the authors address it (in this case \\delta) in a reasonable way.\n\n\nWeakness\n1. The theoretical analysis is based on 1-NN model, which is not strong enough in practice. Also, there is a gap between 1-NN model and deep neural networks so there is a limitation of extending the theoretical results in Sec 2 to general architectures.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-QaTSRLgEmw", "reviewer": "Reviewer_cppJ", "summary": "This paper focuses on low-budget active learning tasks. The proposed method attempts to model the problem as Max Probability Cover question. As Max Coverage is known to be NP-hard problem, the author then adapts a greedy algorithm for subset selection for annotation through covering lens. The improvement of the proposed method over the baselines is shown in supervised and semi-supervised frameworks across different datasets", "questions": "Why Max Coverage's objective is a submodular monotone function? Need a reference here.\n\nThe current greedy algorithm can not guarantee the optimality of Max coverage, the author may explore or discuss a better way to achieve optimal.", "limitations": "Adequately addressed the limitations and potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The idea of seeking maximize Probability Coverage for low budget AL is straightforward and the author gives theoretical proof for this.\n\n2. It is interesting to treat Max Probability Cover and Coreset as dual problems.\n\n3. Most of this paper is clear for practice and the insight for model design is well illustrated.\n\n4. The improvement of the proposed method over the current state-of-the-art methods looks promising in low budget AL setting.\n\nWeaknesses:\n\n1. The greedy algorithm can not guarantee the optimality of Max coverage. Therefore, the sampling solution obtained by the greedy algorithm is hard to be optimal. \n\n2. Missing reference and comparison with ICML'22 Low Budget Active Learning via Wasserstein Distance: An Integer Programming Approach\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept