Year: 2021

Abstract:
For pool-based active learning, in each iteration a candidate training sample is chosen for labeling by optimizing an acquisition function. In Bayesian classification, expected Loss Reduction (ELR) methods maximize the expected reduction in the classification error given a new labeled candidate based on a one-step-lookahead strategy. ELR is the optimal strategy with a single query; however, since such myopic strategies cannot identify the long-term effect of a query on the classification error, ELR may get stuck before reaching the optimal classifier. In this paper, inspired by the mean objective cost of uncertainty (MOCU), a metric quantifying the uncertainty directly affecting the classification error, we propose an acquisition function based on a weighted form of MOCU. Similar to ELR, the proposed method focuses on the reduction of the uncertainty that pertains to the classification error. But unlike any other existing scheme, it provides the critical advantage that the resulting Bayesian active learning algorithm guarantees convergence to the optimal classifier of the true model. We demonstrate its performance with both synthetic and real-world datasets.

text: For pool-based active learning, in each iteration a candidate training sample is chosen for labeling by optimizing an acquisition function. In Bayesian classification, expected Loss Reduction (ELR) methods maximize the expected reduction in the classification error given a new labeled candidate based on a one-step-lookahead strategy. ELR is the optimal strategy with a single query; however, since such myopic strategies cannot identify the long-term effect of a query on the classification error, ELR may get stuck before reaching the optimal classifier. In this paper, inspired by the mean objective cost of uncertainty (MOCU), a metric quantifying the uncertainty directly affecting the classification error, we propose an acquisition function based on a weighted form of MOCU. Similar to ELR, the proposed method focuses on the reduction of the uncertainty that pertains to the classification error. But unlike any other existing scheme, it provides the critical advantage that the resulting Bayesian active learning algorithm guarantees convergence to the optimal classifier of the true model. We demonstrate its performance with both synthetic and real-world datasets.

heading: 1 INTRODUCTION
text: In supervised learning, labeling data is often expensive and highly time consuming. Active learning is one field of research that aims to address this problem and has been demonstrated for sampleefficient learning with less required labeled data (Gal et al., 2017; Tran et al., 2019; Sinha et al., 2019). In this paper, we focus on pool-based Bayesian active learning for classification with 0- 1 loss function. Bayesian active learning starts from the prior knowledge of uncertain models. By optimizing an acquisition function, it chooses the next candidate training sample to query for labeling, and then based on the acquired data, updates the belief of uncertain models through Bayes’ rule to approach the optimal classifier of the true model, which minimizes the classification error.
In active learning, maximizing the performance of the model trained on queried candidates is the ultimate objective. However, most of the existing methods do not directly target the learning objective. For example, Maximum Entropy Sampling (MES) or Uncertainty Sampling, simply queries the candidate with the maximum predictive entropy (Lewis & Gale, 1994; Sebastiani & Wynn, 2000; Mussmann & Liang, 2018); but the method fails to differentiate between the model uncertainty and the observation uncertainty. Bayesian Active Learning by Disagreement (BALD) seeks the data point that maximizes the mutual information between the observation and the model parameters (Houlsby et al., 2011; Kirsch et al., 2019). Besides BALD, there are also other methods reducing the model uncertainty in different forms (Golovin et al., 2010; Cuong et al., 2013). However, not all the model uncertainty will affect the performance of the learning task of interest. Without identifying whether the uncertainty is related to the classification error or not, these methods can be inefficient in the sense that it may query candidates that do not directly help improve prediction performance.
In this paper we focus on the active learning methods directly maximizing the learning model performance. There exist such active learning methods by Expected Loss Reduction (ELR) that aim to maximize the expected reduction in loss based on a one-step-look-ahead manner (Roy & McCallum, 2001; Zhu et al., 2003; Kapoor et al., 2007). The ELR methods can focus on only the uncertainty related to the loss function to achieve sample-efficient learning. In fact, ELR is the optimal strategy for active learning with a single query (Roy & McCallum, 2001). However, a critical shortcoming of previous ELR schemes is that none of them provide any theoretical guarantee regarding their longterm performance. In fact, since these methods are myopic and cannot identify the long-term effect of a query on the loss functions, without special design on the loss function, they may get stuck before reaching the optimal classifier. To the best of our knowledge, there is currently no method that directly maximizes the model performance while simultaneously guaranteeing the convergence to the optimal classifier.
Fig. 1a provides an example of binary classification with one feature where both BALD and ELR methods fail. In the figure, the red lines indicate the upper and lower bounds of the prediction probability of class 1, illustrating the model with higher probability uncertainty on the sides (x → ±4) than that in the middle (x = 0). Querying candidates on the sides will provide more information of the model parameters, and therefore is preferred in BALD. However, since the possible probabilities on the sides are always larger than or less than 0.5, querying candidates on the sides will not help reduce the classification error. On the other hand, ELR queries candidates that help reduce the classification error the most, so it prefers data in the middle whose optimal labels are uncertain given the prior knowledge. The performance shown in Fig. 1b agrees with our analysis. Fig. 1b shows the performance averaged over 1000 runs, with more details and discussions of the example included in Appendix C. BALD performs inefficiently at the beginning by querying points on both sides. On the other hand, the ELR method performs the best at the beginning, but becomes inefficient after some iterations (∼100), indicating some of its runs get stuck before reaching the optimal classifier. In this paper, we consider the algorithm to “get stuck” when the acquisition function value is 0 for all the candidates in the pool and the algorithm degenerates to uniform random sampling.
In this paper, we analyze the reason why ELR methods may get stuck before reaching the optimal classifier, and propose a new strategy to solve this problem. Our contributions are in four parts: 1. We show that ELR methods may get stuck, preventing active learning from reaching the optimal classifier efficiently. 2. We propose a novel weighted-MOCU active learning method that can focus only on the uncertainty related to the loss for efficient active learning and is guaranteed to converge to the optimal classifier of the true model. 3. We provide the convergence proof of the weightedMOCU method. 4. We demonstrate the sample-efficiency of our weighted-MOCU method with both synthetic and real-world datasets.

heading: 2 BACKGROUND
text: Optimal Bayesian classifier. Consider a classification problem with candidates x ∈ X and class labels y ∈ Y = {0, 1, . . . ,M − 1}. The predictive probability p(y|x, θ) is modeled with parameters
θ. Assume θ is uncertain with a distribution π(θ) within the uncertainty class Θ. The classification problem is to find a classifier ψ : X → Y , which assigns a predicted class label to a given candidate. The expected 0-1 loss of the classifier ψ for a candidate x, dependent on θ, is defined as Cθ(ψ, x), which can be derived to be the classification error: Cθ(ψ, x) = 1 − p(y = ψ(x)|x, θ). The optimal classifier with θ, ψθ is defined as the classifier minimizing the classification error: ψθ(x) = arg maxy p(y|x, θ). So we have: Cθ(ψθ, x) = minψ Cθ(ψ, x) = miny{1− p(y|x, θ)}. When there is model uncertainty with π(θ), an Optimal Bayesian Classifier (OBC) ψπ(θ) is the classifier that has the minimum expected loss over π(θ) (Dalton & Dougherty, 2013):
Eπ(θ)[Cθ(ψπ(θ), x)] = min ψ Eπ(θ)[Cθ(ψ, x)] = min y {1− p(y|x)} (1)
where p(y|x) = Eπ(θ)[p(y|x, θ)] is the predictive distribution. It’s easily to see ψπ(θ)(x) = arg maxy p(y|x).
Active learning. Active learning collects the training dataset D in a sequential way. For poolbased active learning, in each iteration, we choose a candidate x from the set of potential training samples X to query for the class label by optimizing an acquisition function U(x). Then, in the Bayesian setting, by including the observed data pair (x, y) to D, we update the posterior distribution based on Bayes’ rule. In each iteration, the acquisition function depends on the posterior distribution of model parameters π(θ|D). In the following discussion, to simplify notations, we omit D from the notations and use π(θ) and p(y|x) to respectively denote the posterior and predictive distributions conditioned on D. When a new observed data point is included, the distributions are updated by Bayes’ rule and the total probability rule as: π(θ|x, y) = π(θ)p(y|x,θ)p(y|x) and p(y′|x′, x, y) = Eπ(θ|x,y)[p(y′|x′, θ)]. The acquisition function of ELR methods in the Bayesian setting can be defined by the expected OBC prediction error reduction after observing the new pair (x, y) (Roy & McCallum, 2001):
UELR(x) = Ep(x′){Eπ(θ)[Cθ(ψπ(θ), x′)]− Ep(y|x)[Eπ(θ|x,y)[Cθ(ψπ(θ|x,y), x′)]]}, (2)
where p(x′) is the distribution over X , independent of θ and D. ELR methods assume that we use OBC as the classifier, and in each iteration we should choose the query that maximize the decrease in OBC prediction error. The first term in (2) is the OBC prediction error of ψπ(θ), and the second term is the expected prediction error of ψπ(θ|x,y), the one-step-look-ahead OBC, with respect to p(y|x). In the following section, we analyze why this acquisition function is sample-efficient as it directly targets at classification error reduction while ignoring irrelevant uncertainty with respect to the learning task; but it may get stuck before converging to the true optimal classifier (optimal classifier of the true model).

heading: 3 MOCU-BASED ACTIVE LEARNING

heading: 3.1 MEAN OBJECTIVE COST OF UNCERTAINTY
text: To analyze ELR methods, we borrow the idea of the Mean Objective Cost of Uncertainty (MOCU) for active learning with respect to the corresponding posterior π(θ). MOCU is a general objectiveoriented uncertainty quantification framework (Yoon et al., 2013). For active learning, MOCU can be defined as the expected loss difference between the OBC and the optimal classifier:
M(π(θ)) = Ep(x′)[Eπ(θ)[Cθ(ψπ(θ), x′)− Cθ(ψθ, x′)]] (3) = Ep(x′)[min
y′ {1− p(y′|x′)} − Eπ(θ)[min y′ {1− p(y′|x′, θ)}]]. (4)
The second line is derived by the definition of ψθ and (1). The first term in (3) is the OBC error as the loss. In the second term, ψθ is the optimal classifier with a specific θ. For the terms inside the expectation operator, we have Cθ(ψπ(θ), x′)− Cθ(ψθ, x′) ≥ 0. Therefore, the second term in (3) is a lower bound of the OBC prediction error. MOCU captures the difference between the OBC error and its lower bound. When MOCU is 0, the OBC converges to the true optimal classifier and we cannot reduce the OBC prediction error further. In that case, we say that OBC has reached the true optimal classifier.
As in ELR methods, we can define an acquisition function by the reduction of MOCU in a one-steplook-ahead manner:
UMOCU(x;π(θ)) =M(π(θ))− Ep(y|x)[M(π(θ|x, y))]. (5) We can show that the second term in (3), the lower bound of the OBC error, is cancelled in (5). The acquisition function (5) hence captures the expected reduction of the OBC error given new data and is equivalent to the ELR acquisition function (2). Expanding the second term in (5), we have:
Ep(y|x)[M(π(θ|x, y))] = Ep(x′){Ep(y|x)[Eπ(θ|x,y)[Cθ(ψπ(θ|x,y), x′)− Cθ(ψθ, x′)]]}. (6) Since ∑ y p(y|x)π(θ|x, y) = π(θ), as x is assumed to be independent of θ so that we have π(θ|x) = π(θ), we can rewrite the first term in (5) as:
M(π(θ)) = Ep(x′){Ep(y|x)[Eπ(θ|x,y)[Cθ(ψπ(θ), x′)− Cθ(ψθ, x′)]]}. (7)
Combining (6) and (7) and canceling the Cθ(ψθ, x′) terms (the lower bound of the OBC error), (6) can be derived as:
UMOCU(x;π(θ)) = Ep(x′){Ep(y|x)[Eπ(θ|x,y)[Cθ(ψπ(θ), x′)− Cθ(ψπ(θ|x,y), x′)]]}, (8) which is just the ELR acquisition function in (2). Therefore, we can conclude that MOCU-based methods are equivalent to ELR methods.
Another property we can observe from (8) is that UMOCU(x;π(θ)) ≥ 0. By definition, ψπ(θ|x,y) is the OBC with the minimum expected classification error over π(θ|x, y). Therefore, Eπ(θ|x,y)[Cθ(ψπ(θ|x,y), x′)] ≤ Eπ(θ|x,y)[Cθ(ψπ(θ), x′)] and we have UMOCU(x;π(θ)) ≥ 0, indicating collecting new data will reduce MOCU.

heading: 3.2 ANALYSIS OF ELR METHODS
text: In the following analysis, we assume that Θ contains the true model θr and π(θr) > 0. We first analyze ELR methods by the MOCU reduction to show that ELR and MOCU-based active learning ignores the uncertainty irrelevant to the OBC prediction. By that, we indicate that not all the model uncertainties directly affect the OBC prediction. Denote the contribution to the MOCU at point x as K(x, π(θ)) = Eπ(θ)[Cθ(ψπ(θ), x) − Cθ(ψθ, x)], so that M(π(θ)) = Ep(x)[K(x, π(θ))]. If K(x, π(θ)) = 0, then we have ∀θ ∈ supp(π), ψθ(x) = ψπ(θ)(x), i.e. arg maxy p(y|x, θ) = arg maxy p(y|x). This means that for all the possible models, the optimal predictions are the same, and the OBC prediction on x will not be affected by the remaining uncertainty of p(y|x, θ), if any. In fact, K(x, π(θ)) = 0 does not necessarily mean that there is no uncertainty associated with p(y|x, θ), for which it requires that the value of p(y|x, θ) is the same ∀θ ∈ supp(π), apparently a stronger statement than K(x, π(θ)) being 0. Therefore, not all the uncertainties of p(y|x, θ) are captured in MOCU whenK(x, π(θ)) = 0. We consider the uncertainty in p(y|x, θ) to be “objectiveirrelevant” to the OBC prediction if K(x, π(θ)) = 0. In the active learning procedure, when a new observation is obtained, it reduces the uncertainty of the parameter θ; and as a result, it reduces the uncertainty of p(y|x, θ) for each x ∈ X . If an observation only reduces objective-irrelevant uncertainty, the value of MOCU will not change. For example, in Fig. 1a, the uncertainty of p(y|x, θ) in the region close to x = ±4 is objective-irrelevant. Evaluating points at x→ ±4 will only reduce irrelevant uncertainty and it will not be considered in either MOCU- or ELR-based methods. That explains why in the first several active learning iterations, the ELR or MOCU-based active learning can be more efficient than the methods guided by total uncertainty reduction, such as BALD.
Now we explain why ELR methods may get stuck before the OBC converges to the true optimal classifier. When we have ∀x ∈ X , UMOCU(x;π(θ)) = 0 and assume the tie is broken randomly, the acquisition function will suggest any random candidate in the pool. When that happens, we say that ELR methods get stuck if the OBC has not reached the true optimal classifier; i.e.,M(π(θ)) is still larger than 0.
Since p(y′|x′) = Eπ(θ)[p(y′|x′, θ)] is a linear function of π(θ), the term miny′{1− p(y′|x′)} in (4) is the minimum among M linear functions, and thus a concave piece-wise linear function. Within each linear piece, ψπ(θ)(x′) = arg maxy′ p(y
′|x′) are the same for different π(θ). The second term Eπ(θ)[miny′{1 − p(y′|x′, θ)}] in (4) is a linear function of π(θ). Subtracting it from the first term and averaging the resulting difference over p(x′) maintain the concavity and the piece-wise linearity.
Therefore, MOCU defined in (4) is a concave piece-wise linear function of π(θ). Moreover, within a linear piece of MOCU, ψπ(θ)(x′) = arg maxy′ p(y
′|x′), i.e. the OBC prediction, is the same for each of x′ ∈ X . To gain some intuition, we study a binary classification problem with the uncertainty class of two possible models Θ = {θ1, θ2} and a candidate pool of two training samples to query: X = {x1, x2}. Further details of the model setup can be found in Appendix D. Since π(θ1) = 1− π(θ2), we can express the MOCU function as a univariate function of π(θ1) as shown in Fig. 2. It is clear that the MOCU function is a concave piece-wise linear function.
Since π(θ) = Ep(y|x)[π(θ|x, y)], from (5), the acquisition function is defined as M[Ep(y|x)[π(θ|x, y)]] − Ep(y|x)[M(π(θ|x, y))]. Based on the concavity of MOCU M(·) and Jensen’s inequality, we have the acquisition function UMOCU(x;π(θ)) ≥ 0. The equality holds if for all y ∈ Y , π(θ|x, y) falls into the same linear piece of MOCU. In this case, the single query (x, y) cannot provide enough evidence to shift the OBC prediction, so that arg maxy′ p(y
′|x′, x, y) = arg maxy′ p(y
′|x′) for each of x′ ∈ X , even though p(y′|x′, x, y) 6= p(y′|x′). In Fig. 2, we have shown in the binary classification problem there exists such a case that π̃(θ1|x1, y1 = 0) and π̃(θ1|x1, y1 = 1) are within the interval of the same linear piece of the corresponding MOCU function. When MOCU is larger than 0, if all candidates cannot provide enough evidence to change the OBC predictions, ELR and MOCU-based methods will get stuck before converging to the true optimal classifier. This is due to the myopic nature of the acquisition function ignoring the long-term effect of querying each candidate.
In summary, ELR methods are efficient by ignoring objective-irrelevant uncertainty. But if sampling one data point can only provide little information and cannot help improve OBC prediction in the current iteration, they will ignore its long-term effect on prediction performance. As a result, they may get stuck before converging to the optimal classifier. To keep the efficient sampling property by ignoring objective-irrelevant uncertainty but avoid getting stuck, we propose a one-step-look-ahead acquisition function based on a weighted version of MOCU, which can capture the change of the predictive probability from one-step query candidates. If that change can potentially shift the OBC predictions in the long run, our acquisition function will have a positive value, and thereby avoid the issues that ELR methods suffer from.

heading: 3.3 WEIGHTED MOCU-BASED ACTIVE LEARNING
text: In this section, we propose a modified MOCU-based acquisition function that has the theoretical guarantee to converge to the optimal classifier. Specifically, we propose a modified MOCU function that multiplies a weight with each loss difference between the OBC ψπ(θ) and the optimal classifier
ψθ in the original MOCU definition:
Mw(π(θ)) = Ep(x′){Eπ(θ){w(π(θ), x′, θ)[Cθ(ψπ(θ), x′)− Cθ(ψθ, x′)]}}, (9)
where w(π(θ), x′, θ) > 0 is the weighting function. The corresponding acquisition function is:
Uw(x;π(θ)) =Mw(π(θ))− Ep(y|x)[Mw(π(θ|x, y))]. (10)
In (9), as more data are collected and the model parameter distribution π(θ) changes, w(π(θ), x′, θ) will change accordingly. The change of w(π(θ), x′, θ) cannot affect the value of the weighted MOCU if Cθ(ψπ(θ), x′) − Cθ(ψθ, x′) = 0, ∀θ ∈ supp(π(θ)), indicating the uncertainty at x′ is objective-irrelevant. This makes sure that the acquisition function based on the weighted MOCU will inherit the property of MOCU-based active learning to directly target at classification error reduction while ignoring irrelevant uncertainty. On the other hand, by introducing the predictive probability into the weighting functions, the probability change from one-step samples can be captured by the weighted-MOCU based acquisition function such that it can have theoretical convergence guaranteed to the optimal classifier as shown below.
We would like to emphasize that there are also active learning algorithms, such as the ones based on the cyclic sampling and -greedy policies (Hoang et al., 2014), that can almost surely converge to the true model, and as a result, the OBC converges to the true optimal classifier. However, these policies focus on the total uncertainty reduction to derive the full knowledge of the true model, which is unnecessary and therefore inefficient, since we only need the knowledge of the true optimal classifier if the classification performance is the primary concern. Unlike such policies, our weighted-MOCU based policy directly reduces the objective uncertainty affecting classification, and as a result, it is much more efficient by focusing only on those queries that are helpful for improving the prediction. As a result, our proposed algorithm guarantees efficiency both in the short term as well as in the longer term.
In the following, we design a weighting function to make Mw(π(θ)) = 0 if and only if ∀x ∈ X , Uw(x;π(θ)) = 0 and show that active learning based on this weighted MOCU converges to the optimal classifier. Specifically, we propose the following weighting function:
w(π(θ), x′, θ) = 1− c ·K(x′, π(θ)), with (11)
K(x′, π(θ)) = Eπ(θ)[Cθ(ψπ(θ), x′)− Cθ(ψθ, x′)] (12) = min
y′ Eπ(θ)[1− p(y′|x′, θ)]− Eπ(θ)[min y′ (1− p(y′|x′, θ)] (13)
= Eπ(θ)[max y′ p(y′|x′, θ)]−max y′ p(y′|x′), (14)
where 0 < c ≤ 1 is a parameter controlling the approximation of the weighted MOCU to the original MOCU, with smaller c giving a better approximation. The choice of c depends on the specific classification problem and the total query budget. Methods using a smaller c approximate the ELR methods better, hence they will perform well in the first several iterations but may converge slowly in the long run. On the other hand, when c is closer to 1, the acquisition function weighs more heavily on long-term benefits. It is clear that K(x′, π(θ)) ≥ 0 by (13). For binary classification, maxy′ p(y
′|x′) ≥ 0.5. As Eπ(θ)[maxy′ p(y′|x′, θ)] ≤ 1, from (14), we have K(x′, π(θ)) ≤ 0.5, demonstrating that the weighting function in (11) satisfies the requirementw(π(θ), x′, θ) ≥ 0.5 > 0. Note that this simple weighting function does not change with respect to the model parameter values. Substituting it into the weighted MOCU expression, we have:
Mw(π(θ)) = Ep(x′){(1− cK(x′, π(θ))) ·K(x′, π(θ))}, (15)
which is a strictly concave function of K. We also illustrate the weighted-MOCU function in Fig. 2 for the same example in Section 3.2. As shown in the figure, a smaller c provides better approximation to the MOCU function, and all the weighted MOCU functions are strictly concave functions of π(θ1) instead of being piece-wise linear, which guarantees that the acquisition function Uw(x1; π̃(θ)) is positive. In general, weighted MOCU is strictly concave along most of the directions and only changes linearly along the directions that K(x, π(θ)) is constant for x ∈ X , which correspond to the queries that only reduce irrelevant uncertainties. Such a property can guarantee the convergence to the true optimal classifier.
Before presenting the theoretical convergence guarantee of the weighted-MOCU based active learning, we summarize the computation of our weighted-MOCU based acquisition function in Algorithm 1, which can replace ELR and MOCU-based acquisition functions in Bayesian active learning algorithms with the pseudo-code given in Appendix B. We estimate the computational complexity of Algorithm 1 for the discrete feature and parameter spaces. Assume that the size of the discrete feature space is Nx = |X | and the size of the uncertainty set of classifiers is Nθ = |Θ|. We study the complexity of calculating the weighted MOCU. In the WMOCU function, the OBC error evaluation in line 19 is called for O(NxNθ) times. In ACQUISITIONFUN, WMOCU is called for constant times. Hence, the total complexity of calculating the acquisition function in weighted-MOCU based active learning is O(NxNθ). Compared with the ELR method, there is O(Nx) additional computation associated with computing the weight (1 − cK) in line 26. Hence, the incurred computational complexity is of the same order as the original ELR and MOCU-based methods.
Algorithm 1 Calculation for Weighted-MOCU based Acquisition Function 1: function ACQUISITIONFUN(x, πθ|D, c) 2: wmocu current =WMOCU(πθ|D) 3: wmocu next = 0 4: for y in {0, 1} do 5: for θ in Θ do 6: Generate array p(θ, y|D,x) = πθ|D · p(y|x, θ) 7: end for 8: p(y|D,x) = ∑ θ p(θ, y|D,x)
9: πθ|D,x,y = p(θ, y|D,x)/p(y|D,x) 10: wmocu next = wmocu next+ p(y|D,x) ·WMOCU(πθ|D,x,y, c) 11: end for 12: return wmocu current− wmocu next 13: end function
14: function WMOCU(πθ|D, c) 15: wmocu = 0 16: for x′ in X do 17: bayesian error = 0 18: for θ in Θ do 19: bayesian error = bayesian error + πθ|D · (1−maxy′ p(y′|x′, θ)) 20: end for 21: for y′ in {0, 1} do 22: p(y′|D,x′) = ∑ θ πθ|D · p(y′|x′, θ) 23: end for 24: obc error = 1−maxy′ p(y′|D,x′) 25: K = obc error − bayesian error 26: wmocu = wmocu+ p(x′) · [(1− cK)K] 27: end for 28: return wmocu 29: end function
Theoretical convergence guarantee. Now we show that if active learning for a binary classification problem is guided by the acquisition function defined by (10) and (11), MOCU will converge to 0 almost surely and hence the procedure will converge to learning the optimal classifier of the true model. We assume that both X and Θ are discrete with finite elements; the true model parameter θr ∈ Θ and the prior distribution π0(θ) over Θ satisfies π0(θr) > 0. We denote the posterior by πn(θ) and predictive probability pn(y|x) in the n-th weighted MOCU based active learning iteration, respectively. In the following, we give important lemmas first. All the proofs of the presented lemmas can be found in Appendix A.
Lemma 1 Given π(θ),M(π(θ)) = 0 if and only ifMw(π(θ)) = 0.
Lemma 1 indicates that ifMw(π(θ)) = 0, the OBC ψπ(θ) converges to the optimal classifier ψθr as explained in the first paragraph in Section 3.1.
Lemma 2 Define G(x′, π(θ)) = (1 − cK(x′, π(θ)))K(x′, π(θ)), 0 < c ≤ 1. G(x′, π(θ)) is a concave function of π(θ).
It is important to choose a weighting scheme that renders a concave function G as it guarantees the acquisition function to be larger than or equal to 0, so that adding a new observation helps to reduce weighted MOCU to effectively guide active learning.
Lemma 3 ∀x ∈ X , Uw(x;π(θ)) ≥ 0.
Lemma 4 At the n-th active learning iteration, if Uw(x;πn(θ)) = 0, ∀x ∈ X ,Mw(πn(θ)) = 0.
This lemma states that if the acquisition function values of all candidates with respect to π(θ) are 0, the weighted MOCU is 0. By Lemma 1, so is MOCU. With these, we can conclude that the OBC with respect to π(θ) has converged to the optimal classifier. This is significant when comparing with original ELR and MOCU-based methods as we have shown that this is not the case for them, which may get stuck earlier and therefore lose the long-term efficiency.
Lemma 5 If following some policy a candidate x is measured infinitely often almost surely, then limn→∞ U w(x;πn(θ)) = 0 almost surely.
Intuitively, if a candidate has been measured many times, there is no benefit to measure it again.
With these lemmas, we can prove the convergence of weighted-MOCU based active learning:
Theorem 1 Assume that both X and Θ are discrete with finite elements, the true model parameter θr ∈ Θ and the prior distribution π0(θ) over Θ satisfies π0(θr) > 0; then for the active learning algorithm defined by the acquisition function (10), we have limn→∞M(πn(θ)) = 0 almost surely.
Proof. As the number of active learning iterations n → ∞, following the acquisition function (10), some of the candidates can be measured infinite times. Define XA ⊂ X as the set whose candidates have been measured infinite times. Denote the measuring sequence of the candidates following (10) as {xn}, we have: ∃N, s.t. ∀n > N, xn ∈ XA. Based on Lemma 5,
limn→∞ U w(xn;π n(θ)) = 0.
On the other hand, since with the weighted MOCU Uw(xn;π n(θ)) = maxx∈X U w(x;πn(θ)), then limn→∞ U w(xn;π
n(θ)) = 0 indicates that ∀x ∈ X , Uw(x;πn(θ)) uniformly converges to 0. Based on Lemma 4, limn→∞Mwn = 0 and we can conclude the proof with Lemma 1.

heading: 4 EMPIRICAL RESULTS
text: We benchmark our weighted-MOCU method with other active learning algorithms, including random sampling, MES (Sebastiani & Wynn, 2000), BALD
(Houlsby et al., 2011) and ELR (Roy & McCallum, 2001), on both simulated and real-world classification datasets. In the following experiments, we set c = 1 for the weighted MOCU function. The code for our experiments is made available at https://github.com/QianLab/WMOCU_AL.
Simulated experiments. In addition to the one-dimensional simulated example introduced in Section 1, we test our model on a similar simulation setting as the block in the middle dataset in (Houlsby et al., 2011), where noisy observations with flip error are simulated in a block region on the decision boundary. We generate data based on a two-dimensional Bayesian logistic regression model: p(y = 1|x,w, b) = 1
1+exp(−wTx−b) with x ∈ [−4, 4] 2. The block region is within [−0.5, 0.5]2
with the flip error rate equal to 0.3. For the model parameter prior, w1 ∼ U(0.3, 0.8) is uniformly distributed and w2 ∼ U(−0.25, 0.25) and b ∼ U(−0.25, 0.25); w1, w2 and b are independent. We randomly sample 100 particles from the parameter prior with one of the particles as the true model parameter. The five active learning algorithms are compared for 500 iterations by the OBC
error with respect to the testing data generated from the true model. We repeat the simulations for 500 runs and plot the average performance with standard deviation bars in Fig. 3. The error regret is defined as the error difference between the OBC and the true optimal classifier. From the figure,
MES simply chooses the candidates with the predictive probability closest to 0.5, it can sample many noisy observations from the block region. ELR performs well in the first several iterations but poorly after 200 samples. Our weighted MOCU performs the best.
We have also benchmarked our weighted-MOCU based method with other active learning methods for a synthetic multi-class classification problem. We assume that the probabilistic model p(y|x, σ2y) = fy(x, σ2y)/ ∑ y′ f(x, σ 2 y′) with x ∈ [−2, 2]2, y ∈ {0, 1, 2} and fy = exp(−(x − my)
2/2σ2y). We set my to be (0, 0), (1, 0), (0, 1)
for y = 0, 1, 2 respectively; and σ2y ∼ U(1, 5) being the uncertain parameters. Same as the previous binary classification experiment, we test for 300 runs and plot the average performance with standard deviations in Fig. 4. We can observe that ELR performs poorly in the long run while our Weighted MOCU has better empirical performance on par with BALD More results and discussion are in Appendix D & E.
Real-world benchmark experiments. We also present the results on the UCI User Knowledge dataset (Kahraman et al., 2013). The dataset includes 403 samples assigned to 4 classes (High, Medium, Low, Very Low) with each sample having five features in [0, 1]5. We have grouped the samples into two classes with 224 samples in High or Medium, 179 in Low or Very Low. We consider the first and fifth features for classification and equally divide the feature space into 4× 4 bins. For the i-th bin, the probability of candidates belonging to High or Medium is denoted by θi, 1 ≤ i ≤ 16 and θi’s are independent and θi ∼ Beta(αi, βi), with hyper-
parameters αi and βi. We present the results with the uncertainty class by setting αi = βi = 10 in eight randomly chosen bins and for the other bins, αi = 5, βi = 2 if the true frequency of High or Medium in the i-th bin is lower than 0.5 and αi = 2, βi = 5 otherwise. We have randomly drawn 150 samples from each class as the candidate pool and perform the five different active learning algorithms. We repeat the whole procedure 150 times and the average error rates are shown in Fig. 5. While ELR clearly gets stuck in this setup, our Weighted MOCU method can converge to the optimal classifier with less samples than all the competing methods. BALD performs poorly as the bins with α = β = 10 have less uncertainty but have more impact on OBC prediction and BALD fails to identify that. More comprehensive results and discussion, including results on the UCI Letter Recognition dataset (Dua & Graff, 2017), can be found in Appendix F.

heading: 5 CONCLUSIONS
text: We have identified potential convergence problems of existing ELR methods and proposed a novel active learning strategy for classification based on weighted MOCU. Our weighted MOCU directly targets at decreasing the classification error and ignores uncertainty irrelevant to the classification performance. More critically, it can capture continuous change in objective-relevant uncertainty. Hence, our new active learning can be efficient both at the beginning and in the long run with the guarantee of converging to the optimal classifier. Empirical results have demonstrated active learning guided by weighted MOCU leads to sample-efficient learning. Future work includes theoretical analysis of MOCU-guided active learning for multi-class classification, as well as developing optimization methods for active learning in continuous space.

heading: ACKNOWLEDGMENTS
text: X. Qian was supported in part by the National Science Foundation (NSF) Awards 1553281, 1812641, 1835690, and 1934904. 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.

heading: A. PROOFS OF LEMMAS
text: Proof of Lemma 1. Based on (3), since Cθ(ψπ(θ), x′) − Cθ(ψθ, x′) ≥ 0, so M(π(θ)) = 0 iff Cθ(ψπ(θ), x
′)−Cθ(ψθ, x′) = 0 ∀x′ ∈ X , ∀θ ∈ supp(π). In addition, in (9), w(π(θ), x′, θ) > 0, so Cθ(ψπ(θ), x
′) − Cθ(ψθ, x′) = 0 ∀x′ ∈ X , ∀θ ∈ supp(π) iffMw(π(θ)) = 0, which concludes the proof.
Proof of Lemma 2. In the following proof, we omit the argument x′ in G and K for simplicity. Owing to the concavity of the min operator, miny′ Eπ(θ)[1 − p(y′|x′, θ)] is a concave function of π(θ). With Eπ(θ)[miny′(1 − p(y′|x′, θ)] being a linear function of π(θ), based on (13), K(π(θ)) equals to a concave function subtracting a linear function and thus is also a concave function.
As analyzed in Section 3.2, 0 ≤ K(π(θ)) ≤ 0.5. We define T (κ) = (1 − cκ)κ, κ ∈ [0, 0.5], a strictly increasing and strictly concave function with 0 < c ≤ 1. G(π(θ)) = T [K(π(θ))] is a composite function of T and K. So we conclude the proof with the property of the concavity for the composite functions:
T [K(λπ1(θ) + (1− λ)π2(θ))] ≥ T [λK(π1(θ)) + (1− λ)K(π2(θ))] ≥ λT [K(π1(θ))] + (1− λ)T [K(π2(θ))]. (16)
The first inequality is because T is increasing and K is concave; and the second inequality holds as T is a concave function. Proof of Lemma 3. Since π(θ) = ∑ y p(y|x)π(θ|x, y), by Jensen’s inequality, we have G(x′, π(θ)) ≥ Ey|x[G(x′, π(θ|x, y))] as G is a concave function. So the weighted MOCU acquisition function:
Uw(x;π(θ)) = Ex′ [G(x′, π(θ))]− Ex′ [Ey|x[G(x′, π(θ|x, y))]] ≥ 0. (17)
Proof of Lemma 4. We will prove the contrapositive of the lemma: assumingMw(πn(θ)) > 0, ∃x ∈ X s.t. Uw(x;πn(θ)) > 0. Based on (15), Mw(πn(θ)) > 0 indicating ∃x ∈ X s.t. K(x, πn(θ)) > 0. It is sufficient to show that if K(x, πn(θ)) > 0, then Uw(x;πn(θ)) > 0. To prove that, we only need to prove G(x, πn(θ)) > Epn(y|x)[G(x, πn(θ|x, y))]; then by (17), Uw(x;πn(θ)) > 0. Since G is a concave function, we know G(x, πn(θ)) ≥ Epn(y|x)[G(x, πn(θ|x, y))]. With πn(θ) =∑ y p
n(y|x)πn(θ|x, y), we can rewrite (16) as: T [K(x, πn(θ))] ≥ T [Epn(y|x)[K(x, πn(θ|x, y))]] ≥ Epn(y|x)[T [K(x, πn(θ|x, y))]].
The second equality holds only if ∀y ∈ {0, 1}, K(x, πn(θ|x, y)) = K(x, πn(θ)), which means that to prove G(x, πn(θ)) > Ey|x[G(x, πn(θ|x, y))], we just need to show ∃y ∈ {0, 1}, K(x, πn(θ|x, y)) 6= K(x, πn(θ)). In the following proof, we will show ifK(x, πn(θ)) > 0, then ∃y ∈ {0, 1}, s.t. K(x, πn(θ|x, y)) 6= K(x, πn(θ)). Denote ŷ = arg maxy p n(y|x). By (14) we have:
K(x, πn(θ)) = ∑
θ∈supp(πn)
πn(θ)[max y p(y|x, θ)− p(ŷ|x, θ)]. (18)
Since K(x, πn(θ)) > 0, the parameter set Θno = {θ ∈ supp(πn) : arg maxy p(y|x, θ) 6= ŷ} is not empty. We only keep the nonzero terms in K:
K(x, πn(θ)) = ∑ θ∈Θo πn(θ)[max y p(y|x, θ)− p(ŷ|x, θ)]. (19)
For binary classification, ŷ = arg maxy p n(y|x), indicating that the predictive probability pn(ŷ|x) ≥ 0.5. For θ ∈ Θo, p(ŷ|x, θ) < 0.5, we have: if θ ∈ Θo, πn(θ|x, ŷ) = π n(θ)p(ŷ|x,θ) pn(ŷ|x) < πn(θ).
If we observe (x, ŷ) in (n+1)-th iteration, the updated posterior predictive probability pn(ŷ|x, {x, ŷ}) ≥ pn(ŷ|x) ≥ 0.5 and therefore maxy pn(y|x, {x, ŷ}) = ŷ. Hence,
K(x, πn(θ|x, ŷ)) = ∑ θ∈Θo πn(θ|x, ŷ)[max y p(y|x, θ)− p(ŷ|x, θ)] < K(x, πn(θ)). (20)
Since K(πn(θ|x, ŷ), x) 6= K(πn(θ), x), we have G(x, πn(θ)) > Epn(y|x)[G(x, πn(θ|x, y))] and Uw(x;πn(θ)) = Ep(x′)[G(x′, πn(θ))]− Ep(x′)[Epn(y|x)[G(x′, πn(θ|x, y))]] ≥ p(x)[G(x, πn(θ))− Epn(y|x)[G(x, πn(θ|x, y))]] > 0. (21) This concludes our proof.
Proof of Lemma 5. Adding a new data point (x, y) to D, the posterior change is: πn(θ|x, y) = πn(θ)p(y|x,θ)
pn(y|x) . Define Θx = {θ ∈ Θ : p(y|x, θ) = p(y|x, θr)}. Denote Nx(n) as the times of the candidate x being queried at the n-th iteration. Based on the posterior consistency theory we have ∑ θ∈Θx π n(θ) a.s.−−→ 1 as Nx(n) → ∞ (Gelman et al., 2013). Since pn(y|x) =∑
θ∈Θ π n(θ)p(y|x, θ), we have limn→∞ pn(y|x) a.s.−−→ p(y|x, θr). Hence limn→∞ πn(θ|x, y) − πn(θ) = 0 almost surely, which indicates limn→∞ Uw(x;πn(θ)) = 0 almost surely.

heading: B. WEIGHTED-MOCU BASED ACTIVE LEARNING & COMPUTATIONAL COMPLEXITY
text: The pseudo-code of the general active learning procedure is provided in Algorithm 2. The function ACQUISITIONFUN can be acquisition functions of various methods, including weighted-MOCU, ELR, BALD, etc.
Computational complexity We study the complexity of the complete active learning procedure. As we analyzed in the main text for the computation of the weighted MOCU acquisition function, the WMOCU function is called for O(NxNθ) times. In ACQUISITIONFUN, WMOCU is called for constant times. Finally, in the main procedure, in each iteration, ACQUISITIONFUN is called for each x. Hence, the total complexity of Weighted MOCU-based active learning is O(TN2xNθ).
4 3 2 1 0 1 2 3 4 x
0.00
0.01
0.02
0.03
0.04
0.05
m ut
ua l i
nf or
m at
io n
(a) Acquisition function of BALD
4 3 2 1 0 1 2 3 4 x
0.00000
0.00001
0.00002
0.00003
0.00004
0.00005
0.00006
0.00007
de sig
n va
lu e
(b) Acquisition function of ELR Figure S1. The acquisition functions based on the model (22).

heading: C. DETAILS OF THE ONE-DIMENSIONAL ACTIVE LEARNING EXAMPLE IN INTRODUCTION
text: The example in the Introduction of the main text is a binary classification problem with y ∈ {0, 1} based on only one feature x ∈ [−4, 4]. The underlying discriminative model is based on:
pc(y = 1|x, a, b) = S(x) + (x, a, b)
S(x) = 0.6 exp (x)
1 + exp (x) + 0.2
(x, a, b) = a exp(−x2) + b[exp(−(x− 4)2) + exp(−(x+ 4)2)], (22)
Algorithm 2 General active learning procedure 1: function MAINPROCEDURE( ) 2: Set a discrete candidate set X , the probability array px, and iteration number T 3: Set the discrete parameter set Θ and the corresponding probability array πθ 4: Initialize the data set D = ∅ 5: πθ|D = πθ 6: for t = 1 to T do 7: for x in X do 8: Store ACQUISITIONFUN(x, πθ|D) to the array UX 9: end for 10: Optimize UX and find the maximum point x∗ 11: Obtain the label y∗ corresponds to x∗ and update D = D ∪ {x∗, y∗} 12: for θ in Θ do 13: Update πθ|D ∝ πθ|D · p(y∗|x∗, θ) 14: end for 15: X = X/{x∗} 16: end for 17: end function
where θ = (a, b)T is the uncertain parameter vector, with a and b independently uniformly distributed on the intervals [−0.1, 0.1] and [−0.2, 0.2] respectively. The discriminative model equals to a sigmoid function S(x) plus the perturbation (x, a, b), a mixed Gaussian function that changes with a and b, the uncertainty class of classifiers can be constructed by such deviations on S(x). The discriminative model has higher uncertainty near x ± 4, which depends on the value of b, than the uncertainty near x = 0, which depends on a. Value of a and b has negligible influence on the p(y = 1|x) near x± 4 and x = 0, respectively. So by observing data at x = ±4, the uncertainty on pc(y = 1|x = 0) will not be reduced significantly. In Figs. S1(a) and (b), we show how the acquisition functions of BALD and ELR change with respect to x. It is clear that the acquisition function of BALD at x = ±4 should have the largest value since p(y|x) has the highest uncertainty. On the other hand, since p(y|x = ±4) is always above or below 0.5, the specific value of p(y|x, a, b) will not affect the corresponding optimal Bayesian classifier (OBC) and therefore the loss reduction in Fig. S1(b) at x = ±4 is always 0; the acquisition function of ELR around x = 0 can be larger than 0, since knowing the specific value of p(y|x = 0, a, b) can reduce the classification error.

heading: D. DETAILS OF THE BINARY CLASSIFICATION EXAMPLE IN SECTION 3.2
text: In the binary classification problem, Θ = {θ1, θ2}, X = {x1, x2}. The probabilistic model setting for the two candidates is symmetric:
p(y1|x1, θ1) = (0.6, 0.4), p(y1|x1, θ2) = (0.3, 0.7) p(y2|x2, θ1) = (0.7, 0.3), p(y2|x2, θ2) = (0.4, 0.6)
There are three intervals corresponding to the linear function pieces of MOCU in Fig. 2: [0, 0.33], (0.33, 0.67] and (0.67, 1]. In the three intervals, ψπ(θ)(x1), the OBC predictions of x1 are 1, 1 and 0, respectively; ψπ(θ)(x2), the OBC predictions of x2 are 1, 0, and 0, respectively.
In Fig. 2 we set the prior π̃(θ1) = 0.15, then based on the Bayes’s rule we can obtain the posterior with the observations of (x1, y1). Based on the observation result of y1, the posteriors are π̃(θ1|x1, y1 = 0) = 0.2609 and π̃(θ1|x1, y1 = 1) = 0.0916, both of which fall into the first linear piece of MOCU.

heading: E. MULTI-CLASS CLASSIFICATION
text: Although we have shown in the main text that our weighted-MOCU can achieve good empirical performance of converging to OBC with the simulated multi-class classification experiment, active learning for multi-class classification problems can be complicated. The weighting function (10) adopted in the main text may not have the same theoretical convergence guarantee to the optimal
classifier if applied to multi-class classification problems. Here we just show a counter example, for which Lemma 4 does not hold if using the same weighting function.
Assume a three-class classification problem y ∈ {0, 1, 2}. The candidate pool only has one candidate X = {x} and the parameter set Θ = {θ1, θ2, θ3}. In addition we set the probabilistic model p(y|x, θ) and the prior π(θ) as shown in Tables S1 and S2, and calculate the posterior and posterior predictive probabilities. In the tables, yo denotes the one-step-look-ahead observation corresponding to x, and x is omitted for simplicity. Without loss generality, we just set the weighted MOCU parameter c = 1.
p(y|θ1) p(y|θ2) p(y|θ3) p(y) p(y|yo = 0) p(y|yo = 1) p(y|yo = 2) y = 0 0.4 0.4 0.4 0.4 0.4 0.4 0.4 y = 1 0.3 0.1 0.5 0.3 0.3 0.327 0.273 y = 2 0.3 0.5 0.1 0.3 0.3 0.273 0.327
Table S1. The probabilities of p(y|x, θ) and p(y|x, yo).
π(θ) π(θ|yo = 0) π(θ|yo = 1) π(θ|yo = 2) θ = θ1 0.8 0.8 0.8 0.8 θ = θ2 0.1 0.1 0.17 0.03 θ = θ3 0.1 0.1 0.03 0.17
Table S2. The prior and posterior of π(θ).
Here two properties in the setting are worth mentioning:
1. π(θ1) is close to 1 and as a result ∀yo ∈ {0, 1, 2}, we have maxy p(y) = maxy p(y|yo) = maxy p(y|θ1) = 0.4; 2. p(y|θ2) and p(y|θ3) are symmetric and π(θ2) = π(θ3), as a result ∀yo ∈ {0, 1, 2}, π(θ1) = π(θ1|yo) = 0.8 and therefore Eπ(θ)[maxy′ p(y|θ)] = Eπ(θ|yo)[maxy′ p(y|θ)] = 0.8 × 0.4 + 0.2 × 0.5 = 0.42.
Recall that the K function and weighted MOCU are:
K(π(θ)) = Eπ(θ)[max y′ p(y|θ)]−max y′ p(y), (23) Mw(π(θ)) = [1−K(π(θ))] ·K(π(θ)). (24) Therefore, we have ∀yo ∈ {0, 1, 2}, K(π(θ)) = K(π(θ|yo)) = 0.02 and Mw(π(θ)) = Mw(π(θ|yo)) > 0. On the other hand,
Uw(π(θ)) =Mw(π(θ))− Ep(yo)[M w(π(θ|yo))] = 0, (25)
which means that the algorithm may get stuck. Here we just give an extreme case where only one candidate is in the search pool, but it is straightforward to build a more practical example based on what we have shown here.
We can see from the example that, unlike in the cases of binary classification problems, the weighting function 1 − cK may remain unchanged for a single observation in multi-class problems. Because of this, the weighted-MOCU algorithm may get stuck. Since OBC prediction is the maximum of the predictive distribution p(y|x), the weight function is introduced to capture the changes of p(y|x), as that indicates the potential shift of OBC prediction in the long run. K is a function of maxy p(y|x), in binary case, maxy p(y|x) must change as p(y|x) changes. However, in multi-class problems, the probability of the optimal label maxy p(y|x) may remain unchanged, when the probability of other labels change, just like in the example above where maxy p(y) = maxy p(y|yo = 1). In the next section, we propose a weighting function that can capture the change of any element in p(y|x).

heading: F. ANOTHER WEIGHTED MOCU SCHEME FOR MULTI-CLASS CLASSIFICATION
text: To extend the weighted MOCU scheme suit for the multi-class problem, we propose a weight function that can capture the change of p(y|x). The weighting function is defined as the softmax of
p(y|x):
w(π(θ), x′, θ) = exp(maxy p(y|x))∑
i exp(p(yi|x)) , (26)
where p(y|x) is the posterior predictive distribution at the current active learning iteration. We compare this Weighted MOCU with other active learning algorithms empirically on the synthetic three-class classification problem and the performance comparison is shown in Fig. S2. This new Weighted MOCU (Weighted MOCU2) performs slightly better than other algorithms on this multiclass classification problem.
0 100 200 300 400 500 Iteration number
10 4
10 3
er ro
r r eg
re t
random MES BALD ELR Weighted_MOCU Weighted_MOCU2
Figure S2. The expected OBC error regret comparison between different active learning algorithms for the three-class classification problem.

heading: G. ADDITIONAL SYNTHETIC EXPERIMENTS
text: We run the same synthetic experiment of Fig. 3 with a different prior setting: w1 ∼ U(0.3, 0.8), w2 ∼ U(−0.02, 0.02) and b ∼ U(−0.25, 0.25), and the results is shown in Figure S3. The performance shows that only our Weighted MOCU method performs better than the random benchmark.
Here we benchmark different active learning strategies for OBC with another synthetic example. Assume the classification problem with two dimensional input features x = (x1, x2) ∈ R2 and binary class labels y ∈ {0, 1}. The computational model is derived by a decision boundary in a quadratic form: x2 = ax21 + bx1 + c, i.e. p(y = 1|x, a, b, c) = 1(x2 > ax21 + bx1 + c). The parameter vector θ = (a, b, c) ∈ R3 is uncertain and the true model is characterized by a true parameter θ∗. Unlike Monte Carlo sampling in the main text, here we consider a discrete grid setting for both input space and parameter space with discretization for each variable as follows: 1. x1 ranges in [−0.5, 0.5] with increment 0.05 2. x2 ranges in [0, 2] with increment 0.1. 3. a ranges in [-4.3, -3.8] with increment 0.05, 4. b ranges in [-0.25, 0.25] with increment 0.05, 5. c ranges in [1, 2] with increment 0.05.
For now, we simply assume that the distributions over the feature space and parameter space are all uniform to illustrate the effectiveness of MOCU-based active learning. With prior knowledge of the system of interest, knowledge-driven prior should be incorporated. Following the weightedMOCU based active learning algorithm in Algorithm 1, we can sequentially query the true system and reduce the model uncertainty in a way that maximally reduces the classification error of the corresponding OBC.
0 100 200 300 400 500 Iteration number
10 3
4 × 10 4
6 × 10 4er ro
r r eg
re t
random MES BALD ELR Weighted_MOCU
Figure S3. The expected OBC error regret comparison between different active learning algorithms on binary classification.
Now we assume that when querying the system, the class label is given with a heterogeneous random flipping error with the error probability being a function of x1: p(y = 1|z = 0) = p(y = 0|z = 1) = 0.3× (1− 4x21) + 0.1. Therefore, when x1 = 0, the flipping error is 0.4; and when x1 = ±0.5, the flipping error is 0.1. We have implemented the same methods as in the main text with 50 iterations and 100 runs, The active learning results are illustrated in Fig. S4. As we can see, in this figure, MES does not perform well as it cannot differentiate between model uncertainty and observation error. ELR performs similarly to BALD and our weighted-MOCU based method at the beginning, but then it gets stuck before finding the true boundary. BALD and our weighted MOCU perform similarly. This is because in this setting p(y|x, θ) is either 1 or 0, so there is no irrelevant uncertainty with which p(y|x, θ) is always larger or smaller than 0.5 but the value is uncertain. In addition to the average performance comparison, we deliberately choose one of the runs in which the ELR method gets stuck to better illustrate the difference between the existing ELR methods and the proposed weighted-MOCU based method. In this run, the randomly chosen parameters are (a = −3, b = 0, c = 1.9). Fig. S5(a) shows the error regret (the OBC error minus the true optimal classifier error) comparison, in which ELR gets stuck and the weighted-MOCU based method reaches 0. Notice that the y-axis is in the logarithm scale, so the vertical line in the WMOCU plot implies that the value turns to 0. Error regret equals to 0 indicates that the OBC classifier equals to the true optimal classifier, but in practice we don’t know the true optimal classifier, so we need the value of MOCU to quantify the expected error difference between OBC and the optimal classifier of each θ = (a, b, c). Fig. S5(b) shows the changes of MOCU value during the two active learning procedures. Not surprisingly, the MOCU value during the iterations of the ELR method also gets stuck, while the MOCU value in the iterations of the weighted-MOCU method continues to decrease. Fig. S5(c) shows the changes of the maximum value of acquisition function in each iteration. The acquisition function of ELR decrease to 0 after 22 iterations, and that explains why ELR gets stuck. On the other hand, the maximum acquisition function of WMOCU is always positive as the corresponding MOCU is positive, until it gets close to 10−16, which is the rounding error in floating point arithmetic. In theory, as the observation is noisy, we can not be sure of the optimal prediction. Therefore, the MOCU and the acquisition function of weighted-MOCU should always be positive, which is demonstrated in the figures.
We have also performed an experiment to show the algorithm performance change under different noise levels. We set the flipping error rate as p(y 6= z|x) = × (1 − 4x21) + , 0 ≤ ≤ 0.25. Therefore, when x1 = 0, the flipping error is 2 ; and when x1 = ±0.5, the flipping error is . We perform the same methods with 100 iterations and 100 runs on the noise level = 0.05 and = 0.25. The resulting active learning performance curves are illustrated in Fig. S6. We can
0 10 20 30 40 50 Iteration number
10 4
10 3
10 2
10 1
er ro
r
random MES BALD ELR Weighted_MOCU
Figure S4. The expected OBC error comparison between different active learning algorithms in the setting with heterogeneous observation error.
0 10 20 30 40 50 Iteration number
10 2
10 1
er ro
r r eg
re t
ELR Weighted_MOCU
(a) Error regret
0 10 20 30 40 50 Iteration number
10 8
10 6
10 4
10 2
M OC
U
ELR Weighted_MOCU
(b) MOCU value
0 10 20 30 40 50 Iteration number
10 14
10 11
10 8
10 5
10 2
M ax
a cq
ui sit
io n
fu nc
tio n
ELR Weighted_MOCU
(c) Acquisition function Figure S5. Comparison of ELR and weighted MOCU on a specific run
0 20 40 60 80 100 Iteration number
10 4
10 3
10 2
10 1
er ro
r r eg
re t
random MES BALD ELR Weighted_MOCU
(a) Noise level = 0.05
0 20 40 60 80 100 Iteration number
10 2
10 1
er ro
r r eg
re t
random MES BALD ELR Weighted_MOCU
(b) Noise level = 0.25 Figure S6. Active learning algorithm performance comparison with different noise levels
see from the figure that the performance of MES degrades significantly with high noise while the performance of other methods does not appear to be very sensitive to the increasing noise level. .

heading: H. REAL-WORLD BENCHMARK EXPERIMENTS.
text: We here present the complete results on the UCI User Knowledge dataset (Kahraman et al., 2013). In addition to the uncertainty class setup in the main text, we have tested two other setups of hyperparameter values: 1) ‘uniform prior’ with αi = βi = 1, and 2) ’good prior’ with αi = βi = 10 in eight bins chosen randomly, for other bins αi = 5, βi = 2 if the true frequency of High or Medium
0 5 10 15 20 25 30 Iteration number
0.0
0.1
0.2
0.3 0.4 er ro r
random MES BALD ELR Weighted_MOCU
(a) Uniform prior
0 10 20 30 40 50 60 Iteration number
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40
er ro
r
random MES BALD ELR Weighted_MOCU
(b) Good prior Figure S7. Classification error rate comparison on UCI User Knowledge dataset
2 4 6 8 10 12 14 16 Iteration number
0.02
0.10
er ro
r r at
e
random MES BALD ELR Weighted_MOCU
(a) Performance of letter E vs. F classification
2 4 6 8 10 12 14 16 Iteration number
0.01
0.10
er ro
r r at
e
random MES BALD ELR Weighted_MOCU
(b) Performance of letter P vs. D classification Figure S8. Classification error rate comparison on UCI Letter Recognition dataset
in the i-th bin is higher than 0.5 and αi = 2, βi = 5 if the frequency is lower than 0.5. We also randomly draw 150 samples from each class as the candidate pool and perform the five different active learning algorithms. We repeat the whole procedure 150 times and the average error rates are shown in Fig. S7. In both Fig. S7a and Fig. S7b, ELR performs the best in these two setups while our Weighted MOCU performs similarly. BALD performs reasonably in Fig. S7a but it again performs poorly in Fig. S7b. This is because the bins with α = β = 10 have less uncertainty but have more impact on OBC prediction and BALD fails to identify that in this setup again.
We also present the results on the UCI Letter Recognition dataset (Dua & Graff, 2017). Letter Recognition is a multi-class classification dataset with each sample having 16 numerical features generated from typed images of the capital letters in the English alphabet. We select two pairs of hard-to-distinguish letters: E vs. F and D vs. P. The total number of training samples is 1543 and 1608 for E vs. F and D vs. P, respectively. Active learning algorithms are applied with Bayesian logistic regression models. We randomly take 100 data points first to construct the prior, and use the rest of the data as the pool to test the five active learning algorithms. For prior construction, we train a logistic regression model on the 100 data points and take the trained parameters as the mean of a normal distributed prior with the variance equal to 1. Then we sample 1000 particles from the prior as the uncertain parameter set. We repeat the whole procedure 100 times and the average error rates are shown in Fig. S8. Unlike the synthetic datasets, the real-world datasets have no corresponding true models. We can only find the optimal models that approximate the data best. However, we can still see the trends of different algorithms. Compared with random sampling, all the algorithms quickly converge to the optimal models. ELR performs the best in the first several iterations, while converges slowly in the latter iterations. Our weighted MOCU based method is again demonstrated to converge faster than other competing methods.
It is clear from all our experiments for both simulated and real-world data that, in addition to its theoretical guarantee for active learning with OBC, our weighted MOCU method has achieved consistently better or similar empirical performance compared to the best performing ones among the
existing pool-based active learning methods, approaching the corresponding OBCs faster with fewer labeled samples.

Review summaries:
This paper studies the label solicitation strategy in active learning. In particular, it focuses on the expected loss reduction (ELR) strategy, analyzes its problem, and modifies the original ELR method to make sure the active learner converges to the optimal classifier along learning iterations. The paper provides theoretical guarantees on the new method’s convergence. In the experiment, the proposed method is evaluated on synthetic data and UCI data. The improvement margin over the existing method is very limited.

This paper provides an interesting algorithm to address the previous Bayesian active learning query strategy in (binary) classification. By the simple modification, the algorithm can overcome the drawbacks of ELR in the convergence to the optimal classifier parameterized by $\theta_r$. In experiments, the proposed algorithm can achieve the advantages of ELR and BALD simultaneously.