On Statistical Bias In Active Learning: How and When to Fix It
Authors: Sebastian Farquhar
Yarin Gal
Tom Rainforth
Venue: ICLR 2021 Spotlight (2021)
Keywords: Active Learning
Monte Carlo
Risk Estimation

Abstract: Active learning is a powerful tool when labelling data is expensive, but it introduces a bias because the training data no longer follows the population distribution. We formalize this bias and investigate the situations in which it can be harmful and sometimes even helpful. We further introduce novel corrective weights to remove bias when doing so is beneficial. Through this, our work not only provides a useful mechanism that can improve the active learning approach, but also an explanation for the empirical successes of various existing approaches which ignore this bias. In particular, we show that this bias can be actively helpful when training overparameterized models---like neural networks---with relatively modest dataset sizes.

Published as a conference paper at ICLR 2021
ON STATISTICAL BIAS IN ACTIVE LEARNING: How AND WHEN TO FIX IT
Sebastian Farquhar!", Yarin Gal', Tom Rainforth
University of Oxford, fOATML, Department of Computer Science; 'Deaarmeent of Statistics
ABSTRACT
Active learning is powerful tool when labelling data is expensive, but it introduces a bias because the training data no longer follows the population distribution. We formalize this bias and investigate the situations which can be harmful and sometimes even helpful. We further introduce novel corrective weights to remove bias when doing so is beneficial. Through this, our work not only provides a useful mechanism that can improve the active learning approach, but also an explanation of the empirical successes of various existing approaches which ignore this bias. In particular, we show that this bias can be actively helpful when training overparameterized models- neural networks with relatively little data.
INTRODUCTION
In modern machine learning, unlabelled data can be plentiful while labelling requires scarce resources and expert attention, for example medical imaging or scientific experimentation. A promising solution to this is active cetrning-pickinne the most informative datapoints to label that will hopefully let the model be trained in the most sample-efficient way possible (Atlas et al. 1990 Settles 2010).
However, active learning has a complication. By picking the most informative labels, the acquired dataset is not drawn from the population distribution. This sampling bias, noted by e.g.. MacKay (1992); Dasgupta & Hsu (2008), is worrying: key results in machine learning depend on the training data being identically and independently distributed (i.i.d.) samples from the population distribution. For example, we train neural networks by minimizing a Monte Carlo estimator of the population risk. If training data are actively sampled, that estimator is biased and optimize the wrong objective. The possibility of bias in active learning has been considered by c.g., Be.ggeggll et al. (2009); Chu ct al. (20TT): Ganti & Gray (012)) but the full problem is not well understood. In particular, methods that remove active learning bias have been restricted to special cases, so it has been impossible to even establish whether removing active learning bias is helpful or harmful in typical situations.
To this end, we show how to remove the bias introduced by active learning with minimal changes to existing active learning methods. As stepping stone, we build a Plain Unbiased Risk Estimator, RPURE, which applies corrective weighting to actively sampled datapoints in pool-based active learning. Our Levelled Unbiased Risk Estimator, PLURE, builds on this and has lower variance and additional desirable finite-sample properties. We prove that both estimators are unbiased and consistent for arbitrary functions, and characterize their variance.
Interestingly, we find-both theoretically and empirically-that our bias corrections can simultane- ously also reduce the variance the estimator, with these gains becoming larger for more effective acquisition strategies. We show that, in turn, these combined benefits can sometimes lead to signif- icant improvements for both model evaluation and training. The benefits are most pronounced in underparameterizee models where each datapoint affects the learned function globally. For example, in linear regression adopting our weighting allows better estimates of the parameters with less data.
On the other hand, in cases where the model is overparameterized and datapoints mostly affect the learned function locally-like deep neural networks- we find that correcting active learning bias can be ineffective or even harmful during model training. Namely, even though our corrections typically produce strictly superior statistical estimators, we find that the bias from standard active learning can actually be helpful by providing regularising effect that aids generalization. Through this, our work explains the known empirical successes of existing active learning approaches for training deep models (Gal et al.) 30176, Shhn et al. 2018), despite these ignoring the bias this induces.
"Equal contribution. Corresponding author sebastia an. farguhartcs. ox. ax.ac.u. uk.

---

Published as a conference paper at ICLR 2021
To summarize, main contributions are:
1. We offer formalization of the problem of statistical bias in active learning.
2. We introduce active learning risk estimators, RPURE and RLURE, and prove both are unbiased, consistent, and with variance that can be less than the naive (biased) estimator.
3. Using these, we show that active learning bias can hurt in underparameterized cases like linear regression but help in overparameterized cases like neural networks and explain why.
BIAS IN ACTIVE LEARNING
We begin by characterizing the bias introduced by active learning. In supervised learning, generally, we aim find a decision rule fo corresponding to inputs, x, and outputs, y, drawn from a population data distribution Paata (x. y) which, given a loss function L(y, fo (x)), minimizes the population risk:
r Ex [C(y, fo())]]
The population risk cannot be found exactly, so instead we consider the empirical distribution for some dataset of N points drawn from the population. This gives the empirical risk: an unbiased and consistent estimator of when the data are drawn i.i.d from Pdata and are independent of A,
C(yn, fo(x)))
In pool-based active learning (Lewis & Gale, 1994; Settles 2010), we begin with a large unlabelled dataset, known as the pool dataset D pool {x,, S n S N), and sequentially pick the most useful points for which to acquire labels. The lack of most labels means we cannot evaluate Å directly, so we use the sub-sample empirical risk evaluated using the M actively sampled labelled points:
R= >
M m=1 flym: fo(x)))
Though almost all active learning research this estimator (see Appendix D). it is not an unbiased estimator of either R or when the M points are actively sampled. Under active-i.e. non-uniform- sampling the M datapoints are not drawn from the population distribution, resulting in a bias which we formally characterize in $4 See Appendix for a more general overview of active learning.
Note an important distinction between what we will call "statistical bias" and "overfitting bias." " The bias from active learning above a statistical bias in the sense that using R biases our estimation of r, regardless 0. As such, optimizing 0 with respect to Rt induces bias into our optimization of In turn, this breaks any consistency guarantees for our learning process: if we keep M/N fixed, take M 00, and optimize for 6, we no longer get the optimal é that minimizes r. Almost all work on active learning for neural networks currently ignores the issue of statistical bias.
However, even without this statistical bias, indeed even if we use A directly, the training process itself also creates overfitting bias: evaluating the risk using training data induces dependency between the data and 0. This is why we usually evaluate the risk on held-out test data when doing model selection. Dealing with overfitting bias is beyond the scope of our work as this would equate to solving the problem of generalization. The small amount of prior work which does consider statistical bias in active learning entirely ignores this overfitting bias without commenting on it.
In 3 we focus statistical bias in active learning, that and consistent, and let us optimize the intended objective, not so they can miraculously close the train-test gap. From more formal perspective, our results all assume that is chosen independently of the training data; an assumption that is almost always (implicitly) made in the literature. This ensures our estimators form valid objectives, but also has important implications that are typically overlooked. We return to this in 7 examining the interaction between statistical and overfitting bias.
produce estimators that valid
UNBIASED ACTIVE LEARNING: RPPURE AND PLURE
We now show how to unbiasedly estimate the risk in the form of a weighted expectation over actively sampled data points. We denote the set of actively sampled points Durain = ((xm.y.)) < m S M). where Vm. X... E Dpoet- We begin by building a "plain" unbiased risk estimator, RPURE. as a stepping stone-its construction is quite natural in that each term is individually an unbiased estimator of the risk. We then use it to construct "levelled" unbiased risk estimator, PLURE, which is unbiased
2

---

Published as a conference paper at ICLR 2021
and consistent estimator of the population risk just like RPURE. but which reweights individual terms to produce lower variance and resolve some pathologies of the first approach. Both estimators are easy to implement and have trivial compute/memory requirements.
3.1 RPURE: PLAIN UNBIASED RISK ESTIMATOR
For our estimators, we introduce an active sampling proposal distribution over indices rather than the more typical distribution over datapoints. This simplifies our proofs, but the two are algorithmically equivalent for pool-based active learning because of the one-to-one relationship between datapoints and indices. We define the probability mass for each index being the next to be sampled, once
Dusin contains m 1 points, as q(mm 11:m-1, D puut). Because we are learning actively, the proposal distribution depends on the indices sampled so far (11mm-1) and the available data (Dpool, note though that does not depend on the labels of unsampled points). The only requirement on this proposal distribution for our theoretical results is that it must place non-zero probability all of the training data: anything else necessarily introduces bias. Considerations for the acquisition proposal distribution discussed further in $3. results:
We first present the estimator before proving the main
RPURE- M E Omi where am Wm En Cis:
M
where the loss at a point Lim. = C(y.,. : fo(x; )), the weights Wmn = 1/Ng(imi : 11mmm D Prnnt and im ~ qbmii 11:m-1. Dooo). ). For practical implementation, RPURE can further be written in the following more computationally friendly form that avoids double summation:
M
M m7
ÖPURE.
Σ
Lim.
M
Nq(im; 11am11 D Ppooo)
However, we focus the first form for our analysis because Om in has some beneficial properties not shared by the weighting factors in (3). In particular, in Appendix B.I we prove that:
Lemma 1. The individual terms am of ПPURE are unbiased estimators of the risk: E [am] = r.
The motivation for the construction of am directly originates from constructing an estimator where Lemma
I hholds while only making use of the observed losses .i...... Li.,, taking care with the fact that each new proposal distribution does not have support over points that have already been acquired. Except for trivial problems, an is essentially unique in this regard; naive importance sampling M Em= Wm Cim) does not lead to an unbiased, or even consistent, estimator. However, the overall estimator ReURE is not the only unbiased estimator of the risk, as we discuss in $3.2
(i.e. 1
We can now characterize the behaviour of RPURE as follows (see Appendix B.2 for proof)
Theorem 1. ReURE as defined above has the properlies:
E
RPURE
M
Var [
Var
Σ m=1
Var [wm Cim, 111m-11 D Ppool]-
(4)
N
M2
The first term of 4 the variance of the loss on the whole pool, while the second term accounts for the variance originating from the active sampling isself given the pool. This second term O(N/M) times larger and so will generally dominate in practice as typically M < N.
Remark 1.
Armed with Theorem we can prove the consistency of RYURE under standard assumptions: RPURE converges in expectation (i.e. its mean squared error tends to zero) as M - oc under the assumptions that > M, L(y, fe (x)) is integrable, and qimii 11mm Pooot is a valid proposal in the sense that it puts non-zero mass on each unlabelled datapoint. Formally, as proved in Appendix B.3
Theorem 2. Let N/M and assume that 1. 1f E [[(y, fo
and
min 38 ne (imm)))
ql n2, f1:m Droat) 2 8/N V m msA N,
then REURE converges in its L norm to r as M + xc, ie,, lim E [RPPUR r)2] =
3

---

Published as a conference paper at ICLR 2021
3.2 RLURE: LEVELLED UNBIASED RISK ESTIMATOR
RPURE is natural in that each term is unbiased estimator r. However, this creates surprising behaviour given the sequential structure of active learning. For example, with a uniform proposal distribution-eeqiivllenn to not actively learning-points sampled earlier are more highly weighted than later ones and RPURE * R. Specifically,, a uniform proposal, q(èmi 81:m-1, Poooi N- gives weight on each sampled point of 1 + M M-2m-1 o 1. Similarly, as M - N (such that we use the full pool) the weights also fail become uniform: setting M N gives weight for each point of M 2mm+1 # L. PLURE fixes this. We first quote the estimator before proving key results:
M
RLURE-
Σ
Um Sim
Um =
N -M N (N 1) g(imi 1:m-1. D Pooo
1
1) (5)
M
m=1
This estimator ensures that the expected value of the weight, Ums does not depend on the position was sampled in, but only on the probability with which it was sampled. That is, E [vm) for all m.
M. N, and qi 11:m-1 D poot). : As a consequence the variance is generally lower. Moreover, we resolve the finite-sample behaviour shown by RPURE. The weights become more even as M increases for a given N, and when M = N, each Um = such that RLURE = R = R. Additionally, if the proposal is uniform, all weights are always exactly such that RLURE = R.
To derive /LURE note that each am estimates without bias for any normalized linear combination:
Σ m==l Cm
E
Em= Cm
provided that the en are constant with respect to the data and sampled indices (they can depend on M, N, and m). In Appendix B.4 show that the choice of:
N(N - M)
Cyn (N m)
1)
produces the Um from () and in turn that these um have the desired property E [mml 1, Vm E {1...., M. We note also that Σm Cm M, such that RLLRE Σ M m= mm We further
characterise the variance and unbiasedness PLURE as follows (see Appendix B.5 for proof)
Theorem 3. RLURE as defined above has the following properties:
E
REURE
=
Var [C(y, fo()))
M
Var
REURE]
Σ m=1
c D
[Var [wm Lim 11:mm Prooil (6)
N
M
Although not obvious from inspection of (6). in Appendix B.6 we prove that the variance of RLURE is always less than that of RYURE subject to a mild assumption about the proposal which we detail there.
Theorem 4. If Equation
14 in Appendix B.6 holds then Var Var[Ruune) < Var ReuRe) If M > 1 and O also hold, then the inequality is strict: Var (RLUE)) < Var RFURE).
ED,,.. [Varww, Ci, [Pooa)]
To provide intuition into why this result holds, remember that cm were introduced ensure that E [um] are all identically one. Therefore this weighting removes the tendency of RPURE to overemphasize the earlier samples; essentially increasing the effective sample size by correcting the imbalance.
We finish by confirming that PLURE is a consistent estimator as M - (proof in Appendix B.7
Theorem 5. Under the same assumptions as Theorem lima-+00 IE (iLUURE -
-r)² r)² 0.
3.3 FROM ACTIVE LEARNING SCHEMES TO PROPOSALS
We have introduced two elements of the active learning scheme: the risk estimators- RPURE and RLURE- and the acquisition proposal distribution (q (1:m D whiih has so far remained general. So long as the acquisition proposal puts non-zero mass all the training data, ÂPURE and
4

---

Published as a conference paper at ICLR 2021
FLURE are unbiased and consistent as proven above. This is in contrast to the naive risk estimator R. for which the choice of proposal distribution affects the bias of the estimator.
is easy to satisfy the requirement for non-zero mass everywhere. Even prior work which selects points deterministically (e.g., Bayesian Active Learning by Disagreement (BALD) (Houlsyy et al.) 2011) or a geometric heuristic like coreset construction (Sener & Savarese 2018 can be easily adapted. Any scheme, like BALD, that selects the points with a argmax distribution. Alternatively, distribution can be constructed analogous to epsilon- apsilon-greedy exploration. With probability we pick uniformly, otherwise we pick the point returned by an arbitrary acquisition strategy. This adapts any deterministic active learning scheme to allow unbiased risk estimation.
f fmaa return
It is also possible use RLURE and RPURE with data collected using proposal distribution that does not fully support the training data, though they will not fully correct the bias in this case. Namely, if we have set of points, I, that are ignored by the proposal (i.e. that are assigned zero mass), we can still use PLURE and RPURE in the same way but they both introduce the same following bias:
1 L WEI
E E LURE] LE E
E |LURE
D pool
E
C. pool
E
N
RET
Sometimes this bias will be small and may be acceptable if it enables desired acquisition scheme, but in general one of the stochastic adaptations described above is likely to be preferable. One can naturally also extend this result to cases where I varies at each iteration of the active learning (including deterministic acquisition strategies), for which we again have a non-zero bias.
Though the choices of acquisition proposal and risk estimator are algorithmically detached, choosing good proposal will still be critical performance in practice. In the next section, will discuss how the proposal distribution can affect the variance of the estimators, and we will see that our approaches also offer the potential to reduce the variance of the naive biased estimator. Later, in $7 we will turn to third element of active learning schemes generalization and consider the fact that optimization introduces bias separately from the choice of risk estimator and proposal distribution.
4 UNDERSTANDING THE EFFECT OF RLURE AND ÎPURE ON VARIANCE
In order to show that the variance of our unbiased estimators be lower than that of the biased R. with well-chosen acquisition function, we first introduce an analogous result to Theorems and for R, the proof for which is given in Appendix B.8
Theorem 6. Let Um=
E [Ci..] and pmlj, == E [C 111m-1, Dpoal). For R (defined
Em
M
E
1
m= Um (# r in general)
M
Var R
Var
R D pool
+ 2
M
Eppatt
Var (Lim 11:m 1, Dooal]
m=1
A
E Dyon
Var [M D. (Dpoal]
+ 2 2
Cov Limo Σ keem
Lin Dpucol
M
1==1
Examining this expression suggests that the variances of RPURE and, in particular. RLURE will often be lower than that of R, given a suitable proposal. Consider the terms of 7 O analogous to the shared first term of 4 and (6). Var fo (x)) /N. If R were an unbiased estimator of R then these would be exactly equal, but the conditional bias introduced by R also varies between pool datasets. In general, I will typically be larger than, or similar to, its unbiased counterparts. In any case, recall that the first terms of 4 and 66) tend to be small contributors to the overall variance anyway, thus @ provides negligible scope for It to provide notable benefits over our estimators.
We can also relate @ terms in (4) and (6): it corresponds to the second half of 4 but where we replace of the expected conditional variances of the weighted losses Wn with the unweighted losses Li For effective proposals, Wm and Lin. should be anticorrelated: high loss points should have higher density and thus lower weight. This means the expected conditional variance of wn,Co Ci,. should be less than Li,, for well-designed acquisition strategy. Variation in the expected value
5

---

Published as a conference paper at ICLR 2021
of the weights with can complicate this slightly for RPLRE, but the correction factors applied for PLURE avoids this issue and ensure that the second half of ( will be reliably smaller than @
We have shown that the variance of RLURE typically smaller than ! + @ under sensible proposals. Expression 7 has additional terms: @ is trivially always positive and so contributes to higher variance for N (it comes from variation in the bias in index sampling given pani); Q reflects correlations between the losses at different iterations which have been eliminated by our estimators. This term is harder to quantify and can be positive negative depending on the problem. For example, sampling points without replacement can cause negative correlation, while the proposal adaptation itself can cause positive correlations (finding one high loss point can help find others). The former effect diminishes as N grows, for fixed M, hinting that @ may tend to be positive for N > M. Regardless, if @ is big enough to change which estimator has higher variance then correlation between losses in different acquired points would lead to high bias in R.
In contrast, we prove in Appendix B.9 that under an optimal proposal distribution both ĀPURE and RLURE become exact estimators of the empirical risk for any number of samples M-such that they will inevitably have lower variance than R in this case. A similar result holds when we are estimating gradients of the loss, though note that the optimal proposal is different in the two cases.
Theorem 7. Given a non-negative loss, the optimal proposal distribution
q" (imm i 11 D Poont) = Lim. /Enggiin La
yields estimators exactly equal to the pool risk, that is RPURE- = RUURE R almost surely VM.
In practice, it is impossible to sample using the optimal proposal distribution. However, we make this point in order to prove that adopting our unbiased estimator is certainly capable of reducing variance relative to standard practice appropriate acquisition strategies are used, It also provides interesting insights into what makes a good acquisition strategy from the perspective of the risk estimation itself.
5 RELATED WORK
Pool-based active learning (Lewis & Gale but labeling them is expensive (Atlas et al. 1990; Settles 2010). The bias from selective sampling was noted by MacKay (1992), but dismissed from a Bayesian perspective based on the likelihood principle. Others have noted that the likelihood principle remains controversial (Rainforth) 2017)) and in this case would assume well-specified model. Moreover, from a discriminative learning perspective this bias is uncontentiously problematic. Lowell et al. (2019) observe that active learning algorithms and datasets become coupled by active sampling and that datasets often outlive algorithms.
1994 is useful in cases where input data are prevalent
Despite the potential pitfalls, in deep learning this bias is generally ignored. As an informal survey, we examined the 15 most-cited peer-reviewed papers citing Gal et al. (2017b), which considered active learning to image data using neural networks. Of these, only two mentioned estimator bias but did not address it while the rest either ignored were unaware of this problem (see Appendix (D).
There have been some attempts to address active learning bias, but these have generally required fundamental changes to the active learning approach and only apply to particular setups. [Beygelzimer corrections (Sugiyama 2006 Bach 2006) to online active learning. Unlike pool-based active learning, this involves deciding whether or not to sample new point it arrives from an infinite distribution. This makes importance-samen sampling estimators much easier to develop, but as SSttles (2010) notes, "the pool-based scenario appears to be much more common among application papers."
et al. 2009), Chu al. (201)), and (Cortes et al. 2019) apply importance-samplinn
Ganti & Gray (2012) address unbiased active learning in a pool-based setting by sampling from the pool with replacement. This effectively converts pool- based learning into stationary online learning setting, although overweights data that happens to be sampled early. Sampling with replacement is unwanted in active learning because it requires retraining the model on duplicate data which is either impossible or wasteful depending on details of the setting. Moreover, they only prove the consistency of their estimator under very strong assumptions (well-specified linear models with noiseless labels and a mean- squared-error loss). Imberg et al. (2020) consider optimal proposal distributions in an importance-sante sampling setting. Outside the context of active learning. [Byrd & Lipton| (2019) question the value of importanceweiihhting weighting for deep learning, which aligns with our findings below.

---

Published as a conference paper at ICLR 2021
6 APPLYING BLURE AND RPURE
25
Ideal Doas
2.0
Unswighttd Dhon
We first verify that RLURE and RPURE remove the bias introduced by active learning and examine the variance of the estimators. We do this by tak- ing fixed function whose parameters are inde- pendent of Drai and estimating the risk using actively sampled points. We note that this equiv- alent to the problem of estimating the risk of an already trained model in a sample-efficien way given unlabelled test data. We consider two set- tings: an inflexible model (linear regression) on toy but non-linear data and overparameterized model (convolutional Bayesian neural network) on a modified version of MNIST with unbalanced classes and noisy labels.
Rouss Deas
Ruse on Deas
Pool Poing Dppi
x
Acquited Plyar
0.
0.0
XXX
-0.5
Figure 1: Illustrative linear regression. Ac- tive learning deliberately over-samples unusual points (red x's) which no longer match the pop- ulation (black dots). Common practice uses the biased unweighted estimator R which puts too much emphasis on unusual points. Our unbiased estimators RPURE and PLURE fix this, learning function using only Daain nearly equal to the ideal you would get if you had labels for the whole of D Poool despite only using a few points.
Linear regression. For linear functions, remov- ing active learning bias (ALB), i.e., the statistical bias introduced by active learning, is critical. We illustrate this in Figure Actively sampled points overrepresent unusual parts of the distribution, so a model learned using the unweighed Prain differs from the ideal function fit the whole of pool- Using corrective weights more closely approxi- mates the ideal line. The full details of the population distribution and geometric acquisition proposal distribution in Appendix C.1. where we also show results using an alternative epsilon-greedd proposal. We inspect the ALB in Figure 2a by comparing the estimated risk (with squared error loss and fixed function) to the corresponding true population risk R. While M < N. the unweighted R is biased (in practice we never have M = N as then actively learning is unnecessary). RPURE and Ri .URE are unbiased throughout, However, they have high variance because the proposal is rather poor. Shading represents the std. dev. of the bias over 1000 different acquisition trajectories.
Bayesian Neural Network. We actively classify MNIST and FashionMNIST images using convolutional Bayesian neural network (BNN) with roughly 80,000 parameters. In Figure 2b and 2c we show that RPURE and ÉLURE remove the ALB. Here the variance of ÆPURE and RLURE is lower or similar to the biased estimator. This is because the acquisition proposal distribution, a stochastic relaxation of the Bayesian Active Learning by Disagreement (BALD) objective (Houlsby et al. (001). effective (c.f. $4. A full description of the dataset and procedure is provided in Appendix C.2 Our modified MNIST dataset is unbalanced and has noisy labels, which makes the bias more distorting.
Overall, Figure 2 shows that our estimators remove the bias introduced by active learning, as expected, and can do so with reduced variance given an acquisition proposal distribution that puts a high probability mass more informative/surpriingg high-expected-loss points.
425
(a) Linear regression.
(b) BNN: MNIST.
(c) BNN: FNShi
Figure 2: RPURE and ÍLURE remove bias introduced by active learning, while unweighted n, which most active learning work uses, is biased. Note the sign: R overestimates risk because active learning samples the hardest points. Variance for REURE and RLURE depends on the acquisition distribution placing high weight on high-expected-loss, points. In (b), the BALD-style distribution means that the variance of the unbiased estimators is smaller. For FashionMNIST. (c), active learning bias is small and high variance in all cases. Shading #1 standard deviation.
7

---

Published as a conference paper at ICLR 2021
28-
Traind wit Peat
Tuee
22
04-
16
20
(a) Linear regression. Test MSE.
(b) MNIST: Test NLL.
(c) MNIST: Test Acc.
3.70
Tranad Auo
3.
125
(d) MashionMNIST: Test NLL.
(e) MNIST (MCDO): Test NLL. (1) MNIST (Balanced): Test NLL.
Figure 3: For linear regression, the models trained with RPURE or RLURE have lower 'population' risk. contrast, BNNs trained with RLURE or RPURE perform either similarly (e) or slightly worse (b,c.d,)), even though they remove bias and have lower variance. Shading is one standard deviation. For (a) 1000 samples and 'r' estimated on 10, 100 points from distribution. For (b)/(c) 45 samples and 'r" estimated on the test dataset. (f)-(f) are alternative settings to validate consistency of result.
Next, we examine the overall effect of using the unbiased estimators to learn a model on downstream performance. Intuitively, removing bias in training while also reducing the variance ought to improve the downstream task objective: test loss and accuracy. To investigate this, we train models using R, RLURE. and RPURE with actively sampled data and measure the population risk of each model.
For linear regression (Figure 3a the new estimators improve the test loss-even with small numbers of acquired points we have nearly optimal test loss (estimated with many samples). However, for the BNN, there is a small but significant negative impact on the full test dataset loss of training with RLURE or RPURE (Figure 3b) and a slightly larger negative impact on test accuracy (Figure 3c That is, we get better model by training using a biased estimator with higher variance!
To validate this further, we consider models trained instead MNSST (Fig. 3d), on MNIST but with Monte Carlo dropout (MCDO) (Gal & Ghahramani 2015) (Fig. (3e]. and on a balanced version of the MNIST data (Fig. 31). In all cases we find similar patterns, suggesting the effects are not overly sensitive to the setting. Further experiments and ablations can be found in Appendix C.2
7 ACTIVE LEARNING BIAS IN THE CONTEXT OF OVERALL BIAS
In order to explain the finding that RLURE hurts training for the BNN, we return to the bias introduced by overfitting, allowing examine the effect of removing statistical bias in the context of overall bias. Namely, we need to consider the fact that training would induce am overfitting bias (OFB) even if we had not used active learning. If we optimize parameters 0 according to it then R(())) o r, because the optimized parameters 8" tend to explain training data better than unseen data. Using RLURE. which removes statistical bias, we can isolate OFB in an active learning setting. More formally, supposing we are optimizing any of the discussed risk estimators (which we will write using R as placeholder to stand for any of them) we define the OFB as:
Born (R()) = (f") where 0" = arg
=rg min,(R())
Born (R()) depends on the details of the optimization algorithm and the dataset. Understanding it fully means understanding generalization machine learning and is outside our scope. We can still gain insight into the interaction of active learning bias (ALB) and OFB. Consider the possible relationships between the magnitudes of ALB and OFB: [ALB >> OFB] Removing ALB reduces overall bias and is most likely occur when fo is not very expressive such that there is little chance of overfitting. [ALB << OFB] Removing ALB is irrelevant as model has massively overfit regardless.
[ALB OFB] Here sign is critical. If ALB and OFB have opposite signs and similar scale, they
8

---

Published as a conference paper at ICLR 2021
40-
2611
25
(a) Linear regression.
(b) BNN: MNIST.
(c) BNN: MaShionMNIST.
Figure 4: Overfitting bias-Bore -OFB for models trained using the three objectives. (a) Linear regression, BOFR is small compared to ALB (c.f. Figure 2ap. Shading IQR. 1000 trajectories. (b) BNN, BOFR is similar scale and opposite magnitude to ALB (c.f. Figure 2b (c) BNN on FashiOnMNISTT OFB is
somewhat larger than with MNIST, particularly for R (i.c. our approaches reduce overfitting) and dominates active learning bias (c.f. Figure 2c). Shading +1 I standard error. 150 trajectories.
will tend to cancel each other out. Indeed, they usually have opposite signs. ВOFв is usually positive: 0" fits the training data better than unseen data. ALB is generally negative: we actively choose amusuaa/surppisnn//nfommaat
points which are harder to fit than typical points.
Therefore, when significant overfitting is possible, unless ALB is also large, removing ALB will have little effect and can even be harmful. This hypothesis would explain the observations in To we were to show that BOFR was small for linear regression but had similar magnitude and opposite sign to ALB for the BNN. This is exactly what we show in Figure
Specifically, we see that for linear regression, the BOFB for models trained with R. RPURE. and RLURE all small (Figure 4a) when contrasted the ALB shown in Figure 2a Here ALB >> OFB; removing ALB matters. For BNNs we instead see that the OFB has opposite sign to the ALB but is either similar in scale for MNIST (Figures 2b and 4b). or the OFB is much larger than ALB for Fashion MNIST (Figures 4c and 2c The two sources of bias thus (partially) cancel out. Essentially, using active learning can be treated (quite instrumentally) as an ad hoc form of regularization. This explains why removing ALB can hurt active learning with neural networks.
CONCLUSIONS
Active learning is a powerful tool but raises potential problems with statistical bias. We offer corrective weighting which removes that bias with negligible compute/memory costs and few requirements-it it suits standard pool-based active learning without replacement. It requires a non- zero proposal distribution over all unlabelled points but existing acquisition functions can be easily transformed into sampling distributions. Indeed, estimates of scores like mutual information are so noisy that many applications already have an implicit proposal distribution.
We show that removing active learning bias (ALB) can be helpful in some settings, like linear regression, where the model is not sufficiently complex to perfectly match the data, such that the exact loss function and input data distribution are essential in diseriminating between different possible (imperfect) model fits. We also find that removing ALB can be counter- prrnuue-rr for overparameterized models like neural networks, even if its removal also reduces the variance of the estimators, because here the ALB can help cancel out the bias originating from overfitting. This leads to the interesting conclusion that active learning can be helpful not only as a mechanism to reduce variance as it was originally designed, but also because it introduces bias that can be actively helpful by regularizing the model. This helps explain why active learning with neural networks has shown success despite using biased risk estimator.
We propose the following rules of thumb for deciding when embrace or correct the bias, noting that we should always prefer RLURE to RPURE. First, the more closely the acquisition proposal distribution approaches the optimal distribution (as per Theorem 7). the relatively better RLURE will be to R. Second, the less overfitting we expect, the more likely it is that RLURE will be useful it reduces the chance that the ALB will actually help. Third, PLURE will tend to have more of an effect for highly imbalanced datasets, as the biased estimator will over-represent actively selected but unlikely datapoints. Fourth, if the training data does not accurately represent the test data, using ÆLURE will likely be less important the ALB will tend to be dwarfed by bias from the distribution shift. Fifth, at test-time, where optimization and overfitting bias are no-longer an issue, there is little cost to using RLURE to evaluate a model and it will usually be beneficial. This final application, of active learning for model evaluation, is an interesting new research direction that is opened up by our estimators.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
The authors would like especially thank Lewis Smith for his helpful conversations and specifically
for his assistance with the proof of Theorem 4 In addition, we would like to thank for their conversations and advice Joost van Amersfoort and Andreas Kirsch.
The authors are grateful to the Engineering and Physical Sciences Research Council for their support of the Centre for Doctoral Training in Cyber Security, University of Oxford as well as the Alan Turing Institute.
REFERENCES
Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds. In Eighth International Conference Learning Representations, April 2020.
Les Atlas, David Cohn, and Richard Ladner. Training Connectionist Networks with Queries and Selective Sampling. Neural Information Processing Systems, 1990.
Francis Bach. Active learning for mispecified generalized linear models. Neural Information Processing Systems, 19, 2006.
Sima Behpour, Anqi Liu, and Brian Ziebart. Active learning for probabilistic structured prediction of cuts and matchings. volume of Proceedings of Machine Learning Research, pp. 563-572, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
William H Beluch, Tim Genewein, Andreas Nurnberger, and Jan M Kohler. The Power of Ensembles for Active Learning in Image Classification. CVPR, 2018.
Alina Beygelzimer, Sanjoy Dasgupta, and John Langfor. Importance weighted active learning. International Conference on Machine Learning, 26, 2009.
Jonathon Byrd and Zachary C. Lipton. What is the Effect of Importance Weighting in Deep Learning? ICML, June 2019.
Jiaoyan Chen, Yan Zhou, Alexander Zipf, and Hongchao Fan. Deep Learning From Multiple Crowds: A Case Study of Humanitarian Mapping. IEEE Transactions on Geoscience and Remote Sensing, 57(3):1133-1722, March 2019. ISSN 1558-0644. doi: 10.1109TTGRS.00 2018.28874888
Wei Chu, Martin Zinkevich, Lihong Li, Achint Thomas, and Belle Tseng. Unbiased online active learning in data streams. KDD '11, pp. 195 203, 2011.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovee, and Matei Zaharia. Selection via Proxy: Efficient Data Selection for Deep Learning. In Eighth International Conference on Learning Representations, April 2020.
Corinna Cortes, Giulia Desalvo, Mehryar Mohri, Ningshan Zhang, and Claudio Gentile. Active learning with disagreement graphs. volume 97 of Proceedings of Machine Learning Research, pp. 1379-1387, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. International Conference on Machine Learning. 25, 2008
Sebastian Farquhar, Michael Osborne, and Yarin Gal. Radial Bayesian Neural Networks: Robust Variational Inference In Big Models. Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020.
Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. Proceedings of the 33rd International Conference on Machine Learning, 48: 48:0090-1059 2015.
Yarin Gal, Jiri Hron, and Alex Kendall, Concrete Dropout. Neural Information Processing Systems, pp. 10, 2017a.
10

---

Published as a conference paper at ICLR 2021
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep Bayesian Active Learning with Image Data. Proceedings of The 34th International Conference on Machine Learning, 2017b.
Ravi Ganti and Alexander Gray. Upal: Unbiased pool based active learning, Artificial Intelligence and Statisties, 15, 2012.
Sambuddha Ghosal, Bangyou Zheng, Scott C. Chapman, Andries B. Potgieter, David R. Jordan, Xuemin Wang, Asheesh K. Singh, Arti Singh, Masayuki Hirafuji, Seishi Ninomiya, Baskar Ganapathysubraaanian Soumik Sarkar, and Wei Guo. A Weakly Supervised Deep Learning Framework for Sorghum Head Detection and Counting, 2019. Publisher: Science Partner Journal Volume: 2019.
Juan Mario Haut, Mercedes E. Paoletti, Javier Plaza, Jun Li, and Antonio Plaza. Active Learning With Convolutional Neural Networks for Hyperspectral Image Classification Using a New Bayesian Approach. IEEE Transactions Geoscience and Remote Sensing, 56(1 (1)41))4446444 6461, November 2018. ISSN 1558-0644. doi: Geoscience and Remote Sensing.
201 Conference Name: IREE Transactions
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. CVPR, 7(3):171-180; 2016.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian Active Learning for Classification and Preference Learning. arXiv, 2011.
Peiyun Hu, Zachary C. Lipton, Anima Anandkumar, and Deva Ramanan. Active Learning with Partial Feedback. International Conference on Learning Representations, 2019.
Sheng-Jun Huang, Jia-Wei Zhao, and Zhao- Yang Liu. Cost-Effective Training of Deep CNNs with Active Model Adaptation. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 1580-1588, New York, NY, USA, July 2018. Association for Computing Machinery. ISBN 978- 978-1-4503-5552-0.
Henrik Imberg, Johan Jonasson, and Marina Axelson-Fiste Optimal sampling in unbiased active learning, Artificial Intelligence and Statistics, 23, 2020.
Michael Jordan, Zoubin Ghahramani, Tommi Jaakkola, and Lawrence K. Saul. Introduction to variational methods for graphical models. Machine Learning, 37(2):183-233, 1999.
Benjamin Kellenberger, Diego Marcos, Sylvain Lobry, and Devis Tuia. Half Percent of Labels is Enough: Efficient Animal Detection in UAV Imagery Using Deep CNNs and Active Learning. IEEE Transactions on Geoscience and Remote Sensing, 57(12):9524-953, December 2019. ISSN 0196-2892. Publisher: Institute of Electrical and Electronics Engineers.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning. arXiv:1906.08155 [cs, stat], 2019.
Akshay Krishnamurthy, Alekh Agarwal, Tuu-Kuo Huang. Hal Daumé, III, and John Langford. Active learning for cost-sensitive classification. volume 70 of Proceedings of Machine Learning Research, pp. 1915-1924, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. In Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval. SIGIR '94, pp. 3-12, Berlin, Heidelberg, August 1994. Springer- Verlag. ISBN 978-0-387-19888--7
David Lowell, Zachary C. Lipton. and Byron C. Wallace. Practical Obstacles to Deploying Active Learning. Empirical Methods in Natural Language Processing, November 2019.
David J C MacKay. Information-Batt Objective Functions for Active Data Selection. Neural Computaaioon 4(4):590-604, 1992.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized Prior Functions for Deep Reinforcement
Learning. Neural Information Processing Systems, 2018.
11

---

Published as a conference paper at ICLR 2021
Tom Rainforth. Automating Inference, Learning, and Design using Probabilistic Programming. PhD thesis, University of Oxford, 2017.
Tom Rainforth, A Golinski, Frank Wood, and Sheheryar Zaidi. Target-award bayesian inference: how to beat optimal conventional estimators. Journal of Machine Learning Research, 21(88), 2020.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. International Conference on Learning Representations, February 2018
Ozan Sener and Silvio Savarese. Active Learning for Convolutional Neural Networks: A Core-Set Approach. International Conference on Learning Representations. February 2018.
Burr Settles, Active Learning Literature Survey. Machine Learning, 15(2):201-221, 2010.
Yanyao Shen, Hyokun Yun, Zachary Lipton, Yakov Kronrod, and Animashree Anandkumar. Deep Active Learning for Named Entity Recognition. In International Conference on Learning Repre- sentations, 2018.
Weishi Shi and Qi Yu. Fast direct search in an optimally compressed continuous target space for efficient multi-label active learning. volume 97 of Proceedings of Machine Learning Research, pp. 5769-5778, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Aditya Siddhant and Zachary C. Lipton. Deep Bayesian Active Learning for Natural Language Processing: Results of Large-Scale Empirical Study. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 2904-2909, Brussels, Belgium, 2018. Association for Computational Linguistics.
Samrath Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational Adversarial Active Learning. In 2019 IEEF/CVF International Conference on Computer Vision (ICCV), pp. 5971-5999 Seoul, Korea (South), October 2019. IEEE, ISBN 978-1-72814-803-8 doi: 10.1 10.1109/0C.2201990000
Masashi Sugiyama. Active learning for misspecified models. Neural Information Prciatiionnroooer Processing Systems, 18:1305-1314 2006.
liris Sundin, Peter Schulam, Eero Siivola, Aki Vehtari, Suchi Saria, and Samuel Kaski. Active learning for decision-making from imbalanced observational data, volume 97 of Proceedings of Machine Learning Research, pp. 6046-6055, Long Beach, California, USA, 09-15 Jun 2019.
PMLR.
Keze Wang, Dongyu Zhang, Ya Li, Ruimao Zhang, and Liang Lin. Cost-Effective Active Learning for Deep Image Classification. IEEE Transactions Circuits and Systems Video Technology, January 2017. arXiv: 1701.03551.
Si Wen, Tahsin M. Kurc, Le Hou, Joel H. Saltz, Rajarsi R. Gupta, Rebecca Batiste, Tianhao Zhao, Vu Nguyen, Dimitris Samaras, and Wei Zhu. Comparison of Different Classifiers with Active Learning to Support Quality Control in Nucleus Segmentation in Pathology Images. AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science, 2017:227-236, 2018. ISSN 2153-4063.
Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active Learning with Logged Data. In Interna- tional Conference on Machine Learning, pp. 5521-5530. PMLR, July 2018. ISSN: 2640-3498.
Jie Yang. Thomas Drake, Andreas Damianou, and Yoelle Maarek. Leveraging Crowdsoureing Data for Deep Active Learning An Application: Learning Intents in Alexa. In Proceedings of the 2018 World Wide Web Conference, WWW '18 pp. 23-32, Republic and Canton of Geneva, CHE, April 2018. International World Wide Web Conferences Steering Committee. ISBN 978-1-4503-5639-8
Donggeun Yoo and In So Kweon. Learning Loss for Active Learning. In 2019 IEEF/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 93-102, Long Beach, CA, USA, June 2019. IEEE. ISBN 978- 1-72813-293-8
Yao Zhang and Alpha A. Lee. Bayesian semi- supervise learning for inoertainty-calibattee prediction of molecular properties and active learning. Chemical Science, (1135):8154-8166 September 2019. doi: 10. 00103//99S000616H Publisher: The Royal Society of Chemistry.
12

---

Published as a conference paper at ICLR 2021
A OVERVIEW OF ACTIVE LEARNING
Active learning selectively picks datapoints for which to acquire labels with the aim more sample- efficient learning. For excellent overview of the general active learning problem setting refer the reader to [Settle] (2010).
Since that review was written, a number of significant advances have further developed active learning. Houlsby al.) 2011) develop an efficient way estimate the mutual information between model parameters and the output distribution, which can be used for the Bayesian Active Learning by Disagreement (BALD) score.
Active learning has been applied deep learning, especially for vision Gal (00 7b); Wang et al.
(017)). In neural networks specifically, empirical work has suggested that simple geometric core-set style approaches can outperform uncertainty-bu
acquisition functions (Sener & Savarese 2018).
lot of recent work in active learning has focused on speeding up acquisition from computational perspective (Coleman et al., 2020) and allowing batch acquisition in order to parallelize labelling (Kirsch et al. 2019 Ash al.] 2020). Some work has also focused on applying active learning to
specific settings with particular constraints (Krishnamurthy et al.. 2017 Yan et al. [0188] Sundin
ct al. 2019 Behpour al. 2019 Shi Yu 2019 Hu et al. 2019).
B PROOFS
B. PROOF OF LEMMA II
Lemma 1. The individual terms am of ReURE are unbiased estimators of the risk: E [am)]
Proof.
We begin by applying the tower property of expectations:
am
E
Lim
Cin
N
1=
Dpstifiim-
Eim
Wmhii
Ci,
Dpoot 21:m-1
By further noting that Et.. Wmmmim Dpool i1:m-1] 1] can be written out analytically as all the possible values of im while N 5m-1 L,, deterministic given Ppoot and i1.m-1 we have:
Cim
m-
Eppatitio
glimitimmmi Pooo) no
Σ
Σ
Ci.
N Wglimidsmme Dpool)
N
Ep
Ln
N
n=1
But C,p is now independent of the indices which have been sampled:
N
A -T.
Eppatt
Cp
Exana
N
B.2 PROOF OF THE UNBIASEDNESS AND VARIANCE FOR RPURE: THEOREM
1
Theorem 1. REURE as defined above has the properties:
[ = r,
Var [C(y, fo(x))
M
Var [PURE]
Σ
E E P Aimm
[aa [Wm Cin, 11 1amnm-, Dpool]]- (4)
N
M2
m=1
13

---

Published as a conference paper at ICLR 2021
Proof. Having established Lemma]
unbiasedness follows quickly from the linearity of expectations:
M
M
E
RPURE
E
am
E
[0ml
M
M
m=1
For the variance we instead have (starting with the definition of RPCRE):
M
27
Var
[RPURE] =
Oy
r?
M
m=1
which by the tower property of expectations
E
R
am
D pool
y2
M
and from the definition of variance
M
E
Var
am
D pool
+ R².
n2
M
m=1
M
E
Var
Om
D Ppoot
+ Var
R
which using the fact that R is standard Monte Carlo estimator
M
Var [C(x, fo(x))
E
Var
Σ
am
D
pool
+
(8)
M
N
m=1
where x, y ~ Pduta-
Now considering the first term we have
M
2
1
Var
am
D
pool
E
am
R R)
D
Pooool
M
M
M
(am - Rt) (ax-A) P
(9)
M
m=
k=
We attack this term by first considering the terms for which m * k and show that these yield terms later. We will assume, without loss of
E [aam (ax r) poool 0, returning to the generality, that < m,, noting that by symmetry the same set of arguments can be similarly applied when < k. Substituting in the definition of a. from equation 2
E (am (as= ft) paol
=E
WmLiin
Σ Li
R8 -R) 12)
wxLin + N
1
Ec,,
Ci
R8
Pron
We introduce the notation Ryam = - ascribable the datapoint with index im. Then, by multiplying out the terms have:
N Em-1 Li, to describe the remainder of the empirical risk
E (am (ax RR) pooo
E [wm Lim w/ Ci, (Ppoot)
E
Wm Li...
Rrom
D
pool
E W. Lig frrem
Dpont
+E
Prrem
perem
D
Poon
Now by the tower property:
= E E [wm Lin Whhrr Dpooos 21.m-2ll/
14

---

Published as a conference paper at ICLR 2021
and noting that because C is deterministic given D Pooo and 81:m-17
= B [un Cir E [Wm Cim
pool, 11:m- [Pool]
= E Wh Prom Poool
which thus cancels with (
The b and
cancel similarly:
b
E
E Wm Lin
Rrem
D Ppoct 11:m
D pool
Rrem B [wi fim
Dpoot 8 1m
D pool
Rr Rrem
D Ppoot
d
Putting this together, we have that:
E (am Ra
R2) Dpoos
0
Ak + m.
Considering now the m = h terms we have
2 |poul pool
am - R)) 2
E
am
R)
Eiim--
Bim
11:m poco
pool
-Bimm-
[Var [am 11mm 1, D pool [2 pool
Eiimm
[Var [Wm Lim 11:m-1, D Dpucil] (D Pppui]
Finally substituting everything back into (9) and then (8. and applying the tower property gives
Var [C(y, fo (x))]
M
Var [PPURE]
E E fam [ Ci, 111mm D Ppool]
N
M
m=1
and we are done.
B.3 PROOF OF THE CONSISTENCY OF RPURE: THEOREM 2
Theorem 2. Let N/M and assume that a > 1. 1f [Cly fo(x)) < oo and
33>0 DE (1:N'
min
(im n1, 17,1mm11, Dpoel) 2 3/N VN VN m N,
then RIURE converges in L? norm to r as M + xc, ie,, lim E (RPURE r)2
Proof. Theorem showed that RPURE is an unbiased estimator and so we first note that its MSE is simply its variance, which we found in (4). Substituting aM:
E [ (ĪTUUR:: - ))
Var [RPURE
Var [o(x
Σ
[ar [im.i,,, ( 1, Prooi]]-
aM
M
The first term tends to zero as M 0o as our standard assumptions guarantee that For the second term note that assumptions about 9 guarantee
Var [[y, [x()
that Wm I 1/3 and thus:
2
m
Var [Wmmi Ci,, 11mm Dpoot] = [ C2 im. 181m--1, Proot]
it
Σ
L
M
1 E [2] 11 Droot]
1
m-1
Lis
32
M
Vi Ppnul
15

---

Published as a conference paper at ICLR 2021
assumptions guarantee that # co, have E [ and so the empirical risk and losses are finite.
Given that each Var [w' Cim 181m- D pooii is finite, it follows that:
M
D Pp
Var (wm Lim 18:m Ppoci]] < 00;
and we thus have:
(RIURE - R) [
Var (aly
52
lim M-000
E
lim M M0000
+
a.d
M
as desired.
B.4 DERIVATION OF THE CONSTANTS OF RLURE
We note from before that because of the unbiasedness of am-
Cm
where
C Em=
Cm
To construct our improved estimator FLURE, we now need to find the right constants Cas that in turn lead overall weights Um (as per (5)) such that [Um] 1. We start by substituting the definition of am:
M
M
M
m -1
RLURE: = C
Σ Um C.m == C
Cm Cma Am = C
Σ
WimmCim +
Cm
Σ t=1
Cie
N
m==
m=1
m==1
and then redistributing the Ci, from later terms where they match m.
M
Σ G
Um = Gy Wy
(-1+--1
Note that though RLURE remains unbiased estimator of the risk, each individual term um
is not. Now we require: E [um]]
= 1 Vm E {I, M}. Remembering that Wm
1/(AV L/(Nqqim qimi f1mm11 P.pol))) P:
M
[m
Cm
Σ
G
N
11.m aimmi
D Dpont)
N
(=
qimm = n2; 81:m -1 D Dpool
4
N
qimm ngin
12; 11:11 11 Prool)
m1
(=++1
Cm (N
+ 1)
Σ
4-
N
[=m+1
Imposing that each E [vm]] = 1, we now have M equations for M unknowns CI...., CMs such that we can find the required values of cm by solving the set of simultaneous equations:
(N -
1
Vm E (1....,M1 M).
(10)
N
1=++1
We do this by induction. First, consider E. [Um]
E [Um+1] 0, for which be rewritten:
(N
Cm
(N
m)
Cm+1
Cm+1
0
N
N
N
and thus:
N m
Cm
Cm+1l
(II)
N
m
16

---

Published as a conference paper at ICLR 2021
By further noting that the solution for M is trivial:
N
CM = N - M+1 11
we have by induction
N
M-1
N
Gm
N
M
+
N -+1
M-1 log(N- - - - log(NV - -
N
N
M +1
m
Now we can exploit the fact that there is canceling of most of the term this sum. The exceptions llo(NN
1), log(NV m), log(N M 1), and log(N MM. We thus have:
Cm N M + exp (log(N M) + log(N - .M + 1) log( N - m) loggNN - m + 1))
N(N M)
(N m) m 1)
which is our final simple form for Cm. We can now check that this satisfies the required recursive relationship (noting trivially gives the correct value for cM) as per (11
N
Cm
Cm+1
N +
N m -
N(N - M) 1)(N ml
N + 1 (N
N(N - M)
(N mN + 1)
as required. Similarly, we can straightforwardly show that this form of cn satisfies 10 by substitu-
tion.
We then find the form of um given this expression for Cm
Remember that:
1
Um Gm Wm
Ct-
N
1=m+1
We rearrange (TO) to:
M Σ
N
m
+1
a=1
Cy
N
N
from which it follows that:
N m
Um
+
Cm
1m
N
Substituting in expressions for cm and Wm we thus have:
N M
= 1 + (N mN(N + ((mmm i1 f( 1), D Dpcot) (N - -m+1)
N - M
N (N + 1) glmmi f1.m Dpnnt) 1).
+
which is the form given in the original expression.
17

---

Published as a conference paper at ICLR 2021
To finish definition, simply need to derive C::
M
-1
c
=
Σ
Cm
m=1
M
-1
N(N M)
Σ
(N
m) -m 1)
m=1
M
1
N(N M))
N m
N - m +1
m=1
where we now have telescopic sum so
+
N(N M))
N M
N
M
We thus see that our Pm always sum to M, giving the quoted form for RLURE in the main paper.
B.5 PROOF OF UNBIASEDNESS AND VARIANCE FOR PLURE: THEOREM 3
Theorem 3. RLURE as defined above has the following properties:
E [QURR
=T,
Var [L(y, fo(x))
M
Var [LURE]
Σ
c Dp
[Var [wm Cin, 111m-11, Ppooi]] (6)
N
M
m=1
Proof. RIURE is, by construction linear combination of the weights am, By Lemma an unbiased estimator of So by the linearity of expectation, E RLURE
each am is
As in Theorem the variance requires degree of because the am not independent. Noting that the expectation does not change through the weighting, we analogously have
M
Var [C(y, fx))
Var
PLURRE
=
E
Var
Car O.
D
Dpool
+
M
N
m=1
Similarly, we also have
2
1
Var
Σ
Cra Oym
Dpool
E
Cm a'm
Dpocl
R22
M
M
M
[am D Dpoul] R.2
Cm C2
M
k=1
M
M
E [amaa [pennl) - 122)
Cm
M
M
C.c (an R) (ar R) (poua]
M
m=1 km
Using the result before that
E ( (am R)
(or
R)
D
pool
E
Var Cim 1i1m Dpooll [aonll[pooo [Dooo]] if m = otherwise
now gives the desired result by straightforward substitution.
18

---

Published as a conference paper at ICLR 2021
B.6 PROOF THAT RLURE HAS LOWER VARIANCE THAN RPURE UNDER REASONABLE ASSUMPTIONS: THEOREM
Recall from Theorems
and 3
that the variances of the RLURE and REURE estimators are
Var [C fo()))]
1
Var
RPURE
Em
(12)
N
M
m=1
Var [c So [x())
1
Var
RLURE
c Fi
(13)
N
M
where we have used the shorthand Em
E Dpan 61:
Var [wm Li 81.m Ppooil]. Recall also that
N² MM2
NN - m m + 1)2
Though the potential for one to use pathologically bad proposals means that it is not possible to show that Var R I Var RPPURE universally holds, we can show this result under relatively weak assumption that ensures our proposal is "sufficiently good."
To formalize this assumption, we first define
Wm
N m +
-2
Fm == E E Dpm
Var
fiim 4iam-1, 1, D panl
Fi
E [wm f1:m-1: D
the weight-normalized expected variance, where the second form comes from the fact that [mm/imm-m Ppool] = (N m + 1)/N. Our assumption is now that
Fm 2 FM-m+1 Vm S m S M/2.
(14)
Note that sufficient, but not necessary, condition for this to hold is that the F.. do not increase with m, i.. Fm 2 F3 j) 1 S. m S S M. Intuitively, this is is equivalent to saying that the conditional variances of our normalized weighted losses should not increase as acquire more points. It is, for example, satisfied by a uniform sampling acquisition strategy (for which all F., are equal). More generally, should hold in practice for sensible acquisition strategies as our proposal should improve on average as we acquire more labels, leading to lower average variance; and b) higher loss points will generally be acquired earlier so the scaling will typically decrease with m. In particular, note that E [wm C.m. 111mm-1. D poool < r and is monotonically decreasing with m because omits the already sampled losses (which is why these are added back in when calculating am).
This assumption actually stronger than necessary: in practice the result will hold even if F.. increases with provided the rate of increase is sufficiently small. However, the assumption as stated already holds for a broad range of sensible proposals and fully encapsulating the minimum requirements on Fm is beyond the scope of this paper.
We are now ready to formally state and prove our result. For this, however, it is convenient to first prove the following lemma, which we will invoke multiple times in the main proof.
Lemma 2. If b, M, E N+ are positive integers such that, M < N and + b < M, then
(N 10-a
a)²
(N - 2
N2 2 (N -
Proof.
(N - a))
(N M)²
(N a)2(N - -2 2
N2
(N - 6)2
N2(N - b)2
2N
+ N2 12 4ab -22) 2abN 22b2
N2 -0--b) b)2
1
N(2N M - a- b) ab N - a a- bb + ab
N2 6)2
2 as 2N M + a and M 2 b so all bracketed terms positive.
19

---

Published as a conference paper at ICLR 2021
Theorem 4. If Equation 14 in Appendix B.6 holds then RLURE I Var [RuRE)- M > 1 and
Ep [Var[um Ci, [Poool] also hold, then the inequality is strict: Var REvee) Var RreRe).
Proof. We start by subtracting equation
13 from
12
yielding
M
Var
[
Var
R
(1
cm Fm
M
m=
1
Σ
em)
N (~
m +
Fm
M
N
Assuming, for now, that M is even and M < N, we can now group terms into pairs by counting from each end of the sequence (i.e. pairing the m-th and M m 1-th terms) to yield
M/2
Var RPURE|
Var
[RLURE]
=
Σ
Sm
M
m=1
where
(N m + 1)3
(N - M + m)²
Sm == (1- (n)
Fm + (1 1--3mmmt)
FM
N2
N
(N m + 1)2
(N - -M)2
Fm (N
M + m)
(N- M)²
FM-m+1-
N2
(N m]
N2
(N- M m - 1)2
We will now show that Sm 2 O, v1 S m S M/2, from which we can directly conclude that
Var [PPURE| 2 Var |LURE For this, note that Fn and FM-m# are themselves non-negative by construction.
Consider first the case where (N-Ma M + m 2 (N MM- +m 1) Here the second term in S,, is non-negative. Furthermore, invoking Lemma 2 with a = - and b m
(noting this satisfies a S M for all 1 I m S M/2 as required) shows that
(N m 1)² (N M)²
(N - mm 20
N2
and the first term is also positive. It thus immediately follows that S,, 2 0 in this scenario.
When this does not hold, (N M + m)? /N2 < (N- BMMMNN/N M m 1)2 and so the second term in Sm is negative. We now instead invoke our assumption that Fm. 2 Fas m+1 to yield
Sm 2 Fm (N
m -W-++11'
(N - M)² (N M + m)²
(N M)
(N M + - 1)3 (15)
N2
(N m)²
N²
We can now invoke Lemma with m and
M m 1 to show that
(N + 1)2
(N M)²
2
N2
(N M + m 1)2
and again with a = M and
to show that
(N - M + m)²
(N- (N - M)²
20.
N2
(N- m)²
Substituting these back into 115) thus again yield the desired result that Sm 2 0 as required.
To cover the case where M is odd, we simply need to note that this adds the following additional term follows:
=(1N ((N- M/2+1/22 + 1/2)²
(N
(N - MM2
1
(M-1/22 1/2)
Var
RPURE]
Var
[LURE]
Fm +
Σ Sm
N2
(N 1/2)3
M
m=11
and we can again invoke Lemma additional term is non-negative.
with a = M/2 - 1/2 and b = -M/2 + 1/2 to show that this
20

---

Published as a conference paper at ICLR 2021
To cover the case where M N, simply note that here
N m + 1)²
m
Sm
Fm +
PM-m+1 m+1
N2
N2
where both terms are clearly positive.
We have now shown that S. 2 0 in all possible scenarios given our assumption on Fm and so we
can conclude that Var [RPURE] 2 Var |LURE
Finally, we need to show the inequality is strict if E1 > 0 and M > 1. For this we first note that Ej ensures Fi > 0 and then consider S1 follows:
(N - M (N 1)
Fi + (N M + 1)2
-1 -1)
S
FM
N
and as the second term is clearly negative and F1 2 FM,
(N M 1)²
(N M)²
2
Fi
N
(N - 1)
(M 1) 2MN + M - 1) Fi
N2 1)
M 1 and N M ensures that each bracketed term is strictly positive. Now 0 and S. 2 0 for all other m, we can conclude that the sum the S., strictly positive, and thus that the inequality in strict.
B.7 PROOF OF THE CONSISTENCY OF PLURE: THEBRREM
Theorem 5. Under the same assumptions as Theorem lim +0 IE (ReURE - r)²] = 0.
Proof.
As before, since ÍLURE is unbiased the MSE simply the variance so:
(ReATRE - -) Var [RPURR]]
E
Var [C(y, fo(x))
Σ 2 E2, Expariii
[ar [wo Li 11mm-1 1 Dpoot]]
N
M2
Taking N = a., already showed in the proof of Theorem 2 that the first of these terms tends to zero as M - 2c.
We also showed that ED (ar (fmit th D.ua) [Wm C.m.] finite given our assumptions. As such, there must be some finite constant such that
Epeaaiiim-i (a Dront [Wm Limil < d
and thus
M
M
M m=1
2 Ppa
[Var (wm Lim 11mm 11 Dpooil] <
M
cm
2
m=1
d
M
N(N - M)
M
(N
m)(N + 1)
21

---

Published as a conference paper at ICLR 2021
and by substituting N- a.M
d M
aMMaM - M)
Σ
(aM (aM- m)aaa - 1)
M
d
aM 2
Σ
M
aM M +1
da M
((a 1)M + 1)²
which clearly tends to zero as M - oc (remembering that 1) and we are done.
B.8 PROOF BIAS AND VARIANCE OF STANDARD ACTIVE LEARNING ESTIMATOR: THEOREM
Theorem 6. Let pm == E [Cim] and Mmla.D == E [Lim [11mm Dpoal.. For R (defined in ①
M
E
Mm
(# r in general)
M
mm
Var R
Var poot
E
R D pool
+ M mmm
E Pp Var (Lim 11:m Dpooil
D
Var [MmleED Dponl]
2 2E Cov Lim E ksm Cin Ppool
M
Proof. The result of the bias follows immediately from definition of pm and the linearity of expecta- tions.
For the variance, we have
Var R
=
R2
R
E D
E
R22
Pooo
R
2 )
Dpu
Var
R
Dponl
R Prool 1)9
R R 2
VarD
ii Pool
E D
Var
Pponi
(16)
puol
where the first term is 1 from the result. For the second term, introducing the notations Mip
12
puol
and
EE [Cim pooo
have
M
2
Var
R
D
pool
E
Lim. MiD)
D pool
M
m=l
M
M
Σ
[Lim - -HiD) (Lie - -H [pooo]
M
m=1
M
M
ΣΣ [LLi..
MmiD + MmmlD mid) (Lis Maa + MaID m1/)) D pool]
M2
1
22

---

Published as a conference paper at ICLR 2021
multiplying out terms and using the symmetry of m and l
M
1
E (Cim
(Li
(Pocul
M
M
M
2
Σ
E
(Lim - (m/lD)
1
Σ
Mk D HiD
D Pponll
M
M
m=1
k=1
M
M HID
(mm|D - HID)
MEID
M
M
m=1
1=1
where we have exploited symmetries in the indices. Now, as 1 M Ek= MuID 1l/, the second and third terms simply zero, have
1
Σ E.EB
E [(Ci... -Lmi [PPD)(P
M
separating out the = k and m < le terms, with symmetry
M
1
Var [Ci.. (Poool +
Σ E [(Crm MLnlD)(Li (m/D)) (rooo]
M
m=1
M
Var [Lim ppooil + 2B (Lim - Hmpp) CErem (Lie - MalD)) Dpoos
M
m=1
M
M Var [Li.. (Ppooll + 2 Cov Cim, Σ kem Lin
(17)
m=11
Here the second term will yield @ in the result when substituted back into [6). For the first term, we have by analogous arguments as those used at the start the proof for Var [t].
Var [Li.. (D Pood = Ei [ar [c... 11 Ppool] ppool] + Var /
(18)
where Pm i..2 := i 111 1. D puul as per the definition in the theorem itself. Substituting this back into (17) and then (16) in turn now yields the desired result through the tower property of expectations, with the first term in (18 producing @ and the second term producing @
B.9 PROOP OF OPTIMAL PROPOSAL DISTRIBUTION: THEOREM 7
Theorem 7. Given non-negative loss, the optimal proposal distribution
q" (imi 11 Ppua) = Lim. /Euggirnn Cn
yields estimators exactly equal to the pool risk, that is ReURE = RIURE Rt almost surely VMM.
Proof. We start by proving the result for the simpler case of RPURE before considering RLURE- To make the notation simpler, will introduce hypothetical indices i, for M. noting that their exact values will not change the proof provided that they are all distinct to each other and the real indices (i.e. that they possible realization of the active sampling process in the setting M N).
23

---

Published as a conference paper at ICLR 2021
For RPURE, the proof follows straightforwardly from substituting the definition of the optimal proposal into the am form of the estimator
RPURE=
Σ
Qm
M
M
m--1
Wmn Lim
Lit
M
N
m=1
1=1
M
N
Li
Li
M
N
N
m=
t=
1=1
Sie
and because all possible indices are uniquely visited
Fm
n=1
R.
The proof proceeds identically for the case of V Li,, because the gradient passes through the summa- tions.
For RLURE. we similarly substitute the optimal proposal into the definition of the estimator
M
BLURE
Σ
Um
Lim
M
m=1
M
N M
Lim
Cim.
Lim
M
N
(N (N-m) - + 1)4² (Jmi 1m 1: Son 1 Dpoco)
m=1
N M ( En Lie
1
Lim
Lim
M
N m
(N m 1)
pulling out the loss
N M
m
Lim
1
+ (N M) Σ
M
N m
(N (N k ++1 =m/(N(N-m))
N
M
Σ M=
C2 - M)
M
(N kN - 1)
(M))
24

---

Published as a conference paper at ICLR 2021
simplifying and rearranging
N
M
N
M m
Lim
1
Σ Ci
M
N m
N
M+1
M
N
M
N m
))
N
Lim
Σ
Li
M
N
m
N
m=l
t= M+1
N
Σ Dim
1
Σ
Cin
N
M=
N
Pm
N
==1
it as required.
Remark 2. The optimal proposal for estimating the gradient of the pool risk, V Vol, with respect to some scalar & is instead) F
(Jmm 11 Dpent) VoLi Enggsi,, (V
Note that when taking gradients with respect to multiple variables, the optimal proposal for each will be different for each.
'One can, in principle, actually construct exact estimator in this scenario as well with the TABI approach Rainfort et al. (2020) by employing two separate proposals that target max (V R, 0) and R.
respectively, then taking the difference between the two resultant estimators.
25

---

Published as a conference paper at ICLR 2021
0.75
VadR]
70
Vanki
0.100
VarRowed
60
VariRoorel
VarR.wul
VariRuari
0.125
50
0.100
20
10
130
10 20
30
40
60
M
(a) Linear Regression
(b) Bayesian Neural Network
Figure 5: For linear regression (a) the biased estimator has the lowest variance, and RLURE improves on RPURE- (b) But for the BNN the variances are comparable, with PLURE the lowest.
C EXPERIMENTAL DETAILS
C.I LINEAR REGRESSION
Our training dataset contains a small cluster of points near x = -1 and two larger clusters at 0 < < 0.5 and 1 < < 1.5, sampled proportionately to the 'true' data distribution. The data distribution from which we select data in a Rao- Blackwellised manner has a probability density function over equal to:
0.12
-1.2 x -0.8
P(x = X)
0.95
S x 0.5
0.95
1.0 1.5
while the distribution over y is then induced by:
[11) #
sin(20x))
max(0,
4
We set 101, where there are points in the small cluster and 96 points in each the other two clusters, and consider 10 < M < 100. We actively sample points without replacement using geometric heuristic that scores the quadratic distance to previously sampled points and then selects points based Boltzman distribution with 3 1 using the normalized scores.
Here, also show in 6 that collected using epsilon-greedy acquisition proposal. The results are aligned with those from the other acquisition distribution we consider in the main body of the paper. This proposal selects the point that has the highest total distance all previously selected points with probability 0.9 and uniformly at random with probability e = 0.1. That is, the acquistion proposal given by:
+
arg max,eeDma. ΣKED (ox x.yl
Piim J; 11:10111 11: Dpmnl)
D
otherwise
D
where of course Durin are the d1:m-1 elements of Dpool-
For all graphs we use 1000 trajectories with different random seeds to calculate error bars. Although, of course, each regression and scoring deterministic, the acquistion distribution is stochastic.
Although the variance of the estimators can be inferred from Figure 2aj we also provide Figure 5a which displays the variance of the estimator directly.
C.2 BAYESIAN NEURAL NETWORK
We train Bayesian neural network using variational inference (Jordan et al.) [1999). In particular, use the radial Bayesian neural network approximating distribution (Farquhar et al. 2020). The details of the hyperparameters used for training are provided in Table T
26

---

Published as a conference paper at ICLR 2021
1.00
Trained with Awce
0.75
6.50
Sue 6-113
-0.00
0.3
-075
-1.0
(a) Bias (like Fig.
2ah
(b) TestMSE (like Fig. 3a
Figure 6: Adopting an alternative proposal distribution-here an epsilon-greedy adaptation
distance-based measure-dee does not change the overall picture for linear regression.
Hyperparameter
Setting description
Architecture
Convolutional Neural Network
Conv
1-16 channels, 5x5 kernel, 2x2 max pool
Conv 2
16-32 channels, 5x5 kernel, 2x2 max pool
Fully connected
128 hidden units
Fully connected 2
10 hidden units
Loss function
Negative log-likelihood
Activation
ReLU
Approximate Inference Algorithm
Radial BNN Variational Inference (Farquhar et al. 2020
Optimization algorithm
Amsgrad (Reddi al. 2018
Learning rate
5-10-4
Batch size
64
Variational training samples
8
Variational test samples
8
Variational acquisition samples
100
Epochs per acquisition
up to 100 (early stopping patience=20), with 1000 copies of data
Starting points
10
Points per acquistion
Acquisition proposal distribution
(bmi 11:mm1 poot
Temperature: T
10,000
Scoring scheme:
BALD (MI between / and output distribution)
Variational Posterior Initial Mean
He et al. 2016
Variational Posterior Initial Standard Deviation
log
Prior
A 0.25")
Dataset
Unbalanced MNIST
Preprocessing
Normalized mean and std inputs.
Validation Split
1000 train points validation
Runtime per result
2-4h
Computing Infrastructure
Nvidia RTX 2080 Ti
Table 1: Experimental Setting Active MNIST.
27

---

Published as a conference paper at ICLR 2021
2.0
Tra ned
1.8
Trained with Rover
Rowy
Entirely Rusas
75
Test
1.4
Test
1.0
Traired R
0.8
Trained with Ryyes
Trained with Ruse
Entirely Ruse
0.4
50
10
20
30
40
M
(a) Test loss
(b) Test accuracy
Figure 7: We contrast the effect of using PLURE throughout the entire acquisition procedure and training (rather than using the same acquisition procedure based R for all estimators). The purple test performance and orange are nearly identical, suggesting the result is not sensitive to this choice.
The unbalanced dataset is constructed by first noising 10% of the training labels, which are assigned random labels, and then selecting a subset of the training dataset such that the numbers of examples of each class is proportional to the ratio (1., 0.5, 0.5, 0.2, 0.2, 0.2, 0.1, 0.1, 0.01, 0.01)-ther is, there are 100 times as many zeros as nines in the unbalanced dataset. (Figure 31 shows a version of this experiment which uses balanced dataset instead, in order to make sure that any effects are not entirely caused by this design choice.) In fact, we took only quarter of this dataset order to speed up acquisition (since each model must be evaluated many times each of the candidate datapoints to estimate the mutual information). 1000 validation points were then removed from this pool to allow early stopping. The remaining points were placed in D poott We then uniformly selected 10 points from P to place in D Durain- Adding noise to the labels and using an unbalanced dataset is designed to mimic the difficult situations that active learning systems despite the relatively simple dataset. However, we used simple dataset for a number of reasons. Active learning is very costly because it requires constant retraining, and accurately measuring the properties of estimators generally requires taking large numbers of samples. The combination makes using more complicated datasets expensive. In addition, because our work establishes lower bound on architecture complexity for which correcting the active learning bias is no longer valuable, establishing that lower bound with MNIST is fact a stronger result than showing a similar result with more complex model.
deployed in practice,
The active learning loop then proceeds by:
training the neural network on Danin using R;
2. scoring p
3. sampling point to be added to Durini
4. Every 3 points, separately trained models on D using fł APPUR, and PEURE and evaluate them.
This ensures that all of the estimators are on data collected under the same sampling distribution for fair comparison. As sense-check, in Figures 7a and 7b we show alternate version in which the first step trains with REERE instead of R. and find that this does not have significant effect on the results.
When we compute the bias fixed neural network in Figure 2b we train a single neural network on 1000 points. We then sample evaluation points using the acquisition proposal distribution from the test dataset and evaluate the bias using those points.
In Figures Sa and [b we review the graphs shown in Figures 3b and 3c this time showing standard errors in order to make clear that the biased å estimator has better performance, while the earlier figures show that the performance is quite variable.
We considered range of alternative proposal distributions. In addition to the Boltzman distribution which we used, we considered a temperature range between 1,000 and 20,000 finding it had relatively little effect. Higher temperatures correspond
certainly picking the highest mutual information
28

---

Published as a conference paper at ICLR 2021
85
Trannd with
Trained with f
1.6
Trained Rave
Trained flous
Trained with Riee
80
Accuroyy
Emo Test
1.2
75
1.0
70
10
20
30
40
50
60
10
20
30
40
60
(a) Test loss
(b) Test accuracy
Figure 8: Versions of Figures 3b and 3c shown with standard errors (45 points) instead of standard deviations. This makes it clearer that the biased Rt has better performance, even if only marginally so.
Thannd
Thinad
Thairad
32-
04-
64
12
18
(a) T=5000 NLL.
(b) T=15000 NLL.
(c) T=20000 NLL.
Traned wii
Tranrd
43-
Trahned
55
(d) T=5000 Acc.
(e) T=15000 Acc.
(i) T=20000 Acc.
Figure 9: Higher temperatures approach a deterministic acquisition function. These also tend to increase the variance of the risk estimator because the weight associated with unlikely points increases, when it happens to be selected. The overall pattern seems fairly consistent, however.
point, which approaches a deterministic proposal. We found that because the mutual information had to be estimated, and was itself random variable, different trajectories still picked very different sets of points. However, for very high temperatures the estimators became higher variance, and for lower temperatures, the acquisition distribution became nearly uniform. In Figure 2 we show the results of networks trained with variety of temperatures other than the 10,000 ultimately used. We also considered a proposal which was simply proportional the scores, but found this was also too close to sampling uniformly for any of the costs or benefits of active learning to be visible.
We considered Monte Carlo dropout as an alternative approximating distribution (Gal & Ghahramani 2015) (see Figures 3e and TOb). We found that the mutual information estimates were compressed in fairly narrow range, consistent with the observation by Osband et al. (2018) that Monte Carlo dropout uncertainties do not necessarily converge unless the dropout probabilities are also optimized (Gal et al. 2017a). While this might be good enough when only the relative score is needed in order to calculate the argmax, for our proposal distribution we would ideally prefer to have good absolute scores well. For this reason, chose the richer approximate posterior distribution instead.
Last, we considered different architecture, using full-connected neural network with single hidden layer with 50 units, also trained as a Radial BNN. This showed higher variance in downstream performance, but was broadly similar the convolutional architecture (see Figures 1Od and 10eh.
29

---

Published as a conference paper at ICLR 2021
(a) FashionMNIST: Accuracy.
(b) MNIST (MCDO): Ace.
(c) MNIST (Balanced): Acc.
16
(d) MNIST (MLP): NLL
(c) MNIST (MLP); Accuracy
Figure 10: Further downstream performance experiments. (a)-(c) are partners to Figures 3d
3e and
3f (d) and (e) show similar results for a smaller multi-layer perceptron (with one hidden layer of 50 units). In all cases the results broadly mirror the results in the main paper.
Reference
Application
Corrects Bias
Acknowledges Bias Notes
Sener & Savarese 2018
Shen et al.
Beluch 2018
Haut et al.
2018
Sinha et 2019
Siddhant & Lipton 2018
Ghosal et al
2019
Yang ct al. 2018
Yoo & K wcon
2019
Kirsch et al.
2019
Huang et al.
2018
Wen et al.
2018
Chen et al. 2019
Discusses bias in D pood Discusses bias in D Pood
Zhang & Lce
2019
Kellenberger al.
2019
Table 2: Existing applications of deep active learning rarely acknowledge the bias introduced by actively sampling points and do not, to the best of our knowledge, try to correct it.
D DEEP ACTIVE LEARNING IN PRACTICE
In Table we show an informal survey of highly cited papers citing Gal et al. (2017b). which introduced active learning computer vision using deep convolutional neural networks. Across range of papers including theory papers as well applications ranging from agriculture to molecular science only two papers acknowledged the bias introduced by actively sampling and none of papers took steps address it. It is worth noting, though, that at least two papers motivated their use of active learning by observing that they expected their training data to already be unrepresentative of the population data and saw active learning work, unless you explicitly assume that the actively chosen distribution is more like the population distribution, but interesting phenomenon observe in practical applications of active learning.
way address that bias. This does not quite
30


Reviews:
[{"review_id": "Pfd9kZIUdF", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The motivation of the paper is well done and it is written clearly as well as well organized although could be improved for the sake of more clarity and precision. \n\nThis kind of analysis is important to understand the successes/failures of active learning strategies commonly used in ML and grounding the analysis in bias-variance trade-off is a very useful start. \n\nI have a couple of clarifying questions that I hope the authors can elaborate on. My main suggestion would be to have an even more explicit discussion (in a separate subsection) on connections to the loss + different acquisition/active learning strategies. \n\nIn the analysis of Thm 5, I don't understand what the authors mean by \"when things are working well\", the expected variance should be low for term 2. \n\nThe analysis in Section 7 and connections to fitting model parameters vs acquistion strategies is also unclear. What exactly is the choice of R_X when the acquisition strategy minimizes $R_{PURE}$ or $R_{SURE}$? Rather why should optimization itself not use these estimators (maybe some thing else other than $\\hat{R}$ to update model parameters? \n\nI think elaborating these will help readers separate the effects of i) acquisition strategies, ii) updating parameters and ii) choice of risk estimators to be used in both cases. All these moving parts are meshed together in between focusing on proofs. I think if the authors could elaborate on how these play together in a more prescriptive manner, it will help the manuscript.\n\nIn the discussion, the authors talk about active model selection. What is active model selection and can authors elaborate what they mean the proposed estimators are useful in this setting? \n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MTTmIncjnw8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis paper analyzes the bias of models in pool-based active learning settings where the sampling procedure is probabilistic (non-deterministic). It proposes two unbiased estimators of the population risk that weight the loss for each sampled data point. Empirical experiments demonstrate that these unbiased estimators work well for active learning settings with under-parameterized models, but are less effective for over-parameterized models. For the latter case, the authors provide meaningful insights into why biased estimators of population risk may actually be beneficial for over-parameterized models.\n\n### Reasons for score\n\n**Strong points**\n\n1. The authors identify a common problem in active learning, namely the problem of non-IID data. The authors also propose theoretically-sound solutions to addressing the active learning bias.\n\n2. The authors experientally demonstrate their estimators in both linear regression and a deep learning experiment, showing how their estimators are beneficial in one case but not the other.\n\n3. The paper explains why the proposed estimators may have lower variance than the standard estimator for population risk.\n\n**Room for improvement and/or more clarity**\n\n1. The paper mentions the \"quality\" of the \"acquisition proposal\" several times (e.g., p.4, p.6, Figure 2, etc.). However, it is unclear what is meant by \"quality.\" What makes for a \"good\" acquisition proposal?\n\n2. The paper only discusses the setting where the active learning sampling procedure is probabilistic (non-deterministic), with non-zero support over all remaining data points in the pool. However, many active learning procedures proposed in the literature are deterministic (e.g., choosing the K examples with highest loss, or the greedy core-set approach proposed by Sener & Savarese (2018)). Could the authors provide more context for bias in these deterministic active learning strategies?\n3. While I did not spend time reading the appendix in detail, it seems that points for the BNN were selected under $\\tilde{R}$ (the biased sub-sample empirical risk). How do the results compare if the points were selected under $R_{SURE}$, which is a more relevant setting given that $R_{SURE}$ is the proposed estimator?\n4. Other than running active learning twice (once using $\\tilde{R}$ and once using $R_{SURE}$), are there methods to determine when one would be preferred over the other, especially in deep learning settings?\n\n\n### Minor comments /  typos / formatting concerns\n\n(these did not affect my score)\n\n1. Please use vector graphics for figures. For example, save the figures as SVG or PDF files (instead of JPG or PNG) and then include them in the LaTeX file. In particular, the legend in Figure 2a is difficult to read.\n\n2. Figure 2: Does \"shading is one standard deviation\" mean +/- 1 std (for a total of 2 std), or +/- 0.5 std (for a total of 1 std)? Please clarify.\n\n3. In Equation (5), why not factor out the $1/N$ in front of the summation?\n\n4. The authors write,\n> \"Using our corrective weights recovers the ideal line.\" (p.6)\n\n    Unless I am reading the graph wrong, this sentence is slightly misleading. It seems like the linear regression model trained using the corrective weights much more closely approximates the ideal line, but doesn't recover the ideal line exactly.\n\n5. In general, the paper is written in an \"opinionated\" or imprecise manner which detracts from the main points of the paper. Words like \"surprising\" and \"greatly\" are unnecessary. Phrases such as \"better variance\" should be replaced with more precise terminology, such as \"lower variance\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jn2y8QBbs6G", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: \nThe authors consider the bias (in the risk) introduced by active sampling strategies with respect to the true underlying data generating distribution. They then propose two estimators of the risk -- SURE and PURE -- that are unbiased and asymptotically consistent under certain assumptions. The authors consider two toy examples where they show the existence of active learning bias, and the effect of removing this. In particular, the authors notice that while training a linear regression (based on actively acquired datapoints) with their unbiased risks improves test loss, the opposite happens for a Bayesian Neural Network (BNN). They then provide a potential explanation for this phenomenon. \n\n**+ves**: \n+ The risk estimator proposals make sense, and their motivation is clear. \n+ The calculations (and the proofs) are presented very clearly; the overall writing quality and the story arc of the paper is very clear\n\n**Concerns** \n- The condition that the proposal distribution needs a non-trivial weight on the entire pool of data seems too strong. Intuitively, if there are irrelevant parts of the distribution (say, far away from the decision boundary), a proposal distribution that doesn't focus there shouldn't introduce too much bias. It would have been nice to see a more nuanced version of this analysis. \n- In fact, the variance depends on this weight (as $1/\\beta^2$). This could imply an extremely large variance in several reasonable scenarios, and hence affect the performance of any active learning algorithm. \n- The authors address the above concern by claiming that this paper is only about the \"statistical bias\" of active learning. I find this unsatisfactory since without the aspect of downstream learning, this is simply an estimation of an expectation with samples from a mismatched distribution. \n- The experimental section could have used significant strengthening. Especially given the difficulty of making theoretical claims about generalization, it would have been useful to see more experiments that shed light on how a learning algorithm that adaptively selects data can benefit from the proposal of this paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-CFmPDuJ2IQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**The changes of the review after rebuttal are  indicated in bold text.**\n\n### Summary\nThe paper discusses the issue of bias in active learning, the problem of actively selecting new training points to label when the labelling task is expensive. \nBecause of the labelling cost, we wish to select only the most informative points, which are not representative of the full dataset, hence incurring a statistical bias. \nThe classical estimator of the risk is the unweighted average loss, which carries the bias of the active training set.\nThe authors propose 2 unbiased estimators of the risk, named $R_{PURE}$ and $R_{SURE}$, in order to treat the statistical bias.\nAlthough both unbiased, they differ in the ponderation on the loss for each active sample and do not have the same variance. \nWhile $R_{PURE}$ depends on the order in which the observations are actively chosen, $R_{SURE}$ removes this dependency. \nBoth estimators are tested and compared with the classical biased risk estimator in two settings: a linear model applied on a toy dataset, \nand a Bayesian convolutional neural network (BNN) applied on a modified version of MNIST putting the data in more difficult setting.\nThe authors show that both their estimators behave much better than the standard one in the linear case, while they are very similar albeit a little worse in the MNIST problem.\nThey finish the paper by explaining that unbiased estimators of the risk are better for low parametrized models, such as the linear one, which are very dependent of the statistical bias;\nwhile they decrease a bit the performances of an over-parametrized estimator, such as the BNN, for which the statistical bias seems to be cancelled out with the overfitting bias.\n\n### Strengths\nThe paper is well written and clear. It addresses the interesting problem of active learning, and it is very insightful of the particular issue of bias in that context.\nEach expression is explained with the meaning of its components, and the authors attempt to provide insight to both the positive and negative results.\nIt is very refreshing to see negative results, showing clearly the limitations of the proposed estimators, and to have a clear suggestion from the authors as to when to use which estimator (theirs or the biased one).\nThe math seems correct, although I have not checked all the proofs. \n\n### Weaknesses and concerns\n1. Proofs\nThe explanations often rely more on intuition than on mathematical proof. While they may be true, it seems to me that it lacks a bit of theoretical grounding.\n**After discussion with the authors, it turns out that this comment was not clear enough. It concerned only the paragraphs after Theorems 3 and 5. I apreciate greatly that the authors made an effort to clarify these paragraphs.**\n\n2. Experiment\n    a. Limitations\nThe experimental study is limited: the estimators have been applied only on two extreme models (a linear model and a BNN), and for each case, only one dataset has been tested. While both are very much used in practice, it is not enough to draw conclusions. There should at least be an emphasis of that, saying that it is only a preliminary, and that more tests will be performed in a more extensive version of the work. Has it been tested on more models (e.g. random forests) or on various architectures of neural networks, as well as on several datasets?\nAs for the choice of the proposal distribution, it seems only one was tested in the linear setting, while a range of them were tested for the BNN. This should be more explicit in the main article, referring to the appendix for more details.\n    b. Reproducibility and relevance of the experiment\nThere are issues on the toy example:\n      * it is a highly nonlinear dataset on which a linear model is trained, which is weird: what happens when using the proposed estimators to train a linear model on (close to) linear data?\n      * the density function on which $X$ is drawn does not seem to sum to 1.\n      * there seems to be an issue in the generation of $y$ (Eq. 124), as there no bias added, yet Figure 1 shows an oscillation for $y$ between 1 and 2.5 and $x$ in $[1, 1.5]$, while I found an oscillation around 0 by applying the formula as specified\n\n  In the modified MNIST dataset:\n      - it seems to me that the proportion of each class used for the pool subset makes this particular dataset somewhat easier rather than harder, as it basically removes the ambiguity between numbers that look alike; for instance, there are very few observations of 9, and a few of 6, and there are 5 times less 7 than 1; in such a case, the accuracy is not a good measure of the quality, as it will be good even if the smaller classes are poorly classified. \n      - Has there been a test on a balanced subset?\n\n**In the revision, the authors added a few experiments to complete the first ones, namely adding a third dataset (Fashion MNIST), testing a balanced subset for MNIST, and testing another acquisition function to see its impact on the results. I think this gives more grounding to the nice theoretical results and insights.**\n\n3. Active sampling for test\nThe authors claim that their estimators should have a positive impact on the actively selecting samples at test time. This claim appears in the introduction and in the conclusion, but it seems more like intuition and there is no explanation as to why this may be true. \nI suggest removing it from the introduction, as it is clearly future work, and if possible add some explanation behind the intuition.\n\n### Minor comments:\n- Please put equation numbers only on equations you refer to, not on all equations. \n- The name $R_{SURE}$ can be confused with Stein's Unbiased Risk Estimator (even though I assume it is so as a reference to that estimator).\n- In Section 6, the acronym BALD is not defined\n- In Figure 4a, the colors and order in the legend are reversed for $R_{PURE}$ and $R_{SURE}$\n\n### Overall evaluation \nI believe this is very promising and insightful work, tackling the important issue of bias. \nHowever, I cannot give it a high score due to the issues I raised about the experiment.\n\n**The revision answered my concerns about the experiment by enlarging it, which is why I upgrade the score I gave. I think it is a very good and interesting paper.**\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an excellent paper that provides analytical and empirical insights on the sample selection bias of pool-based active learning. It provides two very practical methods of removing the bias.  Also, it shows that in over-parameterized networks (like modern neural networks), the active learning bias could actually be useful.   I enjoyed reading the paper.  Reviewers are mostly very positive about the paper.  Experiments in the initial version were limited, and the authors have since added more experiments.   With the increasing interest on learning with limited data, this paper is very timely and useful.  I expect the paper to be of interest to many in the community.
Decision: Accept (Spotlight)