Year: 2020

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 `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.

heading: 1 INTRODUCTION
text: Active learning (Cohn et al., 1996) is a subfield of machine learning to attain data efficiency with fewer labeled training data when it is 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 a certain query strategy, the label of the most informative data is iteratively queried to an oracle to be used in retraining the model (Bouneffouf et al., 2014; Roy & McCallum, 2001; Sener & Savarese, 2017b; Settles et al., 2008; Sinha et al., 2019; Sener & Savarese, 2017a; Pinsler et 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-based sampling (Culotta & McCallum, 2005; Scheffer et al., 2001; 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-based algorithms have their own limitations. Entropy (Shannon, 1948) based uncertainty sampling can query unlabeled samples near the decision boundary for binary classification, but it does not perform well in multiclass classification as entropy does not equate well with the distance to a complex decision 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., 2011) as an uncertainty measure identifies unlabeled samples that are individually informative. This approach, however, is not necessarily 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 of batch, and is infeasible for large query size. The ensemble method (Beluch et al., 2018), one of the query by committee (QBC) algorithm (Seung et al., 1992), has been shown to perform well in many cases. The fundamental premise behind the QBC is minimizing the version space (Mitchell, 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.
This paper defines a theoretical distance referred to as 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 are obtained to be used for retraining the classifier to improve accuracy of the estimated decision boundary. It is generally understood that labels to samples near the decision boundary are the most informative as the samples are uncertain. Indeed in Balcan et al. (2007), selecting unlabeled samples with the smallest margin to 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 to the decision boundary as sample distance to 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.

heading: 2 DISTANCE: LEAST PROBABLE DISAGREEMENT REGION (LPDR)
text: 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 D be the instance space, the label space, the set of hypotheses h : x → y and the joint distribution over (x, y) ∈ X × Y . The distance between two hypotheses ĥ 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):
ρ(ĥ, h) := PD[ĥ(X) 6= h(X)]. (1)
This paper defines the sample distance d of x to the hypothesis ĥ ∈ H based on ρ as the least probable disagreement region (LPDR) that contains x:
d(x, ĥ) := inf h∈H(x,ĥ) ρ(ĥ, h) (2)
whereH(x, ĥ) = {h ∈ H : ĥ(x) 6= h(x)}.
Figure 1 shows an example of LPDR. Let’s define H = {hθ : hθ(x) = I[x > θ]} on input x sampled from uniform distribution D = U [0, 1] where I[·] is an indicator function. Suppose x = x0 and ĥ = ha ∈ H when a < x0. Here, H(x0, ha) consists of all hypotheses whose prediction on x0 is in disagreement with ha(x0) = 1, i.e., H(x0, ha) = {hb ∈ H : hb(x0) = 0} = {hb ∈ H : b > x0}. Then, the LPDR between x0 and ha, d(x0, ha) = x0 − a as the infimum of the distance between ha and hb ∈ H(x0, ha) is ρ(ha, hx0) = x0 − a. Here, the sample distribution D is unknown, and H(x, ĥ) 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′ = {h′ : ρ(ĥ, h′) ≤ ρ′} in terms of ρ′, and perform grid search to determine the smallest ρ′ such that there exists h′ ∈ H′ satisfying ĥ(x) 6= h′(x) for a given x. Sampling the hypotheses within the ball can be performed by sampling the corresponding parameters 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 ρ′ and is therefore computationally inefficient. However, unlabeled samples can be ordered according to d without grid search with the assumption that there exists aH′ such that variation ratio V (x) = 1− f (x)m /|H′| and d(x, ĥ) have strong negative correlation where f (x) m = maxc ∑ h′∈H′ I[h′(x) = c] (see Assumption 2).
Assumption 1. The expected distance between ĥ and randomly sampled h is monotonically increasing in the expected distance between the corresponding ŵ and w, i.e., E[‖ŵ − w1‖ | ŵ] ≤ E[‖ŵ − w2‖ | ŵ] implies that E[ρ(ĥ, h1) | ĥ] ≤ E[ρ(ĥ, h2) | ĥ] where ŵ,w1 and w2 are the parameters pertaining to ĥ, h1 and h2 respectively.
Assumption 2. There exists a hypothesis set H′ sampled around ĥ having the property that large variation ratio for a given sample data implies small sample distance to ĥ with high probability, i.e., there existsH′ such that V (x1) ≥ V (x2) implies that d(x1, ĥ) ≤ d(x2, ĥ) with high probability.

heading: 3 EMPIRICAL STUDIES OF LPDR

heading: 3.1 HYPOTHESES AND PARAMETERS IN DEEP NETWORKS: ASSUMPTION 1
text: The distance between two hypotheses can be approximated by vectors of the predicted labels on random samples by the hypotheses:
ρ(ĥ, h) ≈ ρe(ĥ, h) = 1
m m∑ i=1 I [ ĥ(x(i)) 6= h(x(i)) ] (3)
where x(i) is the ith sample for i ∈ [m]. The h is sampled by sampling model parameter w ∼ N (ŵ, Iσ2) where ŵ is the model parameter of ĥ, and the expectation of distances between w and ŵ depends on σ. The ρe is obtained by the average of 100 times for a fixed σ. The left-hand side of Figure 2 shows the relationship between ρe and σ on various datasets and deep networks. The ρe increases almost monotonically as σ increases. This implies that the order is preserved between
the σ and ρe. Furthermore, the ρe is almost linearly proportional to log(σ) in the ascension of the graph, i.e., σ ∝ eβρe for some β > 0. The right-hand side of Figure 2 shows V with respect to σ for each unlabeled sample on MNIST. The sample distance to the decision boundary can be expressed as σ at which the variation ratio is not zero for the first time (white arrow), where the indices of unlabeled samples in y-axis are 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 a certain range of σ.

heading: 3.2 LPDR VS VARIATION RATIO: ASSUMPTION 2
text: The left-hand side of Figure 3 shows Spearman’s rank correlation coefficient (Spearman, 1904) between LPDR and the variation ratio with respect to σ. The correlation is calculated using only unlabeled samples whose variation ratio is not 0. The strong rank correlation is verified when the σ has the appropriate value. Too larger value of σ 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 σ (log(σ) = −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 nσ be the unlabeled sample size, |H′| and the number of grid for σ respectively. Ordering unlabeled samples in terms of LPDR by grid search with respect to σ requires the time complexity of m × N × nσ (see the right-hand side of Figure 2). However, using variation ratio for ordering unlabeled samples reduces the time complexity to m×N . In the case of nσ = cN for some c > 0, then the time complexity can be reduced from O(mN2) to O(mN).

heading: 4 ALGORITHM FOR LPDR

heading: 4.1 FRAMEWORK
text: Let Lt and Ut be the labeled and unlabeled samples at step t. At step t, LPDR trains model parameters ŵt using labeled samples Lt, and constructs H′ by sampling the model parameters w′n ∼ N (ŵt, Iσ2) for n ∈ [N ]. Then, LPDR queries the top q unlabeled samples having highest variation ratio from the pool data Pt ⊂ Ut of size m.

heading: 4.2 CONSTRUCTION OF SAMPLED HYPOTHESIS SET
text: It is important to set an appropriate σ when constructing H′ as variation ratios goes to 0 with decreasing σ (see the right-hand side of Figure 2) and the rank correlation goes to zero with increasing σ (see the left-hand side of Figure 3). Theoretically, let’s consider the binary classification with logistic regression where the predicted label is defined as y = sgn(xTw) and supx∈X ‖x‖∞ <∞. Then the following theorem holds and the proof is described in Appendix A.
Theorem 1. Suppose that w′n for n = 1, . . . , N are generated with the variance of σ2. For all x, the followings hold: 1) As N → ∞, 1 − f (x)m /N goes to 0 in probability as σ2 goes to 0, 2) As N → ∞, 1 − f (x)m /N goes to 1/2 in probability for binary classification using logistic regression as σ2 goes to∞. The implication of Theorem 1 is that when σ is too small or too large, it would be difficult to compare the sample distances of unlabeled samples. In this active learning task, at least q most informative unlabeled samples must be identified. To meet this condition, it is reasonable to set ρ′n denoted in the Algorithm 1 as ρ∗ = q/m, which is not very small and is less than 1/2 in general, forN hypotheses.
This can be attained by updating σ′n as σ ′ n+1 = σ ′ ne −β(ρ′n−ρ ∗) where β > 0 (see Appendix D). The Figure 10 in Appendix E shows the final test accuracy with respect to target ρ′n on MNIST dataset. The LPDR performs best when the target ρ′n is roughly ρ
∗. In addition, the range of target ρ′n, associated with the best performance, is wide; thus, LPDR is relatively robust against target ρ ′ n. Furthermore, LPDR is robust against hyperparameters β, N and sampling layers (see Appendix F).
Algorithm 1 Least Probable Disagree Region (LPDR) Input: L0, U0 : Initial labeled and unlabeled samples m, q : Size of pool data and number of queries σ20 : Initial variance for sampling ρ∗ : Target hypothesis distance (= q/m)
Procedure: 1: for step t = 0, 1, 2, . . . , T − 1 2: Train parameters ŵt with Lt, then evaluate its empirical error ε̂t on Lt 3: σt → σ′1 4: for n = 1, 2, . . . , N 5: Sample parameters w′n ∼ N (ŵt, Iσ′2n ) for h′n 6: Compute γn = e−(ε ′ n−ε̂t)+ where ε′n is empirical error of w ′ n on Lt
7: Compute ρ′n = ρe(ĥt, h ′ n) 8: Update σ′n+1 = σ ′ ne −β(ρ′n−ρ
∗) where β > 0 9: end for
10: σ′N+1 → σt+1 11: Compute Vw(x(i)) = 1− f (i)w / ∑N n=1 γn where f (i) m = maxc ∑N n=1 γnI [ h′n(x (i)) = c ]
12: Get I∗ = arg maxI⊂IPt ,|I|=q ∑ i∈I Vw(x (i)) where IPt = { j : x(j) ∈ Pt ⊆ Ut } 13: Update Lt+1 = Lt ∪ {( x(i), y(i) )} i∈I∗ and Ut+1 = Ut \ { x(i) } i∈I∗ 14: 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 ĥt is in the version space, the sampled hypotheses h′ns are in 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 h′n where γn = e −(ε′n−ε̂t)+ is a function of ε̂t = errLt(ĥt) and ε ′ n = errLt(h ′ n). Here, (·)+ is max{0, ·} and errL(h) is the empirical error of h on L. Then, LPDR uses weighted variation ratio Vw as a function of the weighted frequency of the modal class fw as defined below:
Vw(x (i)) = 1− f (i) w∑N
n=1 γn (4)
where f (i)w = maxc ∑N n=1 γnI [ h′n(x (i)) = c ] and x(i) ∈ Pt ⊆ Ut.
If H′ is a subset of the version space in realizable case, the sample complexity of LPDR follows Hanneke’s theorem (Hanneke et al., 2014). Let Λ be the sample complexity defined as the smallest integer t such that for all t′ ≥ t, err(ht′) ≤ where err(h) := PD[h(X) 6= Y ] with probability at least 1 − δ. Then, LPDR achieves a sample complexity Λ such that, for D in the realizable case, ∀ , δ ∈ (0, 1),
Λ( , δ,D) . ξ · ( D log ξ + log ( log(1/ )
δ
)) · log 1
where D and ξ are the VC-dimension ofH and the disagree coefficient with respect toH and D. When ξ = O(1), in terms of , the number of labeled samples required by LPDR is just O(log(1/ ) · log log(1/ )), while the number of labeled samples by a passive learning is Ω(1/ ). Therefore, in this case, LPDR provides an exponential improvement over passive learning in sample complexity (Hsu, 2010).

heading: 5 EXPERIMENTS
text: This section discusses experimental results on 8 benchmark datasets: MNIST (LeCun et al., 1998), CIFAR10 (Krizhevsky et al., 2009), SVHN (Netzer et al., 2019), EMNIST (Cohen et al., 2017), CIFAR100 (Krizhevsky et al., 2009), Tiny ImageNet (subset of the ILSVRC dataset containing
200 categories rather than the usual 1000 categories; Russakovsky et al., 2015), Food101 (Bossard et al., 2014) and HAM10000 (Tschandl et al., 2018) datasets. For fair comparison with other active learning algorithms, simple two layered CNN, referred to as ‘S-CNN’ (Chollet et al., 2015) is used for MNIST and four layered CNN, referred to as ‘K-CNN’ (Chollet et al., 2015) is used for CIFAR10, SVHN, EMNIST and CIFAR100. Additionally, Wide-ResNet (WRN-16-8; Zagoruyko & Komodakis, 2016) is used for CIFAR100, Tiny ImageNet, Food101 and HAM10000.
Figure 4–7 show magnified plots of test accuracy to accentuate the difference in performance among different methods: initial labeled sample sizes are not shown in the figures. Figures that include initial labeled sample size are presented in Appendix H.

heading: 5.1 EXPERIMENTAL SETTINGS
text: Experimental settings regarding total number of epochs, data size and acquisition size are summarized in Table 1, and other details concerning the model, optimizer, batch size, learning rate and hyperparameters are presented in Appendix B.

heading: 5.2 RESULTS FOR MNIST, CIFAR10, SVHN AND EMNIST
text: A number of experiments are conducted to compare performance of LPDR with other high performing uncertainty based active learning algorithms on 8 datasets. Figure 4 shows the test accuracy with respect to the number of labeled samples on MNIST, CIFAR10, SVHN and EMNIST datasets. Each algorithm is denoted such as ‘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 ‘ENSVarR’: ensemble method. Overall, LPDR either performs best or comparable with all other algorithms. Its performance is consistent regardless of the benchmark datasets. In the early step, LPDR significantly outperforms all other algorithms on MNIST and CIFAR10 datasets. Of all the algorithms 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, LPDR outperforms BatchBALD on MNIST dataset (see Appendix I). Although MC-VarR 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 CIFAR10 datasets. It is observed that the performances of other algorithms have a relatively strong data dependency compared to LPDR. On CIFAR10 dataset, the performances of MC-VarR and ENS-VarR are no better than that of Random, and Entropy and MC-BALD have lower 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.

heading: 5.3 RESULTS FOR CIFAR100 WITH K-CNN AND WIDE-RESNET
text: In order to compare the performance of the algorithms with respect to the network capacity, experiments are conducted using networks of different capacity but on the same dataset. Figure 5 shows 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 a 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 it seems to be particularly effective with low capacity networks.

heading: 5.4 RESULTS FOR TINY IMAGENET AND FOOD101
text: Experiments on a more difficult task are conducted. Figure 6 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 CIFAR100. Even on more difficult tasks, LPDR outperforms all other algorithms.
5.5 RESULTS FOR HAM10000
Additional experiments are conducted to compare the performance of the algorithms on imbalanced HAM10000 dataset with WRN-16-8. Figure 7 shows the results of the test accuracy with respect to the number of labeled samples. The LPDR outperforms all other algorithms compared. Figure 15 in Appendix J shows the results of AUC with respect to the number of labeled samples. The LPDR performs comparable with all other algorithms.
To sum up the comparing algorithms across all experimental settings and repetitions, rank and DolanMore curves are presented in Appendix K. The LPDR consistently achieves top rank for all steps and significantly outperforms the other algorithms in all experimental settings.

heading: 6 RELATED WORK
text: Other than uncertainty-based sampling framework (Culotta & McCallum, 2005; Scheffer et al., 2001; Mussmann & Liang, 2018; Lewis & Gale, 1994; Gal et al., 2017; Kirsch et al., 2019; Beluch et al., 2018) for active learning, decision-theoretic framework based methods such as expected model change (Settles et al., 2008) have certain relevance to the proposed LPDR 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-Shwartz, 2019; Sinha et al., 2019; Zhang et al., 2020), and 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.

heading: 7 CONCLUSION
text: This paper defines a theoretical distance of unlabeled sample to the decision boundary referred to as the least probable disagreement region (LPDR) containing the unlabeled sample for active learn-
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 are empirically verified.
Experimental results on various datasets show that LPDR 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. 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 to be applied to various classification tasks with deep networks: the implementation requires only sampling a subset of parameters (parameters in the last FC layer of the deep network). Additionally, LPDR is capable of quick and reliable performance in a variety of different settings with only a 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.

heading: A PROOF OF THEOREM 1
text: Assume that ‖ŵt‖ = 1 without the loss of generality, and ‖x‖ 6= 0 to avoid the null case. The predicted label of x by w′n disagrees with that by ŵt if sgn ( xTw′n ) 6= sgn ( xTŵt ) , here, sgn(0) = 1. Note that xTw′n = x Tŵt + σx Te′n where e ′ n = (Zn1, . . . , Zn|w|) T,
and Znks are independent random variables from N (0, 1). The event of {sgn ( xTw′n ) 6=
sgn ( xTŵt ) } is equal to that of E1 ∪E2 where E2 = {σxTe′n ≥ 0,xTŵt < 0} and E2 = {σxTe′n < 0,xTŵt ≥ 0}. Thus, the proof has two folds: the cases of 1) E1 and 2) E2. In the first fold,
P [E1] = P [ σxTe′n ≥ |xTŵt| ] = P [ σ‖x‖Z ≥ |xTŵt| ] = 1− Φ
( a (x, ŵt)
σ ) where Z ∼ N (0, 1), Φ is the cumulative distribution function of the normal distribution, and a (x, ŵt) = |xTŵt|/‖x‖. Note that σxTe′n ∼ N (0, σ2‖x‖2). Consequently, P[E1] < 1/2 due to a (x, ŵt) > 0. Hence, the following
f (x) m
N = N∑ n=1 1 N I [ ĥt(x) = h ′ n(x) ] goes to value greater than 1/2 in probability as N → ∞ because Var(f (x)m /N) → 0 as N → ∞. Therefore, as N →∞, ∀x, the variation ratio is
1− f (x) m
N = 1− N∑ n=1 1 N I [ ĥt(x) = h ′ n(x) ] → 1− Φ ( a (x, ŵt) σ ) in probability. This is due to that f (x)m is the frequency of mode class with probability tending to 1 as N →∞. By the smoothness of Φ,
1− f (x) m
N → 1− Φ(∞) = 0 as σ2 → 0
and
1− f (x) m
N → 1− Φ(0) = 1 2 as σ2 →∞.
Next, in the second fold,
P [E2] = P [ σxTe′n < −|xTŵt| ] = P [ σ‖x‖Z < −|xTŵt| ] = Φ ( −a (x, ŵt)
σ
) .
Consequently, P[E2] < 1/2. Hence the following
f (x) m
N = N∑ n=1 1 N I [ ĥt(x) = h ′ n(x) ] goes to the value greater than 1/2 in probability as N →∞ because Var(f (x)m /N)→ 0 as N →∞. Therefore, as N →∞, ∀x, the variation ratio is
1− f (x) m
N = 1− N∑ n=1 1 N I [ ĥt(x) = h ′ n(x) ] → Φ ( −a (x, ŵt) σ ) = 1− Φ ( a (x, ŵt) σ ) in probability. This is due to that f (x)m is the frequency of mode class with probability tending to 1 as N →∞. By the smoothness of Φ,
1− f (x) m
N → 1− Φ(∞) = 0 as σ2 → 0
and
1− f (x) m
N → 1− Φ(0) = 1 2 as σ2 →∞.
This completes the proof.

heading: B EXPERIMENTAL SETTINGS
text: B.1 DATASETS
MNIST (LeCun et al., 1998) is a 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 a black and white image and 28× 28 in size. CIFAR10 and CIFAR100 (Krizhevsky et al., 2009) are labeled subsets of the 80 million tiny images dataset which have a training set of 50, 000 samples and a test set of 10, 000 samples in 10 and 100 classes respectively. Each sample is a color image and 32× 32 in size. SVHN (Netzer et al., 2019) is a 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 is a color image and 32× 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 a test set of 10, 000 samples in 47 classes. Each sample is a black and white image and 28× 28 in size. Tiny ImageNet is a subset of the ILSVRC (Russakovsky et al., 2015) dataset which has 100, 000 samples in 200 classes. Each sample is a color image and 64 × 64 in size. In experiments, Tiny ImageNet is split into two parts: a training set of 90, 000 samples and a test set of 10, 000 samples.
Food101 (Bossard et al., 2014) is a fine grained dataset which has a training set of 75, 750 samples and a test set of 25, 250 samples in 101 classes. Each sample is 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 a color image and resized to 75 × 75. In experiments, HAM10000 is split into two parts: a training set of 8, 515 samples and a 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 et al., 2015), consists of [3×3× 32 conv - 3×3×64 conv - 2×2 maxpool - dropout (0.25) - 128 dense - dropout (0.5) - #class dense - softmax] layers. K-CNN, which is the Keras CIFAR CNN implementation (Chollet et al., 2015), consists of [two 3 × 3 × 32 conv - 2 × 2 maxpool - dropout (0.25) - two 3 × 3 × 64 conv - 2 × 2 maxpool - dropout (0.25) - 512 dense - dropout (0.5) - #class dense - softmax] layers. WRN-16-8 is a wide residual network that has 16 convolutional layers and a widening factor 8 (Zagoruyko & Komodakis, 2016). The optimizer, initial learning rate, learning rate schedule and batch size for each experimental setting are described in Table 2. 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 5 networks of identical architecture but different random initialization and random batches. For LPDR, we set σ0 = 0.01, β = 1, N = 100 and parameter sampling is applied to the last dense layer of each network.

heading: C RANK CORRELATION BETWEEN LPDR AND VARIATION RATIO
text: D REGULATING ρ′n BY THE VARIANCE OF SAMPLING
The left-hand side of Figure 9 shows the ρ′n with respect to the active learning progress. For all experiments, LPDR reliably guides the ρ′n to be ρ
∗ = q/m (MNIST: 0.01, CIFAR10: 0.05, SVHN: 0.05, EMNIST: 0.075, CIFAR100 (KCNN): 0.1, CIFAR100 (WRN): 0.2, Tiny ImageNet: 0.25, Food101: 0.2 and HAM10000: 0.1) after the initial few steps. The right-hand side of Figure 9 shows
log(σ) 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 ρ′n = ρ ∗ 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.
E FINAL TEST ACCURACY VS TARGET ρ′n
The Figure 10 shows the final test accuracy with respect to target ρ′n 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 ρ′n, associated with the best performance, is wide (0.01 ∼ 0.1); thus, LPDR is robust against the target ρ′n in the wide range.

heading: F ROBUSTNESS OF LPDR AGAINST HYPERPARAMETERS
text: LPDR has four hyperparameters: 1) the initial variance of sampling σ0; 2) the positive hyperparameter for regulating the variance of sampling β; 3) the number of sampled hypotheses N , and 4) the layer index of the network to which sampling is applied. The σ0 has no significant effect on the performance of LPDR since σ is adaptively regulated based on the ρ′n while sampling the sampled hypothesis. Thus, σ0 is not examined in detail. Figure 11 shows the performance comparison with respect to the hyperparameters of LPDR on MNIST and CIFAR10 datasets. The left figures show that there is no significant difference in the performance of LPDR for various β ∈ {0.1, 1, 10} on both datasets. The robustness of LPDR against β is based on the sufficient buffer for regulating σ since the range of target ρ′n 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 ∈ {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 q most informative unlabeled samples with a small number of sampled
hypotheses by setting ρ∗ = q/m. The right figures show that there is 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.

heading: G EMPIRICAL ERRORS OF LEARNED AND SAMPLED HYPOTHESES
text: 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 CIFAR100 with 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, LPDR incorporates the
weighted hypotheses based on the prediction error difference between the learned and the sampled hypotheses, and it works well empirically.

heading: H PLOTS FOR TEST ACCURACY
text: Figure 13 shows the test accuracy with respect to the number of labeled samples from initial to final step for all experimental settings.

heading: I LPDR VS MC-BATCHBALD
text: Figure 14 shows the performance comparison between LPDR and MC-BALD on MNIST dataset using S-CNN when the query size is 1 or 20. LPDR significantly outperforms MC-BatchBALD on MNIST dataset when q = 1 such that MC-BatchBALD is completely identical to MC-BALD. LPDR is also expected to outperform MC-BatchBALD even when q > 1: LPDR with q > 1 performs better than MC-BALD with q = 1 that MC-BatchBALD with q > 1 does not exceed (Kirsch et al., 2019).
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 (q = 1) and LPDR (q = 20) outperforms MC-BALD (q = 1).

heading: J AUC OF HAM10000 DATASET
text: On imbalanced dataset, the performance comparison is performed not only for accuracy but also for AUC. Figure 15 shows the results of AUC with respect to the number of labeled samples on HAM10000 dataset. LPDR performs comparable with Entropy or ENS-VarR performing better than other algorithms.

heading: K RANK AND DOLAN-MORE CURVES
text: 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
algorithms considered in the experiment. The rank curve of each algorithm in the left-hand figure represents the mean of ranks on all datasets at each steps of active learning. LPDR consistently is top-ranked for all steps.
The right-hand figure shows Dolan-More curves defined as follows (Dolan & Moré, 2002). Let accpa be the final test accuracy of the a algorithm on the p problem. After defining the performance gap as ∆pa = maxx(acc p x)−accpa, we can define Dolan-More curve Ra(·) as a function of the performance gap factor τ :
Ra(τ) = #(p : ∆pa ≤ τ)
np
where np is the total number of evaluations for the problem p. Thus, Ra(τ) is the ratio of problems with performance gap between algorithm a and the best performing competitor not more than τ . Note that Ra(0) is the ratio of problems on which algorithm a performs the best. LPDR has the highest value Ra(0) = 43.3%, and LPDR maintains the highest Ra(τ) for all τ .
Table 3 presents the mean and the standard deviation of performance gap from the best competitor 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.

Review summaries:
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. 

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.