# Active Learning: Problem Settings and Recent Developments

Hideitsu Hino  The Institute of Statistical Mathematics
10-3 Midori-cho, Tachikawa, Tokyo 190-8562, Japan
<EMAIL_ADDRESS>
###### Abstract

In supervised learning, acquiring labeled training data for a predictive model
can be very costly, but acquiring a large amount of unlabeled data is often
quite easy. Active learning is a method of obtaining predictive models with
high precision at a limited cost through the adaptive selection of samples for
labeling. This paper explains the basic problem settings of active learning
and recent research trends. In particular, research on learning acquisition
functions to select samples from the data for labeling, theoretical work on
active learning algorithms, and stopping criteria for sequential data
acquisition are highlighted. Application examples for material development and
measurement are introduced.

##  1 Introduction

Supervised learning is a typical problem setting for machine learning that
approximates the relationship between the input and output based on a given
sets of input and output data. The accuracy of the approximation can be
increased using more input and output data to build the model; however,
obtaining the appropriate output for the input can be costly. A classic
example is the crossbreeding of plants. The environmental conditions (e.g.,
average monthly temperature, type and amount of fertilizer used, watering
conditions, weather) are the input, and the specific properties of the crops
are the output. In this case, the controllable variables are related to the
fertilizer and watering conditions, but it would take several months to years
to perform experiments under various conditions and determine the optimal
fertilizer composition and watering conditions. Methodologies to determine
experimental protocols have been developed for obtaining the necessary
information at a minimum cost, such as the experimental design method (Fisher,
1935; Hotelling, 1944; Lindley, 1956) and the sequential experimental design
method (Johnson, 1961; Ford and Silvey, 1980). In the context of supervised
machine learning, sequential experimental design is generally called active
learning. Various methodologies have been proposed for the problem of
sequentially selecting samples to improve the predictive performance based on
a small amount of learning data available. In contrast to active learning,
passive learning refers to when all data are given at once.

Figure 1: Example of binary search for a split threshold of $x\in[0,1]$ that
is completely separable. A two-class classifier
$y=h_{\theta}(x)=\mathbbm{1}(x\geq\theta)$ is efficiently learned.

For active learning, proper selection of samples for training the predictor
can reduce the probability of mistakenly predicting the response variable for
an unknown explanatory variable (i.e., generalization error). Intuitively, the
usefulness of active learning can be demonstrated by the following simple
situation (Cohn et al., 1994). If the variable $x$ is distributed in the
interval $[0,1]$, it is completely separable when
$y=h_{\theta^{\ast}}(x)=\mathbbm{1}(x\geq\theta^{\ast})$ with a certain
threshold $\theta^{\ast}\in(0,1)$. According to standard Vapnik–Chervonenkis
(VC) theory, a sample of $m=O(1/\varepsilon)$ needs to be obtained from
$\Pr(x,y)$ to yield a discriminator with an error of $\varepsilon$ or less. In
active learning, the predictor is trained with increasing the number of number
of samples by sequentially selecting $x\in[0,1]$ and querying $y\in\\{0,1\\}$
for it; then, a hypothesis with a prediction error of $\varepsilon$ or less
can be efficiently obtained through a binary search. As shown in Figure 1, $y$
is queried to obtain label $y=0$ for the midpoint $x^{(1)}$ (i.e., half the
interval $[0,1]$). Then, label $y=0$ is obtained for the midpoint $x^{(2)}$
between $x^{(1)}$ and $1$. Subsequently, label $y=1$ is obtained for the
midpoint $x^{(3)}$ between $x^{(2)}$ and $1$. Finally, label $y=1$ is obtained
for the midpoint $x^{(4)}$ between $x^{(2)}$ and $x^{(3)}$. The interval of
$x^{(2)}$ and $x^{(4)}$ is $\varepsilon$ or less. Thus, by making the midpoint
the estimated value of $\theta^{\ast}$, the threshold
$\theta^{\ast}\pm\varepsilon$ can be searched. This binary search has a
complexity of $O(\log(1/\varepsilon))$ and is an example where active learning
can be realized with exponentially fewer samples than passive learning but
with the same accuracy111Generalized binary search (Nowak, 2008, 2009), which
considers a situation with no observation noise (i.e., no uncertainty in the
predicted label), uses the concept of adaptive submodularity, which has been
shown to be nearly optimal (Golovin and Krause, 2011)..

Figure 2: Example of using active learning to predict MNIST data with random
forest as the predictor. The horizontal axis represents the number of samples
added to the initial 500 samples, and the vertical axis represents the
prediction accuracy. The accuracy is observed to be improved with active
learning compared with the accuracy of random sampling.

This is a very simple one-dimensional two-class classification problem and is
an ideal situation without noise. Although exponential acceleration is not
possible in all cases, theoretical and experimental demonstrations have shown
that active learning can achieve a high prediction accuracy with few samples.
Figure 2 compares some active learning methods with random sampling for the
prediction of MNIST data (Lecun et al., 1998) with random forest (Breiman,
2001). Specifically, the problem was to predict a $28\times 28$ pixel
handwritten number from $0\sim 9$. The prediction model was trained with 500
sets of labeled data in advance. Fifty points of data were sequentially
selected from the pooled data of $60,000-500=59,500$ points and added to the
training data for the prediction model to learn, and the prediction accuracy
was evaluated with a test dataset consisting of 10,000 points. Uncertainty
(Lewis and Catlett, 1994), entropy, and margin (Settles, 2010) represent the
acquisition functions that were used to determine which sample was labeled
next for active learning. Each learning curve shows the average results when
the training dataset used for the initial prediction model was randomly
changed 100 times. The graph shows that active learning improved the accuracy
while using a smaller amount of data than random sampling.

This paper introduces the basic problem setting and concept of active
learning, including recent research trends and application examples. Section 2
introduces terms and notations and explains the basic problem setting. Section
3 introduces typical criteria for selecting data that require labeling.
Although various algorithms and acquisition functions have been proposed, it
is not evident for which situations active learning is better than passive
learning. In addition, some methods require solving an optimization problem
that is difficult to execute in practice, even if the learning is efficient in
principle. In such a case, an approximation method and guaranteeing the
accuracy of the approximation are important. Accordingly, section 4 introduces
results for theoretical guarantees of active learning. Section 5 presents
research on the stopping criteria for active learning. Section 6 provides an
example of applying active learning to measurement and material development.
Finally, section 7 concludes the paper with future tasks and prospects.

We note that Settles (2010) presented a well-known survey of active learning.
Hanneke (2014) presented a survey focusing on the theoretical aspects when no
assumption is made on the noise distribution, which is called agnostic active
learning. Ramirez-Loaiza et al. (2017) presented an experimental comparison of
various methods, and Lowell et al. (2019) summarized the problems with
practical application of active learning to natural language processing.

Active learning may be used in a broad sense to include Bayesian optimization.
In this study, Bayesian optimization is considered as the search for optimal
experimental settings (parameters or variables) from a small number of trials,
while active learning is distinguished as improving the predictive model using
a small amount of learning data.

##  2 Problem Setting

Let $X\in\mathcal{X}$ be an explanatory variable and $Y\in\mathcal{Y}$ be a
response variable. $\mathcal{Y}$ is a subset of $\mathbb{R}$ for regression
problems and is $\\{+1,-1\\}$ for discrimination problems. The realizations of
the random variables $X,Y$ are denoted as $x$ and $y$, respectively. The
function $h:\mathcal{X}\to\mathcal{Y}$, which predicts the response variable
from the explanatory variable, is called a hypothesis or predictor. The set of
hypothesis spaces is represented by $\mathcal{H}$. The mechanism for
generating data, i.e., the true function $y=f(x)$, is called realizable when
it is included in the assumed hypothesis space and non-realizable when it is
not. Consider the random variables $(X,Y)$ with the joint distribution
$D_{XY}$, and let the marginal distribution for $X$ of $D_{XY}$ be $D_{X}$.
The data used for learning the hypothesis are
$S_{n}=\\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})\\}\in(\mathcal{X}\times\mathcal{Y})^{n}$.
The loss function for evaluating the prediction error based on the hypothesis
is represented by
$\ell:\mathcal{H}\times\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{+}$. In the
case of a regression problem, the squared loss $\ell(h,x,y)=(y-h(x))^{2}$ is
often used. In the case of a discrimination problem, the discriminant error or
$0-1$ loss $\ell(h,x,y)=\mathbbm{1}(h(x)\neq y)$ is often used. For active
learning, discrepancies in discriminant results are easier to evaluate
compared to discrepancies in regression results. In addition, theoretical
analysis is easier with a version space that is described later, but the
version space for regression problems does not have a clear definition. Thus,
most studies on active learning have focused on discrimination problems.
However, several active learning methods have been proposed for regression
problems (Sung et al., 1994; Krogh and Vedelsby, 1995; Cohn et al., 1996; Hall
and Molchanov, 2003; Burbidge et al., 2007; Castro et al., 2005). In this
paper, whether a situation is a discrimination or regression problem depends
on the context and explicitly stated when necessary.

For active learning, it is convenient to assume a subject (i.e., learner) who
performs the learning for the predictor. The learner selects a sample $x$ for
which the value of the corresponding explanatory variable $y$ is unknown by
some criteria, thereby obtaining the value of $y$. The value of the
explanatory variable is called a label for both discriminant and regression
problems. The function that returns the value of the explanatory variable for
$x$ is often called the oracle, but this implies that the label is always
correct. In this paper, the term observation is used rather than oracle
because, in practice, occasionally, only values that include labeling errors
are obtained.

For distribution $D_{XY}$ on $\mathcal{X}\times\mathcal{Y}$, the
generalization error and empirical error are defined as

$\mathcal{L}_{D_{XY}}(h)=\mathbb{E}_{D_{XY}}[\ell(h,X,Y)],\quad\mathcal{L}_{S_{n}}(h)=\frac{1}{n}\sum_{i=1}^{n}\ell(h,x_{i},y_{i}).$

Certain active learning methods for discrimination problems use the concept of
version space:

$\mathcal{V}(S_{n})=\\{h\in\mathcal{H}|h(x)=y,\;\forall(x,y)\in S_{n}\\},$ (1)

which is a subset of the hypothesis set that is consistent with the training
data obtained until that point.

In general, the prior distribution $p(h)$ is set for each hypothesis
$h\in\mathcal{H}$, and the hypothesis is stochastically selected. In Bayesian
active learning, the posterior probability $p(h|S_{n})$ of the hypothesis is
learned with data $S_{n}$ to consider the inference given by the hypothesis
sampled according to the posterior probability or the expected value given by
the posterior probability of the predicted value (Mackay, 1992). A setting
with the distribution included with respect to $h\in\mathcal{H}$ is
advantageous because the volume of the version space can be measured
naturally.

The number of samples required for learning a hypothesis to obtain the desired
prediction accuracy is called sample complexity in standard statistical
learning theory. In the context of active learning, however, the required
number of labels is the main concern and is sometimes called label complexity.
In addition, there is some debate on how much unlabeled data is sufficient. In
probably approximately correct (PAC) learning, terms such as $\log
d,\log(1/\delta),\log\log(1/\varepsilon)$ often appear in relation to
parameters such as the VC dimension $d$, prediction error $\varepsilon$, and
confidence $\delta$. However, in this paper, such terms are omitted in favor
of order notation, such as $O(n)$ and $O(\log n)$. In statistics, most
sequential designs assume a setting where observation points can be freely
selected according to some standard; this is called membership query synthesis
in the context of active learning (Angluin, 1988). This is acceptable when the
corresponding explanatory variable value can be reliably obtained. However,
for example, this is difficult to apply to problems involving optical
character recognition (e.g., appropriate labeling of characters freely
composed by the learner)222In character recognition research, the approach of
synthesizing and learning character images on a computer is widely taken, and
in this case, the label of the synthesized image is known. On the other hand,
in active learning, an unlabeled synthetic image that is judged to belong to
the boundary region of the character type, which is difficult to label, is
generated, and labeling is required for that image.. Thus, two types of active
learning are usually considered for machine learning, as detailed in the
subsequent subsections.

###  2.1 Stream-based active learning

In stream-based active learning, data are sequentially presented from the data
generating distribution $D_{X}$ to the learner, who decides whether to request
label $y$ for the presented data $x$ based on some criterion. If a label is
not requested, then the data are discarded. Labeled data are used to train the
predictor. There may be an option where the labeled data are not used to train
the predictor. Atlas et al. (1990) presented a typical discussion of stream-
based active learning in the field of machine learning. For a discrimination
problem, if there is a region in the version space where the predicted label
differs from the presented sample, it is possible to query samples that are
difficult to predict with the current hypothesis by labeling the sample with a
high degree of uncertainty. An exact calculation of the version space and its
sub-regions is difficult, hence approximation methods have been proposed. For
example, Atlas et al. (1990) proposed a method of constructing a filter that
uses a neural network to extract samples that do not match the predictions
included in the version space.

###  2.2 Pool-based active learning

In pool-based active learning, a small number of pre-labeled datasets and rich
unlabeled datasets (i.e., pooled data) are provided, and a predictor trained
with a small dataset is used to select samples from the pooled data for
labeling. The data selected for labeling are added to the pre-labeled data
available, and the predictor is trained again. This setting represents a
typical problem where data collection is easy but the annotation cost is high.
Although numerous active learning methods assume that only one query is issued
at a time, retraining the model every time a sample is added is inefficient.
The time required for one learning session may not be neglected, or the
addition of a single sample may not make a meaningful change in the model,
especially for deep learning models. Cohn et al. (1994) suggested batch active
learning because of the high complexity of version space management. In
situations where multiple experiments are parallelly conducted, batch active
learning is effective because multiple samples from the pooled data can be
selected and labeled simultaneously. If a batch of size $k$ can be labeled at
once, a simple strategy may be to select the top $k$ samples by repeatedly
selecting a single sample $k$ times; however, a concern is that only $k$
similar samples may be selected. For batch active learning, it is crucial for
the selection criteria to consider sample diversity as well as the amount of
information that each sample contains with respect to the model. Various
methods have been proposed, such as a method based on the notion of
submodularity (Hoi et al., 2006) as described below, and formulating the batch
selection problem as a non-convex integer program for empirical risk
minimization (Wang and Ye, 2015). Problem settings can be conveniently
classified as stream-based, pool-based, or arbitrary design; often, a method
that assumes a certain setting can still be applied to another setting with
slight modifications.

##  3 Acquisition Function

Perhaps the most important component of active learning is the acquisition
function, which determines whether a sample requires labeling. Several
acquisition functions aim to quantify the difficulty of label prediction in
some way and actively incorporate difficult-to-predict samples into learning.
Numerous early studies on active learning designed the acquisition function
through heuristics and presented theoretical analyses. In addition, several
methods have recently proposed using reinforcement learning or transfer
learning to obtain acquisition functions according to the environment and
data.

###  3.1 Design of acquisition function

Most active learning algorithms use an acquisition function that selects a
more informative sample or representative sample. The most intuitive approach
is to choose the most uncertain data for the current hypothesis. This is
called uncertainty sampling and is based on the expectation that if the
current prediction model labels the most uncertain data, then the model
uncertainty will be reduced the most (Lewis and Gale, 1994; Yang et al.,
2015). Various measures of uncertainty are available depending on the problem
and model. For logistic regression and multinomial logistic regression models,
where the probability value naturally accompanies the prediction, all data
that are query candidates are predicted, and the sample with the prediction
probability closest to $0.5$ (for two-class classification) or with high
entropy in the predicted distribution (entropy sampling) can be selected.
Alternatively, a sample can be selected that maximizes the difference in
probabilities of the labels with the highest and second-highest probabilities
(margin sampling). Another approach is to choose the sample with the smallest
maximum prediction probability (i.e., least confident sampling). Probabilistic
models are a standard means of measuring the prediction uncertainty.
Nevertheless, there are also methods that use the reciprocal of the support
vector machine (SVM) margin (Tong and Koller, 2002), where the hypothesis can
be efficiently narrowed down by dividing the version space into two parts with
approximately equal volumes for each query. To evaluate uncertainty, a
standard approach is to learn a hypothesis that provides a probabilistic
output or to use an ensemble of several hypotheses. However, such prediction
models are not always suitable for learning. Lewis and Catlett (1994) achieved
a low error rate with significantly fewer samples than random sampling by
performing active learning using a different model from the one used for
prediction. Houlsby et al. (2011) proposed a method of issuing queries under a
Bayesian setting where the entropy of the predicted values is high and the
expected entropy of predicted values for the parameter posterior distribution
of the prediction model is low (i.e., low uncertainty of predicted values with
individual parameter settings). They called their method Bayesian active
learning by disagreement (BALD). This method was extended by Kirsch et al.
(2019) for batch active deep learning, (BatchBALD), and it is currently
considered one of the best-performing methods available.

Given the premise of ensemble learning, the uncertainty of a prediction can be
defined as the sample with the most split votes. Seung et al. (1992) studied
the most basic form of query by committee (QBC), where an even number of
hypotheses is learned, and samples are queried such that the prediction
results of two-class labels fall in two halves. They proposed a method of
sampling a hypothesis from the version space for unlabeled samples and issuing
a query when the prediction results do not match. Intuitively, a sample is
difficult to predict when multiple elements of the version space corresponding
to the hypothesis are extracted and do not match the prediction results.
Moreover, the learning efficiency can be improved if the corresponding label
is obtained. Seung et al. (1992) used a method of statistical physics to show
that the generalization error decreases exponentially with the number of
queries in the limit of an infinite number of hypotheses that are learned
simultaneously. Freund et al. (1992) extended the analytical approach of Seung
et al. (1992) to a broader class of discrimination problems. They showed that,
under certain conditions, the generalization error decreases exponentially
with the increase of labeling. Because QBC involves sampling hypotheses from
the version space, rigorous implementation is difficult. Gilad-Bachrach et al.
(2005) proposed a method for efficiently sampling hypotheses by projecting a
version space onto a low-dimensional space. Various acquisition functions are
available (Settles, 2010), such as selecting the query that changes the model
majorly (Cai et al., 2013) or minimizes the approximation of the expected
error (Guo and Greiner, 2007).

The acquisition functions introduced so far have focused on selecting samples
with a large amount of information with regard to model uncertainty and
change. Because this approach does not consider the distribution of unlabeled
data, there is a risk of issuing queries that are considerably affected by the
discriminant surface obtained from the current hypothesis. It is pointed out
by Eisenberg and Rivest (1990) that it is only a limited situation that active
learning improves sample complexity in terms of PAC learning theory. One
explanation for this is that random sampling contains information on
hypotheses (i.e., correct mapping of explanatory variables to response
variables) and on the distribution of explanatory variables, which is lost
with active learning (Freund et al., 1992). It is reasonable to require active
learning strategy to reflect the distribution of explanatory variables (e.g.,
actively sampling points with high density as representative), and methods
have been proposed that are based on the idea of annotating representative
samples. Nguyen and Smeulders (2004) selected representative samples by
clustering pooled data in advance, and Settles and Craven (2008) implemented
the same by weighting data according to the $k$-neighbor distance. However,
selecting a representative sample requires a large number of queries compared
to an approach that focuses on the amount of information, such as uncertainty.
Some studies have considered combining the two approaches to construct
efficient and effective acquisition functions (Xu et al., 2003; Donmez et al.,
2007; Huang et al., 2014)). For example, Huang et al. (2014) considered a
sample with a small margin for a two-class discrimination problem to have high
uncertainty; they selected a representative and informative query by solving
the minimax optimization problem of minimizing the risk for all possible
labels of pooled data, while maximizing the risk of labeling candidate
samples.

###  3.2 Learning the acquisition function

The success or failure of active learning with the acquisition functions
introduced in the previous subsection depends on the prediction model, data
distribution, and compatibility of the acquisition function to them. In
addition to the selection of the prediction model, another problem is the
general difficulty of selecting an appropriate acquisition function.
Accordingly, an approach called meta-active learning has recently been
proposed, where an acquisition function is learned from data (Konyushkova et
al., 2017). A promising approach is to formulate active learning in the
framework of reinforcement learning and express the acquisition function as a
policy to be learned by reinforcement learning (Ebert et al., 2012).

For the reinforcement learning of a typical acquisition function, some methods
approximate the Q-function with a deep Q-network (DQN) (Mnih et al., 2015).
Fang et al. (2017) regarded stream-based active learning as a Markov decision
process and proposed learning the optimal policy by setting the parameter
$\theta$ of the prediction model and represented state as the unlabeled sample
$x$ and action as whether or not labeling is required. Woodward and Finn
(2017) used one-shot learning with neural Turing machines to design states,
behaviors, strategies, and rewards; in addition, they used reinforcement
learning to design a function that determines if a label needs to be requested
for the presented sample for stream-based active learning. By using deep
reinforcement learning with long short-term memory (LSTM) as the Q-function to
determine the value of an action in a certain state, it is possible to judge
whether a sample is unknown and whether a label should be requested.
Specifically, the state (or observation) is a pair of labels for the input and
the previous observation. It is used to determine whether to request a label
for the currently given input, depending on the confidence level of the
prediction for the input and if a label was requested for the previous input.
The action is to request a label for the presented sample or predict the label
itself. If the prediction of the learner of the label is correct, the reward
is zero; if it is incorrect, the reward is negative. If the learner requests a
label, a slightly negative reward is obtained. This allows a policy to be
learned so that a label is not required if there is confidence in the
prediction. Furthermore, Bachman et al. (2017) applied this method to
reinforcement learning of the acquisition function based on matching networks
for pool-based active learning.

The problem of learning a policy for selecting the optimal query in an ever-
changing environment is closely related to the bandit problem. Baram et al.
(2004); Hsu and Lin (2015) considered the design problem of the acquisition
function for active learning as a multi-armed bandit problem. They proposed a
method to select the optimal strategy as multiple acquisition functions or a
linear combination of such functions. Chu and Lin (2017) further proposed a
method of using a strategy learned as a multi-armed bandit problem in one
domain for active learning in a different domain. Wassermann et al. (2019)
proposed reinforcement learning of a filter for stream-based active learning
based on reinforcement learning. Deep reinforcement learning has also been
used to change the acquisition function dynamically to follow changes in the
input distribution. Haußmann et al. (2019) used a Bayesian deep learner as a
model for evaluating uncertainty and defined states with its predicted
distribution. In addition, they proposed a method where another Bayesian deep
learning model is learned separately from the output prediction, and the
current predictor state and the acquisition function appropriate for the data
are used as feature quantities together with the predicted output distribution
and data.

Large-scale models for active learning are not expected to change
significantly if only a single data point is added to the training data (Sener
and Savarese, 2018). In addition, because of the high learning cost of the
model, batch active learning is considered as a suitable approach. Ravi and
Larochelle (2018) used meta-learning for batch active learning of acquisition
functions. (Sener and Savarese, 2018) empirically showed that the classical
active learning of acquisition functions based on heuristics is ineffective
for a convolutional neural network (CNN). They formulated batch selection as a
core-set selection problem, which is defined as selecting a group of data
points for learning such that the predictor trained using the selected subset
is not significantly different from the case where all data points are used
for learning. To solve the core-set selection problem with no label
information, they derived an upper bound for the difference between the
average loss for a subset and the average loss for all data. Subsequently,
they developed an active learning algorithm that minimizes the upper bound.
Attempts to apply active learning to large-scale models such as deep learning
have been actively studied in recent years. Sinha et al. (2019) designs an
acquisition function using a variational autoencoder (VAE) (Kingma and
Welling, 2014) and an adversarial network (Goodfellow et al., 2014).
Specifically, the VAE is trained to match the distribution of labeled and
unlabeled data, and adversarial networks are labeled against the latent space
of the VAE. It is learned to determine whether or not it corresponds to the
data already given. By using the discrimination network of the adversarial
network as the acquisition function, the learning of the acquisition function
that performs query selection independent of the task is realized.

##  4 Theoretical Guarantee

Active learning is a type of feedback system. Because samples are added
through the acquisition function, training samples cannot be expected to
follow a independent and identical distribution, which is the assumption of
standard learning theory and statistical analysis. The generalization error
can be reduced exponentially by reducing the version space, as in QBC for a
noise-free discrimination problem (Freund et al., 1997). The generalization
error for practical algorithms is still being actively researched. In several
cases, the acquisition function is defined so that some criterion is maximized
or minimized. However, this optimization is often an NP-hard problem that is
difficult to solve. This section introduces an approach that uses
submodularity to provide a theoretical guarantee when an optimization problem
associated with the evaluation of an acquisition function is approximated by a
greedy algorithm. Also, researches on evaluation of label complexity are
briefly summarized.

###  4.1 Utilization of submodularity

The concept of submodularity with respect to a set function (Fujishige, 1991)
is useful for characterizing the effect of gradually adding training data,
such as in active learning. Suppose there is a support set $V$ and power set
function $2^{V}$, and a set function $f:2^{V}\to\mathbb{R}$. Here, the set
function $f$ is considered as an index that expresses the value when certain
elements are selected from $V$. Although there are some equivalent
expressions, we adopt the definition of submodularity which is suitable for
the purpose of this paper. For any $S\subseteq V,\;v\in V$,
$f(v|S)=f(\\{v\\}\cup S)-f(S)$ is called the increase by $v$ relative to a set
$S$. For an arbitrary $A\subseteq B\subset V$ and $v\in V\backslash B$, when
$f(A\cup\\{v\\})-f(A)\geq f(B\cup\\{v\\})-f(B)$ or equivalently $f(v|A)\geq
f(v|B)$ holds true, the set function $f$ is called submodular. Intuitively,
the value of the newly added element $v$ decreases as the existing element set
increases in size. When the function $f$ further satisfies $f(v|A)\geq 0$, $f$
is called monotonous. Consider the problem of maximizing $f(A_{k})$ by
sequentially extracting $k$ elements from $V$ to construct a subset $A_{k}$.
For a monotonic submodular function with $f(\emptyset)=0$, the simple policy
$A_{i+1}=A_{i}\cup\\{\operatorname*{argmax}_{e\in V\backslash
A_{i}}f(A_{i}\cup\\{e\\})\\}$, where a greedy element is added solely based on
the value of $f$, guarantees an approximation ratio of $1-1/e$ (Nemhauser et
al., 1978). In other words, $f(A_{k})\geq(1-1/e)\max_{|A|\leq k}f(A)$. Because
the value obtained by acquiring new labels gradually decreases in pool-based
active learning, an algorithm using submodularity is suitable for batch active
learning. If the batch size $k$ is fixed, the problem of selecting $k$ samples
to maximize the entropy of the predicted distribution $p(y|x)$ is guaranteed
to have an approximation rate of $1-1/e$ through selection by the greedy
algorithm based on the submodularity of entropy. Hoi et al. (2006) considered
a two-class discrimination problem using a model with the parameter $\bm{w}$
as a hypothesis, and quantified the effect of batch data on the model by using
a Fisher information matrix

$I_{p}(\bm{w})=-\mathbb{E}_{p}\sum_{y=\pm
1}p(y|x)\frac{\partial^{2}}{\partial\bm{w}^{2}}\log p(y|x)dx$ (2)

for the distribution $p(x)$ of the sample $x$. Specifically, they aimed to
select a batch that was as close as possible to the information that all
samples had, by minimizing $\mathrm{Tr}[I_{q}(\bm{w})^{-1}I_{p}(\bm{w})]$,
where $p(x)$ and $q(x)$ represent the pooled data distribution and selected
batch distribution, respectively. This criterion is equivalent to
asymptotically minimizing the expected squared error and has long been used as
an acquisition function for active learning (Cohn et al., 1996; Fukumizu and
Watanabe, 1994; Fukumizu, 1996). Hoi et al. (2006) showed that an
approximation of $\mathrm{Tr}[I_{q}(\bm{w})^{-1}I_{p}(\bm{w})]$ for a logistic
regression model is a monotonic submodular function and that the selection of
batch data by the greedy algorithm is a suitable approximation of the optimal
batch. Thus, by designing an acquisition function with submodularity for batch
active learning, batch data can be efficiently acquired in each round by the
greedy algorithm at a guaranteed approximation rate. However, the concept of
submodularity is insufficient for describing the selection of the optimal
sample according to data acquired so far and the hypothesis. Some research has
characterized the sample acquisition policy by generalizing the notion of
submodularity, which is called adaptive submodularity. Golovin and Krause
(2010) showed that reducing the version space can be regarded as a covering
problem for a set of unsuitable hypotheses, which has adaptive submodularity.
They utilized this fact to analyze the label complexity of a generalized
binary search algorithm when there is no noise in the observation. When there
is noise, Golovin et al. (2010) considered the problem of seeking a query
strategy that minimizes the cumulative cost of labeling. By selecting samples
in a finite hypothesis space until the size of the version space becomes
unity, a unique hypothesis can be identified. They proposed an efficient
approximation algorithm based on adaptive submodularity. Similarly, the
adaptive submodularity of version space reduction has been used to derive
approximation rates for batch active learning with a greedy algorithm and
pool-based active learning using several criteria, such as entropy
maximization (Chen and Krause, 2013; Nguyen et al., 2013). The concept of
adaptive submodularity is originally for pool-based active learning, but Fujii
and Kashima (2016) extended it as a policy adaptive submodularity, and derived
a mini-batch active learning algorithm and a stream-based active learning
algorithm with guarantees of the approximation rate.

###  4.2 Learning theory of active learning

Determining when active learning reduces the generalization error at a faster
rate than passive learning is an important question and has been the subject
of various studies. Although active learning can be applied to the binary
search introduced in section 1, it does not work well if there is even a small
amount of observation noise. Eisenberg and Rivest (1990) stated that queries
often have little effect on label complexity in the framework of PAC learning.
Nevertheless, active learning has been clearly demonstrated to improve label
complexity in noisy observation cases. Regarding problems where active
learning is no better than passive learning, (Balcan et al., 2008) indicated
that the sample complexity required to train a predictor with a generalization
error of $\varepsilon$ or less differs from the sample complexity required to
guarantee that the resulting predictor has a generalization error of
$\varepsilon$ or less. Subsequently, they analyzed situations where active
learning can effectively reduce label complexity.

Representative studies on the label complexity of active learning algorithms
are found in (Dasgupta, 2005a, b). Dasgupta (2005a) presented a simple
example: for a realizable and one-dimensional case, learning by
$O(\log(1/\varepsilon))$ through a binary search is possible; for a case with
two dimensions or more, $O(1/\varepsilon)$ is unavoidable in the worst case
(i.e., the correct solution is an unbalanced hypothesis). The study shows that
$O(d\log(1/\varepsilon))$ is possible as an average for an appropriate
distribution in the hypothesis space, where $d$ is the VC dimension of the
hypothesis space. For the problem of two-class discrimination without noise,
Dasgupta (2005b)) introduced the following three quantities: desired accuracy
$\varepsilon$, the degree to which the size of the version space is reduced by
a single query $\rho$, and the quantity $\tau$ to characterize the amount of
unlabeled data (i.e., pooled data). Then, defining the notion of
$(\rho,\varepsilon,\tau)$ separability of the hypothesis space $\mathcal{H}$,
active learning algorithm was characterized. By using $\rho$, Dasgupta (2005b)
introduced an example that the sample complexity of active learning is between
$O(1/\varepsilon)$ and $O(\log(1/\varepsilon))$, and for the realizable
hypothesis space, $O(\log(1/\varepsilon))$ can be achieved depending on the
size of the data distribution and pooled data.

In online active learning, when the problem is linearly separable and the data
is in the $d$ dimensional unit sphere, Freund et al. (1997) showed that lable
complexity for solving a realizable problem if of order
$O(d\log(1/\varepsilon))$, and the number of discarded samples without
labeling is of order $O((d/\varepsilon)\log(1/\varepsilon))$. In QBC, it is
generally difficult to sample hypotheses from the version space. Cesa-Bianchi
et al. (2003); Dasgupta et al. (2009) showed that $O(d\log(1/\varepsilon))$ is
realizable with a simpler algorithm than QBC for data distributed on a unit
sphere.

Much of the discussion about sample complexity in active learning has been on
reducing version space, and the hypothesis space has been assumed to contain a
true hypothesis (otherwise the version space can be an empty set). Kääriäinen
(2010) discussed the label complexity of active learning in unrealizable
situations and showed that this typically did not lead to exponential
improvement compared to passive learning. In ordinary statistical learning
theory, faster convergence can be obtained by imposing conditions on the
observation noise rather than using active learning. Even with active
learning, imposing restrictions on conditional distributions, such as the
margin conditions, may result in exponentially faster convergence than with
passive learning. On the other hand, agnostic active learning can be used to
deal with situations where observation noise is not assumed (Balcan et al.,
2009; Hanneke, 2007; Dasgupta et al., 2008). Balcan et al. (2009) proposed an
$A^{2}$ algorithm that operates under arbitrary noise conditions and achieved
a sample complexity of $O(\eta^{2}/\varepsilon^{2})$, where $\eta$ is the
generalization error due to the optimal hypothesis in the assumed hypothesis
space. The learner must approach the optimal hypothesis in the hypothesis
space as close as $\varepsilon$. Hanneke (2007) introduced the discrepancy
coefficient $\theta$, which is determined by the hypothesis space and data
distribution and showed that the sample complexity of the $A^{2}$ algorithm by
(Balcan et al., 2009) is of order $O(\theta^{2}\eta^{2}/\varepsilon^{2})$.
This was further improved to $O(\theta\eta^{2}/\varepsilon^{2})$ by Dasgupta
et al. (2008). Notably, noise is not the only reason for a case to be non-
realizable. Research on sample complexity has also considered noise models,
such as the margin condition (Castro and Nowak, 2008).

Not many studies on label complexity have focused on computational efficiency.
Awasthi et al. (2017) discussed a methodology that guarantees the acquisition
of the error $\varepsilon$ in polynomial time with bounded noise and agnostic
settings. The theoretical analysis of active learning is detailed in a
tutorial by Hanneke and Nowak333https://nowak.ece.wisc.edu/ActiveML.html.

##  5 Stopping problem

For sequential algorithms, the timing to stop learning is generally an
important issue. For active learning, the optimal stopping criterion depends
on the tradeoff between the labeling cost and the gain of improving the
prediction accuracy. If the limit of the measurement technology (noise level)
is known or the theoretically achievable error can be estimated, learning may
be stopped when the prediction accuracy comes close to that level. However,
even if the labeling cost is not clearly determined or the target accuracy is
not clearly defined, there may be situations where active learning is
desirable to reduce learning costs. In the case of a fixed budget for labeling
(i.e., fixed number of times), requesting the full budget of labels may seem
the best approach. However, if sufficient learning data have already been
obtained within the budget, a smaller budget may be sufficient for similar
situations in the future. In addition, determining the room for improvement of
the prediction accuracy when the budget is exhausted is important. A simple
approach to determine whether the maximum generalization error has reached its
peak is to evaluate the prediction performance with cross-validation or
holdout data. However, active learning is generally assumed to be for
situations with high labeling costs, and obtaining holdout and validation data
separately cannot be expected. In other words, determining when to stop active
learning requires self-contained statistics. The optimal stopping problem has
been considered in the field of OR (Gilbert and Mosteller, 1966; Cissé et al.,
2012). In addition, early stopping (Prechelt, 2012) is widely used with
regularization methods, especially for the learning of complex models, such as
deep learning. For kernel ridge regression, early stopping has an implicit
regularization effect (Yao et al., 2007; Rosasco and Villa, 2015), and its
theoretical properties have been considered for nonparametric regression
(Raskutti et al., 2014). Some heuristics have been proposed in the context of
Bayesian optimization (Desautels et al., 2014; Lorenz et al., 2015), but few
have a solid theoretical background (Dai et al., 2019). Particularly for
active learning, the less is more phenomenon (Schohn and Cohn, 2000) has shown
that a model trained with a small amount of data outperforms a model trained
with all the data. This is the motivation for active learning and shows the
significance of determining the optimal time to stop learning. Methods for
determining the stopping criterion for active learning include using the
entropy of the prediction result for the pooled data, changes in the
prediction result, and certainty of the prediction (Zhu et al., 2008); or
considering the stability of prediction results by multiple predictors
(Bloodgood and Grothendieck, 2013; Altschuler and Bloodgood, 2019). Other
methods include stopping when the sample inside the SVM margin disappears from
the pooled data (Schohn and Cohn, 2000; Vlachos, 2008) and checking the
convergence of a similar quantities (Laws and Schütze, 2008; Krause and
Guestrin, 2007), but their theoretical bases have not been fully verified.

Krause and Guestrin (2007) focused on batch-mode Bayesian active learning with
Gaussian process regression; they used submodularity to derive a relation
among mutual information for the predicted distributions when samples are
actively selected or randomly selected. Although their method has been
suggested as a stopping criterion for active learning, it significantly relies
on the prediction model being a Gaussian process regression, and it also
requires appropriate discretization of the domain of an explanatory variable.
The $A^{2}$ algorithm of Balcan et al. (2009) is formulated as the following
procedure according to Hanneke (2014). For the $t$-th iteration of the
algorithm, $2t$ unlabeled samples are selected and set as $S$. A query is
issued, and a label is provided to the intersection $Q=DIS(\mathcal{H})\cap S$
of the disagreement subspace

$\displaystyle DIS(\mathcal{H})=\\{x\in\mathcal{X}|\exists
h,h^{\prime}\in\mathcal{H},\;h(x)\neq h^{\prime}(x)\\}$

for the hypothesis space and $S$. By using the labeled dataset $Q$, the
empirical loss $\mathcal{L}_{Q}(h)$ is minimized to select the hypothesis
$h\in\mathcal{H}$. Namely,
$\hat{h}=\operatorname*{argmin}_{h\in\mathcal{H}}\mathcal{L}_{Q}(h)$. Finally,
a hypothesis $h$ is removed from the hypothesis space if it satisfies

$\mathcal{L}_{Q}(h)-\mathcal{L}_{Q}(\hat{h})>\sqrt{\hat{P}_{Q}(h\neq\hat{h})\frac{d}{|Q|}}.$

Here, $\hat{P}_{Q}(h\neq\hat{h})$ is the estimated probability using $Q$ that
$h$ is not equal to the hypothesis $\hat{h}$, and $d$ is the VC dimension of
the hypothesis space. By repeating this process and reducing the hypothesis
space, a highly accurate hypothesis remains. Using this algorithm, it is
natural to stop learning if
$\max_{h\in\mathcal{H}}\sqrt{\hat{P}_{Q}(h\neq\hat{h})\frac{d}{|Q|}}<\epsilon$
with an appropriate threshold $\epsilon>0$.

In a more general approach, Ishibashi and Hino (2020) tackled the problem of
stopping active learning from the perspective of PAC Bayesian learning
(McAllester, 1999) when the posterior distribution is obtained. The range of
the loss function $\ell$ is assumed to be $[a,b],\;-\infty<a<b<\infty$. In the
PAC Bayesian learning framework, hypothesis $h$ also follows the distribution
of function values, and a prior distribution $p(h)$ is introduced. Let
$p(h|S_{n})$ be the posterior distribution of $h\in\mathcal{H}$. If the
negative log-likelihood $\ell$ is the loss function, then $\ell(h,x,y)=-\log
p(y|h,x)$ and $p(y|h,x)=e^{-\ell(h,x,y)}$. The posterior distribution of $h$
obtained using the training data $S_{n}$ is

$\displaystyle p(h|S_{n})=$
$\displaystyle\frac{p(\bm{y}_{n}|h)p(h)}{p(\bm{y}_{n})}=\frac{e^{-n\mathcal{L}_{S_{n}}(h)}p(h)}{p(\bm{y}_{n})}$

where the values of the response variable included in $S_{n}$ are arranged as
the vector $\bm{y}_{n}$. The predictive distribution for $y_{\ast}$
corresponding to the new input point $x_{\ast}$ can be represented as

$\displaystyle p(y_{\ast}|S_{n},x_{\ast})=$ $\displaystyle\int
p(y_{\ast}|h,x_{\ast})p(h|S_{n})dh.$

The posterior distributions of the hypotheses obtained by learning with
$S_{n}$ and $S_{n+1}=S_{n}\cup\\{(x_{n+1},y_{n+1})\\}$ are $p(h|S_{n})$ and
$p(h|S_{n+1})$, respectively. The difference with the expected values for the
posterior distribution of the expected risk is defined as

$\mathcal{R}(p(h|S_{n}),p(h|S_{n+1}))=\mathbb{E}_{p(h|S_{n})}[\mathcal{L}_{D}(h)]-\mathbb{E}_{p(h|S_{n+1})}[\mathcal{L}_{D}(h)],$
(3)

where $\mathcal{R}$ represents the amount of reduction in the expected
generalization error. When $p(h|S_{0})=p(h)$, then

$\displaystyle\mathcal{R}(p(h)|p(h|S_{n}))=$
$\displaystyle\sum_{i=1}^{n}\mathcal{R}(p(h|S_{i-1}),p(h|S_{i}))$
$\displaystyle=$
$\displaystyle\mathbb{E}_{p(h)}[\mathcal{L}_{D}(h)]-\mathbb{E}_{p(h|S_{n})}[\mathcal{L}_{D}(h)]=const.-\mathbb{E}_{p(h|S_{n})}[\mathcal{L}_{D}(h)]$

and the convergence of $\mathcal{R}$ and
$\mathbb{E}_{p(h|S_{n})}[\mathcal{L}_{D}(h)]$ is equivalent. If $p(h|S_{n})$
and $p(h|S_{n+1})$ are the posterior distributions of $h\in\mathcal{H}$ given
$S_{n}$ and $S_{n+1}$, then the following holds true:

$\mathcal{R}(p(h|S_{n}),p(h|S_{n+1}))\leq D_{KL}[p(h|S_{n})||p(h|S_{n+1})]+C.$
(4)

Here, $D_{KL}$ is the Kullback–Leibler (KL) divergence, and $C$ is a quantity
that depends on the range $[a,b]$ that $h\in\mathcal{H}$ can take. The KL
divergence on the right hand side is a quantity that can be calculated for a
concrete predictor (e.g., Gaussian process) under certain conditions.
Ishibashi and Hino (2020) proposed a method to determine the optimal time to
stop active learning by sequentially calculating the upper bound of
$\mathcal{R}$ and combining convergence tests for pool-based active learning
when Gaussian process regression is the predictor and the acquisition function
is the predictive variance. Note that the upper bound of Eq. (4) does not
become less than the constant term because KL divergence is nonnegative.
Therefore, when the constant term becomes large, the upper bound does not
become tight. Another upper bound can be derived that is tight even if the
constant term is large as long as the KL divergence is sufficiently small. Let
$p(h|S)$ and $p(h|S^{\prime})$ be posterior distributions for the hypothesis
$h\in\mathcal{H}$ given $S$ and $S^{\prime}$. At this time, the following
inequality holds for any $\lambda>0$ and any measurable function
$\mathcal{L}_{\mathcal{D}}(f)$ and
$v\geq\mathbb{E}[\mathcal{L}^{2}_{\mathcal{D}}(f)]$:

$\mathcal{R}(p(h|S),p(h|S^{\prime}))\leq\frac{v}{b-a}(e^{W(u)+1}-1).$ (5)

Here, $W(\cdot)$ is the Lambert $W$ function, and
$u=\frac{(b-a)^{2}D_{KL}[p(h|S)||p(h|S^{\prime})]-v}{ve}$. For the bound of
Eq. (5), $W\left(-1/e\right)=-1$ when the KL divergence is zero. This
guarantees that the upper bound also approaches zero as the KL divergence
approaches zero, making it a tight bound.

##  6 Application to measurement and material development

Since the establishment of the US Materials Genome Initiative, research has
been actively done to improve the efficiency, acceleration, and sophistication
of materials and measurements through machine learning. Prototyping high-
performance materials and measurements in synchrotron radiation facilities is
often time-consuming and costly. Therefore, active learning is expected to
substantially improve efficiency (Lookman et al., 2019; del Rosario et al.,
2020; Tian et al., 2020). This section introduces two example applications of
active learning to material searching and measurement.

###  6.1 Efficient phase diagram creation

A phase diagram or state diagram represents the relationship between the state
of a material or system and thermodynamic parameters. For example, $H_{2}O$
takes one of three states depending on the temperature and pressure: solid,
gas, and liquid. For metallic materials, the microstructure can be austenite,
ferrite, or pearlite depending on the mixture ratio of raw materials,
processing temperature, and annealing pattern. Understanding the relationship
between these different states and the thermodynamic parameters is necessary
to understand the material properties and develop materials with desirable
properties. An important first step for material development is running trials
and measuring materials while varying different parameters to create phase
diagrams. Comprehensive prototyping and the measurement of multiple parameters
are often bottlenecks for the development process. Terayama et al. (2019)
proposed using active learning to create phase diagrams efficiently. In their
method, the range of the target parameter is divided into an appropriate grid
resolution, and the state is measured at a few points on the grid. In terms of
the notation of active learning, the grid is $\mathcal{X}$, and the parameter
configuration represented by each point corresponds to $x\in\mathcal{X}$. The
state at each point $x$ corresponds to $y$. A probability map is created for
the grid using a label propagation algorithm based on the diffusion process
and starting from a point that corresponds to these few $(x,y)$. Uncertainty
is expected to increase near the phase boundary. Based on the probability
values obtained at each point, a phase diagram can be created by sequentially
selecting measurement points with three types of acquisition functions based
on uncertainty sampling. Terayama et al. (2019) conducted an evaluation
experiment where they created a three-phase diagrams of water and of Si–Al–Mg
glass–ceramic glaze. They showed that the same phase diagram could be obtained
with approximately 20% of the measurements compared to using a conventional
dense grid.

###  6.2 Improving the efficiency of X-ray magnetic circular dichroism
spectroscopy

As an example of the improvement in measurement efficiency achieved by active
learning, its application to X-ray magnetic circular dichroism (XMCD)
spectroscopy by Ueno et al. (2018) is briefly introduced here. For XMCD
spectroscopy, because the integrated intensity of the spectrum directly
corresponds to the magnetic moment according to the magneto-optical sum rule,
this can be used to analyze the magnetic properties of a material
quantitatively. A precise spectrum can be obtained by fine grid of the energy
measurement point, and high-precision quantitative analysis is possible by
integrating the spectrum. In the past, the energy was measured at several
hundred points based on the intuition and experience of the experimenter. The
spectrum measurement can be formulated as a problem of estimating a function
or curve $f(x)$ under the assumption that the spectral curves with the X-ray
energy on the x-axis and absorption on the y-axis are connected by the
function $y=f(x)+\varepsilon$, where $\varepsilon$ is the measurement noise.
Thus, approximating the function $f(x)$ from a small number of measured points
is simply a one-dimensional regression problem with active learning. Ueno et
al. (2018) approximated the relationship between the X-ray energy ($x$) and
absorption amount ($y$) through Gaussian process regression, and they used the
predictive variance at an unobserved point of the Gaussian process regression
as the acquisition function. The spectral data corresponding to 220 points
measured previously were regarded as ground truth. The initial data were set
to 30 randomly measured points, and a Gaussian process model was applied.
Points with a large predictive variance were sequentially measured from the
220 candidate points (corresponding to pooled data) excluding the measured
points. The integrated value of the Gaussian process regression curve
according to the 20 new points added to the initial 30 points was confirmed to
be approximately the same as the integrated value of the ground truth
spectrum. In other words, the physical quantity could be measured with
approximately 22% of the number of measurements for the conventional method,
which demonstrates the usefulness of active learning for material measurement.
However, several issues remain to be addressed, such as the introduction of
prior knowledge, dealing with measurement noise (e.g., whether or not short-
term measurements should be performed multiple times), and stopping criteria.

##  7 Future works and prospects

Active learning has long history, originated in sequential experimental
design, but it is still being actively researched because of its usefulness
and necessity. Depending on the samples used to train the predictor, some
samples may not help improve the prediction performance or even degrade it,
such as in the case of incorrect labels or outliers. Although not stated in
this paper, active learning has been applied to screening such samples (Abe et
al., 2006). In addition, methods such as curriculum learning (Bengio et al.,
2009) and self-paced learning (Kumar et al., 2010), where samples are selected
in an appropriate order for sequential and iterative learning, can be
considered as an extension of pool-based active learning.

For active learning, a small number of pre-collected samples are assumed to be
available at hand. However, if the pre-collected samples are chosen according
to a certain collection policy such as treatment of a particular patient, then
the initial learning uses data that differ from the population distribution of
the pooled data. Thus, the variance of the estimated loss function will be
excessively large if the initial collected data are not handled properly.
Active learning using initial data collected according to such a policy (Yan
et al., 2018, 2019) or using a decision-making model (Sundin et al., 2019) has
attracted attention in recent years. Numerous studies have used active
learning to select the optimal intervention for identification in causal
reasoning (Tong and Koller, 2001; He and Geng, 2008; Masegosa and Moral, 2013;
Hauser and Bühlmann, 2014) and analyze the number of interventions (i.e.,
label complexity) required to identify causal relationships (Shanmugam et al.,
2015; Greenewald et al., 2019).

In deep learning, over-parameterization refers to the learning error tending
to zero while the test error tends to decrease continuously. In this
situation, bounds using learning errors are meaningless. The application of
non-parametric methods (e.g., the kernel method or deep learning) may be a
promising approach for reducing the problem of model bias inherent in active
learning, which assumes a conventional simple hypotheses class. However, few
studies have considered this approach, except for heuristic ones. For example,
Karzand and Nowak (2020) focused on the smoothness of the function
characterized by the RKHS norm of the function $h\in\mathcal{H}$ to be
approximated, and they proposed the acquisition function
$x^{\ast}=\operatorname*{argmax}_{x\in\mathcal{X}}\min\\{\|h_{-}^{x}\|,\|h_{+}^{x}\|\\}$,
where $\|h_{\pm}^{x}\|$ is the RKHS norm of the hypothesis $h\in\mathcal{H}$
that is updated when the label $y$ of the point $x$ is $+1$ or $-1$. They
showed a case in which a label complexity of $O(\log n)$ can be achieved with
this acquisition function, albeit for a special function class. As described
above, several active learning methods assume that some labeled data are
available in advance, but there has been not enough discussion about the
quality of the initially obtained data. Identifying a sample set for labeling
from unlabeled pooled data is important for the initialization of active
learning and has been discussed by Murata and Suzuki (2020).

## Acknowledgement

The author is supported by JST JPMJCR1761 and JPMJMI19G1. The author thank Dr.
Hideaki Ishibashi, Tetsuro Ueno, Kanta Ono and Mr. Masanari Kimura for their
valuable comments on the draft of this paper.

## References

  * Abe et al. (2006) Naoki Abe, Bianca Zadrozny, and John Langford.  Outlier detection by active learning.  In _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , volume 2006, pages 504--509, 2006.  ISBN 1595933395.  doi: 10.1145/1150402.1150459.
  * Altschuler and Bloodgood (2019) Michael Altschuler and Michael Bloodgood.  Stopping Active Learning Based on Predicted Change of F Measure for Text Classification.  In _IEEE International Conference on Semantic Computing, ICSC 2019_ , pages 47--54, 2019.  ISBN 9781538667835.  doi: 10.1109/ICOSC.2019.8665646.  URL http://dx.doi.org/10.1109/ICOSC.2019.8665646.
  * Angluin (1988) Dana Angluin.  Queries and Concept Learning.  _Machine Learning_ , 2(4):319--342, 1988.  ISSN 15730565.  doi: 10.1023/A:1022821128753.
  * Atlas et al. (1990) Les E Atlas, David Cohn, and Richard Ladner.  Training connectionist networks with queries and selective sampling.  In _Advances in Neural Information Processing Systems, NIPS 1989_ , pages 566--573, 1990.  ISBN 9781558601000.
  * Awasthi et al. (2017) Pranjal Awasthi, Maria Florina Balcan, and Philip M. Long.  The power of localization for efficiently learning linear separators with noise.  _J. ACM_ , 63(6), January 2017.  ISSN 0004-5411.  doi: 10.1145/3006384.  URL https://doi.org/10.1145/3006384.
  * Bachman et al. (2017) Philip Bachman, Alessandro Sordoni, and Adam Trischler.  Learning algorithms for active learning.  In _International Conference on Machine Learning, ICML 2017_ , pages 301--310, 2017.
  * Balcan et al. (2008) Maria Florina Balcan, Steve Hanneke, and Jennifer Wortman.  The true sample complexity of active learning.  In _Conference on Learning Theory, COLT 2008_ , pages 45--56, 2008\.
  * Balcan et al. (2009) Maria-Florina Balcan, Alina Beygelzimer, and John Langford.  Agnostic active learning.  _Journal of Computer and System Sciences_ , 75(1):78 -- 89, 2009.  ISSN 0022-0000.  doi: https://doi.org/10.1016/j.jcss.2008.07.003.  URL http://www.sciencedirect.com/science/article/pii/S0022000008000652.  Learning Theory 2006.
  * Baram et al. (2004) Yoram Baram, Ran El-Yaniv, and Kobi Luz.  Online Choice of Active Learning Algorithms.  _Journal of Machine Learning Research_ , 5:255--291, 2004\.
  * Bengio et al. (2009) Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston.  Curriculum learning.  In _International Conference On Machine Learning, ICML 2009_ , pages 41--48, 2009.  ISBN 9781605585161.
  * Bloodgood and Grothendieck (2013) Michael Bloodgood and John Grothendieck.  Analysis of Stopping Active Learning based on Stabilizing Predictions.  In _Conference on Computational Natural Language Learning, Proceedings, CoNLL 2013_ , pages 10--19, 2013.  ISBN 9781937284701.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine Learning_ , 45(1):5--32, 2001.  ISSN 08856125.  doi: 10.1023/A:1010933404324.
  * Burbidge et al. (2007) Robert Burbidge, Jem J. Rowland, and Ross D. King.  Active learning for regression based on query by committee.  In Hujun Yin, Peter Tino, Emilio Corchado, Will Byrne, and Xin Yao, editors, _Intelligent Data Engineering and Automated Learning, IDEAL 2007_ , pages 209--218, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.  ISBN 978-3-540-77226-2.
  * Cai et al. (2013) Wenbin Cai, Ya Zhang, and Jun Zhou.  Maximizing expected model change for active learning in regression.  In _IEEE International Conference on Data Mining, ICDM 2013_ , pages 51--60, 2013.  doi: 10.1109/ICDM.2013.104.
  * Castro et al. (2005) Rui Castro, Rebecca Willett, and Robert Nowak.  Faster rates in regression via active learning.  In _Advances in Neural Information Processing Systems, NIPS 2005_ , pages 179--186, 2005.  ISBN 9780262232531.
  * Castro and Nowak (2008) Rui M Castro and Robert D Nowak.  Minimax bounds for active learning.  _IEEE Transactions on Information Theory_ , 54(5):2339--2353, 2008.  ISSN 00189448.  doi: 10.1109/TIT.2008.920189.
  * Cesa-Bianchi et al. (2003) Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  Learning probabilistic linear-threshold classifiers via selective sampling.  In _Annual Conference on Learning Theory, COLT 2003_ , volume 2777, pages 373--387, 2003.  doi: 10.1007/978-3-540-45167-9˙28.
  * Chen and Krause (2013) Yuxin Chen and Andreas Krause.  Near-optimal batch mode active learning and adaptive submodular optimization.  In _International Conference on Machine Learning, ICML 2013_ , pages 160--168, 2013.
  * Chu and Lin (2017) Hong Min Chu and Hsuan Tien Lin.  Can active learning experience be transferred?  In _IEEE International Conference on Data Mining, ICDM 2017_ , pages 841--846, 2017.  ISBN 9781509054725.  doi: 10.1109/ICDM.2016.135.
  * Cissé et al. (2012) Mamadou Cissé, Pierre Patie, and Etienne Tanré.  Optimal stopping problems for some markov processes.  _Annals of Applied Probability_ , 22(3):1243--1265, 2012.  ISSN 10505164.  doi: 10.1214/11-AAP795.
  * Cohn et al. (1994) David Cohn, Les Atlas, and Richard Ladner.  Improving Generalization with Active Learning.  _Machine Learning_ , 15(2):201--221, 1994.  ISSN 15730565.  doi: 10.1023/A:1022673506211.
  * Cohn et al. (1996) David A. Cohn, Zoubin Ghahramani, and Michael I. Jordan.  Active learning with statistical models.  _Journal of Artificial Intelligence Research_ , 4:129--145, 1996.  ISSN 10769757.  doi: 10.1613/jair.295.
  * Dai et al. (2019) Zhongxiang Dai, Haibin Yu, Bryan Kian Hsiang Low, and Patrick Jaillet.  Bayesian optimization meets Bayesian optimal stopping.  In _International Conference on Machine Learning, ICML 2019_ , pages 2701--2725, 2019.  ISBN 9781510886988.
  * Dasgupta (2005a) Sanjoy Dasgupta.  Analysis of a greedy active learning strategy.  In _Advances in Neural Information Processing Systems_ , 2005a.  ISBN 0262195348.
  * Dasgupta (2005b) Sanjoy Dasgupta.  Coarse sample complexity bounds for active learning.  In _Advances in Neural Information Processing Systems, NIPS 2005_ , pages 235--242, 2005b.  ISBN 9780262232531.
  * Dasgupta et al. (2008) Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni.  A general agnostic active learning algorithm.  _10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008_ , pages 1--8, 2008.
  * Dasgupta et al. (2009) Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni.  Analysis of perceptron-based active learning.  _Journal of Machine Learning Research_ , 10:281--299, 2009\.  ISSN 15324435.
  * del Rosario et al. (2020) Zachary del Rosario, Matthias Rupp, Yoolhee Kim, Erin Antono, and Julia Ling.  Assessing the frontier: Active learning, model accuracy, and multi-objective candidate discovery and optimization.  _The Journal of Chemical Physics_ , 153(2), 2020.  ISSN 0021-9606.  doi: 10.1063/5.0006124.  URL http://aip.scitation.org/doi/10.1063/5.0006124.
  * Desautels et al. (2014) Thomas Desautels, Andreas Krause, and Joel Burdick.  Parallelizing exploration-exploitation tradeoffs with Gaussian process bandit optimization.  _Journal of Machine Learning Research_ , 15:4053--4103, 2014\.  ISSN 1533-7928.
  * Donmez et al. (2007) Pinar Donmez, Jaime G Carbonell, and Paul N Bennett.  Dual strategy active learning.  In _European Conference on Machine Learning and Principles and Practiceof Knowledge Discovery in Database_ , pages 116--127, 2007.  ISBN 9783540749578.  doi: 10.1007/978-3-540-74958-5˙14.
  * Ebert et al. (2012) Sandra Ebert, Mario Fritz, and Bernt Schiele.  RALF: A reinforced active learning formulation for object class recognition.  In _Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , pages 3626--3633, 2012.  ISBN 9781467312264.  doi: 10.1109/CVPR.2012.6248108.
  * Eisenberg and Rivest (1990) Bonnie Eisenberg and Ronald L. Rivest.  On the sample complexity of pac-learning using random and chosen examples.  In _Conference on Learning Theory, COLT 1990_ , 1990.
  * Fang et al. (2017) Meng Fang, Yuan Li, and Trevor Cohn.  Learning how to active learn: A deep reinforcement learning approach.  In _Conference on Empirical Methods in Natural Language Processing, EMNLP 2017_ , pages 595--605, 2017.  ISBN 9781945626838.  doi: 10.18653/v1/d17-1063.  URL https://github.com/.
  * Fisher (1935) R.A. Fisher.  _The design of experiments_.  Oliver and Boyd, Edinburgh, 1935.
  * Ford and Silvey (1980) I Ford and S D Silvey.  A Sequentially Constructed Design for Estimating a Nonlinear Parametric Function.  _Biometrika_ , 67(2):381--388, 1980.
  * Freund et al. (1992) Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby.  Information, prediction, and query by committee.  In _Advances in Neural Information Processing Systems, NIPS 1992_ , pages 483--490, 1992.  URL http://papers.nips.cc/paper/622-information-prediction-and-query-by-committee.
  * Freund et al. (1997) Yoav Freund, H Sebastian Seung, Eli Shamir, and Naftali Tishby.  Selective Sampling Using the Query by Committee Algorithm.  _Machine Learning_ , 28(2-3):133--168, 1997.  ISSN 08856125.  doi: 10.1023/A:1007330508534.
  * Fujii and Kashima (2016) Kaito Fujii and Hisashi Kashima.  Budgeted stream-based active learning via adaptive submodular maximization.  In _Advances in Neural Information Processing Systems, NIPS 2016_ , pages 514--522, 2016.
  * Fujishige (1991) S. Fujishige.  _Submodular Functions and Optimization_.  ISSN. Elsevier Science, 1991.  ISBN 9780080867878.
  * Fukumizu (1996) Kenji Fukumizu.  Active learning in multilayer perceptrons.  In _Advances in Neural Information Processing Systems, NIPS 1996_ , volume 8, pages 295--301, 1996.
  * Fukumizu and Watanabe (1994) Kenji Fukumizu and Sumio Watanabe.  Error estimation and learning data arrangement for neural networks.  In _IEEE International Conference on Neural Networks, ICNN 1994_ , volume 2, pages 777--780 vol.2, 1994.
  * Gilad-Bachrach et al. (2005) Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby.  Query by Committee made real.  In _Advances in Neural Information Processing Systems, NIPS 2005_ , pages 443--450, 2005.  ISBN 9780262232531.  URL http://www.cs.huji.ac.il/labs/learning/code/qbc.
  * Gilbert and Mosteller (1966) John P Gilbert and Frederick Mosteller.  Recognizing the Maximum of a Sequence.  _Journal of the American Statistical Association_ , 61(313):35--73, 1966.  ISSN 1537274X.  doi: 10.1080/01621459.1966.10502008.
  * Golovin and Krause (2010) Daniel Golovin and Andreas Krause.  Adaptive submodularity: A new approach to active learning and stochastic optimization.  In _Conference on Learning Theory, COLT 2010_ , pages 333--345. Omnipress, 2010.
  * Golovin and Krause (2011) Daniel Golovin and Andreas Krause.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  _Journal of Artificial Intelligence Research_ , 42:427--486, 2011.  ISSN 10769757.  doi: 10.1613/jair.3278.
  * Golovin et al. (2010) Daniel Golovin, Andreas Krause, and Debajyoti Ray.  Near-optimal Bayesian active learning with noisy observations.  In _Advances in Neural Information Processing Systems, NIPS 2010_ , 2010.  ISBN 9781617823800.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In _Advances in Neural Information Processing Systems, NIPS 2014_ , volume 27, pages 2672--2680. Curran Associates, Inc., 2014.
  * Greenewald et al. (2019) Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu, Enric Boix-Adserà, and Guy Bresler.  Sample Efficient Active Learning of Causal Trees.  In _Advances in Neural Information Processing Systems, NeurIPS 2019_ , 2019.
  * Guo and Greiner (2007) Yuhong Guo and Russ Greiner.  Optimistic active learning using mutual information.  In _International Joint Conference on Artificial Intelligence, IJCAI 2007_ , pages 823--829, 2007.  URL http://www.cs.ualberta.ca/.
  * Hall and Molchanov (2003) Peter Hall and Ilya Molchanov.  Sequential methods for design-adaptive estimation of discontinuities in regression curves and surfaces.  _Annals of Statistics_ , 31(3):921--941, 2003\.  ISSN 00905364.  doi: 10.1214/aos/1056562467.
  * Hanneke (2007) Steve Hanneke.  A bound on the label complexity of agnostic active learning.  In _International Conference on Machine Learning_ , volume 227, pages 353--360, 2007.  doi: 10.1145/1273496.1273541.
  * Hanneke (2014) Steve Hanneke.  Theory of disagreement-based active learning.  _Foundations and Trends in Machine Learning_ , 7(2-3):131--309, 2014.  ISSN 1935-8237.  doi: 10.1561/2200000037.  URL http://dx.doi.org/10.1561/2200000037.
  * Hauser and Bühlmann (2014) Alain Hauser and Peter Bühlmann.  Two optimal strategies for active learning of causal models from interventional data.  _International Journal of Approximate Reasoning_ , 55(4):926--939, 2014.  ISSN 0888613X.  doi: 10.1016/j.ijar.2013.11.007.  URL www.elsevier.com/locate/ijar.
  * Haußmann et al. (2019) Manuel Haußmann, Fred Hamprecht, and Melih Kandemir.  Deep active learning with adaptive acquisition.  In _International Joint Conference on Artificial Intelligence, IJCAI 2019_ , pages 2470--2476, 2019.  ISBN 9780999241141.  doi: 10.24963/ijcai.2019/343.
  * He and Geng (2008) Yang Bo He and Zhi Geng.  Active learning of causal networks with intervention experiments and optimal designs.  _Journal of Machine Learning Research_ , 9:2523--2547, 2008\.  ISSN 15324435.
  * Hoi et al. (2006) Steven C.H. Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu.  Batch mode active learning and its application to medical image classification.  In _Proceedings of the International Conference on Machine Learning_ , volume 148, pages 417--424, 2006.  ISBN 1595933832.  doi: 10.1145/1143844.1143897.
  * Hotelling (1944) Harold Hotelling.  Some Improvements in Weighing and Other Experimental Techniques.  _Annals of Mathematical Statistics_ , 15(3):297--306, 1944.  ISSN 0091-1798.  URL http://projecteuclid.org/euclid.aop/1176996548.
  * Houlsby et al. (2011) Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel.  Bayesian Active Learning for Classification and Preference Learning.  pages 1--17, 2011.  URL http://arxiv.org/abs/1112.5745.
  * Hsu and Lin (2015) Wei Ning Hsu and Hsuan Tien Lin.  Active learning by learning.  In _AAAI Conference on Artificial Intelligence, AAAI 2015_ , volume 4, pages 2659--2665, 2015.  ISBN 9781577357025.  URL www.aaai.org.
  * Huang et al. (2014) Sheng Jun Huang, Rong Jin, and Zhi Hua Zhou.  Active Learning by Querying Informative and Representative Examples.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 36(10):1936--1949, 2014.  ISSN 01628828.  doi: 10.1109/TPAMI.2014.2307881.
  * Ishibashi and Hino (2020) Hideaki Ishibashi and Hideitsu Hino.  Stopping criterion for active learning based on deterministic generalization bounds.  In _International Conference on Artificial Intelligence and Statistics, AISTATS 2020_ , pages 386--397, 2020.  URL http://proceedings.mlr.press/v108/ishibashi20a.html.
  * Johnson (1961) N. L. Johnson.  Sequential Analysis: A Survey.  _Journal of the Royal Statistical Society. Series A (General)_ , 124(3):372, 1961.  ISSN 00359238.  doi: 10.2307/2343243.
  * Kääriäinen (2010) Matti Kääriäinen.  Active Learning in the Non-realizable Case.  In _International Conference on Algorithmic Learning Theory, ALT 2010_ , pages 63--77, 2010.
  * Karzand and Nowak (2020) Mina Karzand and Robert D Nowak.  MaxiMin Active Learning in Overparameterized Model Classes.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):167--177, 2020.  doi: 10.1109/jsait.2020.2991518.
  * Kingma and Welling (2014) Diederik P. Kingma and Max Welling.  Auto-Encoding Variational Bayes.  In _International Conference on Learning Representations, ICLR 2014_ , 2014.
  * Kirsch et al. (2019) Andreas Kirsch, Joost van Amersfoort, and Yarin Gal.  Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning.  In _Advances in Neural Information Processing Systems, NeurIPS 2019_ , pages 7024--7035, 2019.  URL http://papers.nips.cc/paper/8925-batchbald-efficient-and-diverse-batch-acquisition-for-deep-bayesian-active-learning.
  * Konyushkova et al. (2017) Ksenia Konyushkova, Sznitman Raphael, and Pascal Fua.  Learning active learning from data.  In _Advances in Neural Information Processing Systems, NIPS 2017_ , volume 2017-Decem, pages 4226--4236, 2017.  URL http://ksenia.konyushkova.com.
  * Krause and Guestrin (2007) Andreas Krause and Carlos Guestrin.  Nonmyopic active learning of Gaussian processes: An exploration- exploitation approach.  In _International Conference on Machine Learning_ , volume 227, pages 449--456, 2007.  doi: 10.1145/1273496.1273553.
  * Krogh and Vedelsby (1995) Anders Krogh and Jesper Vedelsby.  Neural Network Ensembles, Cross Validation, and Active Learning.  In _Advances in Neural Information Processing Systems, NIPS 1995_ , pages 231--238, 1995.  ISBN 0262201046.  doi: 10.1.1.37.8876.
  * Kumar et al. (2010) M Pawan Kumar, Benjamin Packer, and Daphne Koller.  Self-paced learning for latent variable models.  In _Advances in Neural Information Processing Systems, NIPS 2010_ , 2010.  ISBN 9781617823800.
  * Laws and Schütze (2008) Florian Laws and Hinrich Schütze.  Stopping criteria for active learning of named entity recognition.  In _International Conference on Computational Linguistics, Coling 2008_ , volume 1, pages 465--472. Manchester, 2008.  ISBN 9781905593446.  doi: 10.3115/1599081.1599140.
  * Lecun et al. (1998) Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278--2324, 1998.
  * Lewis and Catlett (1994) David D. Lewis and Jason Catlett.  Heterogeneous Uncertainty Sampling for Supervised Learning.  In _International Conference on Machine Learning, ICML 1994_ , pages 148--156, 1994.  doi: 10.1016/b978-1-55860-335-6.50026-x.
  * Lewis and Gale (1994) David D Lewis and William A Gale.  A sequential algorithm for training text classifiers.  In _International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 1994_ , pages 3--12. Springer-Verlag, 1994.  ISBN 038719889X.  doi: 10.1145/219587.219592.
  * Lindley (1956) Dennis Lindley.  On a Measure of the Information Provided by an Experiment.  _Annals of Mathematical Statistics_ , 27(4):986--1005, 1956.  URL https://projecteuclid.org/download/pdf{_}1/euclid.aoms/1177728069.
  * Lookman et al. (2019) Turab Lookman, Prasanna V Balachandran, Dezhen Xue, and Ruihao Yuan.  Active learning in materials science with emphasis on adaptive sampling using uncertainties for targeted design.  _npj Computational Materials_ , 5(1), 2019.  ISSN 20573960.  doi: 10.1038/s41524-019-0153-8.  URL https://doi.org/10.1038/s41524-019-0153-8.
  * Lorenz et al. (2015) Romy Lorenz, Ricardo P Monti, Ines R Violante, Aldo A Faisal, Christoforos Anagnostopoulos, Robert Leech, and Giovanni Montana.  Stopping criteria for boosting automatic experimental design using real-time fMRI with Bayesian optimization.  In _5th NIPS Workshop on Machine Learning and Interpretation in Neuroimaging: Beyond the Scanner_ , 2015.  URL http://arxiv.org/abs/1511.07827.
  * Lowell et al. (2019) David Lowell, Zachary C. Lipton, and Byron C. Wallace.  Practical Obstacles to Deploying Active Learning.  In _Conference on Empirical Methods in Natural Language Processing and the International Joint Conference on Natural Language Processing, EMNLP/IJCNLP 2019_ , pages 21--30, 2019.  doi: 10.18653/v1/d19-1003.
  * Mackay (1992) David John Cameron Mackay.  _Bayesian Methods for Adaptive Models_.  PhD thesis, USA, 1992.  UMI Order No. GAX92-32200.
  * Masegosa and Moral (2013) Andrés R. Masegosa and Serafín Moral.  An interactive approach for Bayesian network learning using domain/expert knowledge.  _International Journal of Approximate Reasoning_ , 54(8):1168--1181, 2013.  ISSN 0888613X.  doi: 10.1016/j.ijar.2013.03.009.  URL http://dx.doi.org/10.1016/j.ijar.2013.03.009.
  * McAllester (1999) David A. McAllester.  Some pac-bayesian theorems.  _Machine Learnerning_ , 37(3):355--363, 1999.  doi: 10.1023/A:1007618624809.  URL https://doi.org/10.1023/A:1007618624809.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529--533, 2015.  ISSN 14764687.  doi: 10.1038/nature14236.
  * Murata and Suzuki (2020) Tomoya Murata and Taiji Suzuki.  Gradient Descent in RKHS with Importance Labeling.  Technical report, 2020.  URL http://arxiv.org/abs/2006.10925.
  * Nemhauser et al. (1978) George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher.  An analysis of approximations for maximizing submodular set functions―I.  _Mathematical Programming_ , 14:265--294, 1978.
  * Nguyen and Smeulders (2004) Hieu T. Nguyen and Arnold Smeulders.  Active learning using pre-clustering.  In _International Conference on Machine Learning, ICML 2004_ , pages 623--630, 2004.  ISBN 1581138385.  doi: 10.1145/1015330.1015349.
  * Nguyen et al. (2013) Viet Cuong Nguyen, Wee Sun Lee, Nan Ye, Kian Ming A. Chai, and Hai Leong Chieu.  Active learning for probabilistic hypotheses using the maximum Gibbs error criterion.  In _Advances in Neural Information Processing Systems, NIPS 2013_ , 2013.
  * Nowak (2008) Robert Nowak.  Generalized binary search.  In _46th Annual Allerton Conference on Communication, Control, and Computing_ , pages 568--574, 2008.  ISBN 9781424429264.  doi: 10.1109/ALLERTON.2008.4797609.
  * Nowak (2009) Robert Nowak.  Noisy generalized binary search.  In _Advances in Neural Information Processing Systems, NIPS 2009_ , pages 1366--1374, 2009.  ISBN 9781615679119.
  * Prechelt (2012) Lutz Prechelt.  _Early Stopping -- But When?_ , pages 53--67.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.  ISBN 978-3-642-35289-8.  doi: 10.1007/978-3-642-35289-8˙5.  URL https://doi.org/10.1007/978-3-642-35289-8_5.
  * Ramirez-Loaiza et al. (2017) Maria E Ramirez-Loaiza, Manali Sharma, Geet Kumar, and Mustafa Bilgic.  Active learning: an empirical study of common baselines.  _Data Mining and Knowledge Discovery_ , 31(2):287--313, 2017.  ISSN 1573756X.  doi: 10.1007/s10618-016-0469-7.
  * Raskutti et al. (2014) Garvesh Raskutti, Martin J Wainwright, and Bin Yu.  Early Stopping and Non-parametric Regression: An Optimal Data-dependent Stopping Rule.  Technical report, 2014.
  * Ravi and Larochelle (2018) Sachin Ravi and Hugo Larochelle.  Meta-learning for batch mode active learning.  In _International Conference on Learning Representations, ICLR 2018_ , 2018.
  * Rosasco and Villa (2015) Lorenzo Rosasco and Silvia Villa.  Learning with incremental iterative regularization.  In _Advances in Neural Information Processing Systems, NIPS 2015_ , pages 1630--1638, 2015.
  * Schohn and Cohn (2000) Greg Schohn and David Cohn.  Less is More: Active Learning with Support Vector Machines.  In _International Conference on Machine Learning, ICML2000_ , pages 839--846, 2000.
  * Sener and Savarese (2018) Ozan Sener and Silvio Savarese.  Active learning for convolutional neural networks: A core-set approach.  In _International Conference on Learning Representations, ICLR 2018_ , 2018.
  * Settles (2010) Burr Settles.  Active Learning Literature Survey.  _Machine Learning_ , 15(2):201--221, 2010.  ISSN 00483931.  doi: 10.1.1.167.4245.
  * Settles and Craven (2008) Burr Settles and Mark Craven.  An analysis of active learning strategies for sequence labeling tasks.  In _Conference on Empirical Methods in Natural Language Processing, EMNLP 2008_ , pages 1070--1079, 2008.  doi: 10.3115/1613715.1613855.
  * Seung et al. (1992) H S Seung, M Opper, and H Sompolinsky.  Query by committee.  In _Annual ACM Workshop on Computational Learning Theory, COLT 1992_ , pages 287--294, 1992.  ISBN 089791497X.  doi: 10.1145/130385.130417.
  * Shanmugam et al. (2015) Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath.  Learning causal graphs with small interventions.  In _Advances in Neural Information Processing Systems, NIPS 2015_ , pages 3195--3203, 2015.
  * Sinha et al. (2019) Samrath Sinha, Sayna Ebrahimi, and Trevor Darrell.  Variational adversarial active learning.  In _IEEE International Conference on Computer Vision, ICCV 2019_ , pages 5971--5980, 2019.  ISBN 9781728148038.  doi: 10.1109/ICCV.2019.00607.  URL https://github.com/.
  * Sundin et al. (2019) Iiris Sundin, Peter Schulam, Eero Siivola, Aki Vehtari, Suchi Saria, and Samuel Kaski.  Active learning for decision-making from imbalanced observational data.  In _International Conference on Machine Learning, ICML 2019_ , pages 10578--10587, 2019.  ISBN 9781510886988.
  * Sung et al. (1994) Kay Sung, , and Partha Niyogi.  Active Learning for Function Approximation.  In _Advances in Neural Information Processing Systems, NIPS 1994_ , volume 7, pages 593--600, 1994.
  * Terayama et al. (2019) Kei Terayama, Ryo Tamura, Yoshitaro Nose, Hidenori Hiramatsu, Hideo Hosono, Yasushi Okuno, and Koji Tsuda.  Efficient construction method for phase diagrams using uncertainty sampling.  _Physical Review Materials_ , 3(3):33802, 2019\.  ISSN 24759953.  doi: 10.1103/PhysRevMaterials.3.033802.
  * Tian et al. (2020) Yuan Tian, Ruihao Yuan, Dezhen Xue, Yumei Zhou, Xiangdong Ding, Jun Sun, and Turab Lookman.  Role of uncertainty estimation in accelerating materials development via active learning.  _Journal of Applied Physics_ , 128(1):014103, 2020\.  ISSN 0021-8979.  doi: 10.1063/5.0012405.  URL http://aip.scitation.org/doi/10.1063/5.0012405.
  * Tong and Koller (2001) Simon Tong and Daphne Koller.  Active learning for structure in Bayesian networks.  In _International Joint Conference on Artificial Intelligence, IJCAI 2001_ , pages 863--869, 2001.
  * Tong and Koller (2002) Simon Tong and Daphne Koller.  Support vector machine active learning with applications to text classification.  _Support vector machine active learning with applications to text classification_ , 2(1):45--66, 2002.  ISSN 1533-7928.  doi: 10.1162/153244302760185243.
  * Ueno et al. (2018) Tetsuro Ueno, Hideitsu Hino, Ai Hashimoto, Yasuo Takeichi, Yasuhiro Sawada, and Kanta Ono.  Adaptive design of an X-ray magnetic circular dichroism spectroscopy experiment with Gaussian process modeling.  _npj Computational Materials_ , 4(1), 2018.  ISSN 20573960.  doi: 10.1038/s41524-017-0057-4.
  * Vlachos (2008) Andreas Vlachos.  A stopping criterion for active learning.  _Computer Speech and Language_ , 22(3):295--312, 2008.  ISSN 08852308.  doi: 10.1016/j.csl.2007.12.001.
  * Wang and Ye (2015) Zheng Wang and Jieping Ye.  Querying discriminative and representative samples for batch mode active learning.  _ACM Transactions on Knowledge Discovery from Data_ , 9(3):17, 2015.  ISSN 1556472X.  doi: 10.1145/2700408.  URL http://dx.doi.org/10.1145/2700408.
  * Wassermann et al. (2019) Sarah Wassermann, Thibaut Cuvelier, and Pedro Casas.  RAL â Improving stream-based active learning by reinforcement learning.  In _European Conference on Machine Learning and Principles and Practiceof Knowledge Discovery in Database, Workshop on Iterative Adaptive Learning_ , volume 2444, pages 32--47, 2019.  URL https://hal.archives-ouvertes.fr/hal-02265426.
  * Woodward and Finn (2017) Mark Woodward and Chelsea Finn.  Active One-shot Learning.  Technical report, 2017.  URL http://arxiv.org/abs/1702.06559.
  * Xu et al. (2003) Zhao Xu, Kai Yu, Volker Tresp, Xiaowei Xu, and Jizhi Wang.  Representative sampling for text classification using support vector machines.  In _European Conference on Information Retrieval Research_ , volume 2633, pages 393--407, 2003.  ISBN 3540012745.  doi: 10.1007/3-540-36618-0˙28.  URL https://www.researchgate.net/publication/225138938.
  * Yan et al. (2018) Songbai Yan, Kamalika Chaudhuri, and Tara Javidi.  Active Learning with Logged Data.  Technical report, 2018.
  * Yan et al. (2019) Songbai Yan, Kamalika Chaudhuri, and Tara Javidi.  The Label Complexity of Active Learning from Observational Data.  In _Advances in Neural Information Processing Systems, NeurIPS 2019_ , 2019.
  * Yang et al. (2015) Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G. Hauptmann.  Multi-Class Active Learning by Uncertainty Sampling with Diversity Maximization.  _International Journal of Computer Vision_ , 113(2):113--127, 2015.  ISSN 15731405.  doi: 10.1007/s11263-014-0781-x.
  * Yao et al. (2007) Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto.  On early stopping in gradient descent learning.  _Constructive Approximation_ , 26(2):289--315, 2007.  ISSN 01764276.  doi: 10.1007/s00365-006-0663-2.
  * Zhu et al. (2008) Jingbo Zhu, Huizhen Wang, and Eduard Hovy.  Multi-criteria-based strategy to stop active learning for data annotation.  In _International Conference on Computational Linguistics, Coling 2008_ , volume 1, pages 1129--1136, 2008.  ISBN 9781905593446.  doi: 10.3115/1599081.1599223.