Least Probable Disagreement Region for Active Learning
Authors: Seong Jin Cho
Gwangsu Kim
Chang D. Yoo
Venue:  (2021)
Keywords: active learning
uncertainty sampling
disagreement region
variation ratio
deep learning
distance
decision boundary

Abstract: Active learning strategy to query unlabeled samples nearer the estimated decision boundary at each step has been known to be effective when the distance from the sample data to the decision boundary can be explicitly evaluated; however, in numerous cases in machine learning, especially when it involves deep learning, conventional distance such as the $\ell_p$ from sample to decision boundary is not readily measurable. This paper defines a theoretical distance of unlabeled sample to the decision boundary as the least probable disagreement region (LPDR) containing the unlabeled sample, and it discusses how this theoretical distance can be empirically evaluated with a lower order of time complexity. Monte Carlo sampling of the hypothesis is performed in approximating the theoretically defined distance. Experimental results on various datasets show that the proposed algorithm consistently outperforms all other high performing uncertainty based active learning algorithms and leads to state-of-the-art active learning performance on CIFAR10, CIFAR100, Tiny ImageNet and Food101 datasets. Only the proposed algorithm outperforms random sampling on CIFAR100 dataset using K-CNN while all other algorithms fail to do so.

Under review as a conference paper at ICLR 2021
LEAST PROBABLE DISAGREEMENT REGION FOR ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Active learning strategy query unlabeled samples nearer the estimated decision boundary at each step has been known to be effective when the distance from the sample data the decision boundary can be explicitly evaluated; however, in nu- merous cases in machine learning, especially when it involves deep learning, con- ventional distance such as the lp from sample to decision boundary is not readily measurable. This paper defines theoretical distance of unlabeled sample to the decision boundary as the least probable disagreement region (LPDR) containing the unlabeled sample, and it discusses how this theoretical distance can be empir- ically evaluated with a lower order of time complexity. Monte Carlo sampling the hypothesis is performed in approximating the theoretically defined distance. Experimental results on various datasets show that the proposed algorithm con- sistently outperforms all other high performing uncertainty based active learning algorithms and leads to state-of-the-art active learning performance on CIFAR 10, CIFARI00, Tiny ImageNet and Food101 datasets. Only the proposed algorithm outperforms random sampling on CIFAR 100 dataset using K-CNN while all other algorithms fail to do so.
INTRODUCTION
Active learning (Cohn et al. 1996) is a subfield of machine learning to attain data efficiency with fewer labeled training data when it allowed to choose the training data from which to learn. For many real-world learning problems, large collections of unlabeled samples is assumed available, and based on certain query strategy, the label of the most informative data iteratively queried to an oracle to be used in retraining the model (Bouneffouf et al. 2014 Roy & McCallum, 2001 [Sener Savarese 20176; Settles et al.) 20088] Sinha et al., 2019] Sener Savarese] [2017a] Pinsler al. 2019 Shi & Yu 2019: Gudovskiy et al. 2020 Active learning attempts to achieve high accuracy
using as few labeled samples as possible
Settles 2009).
Of the possible query strategies, uncertainty-bant sampling (Culotta & McCallum 2005 Scheffer (ct al. (200T] Mussmann & Liang 2018), which enhances the current model by labeling unlabeled samples that are difficult for the model to predict, is a simple strategy commonly used in pool-based active learning (Lewis & Gale 1994). Nevertheless, many existing uncertainty-bart based algorithms have their own limitations. Entropy (Shannon) 1948) based uncertainty sampling can query unla- beled samples near the decision boundary for binary classification, but it does not perform well in multiclass classification as entropy does equate well with the distance boundary (Joshi et al.] 2009). Another approach based on MC-dropout sampling (Gal et al.) 2017) which uses a mutual information based BALD (Houlsby et al. (01I)> as an uncertainty measure identifies unlabeled samples that are individually informative. This approach, however, is not neces- sarily informative when it is jointly considered with other samples for label acquisition. To address this problem, BatchBALD (Kirsch et al., 2019) is introduced. However, BatchBALD computes, theoretically, all possible joint mutual information
complex decision
batch, and infeasible for large query size. The ensemble method (Beluch et al./ 2018), one of the query by committee (QBC) algorithm (Se- ung et al. 1992), has been shown to perform well in many cases. The fundamental premise behind the QBC is minimizing the version space (Mitchel] 1982., which is the set of hypotheses that are consistent with labeled samples. However, the ensemble method requires high computation load because all networks that make up the ensemble must be trained.

---

Under review as a conference paper at ICLR 2021
This paper defines theoretical distance referred to the least probable disagreement region (LPDR) from sample to the estimated decision boundary, and in each step of active learning. labels of unlabeled samples nearest to the decision boundary in terms of LPDR for retraining the classifier to improve accuracy of the estimated decision boundary. is generally understood that labels samples near the decision boundary the most informative the samples are uncertain. Indeed in [alccan et al. (2007). selecting unlabeled samples with the smallest margin the linear decision boundary and thereby minimal certainty attains exponential improvement over random sampling in terms of sample complexity. In deep learning, it is difficult to identify samples nearest the decision boundary as sample distance decision boundary is difficult to evaluate. An adversarial approach (Ducoffe & Precioso) 2018) to approximate the sample distance to decision boundary has been studied but this method does not show preservation of the order of the sample distance and requires considerable computation in obtaining the distance.
obtained to be used
DISTANCE: LEAST PROBABLE DISAGREEMENT REGION (LPDR)
This paper proposes an algorithm for selecting unlabeled data that are close to the decision boundary which can not be explicitly defined in many of cases.
Let X, y. H. and be the instance space, the label space, the set of hypotheses h x - y and the joint distribution over (z, y) E X' x V. The distance between two hypotheses and h is defined as the probability of the disagreement region for h and h. This distance was originally defined in Hanneke et al. (2014) and Hsu (2010):
p(h, h) = P>)((( + h(X)).
(1)
This paper defines the sample distance d of x to the hypothesis E H. based on as the least probable disagreement region (LPDR) that contains æ:
d(w,h)== = inf
((h,h)
hEM((,,))
where M(x, h) = {h E H M(x) + +(xx)}
Figure D shows example of LPDR. Let's define
H (x', ha)
H = [hg : hz(2)) = 1[ > 8} on input x sam- pled from uniform distribution D U 1] where [[-] is an indicator function. Suppose x = 3p and
ha
h
h1
H
h h= ha E H when < xp. Here, H( ha) con- sists of all hypotheses whose prediction on 2o is in disagreement with hg (xx)
0
1
1, i.e., H( ha)
{hs E hx(2z) = 0} = (he E H > 20). Then, the LPDR between Ho and has d(zo. ha) To a as the infimum of the distance between ha and ha E H(xo, ha) is p(ha, Rzo) = 20
Figure 1: An example of LPDR between a
sample x = Tp and a hypothesis h = he in binary classification using the he(x) I/r > 0] on input ~ U].
Here, the sample distribution D is unknown, and H(xx, hi) may be uncountably infinite. Therefore, a systematic and empirical method for evaluating the distance is required. One might the procedure below: Sample hypotheses sets H'' = {N' p(h, h²) I p'} in terms of p', and perform grid search to determine the smallest p' such that there exists h' E H' satisfying h(x) * h'(x)) for a given æ. Sampling the hypotheses within the ball can be performed by sampling the corresponding param- eters with the assumption that the expected hypothesis distance is monotonically increasing for the expected distance between the corresponding parameters (see Assumption 1). This scheme is based on performing grid search on p' and is therefore computationally inefficient. However, unlabeled samples can be ordered according to without grid search with the assumption that there exists H! such that variation ratio V(x) = (()) /176'| and d(x:, h) have strong negative correlation where p(a) max, ΣvEW Ilh((=) (see Assumption 2).
2

---

Under review as a conference paper at ICLR 2021
MRIST OFARLO
crdered unlabeled index index.
2300
0.6
1350
0.6
variation ratlo
imagehot
Food203
2000
0.4
HAM10000
750
04
0.2
0.0
loglo)
log(o)
Figure 2: Empirical validation of Assumption 1. Left figure: Relationship between approximated
hypothesis distance and step O. Hypothesis distance is almost linearly proportional to log(or) in the ascension. Right figure: Relationship between variation ratio and a (MNIST). Sample distance to the decision boundary can be expressed as which the variation ratio is not zero for the first time (white arrow). The unlabeled samples are ordered in terms of LPDR.
MNIST (corr. 0.94 log(o)=-5.0)
0.7
SIEST
UPORIU
COTT. between d and
-0.1
ENNSTT
SUNN
OFFRROO SECARI
102
Fond107
rank
300
100 202
kug(o)
rank
Left figure: Spearman's rank correlation coefficient between LPDR and the variation ratio in terms of a showing that there exists a such that LPDR and the variation ratio have strong rank correlation. Right figure: An example of strong negative correlation between both ranks when log(o) 5.00. Samples with increasing LPDR or variation ratio are ranked from high to low.
Figure 3: Empirical validation of Assumption 2.
Assumption 1. The expected distance between and randomly sampled h is monotonically in- creasing in the expected distance between the corresponding vo and w, i.e., Bl]lu will w s El]l@: - w2ll | úd) implies that Elp(h, h1) i]] s Rlp(h,, h2) h] where i, un and w2 are the parameters pertaining to h hy and l2 respectively.
Assumption 2. There exists a hypothesis set H'' sampled around having the property that large variation ratio for a given sample data implies small sample distance to h with high probability, i.e. there exists H'' such that V (xx1) 2 (xx2) implies that d(xx1. h) S d(x2,,) fi) with high probability.
3 EMPIRICAL STUDIES OF LPDR
3.1 HYPOTHESES AND PARAMETERS IN DEEP NETWORKS: ASSUMPTION
The distance between two hypotheses can approximated by vectors of the predicted labels on random samples by the hypotheses:
m T (()())) # M(x:(1))
(h, h) =o po(h,,)) h)) m
where (+) is the ,th sample for [m]. The is sampled by sampling model parameter w ((w Io?) where ú is the model parameter of h, and the expectation distances between w and i depends σ. The Pe is obtained by the average of 100 times for fixed a. The left-hand side of Figure showws the relationship between P. and a on various datasets and deep networks. The Pe: increases almost monotonically increases. This implies that the order is preserved between
3

---

Under review as a conference paper at ICLR 2021
the and Pe- Furthermore, the Pe is almost linearly proportional to log(a) in the ascension of the graph, i.c. a x e for some 3 >> O. The right-hand side of Figure 2howss V with respect to a for each unlabeled sample MNIST. The sample distance to the deciston boundary can be expressed as a at which the variation ratio is not zero for the first time (white arrow), where the indices of unlabeled samples in y-axis
ordered by LPDR. The variation ratio increases as the increases, and it is expected that the data point with short distance has the large variation ratio compared to the data point with long distance on certain range of a.
3.2 LPDR VS VARIATION RATIO: ASSUMPTION
The left-hand side of Figure shows Spearman's rank correlation coefficient (Spearmani 1904) between LPDR and the variation ratio with respect to a. The correlation is calculated using only unlabeled samples whose variation ratio is not O. The strong rank correlation is verified when the has the appropriate value. Too larger value of a generates hypotheses too far away from h, which is not helpful to measure the distance. The right-hand side of Figure 3 shows an example of a (log(o) = -5.0) which makes LPDR and the variation ratio have a strong negative correlation on MNIST, that is, the data point with larger variation is closer to the decision boundary. Results for various datasets and networks are presented in Appendix C.
The time complexity is discussed to validate the efficiency of using variation ratio. Let m, N and ni be the unlabeled sample size, [7L| and the number of grid for a respectively. Ordering unlabeled samples in terms of LPDR by grid search with respect to requires the time complexity of m x N x Yh (see the right-hand side of Figure 2}. However, using variation ratio for ordering unlabeled samples reduces the time complexity m x N. In the case of nu = cN for some e 0, then the time complexity can be reduced from 2m to O(mN).
4 ALGORITHM FOR LPDR
4.1 FRAMEWORK
Let Le and Ue be the labeled and unlabeled samples step t. At step f, LPDR trains model parameters wZ using labeled samples L,, and constructs H' by sampling the model parameters w', NNw, Io²) for n [N]. Then, LPDR queries the top q unlabeled samples having highest variation ratio from the pool data P. C Ui of size m.
4.2 CONSTRUCTION OF SAMPLED HYPOTHESIS SET
is important to set an appropriate a when constructing H'' as variation ratios goes to 0 with de- creasing (see the right-hand side of Figure 2 and the rank correlation goes zero with increasing (see the left-hand side of Figure B. Theoretically, let's consider the binary classification with logistic regression where the predieted label is defined as y = sgn(x" w) and sup ||~|||> 8o. Then the following theorem holds and the proof is described in Appendix A.
Theorem 1. Suppose that w', for n 1,...,N N are generated with the variance of a². For all x, the followings hold: 1) As N + oc, 1 1- 1--f
f(x) /N goes to O in probability as o² goes to 0, 2) As N 3c. 1- /N goes to 1/2 in probability for binary classification using logistic regression as 2² goes to oc.
The implication of Theorem 1 is that when a is small or too large, would be difficult compare the sample distances of unlabeled samples. In this active learning task, at least most informative unlabeled samples must be identified. To meet this condition, is reasonable to set pl denoted the Algorithm a p² = =/mm, which is not very small and is less than 1/2 in general, for N hypotheses.
This can be attained by updating o'1 as 0'41 -', -'e'--'e',-p")) where 3 > O (see Appendix D). The Figure 10 in Appendix E shows the final test accuracy with respect to target P%, on MNIST dataset. The LPDR performs best when the target p', is roughly p² In addition, the range of target ph,, associated with the best performance, is wide: thus, LPDR is relatively robust against target P',- Furthermore, L.DR is robust against hyperparameters N and sampling layers (see Appendix F).
4

---

Under review as a conference paper at ICLR 2021
Algorithm Least Probable Disagree Region (LPDR)
Input:
Co. Mn Initial labeled and unlaheled samples
m, q: Size of pool data and number of queries
a. Initial variance for sampling
p Target hypothesis distance (= q/m)
Procedure:
1: for step 0. 11
2: Train parameters ú. with Le, then evaluate its empirical error é on L
3:
0t +
4:
for =.2......,
5:
Sample parameters w², (N Io for i1,
6: Compute Inn = e -(', -Ee)+ where enn is empirical emorr of wa on Lt.
7: Compute P/, = pe(h,,
8: Update 2/11 = o' 24 -BPpn-p") where B >
9:
end for
10:
a++1 Compute V. (xx = 1 1 fw E Yn where fm max. En= 7al (x) =c]
IN
11:
12: Get I arg maX /1]|= Enez Vi (x( where Ip. (j:000) E EP, Su6
13:
Update C.+1 = Li U ( ,,(1)) Jeez and U441 = Ui (x()),
end for
Meanwhile, the efficiency of querying samples in the disagreement region of the version space is well known both theoretically (Hanneke et al. 2014) and empirically (Beluch et al. 2018). When the trained hypothesis he is in the version space, the sampled hypotheses h2 are the version space with high probability, but there are cases where they are outside the version space (see Appendix G).
Thus, LPDR gives weight "n on the prediction of sampled hypothesis hi where 7n. = (<(--E))
function of é err (h+) and e' crrz, (M2)). Here, (-)+ is max(0, + and err is the empirical error of on Then, LPDR uses weighted variation ratio Vi as a function of the weighted frequency of the modal class fi defined below:
(x = Σ
(4)
where ((0 max. EN 7xd [,,, (x:1)) = and (1) Pt U..
If H' subset of the version space in realizable case, the sample complexity of LPDR follows Hanneke's theorem (Hanneke et al. 2014). Let A be the sample complexity defined as the smallest integer such that for all 2 f., err(he) I e where err(h) = (D( * Y] with probability at least 1 - 8. Then, LPDR achieves sample complexity A such that, for D in the realizable case, Ve, (0, 1),
8,, (Dloge log [log(1/c) ()o3(1/o)) llo
1
where D and & the VC-dimension of H. and the disagree coefficient with respect H. and D.
When = O(1), in terms of e, the number of labeled samples required by LPDR is just (llgg(1/e) log log(1/e)), while the number of labeled samples by passive learning is M(1/e). Therefore, in this case, LPDR provides an exponential improvement over passive learning in sample complexity (Hsu 2010
EXPERIMENTS
This section discusses experimental results benchmark datasets: MNIST (eeCun al. 1998),
CIFAR1O (Krizhessky et al., 2009). SVHN (Netzer et al. 2019). EMNIST Cohen et al.
2017:
CIFAR100 100 (Krizhevsky et al. 2009), Tiny ImageNet (subset of the ILSVRC dataset containing
5

---

Under review as a conference paper at ICLR 2021
Table 1: Experimental settings for comparing the performance various datasets are summarized. Epochs is the maximum number of training epochs. Data size denotes the sizes of datasets for training / validation test. Acquisition size denotes the number of samples for the initial model
number of samples acquired in each step (from the number of samples in the pool data) - Maximum number of samples acquired during training.
size
Dutaset
Model
Epochs
Acquisition size
val test
MNIST
S-CNN
55,000 5,000 10,000
+20 (2K)
1,0220
CIFARIO
K-CNN
150
45,000 5,000 10,000
200
+100 (2K)
10,200
SVHN
K-CNN
150
68,257 / 5,000 26,032
200
+100 (2K)
10.200
EMNIST
K-CNN
100
75,000 / 5,000 10,000
235
+150 (2K)
+ 15,235
CIFARI00
K-CNN
150
45,000 / 5,000 10,000
2,000
+500 (5K)
+ -7,0000
CIFARI00
WRN-16-8
100
45,000 5,000 10,000
5,000
+2,000 (10K)
+ 25,000
Tiny ImageNet
WRN-16-8
200
90,000
10,000 10,000
10,000
+5,000 (20K)
+ 50,000
Food101
WRN-16-3
200
60,600 15,150 25,250
6,000
+3,000 (15K)
30,000
HAM10000
WRN-16-8
7.015 1,500 1,500
500
+300
3,500
200 categories rather than the usual 1000 categories; Russakovsky al. 2015). Food101 (Bossard
et al. 2014) and HAM10000 (Tschandl et al. 2018) datasets. For fair comparison with other ac- tive learning algorithms, simple two layered CNN, referred as 'S-CNN' (Chollet et al. 2015)
used for MNIST and four layered CNN, referred to 'K-CNN' (Chollet et al. 2015) used for
CIFARIO, SVHN, EMNIST and CIFARI00, Additionally, Wide-ResNet (WRN- 16-8; Zagoruyko
& Komodaaii 2016) is used for CIFARIOO, Tiny ImageNet, Food101 and HAM10000.
7 magnified plots of test accuracy to accentuate the difference in performance among different methods: initial labeled sample sizes not shown in the figures. Figures that include initial labeled sample size are presented in Appendix H.
5.1 EXPERIMENTAL SETTINGS
Experimental settings regarding total number epochs, data size and acquisition size are summa- rized in Table D and other details concerning the model, optimizer, batch size, learning rate and hyperparameters are presented in Appendix B.
5.2 RESULTS FOR MNIST, CIFARIO, SVHN AND EMNIST
number experiments are conducted to compare performance of LPDR with other high perform- ing uncertainty based active learning algorithms on 8 datasets. Figure 4 shows the test accuracy with respect to the number of labeled samples on MNIST, CIFARIO, SVHN and EMNIST datasets. Each algorithm is denoted such 'LPDR': the proposed algorithm, 'Random': random sampling, 'Entropy': entropy based uncertainty sampling, 'MC-BALD': MC dropout sampling using BALD, 'MC-VarR': MC dropout sampling using variation ratio (Ducoffe & Precioso 2015) and 'ENS- VarR': ensemble method. Overall, LPDR either performs best or comparable with all other algo- rithms. Its performance is consistent regardless of the benchmark datasets. In the early step, LPDR significantly outperforms all other algorithms on MNIST and CIFARI0 datasets. Of all the algo- rithms compared, Entropy performed the worst. MC-BALD performed well only on SVHN dataset: it seems that the performance of BALD is highly dependent on the dataset. With the query size set to 1, L.DR outperforms BatchBALD on MNIST dataset (see Appendix 1). Although MC-Vark and ENS-VarR are based on different sampling methods, both perform similarily-both outperforming all others on EMNIST dataset, while showing a significant drop in performance compared to LPDR on SVHN and CIFARIO datasets. It is observed that the performances of other algorithms have a relatively strong data dependency compared to LPDR. On CIFARIO dataset, the performances of no better than that of Random, and Entropy and MC-BALD have lower
MarR and ENS- performance than Random. These results can be attributed to the low network capacity compared to the data complexity. This issue will be discussed in next section.

---

Under review as a conference paper at ICLR 2021
MNIST (c)=20)
CIFARIC (co=200)
Lest accuracy 150
105t accuracy (50
UIOK
PC-JALD
LPDR
MC-AAL
Random
Bandom
MC-vart
Entropy
E46 Vark
Entropy
EVS 2:5-2a19
samples
label sa mplles
SVHN (Cg=200)
FMNIST (cc=235)
test acuraay (%)
te5t accuracy (%.
81-
1988
Ne--0i h
Random
PC Vo.1
Randbm
vars
4200
0000
80000
10000
* of labeled samples
of label ledi 5a mamless
Figure 4: The performance comparison of LPDR with the uncertainty based active learning algo- rithms on MNIST, CIFARIO, SVHN and EMNIST datasets (Random: random sampling, Entropy: entropy based uncertainty sampling, MC-BALD: MC dropout sampling with BALD, MarVarR: MC dropout sampling with variation ratio, ENS- VarR: ensemble network with variation ratio). Over- all, LPDR consistently either performs best comparable with all other algorithms regardless of dataset. The performance all algorithms except LPDR tend to be data dependent.
CIFARIOO (KCNN; (Co-2000)
CIFAR1OC (WRN; 5500))
56
54-
1e5t eccurscy (%))
Kandom
handon
Entmpy
Entropy
Vart
12000
125.00
15000
17500
20000
22500
25020
12000
14000
16:00
1,00000
70000
27000
74000
labeled samples
of labe samples
Figure 5: Performance comparison with respect to the network capacity on CIFAR100 dataset. The performances of all algorithms except LPDR much worse than that of Random when using K- CNN, which has a relatively smaller network capacity than that of WRN-16-8. LPDR is able to perform consistently better than Random regardless of the network capacity.
5.3 RESULTS FOR CIFARI00 WITH K-CNN AND WIDE-RESNER
In order to compare the performance of the algorithms with respect to the network capacity, exper- iments are conducted using networks of different capacity but on the same dataset. [ the results of test accuracy with respect to the number of labeled samples on CIFAR100 dataset with K-CNN and WRN-16-8. The left-hand figure is the results of using K-CNN, which has a relatively smaller network capacity than that of WRN-16-8 With the exception of LPDR, the performances of all algorithms are much worse than that of Random. The right-hand figure is the result of using WRN-16-8, which has relatively larger network capacity. In contrast to the results for K-CNN, most algorithms outperform Random. With a large network capacity, the performance gap between LPDR and the other algorithms is reduced, but LPDR still outperforms others. LPDR is able to perform consistently better than Random regardless of the network capacity, and seems to be particularly effective with low capacity networks.

---

Under review as a conference paper at ICLR 2021
T my ImageNet (Co =1000)
Food10: (4g=6000)
(50
40.0
47.5
40.0
Lest
30.0
W--Bol
27.5
NC-ANL
Hancom
Vo's
Kandom
PhS-Nemf
Estropy
PN4S-Vrrt
38.5
15000
20000
23000
30000
35000
40000
45000
50000
12009
16000
10000 18000 20003 22000 20000
20000
28000 50000
# of Tabe led samples
& of labeled samples
Figure 6: The performance comparison on Tiny ImageNet and Food101 datasets with WRN-16-8. LPDR outperforms all other algorithms in more difficult tasks.
5.4 RESULTS FOR TINY IMAGENET AND FOOD101
Experiments on more difficult task are conducted. Figure O shows test accuracy with respect to the number of labeled samples on Tiny ImageNet and Food101 datasets with WRN-16-8. Tiny ImageNet and Food101 are considered to be more difficult than CIFARI00. Even more difficult tasks, LPDR outperforms all other algorithms.
5.5 RESULTS FOR HAM10000
Additional experiments conducted to compare the performance of the algorithms on imbalanced HAM10000 dataset with WRN-16-8. Figure shows the results of the test accuracy with respect to the number of labeled samples. The L.DR outper- forms all other algorithms compared. Figure [5 in Appendix shows the results AUC with respect to the number of labeled samples. The LPDR per- forms comparable with all other algorithms.
HAM10000 (Cp-500)
70
Handom
05. v3m
Enunpy
1AC-Vart
70
To up the comparing algorithms across all perimental settings and repetitions, rank and Dolan- More curves presented in Appendix K. The LPDR consistently achieves top rank for all steps and significantly outperforms the other algorithms all experimental settings.
samples
Figure 7: The performance comparison HAM10000 dataset with WRN-16-8. LPDR outperforms all other algorithms on imbal- anced dataset.
6 RELATED WORK
Other than uncertainty-based sampling framework (Culotta & McCallum 2005 Schefter et al.
2001 Mussmann & Liang 2018 Lewis & Gale, 1994 Gal et | [017]] Kirsch al. [019) Beluch
et al. 2018) for active learning, decision-theoretic framework based methods such as expected model change (Settles et al. 2008) have certain relevance the proposed L.DRR as unlabeled samples nearer the decision boundary which LPDR is attempting to identify have larger gradients leading larger model change. Recently, adversarial approaches are proposed to discriminate labeled and unlabeled samples (Gissin & Shalev-Shward after performing adversarial learning, any unlabeled samples that is most confidently predicted as unlabeled is queried and used to retrain the network. Here adversarial learning is used to indirectly identify sample near the decision boundary.
2019, Sinha et al. 2019: Zhang et al. 22020), and
7 CONCLUSION
This paper defines a thcoretical distance unlabeled sample to the decision boundary referred to the least probable disagreement region (L.DR) containing the unlabeled sample for active learn-
8

---

Under review as a conference paper at ICLR 2021
ing. LPDR can be evaluated empirically with low computational load by making two assumptions regarding parameters of the hypothesis space, variation ratio and the LPDR. The two assumptions empirically verified.
Experimental results on various datasets show that LPDR consistently outperforms all other high performing uncertainty based active learning algorithms and leads state-of-the-an active learning performance on CIFAR10 10, CIFARIOG 100, Tiny ImageNet, and Food101 datasets. In addition, LPDR is able to perform consistently better than random sampling regardless of the network capacity while all other algorithms compared fail to do so.
LPDR is simple enough be applied various classification tasks with deep networks: the im- plementation requires only sampling subset of parameters (parameters in the last FC layer of the deep network). Additionally, LPDR capable of quick and reliable performance in a variety of dif- ferent settings with only computational load that is not much higher than that of other uncertainty sampling methods. In conclusion, LPDR is an effective uncertainty based sampling algorithm in pool-based active learning.
REFERENCES
Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference on Computational Learning Theory, pp. 35-50. Springer, 2007.
William Beluch, Tim Genewein, Andreas Nürnberger, and M Köhler. The power of ensembles for active learning in image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9368 19677,37,, 2018.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food- mining discriminative com- ponents with random forests. In European Conference on Computer Vision, 2014.
Djallel Bouneffouf, Romain Laroche, Tanguy Urvoy, Raphael Féraud, and Robin Allesiardo. Con- textual bandit for active learning: Active thompson sampling. In International Conference on Neural Information Processing, pp. 405-412. Springer, 2014.
François Chollet et al. Keras. https:
2015.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 International Joint Conference on Neural Networks (JCNNN, pp- 2921-2926. IEEE, 2017.
David A Cohn, Zoubin Ghahramani, and Michael I Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4: 129-145, 1996.
Aron Culotta and Andrew McCallum. Reducing labeling effort for structured prediction tasks. In AAAI, volume 5, pp. 746-751, 2005.
Elizabeth D Dolan and Jorge Moré. Benchmarking optimization software with performance pro- files. Mathematical programming, 91(2):201-213, 2002.
Melanie Ducoffe and Frederic Precioso. Qbdc: query by dropout committee for training deep su- 2015.
pervised architecture. arXiv preprint
Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: margin based approach. arXiv preprint trXiv:1802.09844) 2018.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference on Machine Saaming-Volume 70, pp. 1183- 1192. JMLR. org, 2017.
Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv:1907.06347 2019.
arv preprint
Denis Gudovskiy, Alec Hodgkinson, Takuya Yamaguchi, and Sotaro Tsukizawa. Deep active learning for biased datasets via fisher kernel self--uupev In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9041-9049) 2020.

---

Under review as a conference paper at ICLR 2021
Steve Hanneke et al. Theory of disagreement- basse active learning. Foundations and Trends in Machine Learning, 7(2-3):131-23 2014.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani. and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:1112.55: 2011.
Daniel Joseph Hsu. Algorithms for active learning. PhD thesis, UC San Diego, 2010.
Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos, Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2372- 2379. IEEE, 2009.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acqui- sition for deep bayesian active learning. In Advances in Neural Information Processing Systems, pp. 7024-7035, 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and Lffar-100 datasets.
https:
cs. http::/s.tooott..eeee//////////e htmm 2009.
Yann LeCun, Corinna Cortes, and Christopher JC Burges. The mnist database of handwritten digits.
wtt.d///eccccoooo//////ooooo..// mnist. 1998.
David D Lewis and William A Gale. A sequential algorithm for training text classifiers. In SIGIR 994, pp. 3-12. Springer, 1994.
Tom M Mitchell. Generalization search. Artificial intelligence, 18(2):203-22) 226, 1982.
Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Advances in Neural Information Processing Systems, pp. 6955-6964, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and A Ng. The street view house numbers (svhn) dataset, 2019.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Looate Bayesian batch active learning sparse subset approximation. Processing Systems, pp. 6359-6370, 2019.
In Advances in Neural Information
Nicholas Roy and Andrew McCallum. Toward optimal active learning through monte carlo estima- tion of error reduction. ICML, Williamstown, pp. 448,, 2001.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255 2015.
Tobias Scheffer, Christian Decomain, and Stefan Wrobel. Active hidden markov models for in- formation extraction. In International Symposium on Intelligent Data Analysis, pp. 309-318.
Springer, 2001.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint 170.000478000889 201
Ozan Sener and Silvio Savarese. A geometric approach to active learning for convolutional neural networks. arXiv preprint arXiv, 1708:1, 2017b.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Maddisn Department of Computer Sciences, 2009.
Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. In Advances in neural information processing systems, pp. 1289-1296. 2008.
Sebastian Scung, Manfred Opper, and Haim Sompolinsky. Query by committee. Proceedings of the fifth annual workshop Computational learning theory, pp. 287-294, 1992.
10

---

Under review as a conference paper at ICLR 2021
Claude E Shannon. A mathematical theory of communication. Bell system technical journal, 27(3): 379-423, 1948.
Weishi Shi and Qi Yu. Integrating bayesian and discriminative sparse kernel machines for multi- class active learning. In Advances in Neural Information Processing Systems, pp. 2285-2294, 2019.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1972-5981, 2019.
Charles Spearman. "General Intelligence" objectvvely determined and measured. American Journal of Psychology. 15:201-293, 1904.
Philipp Tschandl, Cliff Rosendahl, and Harald Kittler. The ham 10000 dataset, large collection of multi-source dermatoscopic images of common pigmented skin lesions. Scientific data, 5: 180161, 2018.
Sergey Zagoruyko and Nikos Komodakis. wrXiv:1655.07144 2016.
Wide residual networks.
arXiv preprint
Beichen Zhang, Liang Li, Shijie Yang. Shuhui Wang, Zheng-Jun Zha, and Qingming Huang. State- relabeling adversarial active learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8756 8756-8765 8765, 2020.

---

Under review as a conference paper at ICLR 2021
APPENDIX
A PROOF OF THEOREM
Assume that ||abz|| 1 without the loss of generality, and ||:|| # avoid the null case. The
predicted label of by wa, disagrees with that by w if sgu (æ ('', + sgn (x' w:). here, sgn(0) Note that
x z'w,, x + oxTe, e,, where c, (Zn1. Znjui)"
and Zaus are independent random variables from (0 1). The event of (sgn (a! (aTurn)) + sgn (x: T wi.) } equal to that of & U where &2 fa= c 0, 0, th < 0} and &g = fox cn < 0, x w. 2 0}. Thus, the proof has two folds: the cases 1) & and 2) Ez.
In the first fold,
| 2 T tb: 1 ( a ( w))
P[E P Pooxee e |ac [T
where Z ~ (O, 1), 4 is the cumulative distribution function of the normal distribution, and (x. wi) x "w,l///zz// Note that ox
Tx'e', e', (N( o000,)21<113) Consequently, P[E1] < 1/2 due
to (z, w. > 0. Hence, the following
1 N
N Σ
[h(((x) = N1 (2))
goes value greater than 1/2 in probability as N + because Var(fm)) /N) - 0 N Therefore, as + 00, Va, the variation ratio is
fm
Σ
= [2((2 [((c)
( a (a w))
in probability. This due to that (((r) is the frequency of mode class with probability tending to as N + oo. By the smoothness of 4
(x)
m
(0000)
as a² 0
N
and
fm
+ - 2(0)
= as a² + 0o.
N
2
Next, in the second fold,
P [ = |o e', -1 wú = |o||=|| < -10 wr = (- (a, w
Consequently, P(E2 1/2. Hence the following
((a) N
N
Σ
[
[o(x)== -,(())
goes the value greater than 1/2 in probability as oc because Var (m)) /N) - 0 N + 00. Therefore, as N + 0o, Va, the variation ratio is
(x) N
Σ H [mu(())
(x. (0s)
(a wi:)
(1 [2((0)
in probability. This is due to that r((z) is the frequency of mode class with probability tending to N oo. By the smoothness of $
m
+ (000) = as 0² +
N
12

---

Under review as a conference paper at ICLR 2021
and
fm
1
(0)
as
o² 00.
N
2
This completes the proof.
B EXPERIMENTAL SETTINGS
B. DATASETS
MNIST (LeCun et al.) 1998) is dataset of handwritten digits which has a training set of 60, 000 samples and a test set of 10, 000 samples in 10 classes. Each sample is black and white image and 28 X 28 in size.
CIFARIO and CIEARIOO Krizhevsky et al. 2009) are labeled subsets of the 80 million tiny images dataset which have training set of 50, 000 samples and test set of 10, 000 samples in 10 and 100 classes respectively. Each sample a color image and 32 x 32 size.
SVHN Netzer et al. 2019) is real-world digit image dataset which has a training set of 73, 257 samples and a test set of 26, 032 samples in 10 classes. Each sample a color image and 32 x 32 in size.
EMNIST (Cohen et al. 2017) is a dataset of handwritten character digits which has a training set of 80, 000 samples and test set of 10, 000 samples in 47 classes. Each sample is black and white image and 28 x 28 in size.
Tiny ImageNet is subset of the ILSVRC (Russakovsky et al./ 2015) dataset which has 100, 000 samples in 200 classes. Each sample a color image and 64 x 64 in size. In experiments, Tiny ImageNet is split into parts: training set of 90, 000 samples and test set of 10, 000 samples.
Food101 (Bossard et al. 2014) a fine grained dataset which has a training set of 75, 750 samples and test set of 25, 250 samples in 101 classes. Each sample a color image and resized to 75 75.
HAM10000 Tschandl et al. 2018) is a imbalanced dataset which has 10, 015 samples in 7 classes. Each sample is color image and resized to 75 75. In experiments, HAM10000 is split into two parts: training set of 8, 515 samples and test set of 1, 500 samples.
All datasets are used without any preprocessing of images.
B.2 SETTINGS
S-CNN, which is the Keras MNIST CNN implementation (Chollet al. 2015). consists of [3 x x
32 conv -3 x 3 x 64 conv 2 x 2 maxpool dropout (0.25) 128 dense - dropout (0.5) #class dense softmax] layers. K-CNN, which is the Keras CIFAR CNN implementation (Chollet al. 2015). consists of [two 3 x x 32 conv
x 2 maxpool dropout (0.25) two 3 x 3 x 64 conv 2 x maxpool- dropout (0.25) 512 dense dropout (0.5) #class dense softmax] layers. WRN-16-8 is wide residual network that has 16 convolutional layers and a widening factor 8 (Zagoruyko & Komodakis (016). The optimizer, initial learning rate, learning rate schedule and batch size for each experimental setting are described in Table He normal initialization is used for all models. All experiments are run for a fixed number of acquisition steps until a certain amount of training data is labeled. Results are averaged over 5 repetitions. For all datasets, the initial labeled samples for each repetition are randomly sampled according to the distribution of the training set. For MC dropout we use 100 forward passes, and ensemble consists of networks of identical architecture but different random initialization and random batches. For LPDR, we set og = 0.01, 3 = 1, 100 and parameter sampling is applied to the last dense layer of each network.
13

---

Under review as a conference paper at ICLR 2021
Table 2: Settings for Training
Learning Rate Schedule
Dataset
Model
Optimizer
Learning Rate
Batch Size
xdeccy Jepoch schedule]
MNIST
S-CNN
Adam
0.001
32
CIFARIO
K-CNN
Adam
0,0001
64
SVHN
K-CNN
Adam
0.0001
64
EMNIST
K-CNN
Adam
0.0001
64
CIFARI00
K-CNN
Adam
0.0001
CIFARIOO
WRN-16-8
Nesterov
0.05
x0.2 [60, 80]
Tiny ImageNet
WRN-16-8
Nesterov
0.1
x0.2 [60, 120, 160)
128
Food101
WRN-1668
Nesterov
0.1
x0.2 [60, 120, 160)
128
HAM10000
WRN-16-8
Nesterov
0.05
x0.2 [60, 80)
64
C RANK CORRELATION BETWEEN LPDR AND VARIATION RATIO
Figure shows an example of negative Spearman's rank correlation between LPDR and the variation ratio for each experimental setting. Samples with increasing LPDR variation ratio are ranked from high to low. The a is selected to satisfy P/a = =p" q at initial step.
MNIST (cory. -0004 vs kg.0))=5.01
C PARLO tcomr.-00.00 03 vs logid)m=4.55
SVHN (com).m0 95 vs lo.7d))
of
Fant V
CAALOO (sorrom 94 luglo)m-4.71
CIFARDO (cun --0 1..2
250
1300
1us
rork
(ogjotm-41.2)
loglotm-4.2)
teglo/m-2.5)
30.0
10:00
3009
250
<30
-00
2008
25:0
1803
1000
17:30
20:0
12:00
1200
25
Figure 8: An example of negative Spearman's rank correlation between LPDR and the variation ratio for each experimental setting.
D REGULATING P,, BY THE VARIANCE OF SAMPLING
The left-hand side of Figure shows the P/n with respect to the active learning progress. For all experiments, LPDR reliably guides the p to be p" = z//m (MNIST: 0.01, CIFAR10: 0.05, SVHN: 0.05, EMNIST: 0.075, CIFARI00 (KCNN): 0.1, CIFAR100 (WRN): 0.2, Tiny ImageNet: 0.25, Food101: 0.2 and HAM10000: 0. after the initial few steps. The right- side of Figure
14

---

Under review as a conference paper at ICLR 2021
log(o) with respect to the active learning progress. For all experiments, the variance of sampling increases as the labeling proceeds. This is because larger variance is required to make the Pn = =p since unlabeled samples move away from the learned decision boundary from labeled samples due to an increase in network confidence as the number of labeled samples increases.
3/10
EMINST CIFARL OCENNI CIRARLER (HHOO)
Tryy Imagekee
EMAIST CIPARIOC INCRRN CINDKEOG INMMY
Tiry Imaggelle Foont20 MANTLOOGU
2.5
OIAAR1
Food101
OFARIO
HAM330000
SWIM
232
logidt
3.85
2000
percent
Figure 9: The Pl and a with respect to the labeling proceeds for all experimental settings. LPDR reliably guides the pl be the target value by increasing the variance of sampling as the number of labeled samples increases.
E FINAL TEST ACCURACY VS TARGET P'
The Figure 10 shows the final test accuracy with respect to target P/, on MNIST dataset. The results show that at around (= 0.02). it performs the best for q 20 and m 1000. In addition, the range of target pn, associated with the best performance, is wide (0.01 0.1); thus, LPDR is robust against the target P/ the wide range.
t:0
Final (%g
97.5
97.0
85.5
90.0
066
target pl:
Figure 10: The final accuracy with respect to the target P% on MNIST dataset. LPDR performs best in wide range of the target P/
F ROBUSTNESS OF LPDR AGAINST HYPERPARAMETERS
LPDR has four hyperparameters: the initial variance of sampling on: 2) the positive hyperparam- eter for regulating the variance of sampling 93; 3) the number of sampled hypotheses N, and 4) the layer index of the network to which sampling applied. The do has no significant effect on the per- formance of LPDR since a is adaptively regulated based on the p', while sampling the sampled hy- pothesis. Thus, do is not examined detail. Figure TT shows the performance comparison with re- spect to the hyperparameters of LPDR on MNIST and CIFAR10 R datasets. The left figures show that there is no significant difference the performance of LPDR for various datasets. The robustness of LPDR against 3 is based on the sufficient buffer for regulating since the range of target P/, associated with the best performance is wide. The middle figures show that there is no significant difference in the performance of LPDR for various N E {5. 10, 20, 50, 100, 200} on both datasets. The robustness of LPDR against N is based on the sufficient discrimination in the variation ratio for identifying g most informative unlabeled samples with small number of sampled
{0.1, 1, 10) on both
15

---

Under review as a conference paper at ICLR 2021
(Ca-20)
20
60
200
60
800
200
600
100
CIARED (2g=200)
CIFARED (c4-200)
OTARCS (6ym202)
Figure 11: The performance comparison with respect to the hyperparameters of LPDR on MNIST and CIFARIO datasets. LPDR is robust against 3 and N, and has significant performance differ- ence whether the sampling is applied to the parameters of last layer or all layers.
hypotheses by setting pa = q/ m. The right figures show that there no significant difference in the performance of LPDR for the sampling to the parameters of last layer and to the parameters of all layers of the networks on both datasets.
sumpord
LAA EVRUST
CIPAR100 (KCNB)
CIFARIDO (WRM))
U/5 Dis 900 AED EM00
WOB LM00 C400 SAMO CAO 2005
Thny InageMer
Dreems coee
3X2
#c Laieee sargghes
Figure 12:
The empirical errors of the learned and the sampled hypotheses with respect to the acquisition step for all experimental settings. It is observed that the empirical error of the learned hypothesis or the sampled hypothesis is not zero.
G EMPIRICAL ERRORS OF LEARNED AND SAMPLED HYPOTHESES
Figure 12 shows the empirical error of the learned and the sampled hypotheses with respect to the acquisition step for all experimental settings. In many cases, the empirical error of the learned hypothesis becomes zero, thus it is placed in the version space, while the sampled hypothesis is often placed outside the version space, e.g., in SVHN dataset. Even in the cases of EMNIST and CIFAR 100 with K- K-CNN datasets, as the number of labeled samples increases, the empirical error of the learned and the sampled hypothesis increases. To address this situation, L.DR incorporates the
16

---

Under review as a conference paper at ICLR 2021
MKIS 16)
10
SVNN 20
40
MBC
69
2002
4000
1960
20:8
600
4200
8850
$2100
CITARI on OCTANI (rur)
CITARI DO (WRM) (10000))
of libdodd soria
of labeled semples
of s4
Thny Imagehint L6s 10008)
Food10) (Ca $0000
HMVE WWML
10-02
1501 2000 33300 inder
Woog 1090
1000
3840
10000
1000
1003
31080
19000
300
1300
200
300
Figure 13: The test accuracy with respect to the number of labeled samples from initial to final step for all experimental settings.
weighted hypotheses based on the prediction error difference between the learned and the sampled hypotheses, and it works well empirically.
H PLOTS FOR TEST ACCURACY
Figure shows the test accuracy with respect to the number of labeled samples from initial final step for all experimental settings.
I LPDR vs MC-BATCHBALD
Figure 14] shows the performance comparison between LPDR and MC-BALD MNIST dataset using S-CNN when the query size or 20. LPDR significantly outperforms MC-BatchBALD on MNIST dataset when y = 1 such that MC-BatchBALD is completely identical to MC-BALD, LPDR also expected to outperform MCC-BatcBBALD even when q > 1: LPDR with g > performs better than MC-BALD with that IC-BatchBALD with q 1 does not exceed (Kirsch et al. 2019).
MNIST
90
test accurscy (%6
70
LPOR : -1
MC B4LD Iq=11
(q=22)
30
è of labeled samples
Figure 14: The comparison of performance between LPDR and MC-BALD on MNIST dataset where the query size is 1 or 20. The performance of BatchBALD with q > 1 does not exceed that of MC-BALD (g = 1) and LPDR (q = 20) outperforms MC-BALD (q = 1).
17

---

Under review as a conference paper at ICLR 2021
J AUC OF HAM10000 DATASET
On imbalanced dataset, the performance comparison is performed not only for accuracy but also for AUC. Figure [1] shows the results of AUC with respect to the number of labeled samples HAM10000 dataset. LPDR performs comparable with Entropy or ENS-VarR performing better than other algorithms.
HAM10000 (Co=500)
0.90
AUC
0.88
0.88
LPOR
MC BALD
Entropy
ENG--aar
900
1000
1500
2502
# of labeled samples
Figure 15: The comparison AUC on HAM10000 dataset. LPDR performs comparable with the best performing algorithms.
K RANK AND DORE CURVES
Rank curves
Dolan-More curves
C.5
CA.
Entrogy:
30 100
Figure 16: The rank and Dolan-More curves the algorithms across all experimental settings and repetitions. The left figure shows rank curve which is the mean of ranks on all datasets at each step. LPDR consistently is top-ranked for all steps. The right figure shows the each algorithm's Dolan- More curves which present the fraction of problems in which the algorithm has the performance gap from the best competitor. LPDR maintains the highest value for all T.
Table 3: The mean (+: standard deviation) of performance gap from the best competitor for all steps of each algorithm on each dataset. LPDR significantly outperforms the other algorithms on all datasets.
MNIST
CIFAR10
SVHN
EMNIST
CIFAR100
CIFARI00-W
T. ImageNet
Feod101
HAM10K0
LPUK
0.17-1-0.0
0:22-:-007
0.15-H-0012
0.13:::.04
0.23--0.10
0.50:-0.15
0.12:-0.18
0.13:3-009
0
Random
3.4520046
0.56
3.082:111
2:0:2008
0.62:0017
166-20446
1.4120.49
1.74:20.48
2.57 39
Entropy
1.20::0227
19
1.92:1.155
0.95:10113
3,19:1034
1.191:0228
1.82:10336
2.17:10.03
0.98110.10
MC-BALD
1.91:10448
2.25:0 16
0.5:1004
0.7810.18
1.80:10335
1.17200.10
1.00:1::22
1.53:20.09
2.04::299
1.76-4-046
1.72440.01
1.924-220
ENS-VERR
0665:0134
1.744
0.9720006
0:220004
213::028
1.572:034
1.85:20.26
1.3120331
081
Rank curves and Dolan-More curves are used to compare the performance of the algorithms across all experimental settings and repetitions. Figure 16 shows the rank and Dolan-More curves for all
18

---

Under review as a conference paper at ICLR 2021
algorithms considered in the experiment. The rank curve of each algorithm in the left-hand figure represents the mean ranks on all datasets at each steps of active learning. LPDR consistently is top-ranked for all steps.
The right-hante figure shows Dolan-More curves defined as follows (Dolan Moré 2002). Let acc be the final test accuracy of the algorithm on the p problem. After defining the pertormance gap as A = max, (acc*) - acce we can define Dolan-More curve R. (.) as a function the performance gap factor
#(p A T)
R
where Rpp is the total number of evaluations for the problem p. Thus, (T) is the ratio of problems with performance gap between algorithm a and the best performing competitor not more than т. Note that R2 (0) is the ratio of problems which algorithm performs the best. LPDR has the highest value Ra (0) 43.3%, and LPDR maintains the highest (T) for all T.
Table presents the mean and the standard deviation of performance gap from the best competi- tor for all steps of each algorithm on each dataset. Consistent with all the results so far, LPDR significantly outperforms the other algorithms in all experimental settings.
19


Reviews:
[{"review_id": "r6Adm82tg9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper defines a new \"distance to the decision boundary\" and empirically evaluates the corresponding active learning algorithm.\n\nUnfortunately, the motivation for this new distance to the decision boundary is lacking. It seems that there are a variety of possible quantities available and why this new one is principled or where it came from is unclear.\n\nClarity:\n - There are a lot of quantities, functions, and assumptions floating around and it is not clear how they are motivated or related.\n - I'm assuming $V(x)$ is the variation ratio as defined in Assumption 2? This is not clearly written.\n - In Theorem 1: it appears that $a(x,w)$ is undefined in the proof, or at least is defined after it is used.\n - In Theorem 1: the statement is not self-contained\n\nCorrectness:\n - In Theorem 1: it appears that if $x$ is on the decision boundary (i.e. $x^T \\hat{w}_t = 0$) then the first case does not hold.\n\nQuestions:\n - Why do you want $\\ell_p$ distance to the decision boundary instead of uncertainty measures (e.g. entropy)?\n - How is $\\beta$ set in the the algorithm? Is this another hyperparameter to tune?\n\n\nTypo: \"least probably disagreement region\" in Introduction\n\n\n***After author response***\n\nThanks for the response. \n\nPerhaps I didn't explain my concern about the motivation. SVM with uncertainty sampling works well, yes; however, it is equivalently several different things including selecting points closest to the decision boundary in Euclidean distance but also selecting points with highest predictive entropy and selecting points with smallest predictive margin. In other words, it seems that you are extrapolating from the SVM case to the neural network case and it's not clear which of several equivalent things will work in the neural network case.\n\nFurthermore, this paper doesn't even use Euclidean distance but instead uses a newly defined distance. So I really don't find the motivation or theory convincing.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QntYGRAhFf", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper defines a new measure of distance between a hypothesis $h$ and a point $x$, which is the probability mass of the smallest (by probability mass) disagreement region (induced by the other $h' \\in \\mathcal{H}$) containing $x$. In general this is intractable so the authors offer two assumptions about the relationship between this measure and more tractable quantities (one being the distance between the model parameters of those hypotheses, and the other being what the authors call the 'variation ratio'). The reasonability of these assumptions is then assessed, and the algorithm is tested on a variety of dataset and against several reasonable competitors. \n\nPros:\n\nTheorem 1 provides insight into the behaviour of $f_m^{(x)}$ in the binary linear classifier setting, although it strongly uses the linearity in the proof and so it could not be easily extended beyond that. However its purpose is to justify intuition about the variance of the noise used when sampling perturbed model parameters, rather than to make a strong claim, and it seems suitable for that purpose. \n\nThe experimental results are quite promising, with the proposed method outperforming many existing methods for active learning on neural networks. In particular the experiments perform several sets of experiments which give good insight into the general power and robustness of the method (although it would be good to know more about how hyperparameter tuning, in particular was equal computation given to tuning hyperparameters for the competitors)?\n\nCons: \n\nThe paper would benefit from some significant rewriting, as it is quite difficult to follow right now. There are several cases where quantities are used and discussed before being defined (Assumption 2 in the start of section 2) or before being rigorously defined ($f_m^{(x)}$ in Assumption 2 and section 3), or without being defined at all ($\\mathcal{P}_t$ in algorithm 1). In Theorem 1 it should be more clear that the theorem only applies to the case of a linear classifier described above it, as right now a brief read through the paper suggests it applies for the neural networks which are used throughout the rest of the paper.  \n\nTheorem 2 however is a very strong statement, and there is not sufficient justification for this strong a claim. In particular it is unclear why the authors feel any of these settings are realizable (capable of achieving 0 error on the population from which any of these data samples are drawn from). This is exactly the rate achieved by CAL (see http://www.stevehanneke.com/docs/active-survey/active-survey.pdf page 41), an algorithm which requires search over the entire version space, where as the algorithm here does a very limited search over the version space, otherwise it is at risk of missing whether a point is in the disagreement region. Additionally it is unclear what the authors mean by \"When the version space exists...\". The justification for the claim here must be made much more explicit. \n\nThe algorithm uses several fairly ad hoc choices, such as the use of the weights $\\gamma$, which could be much better explained. \n\nOverall I think this method is exciting, but would benefit from additional explanation. And the paper requires further editing and significant expansion around Theorem 2.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q0R-9hpOYGP", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is motivated by the idea that unlabelled samples near the estimated decision boundary show to be very informative/useful in an active learning setting. However, measuring the distance between an instance and the decision boundary is a non-trivial task in numerous machine learning algorithms, especially in deep learning. The paper proposes a (theoretical) sample distance to the decision boundary that relies on the least probable disagreement region (LPDR) that still contains the sample. The paper makes two assumptions to evaluate the proposed distance empirically: (1) closeness of the parameters of two hypotheses implies closeness of these hypotheses as defined by the probability of the disagreement region and (2) the variation ratio of labels obtained by evaluating a set of hypotheses sampled around the decision boundary is a proxy for the proposed distance. Considering these assumptions, hypotheses are sampled around a given decision boundary by adding gaussian noise to the parameters of the fitted model. Both assumptions are validated empirically on different datasets and varying levels of variance of the noise term to show the effect on the variation ratio and distance respectively. Consequently, an iterative active learning algorithm is proposed which adapts the variance of the noise term in order to select the predefined number of samples. Extensive experimental results indicate that LPDR outperforms other uncertainty based active learning algorithms on various datasets or is at least on par with them. \n\nThe submission provides a methodological contribution by proposing a way to evaluate the distance of an instance to the decision boundary for deep learning models. Even though the idea of adding noise to the model parameters and obtaining an ensemble of hypotheses is not groundbreaking, it follows a nice intuition and shows good and interesting empirical results. I think the paper is relevant for the ICLR and (active) learning community in general. The submission is well written and good to follow, the approach is well motivated and the concept of using variation ratio as a proxy for the distance is explained in a reasonable way. The paper draws connections to existing active learning approaches and provides numerous empirical results that highlight different aspects of LPDRs performance on various datasets and model architectures. However, it should be noted that the experiments were only conducted on image datasets and corresponding CNN architectures.\n\nThe paper includes reasonably complete information about the experiments and models/settings and I think that the reproducibility of the results is good (even though I did not explicitly validate it). However, the authors do not provide source code etc. in order to easily reproduce the results, which I would highly encourage.\n\nQuestions / Clarifications / Remarks:\n\n(1) Figure 1 shows the approximated distance between hypothesis h and 100 sampled hypotheses for different levels of sigma. t=0 indicates that the models were trained with a set of samples of initial acquisition size (given by Table 1). I assume that this set was kept constant across the different runs and sigmas. Can you report on the effect of choosing different initial pools? Are the results consistent with other chosen initial pools?\n(2) Can you comment on the results in appendix F showing that the performance does not differ significantly if sampling is applied to the parameters of the last or all layers. Do you think there might be scenarios in which this choice matters?\n(3) Did you test LPDR on tasks other than image classification and if yes, were the results equally good? If not, do you expect any differences in behaviour? \n\nMinor comments:\n\n(1) Add a description of the white arrow in the right plot of Figure 1.\n(2) Please revise the second last sentence on page 3. (The right hand side of ...)\n(3) Line 8 and 10 in Algorihm 1: sigma' in the inner loop has index N+1 (line 8) after completing the iteration, but index N is assigned to the sigma in the outer loop. \n(4) Please have your submission proof-read for English style and grammar issues such as pronouns.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "P5wG4b4XFev", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "- Some notions in Section 2 are confusing to me (maybe because I'm not familiar with related literature). For example, I don't understand why Eq.(2) is a kind distance measure between a sample x and a hypothesis.  How to more intuitively understand a \"distance of a sample to a hypothesis\"? \n- The sentence \"small perturbation in model parameter leads to small perturbation in hypothesis\" does not precisely match the mathematical meaning of Assumption 1.  Assumption 1 is states that $\\rho(h,h')$ is an increasing function of $\\|w-w'\\|^2$.  But the above sentence is better described by $\\rho(h,h') < C\\|w-w'\\|^2$.  Please change either Assumption 1 or the sentence. \n- Assumption 1 and 2 are stated in a very strong way. For example, Assumption 1 states that the relation holds for \"any\" triple of $\\hat{w}, w_1, w_2$. However, in Figure 1, the plotted result is \"averaged\" over random choices of $w_1, w_2$. So Figure 1 does not really verify Assumption 1. Similar for the case of Assumption 2. Please either change the statement of the assumptions or change the experiments in Figure 1 & 2. \n- The experiments in Figure 9 is not extensive. To show that target $\\rho_n'$ is indeed close to $q/m$, one needs to change the value of $q/m$ and see the corresponding $\\rho_n'$.  Also, Figure 9 seems to me \"the smaller $\\rho_n'$, the better test accuracy\".  But in any case, we need more extensive experiments to make any more interpretation.  Besides, do you have any theoretical justification about why $\\rho_n'$ should be close to $q/m$? \n- The authors hoped to connect their algorithm with some theory, but the assumptions are not stated in a precise way. The \"averaged\" plots in Figure 1&2 is intuitive in itself, so I don't think it is necessary to create those complicated notions in Section 2.  \n- The empirical performance of the proposed algorithm is always close to the best baseline, or outperforming it, which is good; but the insensitivity of parameter to the final performance (Section E and F) makes me worry that whether those parameters are taking any effect. Maybe N can be simply chosen as 1 to maximize the computational efficiency? And target $\\rho_n'$ can simply set to some very small quantity according to Figure 9 and we don't need to search for it? \n- Overall, the proposed algorithm seems to be a heuristic algorithm without precise theoretical justification, and the experiments are not extensive in some aspects.  So I think it should go through a major revision before it can be accepted. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the results are promising, several concerns were raised in the reviews, leading to the reject recommendation at this time.  There is an agreement among all reviewers that the paper would benefit from a revision.

Most reviewers felt that the paper lacks a rigorous and compelling theoretical justification for the proposed algorithm, making suggestions for what would make the paper stronger.

AnonReviewer4 would like to additionally convey the following message:

I would like to thank the authors to revise the statement of the assumptions according to my suggestions. However, the wording "with high probability" has rigorous mathematically meaning, so should be used with care. Their Figures still don't justify the current statement of the assumptions in my opinion.
Their experiment in Appendix E, which only contains one single example, is still too simplistic and cannot fully justify their claim. I would encourage the authors to test on more examples.
Decision: Reject