# Bayesian Active Learning by Disagreements:
A Geometric Perspective

Xiaofeng Cao and Ivor W. Tsang _X. Cao and I. W. Tsang are with the Australian
Artificial Intelligence Institute, University of Technology Sydney, NSW 2008,
Australia. E-mail<EMAIL_ADDRESS>This work was supported by
Australian Research Council under Grant DP180100106 and DP200101328._
Manuscript received xx xx, xxxx; revised xx xx, xxxx.

###### Abstract

We present geometric Bayesian active learning by disagreements (GBALD), a
framework that performs BALD on its core-set construction interacting with
model uncertainty estimation. Technically, GBALD constructs core-set on
ellipsoid, not typical sphere, preventing low-representative elements from
spherical boundaries. The improvements are twofold: 1) relieve uninformative
prior and 2) reduce redundant estimations. Theoretically, geodesic search with
ellipsoid can derive tighter lower bound on error and easier to achieve zero
error than with sphere. Experiments show that GBALD has slight perturbations
to noisy and repeated samples, and outperforms BALD, BatchBALD and other
existing deep active learning approaches.

###### Index Terms:

Geometric Bayesian, deep active learning, core-set, model uncertainty,
ellipsoid.

##  1 Introduction

Deep neural networks (DNNs) lack the ability of learning from limited
(insufficient) labels, which degenerates its generalizations to new tasks.
Recently, leveraging the abundance of unlabeled data has become a potential
solution to relieve this bottleneck whereby the expert knowledge is involved
to perform annotations. In such setting, the deep learning researchers
introduced the active learning (AL) [1], which solicit experts’ annotations
from those informative or representative unlabeled data, by maximizing the
model uncertainty [2, 3] of the current learning model. During this AL
process, the learning model tries to achieve a desired accuracy performance
using the minimal data labeling. Recent shift of model uncertainty in many
fields shows that deep Bayesian AL [4, 5] contributes the Bayesian neural
networks training [6], Monte-Carlo (MC) dropout [7], and Bayesian core-set
construction [8], etc.

Bayesian AL [9, 10] presents an expressive probabilistic interpretation on the
model uncertainty estimation [7]. Theoretically, for a simple regression model
such as linear, logistic, and probit, AL can derive their closed-forms on
updating one sparse subset, which maximally reduces the uncertainty of
posteriors over regression parameters [4]. However, for a DNN model,
optimizing massive training parameters is not easily tractable. It is thus
that the Bayesian approximation provides alternatives, including the
importance sampling [11] and the Frank-Wolfe optimization [12]. With
importance sampling, a typical Bayesian AL approach can be expressed as to
maximizing the information gain in terms of predictive entropy over the model,
and it is called Bayesian active learning by disagreements (BALD) [13].

BALD has two interpretations: model uncertainty estimation and core-set
construction. To estimate the uncertainty of a model, a greedy strategy is
usually applied. The criterion is to select those data that maximize the
parameter disagreements between the current training model and its following
updates as [1]. However, naively interacting with BALD using an uninformative
prior [14, 15] leads to unstable biased acquisitions [16], for example,
insufficient or unbalanced prior labels. Under this setting, an uninformative
prior can be constructed to reflect a balanced state among different Bayesian
outcomes, if there is no available information. Moreover, the similarity or
consistency of those acquisitions to their previous, brings some redundant
information to the model, and may decelerate the subsequent training.

Figure 1: Illustration of two-stage GBALD framework, which integrates model
uncertainty estimation and core-set construction into a uniform framework.
Stage $①$: core-set construction is with ellipsoid, not typical sphere,
representing the original distribution to initialize the input features of
DNNs. Stage $②$: model uncertainty estimation with those initial acquisitions
then explores highly informative and representative samples for DNN.

Core-set construction [17] avoids the greedy interaction to learning model via
capturing the characteristics of data distributions. By approximating complete
data posterior over model parameters, optimization of BALD can be deemed as a
core-set construction process on a sphere [5], which seamlessly solicits a
compact subset to draw the input data distribution, and efficiently mitigates
the sensitivity to uninformative prior and redundant information.

From a geometric perspective, updates of core-set construction are usually
optimized with spherical geodesic as [18, 19]. Once the core-set is obtained,
deep AL algorithm immediately seeks annotations from knowledgeable experts and
starts the training. However, the data located at the boundary regions of
distributions, usually with a uniform manner, could not be highly-
representative elements of core-set. Therefore, constructing core-set on
sphere may not be the optimal choice for deep AL.

This paper presents a novel AL framework, namely Geometric BALD (GBALD), over
the geometric interpretation of BALD that, interpreting BALD with the core-set
construction on ellipsoid, initializes effective representations to estimate
the model uncertainty. The goal is to seek for significant accuracy
improvements against an uninformative prior and the redundant information.
Figure 1 describes this two-stage framework. In the first stage, geometric
core-set construction on ellipsoid [20] initializes a set of effective
acquisitions to start a DNN model regardless of an uninformative prior. Taking
the core-set as the inputs, the next stage ranks the batch acquisitions of
model uncertainty according to their geometric representativeness, and then
solicits some highly-representative examples from the batch. With
representation constraints, the ranked acquisitions reduce the probability of
sampling those nearby samples of the previous acquisitions, preventing
redundant information. In order to explore these improvements, following the
typical approximately linear perceptron analysis [21], our generalization
analysis shows that, the lower bound of generalization errors of geodesic
search with ellipsoid, is proven to be tighter than that of geodesic search
with sphere. Achieving a nearly zero error by geodesic search with ellipsoid,
is also proven to have a higher probability than that of sphere.

Contributions of this paper can be summarized from the geometric, algorithmic,
and theoretical perspectives.

  * •

Geometrically, our key technical innovation is to construct core-set on
ellipsoid, not typical sphere, preventing low-representative elements from
boundary distribution.

  * •

In term of the algorithm design, our work proposes a two-stage framework from
a Bayesian perspective that sequentially introduces the core-set
representation and model uncertainty estimation, strengthening their
performance “independently”. Moreover, different to the typical BALD
optimizations, we present geometric solvers to construct a core-set and
estimate model uncertainty using it, which result in a different perspective
for Bayesian AL.

  * •

Theoretically, to guarantee those improvements, our generalization analysis
proves that, compared to the typical Bayesian spherical interpretation, the
geodesic search with ellipsoid can derive a tighter lower error bound and
achieve a higher probability to obtain a nearly zero error.

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 3 and 4,
respectively. Experimental results are presented in Section 5. Finally, we
conclude this paper in Section 6.

##  2 Related work

AL. The early probability support vector machine (SVM) proposed the concept of
AL [22, 23] that acquires the data with minimum margin to effectively update
the support vectors. Many AL acquisition algorithms were then proposed to
relieve the training bottleneck of SVM, which results in unsatisfied
predictions, for example, uncertainty sampling [24], margin sampling [25], MC
estimation of error reduction [26], transductive experimental design [27],
etc. Given a learning model without sufficient training labels, those
effective acquisitions reduce the expensive cost of human annotations in many
scenarios, e.g. multiple correct outputs [10], cost-sensitive classification
[28], adversarial training [29], etc. In theory, the researchers studied the
label complexity bound [30] (label demand before achieving a desired error
threshold) and its noisy performance [31] of an AL algorithm.

Model uncertainty. In deep learning setting, AL was introduced to improve the
training of DNNs by annotating a batch of unlabeled data, where the data which
maximize the model uncertainty [3] are the primary acquisitions. For example,
in ensemble deep learning [2], out-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 _et al._ [7] use
MC dropout to estimate the predictive uncertainty via approximating a Bayesian
convolutional neural network. Lakshminarayanan _et al._ [3] evaluate the
uncertainty of unlabeled data using a proper scoring rule, deriving the
sampling criteria of AL to fed the DNNs.

Bayesian AL. Taking a Bayesian perspective [9], AL can be deemed as minimizing
the Bayesian posterior risk with multiple label acquisitions over the input
unlabeled data. A potential informative approach is to reduce the uncertainty
about model parameters using Shannon’s entropy [32]. This can be interpreted
as 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) [13]. In
applications, BALD was introduced into natural language processing [33], text
classification [34], decision making [31], data augmentation [35], etc.

Deep AL. Recently, Gal _et al._ [1] proposed to cooperate BALD with DNNs to
improve its acquisition performance. The unlabeled data which maximize the
model uncertainty of DNNs 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 is applied as [5,
4]. In BatchBALD, Kirsch _et al._ [5] developed a tractable approximation to
the mutual information of one batch of unlabeled data and the current model
parameters. However, those uncertainty evaluations of Bayesian AL whether in
single or batch acquisitions all take a greedy strategy, which leads to
computationally infeasible, or excursive parameter estimations. Pinsler _et
al._ [4] thus approximated the posterior over the model parameters by a sparse
subset, i.e. a core-set. Applying the Frank-Wolfe optimization [12], the batch
acquisitions of a large-scale dataset can be efficiently derived, thereby
interpreting closed-form solutions for the core-set construction on a linear
or probit regression function. As a consequence, the non-deep models obtained
the theoretical guarantees from this optimization solver due to their
tractable parameters. However, for deep AL, being short of interactions to
DNNs is not able to maximally drive their model performance.

##  3 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 a discriminative model $p(y|x,\theta)$ parameterized by $\theta$
that maps $x\in\mathcal{X}$ into an output distribution over a set of
$y\in\mathcal{Y}$. Given an initial labeled (training) set
$\mathcal{D}_{0}\in\mathcal{X}\times\mathcal{Y}$, the Bayesian inference over
this parameterized model is to estimate the posterior
$p(\theta|\mathcal{D}_{0})$, i.e. estimate $\theta$ by repeatedly updating
$\mathcal{D}_{0}$. AL adopts this setting from a Bayesian perspective.

With AL, the learner can choose a set of unlabeled data from
$\mathcal{D}_{u}=\\{x_{i}\\}_{j=1}^{N}\in\mathcal{X}$ via maximizing the
uncertainty of the model parameters. Houlsby _et al._ [13] proposed a greedy
strategy termed BALD to update $\mathcal{D}_{0}$ by estimating a desired data
$x^{*}$ that maximizes the decrease in expected posterior entropy:

$\begin{split}x^{*}=\operatorname*{arg\
max}_{x\in\mathcal{D}_{u}}{\rm\bm{H}}[\theta|\mathcal{D}_{0}]-\mathbb{E}_{y\sim
p(y|x,\mathcal{D}_{0})}\Big{[}{\rm\bm{H}}[\theta|x,y,\mathcal{D}_{0}]\Big{]},\end{split}$
(1)

where the labeled and unlabeled sets are updated by
$\mathcal{D}_{0}=\mathcal{D}_{0}\cup\\{x^{*},y^{*}\\},\mathcal{D}_{u}=\mathcal{D}_{u}\backslash
x^{*}$, and $y^{*}$ denotes the output of $x^{*}$. In deep AL, $y^{*}$ can be
annotated as a label from experts and $\theta$ yields a DNN model.

###  3.2 Core-set construction

Let $p(\theta|\mathcal{D}_{0})$ be updated by its log posterior ${\rm
log}p(\theta|\mathcal{D}_{0},x^{*})$, $y^{*}\in\\{y_{i}\\}_{i=1}^{N}$, assume
the outputs are conditional independent of the inputs, i.e.
$p(y^{*}|x^{*},D_{0})=\int_{\theta}p(y^{*}|x^{*},\theta)p(\theta|D_{0}){\rm
d}\theta$, then we have the _complete data log posterior following_ [4]:

$\begin{split}&\mathbb{E}_{y^{*}}[{\rm
log}p(\theta|\mathcal{D}_{0},x^{*},y^{*})]\\\ &=\mathbb{E}_{y^{*}}[{\rm
log}p(\theta|\mathcal{D}_{0})+{\rm log}p(y^{*}|x^{*},\theta)-{\rm
log}p(y^{*}|x^{*},\mathcal{D}_{0})]\\\ &={\rm
log}p(\theta|\mathcal{D}_{0})+\mathbb{E}_{y^{*}}\Big{[}{\rm
log}p(y^{*}|x^{*},\theta)+{\rm\bm{H}}[y^{*}|x^{*},\mathcal{D}_{0}]\Big{]}\\\
&={\rm
log}p(\theta|\mathcal{D}_{0})+\sum_{i=1}^{N}\Bigg{(}\mathbb{E}_{y_{i}}\Big{[}{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{D}_{0}]\Big{]}\Bigg{)}.\end{split}$
(2)

The key idea of the core-set construction is to approximate the log posterior
of Eq. (2) by a subset of $D_{u}^{\prime}\subseteq D_{u}$ such that:
$\mathbb{E}_{\mathcal{Y}_{u}}[{\rm
log}p(\theta|\mathcal{D}_{0},\mathcal{D}_{u},\mathcal{Y}_{u})]\approx\mathbb{E}_{\mathcal{Y}^{\prime}_{u}}[{\rm
log}p(\theta|\mathcal{D}_{0},\mathcal{D}_{u}^{\prime},\mathcal{Y}_{u}^{\prime})],$
where $\mathcal{Y}_{u}$ and $\mathcal{Y}^{\prime}_{u}$ denote the predictive
labels of $\mathcal{D}_{u}$ and $\mathcal{D}^{\prime}_{u}$ respectively by the
Bayesian discriminative model, that is,
$p(\mathcal{Y}_{u}|\mathcal{D}_{u},D_{0})=\int_{\theta}p(\mathcal{Y}_{u}|\mathcal{D}_{u},\theta)p(\theta|D_{0}){\rm
d}\theta$, and
$p(\mathcal{Y}_{u}^{\prime}|\mathcal{D}_{u}^{\prime},D_{0})=\int_{\theta}p(\mathcal{Y}_{u}^{\prime}|\mathcal{D}_{u}^{\prime},\theta)p(\theta|D_{0}){\rm
d}\theta$. Here $D_{u}^{\prime}$ can be indicated by a core-set [4] that
highly represents $\mathcal{D}_{u}$. The optimization tricks such as the
Frank-Wolfe optimization [12] then can be adopted to solve this problem.

Motivations. Eqs. (1) and (2) provide the Bayesian rules of BALD over model
uncertainty and core-set construction respectively, which further attract the
attention of deep learning researchers. However, the two interpretations of
BALD are limited by: 1) the redundant information and 2) an uninformative
prior, where one major reason which causes these two issues is the poor
initialization on the prior, i.e. $p(\mathcal{D}_{0}|\theta)$. For example, an
unbalanced label initialization on $\mathcal{D}_{0}$ usually leads to an
uninformative prior, which further conducts the acquisitions of AL to select
those unlabeled data from one or some fixed classes; highly-biased results
[16] with redundant information are inevitable. Therefore, these two
limitations affect each other.

##  4 GBALD

(a) Sphere geodesic

(b) Ellipsoid geodesic

Figure 2: Optimizing BALD with sphere and ellipsoid geodesics. Ellipsoid
geodesic rescales the sphere geodesic to prevent the updates of core-set
towards the boundary regions of the sphere where characteristics of spherical
distribution cannot be properly captured. Note that the black points denote
the feasible updates of the red points and the dash lines denote the
geodesics.

GBALD consists of two components: 1) initial acquisitions based on core-set
construction and 2) model uncertainty estimation with those initial
acquisitions.

###  4.1 Geometric interpretation of core-set

Modeling the complete data posterior over parameter distribution can relieve
the two limitations of BALD, which has been stated at the end of Section 3.2.
Typically, optimizing the acquisitions of Bayesian AL is equivalent to
approximating a core-set centered with the spherical embeddings [8]. Let
$w_{i}$ be the sampling weight of $x_{i}$, $\|w_{i}\|_{0}\leq N$, the core-set
construction is to optimize:

$\begin{split}\operatorname*{min}_{w}&\ \
\Bigg{\|}\underbrace{\sum_{i=1}^{N}\mathbb{E}_{y_{i}}\Big{[}{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{D}_{0}]\Big{]}}_{\mathcal{L}}\\\
&-\underbrace{\sum_{i=1}^{N}w_{i}\mathbb{E}_{y_{i}}\Big{[}{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{D}_{0}]\Big{]}}_{\mathcal{L}(w)}\Bigg{\|}^{2},\\\
\end{split}$ (3)

where $\mathcal{L}$ and $\mathcal{L}(w)$ denote the full and expected
(weighted) log-likelihoods, respectively [17, 36]. Specifically,
$\sum_{i=1}^{N}{\rm\bm{H}}[y_{i}|x_{i},\mathcal{D}_{0}]=-\sum_{y_{i}}p(y_{i}|x_{i},\mathcal{D}_{0}){\rm
log}(p(y_{i}|x_{i},\mathcal{D}_{0})$, where
$p(y_{i}|x_{i},\mathcal{D}_{0})=\int_{\theta}p(y_{i}|x_{i},\theta)p(\theta|\mathcal{D}_{0}){\rm
d}\theta$. Note $\|\cdot\|$ denotes the $\ell^{2}$ norm.

The approximation of Eq. (3) implicitly requires that the complete data log
posterior of Eq. (2) w.r.t. $\mathcal{L}$ must be close to an expected
posterior w.r.t. $\mathcal{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 is intractable due to the cardinality
constraint [4]. Campbell _et al._ [36] proposed to relax the constraint in
Frank–Wolfe optimization, in which mapping $\mathcal{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 a polynomial constraint. However, the initialization on $\mathcal{D}_{0}$
affects the iterative approximation to $\mathcal{D}_{u}$ at the beginning of
the geodesic search. Moreover, the posterior of $p(\theta|\mathcal{D}_{0})$ is
uninformative, if the initialized $\mathcal{D}_{0}$ is empty or 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 [8], is not restricted to this setting. We
thus follow the construction of $k$-centers to find the core-set.

$\bm{k}$-centers. Sener _et al._ [8] proposed a core-set representation
approach for deep AL based on $k$-centers. This approach can be adopted in the
core-set construction of BALD without the help of a discriminative (training)
model. Therefore, the uninformative prior has no further influence to the
core-set. Typically, the $k$-centers approach uses a greedy strategy to search
the data $\widetilde{x}$ whose nearest distance to the elements of
$\mathcal{D}_{0}$ is the maximal:

$\widetilde{x}=\operatorname*{arg\
max}_{x_{i}\in\mathcal{D}_{u}}\min_{c_{i}\in\mathcal{D}_{0}}\|x_{i}-c_{i}\|,$
(4)

then $\mathcal{D}_{0}$ is updated by
$\mathcal{D}_{0}\cup\\{\widetilde{x},\widetilde{y}\\}$, $\mathcal{D}_{u}$ is
updated by $\mathcal{D}_{u}\backslash\widetilde{x}$, where $\widetilde{y}$
denotes the output of $\widetilde{x}$. This max-min operation usually performs
$k$ times to construct the centers.

From a geometric perspective, the ${k}$-centers can be deemed as the core-set
construction via the spherical geodesic search as [37, 38]. Specifically, the
max-min optimization guides $\mathcal{D}_{0}$ to be updated into one data
which draws the longest geodesic from $x_{i},\forall i$ across the sphere
center. The iterative update on $\widetilde{x}$ is then along its unique
diameter through the sphere center. However, this greedy optimization has a
large probability that leads the core-set to fall into the boundary regions of
the sphere, which is not able to capture the characteristics of the
distributions.

###  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 $p(\mathcal{D}_{0}|\theta)$ is
performed with a group of internal spheres centered with $D_{j},\forall j,$
subjected to $D_{j}\in\mathcal{D}_{0}$, in which the geodesic between
$\mathcal{D}_{0}$ and the unlabeled data is over those spheres. Since
$\mathcal{D}_{0}$ is known, the specification of $\theta$ then plays a key
role on initializing $p(\mathcal{D}_{0}|\theta)$. Given a radius $R_{0}$ for
any observed internal sphere, $p(y_{i}|x_{i},\theta)$ is firstly defined by

$p(y_{i}|x_{i},\theta)=\left\\{\begin{aligned} &\ \ \ \ \ \ \ \ \ 1,&\exists
j,\|x_{i}-D_{j}\|\leq R_{0},\\\ &{\rm
max}\Bigg{\\{}\frac{R_{0}}{\|x_{i}-D_{j}\|}\Bigg{\\}},&\forall
j,\|x_{i}-D_{i}\|>R_{0},\\\ \end{aligned}\right.$ (5)

thereby $\theta$ yields the parameter $R_{0}$. 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 ${\rm max}\Big{\\{}\frac{R_{0}}{\|x_{i}-D_{j}\|}\Big{\\}}$
constrained by ${\rm min}\|x_{i}-D_{j}\|,\forall j$, i.e. the probability is
assigned by the nearest ball to $x_{i}$, which is centered with $D_{j}$. From
Eq. (3), the information entropy of $y_{i}\sim\\{y_{1},y_{2},...,y_{N}\\}$
over $x_{i}\sim\\{x_{1},x_{2},...,x_{N}\\}$ can be expressed as the integral
regarding $p(y_{i}|x_{i},\theta)$:

$\begin{split}&\sum_{i=1}^{N}{\rm H}(y_{i}|x_{i},\mathcal{D}_{0})\\\
&=-\sum_{i=1}^{N}\int_{\theta}p(y_{i}|x_{i},\theta)p(\theta|D_{0})d\theta{\rm
log}\Big{(}\int_{\theta}p(y_{i}|x_{i},\theta)p(\theta|D_{0})\Big{)}d\theta,\end{split}$
(6)

which can be approximated by $-\sum_{i=1}^{N}p(y_{i}|x_{i},\theta){\rm
log}\Big{(}p(y_{i}|x_{i},\theta)\Big{)}$ following the details of Eq. (3). In
short, this indicates an approximation to the entropy over the entire outputs
on $\mathcal{D}_{u}$ that assumes the prior $p(D_{0}|\theta)$ w.r.t.
$p(y_{i}|x_{i},\theta)$ is already known from Eq. (5).

Max-min optimization. Recalling the max-min optimization trick of $k$-centers
in the core-set construction of [8], the minimizer of Eq. (3) then can be
divided into two parts: $\operatorname*{min}_{x^{*}}\mathcal{L}$ and
$\operatorname*{max}_{w}\mathcal{L}(w)$, where $\mathcal{D}_{0}$ is updated by
acquiring $x^{*}$. However, the updates of $\mathcal{D}_{0}$ decide the
minimizer of $\mathcal{L}$ with regard to the internal spheres centered with
${D}_{i},\forall i$. Therefore, minimizing $\mathcal{L}$ should be constrained
by an unbiased full likelihood over $\mathcal{X}$ to alleviate the potential
biases from the initialization of $\mathcal{D}_{0}$. Let $\mathcal{L}_{0}$
denote the unbiased full likelihood over $\mathcal{X}$ that particularly
stipulates $\mathcal{D}_{0}$ as the $k$-means centers written as $\mathcal{U}$
of $\mathcal{X}$ which jointly draw the input distribution. We define
$\mathcal{L}_{0}=|{\sum_{i=1}^{N}\mathbb{E}_{y_{i}}[{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{U}]]}|$ to regulate
$\mathcal{L}$, that is

$\begin{split}&\operatorname*{min}_{x^{*}}\|\mathcal{L}_{0}-\mathcal{L}\|^{2},\
\ {\rm s.t.}\
\mathcal{D}_{0}=\mathcal{D}_{0}\cup\\{x^{*},y^{*}\\},\mathcal{D}_{u}=\mathcal{D}_{u}\backslash
x^{*}.\\\ \end{split}$ (7)

The other sub optimizer is $\operatorname*{max}_{w}\mathcal{L}(w)$. We present
a greedy strategy following Eq. (1):

$\begin{split}&\operatorname*{max}_{1\leq i\leq N}\
\operatorname*{min}_{w_{i}}\ \sum_{i=1}^{N}w_{i}\mathbb{E}_{y_{i}}[{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{D}_{0}]]\\\
&=\sum_{i=1}^{N}w_{i}{\rm
log}p(y_{i}|x_{i},\theta)-\sum_{i=1}^{N}w_{i}p(y_{i}|x_{i},\theta){\rm
log}p(y_{i}|x_{i},\theta),\end{split}$ (8)

which can be further written as: $\sum_{i=1}^{N}w_{i}{\rm
log}p(y_{i}|x_{i},\theta)(1-{\rm log}p(y_{i}|x_{i},\theta)).$ Let
$w_{i}=1,\forall i$ for unbiased estimation of the likelihood
$\mathcal{L}(w)$, Eq. (8) can be simplified as

$\begin{split}\operatorname*{max}_{x_{i}\in\mathcal{D}_{u}}\
\operatorname*{min}_{D_{j}\in\mathcal{D}_{0}}{\rm
log}p(y_{i}|x_{i},\theta),\end{split}$ (9)

where $p(y_{i}|x_{i},\theta)$ follows Eq. (5). Combining Eqs. (7) and (9), the
optimization of Eq. (3) is then transformed as

$\begin{split}x^{*}=\operatorname*{arg\ max}_{x_{j}\in\mathcal{D}_{u}}\
\operatorname*{min}_{D_{j}\in\mathcal{D}_{0}}\Bigg{\\{}\|\mathcal{L}_{0}-\mathcal{L}\|^{2}+{\rm
log}p(y_{j}|x_{j},\theta)\Bigg{\\}},\end{split}$ (10)

where $\mathcal{D}_{0}$ is updated by acquiring $x^{*}$, i.e.
$\mathcal{D}_{0}=\mathcal{D}_{0}\cup\\{x^{*},y^{*}\\}$.

Geodesic line. For a metric geometry $M$, a geodesic line is a curve $\gamma$
which projects its interval $I$ to $M$: $I\rightarrow M$, maintaining
everywhere locally a distance minimizer [39]. Given a constant $\nu>0$ such
that for any $a,b\in I$ there exists a geodesic distance
$d(\gamma(a),\gamma(b)):=\int_{a}^{b}\sqrt{{g}_{\gamma(t)}(\gamma^{\prime}(t),\gamma^{\prime}(t))}dt$,
where $\gamma^{\prime}(t)$ denotes the geodesic curvature, and ${g}$ denotes
the metric tensor over $M$. Here, we define $\gamma^{\prime}(t)=0$, then
${g}_{\gamma(t)}(0,0)=1$ such that $d(\gamma(a),\gamma(b))$ can be generalized
as a segment of a straight line: $d(\gamma(a),\gamma(b))=\|a-b\|$.

Ellipsoid geodesic distance. For any observation points $p,q\in M$, if the
spherical geodesic distance is defined as $d(\gamma(p),\gamma(q))=\|p-q\|$.
The affine projection obtains its ellipsoid interpretation:
$d(\gamma(p),\gamma(q))=\|\eta(p-q)\|$, where $\eta$ denotes the affine factor
subjected to $0<\eta<1$.

Optimizing with ellipsoid geodesic search. The max-min optimization of Eq.
(10) is performed on an ellipsoid geometry to prevent the updates of the core-
set towards the boundary regions, where the ellipsoid geodesic line scales the
original update on the sphere. Assume $x_{i}$ is the previous acquisition and
$x^{*}$ is the next desired acquisition, the ellipsoid geodesic rescales the
position of $x^{*}$ as $x_{e}^{*}=x_{i}+\eta(x^{*}-x_{i})$. Then, we update
this position of $x_{e}^{*}$ to its nearest neighbor $x_{j}$ in the unlabeled
data pool, i.e. $\operatorname*{arg\
min}_{x_{j}\in\mathcal{D}_{u}}\|x_{j}-x_{e}^{*}\|$, also can be written as

$\begin{split}\operatorname*{arg\
min}_{x_{j}\in\mathcal{D}_{u}}\Big{\|}x_{j}-[x_{i}+\eta(x^{*}-x_{i})]\Big{\|}.\end{split}$
(11)

To study the advantage of ellipsoid geodesic search, Section 6 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 a ranking scheme to derive both
informative and representative acquisitions.

Single acquisition. We follow [1] and use MC dropout to perform Bayesian
inference on the neural network model. It 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 the batch returns:

$\begin{split}&\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}=\operatorname*{arg\
max}_{\\{\hat{x}_{1},\hat{x}_{2},...,\hat{x}_{b}\\}\subseteq\mathcal{D}_{u}}\\\
&\Bigg{\\{}{\rm\bm{H}}[\theta|\mathcal{D}_{0}]-\mathbb{E}_{\hat{y}_{1:b}\sim
p(\hat{y}_{1:b}|\hat{x}_{1:b},\mathcal{D}_{0})}\Big{[}{\rm\bm{H}}[\theta|\hat{x}_{1:b},\hat{y}_{1:b},\mathcal{D}_{0}]\Big{]}\Bigg{\\}},\\\
\end{split}$ (12)

where $\hat{x}_{1:b}=\\{\hat{x}_{1},\hat{x}_{2},...,\hat{x}_{b}\\}$,
$\hat{y}_{1:b}=\\{\hat{y}_{1},\hat{y}_{2},...,\hat{y}_{b}\\}$, $\hat{y}_{i}$
denotes the output of $\hat{x}_{i}$. The informative acquisition $x^{*}_{t}$
is then selected from the ranked batch acquisitions $\hat{x}_{1:b}$ due to the
highest (most) representation for the unlabeled data:

$\begin{split}x^{*}_{t}=\operatorname*{arg\
max}_{x^{*}_{i}\in\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}}\Bigg{\\{}\max_{D_{j}\in\mathcal{D}_{0}}\
p(y_{i}|x^{*}_{i},\theta):=\frac{R_{0}}{\|x^{*}_{i}-D_{j}\|}\Bigg{\\}},\end{split}$
(13)

where $t$ denotes the index of the final acquisition, subjected to $1\leq
t\leq b$. This also adopts the max-min optimization of $k$-centers in Eq. (4),
i.e. $x^{*}_{t}=\operatorname*{arg\
max}_{x^{*}_{i}\in\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}}\min_{D_{j}\in\mathcal{D}_{0}}\
{\|x^{*}_{i}-D_{j}\|}.$

Batch acquisitions. The greedy strategy of Eq. (13) can be written as a batch
of acquisitions by controlling its output as a batch set, i.e.

$\begin{split}\\{x^{*}_{t_{1}},...,x^{*}_{t_{b^{\prime}}}\\}=\operatorname*{arg\
max}_{x^{*}_{t_{1}:t_{b^{\prime}}}\subseteq\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}}p(y^{*}_{t_{1}:t_{b^{\prime}}}|x^{*}_{t_{1}:t_{b^{\prime}}},\theta),\end{split}$
(14)

where
$x^{*}_{t_{1}:t_{b^{\prime}}}=\\{x^{*}_{t_{1}},...,x^{*}_{t_{b^{\prime}}}\\}$,
$y^{*}_{t_{1}:t_{b^{\prime}}}=\\{y^{*}_{t_{1}},...,y^{*}_{t_{b^{\prime}}}\\}$,
$y^{*}_{t_{i}}$ denotes the output of $x^{*}_{t_{i}}$, $1\leq i\leq
b^{\prime}$, and $1\leq b^{\prime}\leq b$. This setting can be used to
accelerate the acquisitions of AL in a large dataset.

##  5 Two-stage GBALD Algorithm

The GBALD algorithm has two stages: 1) construct a core-set on ellipsoid
(Lines 3 to 13), and 2) estimate model uncertainty with a deep learning model
(Lines 14 to 21).

Algorithmically, core-set construction is derived from the max-min
optimization of Eq. (10), then updated with ellipsoid geodesic w.r.t. Eq.
(11), where $\theta$ yields a geometric probability model w.r.t. Eq. (5).
Importing the core-set into $\mathcal{D}_{0}$ derives the deep learning model
to return $b$ informative acquisitions one time, where $\theta$ yields a deep
learning model. Ranking those samples, we select $b^{\prime}$ samples with the
highest representations as the batch outputs w.r.t. Eq. (14). The iterations
of batch acquisitions stop until its budget is exhaust. The final update on
$\mathcal{D}_{0}$ is our acquisition set of AL.

1 Input: Data set $\mathcal{X}$, core-set size $N_{\mathcal{M}}$, batch
returns $b$, batch output $b^{\prime}$, iteration budget $\mathcal{A}$.

2 Initialization: $\alpha\leftarrow 0$, core-set
$\mathcal{M}\leftarrow\emptyset$.

3 Stage ① begins:

4 Initialize $\theta$ to yield a geometric probability model w.r.t. Eq. (5).

5 Perform $k$-means to initialize $\mathcal{U}$ to $\mathcal{D}_{0}$.

6 Core-set construction begins by acquiring $x_{i}^{*}$,

7 for  _$i\leftarrow 1,2,...,N_{\mathcal{M}}$_ do

8 $x_{i}^{*}\leftarrow\operatorname*{arg\ max}_{x_{i}\in\mathcal{D}_{u}}\
\operatorname*{min}_{D_{i}\in\mathcal{D}_{0}}\Bigg{\\{}\Big{\|}\mathcal{L}_{0}-\mathcal{L}\Big{\|}^{2}+{\rm
log}p(y_{i}|x_{i},\theta)\Bigg{\\}},$ where
$\mathcal{L}_{0}\leftarrow\Big{|}{\sum_{i=1}^{N}\mathbb{E}_{y_{i}}[{\rm
log}p(y_{i}|x_{i},\theta)+{\rm\bm{H}}[y_{i}|x_{i},\mathcal{U}]]}\Big{|}$.

9 Ellipsoid geodesic line scales $x_{i}^{*}$:
$x_{i}^{*}\leftarrow\operatorname*{arg\
min}_{x_{j}\in\mathcal{D}_{u}}\Big{\|}x_{j}-[x_{i}+\eta(x^{*}-x_{i})]\Big{\|}.$

10 Update $x_{i}^{*}$ into core-set $\mathcal{M}$: $\mathcal{M}\leftarrow
x_{i}^{*}\cup\mathcal{M}$.

11 Update $N\leftarrow N-1$.

12

13 end for

14Import core-set to update $\mathcal{D}_{0}$:
$\mathcal{D}_{0}\leftarrow\mathcal{M}\cup\mathcal{U}^{\prime}$, where
$\mathcal{U}^{\prime}$ updates each element of $\mathcal{U}$ into their
nearest samples in $\mathcal{X}$.

15 Stage ② begins:

16 Initialize $\theta$ to yield a deep learning model.

17 while  _$\alpha <\mathcal{A}$_ do

18 Return $b$ informative deep learning acquisitions in one budget:
$\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}\leftarrow\operatorname*{arg\
max}_{x\in\mathcal{D}_{u}}{\rm\bm{H}}[\theta|\mathcal{D}_{0}]-\mathbb{E}_{y\sim
p(y|x,\mathcal{D}_{0})}\Big{[}{\rm\bm{H}}[\theta|x,y,\mathcal{D}_{0}]\Big{]}$.

19 Rank $b^{\prime}$ informative acquisitions with the highest geometric
representativeness:
$\\{x^{*}_{t_{1}},...,x^{*}_{t_{b^{\prime}}}\\}\leftarrow\operatorname*{arg\
max}_{x^{*}_{i}\in\\{x^{*}_{1},x^{*}_{2},...,x^{*}_{b}\\}}p(y_{i}|x^{*}_{i},\theta)$.

20 Update $\\{x^{*}_{t_{1}},...,x^{*}_{t_{b^{\prime}}}\\}$ into
$\mathcal{D}_{0}$:
$\mathcal{D}_{0}\leftarrow\mathcal{D}_{0}\cup\\{x^{*}_{t_{1}},...,x^{*}_{t_{b^{\prime}}}\\}$.

21 $\alpha\leftarrow\alpha+1$.

22

23 end while

Output: final update on $\mathcal{D}_{0}$.

Algorithm 1 Two-stage GBALD Algorithm

##  6 Generalization errors of geodesic search with sphere and ellipsoid

Optimizing with ellipsoid geodesic linearly rescales the spherical search,
which draws core-set on a tighter geometric object. The inherent motivation is
that, geodesic search with ellipsoid can prevent the redundant updates of
core-set, avoiding those elements from spherical boundaries. Following the
approximately perceptron analysis of [21], this section presents
generalization error analysis from geometry, which provides feasible
guarantees for geodesic search with ellipsoid. The proofs are presented in
Appendix.

###  6.1 Assumptions of generalization analysis

Let ${\rm Pr}[err(h,k)=0]_{\rm Sphere}$ and ${\rm Pr}[err(h,k)=0]_{\rm
Ellipsoid}$ be the probabilities of achieving a zero error by geodesic search
with sphere and ellipsoid, respectively, we study their inequality
relationship. The assumptions are inspired from $\gamma$-tube manifold, which
characterizes the probability mass of decision boundaries.

Given $S_{A}$ be the sphere that tightly covers class $A$ where $S_{A}$ is
with a center $c_{a}$ and radius $R_{a}$, the assumption on sphere is as
follows.

######  Assumption 1.

Ben-David et al. [40] proposed that the $\gamma$-tube manifold [41] can
characterize the probability mass of an optimal version space-based
hypothesis. From geometry, we here assume that the probability mass of
achieving a zero error by geodesic search with sphere, is roughly defined as
the volume ratio of the $\gamma$-tube and sphere, that is, ${\rm
Pr}[err(h,k)=0]_{\rm Sphere}:=\frac{\rm{Vol(Tube)}}{{\rm Vol(Sphere)}}$. Given
$\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, the assumption is
formalized as

${\rm Pr}[err(h,k)=0]_{\rm Sphere}=1-\frac{t_{k}^{3}}{R_{a}^{3}},$

where
$t_{k}=\frac{R_{a}^{2}}{3}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}+\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}-\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}$,
and $\mu_{k}=(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{3k}$.

Given class $A$ is tightly covered by ellipsoid $E_{a}$, let $R_{a_{1}}$ be
the polar radius of $E_{a}$, and $R_{a_{2}}$, $R_{a_{3}}$ be the equatorial
radii of $E_{a}$, the assumption on ellipsoid is as follows.

######  Assumption 2.

Following Assumption 1, the probability mass of achieving a zero error by
geodesic search with ellipsoid, can be assumed as the volume ratio of the
$\gamma$-tube and ellipsoid, that is ${\rm Pr}[err(h,k)=0]_{\rm
Ellipsoid}:=\frac{\rm{Vol(Tube)}}{{\rm Vol(Ellipsoid)}}$. Then, the assumption
is formalized as

${\rm Pr}[err(h,k)=0]_{\rm
Ellipsoid}=1-\frac{\lambda_{k_{1}}\lambda_{k_{2}}\lambda_{k_{3}}}{R_{a_{1}}R_{a_{2}}R_{a_{3}}},$

where
$\lambda_{k_{i}}=\frac{R_{a_{i}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k_{i}}}{2\pi}+\sqrt{\frac{\sigma_{k_{i}}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{i}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k_{i}}}{2\pi}-\sqrt{\frac{\sigma_{k_{i}}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{i}}^{3}}{27\pi^{3}}}}$,
and $\sigma_{k_{i}}=(\frac{2k-4}{3k}-\frac{\pi R_{a_{i}}}{2\varphi})\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}-\frac{4\pi R_{b_{1}}R_{b_{2}}R_{b_{3}}}{3k}$,
$i=1,2,3$.

The specifications of of Assumptions 1 and 2 are presented in Appendix A.2 and
A.3, respectively. We next present our low-dimensional generalization
analysis.

###  6.2 Low-dimensional generalizations

Our generalization analysis begins from low-dimensional (3-D) sphere/ellipsoid
to high-dimensional hypersphere/hyperellipsoid, where the high-dimensional
settings can be extended into infinite dimensions.

####  6.2.1 Our settings

Geodesic search with sphere. With Assumptions 1 and 2, given a perceptron
function $h:={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$, the task is to classify the two
classes $A$ and $B$ embedded in a 3-D space. Let $S_{A}$ and $S_{B}$ be the
spheres that tightly cover $A$ and $B$, respectively, where $S_{A}$ is with a
center $c_{a}$ and radius $R_{a}$, and $S_{B}$ is with a center $c_{b}$ and
radius $R_{b}$. Under this setting, our generalization analysis is presented
as follows.

######  Theorem 1.

With Assumptions 1 and 2, given a perceptron function
$h={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$ that classifies $A$ and $B$, and a sampling
budget $k$. By drawing core-set on $S_{A}$ and $S_{B}$, the minimum distances
to the boundaries of that core-set elements of $S_{A}$ and $S_{B}$, are
defined as $d_{a}$ and $d_{b}$, respectively. Let $err(h,k)$ be the
classification error rate with respect to $h$ and $k$, given
$\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, we then have an
inequality of error: ${\rm
min}\Bigg{\\{}\frac{4R_{a}^{3}-(2R_{a}+t_{k})(R_{a}-t_{k})^{2}}{4R_{a}^{3}+4R_{b}^{3}},\frac{4R_{b}^{3}-(2R_{b}+t_{k}^{\prime})(R_{b}-t_{k}^{\prime})^{2}}{4R_{b}^{3}+4R_{a}^{3}}\Bigg{\\}}$

$<err(h,k)<\frac{1}{k},$

where
$t_{k}=\frac{R_{a}^{2}}{3}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}+\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}-\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}$,
$\mu_{k}=(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{3k}$,
$t_{k}^{\prime}=\frac{R_{b}^{2}}{3}+\sqrt[3]{-\frac{\mu_{k}^{\prime}}{2\pi}+\sqrt{\frac{\mu_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu_{k}^{\prime}}{2\pi}-\sqrt{\frac{\mu_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}$, and
$\mu_{k}^{\prime}=(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{b}^{3}-\frac{4\pi R_{a}^{3}}{3k}$.

Geodesic search with ellipsoid. With Assumptions 1 and 2, given class $A$ and
$B$ are tightly covered by ellipsoid $E_{a}$ and $E_{b}$ in a 3-D space. Let
$R_{a_{1}}$ be the polar radius of $E_{a}$, and $R_{a_{2}},R_{a_{3}}$ be the
equatorial radii of $E_{a}$, $R_{b_{1}}$ be the polar radius of $E_{b}$, and
$R_{b_{2}},R_{b_{3}}$ be the equatorial radii of $E_{b}$, the generalization
analysis is ready to present following these settings.

######  Theorem 2.

With Assumptions 1 and 2, given a perceptron function
$h={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$ that classifies $A$ and $B$, and a sampling
budget $k$. By drawing core-set on $E_{a}$ and $E_{b}$, the minimum distances
to the boundaries of that core-set elements of $S_{A}$ and $S_{B}$, are
defined as $d_{a}$ and $d_{b}$, respectively. Let $err(h,k)$ be the
classification error rate with respect to $h$ and $k$, given
$\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, we then have an
inequality of error: ${\rm
min}\Bigg{\\{}\frac{4\prod_{i}\\!R_{a_{i}}-(2R_{a_{1}}+\lambda_{k})(R_{a_{1}}-\lambda_{k})^{2}}{4\prod_{i}R_{a_{i}}+4\prod_{i}R_{b_{i}}},\\!\\!\frac{4\prod_{i}\\!R_{b_{i}}-(2R_{b_{1}}+\lambda_{k}^{\prime})(R_{b_{1}}-\lambda_{k}^{\prime})^{2}}{4\prod_{i}R_{b_{i}}+4\prod_{i}R_{a_{i}}}\Bigg{\\}}$

$<err(h,k)<\frac{1}{k},$

where $i=1,2,3$,
$\lambda_{k}=\frac{R_{a_{1}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}+\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{1}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}-\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{1}}^{3}}{27\pi^{3}}}}$,
$\sigma_{k}=(\frac{2k-4}{3k}-\frac{\pi
R_{a_{1}}}{2\varphi})\pi\prod_{i}R_{a_{i}}-\frac{4\pi\prod_{i}R_{b_{i}}}{3k}$,
$\lambda_{k}^{\prime}=\frac{R_{b_{1}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}+\sqrt{\frac{\sigma_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b_{1}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}-\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{b_{1}}^{3}}{27\pi^{3}}}}$,
and $\sigma_{k}^{\prime}=(\frac{2k-4}{3k}-\frac{\pi
R_{b_{1}}}{2\varphi})\pi\prod_{i}R_{b_{i}}-\frac{4\pi\prod_{i}R_{a_{i}}}{3k}$.

####  6.2.2 Our insights

Insight $①$: tighter lower error bound. Let ${\rm lower}[err(h,k)]_{\rm
Sphere}$ and ${\rm lower}[err(h,k)]_{\rm Ellipsoid}$ be the lower bounds of
the generalization errors by geodesic search with sphere and ellipsoid,
respectively. With $R_{a_{1}}<R_{a}$, compare Theorems 1 and 2, we have the
following proposition.

######  Proposition 1.

Given a perceptron function $h={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$ that classifies
$A$ and $B$, and a sampling budget $k$. By drawing core-set on $S_{a}$ and
$S_{b}$, let $err(h,k)$ be the classification error rate with respect to $h$
and $k$, with Theorems 1 and 2, the lower bounds of geodesic search with
sphere and ellipsoid satisfy: ${\rm lower}[err(h,k)]_{\rm Ellipsoid}<{\rm
lower}[err(h,k)]_{\rm Sphere}$.

Insight $②$: higher probability of achieving a zero error. Let ${\rm
Pr}[err(h,k)=0]_{\rm Sphere}$ and ${\rm Pr}[err(h,k)=0]_{\rm Ellipsoid}$ be
the probabilities of achieving a zero error of geodesic search with sphere and
ellipsoid, respectively. Their relationship is presented in Proposition 2.

######  Proposition 2.

Given a perceptron function $h={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$ that classifies
$A$ and $B$, and a sampling budget $k$. By drawing core-set on $E_{a}$ and
$E_{b}$, let $err(h,k)$ be the classification error rate with respect to $h$
and $k$, with Assumptions 1 and 2, the probabilities of geodesic search with
sphere and ellipsoid satisfy: ${\rm Pr}[err(h,k)=0]_{\rm Ellipsoid}>{\rm
Pr}[err(h,k)=0]_{\rm Sphere}$.

Overall, geodesic search with ellipsoid is more effective than with sphere,
due to 1) tighter lower error bound, and 2) higher probability to achieve a
zero error.

###  6.3 High-dimensional generalizations

With the above insights, we next present a connection between 3-D
sphere/ellipsoid and ${\bm{d}}$-dimensional hyperesphere/hyperellipsoid, where
${\bm{d}}>3$. The major technique is to prove that the volume of the 3-D
sphere and ellipsoid are lower dimensional generalization of the
${\bm{d}}$-dimensional hypheresphere and hyperellipsoid, respectively.
References can refer to $n$-sphere [42], [43], and volume prototypes of
hyperellipsoids [44]. With volume generalization analysis, all proofs from
Theorems 1 to 2 and Propositions 1 and 2 can hold in ${\bm{d}}$-dimensional
geometry.

In the following, Theorems 3 and 4 then present a high-dimensional
generalization for the above theoretical results, in terms of the volume
functions of sphere and ellipsoid.

######  Theorem 3.

Let ${\rm Vol}_{\bm{d}}(S_{a})$ or ${\rm Vol}_{\bm{d}}(r_{a})$ be the volume
of ${\bm{d}}$-dimensional hypersphere $S_{a}$ with a radius $r_{a}$, given
$\vartheta\in[0,\pi]$, by performing integral operation on any
$({\bm{d}\text{-}1})$-dimensional hypersphere, there exists ${\rm
Vol}_{\bm{d}}$ can be approximated as ${\rm
Vol}_{\bm{m}}(S_{a})=\int_{0}^{\pi/2}2{\rm
Vol}_{\bm{m}\text{-}1}(r_{a}cos(\vartheta))r_{a}(cos(\vartheta))d\vartheta$,
and we define this operation as ${\rm Vol}_{\bm{m}}(S_{a})\bowtie{\rm
Vol}_{\bm{m}\text{-}1}(S_{a})$. Then, we know ${\rm
Vol}_{\bm{m}\text{-}1}(S_{a})\bowtie{\rm Vol}_{\bm{m}\text{-}2}(S_{a})$, ${\rm
Vol}_{\bm{m}\text{-}2}(S_{a})\bowtie{\rm Vol}_{\bm{m}\text{-}3}(S_{a})$, …,
${\rm Vol}_{\bm{4}}(S_{a})\bowtie{\rm Vol}_{\bm{3}}(S_{a})$. With this
progressive relationship, we can say ${\rm Vol}_{\bm{3}}(S_{a})$ is a low-
dimensional generalization of ${\rm Vol}_{\bm{d}}(S_{a})$.

The proof skills of Theorem 3 can refer to a mathematical perspective
111https://www.sjsu.edu/faculty/watkins/ndim.htm. Appendix A.8 also presents a
machine learning proof skill. Moreover, the proof of Theorem 3 can be adopted
in the generalization of 3-D ellipsoid to ${\bm{d}}$-D hyperellipsoid.

######  Theorem 4.

Let ${\rm Vol}_{\bm{d}}(E_{a})$ be the volume of a ${\bm{d}}$-dimensional
hyperellipsoid, given $\vartheta\in[0,\pi]$, by performing integral operation
on any $({\bm{d}\text{-}1}$)-dimensional hyperellipsoid, there exists ${\rm
Vol}_{\bm{m}-1}(S_{a})\bowtie{\rm Vol}_{\bm{m}\text{-}2}(S_{a})$, ${\rm
Vol}_{\bm{m}\text{-}2}(S_{a})\bowtie{\rm Vol}_{\bm{m}\text{-}3}(S_{a})$, …,
${\rm Vol}_{\bm{4}}(S_{a})\bowtie{\rm Vol}_{\bm{3}}(S_{a})$. With this
progressive relationship, we can say ${\rm Vol}_{\bm{3}}(E_{a})$ is a low-
dimensional generalization of ${\rm Vol}_{\bm{d}}(E_{a})$.

The volume of a hyperellipsoid can also be generalized by replacing the
operation $\prod_{i}R_{a}$ by the polar radius $\prod_{i}R_{a_{i}}$, for
$0<i<{\bm{d}}+1$, in the formula for the volume of a hypersphere. Proofs also
can refer to a mathematical
skill222https://www.sjsu.edu/faculty/watkins/ellipsoid.htm.

##  7 Experiments

In experiments, we start by showing how BALD degenerates its performance with
an uninformative prior and the 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 an uninformative prior? 2) can GBALD using the ranking
of Eq. (14) improve the informative acquisitions of model uncertainty? and 3)
can GBALD outperform the state-of-the-art acquisition approaches? Following
the experiment settings of [1, 5], we use MC dropout to implement the Bayesian
approximation of DNNs. Three benchmark datasets are selected: MNIST, SVHN, and
CIFAR10.

###  7.1 Baselines

To evaluate the performance of GBALD, several typical baselines from the
latest deep AL literature are selected.

  * •

Bayesian active learning by disagreement (BALD) [13]. It has been introduced
in Section 3.

  * •

Maximize variation ratio (Var) [1]. The algorithm chooses the unlabeled data
that maximizes its variation ratio of the probability:

$x^{*}=\operatorname*{arg\
max}_{x\in\mathcal{D}_{u}}\Big{\\{}1-\max_{y\in\mathcal{Y}}\ {\rm
Pr}(y|,x,\mathcal{D}_{0}))\Big{\\}}.$ (15)

  * •

Maximize entropy (Entropy) [1]. The algorithm chooses the unlabeled data that
maximizes the predictive entropy:

$x^{*}=\operatorname*{arg\
max}_{x\in\mathcal{D}_{u}}\Big{\\{}-\sum_{y\in\mathcal{Y}}{\rm
Pr}(y|x,\mathcal{D}_{0})){\rm log}\Big{(}{\rm
Pr}(y|x,\mathcal{D}_{0})\Big{)}\Big{\\}}.$ (16)

  * •

$k$-modoids [45]. A classical unsupervised algorithm that represents the input
distribution by $k$ clustering centers:

$\\{x_{1}^{*},x_{2}^{*},...,x_{k}^{*}\\}=\operatorname*{arg\
min}_{z_{1},z_{2},...,z_{k}}\Big{\\{}\sum_{i=1}^{k}\sum_{z_{i}\in\mathcal{X}^{k}}\|x_{i}-z_{i}\|\Big{\\}},$
(17)

where $\mathcal{X}^{k}$ denotes the $k$-th subcluster centered with $z_{i}$,
and $z_{i}\in\mathcal{X},\forall i$.

  * •

Greedy $k$-centers ($k$-centers) [8]. A geometric core-set interpretation on
sphere. See Eq. (4).

  * •

BatchBALD [5]. A batch extension of BALD which incorporates the diversity, not
maximal entropy as BALD, to rank the acquisitions:

$\begin{split}&\\{x^{*}_{t_{1}},...,x^{*}_{t_{b}}\\}\\\ &=\operatorname*{arg\
max}_{x_{t_{1}},...,x_{t_{b}}}{\rm H}(y_{t_{1}},...,y_{t_{b}})-{\rm
E}_{p(\theta|\mathcal{D}_{0})}[{\rm H}(y_{t_{1}},...,y_{t_{b}}|\theta)],\\\
\end{split}$ (18)

where ${\rm H}(y_{t_{1}},...,y_{t_{b}})$ denote the expected entropy over all
possible labels from $y_{t_{1}}$ to $y_{t_{b}}$ such that ${\rm
H}(y_{t_{1}},....,y_{t_{b}})={\rm E}_{p}(y_{t_{1}},..,y_{t_{b}})[-{\rm
log}p(y_{t_{1}},..,y_{t_{b}}]$, and ${\rm E}_{p(\theta|\mathcal{D}_{0})}[{\rm
H}(y_{t_{1}},...,y_{t_{b}}|\theta)]$ is estimated by MC sampling [26] [46] a
subset from $\mathcal{X}$ which approximates the parameter distributions of
$\theta$.

Parameters of GBALD. The parameter settings of Eq. (5) are $R_{0}=2.0e+3$ and
$\eta=$0.9. Accuracy of each acquired dataset of the experiments are averaged
over 3 runs.

###  7.2 Uninformative priors

As discussed in the introduction, BALD is sensitive to an uninformative prior,
i.e. $p(\mathcal{D}_{0}|\theta)$. We thus initialize $\mathcal{D}_{0}$ from a
fixed class of the training data of datasets to observe its acquisition
performance. In this way, $p(\mathcal{D}_{0}|\theta)$ is uninformative due to
extreme label category.

Figure 3 presents the prediction accuracies of BALD with an acquisition budget
of 130 over the training set of MNIST. Based on the uninformative setting of
$p(\mathcal{D}_{0}|\theta)$, we randomly select 20 samples from digit ‘0’ and
‘1’ to initialize $\mathcal{D}_{0}$, respectively. The classification model of
AL follows a convolutional neural network (CNN) 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 as with [5].

(a) Digit ‘0’

(b) Digit ‘1’

Figure 3: Acquisitions with uninformative priors from digit ‘0’ and ‘1’.

As the figure shown, BALD can slowly accelerate the training model due to the
biased initial acquisitions, which cannot uniformly cover all the label
categories. Moreover, the uninformative prior guides BALD to unstable
acquisition results. Specifically, in Figure 3(b), BALD with Bathsize = 10
shows better performance than that of Batchsize =1; while BALD in Figure 3(a)
keeps stable performance. This is because the initial labeled data does not
cover all classes and BALD with Batchsize =1 may further be misled to select
those samples from one or a few fixed classes at the first acquisitions.
However, Batchsize >1 may result in a random acquisition process that possibly
covers more diverse labels at its first acquisitions. Another excursive result
of BALD is that the increasing batch size cannot degenerate its acquisition
performance in Figure 3(b). For example, Batchsize =10 $\succ$ Batchsize =1
$\succ$ Batchsize =20,40 $\succ$ Batchsize =30, where ‘$\succ$’ denotes
‘better’ performance; Batchsize = 20 achieves similar results as with
Batchsize =40. This undermines the acquisition policy of BALD: its performance
would be degenerated when the batch size increases, and sometimes worse than
random sampling. This also is the reason why we utilize a core-set to start
BALD in our framework.

Different to BALD, core-set construction of GBALD using Eq. (11) provides a
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 a batch size of 1 and sequence size of 10 (i.e.
breakpoints of acquired size are 10, 20, …, 130) achieves significantly higher
accuracies than BALD using different batch sizes since BALD misguides the
network updating using a poor prior.

(a) Digit ‘0’

(b) Digit ‘1’

Figure 4: GBALD outperforms BALD using ranked informative acquisitions which
cooperate with representation constraints.

###  7.3 Improved informative acquisitions

For BALD, repeated or similar acquisitions can easily delay the acceleration
or improvement of the model training. Following the experiment settings of
Section 7.1, we compare the best performance of BALD with a batch size of 1
and GBALD with different batch size parameters. Following Eq. (14), we set
$b=\\{3,5,7\\}$ and $b^{\prime}$=1, respectively, that means, we output the
most representative data from a batch of highly-informative acquisitions.
Different settings on $b$ and $b^{\prime}$ are used to observe the parameter
perturbations of GBALD.

Training by the same parameterized CNN model as in Section 7.2, Figure 4
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-informative samples and selects the most
representative ones. By employing this special ranking strategy, GBALD can
reduce the probability of sampling those nearby data of the previous
acquisitions. It is thus GBALD significantly outperforms BALD, even if we
progressively increase the ranked batch size $b$.

###  7.4 Active acquisitions

GBALD using Eqs. (11) and (14) has been demonstrated to achieve successful
improvements over BALD. We thus combine these two components into a uniform
framework. Figure 5 presents the AL accuracies using different acquisition
algorithms on the three image datasets. The selected baselines follow [1]
including 1) maximizing the variation ratios (Var), 2) BALD, 3) maximizing the
entropy (Entropy), 4) $k$-medoids, and one greedy 5) $k$-centers approach [8].
The network architecture is a three-layer multi-layer perceptron (MLP) 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
[5]. The initial labeled data of MNIST, SVHN and CIFAR-10 are 20, 1000, 1000
random samples from their full training sets, respectively.

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,b^{\prime}=100$.
As the learning curves shown in Figure 5, 1) $k$-centers algorithm performs
more poorly than the other compared baselines because the representation
optimization with the sphere geodesic usually falls into the selection of the
boundary data; 2) Var, Entropy, and BALD algorithms cannot accelerate the
network model rapidly due to those 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 and the results are not
strong; 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 set 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. The
advantages of these two acquisition paradigms are integrated to present higher
accuracies than any single paradigm.

(a) MNIST

(b) SVHN

(c) CIFAR10

Figure 5:  Active acquisitions on MNIST, SVHN, and CIFAR10 datasets.  TABLE I:
Mean$\pm$std of the test accuracies of the breakpoints of the learning curves
on MNIST, SVHN, and CIFAR-10.

Datasets |  | Algorithms |
---|---|---|---
Var | BALD | Entropy |  $k$-medoids |  $k$-centers | GBALD
MNIST | 0.8419$\pm$ 0.1721 | 0.8645$\pm$0.1909 | 0.8498$\pm$0.2098 | 0.8785$\pm$0.1433 | 0.8052$\pm$0.1838 | 0.9106$\pm$0.1296
SVHN | 0.8535$\pm$0.1098 | 0.8510$\pm$0.1160 | 0.8294$\pm$0.1415 | 0.8498$\pm$0.1294 | 0.7909$\pm$0.1235 | 0.8885$\pm$0.1054
CIFAR-10 | 0.7122$\pm$0.1034 | 0.6760$\pm$0.1023 | 0.6536$\pm$0.1038 | 0.71837$\pm$0.1245 | 0.5890$\pm$0.1758 | 0.7440$\pm$0.1087

TABLE II: Number of acquisitions on MNIST, SVHN and CIFAR10 until 70%, 80%,
and 90% accuracies are reached.

Algorithms |  | Accuracies |
---|---|---|---
70% | 80% | 90%
Var | 140/1,700/5,700 | 150/2,200/>20,000 | 210/>10,000/>6,100
BALD | 110/1,700 /8,800 | 120 /2,300/>20,000 | 190/7,100 / >20,000
Entropy | 110/1,900/11,200 | 150/2,400/>20,000 | 200/8,600/>20,000
$k$-modoids | 70/1,700/5,900 | 90/2,200/16,000 |  170/6,200 />20,000
$k$-centers | 110/2,000/10,100 | 150/3,800/>20,000 | 280/>10,000/>20,000
GBALD | 50/1,400/4,800 | 70/1,900/12,200 |  170/3,900/>20,000

Table 1 reports the mean$\pm$std values of the test accuracies of the
breakpoints of the learning curves in Figure 5, where the breakpoints of MNIST
are $\\{0,10,20,30,...,600\\}$, the breakpoints of SVHN are
$\\{0,100,200,...,10000\\}$, and the breakpoints of CIFAR10 are
$\\{0,100,200,...,20000\\}$. We then calculate their average accuracies and
std values over these acquisition points. As the shown in Table 1, all std
values around 0.1, yielding a norm value. Usually, an average accuracy on the
same acquisition size with different random seeds of DNNs, will result a small
std value. Our mean accuracy spans across the whole learning curve.

The results show that 1) GBALD achieves the highest average accuracies;
2)$k$-medoids is ranked the second amongst the compared baselines; 3)
$k$-centers has ranked the worst accuracies amongst these approaches; 4) 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 CIFAR10, respectively. The results show that GBALD can use
fewer acquisitions to achieve a desired accuracy than the other algorithms.

###  7.5 Active acquisitions with repeated samples

Repeatedly collecting samples in the establishment of a database is very
common. Those repeated samples may be continuously evaluated as the primary
acquisitions of AL due to the lack of one or more categories 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 as $k$-medoids and $k$-centers,
have been shown that they cannot accelerate the training in terms of the
experiment results of Section 7.3. Thus, we are no longer studying their
performance. The network architecture still follows the settings of Section
7.3.

The acquisition results over the repeated SVHN datasets are 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^{\prime}=100$. The mean$\pm$std values of these baselines of the
breakpoints (i.e. $\\{0,100,200,...,10000\\}$) are reported in Table 3. The
results demonstrate that GBALD shows slighter perturbations on the repeated
samples than Var and BALD because it draws the core-set from the input
distribution as the initial acquisitions, leading a 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, the 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 no interactions with the network architecture.

(a) Var

(b) BALD

(c) GBALD

Figure 6: Active acquisitions on SVHN with 5,000 and 10,000 repeated samples.
TABLE III: Mean$\pm$std of active acquisitions on SVHN with 5,000 and 10,000
repeated samples.

Algorithms |  | Accuracies |
---|---|---|---
0 repeats | 5,000 repeats | 10,000 repeats
Var | 0.8535$\pm$0.1098 | 0.8478$\pm$0.1074 | 0.8281$\pm$0.1082
BALD | 0.8510$\pm$0.1160 | 0.8119$\pm$0.1216 | 0.7689$\pm$0.1288
GBALD | 0.8885$\pm$0.1054 | 0.8694$\pm$0.1032 | 0.8630$\pm$0.1002

###  7.6 Active acquisitions with noisy samples

Noisy labels [9, 47] are inevitable due to 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, we 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’,‘1’,…,‘8’$\\}$ to $\\{$‘1’,‘2’,…,‘9’$\\}$, respectively. The network
architecture follows the MLP of Section 7.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 to select 100 data for the training, i.e. $b=300,b^{\prime}=100$.
Table 4 presents the mean$\pm$std values of the breakpoints (i.e.
$\\{0,100,200,...,10000\\}$) over learning curves of Figure 7. The results
further show that GBALD has smaller noisy perturbations than the other
baselines. For Var and BALD, model uncertainty leads high probabilities to
sample those noisy data due to their greatly updating on the model.

(a) Var

(b) BALD

(c) GBALD

Figure 7: Active noisy acquisitions on SVHN with 5,000 and 10,000 noisy
labels.  TABLE IV: Mean$\pm$std of active noisy acquisitions on SVHN with
5,000 and 10,000 noises.

Algorithms |  | Accuracies |
---|---|---|---
0 noises | 5,000 noises | 10,000 noises
Var | 0.8535$\pm$0.1098 | 0.7980$\pm$0.1203 | 0.7702$\pm$0.1238
BALD | 0.8510$\pm$0.1160 | 0.8205$\pm$0.1185 | 0.7849$\pm$0.1239
GBALD | 0.8885$\pm$0.1054 | 0.8622$\pm$0.0991 | 0.8301$\pm$0.0916

###  7.7 GBALD vs. BatchBALD

Batch deep AL was recently proposed to accelerate the training of a DNN model.
In recent literature, BatchBALD [5] extended BALD with a batch acquisition
setting to converge the network using fewer iteration loops. Different to
BALD, BathBALD introduces the diversity to avoid the repeated or similar
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 a theoretical view, the larger the batch size, the
worse the batch acquisitions will be. Experimental results of [5] also
demonstrated this phenomenon. We thus set different batch sizes to run
BatchBALD. Figure 8 presents the comparison results of BALD, BatchBALD, and
our proposed GBALD as with the experiment settings of Section 7.3. As the
shown in this figure, BatchBALD degenerates the test accuracies if we
progressively increase the bath sizes, where BatchBALD with a batch size of 10
keeps similar learning curves as BALD. It shows that BatchBALD actually can
accelerate BALD with a similar acquisition result if the batch size is not
large. This means, if the batch size is between 2 to 10, BatchBALD will
degenerate into BALD and maintains highly-consistent results.

Figure 8: Comparisons of BALD, BatchBALD, and GBALD of active acquisitions on
MNIST with bath settings.

Also because of this, BatchBALD also has the same sensitivity to an
uninformative prior. For our GBALD, the core-set solicits sufficient data
which properly matches the input distribution (w.r.t. acquired data set size
$\leq$ 100), providing expressive input features to start the DNN model
(w.r.t. acquired data set size $>$ 100). Table 5 then presents the
mean$\pm$std of the breakpoints ($\\{0,10,20,...,600\\}$) of active
acquisitions on MNIST with batch settings. The statistical results show that
GBALD has much higher mean accuracy than BatchBALD with different bath sizes.
Therefore, evaluating the model uncertainty of DNN using those highly-
representative core-set samples can improve the performance of the neural
network.

TABLE V: Mean$\pm$std of BALD, BatchBALD, and GBALD of active acquisitions on
MNIST with batch settings.

Algorithms |  Batch sizes |  Accuracies
---|---|---
BALD |  1 |  0.8654$\pm$0.0354
BatchBALD |  10 |  0.8645$\pm$0.0365
BatchBALD |  40 |  0.8273$\pm$0.0545
BatchBALD |  100 |  0.7902$\pm$0.0951
GBALD |  3 |  0.9106$\pm$0.1296

###  7.8 Acceleration of accuracy

Accelerations of accuracy i.e. the first-orders of the breakpoints of the
learning curve, describe the efficiency of the active acquisition loops.
Different to the accuracy curves, the acceleration curve reflects how active
acquisitions help the convergence of the interacting DNN model.

We thus firstly present the acceleration curves of different baselines on
MNIST, SVHN, and CIFAR10 datasets as with the experiments of Section 7.3. The
acceleration curves of active acquisitions are drawn in Figure 9. Observing
those acceleration curves of different algorithms clearly finds 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 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 DNNs. The
acceleration curves of active noisy acquisitions are drawn in Figure 11.
Compared to Figure 7, it presents more intuitive descriptions for the noisy
perturbations to different baselines. With horizontal comparisons to the
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) both the highly representative and informative
acquisitions of the model uncertainty.

(a) MNIST

(b) SVHN

(c) CIFAR10

Figure 9: Accelerations of accuracy of different baselines on MNIST, SVHN, and
CIFAR10 datasets.

(a) Var

(b) BALD

(c) GBALD

Figure 10: Accelerations of accuracy of active acquisitions on SVHN with 5,000
and 10,000 repeated samples.

(a) Var

(b) BALD

(c) GBALD

Figure 11: Accelerations of accuracy of active noisy acquisitions on SVHN with
5,000 and 10,000 noisy labels.

###  7.9 Hyperparameter settings

What is the proper time to start active acquisitions using Eq. (14) in GBALD
framework? Does the size ratio of the core-set and model uncertainty
acquisitions affect the performance of GBALD?

We discuss the key hyperparameter of GBALD here: the core-set size
$N_{\mathcal{M}}$. Table 6 presents the relationship of accuracies and size of
core-set, where start accuracy denotes the test accuracy over the initial
core-set, and ultimate accuracy denotes the test accuracy over up to
$Q=20,000$ training data. Let $b=1000,b^{\prime}=500$ in GBALD,
$\mathcal{N}_{\mathcal{M}}$ be the number of the core-set size, the iteration
budget $\mathcal{A}$ of GBALD can then be defined as
$\mathcal{A}=(Q-\mathcal{N}_{\mathcal{M}})/b^{\prime}$. For example, if the
number of the initial core-set labels are set as
$\mathcal{N}_{\mathcal{M}}=1,000$, we have
$\mathcal{A}=(Q-\mathcal{N}_{\mathcal{M}})/b^{\prime}\approx 38$; if
$\mathcal{N}_{\mathcal{M}}=2,000$, then
$\mathcal{A}=(Q-\mathcal{N}_{\mathcal{M}})/b^{\prime}\approx 36$.

From Table 6, the GBALD algorithm keeps stable accuracies over the start,
ultimate, and mean$\pm$std 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 Eq. (14) can maximize the performance of our
GBALD framework.

TABLE VI: Relationship of accuracies and sizes of core-set on SVHN.

Size of core-set |  | Accuracies |
---|---|---|---
Start accuracy | Ultimate accuracy | Mean$\pm$std accuracy
$N_{\mathcal{M}}=$ 1,000 | 0.8790 | 0.9344 | 0.9134$\pm$0.0169
$N_{\mathcal{M}}=$ 2,000 | 0.8898 | 0.9212 | 0.9151$\pm$0.0148
$N_{\mathcal{M}}=$ 3,000 | 0.8848 | 0.9364 | 0.9173$\pm$0.0138
$N_{\mathcal{M}}=$ 4,000 | 0.8811 | 0.9271 | 0.9146$\pm$0.0165
$N_{\mathcal{M}}=$ 5,000 | 0.8959 | 0.9342 | 0.9197$\pm$0.0117

(a) MNIST

(b) SVHN

(c) CIFAR10

Figure 12: A pairwise penalty matrix over active acquisitions on MNIST, SVHN,
and CIFAR10. Column-wise values at the bottom of each matrix show the overall
performance of the compared baselines (larger value has more significant
superior performance).

Hyperparameter settings on batch returns $b$ and bath outputs $b^{\prime}$.
Experiments of Sections 7.1 and 7.2 used different $b$ and $b^{\prime}$ to
observe the parameter perturbations. No matter what the settings of
$b^{\prime}$ and $b$ are, GBALD still outperforms BALD. For single acquisition
of GBALD, we suggest $b=3$ and $b^{\prime}=1$. For bath acquisitions, the
settings on $b^{\prime}$ and $b$ are user-defined according the time cost and
hardware resources.

Hyperparameter setting on iteration budget $\mathcal{A}$. Given the
acquisition budget $Q$, let $b^{\prime}$ be the number of the output returns
at each loop, $\mathcal{N}_{\mathcal{M}}$ be the number of the core-set size,
the iteration budget $\mathcal{A}$ of GBLAD then can be defined as
$\mathcal{A}=(Q-\mathcal{N}_{\mathcal{M}})/b^{\prime}$.

Other hyperparameter settings. Eq. (5) has one parameter $R_{0}$ which
describes the geometric prior from probability. The default radius of the
intern balls $R_{0}$ is used to legalize the prior and has no further
influences on Eq. (10). It is set as $R_{0}=2.0e+3$ for those three image
datasets. Ellipsoid geodesic is adjusted by $\eta$ which controls how far of
the updates of core-set to the boundaries of distributions. It is set as
$\eta=0.9$ in this paper.

###  7.10 Two-sided $t$-test

We present two-sided (two-tailed) $t$-test [48] [49] for the learning curves
of Figure 5. Different to the mean$\pm$ std of Table 1, $t$-test can enlarge
the significant difference of those baselines. In the typical $t$-test, the
two groups of observations usually require a degree of freedom smaller than
30. However, the numbers of the breakpoints of MNIST, SVHN, and CIFAR10 are
61, 101, and 201, respectively, thereby holding a degree of freedom of 60,
100, 200, respectively. It is thus we introduce $t$-test score to directly
compare the significant difference of the pairwise baselines.

$t$-test score between any pair group of breakpoints are defined as follows.
Let $B_{1}=\\{\alpha_{1},\alpha_{2},...,\alpha_{n}\\}$ and
$B_{2}=\\{\beta_{1},\beta_{2},...,\beta_{n}\\}$, there exists $t$-score of

$t-{\rm score}=\sqrt{n}\frac{\mu}{\sigma},$

where $\mu=\frac{1}{n}\sum_{i=1}^{n}(\alpha_{i}-\beta_{i})$, and
$\sigma=\sqrt{\frac{1}{n-1}\sum_{i=1}^{n}(\alpha_{i}-\beta_{i}-\mu)^{2}}$.

In two-sided $t$-test, $B_{1}$ beats $B_{2}$ on breakpoints $\alpha_{i}$ and
$\beta_{i}$ satisfying a condition of $t-{\rm score}>\nu$; $B_{2}$ beats
$B_{1}$ on breakpoints $\alpha_{i}$ and $\beta_{i}$ satisfying a condition of
$t-{\rm score}<-\nu$, where $\nu$ denotes the hypothesized criterion with a
given confidence risk. Following [50], we add a penalty of $\frac{1}{e}$ to
each pair of breakpoints, which further enlarges their differences in the
aggregated penalty matrix, where $e$ denotes the number of $B_{1}$ beats
$B_{2}$ on all breakpoints. All penalty values finally calculate their $L_{1}$
expressions.

Figure 12 presents the penalty matrix over the learning curves of Figure 5.
Column-wise values at the bottom of each matrix show the overall performance
of the compared baselines. As the shown results, GBALD has significant
performance than that of the other baselines over the three datasets.
Especially for SVHN, it has superior performance.

##  8 Conclusion

We have introduced a novel Bayesian AL framework termed GBALD from the
perspective of geometry, which seamlessly incorporates the representative
(core-set) and informative (model uncertainty estimation) acquisitions to
accelerate the training of a DNN model. Our GBALD yields significant
improvements over BALD, flexibly resolving the limitations of an uninformative
prior and the redundant information by optimizing the acquisition on an
ellipsoid. Generalization analysis has asserted that, geodesic search with
ellipsoid has tighter lower error bound and higher probability to achieve a
zero error, than that of geodesic search with sphere. Compared to the
representative or informative acquisition algorithms, experiments show that
our GBALD spends much fewer acquisitions to accelerate the convergence of
training model. Moreover, it keeps slighter accuracy reduction than other
baselines against repeated and noisy acquisitions. Leveraging the acquisition
sizes of the geometric core-set decides how our framework interacts with the
representative and informative acquisitions. It will be a future work of Auto-
AL that derives an advanced AL pipeline.

## References

  * [1] Y. Gal, R. Islam, and Z. Ghahramani, “Deep bayesian active learning with image data,” in _Proceedings of the 34th International Conference on Machine Learning-Volume 70_. JMLR. org, 2017, pp. 1183–1192.
  * [2] A. Ashukha, A. Lyzhov, D. Molchanov, and D. Vetrov, “Pitfalls of in-domain uncertainty estimation and ensembling in deep learning,” in _International Conference on Learning Representations_ , 2019.
  * [3] B. Lakshminarayanan, A. Pritzel, and C. Blundell, “Simple and scalable predictive uncertainty estimation using deep ensembles,” in _Advances in neural information processing systems_ , 2017, pp. 6402–6413.
  * [4] R. Pinsler, J. Gordon, E. Nalisnick, and J. M. Hernández-Lobato, “Bayesian batch active learning as sparse subset approximation,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 6356–6367.
  * [5] A. Kirsch, J. van Amersfoort, and Y. Gal, “Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 7024–7035.
  * [6] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra, “Weight uncertainty in neural network,” in _International Conference on Machine Learning_ , 2015, pp. 1613–1622.
  * [7] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” in _international conference on machine learning_ , 2016, pp. 1050–1059.
  * [8] O. Sener and S. Savarese, “Active learning for convolutional neural networks: A core-set approach,” in _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018. [Online]. Available: https://openreview.net/forum?id=H1aIuk-RW
  * [9] D. Golovin, A. Krause, and D. Ray, “Near-optimal bayesian active learning with noisy observations,” in _Advances in Neural Information Processing Systems_ , 2010, pp. 766–774.
  * [10] K. Jedoui, R. Krishna, M. Bernstein, and L. Fei-Fei, “Deep bayesian active learning for multiple correct outputs,” _arXiv preprint arXiv:1912.01119_ , 2019.
  * [11] A. Doucet, S. Godsill, and C. Andrieu, “On sequential monte carlo sampling methods for bayesian filtering,” _Statistics and computing_ , vol. 10, no. 3, pp. 197–208, 2000.
  * [12] S. A. Vavasis, “Approximation algorithms for indefinite quadratic programming,” _Mathematical Programming_ , vol. 57, no. 1-3, pp. 279–311, 1992.
  * [13] N. Houlsby, F. Huszár, Z. Ghahramani, and M. Lengyel, “Bayesian active learning for classification and preference learning,” _arXiv preprint arXiv:1112.5745_ , 2011.
  * [14] R. W. Strachan and H. K. Van Dijk, “Bayesian model selection with an uninformative prior,” _Oxford Bulletin of Economics and Statistics_ , vol. 65, pp. 863–876, 2003.
  * [15] H. J. Price and A. R. Manson, “Uninformative priors for bayes’ theorem,” in _AIP Conference Proceedings_ , vol. 617, no. 1, 2002, pp. 379–391.
  * [16] M. Gao, Z. Zhang, G. Yu, S. O. Arik, L. S. Davis, and T. Pfister, “Consistency-based semi-supervised active learning: Towards minimizing labeling cost,” _ECCV_ , 2020.
  * [17] T. Campbell and T. Broderick, “Bayesian coreset construction via greedy iterative geodesic ascent,” in _International Conference on Machine Learning_ , 2018, pp. 698–706.
  * [18] F. Nie, H. Wang, H. Huang, and C. Ding, “Early active learning via robust representation and structured sparsity,” in _Twenty-Third International Joint Conference on Artificial Intelligence_ , 2013.
  * [19] Z. Wang, B. Du, W. Tu, L. Zhang, and D. Tao, “Incorporating distribution matching into uncertainty for multiple kernel active learning,” _IEEE Transactions on Knowledge and Data Engineering_ , 2019.
  * [20] V. Perrone, H. Shen, M. W. Seeger, C. Archambeau, and R. Jenatton, “Learning search spaces for bayesian optimization: Another view of hyperparameter transfer learning,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 12 771–12 781.
  * [21] M. Sugiyama, “Active learning in approximately linear regression based on conditional expectation of generalization error,” _Journal of Machine Learning Research_ , vol. 7, no. Jan, pp. 141–166, 2006.
  * [22] D. Cohn, L. Atlas, and R. Ladner, “Improving generalization with active learning,” _Machine learning_ , vol. 15, no. 2, pp. 201–221, 1994.
  * [23] G. Schohn and D. Cohn, “Less is more: Active learning with support vector machines,” in _ICML_ , vol. 2, no. 4. Citeseer, 2000, p. 6.
  * [24] D. D. Lewis and W. A. Gale, “A sequential algorithm for training text classifiers,” in _SIGIR’94_. Springer, 1994, pp. 3–12.
  * [25] T. Scheffer, C. Decomain, and S. Wrobel, “Active hidden markov models for information extraction,” in _International Symposium on Intelligent Data Analysis_. Springer, 2001, pp. 309–318.
  * [26] N. Roy and A. McCallum, “Toward optimal active learning through monte carlo estimation of error reduction,” _ICML, Williamstown_ , pp. 441–448, 2001\.
  * [27] K. Yu, J. Bi, and V. Tresp, “Active learning via transductive experimental design,” in _Proceedings of the 23rd international conference on Machine learning_ , 2006, pp. 1081–1088.
  * [28] A. Krishnamurthy, A. Agarwal, T.-K. Huang, H. Daumé III, and J. Langford, “Active learning for cost-sensitive classification.” _Journal of Machine Learning Research_ , vol. 20, no. 65, pp. 1–50, 2019.
  * [29] S. Sinha, S. Ebrahimi, and T. Darrell, “Variational adversarial active learning,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 5972–5981.
  * [30] S. Hanneke, “A bound on the label complexity of agnostic active learning,” in _Proceedings of the 24th international conference on Machine learning_ , 2007, pp. 353–360.
  * [31] S. Javdani, Y. Chen, A. Karbasi, A. Krause, D. Bagnell, and S. S. Srinivasa, “Near optimal bayesian active learning for decision making.” in _AISTATS_ , vol. 14, 2014, pp. 430–438.
  * [32] M. Tang, X. Luo, and S. Roukos, “Active learning for statistical natural language parsing,” in _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_. Association for Computational Linguistics, 2002, pp. 120–127.
  * [33] A. Siddhant and Z. C. Lipton, “Deep bayesian active learning for natural language processing: Results of a large-scale empirical study,” in _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , 2018, pp. 2904–2909.
  * [34] S. Burkhardt, J. Siekiera, and S. Kramer, “Semisupervised bayesian active learning for text classification,” in _Bayesian Deep Learning Workshop at NeurIPS_ , 2018.
  * [35] T. Tran, T.-T. Do, I. Reid, and G. Carneiro, “Bayesian generative active deep learning,” in _International Conference on Machine Learning_ , 2019, pp. 6295–6304.
  * [36] T. Campbell and T. Broderick, “Automated scalable bayesian inference via hilbert coresets,” _The Journal of Machine Learning Research_ , vol. 20, no. 1, pp. 551–588, 2019.
  * [37] M. Bādoiu, S. Har-Peled, and P. Indyk, “Approximate clustering via core-sets,” in _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , 2002, pp. 250–257.
  * [38] S. Har-Peled and S. Mazumdar, “On coresets for k-means and k-median clustering,” in _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , 2004, pp. 291–300.
  * [39] A. Lou, I. Katsman, Q. Jiang, S. Belongie, S.-N. Lim, and C. De Sa, “Differentiating through the frechet mean,” _ICML_ , 2020.
  * [40] S. Ben-David and U. Von Luxburg, “Relating clustering stability to properties of cluster boundaries,” in _21st Annual Conference on Learning Theory (COLT 2008)_. Omnipress, 2008, pp. 379–390.
  * [41] W. Li, G. Dasarathy, K. Natesan Ramamurthy, and V. Berisha, “Finding the homology of decision boundaries with active learning,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * [42] N. Barnea, “Hyperspherical functions with arbitrary permutational symmetry: Reverse construction,” _Physical Review A_ , vol. 59, no. 2, p. 1135, 1999\.
  * [43] L. Blumenson, “A derivation of n-dimensional spherical coordinates,” _The American Mathematical Monthly_ , vol. 67, no. 1, pp. 63–66, 1960.
  * [44] U. Kaymak and M. Setnes, “Fuzzy clustering with volume prototypes and adaptive cluster merging,” _IEEE Transactions on Fuzzy Systems_ , vol. 10, no. 6, pp. 705–712, 2002.
  * [45] H.-S. Park and C.-H. Jun, “A simple and fast algorithm for k-medoids clustering,” _Expert systems with applications_ , vol. 36, no. 2, pp. 3336–3341, 2009.
  * [46] M. Osborne, R. Garnett, Z. Ghahramani, D. K. Duvenaud, S. J. Roberts, and C. E. Rasmussen, “Active learning of model evidence using bayesian quadrature,” in _Advances in neural information processing systems_ , 2012, pp. 46–54.
  * [47] B. Han, Q. Yao, X. Yu, G. Niu, M. Xu, W. Hu, I. Tsang, and M. Sugiyama, “Co-teaching: Robust training of deep neural networks with extremely noisy labels,” in _Advances in neural information processing systems_ , 2018, pp. 8527–8537.
  * [48] J. L. Hodges, E. L. Lehmann _et al._ , “The efficiency of some nonparametric competitors of the $t$-test,” _The Annals of Mathematical Statistics_ , vol. 27, no. 2, pp. 324–335, 1956.
  * [49] P. Donmez, J. G. Carbonell, and P. N. Bennett, “Dual strategy active learning,” in _European Conference on Machine Learning_. Springer, 2007, pp. 116–127.
  * [50] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal, “Deep batch active learning by diverse, uncertain gradient lower bounds,” in _International Conference on Learning Representations_ , 2019.

Figure 13: Assumption of the generalization analysis. The ball above $h$
denotes $S_{b}$, the ball below $h$ denotes $S_{a}$, and $R_{b}<R_{a}$.
Spherical cap1 of the half-sphere of $S_{a}$ is denoted as $\mathcal{D}$.

### A.1 Case study of generalization analysis of $err(h,3)$ of geodesic search
with sphere

######  Theorem 5.

Given a perceptron function $h={w_{1}x_{1}+w_{2}x_{2}+w_{3}}$ that classifies
$A$ and $B$, and a sampling budget $k$. By drawing core-set on $S_{a}$ and
$S_{b}$, the minimum distance to the boundaries of that core-set elements of
$S_{A}$ and $S_{B}$, are defined as $d_{a}$ and $d_{b}$, respectively. Let
$err(h,k)$ be the classification error rate with respect to $h$ and $k$, given
$\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, we have an
inequality of error:

${\rm
min}\Bigg{\\{}\frac{(2R_{a}+t)(R_{a}-t)^{2}}{4R_{a}^{3}+4R_{b}^{3}},\frac{(2R_{b}+t^{\prime})(R_{b}-t^{\prime})^{2}}{4R_{b}^{3}+4R_{a}^{3}}\Bigg{\\}}<err(h,3)<0.3334,$

where
$t=\frac{R_{a}^{2}}{3}+\sqrt[3]{-\frac{\mu}{2\pi}+\sqrt{\frac{\mu^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu}{2\pi}-\sqrt{\frac{\mu^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}$,
$\mu=(\frac{2}{9}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{9}$,
$t^{\prime}=\frac{R_{b}^{2}}{3}+\sqrt[3]{-\frac{\mu^{\prime}}{2\pi}+\sqrt{\frac{\mu^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu^{\prime}}{2\pi}-\sqrt{\frac{\mu^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}$, and
$\mu^{\prime}=(\frac{2}{9}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{b}^{3}-\frac{4\pi R_{a}^{3}}{9}$.

###### Proof.

Given the unseen acquisitions of $\\{q_{a},q_{b},q^{*}\\}$, where $q_{a}\in
A$, $q_{b}\in B$, and $q^{*}\in A$ or $q^{*}\in B$ is uncertain. However, the
position of $q^{*}$ largely decides $h$. Therefore, the proof studies the
error bounds highly related to $q^{*}$ in terms of two cases: $R_{a}\geq
R_{b}$ and $R_{a}<R_{b}$.

1) If $R_{a}\geq R_{b}$, $q^{*}\in{A}$. Estimating the position of $q^{*}$
starts from the analysis on $q_{a}$. Given the volume function ${\rm
Vol}(\cdot)$ over the 3-D geometry, we know: ${\rm
Vol}({A})=\frac{4\pi}{3}R_{a}^{3}$ and ${\rm
Vol}({B})=\frac{4\pi}{3}R_{b}^{3}$. Given $k=3$ over $S_{a}$ and $S_{b}$, we
define the minimum distance of $q_{a}$ to the boundary of ${A}$ as $d_{a}$.
Let $S_{a}$ be cut off by a cross section $h^{\prime}$, where $\mathcal{C}$ be
the cut and $\mathcal{D}$ be the _spherical cap_
333https://en.wikipedia.org/wiki/Spherical_cap of the half-sphere (see Figure
13) that satisfy

${\rm Vol}(\mathcal{C})=\frac{2}{3}\pi R_{a}^{3}-{\rm
Vol}(\mathcal{D})=\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{9},$ (19)

and the volume of $\mathcal{D}$ is

$\begin{split}{\rm
Vol}(\mathcal{D})&=\pi(\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}})^{2}(R_{a}-d_{a})+\int_{0}^{2\pi\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}}}\frac{{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}}{2\pi}\pi R_{a}^{2}\ dx\\\
&=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\frac{{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}}{2\pi}\pi
R_{a}^{2}(2\pi\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}})\\\
&=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\pi R_{a}^{2}{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}}.\\\
\end{split}$ (20)

Let $\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, Eq. (20) can
be written as

$\begin{split}{\rm
Vol}(\mathcal{D})=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\frac{\pi
R_{a}^{3}}{\varphi}cos\frac{\pi}{\varphi}.\\\ \end{split}$ (21)

Introducing Eq. (21) to Eq. (19), we have

$\begin{split}(\frac{2}{3}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})=\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{9}.\end{split}$
(22)

Let $t=R_{a}-d_{a}$, Eq. (22) can be rewritten as

$\begin{split}\pi t^{3}-\pi
R_{a}^{2}t+(\frac{2}{9}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{9}=0.\end{split}$ (23)

To simplify Eq. (23), let
$\mu=(\frac{2}{9}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{9}$, Eq. (23) then can be written as

$\begin{split}\pi t^{3}-\pi R_{a}^{2}t+\mu=0.\end{split}$ (24)

The positive solution of $t$ can be

$\begin{split}&t=\frac{R_{a}^{2}}{3}+\sqrt[3]{-\frac{\mu}{2\pi}+\sqrt{\frac{\mu^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu}{2\pi}-\sqrt{\frac{\mu^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}.\end{split}$
(25)

Based on Eq. (19), we know

$\begin{split}{\rm Vol}(\mathcal{D})&=\frac{2}{3}\pi
R_{a}^{3}-\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{9}\\\ &=\frac{2}{9}\pi
R_{a}^{3}-\frac{4}{9}\pi R_{b}^{3}>0.\\\ \end{split}$ (26)

Thus, $\sqrt[3]{2}R_{b}<R_{a}$. We next prove $q^{*}\in{A}$. Based on Eq.
(26), we know

$\begin{split}\pi R_{b}^{3}<\frac{1}{2}\pi R_{a}^{3}.\end{split}$ (27)

Then, the following inequalities hold: 1)$2\pi R_{b}^{3}<\pi R_{a}^{3}$, 2)
$\frac{2}{3}\pi R_{b}^{3}<\frac{1}{3}\pi R_{a}^{3}$, and 3) $\frac{2}{3}\pi
R_{b}^{3}+\frac{1}{3}\pi R_{b}^{3}<\frac{1}{3}\pi R_{a}^{3}+\frac{1}{3}\pi
R_{b}^{3}$. Finally, we have

$\begin{split}\pi R_{b}^{3}<\frac{1}{3}(\pi R_{a}^{3}+\pi
R_{b}^{3}).\end{split}$ (28)

Therefore, ${\rm Vol}({B})<\frac{1}{3}({\rm Vol}({A})+{\rm Vol}({B}))$. We
thus know: 1) $q_{a}\in{A}$ and it is with a minimum distance $d_{a}$ to the
boundary of $S_{a}$, 2) $q_{b}\in{B}$, and 3) $q^{*}\in{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 $S_{a}$ that covers class $A$, the nearly optimal error region can be
bounded as the spherical cap of $S_{a}$ with a volume constraint of ${\rm
Vol}({A})-{\rm Vol}(\mathcal{C})$. We thence have an inequality of

$\begin{split}\frac{{\rm Vol}({A})-{\rm Vol}(\mathcal{C})}{{\rm Vol}({A})+{\rm
Vol}({B})}<err(h,3)<\frac{1}{3}.\end{split}$ (29)

We next calculate the volume of the spherical cap:

$\begin{split}{\rm Vol}(A)-{\rm
Vol}(\mathcal{C})&=\int_{-R_{a}}^{R_{a}-d_{a}}\pi x^{2}d\ y\\\
&=\pi\int_{R_{a}-d_{a}}^{R_{a}}R_{a}^{2}-y^{2}d\ y\\\ &=\frac{4}{3}\pi
R_{a}^{3}-{\pi}d_{a}^{2}(R_{a}-\frac{d_{a}}{3}).\\\ \end{split}$ (30)

Eq. (29) then is rewritten as

$\begin{split}\frac{\frac{4}{3}\pi
R_{a}^{3}-\frac{\pi}{3}(3R_{a}-d_{a})d_{a}^{2}}{\frac{4}{3}\pi
R_{a}^{3}+\frac{4}{3}\pi R_{b}^{3}}<err(h,3)<0.3334,\end{split}$ (31)

Then, we have the error bound of

$\begin{split}\frac{4R_{a}^{3}-(3R_{a}-d_{a})d_{a}^{2}}{4R_{a}^{3}+4R_{b}^{3}}<err(h,3)<0.3334.\end{split}$
(32)

Introducing $d_{a}=R_{a}-t$, Eq. (32) is written as

$\begin{split}\frac{4R_{a}^{3}-(2R_{a}+t)(R_{a}-t)^{2}}{4R_{a}^{3}+4R_{b}^{3}}<err(h,3)<0.3334.\end{split}$
(33)

2) With another assumption of $R_{a}<R_{b}$, we follow the same proof skills
of $R_{a}\geq R_{b}$ and know
$\frac{4R_{b}^{3}-(3R_{b}-d_{b})d_{b}^{2}}{4R_{b}^{3}+4R_{a}^{3}}<err(h,3)<0.3334$,
i.e. where $d_{b}=R_{b}-t^{\prime}$ and
$t^{\prime}=\frac{R_{b}^{2}}{3}+\sqrt[3]{-\frac{\mu^{\prime}}{2\pi}+\sqrt{\frac{\mu^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu^{\prime}}{2\pi}-\sqrt{\frac{\mu^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}$, and
$\mu^{\prime}=(\frac{2}{9}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{b}^{3}-\frac{4\pi R_{a}^{3}}{9}$.

We thus conclude that ${\rm
min}\Bigg{\\{}\frac{4R_{a}^{3}-(2R_{a}+t)(R_{a}-t)^{2}}{4R_{a}^{3}+4R_{b}^{3}},\frac{4R_{b}^{3}-(2R_{b}+t^{\prime})(R_{b}-t^{\prime})^{2}}{4R_{b}^{3}+4R_{a}^{3}}\Bigg{\\}}<err(h,3)<0.3334$.
∎

### A.2 Specification of Assumption 1

In clustering stability, $\gamma$-tube structure that surrounds the cluster
boundary, largely decides the performance of a learning algorithm. Definition
of $\gamma$-tube is as follows.

######  Definition 1.

$\gamma$-tube ${\rm Tube}_{\gamma}(f)$ is a set of points distributed in the
boundary of the cluster.

$\begin{split}{\rm
Tube}_{\gamma}(f):=\\{x\in{X}|\ell(x,B(f))\leq\gamma\\},\end{split}$ (34)

where ${X}$ is a noise-free cluster with $n$ samples, $B(f):=\\{x\in{X},f\
\mbox{ is discontinuous at \ x }\\}$, $f$ is a clustering function, and
$\ell(\cdot,\cdot)$ denotes the distance function.

Following this conclusion, representation data can achieve the optimal
generalization error if they are spread over the tube structure. Let
$\gamma=d_{a}$, the probability of achieving a nearly zero generalization
error can be expressed as the volume ration of $\gamma$-tube and $S_{a}$:

$\begin{split}{\rm Pr}[err(h,k)=0]_{\rm Sphere}&=\frac{{\rm Vol}({\rm
Tube_{\gamma}})}{{\rm Vol}{(S_{a})}}\\\ &=\frac{\frac{4}{3}\pi
R_{a}^{3}-\frac{4}{3}(R_{a}-d_{a})^{3}}{\frac{4}{3}\pi R_{a}^{3}}\\\
&=1-\frac{t_{k}^{3}}{R_{a}^{3}},\\\ \end{split}$ (35)

where $t_{k}$ 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$. If the initial sampling comes
from the tube structure of $B$, the next acquisition must be updated from the
tube structure of $A$. With the updated acquisitions spread over the tube
structures of both classes, $h$ is easy to achieve a nearly zero error.

### A.3 Specification of Assumption 2

Following the specification of Assumption 1, volume of the tube is redefined
as ${\rm Vol(Tube_{\gamma})}=\frac{4}{3}\pi R_{a_{1}}R_{a_{2}}R_{a_{3}}$.
Then, we know

$\begin{split}{\rm Pr}[err(h,k)=0]_{\rm Ellipsoid}&=\frac{{\rm Vol}({\rm
Tube_{\gamma}})}{{\rm Vol}{(E_{a})}}\\\ &=\frac{\frac{4}{3}\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}-\frac{4}{3}(R_{a_{1}}-d_{a})(R_{a_{2}}-d_{a})(R_{a_{3}}-d_{a})}{\frac{4}{3}\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}}\\\
&=1-\frac{\lambda_{k_{1}}\lambda_{k_{2}}\lambda_{k_{3}}}{R_{a_{1}}R_{a_{2}}R_{a_{3}}},\\\
\end{split}$ (36)

where
$\lambda_{k_{i}}=\frac{R_{a_{i}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k_{i}}}{2\pi}+\sqrt{\frac{\sigma_{k_{i}}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{i}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k_{i}}}{2\pi}-\sqrt{\frac{\sigma_{k_{i}}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{i}}^{3}}{27\pi^{3}}}}$,
and $\sigma_{k_{i}}=(\frac{2k-4}{3k}-\frac{\pi R_{a_{i}}}{2\varphi})\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}-\frac{4\pi R_{b_{1}}R_{b_{2}}R_{b_{3}}}{3k}$,
$i=1,2,3$.

### A.4 Proof of Theorem 1

We next present the generalization errors against an agnostic sampling budget
$k$ following the above proof technique.

###### Proof.

The proof studies two cases: $R_{a}\geq R_{b}$ and $R_{a}<R_{b}$. 1) If
$R_{a}\geq R_{b}$, we estimate the optimal position of $q_{a}$ that satisfies
$q_{a}\in A$. Given the volume function ${\rm Vol}(\cdot)$ over the 3-D
geometry, we know: ${\rm Vol}({A})=\frac{4\pi}{3}R_{a}^{3}$ and ${\rm
Vol}({B})=\frac{4\pi}{3}R_{b}^{3}$. Assume $q_{a}$ be the nearest
representative data to the boundary of $S_{a}$, $q_{b}$ be the nearest
representative data to the boundary of $S_{b}$, and $q^{*}$ be the nearest
representative data to $h$ either in $S_{a}$ or $S_{b}$. Given the minimum
distance of $q_{a}$ to the boundary of $\mathcal{A}$ as $d_{a}$. Let $S_{a}$
be cut off by a cross section $h^{\prime}$, where $\mathcal{C}$ be the cut and
$\mathcal{D}$ be the spherical cap of the half-sphere that satisfy

${\rm Vol}(\mathcal{C})=\frac{2}{3}\pi R_{a}^{3}-{\rm
Vol}(\mathcal{D})=\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{3k},$ (37)

and the volume of $\mathcal{D}$ is

$\begin{split}{\rm
Vol}(\mathcal{D})&=\pi(\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}})^{2}(R_{a}-d_{a})+\int_{0}^{2\pi\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}}}\frac{{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}}{2\pi}\pi R_{a}^{2}\ dx\\\
&=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\frac{{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}}{2\pi}\pi
R_{a}^{2}(2\pi\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}})\\\
&=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\pi R_{a}^{2}{\rm
arcsin}\frac{R_{a}-d_{a}}{R_{a}}\sqrt{R_{a}^{2}-(R_{a}-d_{a})^{2}}.\\\
\end{split}$ (38)

Let $\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a}-d_{a}}{R_{a}}$, Eq. (36) can
be written as

$\begin{split}{\rm
Vol}(\mathcal{D})=\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})+\frac{\pi
R_{a}^{3}}{\varphi}cos\frac{\pi}{\varphi}.\\\ \end{split}$ (39)

Introducing Eq. (36) to Eq. (34), we have

$\begin{split}(\frac{2}{3}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\pi({R_{a}^{2}-(R_{a}-d_{a})^{2}})(R_{a}-d_{a})=\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{3k}.\end{split}$
(40)

Let $t_{k}=R_{a}-d_{a}$, we know

$\begin{split}\pi t^{3}-\pi
R_{a}^{2}t+(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{3k}=0.\end{split}$ (41)

To simplify Eq. (38), let
$\mu_{k}=(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{a}^{3}-\frac{4\pi R_{b}^{3}}{3k}$, Eq. (38) then can be written as

$\begin{split}\pi t^{3}-\pi R_{a}^{2}t+\mu_{k}=0.\end{split}$ (42)

The positive solution of $t_{k}$ can be

$\begin{split}&t_{k}=\frac{R_{a}^{2}}{3}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}+\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu_{k}}{2\pi}-\sqrt{\frac{\mu_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a}^{3}}{27\pi^{3}}}}.\end{split}$
(43)

Based on Eq. (35), we know

$\begin{split}{\rm Vol}(\mathcal{D})&=\frac{2}{3}\pi
R_{a}^{3}-\frac{4\pi(R_{a}^{3}+R_{b}^{3})}{3k}\\\ &=\frac{2k-4}{3k}\pi
R_{a}^{3}-\frac{4}{3k}\pi R_{b}^{3}>0.\\\ \end{split}$ (44)

Thus, $\sqrt[3]{\frac{2}{k-2}}R_{b}<R_{a}$. We next prove $q^{*}\in{A}$.
According to Eq. (41), we know

$\begin{split}\pi R_{b}^{3}<{\frac{k-2}{2}}\pi R_{a}^{3}.\end{split}$ (45)

Then, the following inequalities hold: 1)$\frac{2}{k-2}\pi R_{b}^{3}<\pi
R_{a}^{3}$, 2) $\frac{2}{(k-2)k}\pi R_{b}^{3}<\frac{1}{k}\pi R_{a}^{3}$, and
3) $\frac{2}{(k-2)k}\pi R_{b}^{3}+\frac{k^{2}-2k-2}{(k-2)k}\pi
R_{b}^{3}<\frac{1}{k}\pi R_{a}^{3}+\frac{k^{2}-2k-2}{(k-2)k}\pi R_{b}^{3}$.
Finally, we have:

$\begin{split}&\pi R_{b}^{3}\\\ &<\frac{1}{k}\pi
R_{a}^{3}+\frac{k^{2}-2k-2}{(k-2)k}\pi R_{b}^{3}\\\
&=\frac{1}{k}\pi(R_{a}^{3}+R_{b}^{2})-\frac{2}{(k-2)k}\pi R_{a}^{3}\\\
&<\frac{1}{k}\pi(R_{a}^{3}+R_{b}^{3}).\\\ \end{split}$ (46)

Therefore, ${\rm Vol}({B})<\frac{1}{k}({\rm Vol}({A})+{\rm Vol}({B}))$. We
thus know: 1) $q_{a}\in{A}$ and it is with a minimum distance $d_{a}$ to the
boundary of $S_{a}$, 2) $q_{b}\in{B}$, and 3) $q^{*}\in{A}$. Therefore, class
${B}$ can be deemed as having a very high probability to achieve a zero
generalization error and the position of $q^{*}$ largely decides the upper
bound of the generalization error of $h$.

In $S_{a}$ that covers class $A$, the nearly optimal error region can be
bounded as ${\rm Vol}({A})-{\rm Vol}({C})$. We then have the inequality of

$\begin{split}\frac{{\rm Vol}({A})-{\rm Vol}(\mathcal{C})}{{\rm Vol}({A})+{\rm
Vol}({B})}<err(h,k)<\frac{1}{k}.\end{split}$ (47)

Based on the volume equation of the spherical cap in Eq. (30), we have

$\begin{split}\frac{\frac{4}{3}\pi
R_{a}^{3}-\frac{\pi}{3}(3R_{a}-d_{a})d_{a}^{2}}{\frac{4}{3}\pi
R_{a}^{3}+\frac{4}{3}\pi R_{b}^{3}}<err(h,k)<\frac{1}{k}.\end{split}$ (48)

Then, we have the error bound of

$\begin{split}\frac{4R_{a}^{3}-(3R_{a}-d_{a})d_{a}^{2}}{4R_{a}^{3}+4R_{b}^{3}}<err(h,k)<\frac{1}{k}.\end{split}$
(49)

Introducing $d_{a}=R_{a}-t_{k}$, Eq. (46) is written as

$\begin{split}\frac{4R_{a}^{3}-(2R_{a}+t)(R_{a}-t_{k})^{2}}{4R_{a}^{3}+4R_{b}^{3}}<err(h,k)<\frac{1}{k}.\end{split}$
(50)

2) With another assumption of $R_{a}<R_{b}$, we follow the same proof skills
of $R_{a}\geq R_{b}$ and know
$\frac{4R_{b}^{3}-(3R_{b}-d_{b})d_{b}^{2}}{4R_{b}^{3}+4R_{a}^{3}}<err(h,k)<\frac{1}{k}$,
where $d_{b}=R_{b}-t_{k}^{\prime}$ and
$t_{k}^{\prime}=\frac{R_{b}^{2}}{3}+\sqrt[3]{-\frac{\mu_{k}^{\prime}}{2\pi}+\sqrt{\frac{\mu_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\mu_{k}^{\prime}}{2\pi}-\sqrt{\frac{\mu_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b}^{3}}{27\pi^{3}}}}$, and
$\mu_{k}^{\prime}=(\frac{2k-4}{3k}-\frac{1}{\varphi}cos\frac{\pi}{\varphi})\pi
R_{b}^{3}-\frac{4\pi R_{a}^{3}}{3k}$.

We thus conclude that ${\rm
min}\Bigg{\\{}\frac{4R_{a}^{3}-(2R_{a}+t_{k})(R_{a}-t_{k})^{2}}{4R_{a}^{3}+4R_{b}^{3}},\frac{4R_{b}^{3}(2R_{b}+t_{k}^{\prime})(R_{b}-t_{k}^{\prime})^{2}}{4R_{b}^{3}+4R_{a}^{3}}\Bigg{\\}}<err(h,k)<\frac{1}{k}$.
∎

### A.5 Proof of Theorem 2

###### Proof.

Given class $A$ and $B$ are tightly covered by ellipsoid $E_{a}$ and $E_{b}$
in a three-dimensional geometry. Let $R_{a_{1}}$ be the polar radius of
$E_{a}$, $\\{R_{a_{2}},R_{a_{3}}\\}$ be the equatorial radii of $E_{a}$,
$R_{b_{1}}$ be polar radius of $E_{b}$, and $\\{R_{b_{2}},R_{b_{3}}\\}$ be the
equatorial radii of $E_{b}$. Based on Eq. (10), we know
$R_{a_{i}}<R_{a},R_{b_{i}}<R_{b},\forall i$, where $R_{a}$ and $R_{b}$ are the
radii of the spheres over the class $A$ and $B$, respectively. We follow the
same proof technique of Theorem 1 to present the generalization errors of AL
with ellipsoid.

The proof studies two cases: $R_{a_{1}}\geq R_{b}$ and $R_{a_{1}}<R_{b_{1}}$.
1) If $R_{a_{1}}\geq R_{b_{1}}$, $q^{*}\in{A}$. Given the volume function
${\rm Vol}(\cdot)$ over the 3-D geometry, we know: ${\rm
Vol}({A})=\frac{4\pi}{3}R_{a_{1}}R_{a_{2}}R_{a_{3}}$ and ${\rm
Vol}({B})=\frac{4\pi}{3}R_{b_{1}}R_{b_{2}}R_{b_{3}}$. Given the minimum
distance of $q_{a}$ to the boundary of ${A}$ as $d_{a}$. Let $E_{a}$ by cut
off by a cross section $h^{\prime}$, where $\mathcal{C}$ be the cut and
$\mathcal{D}$ be the ellipsoid cap of the half-ellipsoid that satisfy

${\rm Vol}(\mathcal{C})=\frac{2}{3}\pi R_{a}^{1}R_{a}^{2}R_{a}^{3}-{\rm
Vol}(\mathcal{D})=\frac{4\pi(R_{a_{1}}R_{a_{2}}R_{a_{3}}+R_{b_{1}}R_{b_{2}}R_{b_{3}})}{3k},$
(51)

and the volume of $\mathcal{D}$ is approximated as

$\begin{split}{\rm
Vol}(\mathcal{D})&\approx\pi(\sqrt{R_{a_{1}}^{2}-(R_{a_{1}}-d_{a})^{2}})^{2}(R_{a_{1}}-d_{a})+\int_{0}^{\pi
R_{a_{2}}R_{a_{3}}}\frac{arcsin\frac{R_{a_{1}}-d_{a}}{R_{a_{1}}}}{2\pi}\pi
R_{a_{1}}^{2}\ dx\\\
&=\pi({R_{a_{1}}^{2}-(R_{a_{1}}-d_{a})^{2}})(R_{a_{1}}-d_{a})+\frac{arcsin\frac{R_{a_{1}}-d_{a}}{R_{a}}}{2\pi}\pi
R_{a_{1}}^{2}(\pi R_{a_{2}}R_{a_{3}})\\\
&=\pi({R_{a_{1}}^{2}-(R_{a_{1}}-d_{a})^{2}})(R_{a_{1}}-d_{a})+\frac{1}{2}\pi
R_{a_{1}}^{2}R_{a_{2}}R_{a_{3}}arcsin\frac{R_{a_{1}}-d_{a}}{R_{a_{1}}}.\\\
\end{split}$ (52)

Let $\frac{\pi}{\varphi}={\rm arcsin}\frac{R_{a_{1}}-d_{a}}{R_{a_{1}}}$, Eq.
(49) can be written as

$\begin{split}{\rm
Vol}(\mathcal{D})=\pi({R_{a_{1}}^{2}-(R_{a_{1}}-d_{a})^{2}})(R_{a_{1}}-d_{a})+\frac{\pi^{2}}{2\varphi}R_{a_{1}}^{2}R_{a_{2}}R_{a_{3}}.\\\
\end{split}$ (53)

Introducing Eq. (50) to Eq. (48), we have

$\begin{split}(\frac{2}{3}-\frac{\pi R_{a_{1}}}{2\varphi})\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}-\pi({R_{a_{1}}^{2}-(R_{a_{1}}-d_{a})^{2}})(R_{a_{1}}-d_{a})=\frac{4\pi(R_{a_{1}}R_{a_{2}}R_{a_{3}}+R_{b_{1}}R_{b_{2}}R_{b_{3}})}{3k}.\end{split}$
(54)

Let $\lambda_{k}=R_{a_{1}}-d_{a}$, we know

$\begin{split}\pi\lambda_{k}^{3}-\pi
R_{a}^{2}\lambda_{k}+(\frac{2k-4}{3k}-\frac{\pi R_{a_{1}}}{2\varphi})\pi
R_{a_{1}}R_{a_{2}}R_{a_{3}}-\frac{4\pi
R_{b_{1}}R_{b_{2}}R_{b_{3}}}{3k}=0.\end{split}$ (55)

To simplify Eq. (52), let $\sigma_{k}=(\frac{2k-4}{3k}-\frac{\pi
R_{a_{1}}}{2\varphi})\pi R_{a_{1}}R_{a_{2}}R_{a_{3}}-\frac{4\pi
R_{b_{1}}R_{b_{2}}R_{b_{3}}}{3k}$, Eq. (52) then can be written as

$\begin{split}\pi\lambda_{k}^{3}-\pi
R_{a_{1}}^{2}\lambda_{k}+\sigma_{k}=0.\end{split}$ (56)

The positive solution of $\lambda_{k}$ can be

$\begin{split}&\lambda_{k}=\frac{R_{a_{1}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}+\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{1}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}-\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{1}}^{3}}{27\pi^{3}}}}.\end{split}$
(57)

The remaining proof process follows Eq. (40) to Eq. (46) of Theorem 1. We thus
conclude that

$\begin{split}{\rm
min}\Bigg{\\{}\frac{4\prod_{i}R_{a_{i}}-(2R_{a_{1}}+\lambda_{k})(R_{a_{1}}-\lambda_{k})^{2}}{4\prod_{i}R_{a_{i}}+4\prod_{i}R_{b_{i}}},\frac{4\prod_{i}R_{b_{i}}-(2R_{b_{1}}+\lambda_{k}^{\prime})(R_{b_{1}}-\lambda_{k}^{\prime})^{2}}{4\prod_{i}R_{b_{i}}+4\prod_{i}R_{a_{i}}}\Bigg{\\}}<err(h,k)<\frac{1}{k},\end{split}$
(58)

where $i=1,2,3$,
$\lambda_{k}^{\prime}=\frac{R_{b_{1}}^{2}}{3}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}+\sqrt{\frac{\sigma_{k}^{\prime
2}}{4\pi^{2}}-\frac{\pi^{3}R_{b_{1}}^{3}}{27\pi^{3}}}}+\sqrt[3]{-\frac{\sigma_{k}}{2\pi}-\sqrt{\frac{\sigma_{k}^{2}}{4\pi^{2}}-\frac{\pi^{3}R_{a_{1}}^{3}}{27\pi^{3}}}}$,
and $\sigma_{k}^{\prime}=(\frac{2k-4}{3k}-\frac{\pi R_{b_{1}}}{2\varphi})\pi
R_{b_{1}}R_{b_{2}}R_{b_{3}}-\frac{4\pi R_{a_{1}}R_{a_{2}}R_{a_{3}}}{3k}$. In a
simple way, $R_{a_{1}}R_{a_{2}}R_{a_{3}}$ and $R_{b_{1}}R_{b_{2}}R_{b_{3}}$
can be written as $\prod_{i}R_{a_{i}}$ and $\prod_{i}R_{b_{i}}$, i=$1,2,3$,
respectively.

∎

### A.6 Proof of Proposition 1

###### Proof.

Let ${\rm Cube_{a}}$ tightly covers $S_{a}$ with a side length of $2R_{a}$,
and ${\rm Cube}_{a}^{\prime}$ tightly covers the cut $\mathcal{C}$, following
theorem 1, we know

$\begin{split}err(h,k)>\frac{{\rm Vol}({A})-{\rm Vol}(\mathcal{C})}{{\rm
Vol}({A})}>\frac{{\rm Cube_{a}-Cube_{a}^{\prime}}}{{\rm
Cube_{a}}}.\end{split}$ (59)

Then, we know

$\begin{split}err(h,k)&>\frac{\pi R_{a}^{3}-\pi R_{a}^{2}d_{a}}{\pi
R_{a}^{3}}\\\ &=1-\frac{d_{a}}{R_{a}}.\\\ \end{split}$ (60)

Meanwhile, let ${\rm Cube_{e}}$ tightly covers $E_{a}$ with a side length of
$2R_{a_{1}}$, ${\rm Cube_{e}}^{\prime}$ tightly covers $\mathcal{C}$,
following theorem 1, we know

$\begin{split}err(h,k)>\frac{{\rm Vol}({A})-{\rm Vol}(\mathcal{C})}{{\rm
Vol}({A})}>\frac{{\rm Cube_{e}-Cube_{e}^{\prime}}}{{\rm
Cube_{e}}}.\end{split}$ (61)

Then, we know

$\begin{split}err(h,k)&>\frac{\pi R_{a_{1}}R_{a_{2}}R_{a_{3}}-\pi
d_{a}R_{a_{2}}R_{a_{3}}}{\pi R_{a_{1}}R_{a_{2}}R_{a_{3}}}\\\
&=1-\frac{d_{a}}{R_{a_{1}}}.\\\ \end{split}$ (62)

Since ${R_{a_{1}}}<R_{a}$, we know
$1-\frac{d_{a}}{R_{a}}>1-\frac{d_{a}}{R_{a_{1}}}$. It is thus the lower bound
of AL with ellipsoid is tighter than AL with sphere. Then, Proposition 1
holds. ∎

### A.7 Proof of Proposition 2

###### Proof.

Following the proofs of Theorem 3:

$\begin{split}{\rm Pr}[err(h,k)=0]_{{\rm
Sphere}}&=1-\frac{t_{k}^{3}}{R_{a}^{3}}\\\
&=1-\frac{(R_{a}-d_{a})^{3}}{R_{a}^{3}}\\\
&=1-\Bigg{(}1-\frac{d_{a}}{R_{a}}\Bigg{)}^{3}.\\\ \end{split}$ (63)

Following the proofs Theorem 4:

$\begin{split}{\rm Pr}[err(h,k)=0]_{\rm
Ellipsoid}&=1-\frac{\lambda_{k_{1}}\lambda_{k_{2}}\lambda_{k_{3}}}{R_{a_{1}}^{3}}\\\
&=1-\frac{(R_{a_{1}}-d_{a})(R_{a_{2}}-d_{a})(R_{a_{3}}-d_{a})}{R_{a_{1}}^{3}}\\\
&>1-\Bigg{(}1-\frac{d_{a}}{R_{a_{1}}}\Bigg{)}^{3}.\\\ \end{split}$ (64)

Based on Proposition 1, $1-\frac{d_{a}}{R_{a}}>1-\frac{d_{a}}{R_{a_{1}}}$,
therefore ${\rm Pr}[err(h,k)=0]_{{\rm Sphere}}<{\rm Pr}[err(h,k)=0]_{\rm
Ellipsoid}$. Then, Proposition 2 is as stated. ∎

### A.8 Proof of Theorems 3 and 4

Proof of Theorems 3.

###### Proof.

Given $S_{a}$ over class $A$ is defined with ${\bf
x_{1}^{2}+x_{2}^{2}+x_{3}^{2}}=R_{a}^{2}$. Let ${\bf
x_{1}^{2}+x_{2}^{2}}=r_{a}^{2}$ be its 2-D generalization of $S_{a}$, assume
that $x_{2}$ be a variable parameter in this 2-D generalization formula, the
“volume” (2-D volume is the area of the geometry object) of it can be
expressed as

$\begin{split}{\rm
Vol}_{\bm{2}}(S_{a})=\int_{-r_{a}}^{r_{a}}2\sqrt{r_{a}^{2}-{\bf
x_{2}^{2}}}d{\bf x_{2}}.\end{split}$ (65)

Let $\vartheta$ be an angle variable that satisfies
$x_{2}=r_{a}sin(\vartheta)$, we know $d{\bf
x_{2}}=r_{a}cos(\vartheta)d\vartheta$. Then, Eq. (65) is rewritten as

$\begin{split}{\rm
Vol}_{\bm{2}}(S_{a})&=\int_{-\pi/2}^{\pi/2}2r_{a}^{2}cos^{2}(\vartheta)d\vartheta\\\
&=\int_{0}^{\pi/2}4r_{a}^{2}cos^{2}(\vartheta)d\vartheta.\\\ \end{split}$ (66)

For a $3$-D geometry, for the variable ${\bf x_{3}}$, it is over a cross-
section which is a ${\bm{2}}$-dimensional ball (circle), where the radius of
the ball can be expressed as $r_{a}cos(\vartheta)$, s.t.
$\vartheta\in[0,\pi]$. Particularly, let ${\rm Vol}_{\bm{3}}(S_{a})$ be the
volume of $S_{a}$ with $3$ dimensions, the volume of this 3-dimensional sphere
then can be written as

$\begin{split}{\rm Vol}_{\bm{3}}(S_{a})&=\int_{0}^{\pi/2}2{\rm
Vol}_{\bm{2}}(r_{a}cos(\vartheta))r_{a}(cos(\vartheta))d\vartheta.\\\
\end{split}$ (67)

With Eq. (67), volume of a ${\bm{d}}$-dimensional geometry can be expressed as
the integral over the $({\bf d}\text{-}1)$-dimensional cross-section of
$S_{a}$

$\begin{split}{\rm Vol}_{\bm{m}}(S_{a})&=\int_{0}^{\pi/2}2{\rm
Vol}_{\bm{m}\text{-}1}(r_{a}cos(\vartheta))r_{a}(cos(\vartheta))d\vartheta,\\\
\end{split}$ (68)

where ${\rm Vol}_{\bm{m\text{-}1}}$ denotes the volume of
${\bm{(m\text{-}1)}}$-dimensional generalization geometry of $S_{a}$.

Based on Eq. (68), we know ${\rm Vol}_{\bm{3}}$ can be written as

$\begin{split}{\rm Vol}_{\bm{3}}(S_{a})&=\int_{0}^{\pi/2}2{\rm
Vol}_{\bm{2}}(R_{a}cos(\vartheta))r_{a}(cos(\vartheta^{\prime}))d\vartheta\end{split}$
(69)

Introducing Eq. (66) into Eq. (69), we have

$\begin{split}{\rm Vol}_{\bm{3}}(S_{a})&=\int_{0}^{\pi/2}2{\rm
Vol}_{\bm{2}}(R_{a}cos(\vartheta^{\prime}))r_{a}(cos(\vartheta^{\prime}))d\vartheta^{\prime}\\\
&=\int_{0}^{\pi/2}\int_{0}^{\pi/2}8(r_{a}cos(\vartheta^{\prime})^{2}cos^{2}(\vartheta^{\prime})r_{a}(cos(\vartheta))d\vartheta^{\prime}d\vartheta\\\
&=\frac{4}{3}\pi R_{a}^{2}\ \ \ \ \rm{s.t.}R_{a}=r_{a}.\\\ \end{split}$ (70)

Therefore, the generalization analysis results of the 3-D geometry still can
hold in the high dimensional geometry. Then, ∎

Proof of Theorems 4.

###### Proof.

The integral of Eq. (67) also can be adopted into the volume of ${\rm
Vol}_{\bm{3}}(E_{a})$ by transforming the area i.e. ${\rm
Vol}_{\bm{2}}(S_{a})$ into ${\rm Vol}_{\bm{2}}(E_{a})$. Then, Eq. (68) follows
this transform. ∎

|  Xiaofeng Cao completed his PhD study at Australian Artificial Intelligence
Institute (AAII), University of Technology Sydney. He is working as a Research
Assistant at AAII. His research interests include PAC learning theory,
agnostic learning algorithm, generalization analysis, and hyperbolic geometry.
---|---
|  Ivor W. Tsang is Professor of Artificial Intelligence, at University of
Technology Sydney. He is also the Research Director of the Australian
Artificial Intelligence Institute. In 2019, his paper titled “Towards
ultrahigh dimensional feature selection for big data" received the
International Consortium of Chinese Mathematicians Best Paper Award. In 2020,
Prof Tsang was recognized as the AI 2000 AAAI/IJCAI Most Influential Scholar
in Australia for his outstanding contributions to the field of Artificial
Intelligence between 2009 and 2019. His works on transfer learning granted him
the Best Student Paper Award at International Conference on Computer Vision
and Pattern Recognition 2010 and the 2014 IEEE Transactions on Multimedia
Prize Paper Award. In addition, he had received the prestigious IEEE
Transactions on Neural Networks Outstanding 2004 Paper Award in 2007. Prof.
Tsang serves as a Senior Area Chair for Neural Information Processing Systems
and Area Chair for International Conference on Machine Learning, and the
Editorial Board for Journal Machine Learning Research, Machine Learning,
Journal of Artificial Intelligence Research, and IEEE Transactions on Pattern
Analysis and Machine Intelligence.
---|---