Active Expansion Sampling for Learning Feasible Domains in an Unbounded Input Space
Wei Chen Mark Fuge













W. Chen Department of Mechanical Engineering 

              University of Maryland 

              College Park, MD 20742 

              wchen459@umd.edu           

           M. Fuge Department of Mechanical Engineering 

              University of Maryland 

              College Park, MD 20742






Active Expansion Sampling for Learning Feasible Domains in an Unbounded Input Space

This work was funded through a University of Maryland Minta Martin Grant.


    Wei Chen         Mark Fuge 

    Received: date / Accepted: date
================================================================================================================================================================




Many engineering problems require identifying feasible domains under implicit constraints. One example is finding acceptable car body styling designs based on constraints like aesthetics and functionality. Current active-learning based methods learn feasible domains for bounded input spaces. However, we usually lack prior knowledge about how to set those input variable bounds. Bounds that are too small will fail to cover all feasible domains; while bounds that are too large will waste query budget. To avoid this problem, we introduce Active Expansion Sampling (AES), a method that identifies (possibly disconnected) feasible domains over an unbounded input space. AES progressively expands our knowledge of the input space, and uses successive exploitation and exploration stages to switch between learning the decision boundary and searching for new feasible domains. We show that AES has a misclassification loss guarantee within the explored region, independent of the number of iterations or labeled samples. Thus it can be used for real-time prediction of samples' feasibility within the explored region. We evaluate AES on three test examples and compare AES with two adaptive sampling methodsthe Neighborhood-Voronoi algorithm and the straddle heuristicthat operate over fixed input variable bounds.








lLength scale of the Gaussian kernel
xInput sample
x^*Optimal query
yLabel of an input sample (feasible/infeasible)
ŷLabel estimated by Gaussian Process
X_LSet of labeled samples
X_USet of unlabeled samples (candidates)
dInput space dimension
f̅Predictive mean of Gaussian Process
VPredictive variance of Gaussian Process
hActual evaluation function
fEstimated feasibility function
p_ϵϵ-margin probability
ΦCumulative distribution function of standard Gaussian distribution
LMisclassification loss
 





§ INTRODUCTION


In applications like design space exploration <cit.> and reliability analysis <cit.>, people need to find feasible domains within which solutions are valid. Sometimes the constraints that define those feasible domains are implicit, , they cannot be represented analytically. Examples of these constraints are aesthetics, functionality, or performance requirements, which are usually evaluated by human assessment, experiments, or time-consuming computer simulations. Thus usually it is expensive to detect the feasibility of a given input. In such cases, one would like to use as few samples as possible while still approximating the feasible domain well.

To solve such problems, researchers have used active learning (or adaptive sampling)[Note that in this paper the terms “active learning" and “adaptive sampling" are interchangeable.] to sequentially select the most informative instances and query their feasibility, so that the number of queries can be minimized <cit.>.
These methods require fixed bounds over the input space, and only pick queries inside those bounds. But what if we do not know how wide to set those bounds? If we set the bounds too large, an active learner will require an excessively large budget to explore the input space; whereas if we set the bounds too small, we cannot guarantee that an algorithm will recover all the feasible domains <cit.>. In this case, we need an active learning method that can gradually expand our knowledge about the input space until we have either discovered all feasible domains or used up our remaining query budget.

This paper proposes a methodwhich we call Active Expansion Sampling (AES)to solve that problem by casting the detection of feasible domains as an unbounded domain estimation problem.
In an unbounded domain estimation problem, given an expensive function h: 𝒳∈ℝ^d→{-1,1} that evaluates any point x in an unbounded input data space 𝒳, we want to find (possibly disconnected) feasible domains in which h(x)=1. Specifically, h could be costly computation, time-consuming experiments, or human evaluation, so that the problem cannot be solved analytically.
By unbounded, we mean that we don't manually bound the input space. Thus the input space can be considered as infinite, and theoretically if the query budget allows, our method can keep expanding the explored area of the input space. To use as few function evaluations as necessary to identify feasible domains, AES first fully exploits (up to an accuracy threshold) any feasible domains it knows about and then, budget permitting, searches outward to discover other feasible domains.

The main contributions of this paper are:


  * We introduce the AES method for identifying (possibly disconnected) feasible domains over an unbounded input space.

  * We provide a framework that transfers bounded active learning methods into methods that can operate over unbounded input space.

  * We introduce a dynamic local pool method that efficiently finds near optimal solutions to the global optimization problem (Eq. <ref>) for selecting queries.

  * We prove a constant theoretical bound for AES's misclassification error at any iteration inside the explored region.





§ BACKGROUND AND RELATED WORK


Essentially, the unbounded domain estimation problem breaks down into two tasks explored by past researchers: 1) the active learning task, where we efficiently query the feasibility of inputs; and 2) the classification task, where we estimate decision boundaries (, boundaries of feasible domains) that separates the feasible class and the infeasible class (, feasible regions and infeasible regions). For the first task, we will review relevant past work on active learning. For the second task, we use the Gaussian Process as the classifier in this paper and will introduce basic concepts of Gaussian Processes.




 §.§ Feasible Domain Identification


Past work in design and optimization has proposed ways to identify feasible domains or decision boundaries of expensive functions.
Generally those methods were proposed to reduce the number of simulation runs and improve the accuracy of surrogate models in simulation-based design and reliability assessment <cit.>. Also, the problem of feasible domain identification is also equivalent to estimating the level set or the threshold boundaries of a function, where the feasible/infeasible region becomes superlevel/sublevel set <cit.>. Such methods select samples that are expected to best improve the surrogate model's accuracy. A common rule is to sample on the estimated decision boundary, but not close to existing sample points. Existing methods achieve this by (1) explicitly optimizing or constraining the decision function or the distance between the new sample and the existing samples <cit.>, or (2) selecting points based on the estimated function values and their confidence at candidate points <cit.>.




 §.§ Active Learning



Methods for feasible domain identification usually require strategies that sequentially sample points in an input space, such that the sample size is minimized. These strategies fall under the larger category of active learning.

There are three main scenarios of active learning problems: (1) membership query synthesis, (2) stream-based selective sampling, and
(3) pool-based sampling <cit.>. In the membership query model, the learner generates samples de novo for labeling. For classification tasks, researchers have typically applied membership query models to learning finite concept classes <cit.> and halfspaces <cit.>.
In the stream-based selective sampling model, an algorithm draws each unlabeled sample from an incoming data distribution, and then decides whether or not to query that label. This decision can be based on some informativeness measure of the drawn sample <cit.>, or whether the drawn sample is inside a region of uncertainty <cit.>.
In the pool-based sampling model, there is a small pool of labeled samples and a large (but finite) pool of unlabeled samples, where the learner selects new queries from the unlabeled pool. 

The unbounded domain estimation problem assumes that synthesizing an unlabeled sample from the input space is not expensive (as in the membership query scenario), since otherwise we have to use existing samples and the input space will be bounded. An example that satisfies this assumption is experimental design, where we can form an experiment by selecting a set of parameters. With this assumption, our proposed method approximates the pool-based sampling setting by synthesizing a pool of unlabeled samples in each iteration.

A pool-based sampling method first trains a classifier using the labeled samples. Then it ranks the unlabeled samples based on their informativeness indicated by an acquisition function. A query is then selected from the pool of unlabeled samples according to their rankings. After that, we add the selected query into the set of labeled data and repeat the previous process until our query budget is reached. Many of these methods use the informativeness criteria that select queries with the maximum label ambiguity <cit.>, contributing the highest estimated expected classification error <cit.>, best reducing the version space <cit.>, or where different classifiers disagree the most <cit.>. Such methods are usually good at exploitation, since they keep querying points close to the decision boundary, refining our estimate of it. 

However, when the input space may have multiple regions of interest (, feasible regions), these methods may not work well if the active learner is not aware of all the regions of interest initially. Note that while some of the methods mentioned above also consider representativeness <cit.>, or the diversity of queries <cit.>, they don't explicitly explore unknown regions and discover other regions of interests. To address this issue, an active learner also has to allow for exploration (, to query in unexplored regions where no labeled sample has been seen yet). A learner must trade-off exploitation and exploration. 

To query in an unexplored region, there are methods that (1) take into account the predictive variance at unlabeled samples when selecting new queries <cit.>, (2) naturally balance exploitation/exploration by looking a the expected error <cit.>, or (3) make exploitative and exploratory queries separately using different strategies
 <cit.>. In previous methods, the exploitation-exploration trade-off was performed in a bounded input space or a fixed sampling pool. However, in the unbounded domain estimation problem, there is no fixed sampling pool and we are usually uncertain about how to set the bounds of the input space for performing active learning. If the bounds are too small, we might miss feasible domains; while if the bounds are too large, the active learner has to query more samples than necessary to achieve the required accuracy.

In this paper, we introduce a method of using active learning to expand our knowledge about an unbounded input data space, and discover feasible domains in that space. A naïve solution would be to progressively expand a bounded input space, and apply the existing active learning techniques. However, there are two problems with this naïve solution: (1) it is difficult to explicitly specify when and how fast we expand the input space; and (2) the area we need to evaluate increases over time increasing the computational cost. 
Thus existing active learning techniques cannot apply directly to the unbounded domain estimation problem. To the best of our knowledge, <cit.> is the first to deal with the active learning problem over an unbounded input space (, the unbounded domain estimation problem). The AES method proposed in this paper improves upon that previous work (as illustrated in Sect. <ref>).





 §.§ Gaussian Process Classification (GPC)


Gaussian Processes (GP, also called Kriging) are often used as a classifier in active learning <cit.>. Compared to other commonly used classifiers such as Support Vector Machines or Logistic Regression, GP naturally models probabilistic predictions. This offers us a way to evaluate a sample's informativeness based on its predictive probability distribution.

The Gaussian process uses a kernel (covariance) function k(x,x') to measure the similarity between the two points x and x'. It encodes the assumption that “similar inputs should have similar outputs". Some commonly used kernels are the Gaussian kernel and the exponential kernel <cit.>. In this paper we use the Gaussian kernel:

    k(x,x')=exp(-x-x'^2/2l^2)

where l is the length scale.

For binary GP classification, we place a GP prior over the latent function f(x), and then “squash" f(x) through the logistic function to obtain a prior on π(x) = σ(f(x)) = P(y=1|x). In the feasible domain identification setting, we can consider f : 𝒳∈ℝ^d →ℝ as an estimation of feasibility, thus we can call it estimated feasibility function. Under the Laplace approximation, given the labeled data (X_L, y), the posterior of the latent function f(x) at any x∈ X_U is a Gaussian distribution: f(x)|X_L,y,x∼𝒩(f̅(x), V(x)) with the mean and the variance expressed as

    f̅(x)    = k(x)^TK^-1f̂ = k(x)^T ∇log P(y|f̂)
    
    
    V(x)    = k(x,x)-k(x)^T(K+W^-1)^-1k(x)

where W=-∇∇log P(y|f) is a diagonal matrix with non-negative diagonal elements; f is the vector of latent function values at X_L, , f_i=f(x^(i)) where x^(i)∈ X_L; K is the covariance matrix of the training samples, , K_ij=k(x^(i),x^(j)); k(x) is the vector of covariances between x and the training samples, , k_i(x)=k(x,x^(i)); and f̂ = arg max_f P(f|X,y). When using the Gaussian kernel shown in Eq. <ref>, k(x,x)=1. We refer interested readers to a detailed description by Rasmussen <cit.> about the Laplace approximation for the binary GP classifier.

The decision boundary corresponds to f̅(x)=0 or π̅(x)=0.5. We predict y=-1 when f̅(x)<0, and y=1 otherwise.





§ ACTIVE EXPANSION SAMPLING (AES)




  The Active Expansion Sampling algorithm
  
  


Algorithm <ref> summarizes our proposed Active Expansion Sampling method. Overall, the method consists of the following steps:


  * Select an initial sample x^(0) to label.

  * In each subsequent iteration, 
 
  
  * check the exploitation/exploration status (Sect. <ref>),
  
  * generate a pool of candidate samples X_U based on the exploitation/exploration status and previous queries (Sect. <ref> and <ref>),
  
  * train a GP classifier using the labeled set X_L to evaluate the informativeness of candidate samples in X_U,
  
  * select a sample from X_U based on its informativeness and its distance from c (Sect. <ref>),
  
  * label the new sample and put it into X_L.


  * Exit when the query budget is reached.


This AES method improves upon our previous domain expansion method <cit.> in several ways. For example, the previous method generates a pool X_U that expands with the explored region each iteration. So its pool size and hence the computational cost increase significantly over time if using a constant sample density. To avoid this problem, this paper proposes a dynamic local pool method (Sect. <ref>).
Another major difference is that AES provides a verifiable way to distinguish between exploitation and exploration (Sect. <ref>); while the previous method uses a heuristic based on the labels of last few queries (which is more likely to make mistakes). In this section and Sect. <ref>, we show comprehensive theoretical analysis and experiments to prove favorable properties of our new method.




 §.§ ϵ-Margin Probability





We train a GP classification model to evaluate the informativeness of candidate samples based on the ϵ-margin probability (Fig. <ref>):

    p_ϵ(x)    = 
        P(f(x)<-ϵ|x),    if ŷ=1
    
        P(f(x)>ϵ|x),    if ŷ=-1
       = P(ŷf(x) < -ϵ|x) 
       = Φ(-|f̅(x)|+ϵ/√(V(x)))

where ŷ is the estimated label of x, the margin ϵ>0, and Φ(·) is the cumulative distribution function of standard Gaussian distribution 𝒩(0,1). The ϵ-margin probability represents the probability of x being misclassified with some degree of certainty (controlled by the margin ϵ). 
Let the misclassification loss be

    L(x)    = max{0,-f(x)},    if y=1
    max{0,f(x)},    if y=-1

where y is the true label of x. L(x) measures the deviation of the estimated feasibility function value f(x) from 0 when the class prediction is wrong. Then, based on Eq. <ref> and <ref>, p_ϵ(x)=P(L(x)>ϵ), which is the probability that the expected misclassification loss exceeds ϵ. A high p_ϵ(x) indicates that x is very likely to be misclassified, and requires further evaluation. Thus we use this probability to measure informativeness.





 §.§ Exploitation and Exploration





Since our input space is unbounded, naïvely maximizing the ϵ-margin probability (informativeness) will always query points infinitely far away from previous queries.[A point infinitely far away from previous queries has the f̅(x) close to 0 and the maximum V(x), thus the highest p_ϵ(x).]
To avoid this issue, one solution is to query informative samples that are close to previously labeled samples. This allows the active learner to progressively expand its knowledge as the queries cover an increasingly large area of the input space. When a new decision boundary is discovered during expansion, we want a query strategy that continues querying points on that decision boundary, such that the new feasible region can be identified as quickly as possible. Therefore, to enable continuous exploitation of the decision boundary, we propose the following query strategy

    min_x∈ X_U     V(x) 
    s.t.     p_ϵ(x) ≥τ

where V(x) is the predictive variance at x, and τ is a threshold of the informativeness measure p_ϵ(x).


The solution to Eq. <ref> will lie at the intersection of the estimated decision boundary (f̅(x)=0) and the isocontour of p_ϵ(x)=τ (Point A in Fig. <ref>), if that intersection A exists.




In the following proof, we denote f̅_P=f̅(x_P), and V_P=V(x_P). For a sample x_A at the intersection of f̅(x)=0 and p_ϵ(x)=τ, we have f̅_A=0 and p_ϵ(x_A)=Φ(-ϵ/√(V_A))=τ (Point A in Fig. <ref>); and for a sample x_B that is any feasible solution to Eq. <ref>, we have p_ϵ(x_B)=Φ(-(|f̅_B|+ϵ)/√(V_B))≥τ (Point B in Fig. <ref>). Thus we get ϵ/√(V_B)≤ (|f̅_B|+ϵ)/√(V_B)≤ϵ/√(V_A). Therefore, V_A ≤ V_B. The equality holds when |f̅_B|=0 and p_ϵ(x_B)=τ, , x_B is also at the intersection of f̅(x)=0 and p_ϵ(x)=τ. Thus we proved the intersection has the minimal predictive variance among feasible solutions to Eq. <ref>, and hence it is the optimal solution.


Theorem <ref> indicates that when applying the query strategy shown in Eq. <ref>, the active learner will only query points at the estimated decision boundary[In Sect. <ref>, we assume that the queried point is the exact solution to the query strategy. However since we approximate the exact solution by using a pool-based sampling setting, the query may be deviate from the exact solution slightly.] as long as the estimated decision boundary and the isocontour of p_ϵ(x)=τ intersect. The fact that this intersection exists indicates that there are points on the decision boundary that are informative to some extent (, with p_ϵ(x) ≥τ). We call this stage the exploitation stageat this stage the active learner exploits the decision boundary. Equation <ref> ensures that the queries are always on the estimated decision boundary until the exploitation stage ends (, there are no longer informative points on the decision boundary).

If the estimated decision boundary and the isocontour of p_ϵ(x)=τ do not intersect, then the algorithm has fully exploited any informative points on the estimated decision boundary (, for all the points on the estimated decision boundary, we have p_ϵ(x)<τ). We call this stage the exploration stage since the active learner starts to search for another decision boundary (Fig. <ref>). In this stage, we want the new query to be both informative and close to where we started, since we don't want the new query to deviate too far from where we start. Therefore, the query strategy at the exploration stage is

    min_x∈ X_U    x-c
    s.t.     p_ϵ(x) ≥τ

where the objective function is the Euclidean distance between x and a center c. This objective keeps the new query selected by Eq. <ref> close to c. In practice, initially when there are only samples from one class, we set c as the initial point x^(0) to keep new queries close to where we start; once there are both positive and negative samples, we set c as the centroid of these initial positive samples, since we want to keep new queries close to the initial feasible region.


Given x^* as the solution to Eq. <ref>, we have p_ϵ(x^*)=τ, if p_ϵ(c)<τ.




Since p_ϵ(c)<τ, c itself is not the solution of Eq. <ref>. Thus x^*-c>0. Then we have p_ϵ(x)<τ at any point within a (d-1)-sphere centered at c with radius x^*-c, because otherwise the query will be inside the sphere. Thus on that sphere we have p_ϵ(x) ≤τ. So p_ϵ(x^*) ≤τ, since x^* is on that sphere. Because x^* is a feasible solution to Eq. <ref>, we also have p_ϵ(x^*) ≥τ at x^*. Therefore p_ϵ(x^*)=τ.


Theorem <ref> shows that in each iteration, the optimal query x^* selected by Eq. <ref> is on the isocontour of p_ϵ(x)=τ.

For both Eq. <ref> and <ref>, the feasible solutions are in the region of p_ϵ(x)≥τ. Intuitively this means that we only query samples with at least some level of informativeness. We call the region where p_ϵ(x)≥τ the unexplored region, since it contains informative samples (feasible solutions) that our query strategy cares about; while we call the rest of the input space (p_ϵ(x)≤τ) the explored region (Fig. <ref>).

The upper bound of p_ϵ(x) is Φ(-ϵ/sup_x V(x)), and it lies infinitely far away from the labeled samples. In Eq. <ref>, K+W^-1 is positive semidefinite, thus k(x)^T(K+W^-1)^-1k(x) ≥ 0 and V(x)≤ k(x,x). For a kernel k(·) with k(x,x)=1 (, the Gaussian or the exponential kernel), we have V(x)≤ 1. Thus p_ϵ(x) ≤Φ(-ϵ). To ensure that Eq. <ref> has a feasible solution, we have to set τ≤Φ(-ϵ). Therefore, we can set τ=Φ(-ηϵ), where η≥ 1.0. Then the constraint in Eq. <ref> and <ref> can be expressed as

    Φ(-|f̅(x)|+ϵ/√(V(x))) ≥Φ(-ηϵ)

which can be written as

    ηϵ√(V(x)) - |f̅(x)| ≥ϵ

The left-hand side of Eq. <ref> is identical to the acquisition function of the straddle heuristic when ηϵ=1.96 <cit.>. The straddle heuristic queries the sample with the largest value of the acquisition function. This acquisition function accounts for the ambiguity of samples in terms of their confidence intervals <cit.>:

    a(x)    = min{-min Q(x), max Q(x)}
       = 1.96√(V(x)) - |f̅(x)|

where Q(x) is the 95% confidence interval of x. 




Substituting Eq. <ref> for the constraint in Eq. <ref> and <ref>, and combining the exploitation and exploration stages, our overall query strategy becomes

    min_x∈ X_U     V(x)^αx-c^1-α
    s.t.    ηϵ√(V(x)) - |f̅(x)| ≥ϵ

where the indicator α is 1 at the exploitation stage, and 0 otherwise. Section <ref> introduces how to set α (, when to exploit vs explore).

In general, the unbounded domain estimation problem can be solved using a family of query strategies with the following form

    min_x∈ X_U     D(x) 
    s.t.     I(x) ≥τ

where D(x) is a function that increases as x moves away from the labeled samples, and I(x) is the informativeness measure that is used in any bounded active learning methods. Our query strategies of Eqn <ref> and <ref> all have this form. Comparatively, for bounded active learning methods, the query strategies are usually in the form of max_x∈ X_U I(x).





§ DYNAMIC LOCAL POOL GENERATION



We cast our problem as pool-based sampling by generating a pool of unlabeled instances de novo in each iteration. A naïve way to generate this pool is to try to sample points anywhere near the p_ϵ(x)=τ isocontour. However, intuitively, as the algorithm searches progressively larger volumes of the input space, the pool volume will likewise expand. This expansion means that the size of the pool will increase dramatically over time (assuming we want a constant sample density). This increase, however, makes the computation of Eq. <ref> and <ref> expensive during later expansion stages.

To bypass this problem, we propose a dynamic local pool method that generates the pool of candidate samples only at a certain location in each iteration, rather than sampling the entire domain.[Sampling methods like random sampling or Poisson-disc sampling <cit.> can be used to generate the pool. We use random sampling here thereby for simplicity. The specific choice of the sampling method within the local pool is not central to the overall method.] The key insight behind our local pooling method is that while the optimal solution to Eq. <ref> can, in principle, occur anywhere on the p_ϵ(x)=τ isocontour, in practice, multiple points on the isocontour are equally optimal. All we need to do is sample points around any one of those optima. Below, we derive guarantees for how to sample volumes near one of those optima, thus only needing to sample a small fraction of the total domain volume.




 §.§ Scope of an Optimal Query



Let δ be the distance between an optimal query[The optimal query means the exact solution to the AES query strategy shown in Eq. <ref>, <ref>, or <ref>.] and its nearest labeled sample.  We have

    δ < β l

where β is a coefficient depends on ϵ, η, and the GP model.



We include the proof of Theorem <ref> and the way of computing β in the appendix (Sect. <ref>).
Theorem <ref> indicates that if we set the pool boundary by extending the current labeled sample range by β l, then that pool is guaranteed to contain all solutions to Eq. <ref>; that is, extending the overall pool boundary further will not increase the chances of sampling near p_ϵ(x)=τ, and will only decrease the sample density (given a fixed pool size) or increase the evaluated samples (given a fixed sample density). However, if we generate the pool based solely on this principle (, extending the current labeled sample range by β l), the pool size will still increase over time as the domain size grows. The next two sections show how, for the exploration and exploitation stages respectively, we can further reduce the sample boundary to only a local hyper-sphere.




 §.§ Pool for the Exploration Stage






During the exploration stage of Active Expansion Sampling, the distance between an optimal query and its nearest labeled sample is

    δ < δ_explore = β l




Theorem <ref> is derived from Eq. <ref>.
The nearest labeled sample of the optimal query could be any border point (a sample lying on the periphery of the labeled set). There are multiple local optima that are equally useful for expanding the explored region (Fig. <ref>). Thus we just sample near one of those optima. Specifically, we approximate the nearest labeled sample as the previous query. With this approximation, incorporating Theorem <ref>, the optimal query will be inside 𝒞(x^(t-1), δ_explore), the (d-1)-sphere with a radius of δ_explore, centered at the previous query x^(t-1). Thus during the exploration stage, we set the pool boundary to be that sphere (Fig. <ref>).

Sometimes when AES switches from exploitation to exploration, the previous query may not lie on the periphery of the labeled samples. 
This causes samples around the previous query to have low values of p_ϵ(x). In this case, there might not be feasible solution to Eq. <ref>. Thus, every time AES switches from exploitation to exploration, we center the pool around the farthest labeled sample from the centroid of the initial positive samples (, argmax_x∈ X_Lx-c). This ensures that AES generates pool samples near the periphery of the labeled samples.





 §.§ Pool for the Exploitation Stage




During the exploitation stage of Active Expansion Sampling, the distance between an optimal query and its nearest labeled sample is

    δ < δ_exploit = γ l

where γ is a coefficient depends on ϵ, η, and the GP model.



We include the proof of Theorem <ref> and the way of computing γ in the appendix (Sect. <ref>).
Similar to the exploration stage, based on Theorem <ref>, we define the pool boundary during the exploitation stage as 𝒞(x^(t-1), δ_exploit), a (d-1)-sphere with a radius of δ_exploit, centered at the previous query x^(t-1) (Fig. <ref>).





 §.§ Choosing when to Exploit versus Explore



Since we use different rules to generate the pool at the exploitation and exploration stage, we need to distinguish between the two stages at the beginning of each iteration. In the exploitation stage, according to Theorem <ref>, the optimal query lies within the (d-1)-sphere 𝒞(x^(t-1), δ_exploit) centered at the previous query. While, according to Theorem <ref>, that same query must lie where the estimated decision boundary and the isocontour of p_ϵ(x)=τ intersect.
Thus, the decision boundary and the isocontour divide the sphere 𝒞 into four regions (Fig. <ref>):

unexplored negative ℛ_1 = {x|p_ϵ(x)>τ, f̅(x)<0}; 

unexplored positive ℛ_2 = {x|p_ϵ(x)>τ, f̅(x)>0}; 

explored negative ℛ_3 = {x|p_ϵ(x)<τ, f̅(x)<0}; and 

explored positive ℛ_4 = {x|p_ϵ(x)<τ, f̅(x)>0}.

In contrast, during exploration the estimated decision boundary and the p_ϵ(x)=τ isocontour do not intersectmeaning, unlike exploitation, there exist only two of the four regions (either ℛ_1 & ℛ_3 or ℛ_2 & ℛ_4). In particular, within the unexplored region, f̅(x) will be either all positive or all negative, , ℛ_1 and ℛ_2 cannot exist simultaneously (Fig. <ref>). 

We use this property to detect exploitation or exploration by generating a pool (a set of uniformly distributed samples) within the boundary 𝒞(x^(t-1), δ_exploit) and checking if, for samples with p_ϵ(x)>τ, samples differ in f̅(x)>0 and f̅(x)<0. If so, AES is in the exploitation stage; otherwise it is in the exploration stage.








§ THEORETICAL ANALYSIS


In this section, we derive a theoretical accuracy bound for AES with respect to its hyperparameters. We further discuss the influence of those hyperparameters on the classification accuracy, the query density, and the exploration speed. The results of this section guides the selection of proper hyperparameters given an accuracy or budget requirement.




 §.§ Accuracy Analysis



It is impossible to discuss the function accuracy across the entire input space, since the input space is unbounded. However, we can consider ways to bound the accuracy within bounded explored regions at any time step.

As mentioned in Sect. <ref>, p_ϵ(x)=P(L(x)>ϵ), where L(x) is the misclassification loss at x defined in Eq. <ref>. Thus within the explored region, we have

    P(L(x)≥ϵ)≤τ   ∀x∈{x|p_ϵ(x)≤τ}

or

    P(L(x)≤ϵ)≥ 1-τ   ∀x∈{x|p_ϵ(x)≤τ}


This shows that at any location within the explored region of the input space, the proposed method guarantees an upper bound ϵ of misclassification loss with a probability of at least 1-τ at any given point. Since, in the exploration stage, the estimated decision boundary lies inside the p_ϵ(x)≤τ region (as discussed in Sect. <ref>), we have 

    P(L(x)≤ϵ)≥ 1-τ   ∀x∈{x|f̅(x)=0}

This means that in the exploration stage, the estimated decision boundary f̅(x)=0 lies in between the isocontours of f(x)=±ϵ with a probability of at least 1-τ, where f is the true latent function.

Note that Eq. <ref> shows that AES's accuracy bound within the explored region is independent of the number of iterations or labeled samples. One advantage of keeping a constant accuracy bound for AES is that the accuracy in the explored region meets our requirements[We can set ϵ and τ such that the accuracy bound is as required. Details about how to set hyperparameters are in Sect. <ref>.] whenever AES stops. This also means that the estimation within the explored region is reliable at any iteration (although this is not true if one includes the unexplored region). In contrast, bounded active learning methods usually only achieve required accuracy after a certain number of iterations, before which the estimation may not be reliable. Therefore, AES can be used for real-time prediction of samples' feasibility in the explored region.





 §.§ Query Density


In Gaussian Processes, given a fixed homoscedastic Gaussian or exponential kernel, we can measure the query density by looking at the predictive variance at queried points. According to Eq. <ref>, V(x) only depends on k(x), which is affected by the distances between x and other queries. A smaller variance at a query indicates that it is closer to other queries, and hence a higher query density; and vise versa.


The predictive variance of an optimal query in the exploitation and exploration stage is

    V(x_exploit) = 1/η^2

and

    V(x_explore) = 1/η^2(1+|f̅(x_explore)|/ϵ)^2

where x_exploit and x_explore are optimal queries at the exploitation stage and exploration stage, respectively.



The proof of Theorem <ref> is in the appendix (Sect. <ref>). This theorem indicates that the predictive variances of queries at the exploitation stage are always smaller than those at the exploration stage (as |f̅(x_explore)|>0). Thus the query density at the exploitation stage is always higher than that at the exploration stage. The property of having a denser set of points along the decision boundary (queried during the exploitation stage) and a sparser set of points at other regions (queried during the exploration stage) is desirable because we want to save our query budget for refining the decision boundary rather than other regions of the input space.

Equation <ref> and <ref> also reflect the trade-off between the accuracy and the running time. When the query density near the decision boundary is high (small V(x_exploit) in Eq. <ref>), η is large, thus τ in Eq. <ref> is small, which means our model will have a higher probability of having a misclassification loss less than ϵ. However, as the query density gets higher, we need more queries to cover a certain region, thus the running time increases.







 §.§ Influence of Hyperparameters



There are four hyperparameters that control Active Expansion Samplingthe initial point x^(0), ϵ and η in the exploitation/exploration stage, and the length scale l of the GP kernel.
The choice of the kernel function and length scale depends on assumptions regarding the nature and smoothness of the underlying feasibility function. Such kernel choices have been covered extensively in prior research and we refer interested readers to  <cit.> for multiple methods of choosing l. Note that it is difficult to optimize the length scale at each iteration, since the length scale will eventually be pushed to extremes. In the exploitation stage, for example, once the length scale is smaller than the previous iteration, the distance between the new query and its nearest query will also be smaller (due to Eq. 12). Then the maximum marginal likelihood estimation will result in a smaller length scale, as the estimated function is steeper. This process will repeat and eventually cause the optimal length scale to converge to 0. The initial point x^(0) can be any point not too far away from the boundary of feasible regions, since otherwise it will take a large budget to just search for a sample from the opposite class. Here we focus on the analysis of the other two hyperparametersϵ and η.

According to Eq. <ref>, ϵ and τ affect the classification accuracy in a probabilistic way. When τ=Φ(-ηϵ), we have P(L(x)≤ϵ)≥ 1-Φ(-ηϵ) in the explored region. This offers us a guideline for setting ϵ and η with respect to a given accuracy requirement.

According to Eq. <ref> and <ref>, η controls the density of queries in both exploitation and exploration stages. Specifically, as we increase η, V_exploit and V_explore decreases, increasing the query density and essentially placing labeled points closer together.

In contrast, ϵ only controls the distances between queries in the exploration stage.
[Technically, due to sampling error introduced when generating the pool, the exploitation stage will be influenced by ϵ (since f̅(x^*) is only ≈ 0). But this effect is negligible compared to ϵ's influence on the exploration stage.] Increasing ϵ decreases V_explore and hence increases the density of queries in the exploration stage. 
This density of queries affects (1) how fast we can expand the explored region, and (2) how likely we are to capture small feasible regions. When η or ϵ increases, we expand the explored region slower, making it more likely that we will discover smaller feasible regions. Likewise, we also slow down the expansion in exploitation stages, making the classifier more likely to capture a sudden change along domain boundaries.

Note that when ϵ=0, the constraint of p_ϵ(x)≥τ in Eq. <ref> is equivalent to f̅(x)=0, thus theoretically all queries should lie near the estimated decision boundary. In this case, the Active Expansion Sampling acts like Uncertainty Sampling <cit.>. In practice, however, AES will be unable to find a feasible solution when ϵ=0 since no candidate sample will be exactly on the decision boundary under the pool-based sampling setting.









§ EXPERIMENTAL EVALUATION



We evaluate the performance of AES in capturing feasible domains using both synthesized and real-world examples. The performance is measured by the F1 score, which is expressed as

    F_1 = 2·precision·recall/precision+recall

where

    precision=true positives/true positives+false positives

and

    recall=true positives/true positives+false negatives



We compare AES with two conventional bounded adaptive sampling methodsthe Neighborhood-Voronoi (NV) algorithm <cit.> and the straddle heuristic <cit.>. We also investigate the effects of noise and dimensionality on AES.

We use the same pool size (500 candidate samples[For NV algorithm, its pool size refers to the test samples generated for the Monte Carlo simulation.]) in all the experiments. In Fig. <ref>-<ref> and <ref>, the F1 scores are averaged over 100 runs. We run all 2-dimensional experiments on a Dell Precision Tower 5810 with 16 GB RAM, a 3.5 GHz Intel Xeon CPU E5-1620 v3 processor, and a Ubuntu 16.04 operating system. We run all higher-dimensional experiments on a Dell Precision Tower 7810 with 32 GB RAM, a 2.4 GHz Intel Xeon CPU E5-2620 v3 processor, and a Red Hat Enterprise Linux Workstation 7.2 operating system. The Python code needed to reproduce our AES algorithm, our baseline implementations of NV and Straddle, and all of our below experiments is available at <https://github.com/IDEALLab/Active-Expansion-Sampling>.









































































































 §.§ Effect of Hyperparameters


We first use two 2-dimensional test functionsthe Branin function and Hosaki function, respectivelyas indicator functions to evaluate whether an input is inside the feasible domain. Both examples construct an input space with multiple disconnected feasible regions, which makes the feasible domain identification task challenging.

The Branin function is

    g(x) =    (x_2-5.1/4π^2x_1^2+5/πx_1-6)^2 
       +10(1-1/8π)cos x_1+10

We define the label y=1 if x∈{x|g(x)≤ 8, -9<x_1<14, -7<x_2<17}; and y=-1 otherwise. The resulting feasible domains resemble three isolated feasible regions (Fig. <ref>). The initial point x^(0) = (3,3). For the Gaussian process, we use a Gaussian kernel (Eq. <ref>). We set the kernel length scale l=0.9. To compute the F1 scores, we generate samples along a 100 × 100 grid as the test set in the region where x_1 ∈ [-13,18] and x_2 ∈ [-8,23].

This section mainly describes the Branin exampleas both the Branin and Hosaki examples show similar resultshowever we direct interested readers to the appendix (Sect. <ref>) where we describe the Hosaki example in detail and show its experimental results.



For both examples, we use three levels of ϵ (0.1, 0.3, 0.5) and η (1.2, 1.3, 1.4) to demonstrate their effects on AES's performance.

Figures <ref> and <ref> show the sequence of queries selected by AES and the two bounded adaptive sampling methods, respectively, applied on the Branin example. For AES, there are three exploitation stages, as there are three disconnected feasible domains. AES starts by querying samples along the initial estimated decision boundary, and then expands queries outward to discover other feasible regions. In contrast, the straddle heuristic simultaneously explores the whole bounded input space, and refines all three decision boundaries. Fig. <ref> shows the corresponding F1 scores of the experiment in Fig. <ref>. During exploitation stages, AES's F1 score non-monotonically increases as part of the estimated decision boundary is outside the explored region (where AES has confidence on the accuracy); while in the exploration stage, the current decision boundaries are inside the explored region and remain unchanged, thus the F1 score stabilizes.

Figures <ref> and <ref> demonstrate the effects of hyperparameters ϵ and η, respectively, on AES's performance. Increasing ϵ or η leads to a slower expansion of the explored region and a higher F1 score. This means that using a higher ϵ or η enables accuracy improvement but requires larger query budget. In both examples, the F1 score is more sensitive to η than ϵ.







 §.§ Unbounded versus Bounded



We use the NV algorithm and the straddle heuristic as examples of bounded adaptive sampling methods. 








Because these two methods do not progressively expand the region (as in AES), but rather assumes a fixed region, we create a “bounding box” in the input space, and generate queries inside this box.









When comparing AES with the bounded methods, we use ϵ=0.3 and η=1.3 for AES. In each experiment, we change the size of the input space bounds to evaluate the effect of bound size on these methods. 
Specifically, we simulate the cases where we set tight, loose, and insufficient bounds, as shown in Tab. <ref> and Fig. <ref>. “Tight” means the bounds cover the entire feasible domain while being no larger than needed (in practice we use bounds slightly larger than this to ensure the feasible domain boundary is inside the tight bounds); “loose” means the bounds cover the entire feasible domain but are larger than the tight bounds; “insufficient” means the variable bounds do not cover the entire feasible domain.

As shown in Fig. <ref>, the NV algorithm makes fast accuracy improvement at early stages, and slows down after some iterations. The F1 score of NV is almost monotonically increasing; while AES's score fluctuates because it focuses first on refining the domains it knows about during exploitation (at the expense of accuracy on domains it has not seen yet). This causes AES to have a lower F1 score early on. For the NV algorithm, when the input variable bounds are set properly, both AES and NV achieve similar final F1 scores. However, NV requires more iterations to achieve a similar final accuracy to AES, especially when the bounds are set too large, where NV exhausts its query budget exploring unknown regions. When the bounds are set too small to cover certain feasible regions, NV stops improving the F1 score when it begins to over-sample the space and is unable to reach similar accuracy as AES. Note that in this case, we purposefully set the bounds such that they cover the vast majority of the feasible region, leaving only a small feasible area outside of those bounds. Our explicit purpose here is to demonstrate how sensitive such bounded heuristics can be when their bounds are misspecified (even by small amounts). The performance of bounded methods degrades rapidly as their bound sizes decrease further.

Although AES shows slow accuracy improvement over the entire test region, it keeps a constant accuracy bound within the explored region (as discussed in Sect. <ref>). Fig. <ref> shows the F1 scores within the p_ϵ(x)<τ region, which is AES's explored region. Specifically, we set ϵ=0.3, η=1.3, and τ=Φ(-ηϵ). For the NV algorithm, we use the tight input space bounds from the previous experiments. By just considering the explored region, AES's F1 scores are quite stable throughout the sampling sequence; while NV's F1 scores are low at the beginning, and then increase until stable.[This difference is because NV's explored region covers more area than AES at the beginning.] Since AES's accuracy inside the explored region is invariant of the number of iterations, it can be used for real-time prediction of samples' feasibility in the explored region.



Table <ref> shows the final F1 scores and wall-clock running time of AES, NV, and the straddle heuristic. Note that the confidence interval for NV's averaged F1 scores are much larger than AES. This is because during some runs NV fails to discover all the three feasible regions (Fig. <ref> for example).





 §.§ Effect of Noise


Label noise is usually inevitable in active learning tasks. The noise comes from, for example, simulation/experimental error or human annotators' mistakes. We test the cases where the labels are under (1) uniform noise and (2) Gaussian noise centered at the decision boundary. 

We simulate the first case by randomly flipping the labels. The noisy label is set as y' = (-1)^λ y, where λ∼Bernoulli(p), p is the parameter of the Bernoulli distribution that indicates the noise level, and y is the true label. 

The second case is probably more common in practice, since it is usually harder to decide the labels near the decision boundary. To simulate this case, we add Gaussian noise to the test functions: g'(x)=g(x)+e, where g(x) is the Branin or Hosaki function, and e ∼ s·𝒩(0, 1).

In each case we compare the performance of AES (ϵ=0.3, η=1.3) and NV (with tight bounds) under two noise levels. As expected, adding noise to the labels decreases the accuracy of both methods (Fig. <ref> and <ref>). However, in both cases (Bernoulli noise and Gaussian noise), the noise appears to influence NV more than AES. As shown in Fig. <ref>, when adding noise to the labels, NV has high error mostly along the input space boundaries, where it cannot query samples outside to further investigate those apparent feasible regions. In contrast, AES tries to exploit those rogue points to try to find new feasible regions, realizing after a few new samples that they are noise.






 §.§ Effect of Dimensionality


To test the effects of dimensionality on AES's performance, we apply both AES and NV on higher-dimensional examples where the feasible domains are inside two (d-1)-spheres of radius 1 centered at a and b respectively. Here a=0 and b=(3,0,...,0). Fig. <ref> shows the input space of the 3-dimensional double-sphere example. The initial point x^(0) = 0. For the Gaussian process, we use a Gaussian kernel with a length scale of 0.5. We set ϵ=0.3 and η=1.3. To compute the F1 scores, we randomly generate 10,000 samples uniformly within the region where x_1 ∈ [-2,5] and x_k ∈ [-2,2], k=2,...,d. The input space bounds for the NV algorithm are x_1 ∈ [-1.5,4.5] and x_k ∈ [-1.5,1.5], k=2,...,d. We get the F1 scores and running time after querying 1,000 points.

As shown in Fig. <ref>, both AES and NV shows an accuracy drop and running time increase as the problem's dimensionality increases. This is expected, since based on the curse of dimensionality <cit.>, the number of queries needed to achieve the same accuracy increases with the input space dimensionality. The curse of dimensionality is inevitable in machine learning problems. However, since AES explores the input space only when necessary (, only after it has seen the entire decision boundary of the discovered feasible domain), its queries do not need to fill up the large volume of the high-dimensional space. Therefore, AES's accuracy drop with problem dimensionality is not as severe as bounded methods like NV. For particularly high-dimensional design problems, another complementary approach is to construct explicit lower-dimensional design manifolds upon which to run AES <cit.>.





 §.§ Nowacki Beam Example


To test AES's performance in a real-world scenario, we consider the Nowacki beam problem <cit.>. The original Nowacki beam problem is a design optimization problem where we minimize the cross-section area A of a cantilever beam of length l with concentrated load F at its end. The design variables are the beam's breadth b and height h. We turn this problem into a feasible domain identification problem by replacing the objective with a constraint A = bh ≤ 0.0025 m^2. Other constraints are (1) the maximum tip deflection δ = Fl^3/(3EI_Y) ≤ 5mm, (2) the maximum blending stress σ_B = 6Fl/(bh^2) ≤σ_Y, (3) the maximum shear stress τ = 1.5F/(bh) ≤σ_Y/2, (4) the ratio h/b ≤ 10, and (5) the failure force of buckling F_crit = (4/l^2)√((G I_T)(E I_Z)/(1-ν^2))≥ fF, where I_Y=bh^3/12, I_Z=b^3h/12, I_T=I_Y+I_Z, and f is the safety factor. And σ_Y, E, ν, and G are the yield stress, Young's modulus, Poisson's ratio, and shear modulus of the beam's material, respectively. We use the settings from <cit.>, where l=0.5m, F=5kN, f=2, σ_Y=240MPa, E=216.62GPa, ν=0.27, and G=86.65GPa. As shown in Fig. <ref>, the feasible domain is a crescent-shaped region. Given only these constraints, it is unclear what appropriately tight bounds on the design variables should be.

In this experiment, we set the Gaussian kernel's length scale as 0.005, ϵ=0.3 and η=1.3. The initial point x^(0)=(b_0,h_0)=(0.05,0.05). The test samples are generated along a 100 × 100 grid in the region where b ∈ [0,0.02] and h ∈ [0.1,0.16].

After 242 iterations, the F1 score of AES reaches 0.933 and remains constant. Note that mostly the estimation error comes from the two sharp ends of the crescent-shaped feasible region (Fig. <ref>). This is because the kernel's assumption on function smoothness (, similar inputs should have similar outputs) causes the GP to have bad performance where the labels shift frequently. The similar problem also exists when using other classifiers like SVM, where a kernel is also used to enforce similar outputs between similar inputs. This problem can be alleviated by using a smaller kernel length scale. 







§ CONCLUSION


We presented a pool-based sampling method, AES, for identifying (possibly disconnected) feasible domains over an unbounded input space. Unlike conventional methods that sample inside a fixed boundary, AES progressively expands our knowledge of the input space under an accuracy guarantee. We showed that AES uses successive exploitation and exploration stages to switch between learning the decision boundary and searching for new feasible domains. To avoid increasing the pool size and hence the computation cost as the explored area grows, we proposed a dynamic local pool generation method that samples the pool locally at a certain location in each iteration.
We showed that at any point within the explored region, AES guarantees an upper bound ϵ of misclassification loss with a probability of at least 1-τ, regardless of the number of iterations or labeled samples. This means that AES can be used for real-time prediction of samples' feasibility inside the explored region. We also demonstrated that, compared to existing methods, AES can achieve comparable or higher accuracy without needing to set exact bounds on the input space.

Note that AES cannot be applied on input spaces where synthesizing a useful sample is difficult. For example, in an image classification task, we cannot directly synthesize an image by arbitrarily setting its pixels, since most of the synthesized images may be unrealistic and hence useless. Usually in such cases, we use real-world samples as the pool and apply bounded active learning methods (since we know the bounds of real-world samples). Or instead, we first embed the original inputs onto a lower-dimensional space, such that given the low-dimensional representation, we can synthesize realistic samples. We can then apply AES on that embedded space. This approach can be used for discovering novel feasible domains (, finding feasible inputs that are nonexistent in the real-world). We refer interested readers to a detailed introduction of this approach by <cit.>.

One limitation of AES is that the accuracy improves slowly at the early stage compared to bounded active learning methods. This is because AES focuses on only the explored region (which is small at the beginning), while bounded active learning methods usually do space-filling at first. In the situation where we want fast accuracy improvement at the beginning, one possible way of tackling this problem is by dynamically setting AES's hyperparameters. Specifically, since the expansion speed increases as ϵ or η decreases, we can accelerate AES's accuracy improvement at earlier stages by setting small values of ϵ and η, so that queries quickly fill up a larger region. Then to achieve high final accuracy, we can increase ϵ and η to meet the accuracy requirement.














































spbasic      


   

























Appendix A: Theorem Proofs




















§ PROOF OF THEOREM <REF>



According to Eq. <ref>, given an optimal query x^*, we have

    |f̅(x^*)|    = |k(x^*)^T ∇log p(y|f̂)| 
       = |k(x^*)^T ∇log[     Φ(y_1f_1);             ⋮; Φ(y_t-1f_t-1) ]| 
       = |k(x^*)^T [         y_1𝒩(f_1)/Φ(y_1f_1);                           ⋮; y_t-1𝒩(f_t-1)/Φ(y_t-1f_t-1) ]| 
    
       = | ∑_i=1^t-1 k(x^*,x^(i))y_i𝒩(f_i)/Φ(y_if_i)| 
    
       ≤∑_i=1^t-1| k(x^*,x^(i))y_i𝒩(f_i)/Φ(y_if_i)| 
    
       < ∑_i=1^t-1 k_m sign(y_i)y_i𝒩(f_i)/Φ(y_if_i)
       = k_m sign(y)^T [         y_1𝒩(f_1)/Φ(y_1f_1);                           ⋮; y_t-1𝒩(f_t-1)/Φ(y_t-1f_t-1) ]
       = k_m μ

where 

    k_m    = max_x^(i)∈ X_L k(x^*,x^(i)) 
       = exp(-min_x^(i)∈ X_Lx^*-x^(i)^2/2l^2) 
       = e^-δ^2/(2l^2)

and

    μ = sign(y)^T ∇log p(y|f̂)


Similarly,

    V(x^*)    = 1-k(x^*)^T(K+W^-1)^-1k(x^*) 
       > 1-(k_m1)^T (K+W^-1)^-1 (k_m1) 
       = 1-k_m^21^T(K+W^-1)^-11
       = 1-k_m^2 ν

where

    ν = 1^T(K+W^-1)^-11


Therefore for the optimal query x^* we have

    p_ϵ(x^*) = Φ(-|f̅(x^*)|+ϵ/√(V(x^*))) 
    > Φ(-k_m μ+ϵ/√(1-k_m^2 ν))


Both Theorem <ref> and <ref> state that p_ϵ(x^*)=τ, thus

    Φ(-k_m μ+ϵ/√(1-k_m^2 ν)) < τ


When τ=Φ(-ηϵ), we have

    k_m μ+ϵ/√(1-k_m^2 ν) > ηϵ


Plugging Eq. <ref> into Eq. <ref> and solving for the distance δ, we get

    δ < β l

where

    β=√(2logμ^2+η^2ϵ^2ν/ηϵ√(μ^2+(η^2-1)ϵ^2ν)-ϵμ)





§ PROOF OF THEOREM <REF>



Theorem <ref> states that the optimal query in the exploitation stage lies at the intersection of f̅(x)=0 and p_ϵ(x)=τ. By substituting Φ(-ηϵ) for τ, we have

    V(x^*) = 1/η^2

According to Eq. <ref>, we have V(x^*)>1-k_m^2ν. Combining Eq. <ref>, <ref>, and <ref>, we get 

    δ < δ_exploit = γ l

where

    γ = √(logη^2ν/η^2-1)





§ PROOF OF THEOREM <REF>



According to Eq. <ref>, the predictive variance of an optimal query x_exploit in the exploitation stage is

    V(x_exploit) = 1/η^2

While in the exploration stage, we have p_ϵ(x_explore)=τ at the optimal query x_explore (Theorem <ref>). And by applying Eq. <ref> and setting τ = Φ(-ηϵ), we have

    V(x_explore) = 1/η^2(1+|f̅(x_explore)|/ϵ)^2








Appendix B: Additional Experimental Results




















§ HOSAKI EXAMPLE
















We use the Hosaki example as an additional 2-dimensional example to demonstrate the performance of our proposed method. Different from the Branin example, the Hosaki example has feasible domains of different scales. Its feasible domains resemble two isolated feasible regionsa large “island” and a small one (Fig. <ref>). The Hosaki function is

    g(x)=(1-8x_1+7x_1^2-7/3x_1^3+1/4x_1^4)x_2^2e^-x_2

We define the label y=1 if x∈{x|g(x)≤ -1, 0<x_1,x_2<5}; and y=-1 otherwise. 



For AES, we set the initial point x^(0) = (3,3). We use a Gaussian kernel with a length scale l=0.4. The test set to compute F1 scores is generated along a 100 × 100 grid in the region where x_1 ∈ [-3,9] and x_2 ∈ [-3.5,8.5]. For NV and straddle, the input space bounds are shown in Tab. <ref>.



Table <ref> shows the final F1 scores and running time of AES, NV, and the straddle heuristic. Fig. <ref> shows the F1 scores and queries under different ϵ and η. Fig. <ref> compares the performance of AES and NV with different boundary sizes. Fig. <ref> shows the performance of AES and NV under Bernoulli and Gaussian noise.





§ RESULTS OF STRADDLE HEURISTIC



In this section we list experimental results related to the straddle heuristic. Specifically, Fig. <ref> shows straddle's F1 scores and queries using different sizes of input variable bounds, and the comparison with AES. Fig. <ref> shows the comparison of AES and straddle under noisy labels.





