Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds

We design a new algorithm for batch active learning with deep neural network models. Our algorithm, Batch Active learning by Diverse Gradient Embeddings (BADGE), samples groups of points that are disparate and high-magnitude when represented in a hallucinated gradient space, a strategy designed to incorporate both predictive uncertainty and sample diversity into every selected batch. Crucially, BADGE trades off between diversity and uncertainty without requiring any hand-tuned hyperparameters. We show that while other approaches sometimes succeed for particular batch sizes or architectures, BADGE consistently performs as well or better, making it a versatile option for practical active learning problems.


INTRODUCTION
In recent years, deep neural networks have produced state-of-the-art results on a variety of important supervised learning tasks. However, many of these successes have been limited to domains where large amounts of labeled data are available. A promising approach for minimizing labeling effort is active learning, a learning protocol where labels can be requested by the algorithm in a sequential, feedback-driven fashion. Active learning algorithms aim to identify and label only maximally-informative samples, so that a high-performing classifier can be trained with minimal labeling effort. As such, a robust active learning algorithm for deep neural networks may considerably expand the domains in which these models are applicable.
How should we design a practical, general-purpose, label-efficient active learning algorithm for deep neural networks? Theory for active learning suggests a version-space-based approach (Cohn et al., 1994;Balcan et al., 2006), which explicitly or implicitly maintains a set of plausible models, and queries examples for which these models make different predictions. But when using highly expressive models like neural networks, these algorithms degenerate to querying every example. Further, the computational overhead of training deep neural networks precludes approaches that update the model to best fit data after each label query, as is often done (exactly or approximately) for linear methods (Beygelzimer et al., 2010;Cesa-Bianchi et al., 2009). Unfortunately, the theory provides little guidance for these models.
One option is to use the network's uncertainty to inform a query strategy, for example by labeling samples for which the model is least confident. In a batch setting, however, this creates a pathological scenario where data in the batch are nearly identical, a clear inefficiency. Remedying this issue, we could select samples to maximize batch diversity, but this might choose points that provide little new information to the model. For these reasons, methods that exploit just uncertainty or diversity do not consistently work well across model architectures, batch sizes, or datasets. An algorithm that performs well when using a ResNet, for For all examples x in U \ S: 1. Compute its hypothetical labelŷ(x) = h θt (x). 2. Compute gradient embedding g x = ∂ ∂θout CE (f (x; θ),ŷ(x))| θ=θt , where θ out refers to parameters of the final (output) layer.

5:
Compute S t , a random subset of U \ S, using the k-MEANS++ seeding algorithm on {g x : x ∈ U \ S} and query for their labels. 3 ALGORITHM BADGE, described in Algorithm 1, starts by drawing an initial set of M examples uniformly at random from U and asking for their labels. It then proceeds iteratively, performing two main computations at each step t: a gradient embedding computation and a sampling computation. Specifically, at each step t, for every x in the pool U , we compute the labelŷ(x) preferred by the current model, and the gradient g x of the loss on (x,ŷ(x)) with respect to the parameters of the last layer of the network. Given these gradient embedding vectors {g x : x ∈ U }, BADGE selects a set of points by sampling via the k-MEANS++ initialization scheme (Arthur and Vassilvitskii, 2007). The algorithm queries the labels of these examples, retrains the model, and repeats.
We now describe the main computations -the embedding and sampling steps -in more detail.
The gradient embedding. Since deep neural networks are optimized using gradient-based methods, we capture uncertainty about an example through the lens of gradients. In particular, we consider the model uncertain about an example if knowing the label induces a large gradient of the loss with respect to the model parameters and hence a large update to the model. A difficulty with this reasoning is that we need to know the label to compute the gradient. As a proxy, we compute the gradient as if the model's current prediction on the example is the true label. We show in Proposition 1 that, assuming a common structure satisfied by most natural neural networks, the gradient norm with respect to the last layer using this label provides a lower bound on the gradient norm induced by any other label. In addition, under that assumption, the length of this hypothetical gradient vector captures the uncertainty of the model on the example: if the model is highly certain about the example's label, then the example's gradient embedding will have a small norm, and vice versa for samples where the model is uncertain (see example below). Thus, the gradient embedding conveys information both about the model's uncertainty and potential update direction upon receiving a label at an example.
The sampling step. We want the newly-acquired labeled samples to induce large and diverse changes to the model. To this end, we want the selection procedure to favor both sample magnitude and batch diversity. Specifically, we want to avoid the pathology of, for example, selecting a batch of k similar samples where even just a single label could alleviate our uncertainty on all remaining (k − 1) samples.
A natural way of making this selection without introducing additional hyperparameters is to sample from a k-Determinantal Point Process (k-DPP; (Kulesza and Taskar, 2011) (2018) showed that in experimental design for least square linear regression settings, learning from samples drawn from a k-DPP can have much smaller mean square prediction error than learning from iid samples. In this process, when the batch size is very low, the selection will naturally favor points with a large length, which corresponds to uncertainty in our space. When the batch size is large, the sampler focuses more on diversity because linear independence, which is more difficult to achieve for large k, is required to make the Gram determinant non-zero.
Unfortunately, sampling from a k-DPP is not trivial. Many sampling algorithms (Kang, 2013;Anari et al., 2016) rely on MCMC, where mixing time poses a significant computational hurdle. The state-of-the-art algorithm of Dereziński (2018) has a high-order polynomial running time in the batch size and the embedding dimension. To overcome this computational hurdle, we suggest instead sampling using the k-MEANS++ seeding algorithm (Arthur and Vassilvitskii, 2007), originally made to produce a good initialization for k-means clustering. k-MEANS++ seeding selects centroids by iteratively sampling points in proportion to their squared distances from the nearest centroid that has already been chosen, which, like a k-DPP, tends to select a diverse batch of high-magnitude samples. For completeness, we give a formal description of the k-MEANS++ seeding algorithm in Appendix A.
Example: multiclass classification with softmax activations. Consider a neural network f where the last nonlinearity is a softmax, i.e. σ(z) i = e z i / K j=1 e z j . Specifically, f is parametrized by θ = (W, V ), where θ out = W = (W 1 , . . . , W K ) ∈ R K×d are the weights of the last layer, and V consists of weights of all previous layers. This means that f (x; θ) = σ(W · z(x; V )), where z is the nonlinear function that maps an input x to the output of the network's penultimate layer. Let us fix an unlabeled sample x and define p i = f (x; θ) i . With this notation, we have , y) for a label y and g x = gŷ x as the gradient embedding in our algorithm, wherê y = argmax i∈[K] p i . Then the i-th block of g x (i.e. the gradients corresponding to label i) is Based on this expression, we can make the following observations: 1. Each block of g x is a scaling of z(x; V ), which is the output of the penultimate layer of the network. In this respect, g x captures x's representation information similar to that of Sener and Savarese (2018). 2. Proposition 1 below shows that the norm of g x is a lower bound on the norm of the loss gradient induced by the example with true label y with respect to the weights in the last layer, that is g x ≤ g y x . This suggests that the norm of g x conservatively estimates the example's influence on the current model. 3. If the current model θ is highly confident about x, i.e. vector p is skewed towards a standard basis vector e j , thenŷ = j, and vector (p i − I(ŷ = i)) K i=1 has a small length. Therefore, g x has a small length as well. Such high-confidence examples tend to have gradient embeddings of small magnitude, which are unlikely to be repeatedly selected by k-MEANS++ at iteration t. Proposition 1. For all y ∈ {1, . . . , K}, let g y x = ∂ ∂W CE (f (x; θ), y). Then Consequently,ŷ = argmin y∈[K] g y x .
Proof. Observe that by Equation (1), The second claim follows from the fact thatŷ = argmax y∈[K] p y .
This simple sampler tends to produce diverse batches similar to a k-DPP. As shown in Figure 1, switching between the two samplers does not affect the active learner's statistical performance but greatly improves its computational performance. Appendix G compares run time and test accuracy for both k-MEANS++ and k-DPP based sampling based on the gradient embeddings of the unlabeled examples. Figure 2 illustrates the batch diversity and average gradient magnitude per selected batch for a variety of sampling strategies. As expected, both k-DPPs and k-MEANS++ tend to select samples that are diverse (as measured by the magnitude of their Gram determinant) and high magnitude. Other samplers, such as furthest-first traversal for k-Center clustering (FF-k-CENTER), do not seem to have this property. The FF-k-CENTER algorithm is the sampling choice of the CORESET approach to active learning, which we describe in the proceeding section (Sener and Savarese, 2018). Appendix F discusses diversity with respect to uncertainty-based approaches.
Appendix B provides further justification for why BADGE yields better updates than vanilla uncertainty sampling in the special case of binary logistic regression (K = 2 and z(x; V ) = x).

EXPERIMENTS
We evaluate the performance of BADGE against several algorithms from the literature. In our experiments, we seek to answer the following question: How robust are the learning algorithms to choices of neural network architecture, batch size, and dataset?
To ensure a comprehensive comparison among all algorithms, we evaluate them in a batch-mode active learning setup with M = 100 being the number of initial random labeled examples and batch size B varying from {100, 1000, 10000}. The following is a list of the baseline algorithms evaluated; the first performs representative sampling, the next three are uncertainty based, the fifth is a hybrid of representative and uncertainty-based approaches, and the last is traditional supervised learning. We consider three neural network architectures: a two-layer Perceptron with ReLU activations (MLP), an 18-layer convolutional ResNet (He et al., 2016), and an 11-layer VGG network (Simonyan and Zisserman, 2014). We evaluate our algorithms using three image datasets, SVHN (Netzer et al., 2011), CIFAR10 (Krizhevsky, 2009 and MNIST (LeCun et al., 1998) 1 , and four non-image datasets from the OpenML repository (#6, #155, #156, and #184). 2 We study each situation with 7 active learning algorithms, including BADGE, making for 231 total experiments.

k-DPP k-means++
For the image datasets, the embedding dimensionality in the MLP is 256. For the OpenML datasets, the embedding dimensionality of the MLP is 1024, as more capacity helps the model fit training data. We fit Learning curves. Here we show examples of learning curves that highlight some of the phenomena we observe related to the fragility of active learning algorithms with respect to batch size, architecture, and dataset.
Often, we see that in early rounds of training, it is better to do diversity sampling, and later in training, it is better to do uncertainty sampling. This kind of event is demonstrated in Figure 3a, which shows CORESET outperforming confidence-based methods at first, but then doing worse than these methods later on. Element Pi,j corresponds roughly to the number of times algorithm i outperforms algorithm j. Column-wise averages at the bottom show overall performance (lower is better).

BADGE ALBL Coreset Conf
In this figure, BADGE performs as well as diversity sampling when that strategy does best, and as well as uncertainty sampling once those methods start outpacing CORESET. This suggests that BADGE is a good choice regardless of labeling budget.
Separately, we notice that diversity sampling only seems to work well when either the model has good architectural priors (inductive biases) built in, or when the data are easy to learn. Otherwise, penultimate layer representations are not meaningful, and diverse sampling can be deleterious. For this reason, CORESET often performs worse than random on sufficiently complex data when not using a convolutional network ( Figure 3b). That is, the diversity induced by unconditional random sampling can often yield a batch that better represents the data. Even when batch size is large and the model has helpful inductive biases, the uncertainty information in BADGE can give it an advantage over pure diversity approaches ( Figure 3c). Comprehensive plots of this kind, spanning architecture, dataset, and batch size are in Appendix C.
Pairwise comparisons. We next show a comprehensive pairwise comparison of algorithms over all datasets (D), batch sizes (B), model architectures (A), and label budgets (L). From the learning curves, it can be observed that when label budgets are large enough, all algorithms eventually reach similar performance, making the comparison between them uninteresting in the large sample limit. For this reason, for each combination of (D, B, A), we select a set of labeling budgets L where learning is still progressing. We experimented with three different batch sizes and eleven dataset-architecture pairs, making the total number of (D, B, A) combinations 3 × 11 = 33. Specifically, we compute n 0 , the smallest number of labels where RAND's accuracy reaches 99% of its final accuracy, and choose label budget The calculation of scores in the penalty matrix P follows the following protocol: For each (D, B, A, L) combination and each pair of algorithms (i, j), we have 5 test errors (one for each repeated run), e 1 i , . . . , e 5 i and e 1 j , . . . , e 5 j respectively. We compute the t-score as t = We use the two-sided t-test to compare pairs of algorithms: algorithm i is said to beat algorithm j in this setting if t > 2.776 (the critical point of p-value being 0.05), and similarly algorithm j beats algorithm i if t < −2.776. For each (D, B, A) combination, suppose there are n D,B,A different values of L. Then, for each L, if algorithm i beats algorithm j, we accumulate a penalty of 1/n D,B,A to P i,j ; otherwise, if algorithm j beats algorithm i, we accumulate a penalty of 1/n D,B,A to P j,i . The choice of the penalty value 1/n D,B,A is to ensure that every (D, B, A) combination is assigned equal influence in the aggregated matrix. Therefore, the largest entry of P is at most 33, the total number of (D, B, A) combinations. Intuitively, each row i indicates the number of settings in which algorithm i beats other algorithms and each column j indicates the number of settings in which algorithm j is beaten by another algorithm.
The penalty matrix in Figure 4 summarizes all experiments, showing that BADGE generally outperforms baselines. Matrices grouped by batch size and architecture in Appendix D show a similar trend.
Cumulative distribution functions of normalized errors. For each (D, B, A, L) combination, we compute the average error for each algorithm i asē i = 1 5 5 l=1 e l i . To ensure that the errors of these algorithms are on the same scale in all settings, we compute the normalized error of every algorithm i, defined as ne i =ē i /ē r , where r is the index of the RAND algorithm. By definition, the normalized errors of the RAND algorithm are identically 1 in all settings. Like with penalty matrices, for each (D, B, A) combination, we only consider a subset of L values from the set M + 2 m−1 B : m ∈ [ log((n 0 − M )/B) ] . We assign a weight proportional to 1/n D,B,A to each (D, B, A, L) combination, where there are n D,B,A different L values for this combination of (D, B, A). We then plot the cumulative distribution functions (CDFs) of the normalized errors of all algorithms: for a value of x, the y value is the total weight of settings where the algorithm has normalized error at most x; in general, an algorithm that has a higher CDF value has better performance.
We plot the generated CDFs in Figures 5, 22 and 23. We can see from Figure 5 that BADGE has the best overall performance. In addition, from Figures 22 and 23 in Appendix E, we can conclude that when batch size is small (100 or 1000) or when an MLP is used, both BADGE and MARG perform best. However, in the regime when the batch size is large (10000), MARG's performance degrades, while BADGE, ALBL and CORESET are the best performing approaches.

RELATED WORK
Active learning is a been well-studied problem (Settles, 2010;Dasgupta, 2011;Hanneke, 2014). There are two major strategies for active learning-representative sampling and uncertainty sampling.
Representative sampling algorithms select batches of unlabeled examples that are representative of the unlabeled set to ask for labels. It is based on the intuition that the sets of representative examples chosen, once labeled, can act as a surrogate for the full dataset. Consequently, performing loss minimization on the surrogate suffices to ensure a low error with respect to the full dataset. In the context of deep learning, Sener and Savarese (2018); Geifman and El-Yaniv (2017)  There is also a large body of literature on batch mode active learning, where the learner is asked to select a batch of samples within each round (Guo and Schuurmans, 2008;Wang and Ye, 2015;Chen and Krause;Wei et al., 2015;Kirsch et al., 2019). In these works, batch selection is often formulated as an optimization problem with objectives based on (upper bounds of) average log-likelihood, average squared loss, etc.
A different query criterion based on expected gradient length (EGL) has been proposed in the as well (Settles et al., 2008). In recent work, Huang et al. (2016) show that the EGL criterion is related to the T -optimality criterion in experimental design. They further demonstrate that the samples selected by EGL are very different from those by entropy-based uncertainty criterion. Zhang et al. (2017a) use the EGL criterion in active sentence and document classification with CNNs. These approaches differ most substantially from BADGE in that they do not take into account the diversity of the examples queried within each batch.
There is a wide array of theoretical articles that focus on the related problem of adaptive subsampling for fully-labeled datasets in regression settings (Han et al., 2016;Wang et al., 2018;Ting and Brochu, 2018). Empirical studies of batch stochastic gradient descent also employ adaptive sampling to "emphasize" hard or representative examples (Zhang et al., 2017b;Chang et al., 2017). These works aim at reducing computation costs or finding a better local optimal solution, as opposed to reducing label costs. Nevertheless, our work is inspired by their sampling criteria, which also emphasize samples that induce large updates to the model.
As mentioned earlier, our sampling criterion has resemblance to sampling from k-determinantal point processes (Kulesza and Taskar, 2011). Note that in multiclass classification settings, our gradient-based embedding of an example can be viewed as the outer product of the original embedding in the penultimate layer and a probability score vector that encodes the uncertainty information on this example (see Section 3). In this view, the penultimate layer embedding characterizes the diversity of each example, whereas the probability score vector characterizes the quality of each example. The k-DPP is also a natural probabilistic tool for sampling that trades off between quality and diversity (See Kulesza et al., 2012, Section 3.1). We remark that concurrent to our work, Bıyık et al. (2019) develops k-DPP based active learning algorithms based on this principle by explicitly designing diversity and uncertainty measures.

DISCUSSION
We have established that BADGE is empirically an effective deep active learning algorithm across different architectures and batch sizes, performing similar to or better than other active learning algorithms. A fundamental remaining question is: "Why?" While deep learning is notoriously difficult to analyze theoretically, there are several intuitively appealing properties of BADGE: Stephen Mussmann and Percy S Liang. Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss. In Neural Information Processing Systems, 2018.
A THE k-MEANS++ SEEDING ALGORITHM Here we briefly review the k-MEANS++ seeding algorithm by (Arthur and Vassilvitskii, 2007). Its basic idea is to perform sequential sampling of k centers, where each new center is sampled from the ground set with probability proportional to the squared distance to its nearest center. It is shown in (Arthur and Vassilvitskii, 2007) that the set of centers returned is guaranteed to approximate the k-means objective function in expectation, thus ensuring diversity.
Algorithm 2 The k-MEANS++ seeding algorithm (Arthur and Vassilvitskii, 2007) end for return C k .

B BADGE FOR BINARY LOGISTIC REGRESSION
We consider instantiating BADGE for binary logistic regression, where Y = {−1, +1}. Given a linear classifier w, we define the predictive probability of w on x as p w (y|x, θ) = σ(yw · x), where σ(z) = 1 1+e −z is the sigmoid funciton.
Recall thatŷ =ŷ(x) is the hallucinated label: The binary logistic loss of classifier w on example (x, y) is defined as: (w, (x, y)) = ln(1 + exp(−yw · x)). Now, given model w and example x, we defineĝ x = ∂ ∂w (w, (x,ŷ)) = (1 − p w (ŷ|x, θ)) · (−ŷ · x) as the loss gradient induced by the example with hallucinated label, andg x = ∂ ∂w (w, (x, y)) = (1−p w (y|x, θ))·(−y·x) as the loss gradient induced by the example with true label. Suppose that BADGE only selects examples from region S w = {x : w · x = 0}, then as p w (+1|x, θ) = p w (−1|x, θ) = 1 2 , we have that for all x in S w ,ĝ x = s x · g x for some s x ∈ {±1}. This implies that, sampling from a DPP induced byĝ x 's is equivalent to sampling from a DPP induced by g x 's. It is noted in Mussmann and Liang (2018) that uncertainty sampling (i.e. sampling from D |Sw ) implicitly performs preconditioned stochastic gradient descent on the expected 0-1 loss. In addition, it has been shown that DPP sampling over gradients may reduce the variance of the mini-batch stochastic gradient updates (Zhang et al., 2017b); this suggests that BADGE, when restricted its sampling over low-margin regions (S w ), improves over uncertainty sampling by collecting examples that together induce lower-variance updates on the gradient direction of expected 0-1 loss.

C ALL LEARNING CURVES
We plot all learning curves (test accuracy as a function of the number of labeled example queried) in Figures 6 to 12. In addition, we zoom into regions of the learning curves that discriminates the performance of all algorithms in Figures 13 to 19.

D PAIRWISE COMPARISONS OF ALGORITHMS
In addition to Figure 4 in the main text, we also provide penalty matrices (Figures 20 and 21), where the results are aggregated by conditioning on a fixed batch size (100, 1000 and 10000) or on a fixed neural network model (MLP, ResNet and VGG). For each penalty matrix, the parenthesized number in its title is the   total number of (D, B, A) combinations aggregated; as discussed in Section 4, this is also an upper bound on all its entries. It can be seen that uncertainty-based methods (e.g. MARG) perform well only in small batch size regimes (100) or when using MLP models; representative sampling based methods (e.g. CORESET) only perform well in large batch size regimes (10000) or when using ResNet or VGG models. In contrast, BADGE's performance is competitive across all batch sizes and neural network models. The k-centers sampler finds points that are not as diverse or high-magnitude as other samplers. Notice also that k-MEANS++ tends to actually select samples that are both more diverse and higher-magnitude than a k-DPP, a potential pathology of the k-DPP's degree of stochastisity. Among all algorithms, CONF has the largest average norm of gradient embeddings within a batch; however, in OpenML #6, and the first few interations of SVHN, some batches have a log Gram determinant of −∞ (shown as gaps in the curve), which shows that CONF sometimes selects batches that are inferior in diversity.
many gaps in the CONF plot seem to correspond to situations in which CONF performs poorly in terms of accuracy (see Figure 13 for the corresponding learning curve). Both k-DPP and FF-k-CENTER (an algorithm that approximately minimizes k-center objective) select batches that have lower diversity than k-MEANS++  and space complexity of O(k 2 + kd), where τ is the number of sampling steps. We set τ as 5k ln k in our experiment. The comparisons for batch size 10000 are not shown here as the implementation of k-DPP sampling runs out of memory.
It can be seen from the figures that, although k-DPP and k-MEANS++ are based on different sampling criteria, the classification accuracies of their induced active learning algorithm are similar. In addition, when large batch sizes are required (e.g. k = 1000), the running times of k-DPP sampling are generally much higher than those of k-MEANS++.