On the Geometry of Deep Bayesian Active Learning
Authors: Xiaofeng Cao
Ivor Tsang
Venue:  (2021)
Keywords: Bayesian active learning
geometric interpretation
core-set construction
model uncertainty
ellipsoid.

Abstract: We present  geometric Bayesian active learning by disagreements (GBALD), a framework that performs BALD on its geometric interpretation interacting with a deep learning model. There are two main components in GBALD: initial acquisitions based on core-set construction and model uncertainty estimation with those initial acquisitions. Our key innovation is to construct the core-set on an ellipsoid, not typical sphere, preventing its updates towards the boundary regions of the distributions. Main improvements over BALD are twofold: relieving sensitivity to uninformative prior and reducing redundant information of model uncertainty. To guarantee the improvements, our generalization analysis proves that, compared to typical Bayesian  spherical interpretation, geodesic search with ellipsoid can derive a tighter lower error bound and achieve higher probability to obtain  a nearly zero error. Experiments on acquisitions with several scenarios demonstrate that, yielding slight perturbations to noisy and repeated samples,  GBALD further achieves significant accuracy improvements  than BALD, BatchBALD and other baselines.

Under review as a conference paper at ICLR 2021
ON THE GEOMETRY OF DEEP BAYESIAN ACTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We present geometric Bayesian active learning by disagreements (GBALD), a framework that performs BALD on its geometrie interpretation interacting with a deep learning model. There are two main components in GBALD: initial acquisi- tions based on core-set construction and model uncertainty estimation with those initial acquisitions. Our key innovation is to construct the core-set on an ellipsoid, not typical sphere, preventing its updates towards the boundary regions of the dis- tributions. Main improvements over BALD are twofold: relieving sensitivity to uninformative prior and reducing redundant information model uncertainty. To guarantee the improvements, our generalization analysis proves that, compared to typical Bayesian spherical interpretation, geodesic search with ellipsoid can derive tighter lower error bound and achieve higher probability to obtain nearly zero error. Experiments on acquisitions with several scenarios demonstrate that, yield- ing slight perturbations noisy and repeated samples, GBALD further achieves significant accuracy improvements than BALD, BatchBALD and other baselines.
INTRODUCTION
Lack of training lahels restricts the performance of deep neural networks (DNNs), though prices of GPU resources were falling fast. Recently, leveraging the abundance of unlabeled data has become a potential solution to relieve this bottleneck whereby expert knowledge is involved to annotate those unlabeled data. such setting, the deep learning community introduced active learning (AL)
(Gal et al. 2017) that, maximizing the model uncertainty (Ashukha et al.) 2019 Lakshminarayanan al. 2011) 7) to acquire a set of highly informative or representative unlabeled data, and solicit experts' annotations. During this AL process, the learning model tries to achieve desired accuracy using minimal data labeling. Recent shift of model uncertainty in many fields, such as Bayesian neural networks (Blundell et al. 2015), Monte-Cart (MC) dropout (Gal & Ghahraman] (206)), and Bayesian core-set construction Senner & Savarese 2018), shows that, new scenarios arise from deep Bayesian AL (Pinsler et al.) 2019 Kirsch al. 2019).
Bayesian AL (Golovin et al. 2010 Jedoui et al. 2019 presents an expressive probabilistic interpre-
tation on model uncertainty (Gal & Ghahramani 2016). Theoretically, for a simple regression model such as linear, logistic, and probit, AL can derive their closed-forms on updating one sparse subset that maximally reduces the uncertainty of the posteriors over the regression parameters (Pinsler et al.) 2019). However, for a DNN model, optimizing massive training parameters is not casily tractable. It thus that Bayesian approximation provides alternatives including importance sampling (Doucet optimization (Vavasis, 1992). With importance sampling, a typical
ct al. 2000) and approach is to express the information gain in terms of the predictive entropy over the model, and is called Bayesian active learning by disagreements (BALD) (Houlsby et al. (0011).
BALD has two interpretations: model uncertainty estimation and core-set construction. To estimate the model uncertainty, a greedy strategy is applied select those data that maximize the parameter disagreements between the current training model and its subsequent updates as (Gal et al.. 2017). However, naively interacting with BALD using uninformative prior (Strachan & Van Dijk (2033 (Picee & Manson 2002), which can be created to reflect a balance among outcomes when no information available, leads to unstable biased acquisitions (Gao et al., 2020), e.g. insufficient prior labels. Moreover, the similarity or consistency of those acquisitions to the previous acquired samples, brings redundant information to the model and decelerates its training.
Core-set construction (Campbell & Broderick, 2018) avoids the greedy interaction to the model by capturing characteristics of the data distributions. By modeling the complete data posterior over the

---

Under review as a conference paper at ICLR 2021
distributions of parameters, BALD be deemed core-set construction process sphere (Kirsch et al., (2019), which seamlessly solicits a compact subset to approximate the input data distribution, and efficiently mitigates the sensitivity to uninformative prior and redundant information.
From the view of geometry, updates of core-set construction is usually optimized with sphere geodesic as (Nie et al. 2013] Wang al. 2019). Once the core-set is obtained, deep AL immediately seeks annotations from experts and starts the training. However, data points located at the boundary regions of the distribution, usually win uniform distribution, cannot be highly-representative candidates for the core-set. Therefore, constructing the core- set on a sphere may not be the optimal choice for deep AL.
BALD
construction
X
GBALD
Figure 1: Illustration of two-stage GBALD framework. BALD has two types of interpretation: model uncer- tainty estimation and core-set construction where the deeper the color of the core-set element, the higher the representation; GBALD integrates them into uniform framework. Stage T) core-set construction is with an ellipsoid, not typical sphere, representing the origi- nal distribution to initialize the input features of DNN. Stage @: model uncertainty estimation with those ini- tial acquisitions then derives highly informative and representative samples for DNN.
This paper presents a novel AL framework, namely Geometric BALD (GBALD), over the geometric interpretation of BALD that, interpreting BALD with core-set con- struction on an ellipsoid, initializes an drive DNN model. The goal is to seek for significant accuracy improvements against an uninformative prior and redundant information. Figure 1 describes this two-stage framework. In the first stage, geometric core-set construction on an ellipsoid initializes effective acquisitions to start DNN model regardless of the uninformative prior. Taking the core-set as the input features, the next stage ranks the batch acquisitions of model uncertainty according to their geometric representativeness, and then solicits some highly-represetteen batch. With the representation constraints, the ranked acquisitions reduce the probability of sampling nearby samples of the previous acquisitions, preventing redundant acquisitions. To guarantee the improvement, our generalization analysis shows that, the lower bound of generalization errors of AL with the ellipsoid is proven to be tighter than that AL with the sphere. Achieving a nearly zero generalization error by AL with ellipsoid is also proven to have higher probability. Contributions of this paper can be summarized from Geometric, Algorithmic, and Theoretical perspectives.
effective representation
examples from the
Geometrically,
key innovation is to construct the core-set on an ellipsoid, not typical sphere, preventing its updates towards the boundary regions of the distributions.
In term of algorithm design, in our work, from a Bayesian perspective, we propose two-stage framework that sequentially introduces the core-set representation and model uncertainty, strengthening their performance "independently". Moreover, different to the typical BALD optimizations, we present geometric solvers to construct core-set and estimate model uncertainty, which result in different view for Bayesian active learning.
Theoretically, guarantee those improvements, our generalization analysis proves that, compared to typical Bayesian spherical interpretation, geodesic search with ellipsoid can derive a tighter lower error bound and achieve higher probability to obtain a nearly zero error. See Appendix B.
The rest of this paper is organized as follows. In Section 2, we first review the related work. Secondly, we elaborate BALD and GBALD in Sections and 4, respectively. Experimental results are presented in Section 5. Finally, we conclude this paper in Section
RELATED WORK
Model uncertainty. In deep learning community, AL (Cohn et al. 1994) was introduced to improve the training of DNN model by annotating unlabeled data, where the data which maximize the model uncertainty LLakshminarayanan et al., (017)) are the primary acquisitions. For example, in ensemble deep learning (Ashukha et al. 2019). oft-of-domain uncertainty estimation selects those data which do not follow the same distribution as the input training data; in-domain uncertainty draws the data from the original input distribution, producing reliable probability estimates, Gal &
2

---

Under review as a conference paper at ICLR 2021
MC dropout to estimate predictive uncertainty for approximating Bayesian convolutional neural network. [akksminarayaaaa et al.] (2017) estimate predictive uncertainty using proper scoring rule the training criteria to fed DNN.
Ghahramani (2016)
Bayesian AL. Taking Bayesian perspective (Golovin et al. 2010), AL can be deemed as minimizing the Bayesian posterior risk with multiple label acquisitions informative approach is to reduce the uncertainty about the parameters using Shanmon's 's entropy (Tang al. 2002). This can be interpreted seeking the acquisitions for which the Bayesian parameters under the posterior disagree about the outcome the most, so this acquisition algorithm is referred to as Bayesian active learning by disagreement (BALD) (Houlsby et 2011).
the input unlabeled data. A potential
Deep AL. Recently, deep Bayesian AL attracted our eyes. Gal et al. (017)) proposed to cooperate BALD with DNN improve the training. The unlabeled data which maximize the model uncertainty provide positive feedback. However, it needs to repeatedly update the model until the acquisition budget is exhausted. To improve the acquisition efficiency, batch sampling with BALD applied as (Kirsch et al., 2019] Pinsler et al., 2019). In BatchBALD, Kirsch et al. (2019) developed a tractable approximation to the mutual information of one batch of unlabeled data and current model parameters. However, those uncertainty evaluations of Bayesian AL whether in single or batch acquisitions all take greedy strategies, which lead to computationally infeasible, or excursive parameter estimations. For deep Bayesian AL, being short of interactions to DNN can not maximally drive their model performance as (Pinsler et al. 2019
Sener & Savarese 2018), etc.
BALD
BALD has two different interpretations: model uncertainty estimation and core-set construction. We simply introduce them in this section.
3.1 MODEL UNCERTAINTY ESTIMATION
We consider discriminative model p(y| parameterized by 0 that maps æ X into an output distribution over a set of y. Given an initial labeled (training) set Du X' V, the Bayesian inference over this parameterized model to estimate the posterior p(f)Du), i... estimate by repeatedly updating Do. AL adopts this setting from Bayesian view.
With AI,, the learner can choose unlaheled data from D, (2:) e XX to observe the outputs of the current model, maximizing the uncertainty of the model parameters. (Houlsby et al. (201T) proposed a greedy strategy termed BALD to update Do by estimating a desired data x that maximizes the decrease in expected posterior entropy:
x² arg max [ -APPAlEyy-ptree E || y, Doll. bile,,DDol]
(1) where the labeled and unlabeled sets are updated by Do Do u f=x .y" Du Dulx", and y² denotes the output of x". In deep AL. y* can be annotated label from experts and yields DNN model.
zeD
3.2 CORE-SET CONSTRUCTION
Let p() be updated by its log posterior logp( ( Do. x²), ). y² (ui) assume the outputs conditional independent of the inputs, i.c. p(y" l Do)
p(y" aa ())(()) then we have
the complete data log posterior following (Pinsler e al. 2019
Ey [logp( O Do, x" :y"]] Ey. [U)))(U[D))) logo(y' (y' |x", 0) - logp(y |a" Do)]
=logp(((D)) Ey. logp(y" (y"""""""" | ())))) + H[y" |x" Dol
logg(((Do)
Σ
E logp(1s 0) + + [ Dol]
The key idea of core-set construction is to approximate the log posterior of Eq. (2) by subset of D', E D. such that: Ey, [ly][[or(([])) (.D, D.)) ] Ey. (ogg((/D, D'.' where Vn, and y denote the predictive labels of D. and D', respectively by the Bayesian discriminative model, that is, p(),,Da,, D₂) = So (P.,.l p) ( D. dl, and p() (D', Du) So P(", DD',, ()) Here D', can be indicated by core-set (Pinsler et al. 2019) that highly represents D,,. Optimization tricks such Frank- Wolfe optimization [Vavasis 1992) then can be adopted to solve this problem.
3

---

Under review as a conference paper at ICLR 2021
Motivations. Eqs. (1) and (2) provide the Bayesian rules of BALD model uncertainty and core-set construction respectively, which further attract the attention of the deep learning commu- nity. However, the two interpretations of BALD are limited by: 1) redundant information and 2) uninformative prior, where one major reason which causes these two issues is the poor initialization on the prior, i.e. p(Do)O). For example, unbalanced label initialization uninformative prior, which further conducts the acquisitions of AL to select those unlabeled data from one or some fixed classes; highly-biased results with (Gao al. 2020 redundant information are inevitable. Therefore, these two limitations affect each other.
Dn usually leads to an
GBALD
GBALD consists of two components: ini- tial acquisitions based on cote-set construc- tion and model uncertainty estimation with those initial acquisitions.
4.1 GEOMETRIC
(a) Sphere geodesic
(b) Ellipsoid geodesic
INTERPRETATION OF CORE-SET
Modeling the complete data posterior over the parameter distribution can relieve the above two limitations of BALD. Typically, finding the acquisitions of AL is equivalent to approximating core-set centered with spherical embeddings (Sener & Savarese 2018). Let w; be the sampling weight of 10 lo S N, the core-set construction is to optimize:
Figure 2: soid geodesies. Ellipsoid geodesic rescales the sphere geodesic to prevent the updates of the core-set towards the boundary regions of the sphere where the charac- teristies of the distribution cannot be captured. Black points denote the feasible updates of the red points. Dash lines denote the geodesics.
Optimizing BALD with sphere and ellip-
min
Ey (ogp(yila,, 0) H[yi Dol]
wr [ogp(ur)22 1y Dol]
(3)
((w)
where C and L(w) denote the full and expected (weighted) log- likeliikohhdd, respectively (Campbell
& Broderick 2018 2019). Specifically, Eee H[,] Do] Σ,, p(yi Do (og Da). where p (3 F., Do) Jo P(ul,, Du) Note |- denotes the 8² norm.
The approximation of Eq. (3) implicitly requires that the complete data log posterior of Eq. (2) w.r.t. must be close to an expected posterior w.r.t. L(w) such that approximating a sparse subset for the original inputs by sphere geodesic search is feasible (see Figure 2(a)). Generally, solving this optimization intractable due to cardinality constraint (Pinsler et al.) 2019). [Cmmbell & Broderick (2019) proposed to relax the constraint in Frank-Wolfe optimization. which mapping X is usually performed in a Hilbert space (HS) with a bounded inner product operation. In this solution, the sphere embedded in the HS replaces the cardinality constraint with polynomial constraint. However, the initialization on Dd affects the iterative approximation to u at the beginning of the geodesic search. Moreover, the posterior of (()))) is uninformative, if the initialized Do is empty not correct. Therefore, the typical Bayesian core-set construction of BALD cannot ideally fit an uninformative prior. The another geometric interpretation of core-set construction, such as k-centers (Sener & Savarese 2018), is not restricted to this setting. We thus follow the construction of k-centers to find the core-set.
k-centers. Sener & Savarese (0018) proposed core-set representation approach for active deep learning based on k-centers. This approach can be adopted in core-set construction BALD without the help of the discriminative model. Therefore, the uninformative prior has no further influence on the core-set. Typically, the k-centers approach uses a greedy strategy to search the data T whose nearest distance to elements of Do is the maximal:
T = arg max min | -c 2.:D. c,62o
(4)
then Do is updated by Do 7). D,, is updated by D., where y denotes the output of ह. This max-min min operation usually performs i times to construct the centers.
From the view of geometry, k-centers can be deemed as the core-set construction via spherical geodesic search (Bādoiu et al., 2002 (Har-Peled & Mazumdar 2004). Specifically, the max-min
4

---

Under review as a conference paper at ICLR 2021
optimization guides Du to be updated into data, which draws the longest line segment from 2;, Vi across the sphere center. The iterative update on H is then along its unique diameter through the sphere center. However, this greedy optimization has large probability that yields the core-set to fall into boundary regions of the sphere, which cannot capture the characteristics of the distribution.
4.2 INITIAL ACQUISITIONS BASED ON CORE-SET CONSTRUCTION
We present a novel greedy search which rescales the geodesic of a sphere into an ellipsoid following Eq. (4), in which the iterative update on the geodesic search is rescaled (see Figure 2(b)). We follow the importance sampling strategy to begin the search.
Initial prior on geometry. Initializing pDDo)0) is performed with group of internal spheres centered with D,, Vj, subjected to Dj E Do. in which the geodesic between Do and the unlabeled data is over those spheres. Since Do is known, specification of 0 plays the key role for initializing pl (Dol0). Given a radius Ro for any observed internal sphere, p. 0) is firstly defined by 3j. x2 Dý1 s Ro,
O)
Ro
(5)
max
Vi. D11 > Ro.
| - D2l
thereby 0 yields the parameter Ro. When the data is enclosed with a ball, the probability of Eq. (5) is 1. The data near the ball, is given a probability of max [TI--iT] constrained by minl|a;; -Di V.j. ie. the probability is assigned by the nearest ball I4, which is centered with Dj. From Eq. (3), the information entropy of y/s (81.8/2 .... yN over 24 (211 .2,,..,TTT .N} can be expressed as the integral regarding p(
N H( Do) - Σ P(unlrr (( i1
Se Pivilor p ())
(6)
which can be approximated by ENN, p(u.,, log () p(us 0) following the details of Eq. (3). In short, this indicates an approximation to the entropy over the entire outputs on Du, that assumes the prior (o(0)) w.r.t (1, 0) is already known from Eq. (5).
Max-min optimization. Recalling the max-min optimization trick of k-centers in the core-set construction of (Sener& & Savarese, 2018). the minimizer of Eq. (3) can be divided into two parts: min.. L and max., [ww), where Do is updated by acquiring 2". However, updates of Do decide the minimizer of with regard the internal spheres centered with D,, Vi. Therefore, minimizing L should be constrained by unbiased full likelihood over X' to alleviate the potential biases from the initialization of 'Do. Let fo denote the unbiased full likelihood over X' that particularly stipulates Do the k-means centers written U of X which jointly draw the input distribution. We define Co = Σ Ey, [logp(u f 0)+ H (r, 2]]l to regulate L, that is min Cn CII s.t. Do Do u {a",") "y""""), =Dla=*
The other sub optimizer is max.. ((w). We present greedy strategy following Eq. (1):
max min N My
Σ w. [logp(uske,,)) 0) + H[uulx,, Doll
(8)
Σ w. w,llogr(ull, 0) Σ
E1
which can be further written as: ΣN wylogp(u (1 logr(ui (uil Let w; 1, Vi for unbiased estimation of the likelihood [(w), Eq. (8) can be simplified as
max min (og,(us(z,,)))
(9)
2. Do
where p(u,l,,,0) 0) follows Eq. (5). Combining Eqs. (7) and (9), the optimization of Eq. (3) is then transformed as
[Coo 2 logp(us 00).
r" = arg max min a,eDa DjeDo
(10)
where Do is updated by acquiring x", i.e. Do = Do (x",
Geodesic line. For metric geometry M, geodesic line is curve y which projects its in- terval I to M: + M, maintaining everywhere locally a distance minimizer (Lou et al. 2020). Given a constant 0 such that for any a.b E T there exists geodesic distance
5

---

Under review as a conference paper at ICLR 2021
d(>(a);>(b)) (r(o) where 7((1) denotes the geodesic curvature, and g denotes the metric tensor over M. Here, we define (t) 0, then 9)(e) (0, such that (()()) can be generalized as segment of straight line: d(>(a), = bll.
Ellipsoid geodesic distance. For any observation points p, q с M, if the spherical geodesic distance is defined as d( d(<(p),7(g) Ip - ql. The affine projection obtains its ellipsoid interpretation: d(r(p). (11pp(pp)) where 17 denotes the affine factor subjected to 0 < <1 <1.
Optimizing with ellipsoid geodesic search. The max-min optimization of Eq. (10) is performed on an ellipsoid geometry to prevent the updates of core-set towards the boundary regions, where ellipsoid geodesic line scales the original update on the sphere. Assume 2; is the previous acquisition and x" is the next desired acquisition, the ellipsoid geodesic rescales the position of x² as Fx = I; + 77(2" x;). Then, we update this position of xe to its nearest neighbor vi in the unlabeled data pool, i.e. arg min ED. | - x= also can be written as
arg min min |. [at 71 x. ]
(11)
x,eD, To study the advantage of ellipsoid geodesic search, Appendix B presents our generalization analysis.
4.3 MODEL UNCERTAINTY ESTIMATION WITH CORE-SET
GBALD starts the model uncertainty estimation with those initial core-set acquisitions, in which it introduces ranking scheme to derive both informative and representative acquisitions.
Single acquisition. We follow (Gal et al. 2017) and use MC dropout to perform Bayesian inference on the model of the neural network. then leads to ranking the informative acquisitions with batch sequences is with high efficiency. We first present the ranking criterion by rewriting Eq. (1) as batch returns:
{5i. 22: x%)
arg max H[0[Do] F plunllii Da)
H[ Un. Dal]:
(12)
(#1 (2 DED
where f1 (01, J. D1 (ū1, .i.....,.... ...; ). in denotes the output of dt. The informative acquisition =7 is then selected from the ranked batch acquisitions 11 due to the highest representation for the unlabeled data:
Ro
arg max 27 ((; . (....)))) where denotes the index of the final acquisition, subjected to 1s b. This also adopts the max-min optimization of k-centers in Eq. (4), i.e, x arg au@xatelut.ag.....
max p(y] DrcDo
10 - D2I
(13)
minp,ePo |x - D3ll-
Batch acquisitions. The greedy strategy of Eq. (13) can be written as a batch acquisitions by setting its output batch set, i.e. ( ".,,, "i (sg....())
arg max p pluitt ( !),
(14)
where Thi {x/, ..... o7,, ). Viyt (8,, ...., yi }, Vf, denotes the output of z isish b, and 1 b' s b. This setting can be used to accelerate the acquisitions of AL in large dataset. Appendix A presents the two-stage GBALD algorithm.
5 EXPERIMENTS
In experiments, start by showing how BALD degenerates its performance with uninformative prior and redundant information, and show that how our proposed GBALD relieves theses limitations.
Our experiments discuss three questions: 1) is GBALD using core-set of Eq. (11) competitive with uninformative prior? 2) can GBALD using ranking of Eq. (14) improve informative acquisitions of model uncertainty? and 3) can GBALD outperform state-of-the-a acquisition approaches? Following the experiment settings of (Gal et al. 2017: Kirsch et al.) 2019), we use MC dropout to implement the Bayesian approximation of DNNs. Three benchmark datasets are selected: MNIST, SVHN and CIFAR1O. More experiments are presented in Appendix C.
5.1 UNINFORMATIVE PRIORS
As discussed in the introduction, BALD is sensitive an uninformative prior, i.e. p(Do)0). We thus initialize Do from a fixed class of the tested dataset to observe its acquisition performance. Figure presents the prediction accuracies of BALD with acquisition budget of 130 over the training

---

Under review as a conference paper at ICLR 2021
set of MNIST, in which randomly select 20 samples from the digit "0' and 'I' initialize Do. respectively. The classification model of AL follows a convolutional neural network with one block of [convolution, dropout, max-pooling, relu]. with 32, 3x3 convolution filters, 5x5 max pooling, and 0.5 dropout rate. In the AL loops, we use 2,000 MC dropout samples from the unlabeled data pool to fit the training of the network following (Kirsch et al.! 2019).
The results show BALD can slowly accelerate the training model due to biased initial ac- quisitions, which cannot uni-
Accrecy
Accuncty
formly cover all the label cat- egories. Moreover, the unin- formative prior guides BALD to unstable acquisition results. As the shown in Figure 3(b), BALD with Bathsize = 10 shows better performance than that of Batchsize =1; while Figure 3: Acquisitions with uninformative priors from digit 'O' and BALD in Figure 3(a) keeps sta- '1'.
Burden Samplnn
SALD 288
GBALD Seg
C86- Seesence
Acquired datasel
Acquired
(a) Digit '0'
(b) Digit 'I'
ble performance. This is because the initial labeled data does not cover all classes and BALD with Batchsize =1 may further be misled select those samples from one few fixed classes at the first acquisitions. However, Batchsize >1 may result in a random acquisition process that possibly covers more diverse labels its first acquisitions. Another excursive result of BALD is that the increasing batch size cannot degenerate its acquisition performance in Figure 3(b). Specifically, Batchsize =10> > Batchsize =1 Batchsize =20,40 > Batchsize =30, where '>' denotes 'better' performance; Batchsize 20 achieves similar results of Batchsize =40. This undermines the acquisition policy of BALD: its performance would degenerate when the batch size inereases, and sometimes worse than random sampling. This also is the reason why utilize core-set to start BALD in our framework.
Different to BALD, the core-set construction of GBALD using Eq. (11) provides complete label matching against all classes. Therefore, it outperforms BALD with the batch sizes of 1, 10, 20, 30, and 40. As the shown learning curves in Figure 3, GBALD with batch size of and sequence size of 10 (i.e. breakpoints acquired size are 10, 20, 130) achieves significantly higher accuracies than BALD using different batch sizes since BALD misguides the network updating using poor prior.
5.2 IMPROVED INFORMATIVE ACQUISITIONS
Repeated or similar acquisitions delay the acceleration of the model training of BALD. Fol- lowing the experiment settings of Section 5. we compare the best performance of BALD with a batch size of 1 and GBALD with different batch size parame- ters. Following Eq. (14), we set b (3.5, 7) and b'=1, respec- tively, that means, we output the highest representative data from batch of highly-infrrmaive. acquisitions. Different settings on and D' are used to observe the parameter perturbations of GBALD.
CIALO bettoiced
Acqured catasetsize
Acquired datasetiszze
(a) Digit '0'
(b) Digit '1'
Figure 4: GBALD outperforms BALD using ranked informative acquisitions which cooperate with representation constraints.
Training by the same parameterized CNN model as Section 5.1, Figure presents the acquisition performance of parameterized BALD and GBALD. As the learning curves shown, BALD cannot accelerate the model as fast as GBALD due to the repeated information over the acquisitions. For GBALD, it ranks the batch acquisitions of the highly highly-informative samples and selects the highest representative ones. By employing this special ranking strategy, GBALD can reduce the probability of sampling nearby data of the previous acquisitions. It is thus GBALD significantly outperforms BALD, even we progressively increase the ranked batch size b.
7

---

Under review as a conference paper at ICLR 2021
Accurncy
Accusay
8
VIIAATIS 2011
DALD BALD.
Bakhubent
BALO BelrnisenGI
BALD Rarrec
GBALD.BU2TSEa
DIAALO BOXTAAA00O
1906
Acquied dacaset size
Acquired datasetsize
Acquined dataset
(a) MNIST
(b) SVHN
(c) CIFARIO
Figure 5: Active acquisitions MNIST, SVHN and CIFARIO datasets.
Table 1: Mea of the test accuracies of the breakpoints of the learning curves MNIST, SVHN, and CIFAR-10.
Algorithms
Datasets
Var
BALD
Entropy
k-medoids
k-centers
GBALD
MNIST
0.8419= 0.1721 0.8645 1909 0.8498#0. 2098 0.8785=0. 1433 0.8052=0. 1838 0.9106=0.1 1.666 0.853520.1098 0.8510=0. 1160 0.8294.0.144 1415 0,8498=0. 1294 0.7909=0. 1235 0.8885=0.1054
SVHN
CIFAR-10 10
0.7122+0.1033 0.6760#0. 1023 0.6536#0. 1038 0.71837=0. 1245 0.5890=0. 1758
0.7440=0. 1087
5.3
ACTIVE ACQUISITIONS
GBALD using Eqs. (11) and (14) has been demonstrated achieve successful improvements over BALD. We thus combine these two components into a uniform framework. Figure 5 reports the AL accuracies using different acquisition algorithms the three image datasets. The selected baselines follow (Gal et al. 2017) including 1) maximizing the variation ratios (Var), 2) BALD, 3) maximizing the entropy (Entroyy), 4) k-medoids, and one greedy 5) k-centers approach (Sener & Savarese 2018). The network architecture is a three-layer MILP with three blocks of [convolution, dropout, max-pooling, relu], with 32, 64, and 128 3x3 convolution filters, 5x5 max pooling, and 0.5 dropout rate. In the AL loops, the MC dropout still randomly samples 2,000 data from the unlabeled data pool to approximate the training of the network architecture following (Kirsch al. 2019). The initial labeled data of MNIST, SVHN and CIFAR-10 10 are 20, 1000, 1000 random samples from their full training sets. Details of baselines are presented in Appendix C.I.
The batch size of the compared baselines is 100, where GBALD ranks 300 acquisitions to select 100 data for the training, i.e. b 300, D' 100. As the learning curves shown in Figure 1) k-centers algorithm performs more poorly than other compared baselines because the representative optimization with sphere geodesic usually falls into the selection of boundary data: 2) Var, Entropy and BALD algorithms cannot accelerate the network model rapidly due to highly-skewed acquisitions towards few fixed classes at its first acquisitions (start states); 3) k-medoids approach does not interact with the neural network model while directly imports the clustering centers into its training set; 4) The accuracies of the acquisitions of GBALD achieve better performance at the beginning than the Var, Entropy and BALD approaches which fed the training of the network model via acquisition loops. In short, the network is improved faster after drawing the distribution characteristics of the input dataset with sufficient labels. GBALD thus consists of the representative and informative acquisitions in its uniform framework. Advantages of these two acquisition paradigms are integrated and present higher accuracies than any single paradigm.
Table reports the mean val- ues of the test accuracies of the breakpoints of the learning curves in Figure 5, where breakpoints of
Table 2: Number of acquisitions on MNIST, SVHN and CIFAR10 until 70%, 80%, and 90% accuracies are reached.
MNIST are (0, 10, 20, 30,..... 600),
Algorithms
Accuracies
breakpoints of SVHN are (0, 100, 200, 10000).
Var
140/1,300/5,700 700
15002.2000-20.000
2100-10.00056, 100
and
120/223000=200.00
190/7,100 >00,000
Entropy
1101,5000111
1,200
150/2,4005-200000
breakpoints of CIFARIO (0, 100, 200 200, 20000). We then calculate their average accuracies and std values over these acquisition
k-modoids
70/1.
90/2.200V16.000
k-centers
110/2,000100 100
150Y3 8000-20,00000000
2300=10.0000-20000
GBALD
00/1,400/48800
70/1,90012,2000
170/3,9000520.000
points. As the shown in Table 1, all std values around 0.1, yielding norm value. Usually, average
8

---

Under review as a conference paper at ICLR 2021
accuracy same acquisition size with different random seeds of DNNs, will result small std value. Our mean accuracy spans across the whole learning curve.
The results show that 1) GBALD achieves the highest average accuracies; k-medoids is ranked the second amongst the compared basclines; 2) k-centers has ranked the worst accuracies amongst these approaches; 3) the others, which iteratively update the training model are ranked at the middle including BALD, Var and Entropy algorithms. Table 2 shows the acquisition numbers of achieving the accuracies of 70%, 80%, and 90% on the three datasets. The three numbers of each cell are the acquisition numbers over MNIST, SVHN, and CIFAR 10, respectively, The results show that GBALD can use fewer acquisitions achieve desired accuracy than the other algorithms.
5.4 GBALD vs. BATCHBALD
Batch active deep learning was recently proposed accelerate the training of DNN model. In recent literature, BatchBALD (Kirsch et al., 2019) extended BALD with batch acquisition setting to converge the network using fewer iteration loops. Different to BALD, BathBALD introduces diversity to avoid repeated or similar output acquisitions.
How to set the batch size of the acquisitions attracted our eyes before starting the experiments. It involves with whether our experiment settings are fair and reasonable. From theoretical view, the larger the batch size, the worse the batch acquisitions will be. Experiments results of (Kirsch et al. 2019) also demonstrated this phenomenon. We thus set different batch sizes to run BatchBALD, Figure 6 reports the comparison results of BALD, BatchBALD, and our pro- posed GBALD following the experiment settings of Section 5.3. As the shown in this figure, BatchBALD degenerates the test accuracies if we progres- sively increase the bath sizes, where BatchBALD with batch size of 10 keeps similar learning curves as BALD. This means BatchBALD actually can accelerate BALD with a similar acquisition result if the batch size is not large. That means, if the batch size is between 2 to 10, BatchBALD will degenerate into BALD and maintains highly-consistent results.
ACCUFC))
BALD Satchita
Battritee BarrBBALD
BusHHAALD wwwp//tcesss
Also because of this, BatchBALD has the same sensitivity to the uninformative prior. For our GBALD, the core-set solicits sufficient data which properly matches the input distribution (w.rt. acquired data set size S 100), providing powerful input features
Acquird dataset size
Figure 6: Comparisons of BALD, Batch- BALD, and GBALD of active acquisi- tions on MNIST with bath settings.
start the DNN model (w.r.t.
acquired data set size > 100). Table then presents the mean of breakpoints (f0, 10, 10,20,... 600)) of active acquisitions on MNIST with batch settings. The statistical results show GBALD has much higher mean accuracy than BatchBALD with different bath sizes. Therefore, evaluating the model uncertainty of DNN using sighly-representative core-set samples improve the performance of the neural network.
6 CONCLUSION
Table 3: Meanastd of BALD, BatchBALD, and GBALD of active acquisitions on MNIST with batch settings.
We have introduced a novel Bayesian AL frame- work, GBALD, from the geometric perspective, which seamlessly incorporates representative (core-set) and informative (model uncertainty estimation) acquisitions to accelerate the train- ing of a DNN model. Our GBALD yields sig- nificant improvements over BALD, flexibly re- solving the limitations of an uninformative prior and redundant information by optimizing the acquisition on an ellipsoid. Generalization anal- ysis has asserted that training with ellipsoid has tighter lower error bound and higher probability to achieve a zero error than training with a typical sphere. Compared to the representative informative acquisition algorithms, experiments show that our GBALD spends much fewer acquisitions to accelerate the accuracy. Moreover, it keeps slighter accuracy reduction than other baselines against repeated and noisy acquisitions.
Algorithms
Batch sizes
Accuracies
BALD
1
0.865420.0354
BatchBALD
10
0.8645=0.0366
Batc
40
0.8273
BatchBALD
100
0.7902=0.099
GBALD
3
0.9106=0.1299

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds, In International Conference on Learning Representations, 2019.
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov, Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations, 2019.
Mihai Bădoiu, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceed- ings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 250-257, 2002.
Shai Ben-David and Ulrike Von Luxburg. Relating clustering stability to properties of cluster boundaries. In 2 Annual Conference on Learning Thheory (COLT'2008), pp. 379-390. Omnipress, 2008.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In International Conference on Machine Learning, pp. 1613-1622, 2015.
Trevor Campbell and Tamara Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In International Conference on Machine Learning pp. 698-706, 2018.
Trevor Campbell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. The Journal of Machine Learning Research, 20(1):551-558 2019.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221 1994.
Arnaud Doucet, Simon Godsill, and Christophe Andrieu. On sequential monte carlo sampling methods for bayesian filtering, Statistics and computing, 1063):197-208, 2000.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference on Machine Learning-Voi Volume 70, pp. 1183-1192. JMLR. org, 2017.
Mingfei Gao, Zizhao Zhang, Guo Yu, Serean Arik, Larry Davis, and Tomas Pfister. Consistency- based semi-supervised active learning: Towards minimizing labeling cost. ECCV, 2020.
Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal bayesian active learning with noisy observations. In Advances in Neural Information Processing Systems, pp. 766-774, 2010.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pp. 8527-8537, 2018
Sariel Har-Peled and Soham Mazumdar, On coresets for k-means and k-median clustering, In Proceedings of the thitty-sixth annual ACM symposium on Theory of computing, pp. 291-300, 2004.
Neil Houlsby, Ferene Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning, arXiv preprint arXiv:1112.5745 2011.
Khaled Jedoui, Ranjay Krishna, Michael Bernstein, and Li Fei-Fei. Deep bayesian active learning for multiple correct outputs. arXiv preprint arXiv: 2019.
Andreas Kirsch, Joost Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning. In Advances in Neural Information Processing Systems, pp. 7024-7035, 2019.
10

---

Under review as a conference paper at ICLR 2021
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in neural information processing systems. pp. 6402-6413. 2017.
Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa. Differentiating through the frechet mean. ICML, 2020.
Feiping Nie, Hua Wang, Heng Huang, and Chris Ding. Early active learning via robust representation and structured sparsity. In Twenty-Thire International Joint Conference on Artificial Intelligence, 2013.
Michael Oshome, Roman Garnett, Zoubin Ghahramani, David K Duvenaud, Stephen J Roberts, and Carl E Rasmussen. Active learning of model evidence using bayesian quadrature. In Advances in neural information processing systems, pp. 46-54, 2012.
Hae-Sang Park and Chi-Hyuck Jun. simple and fast algorithm for k-medoids clustering, Expert systems with applications, 36(2):3336-3341, 2009.
Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobato. Bayesian batch active learning as sparse subset approximation. Advances Neural Information Processing Systems, pp. 335666367, 2019.
Harold J Price and Allison R Manson. Uninformative priors for bayes' theorem. In AIP Conference Proceedings, volume 617, pp. 2002.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through monte carlo estimation of error reduction. ICML, Williamstown, pp. 441 448, 2001.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL
net
Rodney W Strachan and Herman K Van Dijk. Bayesian model selection with uninformative prior. Oxford Bulletin of Economics and Statistics, 65:863-876, 2003.
Min Tang, Xiaoqiang Luo, and Salim Roukos. Active learning for statistical natural language parsing. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pp- 120-127. Association for Computational Linguistics, 2002.
Stephen A Vavasis. Approximation algorithms for indefinite quadratic programming. Mathematical Programming, 57(1-3):279-311 1992.
Zengmao Wang, Bo Du Weiping Tu, Lefei Zhang, and Dacheng Tao. Incorporating distribution matching into uncertainty for multiple kernel active learning. IEEE Transactions Knowledge and Data Engineering, 2019.

---

Under review as a conference paper at ICLR 2021
A. TWO-STAGE GBALD ALGORITHM
The two-stage GBALD algorithm is descrihed follows: 1) construct core-set ellipsoid (Lines 3 to 13), and 2) estimate model uncertainty with a deep learning model (Lines 14 to 21). Core-set construction is derived from the max-min optimization geodesic w.r.t. Eq. (11), where yields a geometric probability model w.r.t. Eq. (5). Importing the core-set into Du derives the deep learning model to return informative acquisitions one time, where 8 yields deep learning model. Ranking those samples, we select D' samples with the highest representations as the batch outputs. The iterations of batch acquisitions stop until its budget exhaust. The final update on Do is our acquisition set of AL..
Eq. (10), then updated with ellipsoid
Details of the hyperparameter settings are presented Appendix C.6.
Algorithm 1: Two-stage GBALD Algorithm
Input:
Data set X' core-set size NM, batch returns b, batch output H' iteration budget A. Initialization: a 0, core-set M < Ø.
Stage ! begins:
Initialize to yield a geometric probability model w.r.t. Eq. (5).
Perform k-means to initialize U to Do.
Core-set construction begins by acquiring x;" for i 1,2, NM do
x.- - arg D, minD,eD, |15o (lb--l e|( logp(uilss,0) 0)) where
Co Σ Eg [u 0) H[br|2,,,21]]
Ellipsoid geodesic line scales wf: x arg min min, (og - -(====)))) mx)]
Update x. into core-set M: M x7 M.
11
Update N -N--L
12 end
Import core-set to update Do: Do Mul', where U' updates each element of 72 into their nearest samples in X.
Stage 2 begins: Initialize to yield a deep learning model.
15
16 while AA do
17
Return informative deep learning acquisitions in one budget:
{ x2,,,.,, arg max H[][Do] Eu-r((): H[0]æ, Do]] Rank D' informative acquisitions with the highest geometric representativeness: { 1..,,..266 x.,,,,,,,,) arg max effe( .......g) p( 0).
18
Update {2t, :..; Ni into Do: Do + Du (z/ .... 27
19
29
++1+.
21 end
22 Output: final update on Do.
B. GENERALIZATION ERRORS OF GEODESIC SEARCH WITH SPHERE AND ELLIPSOID
Optimizing with ellipsoid geodesic linearly rescales the spherical search on tighter geometric object. The inherent motivation is that the ellipsoid can prevent the updates of core-set towards the boundary regions of the sphere. This section presents generalization enror analysis from geometry, which provides feasible error guarantees for geodesic search with ellipsoid, following the perceptron analysis. Proofs are presented in Appendix D.
12

---

Under review as a conference paper at ICLR 2021
B.1 ERROR BOUNDS OF GEODESIC SEARCH WITH SPHERE
Given a perceptron function / := W1X1 + W2X2 + Wa. the classification task is over two classes A and B embedded in three-dimensiona geometry. Let SA and SB be the spheres that tightly cover A and B. respectively, where SA is with a center and radius Ra, and SB is with a center Co and radius Rg. Under this setting, generalization analysis presented.
Theorem 1, Given a linear perceptron function = W1X1 W22X2 Wg that classifies A and B, and a sampling budget k. with representation sampling over S and SR, the minimum distances to the boundaries of S and Sn of that representation data are defined as da and da, respectively. Let err err(h, k) be the classification error rate with respect to h and k, I = -arcsin Ra-da we then have an inequality of error:
Ra
4R
(2R, + (Ru - +2)2
4R (2Rg (R k22
1
min
<er((h,k)
4R + 4R)
4R2
4R
K
where ly
R2
2n
4x
27
R
2x
472
T P
2753
Pk
22k- 3k
- c0ss xp )m R
4m Rm
3k
f/
RE
3
+
25r
4n
27
R
2n
4
T
27
R
and u4g = (2h-1
3k
1 cos xI T
3k
B.2 ERROR BOUNDS OF GEODESIC SEARCH WITH ELLIPSOID
Given class A and B are tightly covered by ellipsoid E. and Es in three-dimensional geometry. Let Ra, be the polar radius of E.. (Ray Ras) be the equatorial radii of Eg. Rs be the polar radius of Eg. and ( Roy Rb,] be the equatorial radii of Fs, the generalization analysis is ready to present following these settings.
Theorem 2. Given a linear perceptron function = W1x1 W2X2 + Wg that classifies A and B, and a sampling budget with representation sampling over Eg and Es, the minimum distance to the boundaries of Ea and E, of that representation data are defined as da and dæ, respectively. Let err(h,k) k) be the classification error rate with respect to h and k, I arrsinn Ra-ds we then have an R.
&
inequality of error:
4 41, R., (2R.; >Ro; -Xx)² 411, Rd, -(2Rs, XRs, x0)²
1
min
<err(h,k)
411: Ra, + 11, Rb:
411, Rs, + 4 111 Ra:
where i 1,2,3, 2 =
R2
+
0k +
n R
2m
dk
1x
Rg
Ok
2k-4
RRa 2G
n II, Ra.
4t II. Rog
X
R
dk
2 R
and
3k
3
2n
27
2n
18
27
o
2k-4
RRg,
π II:
Rs;
4m II.
Ray
3k
24p
3k
B.3 PROBABILITY BOUNDS OF ACHIEVING ZERO GENERALIZATION ERROR
Let Pr[err(A (h, k) 0] and Pr[err (h, k)) = O be the probabilities of achieving a zero generalization eтror of geodesic search with sphere and ellipsoid, respectively, we present their inequality relationship.
Theorem 3. Based on 7-tube theory (Bvi- & Von Luxburg 2008) of clustering stability, the probability of achieving a zero generalization error of geodesic search with ellipsoid can be defined as the volume ratio of Vol(Tube) Vol(Spherc) Then, we have:
Pr[err(h, (h, k) = O]Sphere 1
13

---

Under review as a conference paper at ICLR 2021
where ty keeps consistent with Theorem 1.
Theorem 4. Based on 7-tube theory (Ben-David & Von Luxburg 2008 of clustering stability, the probability of achieving zero generalization error of geodesic search with ellipsoid can be defined Vol(Tube) Then, we have:
as the volume ratio of Vol(E]iissodd)
Aks AM,,A,, Ake
Pr[err(h,, k) Ellipsoid
Rui Ruz Ras
where Ak.
n2
x
nt
2
x ng
and ok. = =(2
(2k-4
2
As
27
2x
4n
27a
3k
TRa, 2p
) It Rai Raz Ras
1x Rs, Rog Rbg
1,2.3.
3k
B.4 MAIN THEORETICAL RESULTS OF GEODESIC SEARCH WITH ELLIPSOID
TIGHTER LOWER ERROR BOUND
Let lower[eree [err (h, k) ISphere and lower[err(s (he k) Ellipsood be the lower bounds of the generalization errors of geodesic search with sphere and ellipsoid, respectively. With Ray < Ra, compare Theorem I and Theorem 2, we have the following proposition.
Proposition! Given a linear perceptron function h W1X1 + W2X2 + W3 that classifies and B, and sampling budget k. With representation sampling over Sa and Sa, let orr(h, k) be the classification error rate with respect to h and k, the lower bounds of geodesic search with sphere and ellipsoid satisfy: lower[ery erreterr((e (h, k) Ellipsoid lower[erry err(h, k) Sphere-
HIGHER PROBABILITY OF ACHIEVING A ZERO ERROR
Let Pr[err(Ht (h, k)
OJ Sphere and Pr[err (h, k) 0] Ellipsoid be the probabilities of achieving zero generalization error of geodesic search with sphere and ellipsoid, respectively. Their relationship is presented in Proposition! 2.
Proposition 2. Given a linear perceptron function h WIx1 + W2X2 + Ws that classifies A and B. and sampling budget k. With representation sampling over E. and Es. let err(h, b, k) be the classification error rate with respect to h and k. the probabilities of geodesic search with sphere and ellipsoid satisfy: Pr[err(h,,, = Ellipsnid Pr[err(h, k)) S]Sperre-
With these theoretical results, geometric interpretation of geodesic search over ellipsoid is more effective than sphere due to tighter lower error bound and higher probability to achieve zero error. Theorems and 7 of Appendix D then present high-dimensional generalization for the above theoretical results in terms of the volume functions of sphere and ellipsoid.
C. EXPERIMENTS
C.I BASELINES
To evaluate the performance of GBALD, several typical baselines from the latest deep AL literatures are selected.
Bayesian active learning by disagreement (BALD) (Houlsby al. 2011). has been introduced in Section 3.
The algorithm chooses the unlabeled data that maximizes its variation ratio of the probability:
Maximize Variation Ratio (Var) (Gal et al. 2017).
x= arg max max Pr(vl, (v))) yey
(15)
zeDr
Maximize Entropy (Entropy) Gal al. 2017). The algorithm chooses the unlabeled data that maximizes the predictive entropy:
x² arg max
{
Σ BEy
Pr(y/æ, Do)) (Pr(yle, (P()))::Do))
(16)
D.
14

---

Under review as a conference paper at ICLR 2021
Table 4: Mean+std of active acquisitions on SVHN with 5,000 and 10,000 repeated samples.
Accuracies
Algorithms
repeated samples
5,000 repeated samples
10,000 repeated samples
Var
0.8535
0.8478#0.107.
0,,28810,1000 0.7689=0.1288 0.8630
BALD
0.85 1551000.1100 0.8885=0.1054
188119001121 0.8694=0.1032
GBALD
k-modoids (Park & Jun 2009). A classical unsupervised algorithm that represents the input distribution with &s clustering centers:
{zj 2j...., 22} arg min Fi.......
Σ
Σ
|x - zill
(17)
== 2
where x denotes the k-th subcluster centered with 2;, and 2, E X, Ví..
Greedy k-centers (k-centers) (Sener & Savarese 2018 A geometric core-set interpretation sphere. See Eq. (4).
BatchBALD (Kirsch al., 2019). A batch extension of BALD which incorporates the diversity, not maximal entropy as BALD, to rank the acquisitions:
(5) Pup oig) arg max H(yt, - Vt.) Eppe)p)) (H(y))s---B)) (0)]
(18)
where H( ((..,,...,, Bt.) denote the expected entropy over all possible labels from V/b
and E EprorD.) H[ (t, [0)] is estimated by MC sampling (Roy & McCallum (0001 (Osborne) et al. 2012) a subset from X which approximates the parameter distributions of
Mt, such that H(Vt.....,,h,,
(yta. -t -I- (l
The parameter settings of Eq. (5) are Ro = 2.0e + 3 and 17 =0.9. Accuracy of each acquired dataset size of the experiments are averaged over 3 runs.
C.2 ACTIVE ACQUISITIONS WITH REPEATED SAMPLES
Repeatedly collecting samples in the establishment of database is very common. Those repeated samples may be continuously evaluated as the primary acquisitions of AL due the lack of one or more kinds of class labels. Meanwhile, this situation may lead the evaluation of the model uncertainty to fall into repeated acquisitions. To respond this collecting situation, we compare the acquisition performance of BALD, Var, and GBALD using 5,000 and 10,000 repeated samples from the first 5,000 and 10,000 unlabeled data of SVHN, respectively. In addition, the unsupervised algorithms which do not interact with the network architecture, such k-medoids and k-centers, have been shown that they cannot accelerate the training in terms the experiment results Section 5.3. Thus, we are longer studying their performance. The network architecture still follows the settings of the MLP as Section 5.3.
The acquisition results over the repeated SVHN datasets presented in Figure 7. The batch sizes of the compared baselines are 100, where GBALD ranks 300 acquisitions to select 100 data for the training, i.e. b 300, b' 100. The mean values of these baselines of the breakpoints (i.e. (0, 100, 200, .... 10000}) are reported in Table 4. Results demonstrate that GBALD shows slighter perturbations on repeated samples than Var and BALD because it draws the core-set from the input distribution as the initial acquisition, leading small probability to sample from one or more fixed class. In GBALD, the informative acquisitions constrained with geometric representations further scatter the acquisitions spread in different classes. However, Var and BALD algorithms have no particular schemes against the repeated acquisitions. The maximizer on the model uncertainty may be repeatedly produced by those repeated samples. In additional, the unsupervised algorithms such as k-medoids and k-centers don not have these limitations, but cannot accelerate the training since there has interactions with the network architecture.
15

---

Under review as a conference paper at ICLR 2021
03
Accuracy
Accuracy
08
BAth. 0 Recaphors
SBALD Aet.D.etttsss3. Recepicts
Eachstet--1000 5E00 Receptinss
Recepiiess
GBALD Bit.stttttttt100000 Receptats
Vor E0thittte-000, 100CEC Receptonss
BALD, 100000 Receplaess
SSALDD.Atttse=3311100000 Receptans
C1
1800
Acquird dize
Acquired dataset size (b) BALD
Acquired datasetsze
(a) Var
GBALD
Figure 7: Active acquisitions on SVHN with 5,000 and 10,000 repeated samples.
Accurccy
Accuracy
Accuracy
08
35
VarBaKts 22-001 5es
BALD BethhbeeDD Kolee
00
Var8stth 3000 Noses
BALD Daldhie=DD 5200 Nobes
Batths 3000 Moses
YarBakts 20-001 100000 Nes
02
BALD 120000
02
88ALD, 100000 Va
#08 Acquired datasetsire
2000
400
1980
Acquired date
Acquired dataset
(a) Var
(b) BALD
(c) GBALD
Figure 8: Active noisy acquisitions SVHN with 5,000 and 10,000 noisy labels.
C.3 ACTIVE ACQUISITIONS WITH NOISY SAMPLES
Noisy labels (Golovin et al. 2010) (Han al.) 2018 inevitable due human errors in data annotation. Training on noisy labels, the neural network model will degenerate its inherent properties. To assess the perturbations of the above acquisition algorithms against noisy labels, organize the following experiment scenarios: we select the first 5,000 and 10,000 samples respectively from the unlabeled data pool of the MNIST dataset and reset their labels by shifting {'0', ' ,..., '8'3 to ("1',2",,... ...., '9'}, respectively. The network architecture follows MLP of Section 5.3. The selected "".,""""..,,''',,,
baselines are Var and BALD.
Figure 7 presents the acquisition results of those baseline with noisy labels. The batch sizes of the compared baselines are 100, where GBALD ranks 300 acquisitions select 100 data for the training, i.e. b 300, b' = 100. Table presents the mean values of the breakpoints (i.e. (0, 100, 200, ..., 10000)) over learning curves of Figure 8. The results further show that GBALD has smaller noisy perturbations than other baselines. For Var and BALD, model uncertainty leads high probabilities to sample those noisy data due to their greatly updating on the model.
C.5 ACCELERATION OF ACCURACY
Accelerations of accuracy i.e. the first-orders of breakpoints of the learning curve, describe the efficiency the active acquisition loops. Different to the accuracy curves, the acceleration curve reflects how active acquisitions help the convergence of the interacting DNN model.
16

---

Under review as a conference paper at ICLR 2021
Table 5: Mean=std of active noisy acquisitions on SVHN with 5,000 and 10,000 noises.
Accuracies 5,000 noises
Algorithms
noises
10,000 noises
Var
0.8535
0.7980
0.7702
BALD
0.85 10=00.1116
0.8205
0.7849:0.. 0.8301:0.0916
GBALD
0.8855=0.1054
0.8622:
We thus firstly present the acceleration curves of different baselines MNIST, SVHN, and CIFARIO datasets following the experiments of Section 5.3. The acceleration curves of active acquisitions of different algorithms clearly finds
drawn in Figure 9. Observing those acceleration that, GBALD always keeps higher accelerations of accuracy than the other baselines against the three benchmark datasets. This revels the reason of why GBALD can derive more informative and representative data to maximally update the DNN model.
The acceleration curves of active acquisitions with repeated samples Appendix C.2 are presented in Figure 10. As the shown in this figure, GBALD presents slighter perturbations to the number of repeated samples than that of Var and BALD due to its effective ranking scheme on optimizing model uncertainty of DNN. The acceleration curves of active noisy acquisitions of Section Appendix C.3 are drawn Figure 11. Compared Figure 7, it presents more intuitive descriptions for the noisy perturbations to different baselines. With horizontal comparisons to acceleration curves of Var and BALD, our proposed GBALD has smaller noisy perturbations due to 1) the powerful core-set which properly captures the input distribution, and 2) highly representative and informative acquisitions of model uncertainty.
Var6ab76Re-000
11
BALD Bathikest
014
BALD Batz tibe-100
Accoleration acccracyy
Baxhaee
dedadds
Acceleration retionaionoooo aaccrrac
612
mettils
Acceleration of accuracy
Entopy.Bathsieesly
kedeaas
GBALD GBALD Betthsbee)
SBALD Bachsize-000
6.8
034
0.2
600
200
Acquired dataset size
Acquired datase: size
Acquired datasetsize
(a) MNIST
(b) SVHN
(c) CIFARIO
Figure 9: Accelerations accuracy of different baselines on MNIST, SVHN, and CIFARIO datasets.
Vax Eot.hbeeUU0,,,. Reccstiosss Bithhtehhbe 500C Recestens
BALD taztsi Resepters
GBALD Baxhhir=1100, Recepties
BALD 100ee00- 5000 Racoptons
GBALD Baxhsize=00.. 5200 Recepizes
Acceleration of accuracy
Vart Eattheee-000 100000 Receptioss
Acceleration of accuracy
BALD Bazz rste-1tt. 200000 Reception
Acceteration of accuracy
GBALD Baxhiir--0C, 133230 Receptons
g
Ss
2000
1300
30K
X08K
500
180
1000
2300
.300
3000
3009
1839
Acquired dataset (a) Var
Acquired dataset
Acquired dataset
(b) BALD
(c) GBALD
Figure 10: Accelerations of accuracy of active acquisitions SVHN with 5,000 and 10,000 repeated samples.
17

---

Under review as a conference paper at ICLR 2021
voskatheeee411, 1 Moses
Buth,attiii- 2 Nelsss
GBALD ce Meñes
VorBakteies111,
GE 5000 Nekee
Acceleration of Accuracy
warsanthooe033,, 203333 Nobas
Acceleration Accuracy
BALL,,attstte--l (30000 Molses
Acceleration of accuracy
201 (030000 Noilss
15
6-
E080 Acquired dalaset size
300
2000
200
4000
5000
3000
1303
Acquired dataset
Acquired dalaset
Var
(b) BALD
GBALD
Figure 11: Accelerations of accuracy of active noisy acquisitions on SVHN with 5,000 and 10,000 noisy labels.
Table 6: Relationship of accuracies and sizes of core-set on SVHN.
Accuracies Ultimate accuracy
Size of core-set
Start accuracy
Mean accuracy
NM 1,000
0.8790
0.9344
0.913420.0169
NM 2,000
0.8898
0.9212
0.9151
NM = 3,000
0,8848
0.9364
0.9173=0.0138
NM = 4,000
0,8811
0,9271
0.9146=0.0165
NM 5,000
0.8959
0.9342
0.9197=0.0117
C.6 HYPERPARAMETER SETTINGS
What is the proper time to start active acquisitions using Eq. (14) in GBALD framework? Does the ratio core-set and model uncertainty acquisitions affect the performance of GBALD?
We discuss the key hyperparameter of GBALD here: core-set size NM- Table 6 presents the relationship of accuracies and the sizes of core-set, where the start accuracy denotes the test accuracy over the initial core-set, and the ultimate accuracy denotes the test accuracy training data. Let b = 1000, 6' 500 in GBALD, NM be the number of the core-set size, the iteration budget A of GBALD then can be defined A (Q NM) For example, the number of the initial core-set labels are set as NM 1, 000,, we have A (Q- -NxiUU x 38; if NM = 2, 000, then A (Q-NM)/Bb 36.
up to 20, 000
From Table 6, GBALD algorithm keep stable accuracies over the start, ultimate, and mean accuracies when there inputs more than 1.000 core-set labels. Therefore, drawing sufficient core-set labels using Eq. (10) to start the model uncertainty of Fq. (14) can maximize the performance of our GBALD framework.
Hyperparameter settings on batch returns and bath outputs V. Experiments of Sections 5.1 and 5.2 used different and to observe the parameter perturbations. No matter what settings of i/ and b are, GBALD still outperforms BALD. For single acquisition of GBALD, we suggest b = and 8' = 1. For bath acquisitions, the settings on b' and are dser-eefined according the time cost and hardware resources.
Hyperparameter setting on iteration budget A. Given the acquisition budget Q, let b' be the number of the output returns at each loop, .&M be the number of the core-set size, the iteration budget A of GBLAD then can be defined as A (Q NM)
Other hyperparameter settings. Eq. (5) has parameter R, which describes the geometry prior from probability. The default radius of the intern balls Rg is used to legalize the prior and has no further influences on Eq. (10). It is set Rg 2.0e for those three image datasets. Ellipsoid
18

---

Under review as a conference paper at ICLR 2021
geodesic is adjusted by 7 which controls how far of the updates of core-set to the boundaries of the distributions. is set as = 0.9 in this paper.
C.7 TWO-SIDED 1-TEST
We present two-sided (two-tailed) (-test for the learning curves of Figure 5. Different to the mean std of Table 1, I-test can enlarge the significant difference of those baselines. typical f-test, the two groups of observations usually require degree of freedom smaller than 30. However, the numbers of breakpoints of MNIST, SVHN, and CIFARIO I0 are 61, 101, and 201, respectively, thereby holding degree of freedom of 60, 100, 200, respectively. It is thus we introduce t-test score to directly compare the significant difference pairwise baselines.
t-test score between any pair group of breakpoints defined as follows. Let B1 {a1, 02 ... an) and B₂ (31,82.. B. there exists t-score
v σ
score
where === Ei (a: Bi), and o n-1 E (a; B: -2))
In two-sided t-test, B1 beats B2 on breakpoints and 8r satisfying a condition of t- score > D; B2 beats B| on breakpoints a; and 8, satisfying condition of score -v, where v denotes the hypothesized criterion with given confidence risk. Following (Ash et al. 2019), add penalty 2
of _ to each pair of breakpoints, which further enlarges their differences in the aggregated penalty matrix, where denotes the number of B1 beats B2 on all breakpoints. All penalty values finally calculate their L1 expressions.
Figure 12 presents the penalty matrix over learning curves of Figure 5, Column-wist values at the bottom of each matrix show the overall performance of the compared baselines. As the shown results, GBALD has significant performances than that of the other baselines over the three datasets. Especially for SVHN, it has superior performance.
BALD
Eainpy
Amedols kentass
OBAL3
BALD
Jonder GIALD
BALD
Jeadods bosten GEALD
VSr
kM
101
V5r
336
BALD
Earpy
Eatrpy
boatees
Forber
1358
14271
21110
GEALD
1115
1100
1033
E273
1393
5112
4.500
8300
(a) MNIST
(b) SVHN
(c) CIFARIO
Figure 12: A pairwise penalty matrix over active acquisitions on MNIST, SVHN, and CIFAR 10. Column-wise values the bottom of each matrix show the overall performance of the compared baselines (larger value has more significant superior performance).
D. PROOFS
We firstly present the generalization errors k of AL with sphere as case study. The assumption of the generalization analysis is described in Figure 13.
19

---

Under review as a conference paper at ICLR 2021
Qa
qb q"
cut C
h
d
Figure 13: Assumption of the generalization analysis. The ball above denotes S.. the ball below denotes Sg, and Rs Ra. Spherical cap' of the half-sphere of Sa is denoted as D.
D.1 CASE STUDY OF GENERALIZATION ANALYSIS OF err(h, OF GEODESIC SEARCH WITH SPHERE
Theorem 5, Given a linear perceptron function W1x1 W222 + Wg that classifies and B, and a sampling budget k. With representation sampling over Sa and Sb, the minimum distance to the boundaries of SA and SB of that representation data are defined as dg and dg, respectively. Let err (h, k) be the classification error rate with respect to h and k. arcsin Ru we have an inequality of error:
R.
(2Rg +t) t)2 (2),+t)(Ro +t)² 4Rg
min
<err(h,,) 0.3334,
4R2 + 4R2
4R
where
n2 3
t" R2
1 ! c00 4x
2m
27
2T
27
R
R
and p cos of )z Rij
AnR²
27
4n
27
Proof. Given the unseen acquisitions of (qus qo 9²}, where qa A, q B, and q² A or B is uncertain. However, the position of q" largely decides h. Therefore, the proof studies the error bounds highly related q² terms of cases: R2 2 Rg and Rg R.
I) If R2 2 Re. q" e A. Estimating the position of q² starts from the analysis on la- Given the volume function Vol(-) over the 3-D geometry, we know: Vol(A) in R and Vol(B) 4x R Given k over S, and Sg, we define the minimum distance of qa to the boundary of A as d. Let S, be cut off by a cross section Vi, where be the cut and D be the spherical cap of the half-sphere (see Figure 12) that satisfy
3
3
2 Vol(C)
2 R Vol(D) = 4T 4T R +R)
(19)
3
9
and the volume of D is
2T Rg (R., (R.-d.) 22
aresin Ra-da R,
Vol(D) . RR? - -Ra do) 2 -da) dda++ +
RR dx
2x
arcsin Rudd
(R? - (Ru da) 2),)2)(R.. -da)+
R. R 2 (2 R2 - -RR. d)
(20)
2
R., du
*<RR (R.. d.) (R, da) Paarcsin
R2 (Raa d
R
20

---

Under review as a conference paper at ICLR 2021
Let I 9 4 R + Rg)
aresin R.-da R. Eq. (20) can be written
Vol(D)= (R, - (Ra - (Ro - +da)
TR
cos
π
(21)
4p
Introducing Eq. (21) to Eq. (19), we have
G
3 6 vp - x (12 - (Ra - -d)) da)
2 1
(22)
Let t- Ru- da. Eq. (22) can be rewritten as
2
1
4
tt² π RRet +
C0s
T
0.
(23)
9 4
To simplify Eq. (23), let μ G + cos
I n Ra A
Eq. (23) then can be written
R2
0.
(24)
The positive solution of /. can be
R
2²
π R
3
n22
π
R
(25)
1=
3
2x
4
27T
2
4
27
Based on Eq. (19), we know
2
4T
R
R
Vol(D)
R
9
(26)
2
4
R
R3 0.
9
Thus, V/Rg < Ra. We next prove q¹ e A. Based on Eq. (26), we know
n RR
Ra.
(27)
2
Then, the following inequalities hold: R + R Finally, we have
1)2TR2 T R 2) 2 T
1 and 3) T + 1
T TR ( + +
(28)
Therefore, Vol(B) < 1 (Vol(A)+ + VB)( We thus know: 1) qa A and it is with a minimum distance d, to the boundary of Sa, 2) q B, and 3) g" E A. Therefore, class B can be deemed as having a very high probability to achieve a nearly zero generalization error and the position of q" largely decides the upper bound of the generalization error of h.
In Sa that covers class A, the nearly optimal error region can be bounded as the spherical cap of S. with volume constraint of Vol(A) Vol(C). We thence have an inequality of
Vol(A) Vol(C) < <err(h,,) < 3
(29)
Vol(A) + Vol( [)
We next calculate the volume of the spherical cap:
n. n. -d
(a((A)-ol(( -
Tx² d y
Ru
Ba
R²g -dd
(30)
π
Ru-do
4
dg nda(.. -
R
Eq. (29) then is rewritten as
4 t
3
R
(3RR da
< err(h,3) 0.3334.
(31)
1 + 1
Then, have the error bound of
4R3 (3R, - d.
< <err(h,3) < 0.3334.
(32)
4R3 + 4R3
21

---

Under review as a conference paper at ICLR 2021
Introducing da Rs -t, Eq. (32) is written
4R% - (2 + () 1)2 eer(h,3) < 0.3334.
(33)
4Rg 4Rg
2) With another assumption of Ra < Ra, we follow the same proof skills of Ra 2 Rs and know =
4nd (330 -df)-
<err(h,3) < 0.3334, i.e. where do Rs - l'' and l' RE
1Rg 1R
4n
27
R 27
and j = ( cos )t R
1x
2T
We thus conclude that min- AR (2R, +2) Rs :)² - - 1 Rg (R)2
(2Rg
< <err(h,3)< 0.33344
+RR
+4R4
D.2 PROOF OF THEOREM
We next present the generalization errors against an agnostic sampling budget l: following the above proof technique.
Proof. The proof studies two cases: R2 Rg and R. Rs- 1) R. RG, estimate the optimal position of do that satisfies la E A. Given the volume function Vol(-) over the 3-D geometry, we know: Vol(A) 4x R and Vol(B) boundary of Sa. Q be the nearest representative data to the boundary of Sh, and q" be the nearest representative data to h either in S. or S₁. Given the minimum distance of qa to the boundary of AA section h', where C be the and D be the spherical cap of the
4 R Assume 9a be the nearest representative data to the
3
3
da. Let Sa be off by half-sphere that satisfy
2 3 Vol(D) = 4T R R
Vol(C) = 3
(34)
3k
and the volume of D is
Vol(D) = T R2 - -RR, - d -da) + fo 2 2 (Ra-(Ra-d)) d.)
aresin Ra-ds
R.
RR² dx
2T
arcsin R.-da
. (12 (Ru - do)²) ) do)
Ra
RR (2 (2TH/ R2 - (Ro da
(35)
2x
= (R - (Ru da)²) - do) n R2, aresin
Rs du
v Rg - (Ra da)
Ra
Let = arcssn Ro-ds Eq. (36) can be written as
TR π
Vol(D) π (R? - (Ra ( - da)
co8
(36)
4
4
Introducing Eq. (36) to Eq. (34), we have
- -
2
T x (R, (Ra (Ra-da)) -da))) da)
4
R R
(37)
& 4
3k
Let ty = Ro da. we know
2h:
1
4T
T π Ro.
C08
R
0.
(38)
3h
3k
To simplify Eq. (38), let me
2k-1
1
cos
FT R
4m
Eq. (38) then can be written
3k
1/3
R2:
+ 11
0.
(39)
The positive solution of t can be
R22
2
3 R3
2
3
R3
(40)
3
2x
4
27
2x
4
27
22

---

Under review as a conference paper at ICLR 2021
Based on Eq. (35), we know
2
4 4 + Riy))
Vol(D) -
3k
(41)
2k
4
4
n
Ria
R 0.
3k
3k
Thus, V
2 E-2 Rs < Ra. We next prove g² A. According to Eq. (41), we know
k h-2
t T
RR.
(42)
Then, the following inequalities hold: 1) - 1 π Ri k² 2k-2-2 n Rij
ग Rdg 2) (k-2)x T Rig _ Ra. and 3) (K-2)T R.g.
2
2
+ 22-22-2 (R-2)k
x Rig. Finally, we have:
(R-2)6
n R
k:2 2k: 2
t R +
n
k
(k 2)
2
(43)
-nt T (Rig Rh)
π R
(k- - 2
π (Rag + Ro)). k
Therefore, (Bl(B) (Vol(A)+ Vol Vol(B)) B)). We thus know: 1) 9a A and it is with minimum
distance du to the boundary of Sa, 2) q E B, and 3) q" E A. Therefore, class B can be deemed as having a very high probability to achieve zero generalization error and the position of q² largely decides the upper bound of the generalization error of h.
In Sa that covers class A, the nearly optimal error region can be bounded as Vol(A) Vol(C). We then have the inequality of
Vol(A) Vol(C)
Vol (A) + Vol( < err eer((h,)) (h,k) K
(44)
Based on the volume equation of the spherical cap in Eq, (30), we have
π n 3 (3R, dg de
1
(rr(h, k)
(45)
1 + TT
Then, have the error bound of
4R (3R, - do)
<err(h,h) 1
(46)
4R 4R
Introducing d, = RR L2, Eq. (46) is written as
4R (2R, (Ra t²
1
< <err(h, k)
(47)
4R3 4R3
2) With another assumption of Rg < Rs. we follow the same proof skills of Ra 2 Rg and know
4R (R), < err(h, < 1.4 where d, Rs the and t
R
M6 2x
R5
4163 41t
4g
27
27 and 1/:-
22-44
R
4 3k
25
3k
We thus conclude that min
(2
<err(h,k)
L
485-110
D.3 PROOF OF THEOREM 2
Proof. Given class A and are tightly covered by ellipsoid E, and Es in a three-dimensional geometry. Let Ro, be the polar radius of E.. {Rag Rag} be the equatorial radii of E., Rs, be polar radius of Es, and (Roys Rys} be the equatorial radii of Eg. Based on Eq. (10), we know the class A and B,
Ro, Rg, Rs. < Rs, Vi, where R₂ and Rg the radii of the spheres respectively. We follow the same proof technique Theorem to present the generalization errors of AL with ellipsoid.
23

---

Under review as a conference paper at ICLR 2021
The proof studies two cases: Raj 2 Rs and Rai Rej. 1) If Rui Roy q" E A. Given the volume function Vol(.) over the 3-D geometry, we know: (ol(A) 4n Ra, Ray Raz and (ol(B)
4m Ra, Rag Rag Given the minimum distance of qa the boundary of A as da. Let E, by cut off by 3
cross section ht, where C be the cut and D be the ellipsoid cap of the half-ellipsoodd that satisfy 4 Rs, Ra, Ras + Rs, Ro, Roa)
Vol(C) π R R² Vol(D)
(48)
3k
and the volume of D is approximated as
Ruu Rug aresin -d,
Vol(D) 7( ((R,,, -RRo ddo))) da)
Rai
tt R2 dx
Ray dd
T (R(,, -Ro, - da)) ) da)
aresin
R.
n Re, (TRus Rus)
(49)
2T
Ray da Rai
( (Ro, da) ( - du))
T Rug Bay aresin
2
= =arcsin Ray-da Ra,
Let 9
Eq. (49) can be written
nT² Vol(D) x (Re, (Rui (da) - do)+
R², Rug Rus.
(50)
2:p
Introducing Eq. (50) to Eq. (48), we have
2 Ray )x Bun Rag Ras n (R2,
4T Ray Rag Rag
Ra, Roy Roy
(Bus da) (Bus - da)
2p
3k
(51)
Let d Rai du we know
2h: -
π Raj ) RR, Ray Rag
AT Rb, Rig Ris
ThZ n RR +
0.
(52)
3k
2p
3k
To simplify Eq. (52), let ol written as
22k4
Ilan 24
) Ray
Rag Ras
1r nay Rog 3k
Eq. (52) then can be
3k
π n R dE + 0k =0.
(53)
The positive solution of X can be
A
R2
3
R3
5k
k
3
R3
(54)
3
2x
4m
27
2x
4m²
27
The remaining proof process follows Eq. (40) to Eq. (46) of Theorem 1. We thus conclude that
min 411 Ro, (2Ro, + (Ro, - >x)²
2
II: Rs (2 xx,) X22
1
< cer((,, k) <
4 11; Ra, + +4 417 Ro:
4 I1: Rs, +4 +17 Ra;
k
(55)
where i= 1,,,3, X1-
R2
and 0%
2k-4
2n
27
2
4x
27
3k
In a simple way, Ra, Ray Ray and Rv, Ro, Ro, can be written as Il Ro, and [T Rb. i=1, 2, 3, respectively.
RRb Ro, Ro, Rog
4st Ray Rag Rag
2,p
3k
D.4 PROOF OF THEOREM
Proof. In clustering stability, 7-tube structure that surrounds the cluster boundary largely decides the performance of learning algorithm. Definition of y-tube as follows.
Definition 1. 7-tube Tube,(f) is a set of points distributed in the boundary of the cluster:
Tube, (f) == {x E X)((x, B(f)) S7). where X is a noise-free cluster with n samples, B(f) == {x X, is discontimuous at x }. f is clustering function, and ((.,) denotes the distance function.
(56)
24

---

Under review as a conference paper at ICLR 2021
Following this conclusion, representation data achieve the optimal generalization error if they spread over the tube structure. Let t = da. the probability of achieving a nearly zero generalization error can be expressed the volume ration of y-tube and S
Vol(Tube,)
Pr[err(h, k) Sphere
(S,
3 1R
{ da)3
(57)
3 R
4
R
where ia keeps consistent with Eq. (40). With the initial sampling from the tube structure of class A, the subsequent acquisitions of AL would be updated from the tube structure of class B. the initial sampling comes from the tube structure of B, the next acquisition must be updated from the tube structure of With the updated acquisitions spread over the tube structures both classes, is easy to achieve a nearly zero error. Then Theorem 3 is as stated.
D.5 PROOF OF THEOREM 4
Proof. Following the proof technique of Theorem 3, volume the tube is redefined as Vol(Tube,) T Roj Raz Rog. Then, we know
Vol(T)
Prferr(h, k:) 0] Eliisoiid
Vo)(Ea)
3 Re, Ros Ros 3( (Ro, - (Roz - da) - da)
(58)
Ra, Ras Ros
Aky Aka Ake Ray Ray Rag
where As.
n2
3 128
and oke
(2k-4
3
2x
4n
27x
2n
1x
27x²
3k
TRa; 2p
Rs, Rag Rbg
T Rui Rug Rus
i= 1,
3k
Theorem then is stated.
D.6 PROOF PROPOSITION
Proof. Let Cube, tightly covers S, with a side length of 2Rg, and Cube', tightly covers the cut C, following theorem 1, we know
Vol(A) Vol(C)
Cubea Cube's
err(h,k)
(59)
Vol(A)
Cubca
Then, we know
1 RR. n R3,da
err(h,k)
RR da
(60)
=
Ra
Meanwhile, let Cube, tightly covers E, with side length of 2Ra, Cubo.' tightly covers C, following theorem 1, we know
Vol(A) - Vol(C), Cubc. Cubc'
krr(h,k)>
(61)
Vol(A)
Cube.
Then, we know
a Ray Rag Ra, Tdl Rag Ras n TRa Ro, Roy
err(h,k)
(62)
du
Ra:
Since R,, < Rg, we know da R.
>
da
is thus the lower bound of AL with ellipsoid is tighter
R.
than AL with sphere. Then, Proposition holds.
25

---

Under review as a conference paper at ICLR 2021
D.7 PROOF PROPOSITION
Proof. Following the proofs of Theorem 3:
Pr(err(h, k:) Sphere
(Ru da)²
R2
(63)
do
1
Ra
Following the proofs Theorem 4:
Prferr(h, (h, k)) O] 1 Aey Aka
R
(Ray (a)( dd))(Re Ras da)
1
Ra
(64)
da
1
Ray
Based on Proposition 1, 1111 du R.
d_ Ray
therefore Pr[err ( k) 0 Sphhere < Pr(err(h,,))
Bllipooidd Then, Proposition stated.
D.8 LOWER DIMENSIONAL GENERALIZATION OF THE d-DIMENSIONAL GEOMETRY
With the above theoretical results, next present connection between 3-D geometry and d- dimensional geometry. The major technique is to prove that the volume the 3-D geometry is lower dimensional generalization of the d-dimensional geometry. It then can make all proof process from Theorems to hold in d-dimensional geometry.
Theorem 6. Let Vola be the volume of a d-dimensional geometry, Volg(S.) is a low-dimensional generalization of (ola
Proof. Given S₂ over class A defined with x + x3 R2 Let x² x3 its 2-D generalization of S., assume that be variable parameter in this 2-D generalization formula, the "volume" (2-D) volume the area of the geometry object) of can be expressed as
Vol2(S.) -
2/12 x3dx2-
(65)
Let & be an angle variable that satisfies = srsin(()), (i), we know dx2 cacos())dd) Then, Eq. (65) rewritten as
f x/2
Vol2(S.)
m/2 c0s
(66)
7/2 4r cos (O)do.
For 3-D geometry, for the variable Xy. it is cross-section which is 2-dimensional ball (circle), where the radius the ball can be expressed as ra.oo(()) (), s.t. 0 e [0, Tr. Particularly, let (ol,(S.) be the volume of S, with 3 dimensions, the volume of this 3-dimensional sphere then can be written as
Volv(S.) St" n/2 2Vo12 (ool((r.os(()))) (cos (C)s()))d
(67)
With Eq. (67), volume of a d-dimensional geometry can be expressed as the integral over the (d-1)-dimensional cross-section of S.
Volm (Sa) S( 1/2
2Volm-1 (r.mmm//rr.ooo()))))))))) (d),,
(68)
where Vol denotes the volume of (m-1) dimennsioal generalization geometry of S..
26

---

Under review as a conference paper at ICLR 2021
Based on Eq. (68), we know Vols can be written
Vol)(S.)= Jo x2/
(osl dd
(69)
Introducing Eq. (66) into Eq. (69), we have
n/2 ((ola(
Volz(S.)
1/2 Jo (a/2
8(racos(U))) cos" (cos( do
(70)
3 T s.t.Ra I
Therefore, the generalization analysis results of the 3-D geometry still can hold in the high dimensional geometry. Then,
Theorem 7. Let Vola be the volume of a d-dimensional geometry, Volg a low-dimensional generalization of Vola P.).
Proof. The integral of Eq. (67) also can be adopted into the volume of Vols by transforming area i.e. (S,, into Vol2 Ea). Then, Eq. (68) follows this transform.
27


Reviews:
[{"review_id": "xsPqMmwQV12", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Quality and clarity: the paper is well-written with good knowledge of the current state of the research in the subject area.\n\nSignificance: active learning is an important practical direction in machine learning. It currently has two main approaches - one is based on the uncertainty and another one on selecting the most representative subsets. The effective combination of these two is a promising direction of the research and it is addressed in the paper.\n\nOriginality: The idea to combine the uncertainty and diverse points selection is not exactly novel, but the paper proposes an interesting idea of improving the point selection with the rescaled geodesic search.\n\nPros:\n* The proposed method is well-reasoned\n* Good mathematical justification for the method\n* Tractable method implementation is presented.\n\nCons:\n* The results in Table 1 are a bit confusing as the provided std values are quite large. The explicit p-value for the proposed method could be relevant.\n* The experiments compare the new method only with basic ones like k-centers and BALD. More complex approaches (like batch BALD [Kirsch, 2019] and Sparse Subset Approximation [Pinsler, 2019]) were mentioned, but not presented in the main paper experiments for some reason, while they use a similar idea and show comparable improvement on the image datasets.\n* Experiments 5.1, 5.2 - with a small number of initial samples and large batches, the BALD sometimes performs worse than random sampling; it would be good to add random sampling here for reference.\n* The experiments are on the relatively small and simple image datasets, but it’s not clear how well the method would work on real-world size images, as the method partly relies on the l2 norm and it’s not a good metric for bigger images.\n\nReference\nAndreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch\nacquisition for deep bayesian active learning. In Advances in Neural Information Processing\nSystems, pp. 7024–7035, 2019.\n\nRobert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hernández-Lobato. Bayesian batch\nactive learning as sparse subset approximation. In Advances in Neural Information Processing\nSystems, pp. 6356–6367, 2019.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XfZfSMBEq5Y", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper the author/s study/ies the relvant problem of acive learning, i.e. the setting in which labeled data are not available. The innovation of the paper consist in constructing the core-set on an ellipsoid, and not on the typical sphere, preventing its updates towards the boundary regions of the distributions.\nThe paper states the main improvements of GBALD, the proposed method, over the existing method BALD are twofold: a) to relieve the sensitivity analysis to uninformative prior \nb) to reduce redundant information related to model uncertainty.\nImprovements of GBALD over existing models are proved through comparison to BALD spherical interpretation.\nIn particular, the paper shows that a geodesic search with ellipsoid can give a \"lower error bound\" which is tighter than that in the specialied literature. Furthermore, the paper aims to prove that with high probability the proposed approach achieves zero error. Numerical experiments conducted under different scenarios prove GBALD improves on BALD and BatchBALD which are considered ot be state-of-the-art meyhods.\n\n----------------------------------------------------------------------------------------------------------------------\nReason for Score:\nOverall, I vote for rejecting. I like the cleaness of the proposed approach but I think that the paper in the current status is not yet mature for such a relevant venue as ICLR. However, my opinion is better described in the  Cons section.\n\n----------------------------------------------------------------------------------------------------------------------\nPros.\n1) the paper tackles a very relevant problem, the one of unlabeled data.\n2) I appreciate the clean mathematical approach.\n3) the proposed approach is well described.\n3) numerical experiments, on the selected data sets, witness in favour of the proposed method, even if I also have concerns on this part of the paper.\n----------------------------------------------------------------------------------------------------------------------\nCons.\n1) a fundamental aspect of the proposed approach, when compared to alternative methods, is missing, i.e., the computational cost of the proposed approach when compared to other methods.\n2) I was not able to find a discussion about the relevance or cost incidence about data labeling. Which is the concrete advantage of labeling 100 in place of 200 cases? In oother words I would like to provide motivations for the problem tackled and a quantitative assessment of the advantage of the proposed approach.\n3) I'm increasingly concerned with the fact that only image datasets are taken into account in numerical experiments, images have a highly structured nature, the concept of smoothness, closeness between pixels, etc... I truly would like to see how the proposed method improves on different types of data, health data, biology data, financial data, ...\nIf the proposed approaches are confined to image datasets then this should be clearly stated in the paper in my humble opinion.\n4) the proposed approach, even if it is well desribed and analyzed, is somewhat straightforward. Indeed, the entire contribution builds on using an ellipsoid in place of shpere.\n5) In figure 4 I do not appreciate a strong difference between the proposed apporahc and BALD, at leat for digit 1 and 0, which I also would like to know why they were selected and not othe digits.\n6) In figure 6, the advantage of the proposed approach over alternative methods it is limited to the very beginning of the left part of the plots, I can non understand which is the effective/practical/economic advantage of such a difference. I would kindly ask the author to help me understand it.\n7) In table 1; standard deviations are huge and thus the expeted value of accuracy, achieved by differente methods, are extrelemy un certain, I would like the authors to help me understand how this impact their conclusions.\n8) In Table 2, K-medoids seems to be not that bad, what about comparison in terms of computational efforts to the proposed approach?\n----------------------------------------------------------------------------------------------------------------------\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above \n----------------------------------------------------------------------------------------------------------------------\nSome typos: \n\npage 2: I read \"which are no longer distributed uniformly\", I would like the author/s to better clarify on this\n\tI read \"It is thus the ranking rejects unnecessary redundant acquisitions.\", it makes no sense to me\npage 5: equation (10), I would suggest the use of DJ and not Di, indeed in previous part you used xi and Dj, while now using xi and Di makes me confuse\n----------------------------------------------------------------------------------------------------------------------", "extra_scores": {}, "extra_text": {}}, {"review_id": "9LV4SVZKlaW", "reviewer": "AnonReviewer1", "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": "\nThis paper introduces a new active learning algorithm called Geometric BALD, or GBALD. While the empirical experiments look promising, the writing for this paper is a bit strange.\n\nComments and questions:\n - It is a bit strange to say the \"deep learning community introduced active learning\" and cite a 2017 paper, since active learning has been around for over 20 years before that.\n - I'm confused by the line \"BALD has two interpretations: model uncertainty estimation and core-set construction\" in the introduction. Can the authors provide a reference or argument for this statement? How is core-set construction an interpretation of BALD?\n - What do the authors mean by \"Recently, deep Bayesian AL attracted the community.\"? What community?\n - How is $p(D_0 | \\theta)$ a \"prior\"? Perhaps the authors meant $p(\\theta | D_0)$, but that would be a posterior based on the initial seed set?\n - I don't think this paper uses the term \"uninformative prior\" correctly. For example, the paper states, \"For example, unbalanced label initialization on $D_0$ usually leads to an uninformative prior,\".\n - Why is the theory (appendix B) done specifically with three-dimensions? Don't most datasets have many more dimensions?\n - In appendix B, what sort of mathematical objects are A and B? They are explicitly said to be \"two classes\" but there are spheres that \"tightly cover\" A and B.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5h66gfRhjS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is basically unreadable. The sentence structure / grammar is strange, and if that was the only issue it could be overlooked. The paper also does not describe or explain the motivation and interpretation of anything, but instead just lists equations. For example, eta is the parameter that projects a spherical geodesic onto an the ellipsoid one, and an ellipsoid geodesic prevents updates of the core-set towards the boundary regions where the characteristics of the distribution cannot be captured. However, what are these characteristics, and how can they motivate how to choose eta?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers express concerns, such as about the presentation, the situation of the paper w.r.t. prior work, the experimental evaluation etc., and recommend rejection.
Decision: Reject