summaries: This paper is in the field of Active learning, which has proven to be useful for minimizing labeling costs by selecting the most informative samples from unlabeled datasets, which are then to be labeled by a human in the loop. The goal is to achieve high accuracy of the trained model, while minimising the number of points to be labeled by the human in the loop. However, as the authors say, many existing state of the art active learning methods are trained on datasets which are not very realistic, and they do not perform well in many common real-life situations such as imbalance or rare classes, out-of-distribution data in the unlabeled set, and redundancy. Given the size of these datasets, cleaning them manually is not realistic. The authors propose an active learning framework which they call SIMILAR, which uses submodular information measures as acquisition functions. They argue that SIMILAR performs well on the realistic scenarios mentioned previously, and empirically demonstrate that SIMILAR outperforms previous state of the art methods in these scenarios.   In this paper, the authors propose methods for selecting a query set for batch active learning. These methods select a query set by maximizing a criterion based on submodular functions such as facility location function, graph cut function, and log-determinant function. The similarity matrix between data points, used in the definition of submodular functions, is defined by the inner product of the gradients of loss functions.  The authors empirically validate the efficiency of the proposed methods for batch active learning with rare classes, redundancy, and out-of-distribution data points. They adopt standard image datasets and standard deep neural network models. In each experimental setting, some of the proposed methods outperform existing methods for batch active learning. This paper proposes a "unified active learning framework". The key element of this framework is a submodular information measure, denoted by $I_f(A;Q|P)$ where $f$ is a submodular score function, $A$ is a set of unlabeled samples whose "value" is measured, and $P$ and $Q$ are set of samples to be specified by the algorithm as parameters. $I_f(A;Q|P)$ is supposed to measure similarity and dissimilarity among $A$, $P$, and $Q$. In each round of the proposed "unified active learning framework", it chooses $A$ that maximizes $I_f$. By choosing $P$ and $Q$ properly (for example, for the class imbalance task, setting $Q$ to be a small labeled sample set from rare classes), this paper shows empirically the proposed algorithm outperforms other active learning algorithms on various tasks, including standard AL, AL with class imbalance, AL with redundant data, and AL with out of distribution data. In this paper, the authors propose a new diversity based active learning algorithm by utilizing a series of information functions in submodular optimization (SO) problems. Specifically, they consider three submodular information measures (SIM) in SO: Submodular Mutual Information (SMI), Submodular Conditional Gain (SCG) and Submodular Conditional Mutual Information (SCMI) and found that SCMI ($I_f(\mathbf{A};\mathbf{Q}|\mathbf{P})$) is the most expressive SIM such that one could tailor $\mathbf{Q}$ and $\mathbf{P}$ to represent SCG and SMI, and thus propose to use it as a “unified” acquisition function for tackling three scenarios in realistic AL: rare class due to class imbalance, redundant data and out-of-distribution(OOD) data. The basic idea is to specify $\mathbf{Q}$ and $\mathbf{P}$ depending on the desired/un-desired classes, such that one could condition on data region that they want to exclude (OOD, redundant data), while up-sample regions that one want to include (rare class) by considering the mutual information w.r.t that region. To instantiate SIM acquisition function, the authors borrow the utility function from three well known graph-based SO problems for diversity coverage: Facility location (FL), Graph cut (GC) and Log Determinant (LOGDET), and use the similarity kernels computed with pairwise cosine similarity of the last layer gradients w.r.t the model-predicted label for every pair of unlabeled data points. They experiment with synthetic datasets rooted from MNIST/CIFAR-10/ImageNet to test for the three special scenarios, and show promising results against several strong baselines including BADGE.
abstractText: Active learning has proven to be useful for minimizing labeling costs by selecting the most informative samples. However, existing active learning methods do not work well in realistic scenarios such as imbalance or rare classes, out-of-distribution data in the unlabeled set, and redundancy. In this work, we propose SIMILAR (Submodular Information Measures based actIve LeARning), a unified active learning framework using recently proposed submodular information measures (SIM) as acquisition functions. We argue that SIMILAR not only works in standard active learning but also easily extends to the realistic settings considered above and acts as a one-stop solution for active learning that is scalable to large real-world datasets. Empirically, we show that SIMILAR significantly outperforms existing active learning algorithms by as much as ≈ 5%− 18% in the case of rare classes and ≈ 5%− 10% in the case of out-of-distribution data on several image classification tasks like CIFAR-10, MNIST, and ImageNet. SIMILAR is available as a part of the DISTIL toolkit: https://github.com/decile-team/distil.
authors.name: Suraj Kothawade
references.authors: Sami Abu-El-Haija Nisarg Kothari Joonseok Lee Paul Natsev George Toderici Balakrishnan Varadarajan Sudheendra Vijayanarasimhan
references.title: Youtube-8m: A large-scale video classification benchmark
references.venue: arXiv preprint arXiv:1609.08675,
references.authors: David Arthur Sergei Vassilvitskii
references.title: k-means++: the advantages of careful seeding
references.venue: In SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms,
references.authors: Jordan T Ash Chicheng Zhang Akshay Krishnamurthy John Langford Alekh Agarwal
references.title: Deep batch active learning by diverse, uncertain gradient lower bounds
references.authors: Francis Bach
references.title: Learning with submodular functions: A convex optimization perspective
references.venue: arXiv preprint arXiv:1111.6453,
references.authors: Francis Bach
references.title: Submodular functions: from discrete to continuous domains
references.venue: Mathematical Programming,
references.authors: Christopher Berlind Ruth Urner
references.title: Active nearest neighbors in changing environments
references.venue: In International Conference on Machine Learning,
references.authors: Joy Buolamwini Timnit Gebru
references.title: Gender shades: Intersectional accuracy disparities in commercial gender classification
references.venue: In Conference on fairness, accountability and transparency,
references.authors: Holger Caesar Varun Bankiti Alex H Lang Sourabh Vora Venice Erin Liong Qiang Xu Anush Krishnan Yu Pan Giancarlo Baldan Oscar Beijbom
references.title: nuscenes: A multimodal dataset for autonomous driving
references.venue: In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition,
references.authors: Colin Campbell Nello Cristianini Alex Smola
references.title: Query learning with large margin classifiers
references.venue: In ICML,
references.authors: Ciprian Chelba Tomas Mikolov Mike Schuster Qi Ge Thorsten Brants Phillipp Koehn Tony Robinson
references.title: One billion word benchmark for measuring progress in statistical language modeling
references.venue: arXiv preprint arXiv:1312.3005,
references.authors: Laming Chen Guoxin Zhang Hanning Zhou
references.title: Fast greedy map inference for determinantal point process to improve recommendation diversity
references.venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,
references.authors: Shai Fine Ran Gilad-Bachrach Eli Shamir
references.title: Query by committee, linear separation and random walks
references.venue: Theoretical Computer Science,
references.authors: Yoav Freund H Sebastian Seung Eli Shamir Naftali Tishby
references.title: Selective sampling using the query by committee algorithm
references.venue: Machine learning,
references.authors: Satoru Fujishige
references.title: Submodular functions and optimization
references.authors: Denis Gudovskiy Alec Hodgkinson Takuya Yamaguchi Sotaro Tsukizawa
references.title: Deep active learning for biased datasets via fisher kernel self-supervision
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Anupam Gupta Roie Levin
references.title: The online submodular cover problem
references.venue: In ACM-SIAM Symposium on Discrete Algorithms,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Rishabh Iyer Jeffrey Bilmes
references.title: A memoization framework for scaling submodular optimization to large scale problems
references.venue: In The 22nd International Conference on Artificial Intelligence and Statistics,
references.authors: Rishabh Iyer Ninad Khargoankar Jeff Bilmes Himanshu Asanani
references.title: Submodular combinatorial information measures with applications in machine learning
references.venue: In Algorithmic Learning Theory,
references.authors: Rishabh Krishnan Iyer
references.title: Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications
references.venue: PhD thesis,
references.authors: Kimmo Karkkainen Jungseock Joo
references.title: Fairface: Face attribute dataset for balanced race, gender, and age for bias measurement and mitigation
references.venue: In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision,
references.authors: Vishal Kaushal Rishabh Iyer Suraj Kothawade Rohan Mahadev Khoshrav Doctor Ganesh Ramakrishnan
references.title: Learning from less data: A unified data subset selection and active learning framework for computer vision
references.venue: IEEE Winter Conference on Applications of Computer Vision (WACV),
references.authors: Vishal Kaushal Suraj Kothawade Ganesh Ramakrishnan Jeff Bilmes Rishabh Iyer
references.title: Prism: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization
references.venue: arXiv preprint arXiv:2103.00128,
references.authors: Krishnateja Killamsetty Durga Sivasubramanian Ganesh Ramakrishnan Rishabh Iyer
references.title: Glister: Generalization based data subset selection for efficient and robust learning
references.venue: arXiv preprint arXiv:2012.10630,
references.authors: Diederik P Kingma Max Welling
references.title: Auto-encoding variational bayes
references.venue: arXiv preprint arXiv:1312.6114,
references.authors: Andreas Kirsch Joost Van Amersfoort Yarin Gal
references.title: Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.authors: Alex Kulesza Ben Taskar
references.title: Determinantal point processes for machine learning
references.venue: arXiv preprint arXiv:1207.6083,
references.authors: Yann LeCun Bernhard Boser John S Denker Donnie Henderson Richard E Howard Wayne Hubbard Lawrence D Jackel
references.title: Backpropagation applied to handwritten zip code recognition
references.venue: Neural computation,
references.authors: Yann LeCun Corinna Cortes CJ Burges
references.title: Mnist handwritten digit database
references.venue: at&t labs,
references.authors: Ilya Loshchilov Frank Hutter
references.title: Sgdr: Stochastic gradient descent with warm restarts
references.venue: arXiv preprint arXiv:1608.03983,
references.authors: Baharan Mirzasoleiman Ashwinkumar Badanidiyuru Amin Karbasi Jan Vondrák Andreas Krause
references.title: Lazier than lazy greedy
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: George L Nemhauser Laurence A Wolsey Marshall L Fisher
references.title: An analysis of approximations for maximizing submodular set functions—i
references.venue: Mathematical programming,
references.authors: Yuval Netzer Tao Wang Adam Coates Alessandro Bissacco Bo Wu Andrew Y Ng
references.title: Reading digits in natural images with unsupervised feature learning
references.authors: Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga Alban Desmaison Andreas Kopf Edward Yang Zachary DeVito Martin Raison Alykhan Tejani Sasank Chilamkurthy Benoit Steiner Lu Fang Junjie Bai Soumith Chintala
references.title: Pytorch: An imperative style, highperformance deep learning library
references.venue: Advances in Neural Information Processing Systems
references.authors: Dan Roth Kevin Small
references.title: Margin-based active learning for structured output spaces
references.venue: In European Conference on Machine Learning,
references.authors: Olga Russakovsky Jia Deng Hao Su Jonathan Krause Sanjeev Satheesh Sean Ma Zhiheng Huang Andrej Karpathy Aditya Khosla Michael Bernstein
references.title: Imagenet large scale visual recognition challenge
references.venue: International journal of computer vision,
references.authors: Greg Schohn David Cohn
references.title: Less is more: Active learning with support vector machines
references.venue: In ICML,
references.authors: Ozan Sener Silvio Savarese
references.title: Active learning for convolutional neural networks: A core-set approach
references.venue: arXiv preprint arXiv:1708.00489,
references.authors: Burr Settles
references.title: Active learning literature survey
references.authors: Samarth Sinha Sayna Ebrahimi Trevor Darrell
references.title: Variational adversarial active learning
references.venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,
references.authors: Ehsan Tohidi Rouhollah Amiri Mario Coutino David Gesbert Geert Leus Amin Karbasi
references.title: Submodularity in action: From machine learning to signal processing applications
references.venue: IEEE Signal Processing Magazine,
references.authors: Dan Wang Yi Shang
references.title: A new active labeling method for deep learning
references.venue: In 2014 International joint conference on neural networks (IJCNN),
references.authors: Kai Wei Rishabh Iyer Jeff Bilmes
references.title: Submodularity in data subset selection and active learning
references.venue: In International Conference on Machine Learning,
references.authors: Xiang Zhang Junbo Zhao Yann LeCun
references.title: Character-level convolutional networks for text classification
references.venue: arXiv preprint arXiv:1509.01626,
references.authors: Yukun Zhu Ryan Kiros Rich Zemel Ruslan Salakhutdinov Raquel Urtasun Antonio Torralba Sanja Fidler
references.title: Aligning books and movies: Towards story-like visual explanations by watching movies and reading books
references.venue: In Proceedings of the IEEE international conference on computer vision,
sections.text: 1 Introduction
  Deep neural networks (DNNs) have had a lot of success in a wide variety of domains. However, they require large labeled datasets which are often taxing, time-consuming, and expensive to obtain. Active learning (AL) [12, 13, 39, 3, 9] is a promising approach to solve this problem. It aims to select the most informative data points from an unlabeled dataset to be labeled in an adaptive manner with a human in the loop. The goal of AL is to achieve maximum accuracy of the model while minimizing the number of data points required to be labeled.
  Current AL methods have been tested in relatively simple, clean, and balanced datasets. However, real-world datasets are not clean and have a number of characteristics that makes learning from them challenging [10, 46, 47, 38, 1, 8]. Firstly, these real-world datasets are im-
  balanced, and some classes are very rare (e.g., Fig 1(a)). Examples of this imbalance are medical
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  imaging domains where the cancerous images are rare. Secondly, real-world data has a lot of redundancy (e.g., Fig 1(b)). This redundancy is more prominent in datasets that are created by sampling frames from videos (e.g., footage from a car driving on a freeway or surveillance camera footage). Thirdly, it is common to have out-of-distribution (OOD) (e.g., Fig 1(c)) data, where some part of the unlabeled data is not of concern to the task at hand. Given the amount of unlabeled data, it is not realistic to assume that these datasets can be cleaned manually; hence, it is the need of the hour to have active learning methods that are robust to such scenarios. We show that current AL approaches (including the state-of-the-art approach BADGE [3]) do not work well in the presence of the dataset biases described above. In this work, we address the following question: Can a machine learning model be trained using a single unified active learning framework that works for a broad spectrum of realistic scenarios? As a solution, we propose SIMILAR1, a unified active learning framework which enables active learning for many realistic scenarios like rare classes, out-of-distribution (OOD) data, and redundancy.
sections.heading: 1.1 Related Work
sections.text: Active learning has enabled efficient training of complex deep neural networks by decreasing labeling costs. The most commonly used approach is to select the most uncertain items. Examples of uncertainty strategies include ENTROPY [41], LEAST CONFIDENCE [44], and MARGIN [37]. One challenge of this approach is that all the samples within a batch can be potentially similar even though they are uncertain. To overcome this problem in batch active learning, many recent works have attempted to select diverse yet informative data points. [45, 22] propose a simple approach: Filter a set of points using uncertainty sampling and then select a diverse subset from the filtered set. [40] propose CORESET, which forms core-sets using greedy k-center clustering while maintaining the geometric arrangement. BADGE [3], another recent approach, proposes to select data points corresponding to high-magnitude, diverse hypothesized gradients by using K-MEANS++ [2] initialization to distance from previously selected data points in the batch. Most existing AL approaches fail to ensure diversity across AL selection rounds and do not perform as well when there is a lot of redundancy. Sinha et al. [42] used a variational autoencoder (VAE) [25] to learn a feature space and an adversarial network [32] to distinguish between labeled and unlabeled data points. However, their approach is computationally expensive and requires extensive hyperparameter tuning. Similarly, BATCHBALD [26] does not scale to larger batch sizes since their method would need a large number of Monte Carlo dropout samples to obtain a significant mutual information. Such limitations reduce the scope of applying these methods to realistic settings.
  Closely related to our work are two recently proposed works. The first is GLISTER-ACTIVE [24], which formulates the AL acquisition function by maximizing the log-likelihood on a held-out validation set. This validation set could consist of examples from the rare classes or in-distribution examples. The second approach is the work of Gudovskiy et al. [15], who study AL for biased datasets using a self-supervised FISHER kernel and pseudo-label estimators. They address this problem by explicitly minimizing the KL divergence between training and validation sets via maximizing the FISHER kernel. Although their method shows promising results, they make multiple unrealistic assumptions: a) They use a large labeled validation set, and b) they use feature representations from a model pretrained using unsupervised learning on a balanced unlabeled dataset. In this work, we compare against both GLISTER-ACTIVE [24] and FISHER [15] approaches in the more realistic setting of a small held-out validation set (smaller than the seed labeled set) and an imbalanced unlabeled set. Another work proposed a discrete optimization method for k-NN-type algorithms in the domain shift setting [6]. However, their approach is limited to k-NNs.
  This work utilizes submodular information measures (SIM) by [19] and their extensions by [23]. SIMs encompass submodular conditional mutual information (SCMI), which can then be used to derive submodular mutual information (SMI); submodular conditional gain (SCG); and submodular functions (SF). We discuss these functions in detail in Sec. 2. [23] also studies these functions on the closely related problem of targeted data selection.
sections.heading: 1.2 Our Contributions
sections.text: The following are our main contributions: 1) Given the limitations of existing approaches in handling active learning in the real world, we propose SIMILAR (Sec. 3), a unified active learning framework that can serve as a comprehensive solution to multiple realistic scenarios. 2) We treat SIM as a
  1Submodular Information Measures based actIve LeARning
  common umbrella for realistic active learning and study the effect of different function instantiations offered under SIM for various realistic scenarios. 3) SIMILAR not only handles standard active learning but also extends to a wide range of settings which appear in the real world such as rare classes, out-of-distribution (OOD) data, and datasets with a lot of redundancy. Finally, 4) we empirically demonstrate the effectiveness of SMI-based measures for image classification (Sec. 4) in a number of realistic data settings including imbalanced, out-of-distribution, and redundant data. Specifically, in the case of imbalanced and OOD data, we show that SIMILAR achieves improvements of more than 5 to 10% on several image classification datasets.
sections.heading: 2 Background
sections.text: In this section, we enumerate the different submodular functions that are covered under SIM and the relationships between them.
  Submodular Functions. We let U denote the unlabeled set of n data points U = {1, 2, 3, ..., n} and a set function f : 2U −→ R. Formally, a function f is submodular [14] if for x ∈ U , f(A∪x)−f(A) ≥ f(B ∪ x)− f(B), ∀A ⊆ B ⊆ U and x /∈ B. For a set A ⊆ U , f(A) provides a real-valued score for A. In the context of batch active learning, this is the score of an acquisition function f on batch A. Submodularity is particularly appealing because it naturally occurs in real world applications [43, 4, 5, 20] and also admits a constant factor 1− 1e [34] for cardinality constraint maximization. Additionally, variants of the greedy algorithm maximize a submodular function in near-linear time [33].
  Submodular Mutual Information (SMI). Given sets A,Q ⊆ U , the SMI [16, 19] is defined as If (A;Q) = f(A) + f(Q) − f(A ∪ Q). Intuitively, SMI models the similarity between Q and A, and maximizing SMI will select points similar to Q while being diverse. Q here is the query set. Submodular Conditional Gain (SCG). Given sets A,P ⊆ U , the SCG f(A|P) is the gain in function value by adding A to P . Thus, f(A|P) = f(A∪ P)− f(P) [19]. Intuitively, SCG models how different A is from P , and maximizing SCG functions will select data points not similar to the points in P while being diverse. We refer to P as the conditioning set. Submodular Conditional Mutual Information (SCMI). Given sets A,Q,P ⊆ U , the SCMI is defined as If (A;Q|P) = f(A∪P)+ f(Q∪P)− f(A∪Q∪P)− f(P). Intuitively, SCMI jointly models the similarity between A and Q and their dissimilarity with P .
  Relationship between SIM The relationship between the above measures is the key component that unifies our AL framework [19, 23]. The unification comes from the rich modeling capacity of SCMI: If (A;Q|P) where Q,P ⊆ U . This facilitates a single acquisition function that can be applied to multiple scenarios. Concretely, the submodular function f can be obtained
  by setting Q ← U and P ← ∅. Next, the SMI can be obtained by setting Q ← Q and P ← ∅, while we obtain SCG by setting Q ← ∅, P ← P . We summarize the relationships between SIM in Tab. 1. Instantiations of SIM. The formulations for Facility Location (FL), Graph Cut (GC) and Log Determinant (LOGDET) are as in [19, 23] and we adapt them as acquisition functions for batch active learning. We use two variants for FL: FLQMI, which models pairwise similarities of only the query set Q to the unlabeled dataset, and FLVMI, which additionally considers the pairwise similarities within the unlabeled dataset U . The SCG and SCMI expressions corresponding to FL are referred as FLCG and FLCMI, respectively (see row 1 in Tab. 2a and 2b). For LOGDET, we refer to the SMI, SCG and SCMI expressions as LOGDETMI, LOGDETCG and LOGDETCMI, respectively (see row 5 in Tab. 2a and row 2 in Tab. 2b). Similarly, the SMI and SCG expressions are respectively referred to as GCMI and GCCG for GC (see row 3 in Tab. 2a and 2b). For notation in Tab. 2, the pairwise similarity matrix S between items in sets A and B is denoted as SA,B. Also, we denote Sij as the (i, j) entry of S.
sections.heading: 3 SIMILAR: Our Unified Active Learning Framework
sections.text: In this section, we propose a unified active learning framework SIMILAR, which uses SIMs to address the limitations of the current work (see Sec. 1.1). We show that SIMILAR can be effectively applied to a broad range of realistic scenarios and thus acts as one-stop solution for AL.
  The basic idea behind our framework is to exploit the relationship between the SIMs (Tab. 1) such that it can be applied to any real-world dataset. Particularly, we use the formulation of SCMI and appropriately choose a query set Q and/or a conditioning set P depending on the scenario at hand. Towards this end, we use the inspiration from [3] where they select data points based on diverse gradients. The SIM functions (see Tab. 2) are instantiated using similarity kernels computed using pairwise similarities Sij between the gradients of the current model. Specifically, we define Sij = 〈∇θHi(θ),∇θHj(θ)〉, where Hi(θ) = H(xi, yi, θ) is the loss on the ith data point. Similar to [45, 3], we use hypothesized labels for computing the gradients, and the corresponding similarity kernels. The hypothesized label for each data point is assigned as the class with the maximum probability. We then optimize a SCMI function:
  max A⊆U,|A|≤B
  If (A;Q|P) (1)
  with appropriate choices of query setQ and conditioning set P . In the context of batch active learning, A is the batch and B is the budget (batch size in AL). We present our unified AL framework in Algorithm 1 and illustrate the choices of query and conditioning set for realistic scenarios in Fig. 2.
  Algorithm 1 SIMILAR: Unified AL Framework Require: Initial Labeled set of data points: L, large unlabeled dataset: U , Loss function H for
  learning modelM, batch size: B, number of selection rounds: N 1: for selection round i = 1 : N do 2: Train modelM with lossH on the current labeled set L and obtain parameters θ 3: Using model parameters θi, compute gradients using hypothesized labels {∇θH(xj , ŷj , θ),∀j ∈ U} and obtain a similarity matrix X . 4: Instantiate a submodular function f based on X . 5: Ai ← argmaxA⊆U,|A|≤BIf (A;Q|P) (Optimize SCMI with an appropriate choice of Q and P , see Tab. 1) 6: Get labels L(Ai) for batch Ai and L ← L ∪ L(Ai), U ← U −Ai 7: end for 8: Return trained modelM and parameters θ.
  In the scenarios below, we will discuss how this paradigm can provide a unified view of active learning, handle aspects like standard active learning (Sec. 3.1), rare classes and imbalance (Sec. 3.2), redundancy (Sec. 3.3) and, OOD/outliers in the unlabeled data (Sec. 3.4).
sections.heading: 3.1 Standard Active Learning
sections.text: We refer to standard active learning for ideal scenarios when there is no imbalance, redundancy or OOD data in the unlabeled dataset. In such cases, there is no requirement for having a query set and conditioning set. Hence, given a SCMI function If (A;Q|P), we get If (A;Q|P) = f(A) by setting Q ← U (the unlabeled dataset) and P ← ∅. In a nutshell, the standard diversified active learning setting can be seen as a special case of our proposed unified AL framework (Equ. (1)) by choosingQ,P as above. Note that this approach is very similar and closely related to BADGE [3], where the authors
  also choose points based on diverse gradients. Furthermore, the authors discuss the use of Determinantal Point Processes (DPP) [28] for sampling, and this is very similar to maximizing log-determinants. In the supplementary paper, we compare the choice of different submodular functions for AL.
sections.heading: 3.2 Rare Classes
sections.text: A very common and naturally occurring scenario is that of imbalanced data. This imbalance is because some classes or attributes are naturally more frequently occurring than others in the realworld. For example, in a self-driving car application, there may be very few images of pedestrians at night on highways, or cyclists at night. Another example is medical imaging, where there are many rare yet important diseases (e.g., various forms of cancers), and it is often the case that non-cancerous images are much more than compared to the cancerous ones. While such classes are rare, it is also critical to be able to perform well in these classes. The problem with running standard active learning algorithms in such a case is that they may not sample too many data points from these rare classes, and as a result, the model continues to perform poorly on these classes. In such cases, we can create a (small) held-out setR which contains data points from these rare classes, and try to encourage the AL by sampling more of these rare classes by maximizing the SMI function If (A;R):
  max A⊆U,|A|≤B
  If (A;R) (2)
  This setting is shown in Fig. 2(a). R contains a small number of held-out examples of classes 5, 8 which are rare, and the AL acquisition function is Equ. (2). Note that this is exactly equivalent to maximizing the SCMI function withQ ← R and P ← ∅ (i.e. Equ. (1) in Line 5 of Algorithm 1). Furthermore, since the SMI functions naturally model query relevance and diversity, they will also try to pick a diverse set of data points which are relevant toR. Finally, we also point out that this setting was considered in [15] where they use a FISHER kernel based approach to sample data points. Note that for this setting to be realistic, it is critical that the size of this validation set is very small – [15] uses a much larger validation set which is not very realistic (e.g., 200× our set, see Appendix B for more details).
  3.3 Redundancy in Unlabeled Data
  Another commonplace scenario is where we are dealing with a lot of redundancy – e.g., frames sampled from a video, where subsequent frames are visually similar. In such cases, existing AL algorithms tend to pick data points that are semantically similar to the ones selected in some earlier batch. This is true even for the state-ofthe-art AL algorithm BADGE [3] that attempts to enforce diversity, but only in the current batch of data points and not the already selected labeled set. To illustrate this, consider the scenario in Fig. 2(b). The digits 0, 1 are redundant in the unlabeled set, and they are already present in the labeled set L. Algorithms which just focus on diversity in the current batch could fail at ensuring diversity across batches. To mitigate inter-batch redundancy, we use SCG acquisition function and condition upon the already labeled set L:
  max A⊆U,|A|≤B
  f(A|L) (3)
  Notice that this is a special case of our proposed unified AL framework (Equ. (1)) since the SCG function f(A|L) is basically a SCMI function with Q ← ∅ and P ← L.
sections.heading: 3.4 Out of Distribution Data
sections.text: In real world scenarios, we often have out-ofdistribution (OOD) data or irrelevant classes in the unlabeled set. Such OOD data is not useful for
  the given classification task at hand. Using an acquisition function that selects a lot of OOD data points will lead to a waste of labeling effort and time. This is because annotators have to spend time in filtering out OOD data points and discard them from the training dataset. To account for OOD data, we add an additional class called "OOD" in our model. Since the goal is to improve on in-distribution classes , we ignore the prediction for the OOD class at test time. For our AL acquisition function, we use the currently labeled OOD points O as the conditioning set P , and the currently labeled in-distribution (ID) points I as the query setQ. In other words, our acquisition function is to optimize:
  max A⊆U,|A|≤B
  If (A; I|O) (4)
  This is illustrated in Fig. 2(c), where the labeled set consists of six examples, four of them being ID data points (set I) and two being OOD data points (set O). In Fig. 2(c), the ID data are digits (digit classification) and the OOD examples are alphabets. This SCMI based approach will naturally pick points "close" to the ID data while avoiding the OOD points.
  Another approach for designing the acquisition function is to not explicitly condition on the OOD data points. In other words, we can just optimize the SMI function:
  max A⊆U,|A|≤B
  If (A; I) (5)
  We contrast the choices of SCMI (Equ. (4)) and SMI (Equ. (5)) functions in our experiments.
sections.heading: 3.5 Multiple Co-occurring Realistic Scenarios
sections.text: We can also apply SIMILAR to datasets where more than one realistic scenarios are co-occurring. As illustrated in Tab. 3, we can use the formulation of SCMI and make appropriate choices of Q and P to tackle multiple realistic scenarios.
  Rare classes and OOD: We set Q ← R and P ← O and maximize If (A;R|O). Intuitively, this function would pick points close toR while avoiding the OOD points. In this scenario, we can also optimize an SMI function If (A;R) if the data points belonging to the rare classes are not similar to the OOD data points, meaning that only searching for rare classes may suffice. Regardless, the SCMI approach above will further reinforce the avoidance of the OOD points.
  Rare classes and Redundancy: We set Q ← R and P ← L − R̃. Here, R̃ is the subset of data points from the labeled set L that belong to the rare classes. Intuitively, this function would pick points close to R while avoiding points already in L − R̃, thereby avoiding redundant data. Just focusing on R by optimizing If (A;R) is also a feasible option because rare classes are generally not redundant. As before, the SCMI approach will only reinforce the avoidance of redundant samples in any non-rare class instances selected.
  Redundancy and OOD: This is a more challenging scenario than the ones above. We start with using the SCMI formulation for the OOD scenario, i.e., If (A; I|O), where I is the set of ID samples and O is the set of OOD samples. Optimizing this function will pick diverse in-distribution samples within a batch. For selecting diverse samples across different batches, we can tackle this by using an appropriate kernel for the conditioning set. For instance, consider the FLCMI function in Tab. 2(b). On setting P ← O ∪ I, we can rewrite the FLCMI function by splitting the penalty term as follows:∑ i∈U max(min(max j∈A Sij ,max j∈I Sij)−max(max j∈O Sij ,max j∈I S′ij), 0). While S is computed using cosine similarity, we can compute S′ using an exponential kernel to magnify the value of S′ij using the exponent when i and j are very similar. This exponent is a hyperparameter which can be tuned to penalize selecting redundant samples from I (denoted as I ′ ) in Tab. 3.
sections.heading: 3.6 Realizing Realistic Scenarios in Applications
sections.text: In this section, we discuss a few insights on how these realistic scenarios can be realized. To begin with, the initial labeled set used in AL usually follows the distribution of the unlabeled set. The
  statistics of this set can be used to identify rare classes. If the initial seed set is small, the rare classes/OOD data points can be realized after a few rounds of standard AL. Until such scenarios are discovered, standard AL can be done using a diversity-based acquisition function like the log determinant (LOGDET). For production-level models, they go through a test deployment phase. During this phase, systematically recurring errors are often found. An example is of undetected bicycles at night in an object detector (false negatives). Such recurring failure cases can be due to rare classes in the labeled set. Moreover, we as users often know whether there are rare classes or if there is redundancy from domain knowledge. For instance, in the biomedical domain, images of cancer cells are typically rarer than ones of non-cancer cells because cancer inherently is a rare disease.
sections.heading: 3.7 Scalability and Computational Aspects of SIMILAR
sections.text: Computational Complexity: The computational complexity of the different SMI functions are determined by (1) the kernel computation time, and (2) the time complexity of the greedy algorithm. All functions considered here are graph based functions and require computing a kernel matrix. The LOGDET functions (LOGDET, LOGDETMI, LOGDETCG, LOGDETCMI), some FL functions (FL, FLVMI, FLCMI), and GC, GCMI all require the n×n similarity matrix (n = |U| is the number of unlabeled points) which entails a complexity ofO(n2) to construct the similarity kernel. Once constructed, the complexity of the greedy algorithm for LOGDET class of functions is roughly O(B3n) [11], while the complexity of the greedy algorithm with FL, FLVMI, and FLCMI is O(Bn2) [18, 20](B is the batch size). Different from others, FLQMI does not require computing a n× n kernel, but only a n× q kernel (where q = |Q| is the number of query points). Correspondingly, the complexity of the greedy algorithm with FLQMI is O(nqB), and is linear in n. In Appendix. A, we provide a detailed summary of the complexity of different SF, SMI, SCG, and SCMI functions.
  Partition Trick: The deal with the high O(n2) of the LOGDET, GC, and some of the FL variants (except FLQMI), we also propose the following partitioning algorithm: We randomly split the unlabeled set U into p partitions U1, · · · ,Up, and we then define the corresponding function (SF, SMI, SCMI, SCG) on each of the partitions and independently optimize them. In each partition, we select B/p points. The complexity of this reduces from O(n2) to O(n2/p) and with an appropriate choice of p, we can significantly reduce the computational complexity. We use this in our ImageNet experiments (see Sec. 4.1), and observe that our approaches continue performing well while being more scalable. We provide more details on partitioning in Appendix. A.
  Last Layer Gradients: Deep models have numerous parameters leading to very high dimensional gradients. Since our kernel matrix is computed using the cosine similarity of gradients, this becomes intractable for most models. To solve this problem, we use last-layer gradient approximation by representing data points using last layer gradients. BADGE [3], CORESET [40] and GLISTER [24] are other baselines that also use this approximation. Using this representation, we compute a pairwise cosine similarity matrix to instantiate acquisition functions in SIMILAR (see lines 3,4 in Algorithm 1).
sections.heading: 4 Experimental Results
sections.text: In this section, we empirically evaluate the effectiveness of SIMILAR on a wide range of scenarios like rare classes (Sec. 4.1), redundancy (Sec. 4.2) and out-of-distribution (Sec. 4.3). We do so by comparing the accuracy and selections of various SCMI based acquisition functions with existing AL approaches. Using these experiments, we cover the issues with the current AL methods and show that these issues can be mitigated by using a unified implementation using SCMI with appropriate choices of query and/or conditioning sets. Although this section focuses on realistic scenarios, we also study SIMILAR in a standard active learning setting and show that it performs at par with current AL methods (see Appendix. C). Furthermore, we present some experiments on a real-world medical dataset in Appendix. H and some experiments on multiple co-occurring realistic scenarios (Sec. 3.5) in Appendix. I.
  Baselines in all scenarios: We compare SCMI based functions against several methods. Particularly, we compare against: (1) three uncertainty based AL algorithms: i)ENTROPY: Selects the top B data points with the highest entropy [41], ii) MARGIN: Select the bottom B data points that have the least difference in the confidence of first and the second most probable labels [37], iii)LEAST-CONF: SelectB samples with the smallest predicted class probability [44], (2) state-of-the-art diversity based algorithms: iv) BADGE [3] v) GLISTER [24] vi) CORESET [40] which are all discussed in section Sec. 1.1, and, 3) RANDOM: Select B samples randomly. Additionally, in the rare classes scenario, we compare against FISHER [15] which is also discussed in Sec. 1.1.
  LOGDETMI
  FLVMI
  DIV-GCMI
  FISHER-LV
  BADGE
  ENTROPY
  MARGIN
sections.heading: 125 250 375 500 625 750 875 1000 1125 1250
sections.text: Datasets, model architecture and experimental setup: We apply our framework to CIFAR-10 [27] and MNIST [30] classification tasks. Additionally, we also evaluate our method on down sampled 32× 32 ImageNet-2012 [38] for the rare classes setting (Sec. 4.1). Due to the lack of test split on ImageNet, we used the validation split for evaluation. In the sections below, we discuss the individual splits for L, U ,R, I, and O in each realistic scenario. To ensure that all the selection algorithms that we are studying are given fair and equal treatment across all realistic scenarios, we use a common training procedure and hyperparameters. We use standard augmentation techniques like random crop, horizontal flip followed by data normalization except for MNIST which does not use horizontal flip to preserve labels. For training, we use an SGD optimizer with an initial learning rate of 0.01, the momentum of 0.9, and a weight decay of 5e-4. We decay the learning rate using cosine annealing [31] for each epoch. On all datasets except MNIST, we train a ResNet18 [17] model, while on MNIST we train a LeNet [29] model. For all the experiments in a particular scenario (rare classes, redundancy and OOD), we start with an identical initial modelM and initial labeled set D. We reinitialize the model parameters at the beginning of every selection round using Xavier initialization and train the model until either the training accuracy reaches 99% or the epoch count reaches 150. We run each experiment 3× on CIFAR10 and MNIST and 1× on ImageNet and provide error bars (std deviation). All experiments were run on a V100 GPU. For more details on the experimental setup, baselines, and datasets see Appendix. B.
sections.heading: 4.1 Rare Classes
sections.text: Custom dataset: Following [15, 24], we simulate these rare classes by creating a class imbalance. We initialize the batch active learning experiments by creating a custom dataset which is a subset of the full dataset with the same marginal distribution. Given that C consists of data points from the imbalanced classes and D consists of data points from the balanced classes, we create an initial labeled set L such that |DL| = ρ|CL| and an unlabeled set |DU | = ρ|CU |, where ρ is the imbalance factor. We use a small and clean validation/query setR containing data points from the imbalanced classes (≈ 3 data points per imbalanced class). We create an imbalance in CIFAR-10 using 5 random classes, ρ = 10 and for MNIST we create an imbalance using the same classes as in [15] (5 · · · 9) and use ρ = 20. For both datasets: |CL|+ |DL| = 125, |CU |+ |DU | = 16.5K, B = 125 (AL batch size) and, |R| = 25 (size of the held out rare instances). For MNIST, we also present the results for B = 25 and ρ = 100 in the supplementary. On ImageNet, we randomly select 500 classes out
  LOGDETCG FLCG GLISTER BADGE CORESET ENTROPY MARGIN RANDOM
  of 1000 classes for imbalance and ρ = 5 such that |CL| + |DL| = 102K, |CU | + |DU | = 664K, B = 25K and, |R| = 2.5K. These data splits are chosen to simulate a low initial accuracy on the rare classes and at the same time maintain the imbalance factor in the labeled and unlabeled datasets.
  Results: The results are shown in Fig. 3. We observe that SMI based functions not only consistently outperform uncertainty based methods (ENTROPY, LEAST-CONF and MARGIN) but also all the state-of-the-art diversity based methods (BADGE, GLISTER, CORESET) by ≈ 5 − 10% in terms of overall accuracy and ≈ 10− 18% in terms of average accuracy on rare classes (see Fig. 3a, 3d, 3g). The reason for the same can be seen in Fig. 3c, 3f, 3i which illustrates that they fail to pick an adequate number of examples from the rare classes. Evidently, FLQMI and LOGDETMI which balance between diversity and relevance perform better than GCMI which only models relevance. Furthermore, DIV-GCMI which is a linear combination of GCMI and a diversity term performs consistently worse, which suggest that a naive combination of the two may not be as effective. This suggests the need of SMI based acquisitions functions (Equ. (2)) with richer modeling capabilities like FLQMI and LOGDETMI within SIMILAR. Furthermore, all SMI based functions also outperform the FISHER kernel based method when the validation set is small and realistic, i.e., |R| = 25. Since, [15] use a very large validation set in their experiments, we try their method FISHER-LV with a 40× larger validation set of size 1000 (which is not practical) and observe a comparable performance with the SMI functions which use a small validation set. Furthermore, we see that FISHER-LV actually picks significantly larger number of rare class instances in MNIST, but yet is comparable in performance of FLQMI and LOGDETMI. This suggests that both these methods select higher quality and diverse rare class instances. We observe that the GC SMI variants( GCMI and DIV-GCMI) do not perform well on MNIST classification. Finally, we point out in the case of ImageNet, FLQMI performs the best and outperforms FLVMI and LOGDETMI – this is because we do not need to do the partition trick for FLQMI since it is already linear in time complexity. For FLVMI and LOGDETMI, we set the number of partitions p = 50 for ImageNet. Finally, we do a pairwise t-test to compare the performance of the algorithms (Appendix. D) and observe that the SMI functions (and particularly FLVMI and LOGDETMI) statistically significantly outperform all AL baselines.
sections.heading: 4.2 Redundancy
sections.text: Custom dataset: To simulate a realistic redundancy scenario we create a custom dataset by duplicating 20% of the unlabeled dataset 10×. For CIFAR-10, the number of unique points in the unlabeled set |U| = 5K, the initial labeled set |L| = 500, B = 500, whereas for MNIST |U| = 500, |L| = 50 and B = 50. For MNIST, we also present the results for 5× and 20× in the Appendix. E. SCG vs Baselines: As expected, the diversity and uncertainty based methods outperform random. Importantly, we observe that the SCG functions (FLCG and LOGDETCG) significantly outperform all baselines by ≈ 3− 5% towards the end as the conditioning gets stronger with increase in L (see Fig. 4a, 4b). This implies that simply relying on model parameters for diversity and/or uncertainty is not sufficient and that conditioning on the updated labeled set L (Equ. (3)) is required in batch active learning. In Fig. 4c we show that SCG based acquisition functions select significantly more unique data points than other baselines. We also perform a pairwise t-test (Appendix. E), to prove that the SCG functions consistently and statistically significantly outperform BADGE and other baselines.
sections.heading: 4.3 Out-Of-Distribution
sections.text: Custom dataset: We simulated a scenario where we convert the classification problem in CIFAR-10 and MNIST to a 8-class classification, where the first 8 classes represent the set IF of in-distribution
  LOGDETCMI
  FLCMI
  LOGDETMI
  FLQMI
  FLVMI
  GCMI
  DIV-GCMI
  GLISTER
  BADGE
  CORESET
  ENTROPY
  MARGIN
  RANDOM
  1600 1850 2100 2350 2600 2850 3100 3350 3600 3850 Labeled Set Size
  60
  65
  70
  75
  A cc
  u ra
  cy (a)CIFAR-10: SCMI vs Baselines
sections.heading: 1600 1850 2100 2350 2600 2850 3100 3350 3600 3850
sections.text: Labeled Set Size
  60
  65
  70
  75
  A cc
  u ra
  cy
  (b)CIFAR-10: SCMI vs SMI
  3600 3850
  72.17
  74.83
  0.0
  0.5
  1.0
  1.5
  2.0
  2.5
  A v e ra
  g e
  V a ri
  a n
  ce
  0.73
  1.09
  1.42 1.7 1.41
  1.05 0.9
  1.74
  2.69
  1.41
  1.9
  2.28 2.05
  (c)OOD: Variance Comparison
  (ID) data points and the last 2 represent the set OF of out-of-distribution(OOD) data points. The initial labeled set L consists only of ID points, i.e. OF ∩ L = ∅. The unlabeled set is simulated to reflect a realistic and somewhat extreme setting where the unlabeled ID data points |IF | is much smaller than the unlabeled OOD data points |OF |. Additionally, we also assume we have a very small validation set of ID points IV . For CIFAR-10: |L| = 1.6K, |IF | = 4K, |OF | = 10K, |IV | = 40, B = 250 whereas for MNIST which is a relatively simpler task, we use a smaller initial labeled sets and keep the unlabeled sets of the same size: |L| = 40, |IF | = 400, |OF | = 10K, |IV | = 16, B = 20. Recall that our algorithm uses ID set I (initialized to IV ) and OOD set O which we build as follows. Every time our selection approach selects a set A, we update I = I ∪ (A ∩ IF ) and O = O ∪ (A ∩OF ), i.e. we augment the ID and OOD points in A to the sets I and O respectively. SCMI vs Baselines: Since we care about the predictive performance of the ID classes, we report the ID classes accuracy. We see that SCMI based acquisition functions significantly outperform existing AL approaches by ≈ 5− 10% (see Fig. 5a, 5d). We also observe that existing acquisition functions have a high variance, which is undesirable in real-world deployment scenarios where deep models are being continuously developed. Our SCMI based acquisition functions (LOGDETCMI and FLCMI) show the lowest variance in training (see Fig. 5c). This reinforces the need of having a framework like SIMILAR that facilitates query and conditioning sets.
  SCMI vs SMI: We compare SCMI functions against SMI functions to study the effect of conditioning and observe that the SCMI functions are comparable to the SMI functions initially but in the later selection rounds of active learning, the SCMI functions consistently outperform SMI functions. In particular, we see an improvement of 2− 3% as the conditioning becomes stronger (see Fig. 5b, 5e). We also observe the SCMI tends to select more ID points than SMI and other baselines (see Fig. 5f), and SCMI functions have a lower variance overall compared to even the SMI functions (Fig. 5c).
sections.heading: 5 Conclusion
sections.text: In this paper, we proposed a unified active learning framework SIMILAR using the submodular information functions. We showed the applicability of the framework in three realistic scenarios for active learning, namely rare classes, redundancy, and out of distribution data. In each case, we observed that the functions in SIMILAR significantly outperform existing baselines in each of these tasks. Our real-world experiments on MNIST, CIFAR-10, and ImageNet show that many of the SIM functions (specifically the LOGDET and FL variants) yield ≈ 5% − 18% gain compared to existing baselines, particularly in the rare class scenario and ≈ 5%− 10% OOD scenarios. The main limitations of our work is the dependence on good representations to compute similarity. A potential negative societal impact of this work is the use of SIMILAR to perpetuate certain biases through a malicious use of the query and conditioning set. We discuss this in more detail in Appendix. G.
  Acknowledgments and Disclosure of Funding
  This work is supported by the National Science Foundation under Grant No. IIS-2106937, a startup grant from UT Dallas, and by a Google and Adobe research award. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation, Google or Adobe.
title: SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios