Efficient Active Learning for Gaussian Process Classification by Error Reduction
Authors: Guang Zhao
Edward Dougherty
Byung-Jun Yoon
Francis Alexander
Xiaoning Qian
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian Active Learning
Gaussian Process Classification
Expected Error Reduction
Query Synthesis

Abstract: Active learning sequentially selects the best instance for labeling by optimizing an acquisition function to enhance data/label efficiency. The selection can be either from a discrete instance set (pool-based scenario) or a continuous instance space (query synthesis scenario). In this work, we study both active learning scenarios for Gaussian Process Classification (GPC). The existing active learning strategies that  maximize the Estimated Error Reduction (EER) aim at reducing the classification error after training with the new acquired instance in a one-step-look-ahead manner. The computation of EER-based acquisition functions is typically prohibitive as it requires retraining the GPC with every new query. Moreover, as the EER is not smooth, it can not be combined with gradient-based optimization techniques to efficiently explore the continuous instance space for query synthesis. To overcome these critical limitations, we develop computationally efficient algorithms for EER-based active learning with GPC. We derive the joint predictive distribution of label pairs as a one-dimensional integral, as a result of which the computation of the  acquisition function avoids retraining the GPC for each query, remarkably reducing the computational overhead. We also derive the gradient chain rule to efficiently calculate the gradient of the acquisition function, which leads to the first query synthesis active learning algorithm implementing EER-based strategies. Our experiments clearly demonstrate the computational efficiency of the proposed algorithms. We also benchmark our algorithms on both synthetic and real-world datasets, which show superior performance in terms of sampling efficiency compared to the existing state-of-the-art algorithms. 

Efficient Active Learning for Gaussian Process Classification by Error Reduction
Guang Zhao', Edward R. Dougherty', Byung-Jun Yoon Francis Alexander & Xiaoning Qian 1,2.3 guangzhao@t edu, falexander@bnl, (edward, bjyoon, xqian tamu.edu edu
"Department of Electrical & Computer Engineering, Department of Computer Science & Engineering,
*Computational Science Initiative, Brookhaven National Laborator Upton, NY 11973, USA
Texas A&M University
College Station, TX 77843, USA
Abstract
Active learning sequentially selects the best instance for labeling by optimizing an acquisition function to enhance data/label efficiency. The selection can be either from a discrete instance set (pool-based scenario) or continuous instance this work, we study both active learning scenarios for Gaussian Process Classification (GPC). The existing active learning strategics that maximize the Estimated Error Reduction (EER) aim at reducing the classification error after training with the new acquired instance in step-look-abes -hccd manner. The computation of EER- based acquisition functions query.
space (query synthesis scenario).
is typically prohibitive Moreover, as the EER not smooth, can not be combined with gradient based optimization techniques to efficiently explore the continuous instance space for query synthesís. To overcome these critical limitations, we develop computationally efficient algorithms for -EERd active learning with GPC. We derive the joint predictive distribution of label pairs as a one-dimensional integral, as a result of which the computation of the acquisition function avoids retraining the GPC for each query. remarkably reducing the computational overhead. We also derive the gradient chain rule efficiently calculate the gradient of the acquisition function, which leads to the first query synthesis active learning algorithm implementing EER-based strategies. Our experiments clearly demonstrate the computational efficiency of the proposed algorithms. We also benchmark our algorithms on both synthetic and real-world datasets, which show superior performance in terms of sampling efficiency compared to the existing state-of-the-an algorithms.
it requires retraining the GPC with every
Introduction
Compared to traditional passive learning with randomly sampled training instances, active learning aims "optimally" querying instances for labeling to achieve label efficiency when training machine learning models, especially when labeling is difficult or costly. There are two fundamental scenarios of active learning discussed in the literature: query synthesis and pool-based sampling (14). In query synthesis, the leaner can request labels for any instance generated from continuous feature space while pool-based sampling selects the instance from finite set. Query synthesis more challenging due to the infinite search space and inherent higher label uncertainty. Recent research on query synthesis with deep generative models has shown promising potential [18 [I]. However, in
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

n- 18
C2
32
-44
Figure 1: Phase diagram identification by active learning with Gaussian Process Classification (GPC).
many science and engineering applications, acquiring the label for even one instance is prohibitively resource-demanding and therefore active learning with deep models may not be practical.
For example, one of critical materials science research questions is to identify phase transition diagrams, where the phase transition response surface can be complex [8] Identifying phase transitions can be formulated as finding the optimal classification boundaries between different phases in the enormous materials design space. However, precisely knowing the phase of each design with the corresponding input features requires costly and time-consuming materials synthesis and profiling experiments or running complex simulation models. Furthermore, there may exist significant uncertainty in acquired phase labels due to technical limitations. Hence, active learning for optimal Bayesian classifiers is natural solution to help identify the phase diagram with few as possible synthesized or simulated materials under such uncertainty and complexity. Gaussian Process Classification (GPC) as a popular and powerful Bayesian classifier with the flexibility of adopting different kernels 15). is suitable for solving this problem with appropriate active learning strategies. Fig D shows example of phase identification in two-dimensional design space by active learning with GPC (Details in the Appendix). In the figure, the black solid line indicates the phase transition response surface, the crosses and dots indicate the queries of different phases, and the colorbar indicates the predictive distribution of GPC. From the figure we can see, the predictive distribution identifies the phase transition boundary with few samples guided by active learning using GPC surrogate models, which has significant cost and time savings compared to the traditional trial-and-errol phase diagram identification paradigm in the current materials science practice.
Many active learning strategies have been proposed for GPC. For example. Bayesian Active Learning by Disagreement (BALD) selects the instance with the maximum mutual information between the observation and the derived uncertain model [5]. There also have been strategies targeting at reducing classification error directly or indirectly. Estimated Error Reduction (EER) strategies optimize for the eтror reduction after training with the new queries [13 6). We note here that based active learning has been studied for both Gaussian Process Regression (GPR) and GPC [13 6
For GPR, the regression eтror can be represented by the posterior predictive variance with the analytical expression and the acquisition function is easy to calculate for efficient active learning. contrast, for GPC, there is no analytical expression for the posterior predictive. The model updates need approximate inference, such Expectation Propagation (EP), an algorithm iteratively approximating the GPC posterior 77. Moreover, the classification етrоr computation requires the new query labels; so the caleulation of the corresponding EER- -baed acquisition function requires incrementally retraining the model for each possible query label to calculate the expected future error as the utility to guide
active learning. The complexity of training GPC with EP approximation is ( where n is the number of observed data. This has been the main hurdle to develop active learning for GPC models.
To reduce the calculation cost EER, the paper (6] proposed to use a non-iterative but less accurate method Assumed Density Filtering (ADF) approximating the new posterior when calculating the acquisition functions. The paper proposed novel approximated error reduction (AER) criterion, in which the error reduction of a candidate is estimated based on the impact over its nearby instances. The approximated estimation avoids re-inferring the labels of massive instances. These methods are relatively efficient in computation. But besides EP approximation, they need additional approxima- tions in calculating acquisition functions so the acquisition functions are not precisely calculated, which may degrade the desired data efficiency.
2

---

In this paper, within the BER-based active learning framework for GPC, we develop computationally efficient algorithms to compute EER to guide both query synthesis and pool-based active learning. In particular, we consider EER as the reduction of the Mean Objective Cost of Uncertainty (MOCU) [16] since the learning objective of GPC, in particular for identifying phase diagram, is to reduce the classification error. By deriving the joint distribution of queries as one -iedimensio integral, we avoid retraining the GPC for each query when calculating the EER/MOCU- We further leverage smooth approximation of MOCU, Soft MOCU (SMOCU) [17), to enable efficient gradient computation of the SMOCU reduction by deriving the corresponding chain rule for efficient query synthesis with GPC. To the best of our knowledge, this is the first algorithm for query synthesis active learning based on EER strategies. We show in our experiments that our algorithms accelerate the computation of the acquisition functions. Compared with other existing algorithms, we demonstrate consistent data efficiency of our algorithms with both synthetic and real-world datasets.
acquisition function.
2
Problem Setting and Background
2.1 Gaussian Process Classification (GPC)
Consider binary classification problem with the instance space X' and binary label set y - {0, 1). we aim to train a classifier &b X + y to predict labels for unobserved instances th [{. x, E X. The Gaussian Process classification (GPC) framework connects the instance and the label by a latent function f. which is a random process depending on æ. Assume that f follows a Gaussian Process (GP) prior f GP(m(-), -)), where u(()) is a mean function and :(: is covariance kernel function 99. GP is popular and powerful model for both regression and classification. A good property of GP is that given any finite number of instances 2;, the joint distribution of fax; is still Gaussian. For classification problems, given f. the label y takes a Bernoulli distribution with probability p(y = 1 1 f) = (f(()), where is the Gaussian cumulative distribution function.
Given a sequence of observations D = {x, Y) with X = {0r, 22,..... .n and Y {y1,
}, the class labels are conditionally independent given the latent function. Therefore, the joint likelihood can be factorized as: p( p(Y | f) = II p(gn (z,, f). Since the likelihood proba- bility is non- Con-aausiian, the posterior π [f]x, Y) x (((())p(())) [f,, X) can not be computed analytically and approximation are often adopted. The Expectation Propagation (EP) algorithm approximates o (f|X, Y) with Gaussian approximation q(flx, Y) = N(((() :)) by iteratively moment matching marginal posteriors (9.
With the approximated posterior, the marginal distribution of f. = f(.) is still Gaussian. De- note the mean and variance as jl, and o.. respectively, then there is closed-form expression for p(y. I.,, X, Y) as:
p(y. - 11x,,,,,,,,,)). = (()))
14.
VT
VT+... o..
Given the predictive probability, we assume the prediction of the instance is the most probable label arg max,, p(y. XX, Y. x.). which known as the Optimal Bayesian Classifier (OBC) I
2.2 Bayesian Active Learning Based on Estimated Error Reduction (EER)
In the Bayesian active learning procedure, we consider a general case that the label given by the annotator is not deterministic, but the label follows an unknown distribution instead. Given the GPC model and observations, active learning sequentially chooses a query from a discrete instance set or continuous instance space, to efficiently improve the prediction performance of GPC. In each iteration, the query is chosen by optimizing an acquisition function. The acquisition function reflects the anticipated benefit of the queries, and it usually depends on the model posterior (f] Y). After observing the new data (I., the model is updated by Bayes' rule to get the posterior (J|X, Y, y.). In the following content, we'll Il discuss the iteration of active learning after observing training data (X, Y), for the sake of clarity, we omit X, Y from the notations of posterior and posterior predictive distributions as x (s) and p(y]z)).
Assume the distribution of instances over X' is vs ~ p(æ.), denote the optimal Bayesian classi- fier (OBC) (.). Based on GPC, the expected classification error of the OBC is:
Ez, (1 p(u+ aa(n) (2x,) [.,)} (x.)) E.. {1 max p(v= [x.)).
(2)
8a
3

---

In the GPC setting, if the latent function is known, we can accordingly label each instance with the most probable label as ( arg max, p(y x. f), where x denotes the optimal classifier. The classification error of y is Ex, {1 max, ply f)}. Due to the model uncertainty, the classification error of OBC should be larger than that of the optimal classifier. The Mean Objective Cost of Uncertainty (MOCU) measures the classification error increase due to the model uncertainty [16.. It is defined as the OBC classification error minus the expected classification error of the optimal classifier under model uncertainty:
M(*(f)) = Ex, {1 max p(ys (B maxp f)l}. N.
As MOCU captures the direct influence of the model uncertainty on the classification error, we can take the MOCU reduction in one sneessteploook-bbile setting as the acquisition function:
U (ax;; a (f)) -M((f)) - Ey. lr. [M( x y+))]
(4)
The second term is the MOCU after observing (æ.,, My), and averages over p(y- (x.) since we do not know the label of yy before observation. It is easy to verify that in (4), the maxy, p(ya 2 f) terms in Mfx(f)) and MMa[ffxx y are cancelled and the acquisition function can be proved to be equivalent to the Expected Error Reduction (EER) of OBC [7:
(a.)) En, {1 max ply xt x.)) Ey. (B [1 - max pe,, &., 9,
9o = BE, (Ey. [max p (2,, x, v)] max p(y.(=,))
(5)
Although MOCU reduction or EER is optimal for single queries, with noisy observation labels, it may get stuck before converging to the optimal classifier as discussed in [16]. To address this issue, the paper (17) proposed smooth concave approximation of MOCU, called Soft-MOCU (SMOCU), which replaces the max,, p(ys (x.) term in (3) with LogSumExp term:
(x)x(f)) = Em, (1 LogSumExx((k p(y|=.)) - Em()) (E,, max p(y, f)1).
(6)
k
where & is parameter controlling the approximation to MOCU. The resulting acquisition function based on the SMOCU reduction can be defined as:
S (x.) = Ez, (Ey m. LogSumExp(A (k: p(ys (x,, xx,, y.))] LogSumExp(k: p(uslx,))) (7)
k
which guarantees the convergence to the optimal classifier 17 The resulting acquisition function
smooth function of p(y, x., æ. y) and has no maximization operators. We will leverage this smooth acquisition function to derive the first efficient gradient- query synthesis active learning algorithm for GPC.
3 Efficient Active Learning for GPC
In this section, we present our ZEERbbssed active learning algorithms for GPC based on the acquisition functions defined by the MOCU and SMOCU reduction. At each iteration, with the updated GPC given previous observations, the acquisition function (5) or 7 can be optimized to guide the selection of the next query for active learning. We first present straightforward algorithm for both the discrete instance set (pool-based sampling) and continuous instance space (query synthesis) scenarios, where the acquisition function is optimized by random optimization. Random optimization first collects random sample set X C. X of size M1. calculates the acquisition function for each sample in the set and then takes the instance with the maximum acquisition function value the query.
To calculate (5) or (7) the integral over space is not analytical. Hence we need calculate the integral by Monte Carlo sampling with M2 samples of I, E X. Define (x,; and (zx; x.)) such that UM (x.))
Ez, (xx;; (xx);==))) Let g( x.) denote either g (xx;; ) or g (xxx ). For each x., the calculation of g( gx x.) requires deriving the probability distribution of p(ys (a..) and p(ya (x, v. y.), Vy. E ). Here, p(ys|ar (ax.) can be calculated directly from (1) while updating p(,./a,,, F. v.) needs incremental training of GPC with observations (X,Y Y.a.. .. y.) based on the EP approximation, and then calculating (1). The whole
Ez, (xx xx)) and US
procedure of optimizing the acquisition function at the n-th iteration need to retrain GPC for each

---

possible pair (Ix, v-), therefore, the EP approximation needs to be performed 2 x M1 times. The whole procedure is illustrated as the pseudocode Algorithm in the Appendix.
There are three issues of the acquisition function calculation in the straight forward algorithm. First, need large number of samples M2 have reliable estimation of the integral in (5) or (7) Second, the calculation of p(ya 2., y-) requires incremental retraining of the GPC model for each pair of (x+: )/ with computational complexity ((M)n Third, even though U ) is differentiable function of p(yal Ø., æ. W+), in the algorithm we actually use the EP approximation (.. y/-) calculate U (x.). ). and it is impossible to calculate the gradient Vg(ff z.. y=) during the EP procedure.
GER-based active learning algorithms to address these three presented challenges: 1) By importance sampling leveraging inhere GPC assumptions, we reduce the required number of samples for estimating acquisition functions; 2) We compute p(ys|as. :. y-) by deriving ana- lytic solution to marginalize the joint distribution p(us, Ye xt, æ.,) from the approximated posterior q(][,, Y). which avoids the retraining with EP approximation: 3) More critically, we derive the first gradient-based query synthesis algorithm when using the SMOCU-based acquisition function by deriving the gradient Vq(f(x,, v/) for efficient active learning.
We develop
3.1 Importance Sampling
Regarding the issue in requiring the high sampling number of I, for reliable estimation of the acquisition function, we notice that most of the kernels applied in GPC assume that the observed data only have influence on neighhoring regions. Hence, we only need to account for the samples near æ. to estimate its influence on the classification error, thereafter the acquisition function for each new query. More specifically, we can use importance sampling to reduce the required sampling number. Reformulate the expectation (x.) = Ee, [9(2;;; æ.)] over an assistant distribution p(x.; x.) as: Uxx)) = E.,.aiim.......... [p(x; (gllz..g.ge)) (g(;); x..) p(z;: x.)).
The variance of the expectation minimized when p(z,; x.) is proportional to p(æ.)g(<s x.). But this requires knowledge of the value of (zx)), which is the acquisition function that we try to estimate. In practice, we can choose p(x,;; x 2. x. )p(x)) instead, as k(æ,, x.) reflects the non-zero region of g( x.): k(x,, x.) 0 means (2., and (x., y.) are independent, thus p(y, E., x. y.) = p(y, (x.)) and g( x.) Ro O. For example, if p(xx)) is uniformly distributed within finite region, k( A(Z,, x.) is a square exponential kernel, then p(a;;; xx.) can be chosen truncated Gaussian distribution. Note that importance sampling and random optimization is only suitable for continuous instance space, or discrete set with large cardinality, For small instance set, can traverse all the elements for calculating the expectation and optimizing the acquisition function.
3.2 Joint Distribution Calculation
To avoid the retraining of GPC for each (x., we can calculate the posterior predictive by p(ya|at (2., w., y.) p(ys, wx, a.)/p(y, (x.). which requires computing the joint distribution of p(ys, ys lx, ). We remind the reader all the probabilities are conditioned on {X, Y} and we omit them for the seek of brevity. Denote f. = f(x,) and fa = f(x.). Now we show how to simplify the calculation of p(ye. (x., J. In the Gaussian approximation of the posterior q(ff.X. Y), the joint distribution of fs: still Gaussian. Since ys and y. are conditionally independent given fs and f., the joint distribution can be expressed as:
// fa Dox) dff..
ply. 1, y, = 1| x.))
(8)
where Pa. and Σg, are the marginal mean and covariance matrix of fa and f.. This integral can be simplified as a one-dimensional integral. Denote p.a (( Ps and Σ.. Oss Tex μr
Tex oue
We can decompose the joint Gaussian distribution as the marginal distribution of Sa times the conditional distribution of fo given far ie. &(fer fo Hon, E.e) o(f. 6(falMe, (f Ji, (fa), ō..).
5

---

where (f.) = 2r + (fo 20)000/
30/0000000 /... and o.. = J.z -02//Oss. Then, 8
can be transformed as:
//
ply. = 1, Vv = 1| x.) =
falMss Ege )df.dffff..
= |f @ (f.),
/ Φ( (Ja) (fffa)
(9)
The last line is based the integral equation introduced in [9] The above equation (9) calculates the joint distribution with the 1-d integral in constant time. With the joint distribution p(ys = easily obtain the joint distribution of ys. V. with other label pairs, and
y. 1 ).,,, finally we can obtain the posterior predictive p(y, 2,. 2., yy. without retraining the GPC with EP approximation. Based on this solution with importance sampling, we can develop efficient algorithms estimating MOCU/SMOCU reduction. Combining with Random Optimization, we develop the active learning algorithm with MOCU reduction named Retrainini MOCU reduction with Random Optimization INRMOOC-RO)) and similarly for SMOCU reduction NR-SM AR-SMOCU-RO The pseudocode of MOCU-RO can be found in the Appendix (Algorithm 2).
3.3 Gradient Calculation
With the introduced marginalization strategy and importance sampling, significantly improve the computational efficiency for pool-based active learning with GPC. However, in the query synthesis problems, we would like to optimize the acquisition functions with gradient-basee algorithms. Usually the acquisition functions are multi-modal in the feature space, so the common practice is to perform random optimization first, and then take the optimal point as the initial point perform the gradient- based algorithms [4]
Here consider the gradient calculation of the acquisition function based the SMOCU reduction (US(x,) for query synthesis active learning as U (x.) is a smooth function whose gradients exist everywhere. For Gaussian Process, the gradients of its mean and covariance functions have closed- form expressions of the gradients of its adopted kernel function. Here we assume that given the EP approximation q( Y) and any pair of points (ar,, ). the gradients Vpe, Vo.. and Va with respect to x, are known. Calculation of these gradients is detailed in Appendix E. With this assumption, we can use the chain rule finally express the gradients U (x.) in the form of Vp.. Vo,, and Va
In 7 the second term is unrelated I.,, the gradient of the SMOCU reduction is:
(U)()=) = Ez, Vgg (x,, x.)) = VE p(y x.) LogSumExp(k p(ys ( 2 y+)1}
V.
Σ Vp(y,/xx)) Ex,, LogSumExpl is ply, x.. x x., y-)1 N-
Σ p(v.kw.) Ez, (V LogSumExp/H /k: p(y, ( V., (.,
(10)
In the first term, Vp(y- xx)) can be calculated with V and Vo.. based on (I.. For the second term, we can use the chain rule to compute VLogSumExple [k p(ya (x,, x. y-)] = 91 92, where:
91 HLoSSumExp l: p(ys [x,, F., y+)
J2 Fply,/x,, x.. yz).
(11)
0p(Ue (2,, x., M/))
Since p(ya x., x.,, y.) = p(yer /1 only need to calculate Vp(us, y/ |2,,, xx.) based
[., x. 3/v(y (x.) and we have calculated Vp(y, (x.), now we
Vply. = 1, 1, y 1/ xx, = / ((f.))(felH (La(fa)
Vo.. +1 )df
-f f (all)) Vo.o
(Ts) V(
Von +I ydfs, (12)

---

which is again a 1-d integral. The gradient of V R.(Sa) connected the calculation of V ja. (fa) and Vō..:
can be again calculated by chain rule, and
vo.++
Me Vo
2
Vja+(f)) Vu,
Vo Vo
(13)
Jss
3ss
Therefore, 4
(=(f=) is linear function of fa. and we can use numerical integral methods to calculate 12 The query synthesis algorithm with the integral computation is summarized in the
vo.++I
pseudocode:
NR-SMOCU with Stochastic Gradient Descent (NR-SMOCU-SGD),
In summary, to reduce the number of samples æ, for reliable estimation of acquisition functions, our algorithm utilizes an importance sampling with an assistant distribution chosen according to the kernel function. By calculating the posterior predictive directly from the joint distribution, the algorithm avoids retraining GPC with EP approximation. The introduction of the joint distribution also enables the efficient calculation of the gradient of the smooth acquisition function, with which we develop an efficient active learning algorithm for query synthesis.
NR-SMOCU-SGD: n-th iteration
1: function GR GRADIENTOPT((x))) ((X XI, Y))
2: Obtain initial point æ, from RANDOMOPTO(()) Y))
3: while not converge do
4: Sample M2 samples of a. ~ p(xx;: Calculate p(y. (x.) and Vp(y- x.)) by
5:
6:
for each x, do
7:
for y in {0, 1] do Calculate p(ye, yr v.). end for Calculate Vgg( end for
8:
Vp(ys, yn Ie xx)) and plys (x,) by
9 12
9:
10:
(x. x.) by
10
12
11:
12:
(US(2.) = 1 Ex, ((x,) V (x, (/)aaaa))
Me
13:
Update with VU (x.) end while
14:
15:
return v.
16:
end function
4 Experiments
In this section we demonstrate the efficiency of our active learning algorithms combined with either random optimization (NR-MOCU-RO, NR-SMOCU-RO) Adagrad (NR-SMOCU-SGD) in the following sets of experiments. In the first set of experiments, we analyze and benchmark the running time of our algorithm by comparing to the naive computation of the MOCU/SMOCU reduction. Then we benchmark our algorithms with other active learning algorithms for both query synthesis on synthetic benchmark datasets, and pool-based active learning on real-world datasets. The competing algorithms include random sampling, Maximum Entropy Search (MES) 12]. Bayesian Active Learning by Disagreement (BALD) [5]; several MOCU-based active learning algorithms are also included to better show the accuracy and computation efficiency of our proposed algorithms, including the original MOCU and SMOCU
algorithms as described in the beginning of Section 3. In addition, an ADF-MOCU algorithm is also included for comparison, which uses Assumed Density Filtering (ADF) to retrain the GPC (6) and importance sampling (IS) to calculate the expectation. In our experiments,
use GP prior for ʃ with the squared-exponentis kernels k(x, x') >2xxp( | æ - x' /122, where {y, |} are model hyperparameters. The label probability modeled with the probit function p( y) x. f) 4 (f(()))) The code for our experiments is made available at hhttt:::: //github. com/ www//ianm..aaeeoooo aabaaaaaaaaaaaaaaaaaaaaaaaaaaaaa NR_ SMOCRSSSSSUSSCCER SRROCCU_SDDGGPPPP
4.1 Estimation Accuracy And Running Time Comparison
We first evaluate the effect of using the joint distribution integral in calculating the acquisition functions. We compare the estimation of (!) (yal E. xr y+) through the joint distribution Integral
(1)
7

---

Table 1: Running time (in seconds) and estimation accuracy.
Algorithm
n 10
n= 100
=500
1000
naive
0.125
0.675
64.2
846
Time (s)
IS
0.126
0.674
64.2
848
IS+JDI
0.568
0.591
0.598
0.643
naive
0.149
0.207
0.195
0.27
Relative Error
IS
0.013
0.029
0.027
0.026
IS+JDI
0.013
0.032
0.027
0.022
( with yl (ys [x,, x2 y/) estimated by Retraining GPC with EP approximation. For this set of experiments, generate the initial data points using latent function f sampled from the GP prior. The instance space X' = [-4, 4]. and the hyperparameters 7² = 0.5, 1 = 1. We initially sample 100 data points to train GPC, then we compare the values g( = LogSumExpl (:: -p"") (ys (2,, x, y)) and g = LogSumExp p( (y,, xz, æ. y))/k, since these are related to the calculation of the SMOCU reduction. With 1000 pairs of (æ., v.) randomly sampled from X, we calculate the relative error as (g(*) - 1/ The average relative error is 1.8e-5 and the maximum relative error is 2.4e-3. We also compare the values g( maxy, ( (y.la., x, y) and g g( maxy, p! (yslaz (y,..,, Z, y), which is used to calculate the MOCU reduction. The average relative error is 1.3e-5 and the maximum relative error is 2.2e-3. These results validate that using (9) can provide accurate estimates of the acquisition functions.
Next, we compare the running time and accuracy of estimating acquisition functions by three algorithms: 1) a naive algorithm calculating p(y, [x5, Re,yo) v-) with GPC retraining (naive), 2) sampling a, by Importance Sampling and calculating p(y, (22, R., with GPC retraining (IS), 3) sampling v, by Importance Sampling and calculating p(y. [2,, L., yo) with the Joint Distribution Integral (IS+JDI). The algorithms are implemented in Python 3.7 on personal computer with Intel i5- 10400 2.9 GHz CPU and 16G RAM. We set the initial datasets of size n = 10, 100, 500 and 1000, respectively. Note that in all three algorithms, inferring the predictive distribution for each æ, also takes a considerable part of computations, especially when n is small, so we separate out the computation of the predictive distributions and directly compare the running time between retraining GPC (in the naive and IS algorithm) and calculating the joint distribution integral (in the IS+JDI algorithm). For all three competing algorithms, we sample 1000 æc,' s, and calculate (T. We benchmark them with a "ground truth" algorithm: calculating (x. by the naive algorithm with /eó x, samples. We perform this comparison for 100 a. ss. The average running time for a single æ. and relative error are shown in Table [ From the table, the relative error of the naive algorithm with 1000 samples is much larger than the other two as expected since the other two algorithms use importance sampling with smaller estimation variance. As n increase, the running time of both naive and IS algorithms increases fast since GPC training has a complexity of O(n²), ). while the running time of IS+JDI does not change much because the joint distribution integral is calculated in almost constant time. The results show that importance sampling does not impose much extra computation load in active learning, while it significantly increases the estimation accuracy. When is large, the joint distribution integral faster than retraining GPC with EP approximation.
4.2
Query Synthesis
We now benchmark our proposed algorithms with a challenging synthetic dataset checkerboard 4 x 4, similar the one tested in (5). which emulates the setup of phase diagram identification in materials science. Fig. 2a illustrates the classification boundaries. We perform all the competing active learning algorithms on this dataset. MES, BALD BALD.RO-MOCU, RO-SMOCU, ADF-MOCU, NR-MOCU-RO and NR-SMOCU-RO are all optimized by random optimization with Mi = 1000. In NR-SMOCU- SGD, we first perform random optimization with M₁ 800 and set the best point as the initial point for Adagrad so that WR-SMOCU-SGGI has similar running time compared with NR- ER-SMOCU-RO at their corresponding setups for fair comparison. Algorithm performance is measured in terms of the eтror regret defined as the OBC error at n-th iteration minus the optimal classifier error of the simulated ground truth. To show the influence of the observation error on the performance of different algorithms, we further assume that there is a constant flip error rate on the observing labels. We report the results with different error rates equal to 0 and 0.2. In the experiments, we initially draw 100 samples for labeling to estimate the hyperparameters {7, (]. Then we perform different
8

---

algorithms to collect new data. We repeat the procedure for 150 runs and plot the average error regret with standard deviations in Figs. 2p-c. for the flip error rate 0.2, the running time of each algorithm in each iteration is also shown in Fig. 21. The algorithm performance with the flip emor rate of 0. is shown in the Appendix.
We can observe from these figures that MES does not performs well, which is because MES tends query the points close to the decision boundary, while this problem has multiple intertwined boundaries and MES cannot differentiate different boundaries. OR-MOCU and OR-SMOCU perform worse than our proposed NR-MOCU-RO and UR-SMOCU-RO with respect to both computation and sample efficiency. That is because when compared with IS, the naive Monte Carlo used in DR-MOCU/OR-SMO -MOCU with GPC cannot accurately estimate the acquisition function values. On the other hand, the running time of OR-MOCU/OO SU/OO-SMMCUU SMOCU increases much faster than NR-MOCU- CONNR-SMOCU-RO since they retrain the model for every query samples. ADF-MOCU runs faster than our proposed algorithms, but it performs poorly as the ADF approximation is not accurate enough. We also observe that as the error rate increases, the difference between NR-MOCU and NR-SMOCU also increases, that is because as the error rate increases, MOCU reduction tends to ignore the long-term effect a query, leading to the degraded long-term performance, also discussed in [16.. Among these algorithms, NR-SMOCU-SGD performs better than other proposed algorithms by leveraging the gradient information in the optimization procedure.
4.3 Pool-Based Active Learning with Real- World Datasets
We also compare algorithms on the UCI datasets
pool-based active learning. NR-SMOCU-
SGD is not included as it is designed to search the continuous space. For each dataset, we split it into training and testing datasets. We take the training dataset as the sampling pool for active learning, initially we randomly choose two samples from each class for labelling, and use them to estimate the GPC hyperparameters. Then we apply the competing active learning algorithms to sequentially select the query from the training dataset and estimate the OBC eπror with the testing dataset after each iteration. Details of the tested UCI datasets are provided in the Appendix.
Running time 14
0.14
0.13
BALD
OR-SMOCU
MOCU
0.10
MR-MCCU-RO
NR. RR-SMOCUIRO
WR-SMOCU-SGD
Iteration number
(a) Checkerboard 4 x problem
(b) Flip error rate
120
2. x
2x
100
Eroo rogres
1.9
80-
18x10-1
BALD
MES
Runningg
00
BALD
MES
OR/MCU
1.7x10
ADF-NOCU
16x
NI--OCIU-RO
WR.SMOCU.RO
20
NR- NR-SMOCURRO
NI--MCCU-RO
WR-SMOCLL-SGD
20
20
Number lakeled
(c) Flip error rate 0.2
(d) Running time comparison for flip error rate = 0.2
Figure 2: Comparison of expected OBC error regret and running time on the 4 checkerboard problem.

---

0.16
0.300
0.275
rate
0.10
random
0.225
random
MES
BALD
0,200
ADF- MO-MM
ADF-MOCU
NR. SMOCUROO
0.150
NR-SMOCU-RO
10
15
20
10
20
Iteration
Iteration number
(a) WDBC
(b) Ionosphere
0.12
ente rate
0.22
0.09
0.20
MES
MES
BALD
0.06
BALDD
0.18
0.16
NR-MOCILRO
NR MR-MOCI-RO
NR-SMOCU-RO
NR-SMOCU-RO
Iteration number
Iteration number
(c) Vehicle
(d) Wine
Figure 3: Classification error rate comparison on UCI datasets.
We repeat the active learning procedures for 100 runs and plot the average OBC error with standard deviation values for each algorithm for performance comparison shown in Fig- 3 In pool-based active learning, the expectation in MOCU/SMOCU is calculated by averaging over the whole instance pool, and there no need for sampling, so the acquisition functions calculated OR-MOCU/OR SMOCU are almost the same as the ones calculated by performances of OR-MOCU/OR-SMEE We notice that ADF-MOCU also performs similar to NR- IR-MOCU-RO, though ADF provides rough approximations. That is because for the discrete space and small number of iterations, the small deviation due to approximation will not change the ranking of the instances in the pool. Overall, ADF-MOCU, NR-MOCU-RO and NR-SMOCU-RO are better than MES and BALD, which validates that MOCU-based algorithms achieve better sample, in particular label efficiency. Note that in the Vehicle and Wine datasets, MES performs closely to MOCU-based algorithms. When checking the converging GPC model, the classification boundary is relatively simple on these datasets with relatively -ow-dimensional feature space (d < 18). The WDBC and lonosphere data are in higher dimensions (d > 30), for which our proposed algorithms perform significantly better.
-OS-ROONNSSOO---ROOOOO Therefore, are not provided in the figure for the sake of conciseness.
5 Conclusions
We have proposed efficient EER-based active learning algorithms with GPC, which estimate the error reduction by querying instances based on the joint distribution of label pairs. We have derived the joint distribution as one-dimensional integral with constant computation cost and calculate the predictive posterior based on Together with importance sampling, the acquisition function can be estimated efficiently by the 1-d integral of the joint distribution without incrementally retraining GPC with EP approximation, which has computation complexity of O(n²). Without the need for EP approximation, we can further derive the chain rule to calculate the gradient of the SMOCU reduction, which provides us the first efficient gradient-based query synthesis active learning algorithm. Our experiments have demonstrated not only the accuracy and the running speed of our algorithms but also consistently better data/label efficiency compared with competing algorithms for both query synthesis and pool-based active learning.
10

---

Acknowledgments X. Qian was supported in part by the National Science Foundation (NSF) Awards 1553281, 1812641, 1835690, 1934904, and 2119103. B.-J. Yoon was supported in part by the NSF Award 1835690. The work of E. R. Dougherty and F. J. Alexander was supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Mathematical Multifaceted Integrated Capability Centers program under Award DE-SC0019303
References
[1] Lori A Dalton and Edward R Dougherty. Optimal classifiers with minimum expected error within Bayesian framework -aat Discrete and Gaussian models. Pattern Recognition, (6(5):131-11114, 2013.
[2] Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
[3] Weijie Fu, Meng Wang. Shijie Hao, and Xindong Wu. Scalable active learning by approximated error reduction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1396-1405, 2018.
[4] José Miguel Hernández-Lobato Matthew W Hoffman, and Zoubin Ghahramani. Predic- tive entropy search for efficient global optimization of black-box functions. arXiv preprint
1rXiv:1406.2541, 2014.
[5] Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:11 2011.
[6] Ashish Kapoor, Eric Horvitz, and Sumit Basu. Selective supervision: Guiding supervised learning with decision-theoretie active learning. In IJCAI, volume 7, pages 877-882, 2007.
[7] Malte Kuss, Carl Edward Rasmussen, and Ralf Herbrich. Assessing approximate inference for binary Gaussian process classification. Journal of machine learning research, 6(10), 2005.
[8] GE Poirier, WP Fitts, and JM White. Two-dimensional phase diagram of decanethiol on au (111). Langmuir, 17(4): 176-11887, 2001.
[9] Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pages 63-71. Springer, 2003.
[10] Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of error reduction. In Proceedings of the 18th International Conference on Machine Learning, ICML '01, pages 441-448, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
[11] Raphael Schumann and Ines Rehbein. Active learning via membership query synthesis for semi- supervised sentence classification. Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pages 472-481 2019.
[12] Paola Sebastiani and Henry P Wynn. Maximum entropy sampling and optimal Bayesian experimental design. Journal of the Royal Statistical Society: Series (Statistical Methodology), 62(1):145-157, 2000.
[13] Sambu Seo, Marko Wallat, Thore Graepel, and Klaus Obermayer. Gaussian process regression: Active data selection and test point rejection. In Mustererkemmang 2000, pages 27-34. Springer, 2000.
[14] Burr Settles, Active learning literature survey. Computer Science Technical Report 1648, University of Wisconsin-Madisene 2009.
[15] Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric Xing. Deep kernel learning. In Artificial intelligence and statistics, pages 370-378. PMLR, 2016.
[16] Guang Zhao, E Dougherty, Byung-Jun Yoon, F Alexander, and Xiaoning Qian. Uncertainty- aware active learning for optimal Bayesian classifier. In Proc. 9th Int. Conf. Learn. Repre- sent,(ICRR), pages 1-20, 2021.

---

[17] Guang Zhao. Edward Dougherty, Byung-Jun Yoon, Francis Alexander, and Xiaoning Qian. Bayesian active learning by soft mean objective cost of uncertainty. International Conference on Artificial Intelligence and Statistics, pages 3970-3978. PMLR, 2021.
[18] Jia-Jie Zhu and José Bento. Generative adversarial active learning. arXiv preprint 1rxi::100..07966, 2017.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/]]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Sections & 5. In addition to deriving label- efficient EER-based active learning for GPC with improved computational efficiency, we have derived the first gradient-based query synthesis algorithm for GPC.
(b) Did you describe the limitations of your work? [Yes] See the discussions in Sections
2 & 3. Active learning algorithms this work are derived for GPC using probit likelihood, which may have its inherent limitation in nigh-dimeensions
feature space.
(c) Did you discuss any potential negative societal impacts of your work? [No] The paper focuses on active learning algorithm development, which helps reduce the cost and time of machine learning and experimental design. We do not foresee immediate negative societal impact if not implemented for malicious machine learning applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The settings for deriving the joint distribution and gradient calculation based on basic calculus as presented in Section 3.
(b) Did you include complete proofs of all theoretical results? [Yes] The derivation of the joint distribution and gradient calculation detailed in Section
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL.)? [Yes] Included in the supplementary
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the corresponding descriptions in all the experiments in Section 4.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] For all the experimental results, we have shown the error bars with standard deviation values.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] All the experiments are implemented PC described in Section 4.1.
12

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] In Section 4, we have explicitly stated and cited the corresponding programming environment and competing algorithms for performance comparison.
(b) Did you mention the license of the assets? [No] The licenses of the assets can be viewed in their respective documentation.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We have included our code in the supplementary.
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "muOUtLT_EXO", "reviewer": "Reviewer_ii33", "summary": "This paper proposes to incorporate three ideas in order to improve the efficiency of the classification algorithm based on the Gaussian processes.\n(1) Importance sampling to reduce the number of sampling to reliably estimate the acquisition function.\n(2) Joint distribution calculation to avoid the retraining of GPC model with a candidate point of query.\n(3) Gradient calculation of the acquisition function to efficiently optimize in the query synthesis senario. \nThree experiments are conducted to evaluate the proposed approach.\ni) With synthetic data to evaluate the approximation error between p (which is estimated by joint distribution calculation) and p' (which is estimated by retraining i.e. naive algorithm).\nii) With synthetic \"checkerboard\" data to compare the proposed method with conventional approaches:\nrandom, MES and BALD. \niii) With UCI datasets to compare the proposed method with conventional approaches employed in ii) under the pool-based setting. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This study aims to improve the efficiency of EER-based methods in active learning for gaussian process classification. In this study, three approaches to improve efficiency are proposed, and the proposed method is composed of a combination of them. Among them, the joint distribution calculation to avoid retraining of Gaussian process classification (GCP) model and the gradient computation method to optimize the acquisition function by gradient method in query synthesis senario are considered to be important. The former makes it possible to estimate how much the error will decrease when new data is observed, without the need for computationally expensive retraining of the model. The latter is essential for efficient optimization of the acquisition function by the gradient method in query synthesis scenarios which corresponds to considering a non-countable infinite number of instances.\n\nQuality: This paper technically sounds. How much the proposed method improves the efficiency of GCP-based active learning has been partially evaluated by experiments. \nStill, there are a few questions (see Question). \n\nClarity: The paper is well organized. The explanations of motivation, existing methods and their problems, and the proposed approach are easy to understand.\n\nSignificance: While the proposed method provides a general way to improve the efficiency of active learning for GCP, it is especially effective for problems with high data acquisition costs, such as materials science, as mentioned in this paper.\n\nQuestions:\n\n- The experiments in section 4.1 show results up to n=100. Is the tendency for the proposed method to be robust (in terms of computation time) to increasing sample size similarly observed for further increases in n?\n\n- Why is MES the only acquisition function for existing methods in the experiments in sections 4.2 and 4.3? I think it is desirable that the comparisons with the more widely used EI and/or UCB (with the error function as the objective function) are conducted.\n\n- The query synthesis scenario considered in the experiment is quite low-dimensional problem (up to two-dimensional). Can we expect the same behavior in higher dimensional spaces?\n\n- SMOCU contains a parameter k that contributes to the approximation to MOCU, how do you adjust this?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention in the main text the limitation of the proposed method that it is difficult to apply it to high dimensional problems because it is based on GCP.\nI believe that there is no negative social impact from this research.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10h"}, "extra_text": {}}, {"review_id": "ZhTs4B0uzT", "reviewer": "Reviewer_C1HE", "summary": "this work derives an efficient way to compute the expected error reduction acquisition function for Gaussian Process classification active learning without requiring retraining under the well-known expectation propegation (EP) approximation for GP's. towards this end they use 1) importance sampling and 2) that the joint distribution of a training and test point of the Gaussian Process Classification model can be computed efficiently through a 1-dimensional integral. Their approach can also be used to derive gradients of the acquisition function which allows the approach to be used for query synthesis active learning. Furthermore, they empirically investigate the computational complexity and accuracy of their method, and benchmark the resulting active learning strategies. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After author response: all my concerns have been addressed, and in view of the new experimental results, I have further increased my score. \n\nI think this is a very well written, novel, and good paper and I really enjoyed reading it. It solves an important problem, making active learning with Gaussian Process classification much more feasible. My most pressing concern is that some obvious baselines [3,6,a] (for [a] see bottom) seem to be missing from the experiments. I would certainly raise my score further if these could be included in the experiments, irrespective of the actual outcome (e.g. if these baselines beat the proposed score, I would still vote for acceptance and further raise my score). Otherwise, there are some minor issues that should be further clarified regarding the experimental setup, and finally, since the paper's main contribution is computational efficiency I think this aspect should also be highlighted in the real world experiments. \n\nStrengths\n- well written, good quality\n- novel and simple approach\n- makes active learning with GP classification models computational feasible \n- decent experiments\n\nWeaknesses\n- misses some obvious baselines [3,6,a] (I hope this can be resolved through openreview)\n- computational efficiency should be reported in experiments for competing approaches\n- there is no Discussion section discussing the weaknesses of the work (!!!) I really expect this to be addressed also during the review process...!\nif the authors make a good effort to resolve these issues I would raise my score to 8 or 9.\n\nNote: I didn't go through the mathematical derivation in detail, but it seems correct to me. \n\nmost important issues\n\n1) Why are [3] and [6] not included in the benchmark? As they seem to be the most closely related to the current work. \n\n2) I would really appreciate it if you would include a Gaussian Process regression model and it's corresponding acquisition strategy. My suspicion is that it could be very competitive with GP classification active learning; even though of course the model is misspecified. For example [a] (see at bottom) uses GP regression for active learning for a classification task. Their strategy is closely related to expected error reduction. \n\nNote that; if the above baselines would be included I would for sure raise my score; irrespective of the outcome of the experiments. More comparisons only would improve the value of the work in my eyes, even if your strategy is outperformed by these other strategies. I think that the current work is so elegant and a nice solution to this problem, that even if the performance is not always competitive , it should definitely be accepted. \n\n3) line 289: here you say that SMOCU performs better because MOCU has problems with long term effects. However, in Figure 2d I clearly see that SMOCU is performing worse than MOCU; but SMOCU-SGD _does_ perform better. Do you have any idea what is going on here? I think a remark is in order, the interpretation as I read it now is incorrect? Note that (Line 294) my intuition is that SGD may also have an advantage because it can more precisely pick locations of points than the other algorithms which are restricted to the finite pool. But it doesn't really \n\n4) line 247: the relative absolute error seems small. however, I found in active learning the acquisition functions may sometimes only differ also by small values, thus small numerical inaccuracies can have a huge effect on what samples are selected. so to make this meaningful, I suggest you also give the minimal difference between two points their acquisition functions. this however, may be on the other hand too pessimistic, because the ordering might still be more or less the same. even more convincing that this will be no problem is to include the learning curve of the naive strategy without approximation versus the proposed strategies; these should overlap and have no significant differences if the approximation is truely good (which I suspect is the case). another option is to compute the ranking of all points in the pool for both methods and to compute the amount of ranking errors. \n\n5) Since one of the main points of the work is computational efficiency, I think in the real world experiments it would be fair to also report on this aspect for all compared approaches. \n\nmedium importance\n\n6) How was k determined for SMOCU? What is the value? I think I maybe missed this. \n\n7) line 140-142: here definition of random optimization is confusing. is this now a baseline which just samples randomly, or is this an active learning strategy? it seems like the latter. I do not see why in lines 197 the active learning strategies are combined with random sampling... it seems to be almost part of the experimental setup. shouldn't there always be a pool that is sampled randomly? this seems like a default choice in pool-based AL which may not even need to be explicitly mentioned in the algorithm design, as all other approaches also use this component.  \n\n8) Figure 2 and 3: please put #training samples on the x-axis instead which is much clearer. Now it seems uncertain if iteration 1 corresponds to how many samples? \n\n9) line 277: this must be M_1? \n\n10) I would find it much more convincing if in Table 1 you would add an experiment with n = 500 or n = 1000, and illustrate that indeed the computation times blow up completely for naive and IS. if this is infeasible, perhaps these computation times can be estimated from a graph (e.g. plot computation time versus n, and fit a n^3 polynomial, and extrapolate the computation times). Now it is less convincing as the computation times are relatively still the same order of magnitude. By the way, is the computation time for the entire pool here?\n\n11) line 284: how are the hyperparameters estimated; cross validation or using the marginal likelyhood? I suggest it may be wise to use cross validation to make a surfaceplot of the two hyperparameters, and have a look by hand if there is only a single optima or if there are multiple optima. then it may be better to hand pick one minima and fix the hyperparameters to that value, to reduce the variance of the experiments. this is not a problem if this is only done once, of course. I guess the data used to tune the hyperparameters is discarded afterwards? This wasn't entirely clear. \n\nminor points\n\n12) line 26: membership query framework is also a fundemental setup often studied, see Settles [14]\n13) line 31-33: I would perhaps remove or change this claim regarding deep models, as this paper seems to pertain anyway to GPR models? But I agree: the material science motivation is good and keep that aspect; e.g. that the number of samples in such application is usually orders of magnitude smaller. \n14) line 31: if you want to keep the deep learning link, here is a relevant paper on active learning with generative models:\nHuijser, Miriam, and Jan C. van Gemert. \"Active decision boundary annotation with deep generative models.\" Proceedings of the IEEE international conference on computer vision. 2017. which is also related to query synthesis. \n15) line 130: what is stated here is not backed up by the equation which can be confusing. introduce the quantity, and keep the remark but relate it to [17]. \n16) line 143-147: here the mathematical notation and writing is really cumbersome and confusing. I think clearly eq 5 and 7 should define g^S and g^M, and then U^M and U^S should in turn be defined by just integrating out x_s! now the definitions are really terrible to get understand. your reader will also be happy if you clarify that the S stands for Smooth (still lost what the M stands for?)\n17) line 154: \"need a large number of samples M_2\" to clarify that you are still talking about the M_2 samples\n18) line 180: if the kernel is a square exponential, isn't then the proposal distribution just a Gaussian distribution? why the truncation? \n19) section 4.1: was this experiment repeated multiple times with different f sampled from the GP prior? \nline 261: maybe give the absolute error rate? I guess you mean here g=g' or p-p', or are you talking about the actual classification errors? \n\nSuggestion for future work:\ncan we do the same trick to find 2 query points at the same time? Of course, computational complexity would be gigantic, but maybe SGD can make it work? This may be a better option to resolve the look ahead problem than SMOCU. \n\nNote: if you run into pagelimit issues I would put the pseudo-code of the SGD alg. also in the appendix. \n\n[a] Freytag, Alexander, Erik Rodner, and Joachim Denzler. \"Selecting influential examples: Active learning with expected model output changes.\" European conference on computer vision. Springer, Cham, 2014.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "nothing I can see", "review_text": "", "extra_scores": {"ethical_concerns": "nothing I can see", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "WdQVyGZfkS", "reviewer": "Reviewer_gsQi", "summary": "This paper proposes a bag of three techniques to improve the computational efficiency of  expected error reduction acquisition function for active learning Gaussian process classification models. The three techniques are\n* importance sampling: theoretically the error reduction is integrated over the whole input space, which is intractable and Monte Carlo sampling is adopted. To reduce the number of Monte Carlo samples x_s, importance sampling is proposed to focus sampling nearby the query candidate x_star, which is achieved by sampling portional to the kernel function centered at x_star. \n* avoid retraining for each query candidate by deriving the joint distribution of the query candidate label and Monte Carlo sample label, which become a one-dimensional integral.\n* deriving the gradient of the acquisition function for the SMOCU acquisition function so that gradient-based optimization can be used in query synthesis setting. \n\nExperiments\n* simulation experiments are conducted to demonstrate the accuracy of the joint distribution method against naive retraining \n* simulation experiments are conducted to demonstrate the accuracy and efficiency of the proposed method against naive computation of the acquisition function \n* experiment on the checkerboard dataset to show the effectiveness of the proposed algorithms in query synthesis setting against baselines such as random, max entropy search (MES) and Bayesian active learning by disagreement (BALD), where 0, 10%, or 20% noise is added in observations. \n* experiments on three UCI datasets to demonstrate the effectiveness of the proposed algorithm in pool-based active learning setting against MES and BALD. \n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes a combination of three techniques to improve the efficiency of some recently proposed active learning policy. While all the three techniques are well motivated and seem mathematically solid, the contribution is somewhat incremental, and empirical results are not super convincing.  \n\nThe main argument is improved efficiency but the only experiment to demonstrate this is on a 1d toy example where the advantage is not even that big, at least not presented in a convincing way. \n\nI would also expect more ablation studies on the number of samples on more datasets. E.g., how does the error rate drop as we increase the number of samples, comparing random vs importance sampling. \n\nThe paper is clearly written. \n\nSome questions\nhow to compute the integration is (9)? Is it analytically tractable? \ntypos\nline 215: “need to calculated” \nline 221: should be reliable estimation \nline 242: sampled from \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "MFNsqT7e_A-", "reviewer": "Reviewer_U1Z1", "summary": "For the limitations of active learning in Gaussian Process Classification (GPC), the paper proposes an active learning algorithm based on EER with GPC, which shows computational efficiency and superior performance through experiments. Specifically, the paper derives the joint prediction distribution of queries as a one-dimensional integral to avoid retraining GPC for each query regarding the problems of active learning strategies in the GPC field, which reduces computational overhead. In addition, the paper also uses the Soft MOCU (SMOCU) to effectively calculate the gradient of the SMOCU reduction.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper mainly considers the active learning scenario in GPC, which can be used to deal with the problem of identifying phase transitions in the field of materials science as the author says. Previous methods have some limitations, such as high computational overhead. Another problem is that EER cannot be applied to synthesis query with gradient optimization strategy.\nThis paper reduces the number of samples to estimate acquisition functions by importance sampling and proposes an appropriate solution to avoid retraining GPC for each query. The gradient based optimization method is applied to the synthesis query scenario by deriving $ \\nabla q\\left(f \\mid \\boldsymbol{x}_{*}, y_{*}\\right) $.\n\nHowever, the novelty of the paper is not enough. The improvement in computational efficiency is limited. The paper claims that the method proposed could avoid retraining GPC for each query, but it still needs much time to calculate the joint distribution integral. It can be seen from table 1 that when n=10, the IS+JDI method even costs more time than the naive method. The experiments are not solid. In the pool-based scenario, only one dataset is used. What's more, except for random, there are only two methods selected for comparison in the pool-based scenario, which is not convincing. In Section 3.3, this paper assumes that \"given the EP approximation ... know the gradient ...\", which is unrealistic. This paper is not well-written. For example, the formula such as `logsumexp` is not standard. Many formula and symbols are involved, but some of them are not clearly explained. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally liked the novel ideas presented in the paper about speeding up active learning. Concerns expressed originally in the reviews were mitigated by the rebuttal and a good discussion between the reviewers.
The contributions made in the paper are sufficiently strong to merit publication at NeurIPS. The authors should however make sure to clearly incorporate that answers the questions of the reviewers in the final version.
Decision: Accept (Poster)