summaries: Most batch-mode active learning strategies involve maximizing a sub-modular score function of the value of each image to be labeled. This paper demonstrates that current methods fail to sample diverse classes or images near decision boundaries, arguably one of the most important regions to obtain label information. The paper proposes a technique for incorporating class-balance and boundary-balance constraints to the sub-modular optimization problem and performs experiments over several image data sets to show the value of class and boundary balancing.  The paper describes a new active learning algorithm for classification problems. The authors propose a selection criteria that trades off between uncertainty and diversity. The novelty lies in formulating a three-pronged approach to diversity that still manages to maintain submodularity of the selection criteria: 1) a traditional diversity metric based on cosine similarity of embeddings 2) a new triplet/clique "loss" that penalizes the selection of nearby points 3) class-balancing and boundary-balancing constraints  By showing this three-pronged approach maintains submodularity, they are able to devise a greedy algorithm that still has a constant approximation guarantee to the optimal selection subset (as measured by the selection criteria). Experiments on CIFAR-10, CIFAR-100, ImageNet, and CIFAR-100LT (long-tailed) suggest that the new approach performs as well as or better than state-of-the-art methods. This paper presents a new method for batch active learning in deep neural networks, which aims to progressively construct compact subsets from a training dataset that maximize accuracy of learned models. The authors propose to address this problem by optimizing a submodular set function, expressed as a weighted combination of uncertainty, diversity, and triplet objectives, under a set of balancing constraints on classes and decision boundaries. The resulting optimization problem is solved using a greedy algorithm. Experiments are conducted on CIFAR10, CIFAR100, ImageNet and CIFAR100-LT datasets, where the proposed approach outperforms all baselines, with larger improvements under a class-imbalanced setting (CIFAR100-LT). This paper proposed a new subset selection method with novel diversity objective and balancing constraints. The authors prove that the proposed sample selection criterion is a submodular function. Hence its greedy algorithm comes with approximation guarantees (Nemhauser et al., 1978). The experiments on popular image classification datasets show that the proposed method is slightly better than k-center (Sener & Savarese, 2018). 
abstractText: Deep learning has yielded extraordinary results in vision and natural language processing, but this achievement comes at a cost. Most models require enormous resources during training, both in terms of computation and in human labeling effort. We show that we can identify informative and diverse subsets of data that lead to deep learning models with similar performance as the ones trained with the original dataset. Prior methods have exploited diversity and uncertainty in submodular objective functions for choosing subsets. In addition to these measures, we show that balancing constraints on predicted class labels and decision boundaries are beneficial. We propose a novel formulation of these constraints using matroids, an algebraic structure that generalizes linear independence in vector spaces, and present an efficient greedy algorithm with constant approximation guarantees. We outperform competing baselines on standard classification datasets such as CIFAR10, CIFAR-100, ImageNet, as well as long-tailed datasets such as CIFAR-100-LT.
references.authors: J.T. Ash C. Zhang A. Krishnamurthy J. Langford A. Agarwal
references.title: Deep batch active learning by diverse, uncertain gradient lower bounds
references.venue: In ICLR,
references.authors: V. Badrinarayanan F. Galasso R. Cipolla
references.title: Label propagation in video sequences
references.venue: In CVPR,
references.authors: J. Bien R. Tibshirani
references.title: Prototype selection for interpretable classification
references.venue: The Annals of Applied Statistics,
references.authors: V. Birodkar H. Mobahi S. Bengio
references.title: Semantic redundancies in image-classification datasets: The 10% you don’t need, 2019
references.authors: A. Borodin A. Jain H.C. Lee Y. Ye
references.title: Max-sum diversification, monotone submodular functions, and dynamic updates
references.venue: ACM Trans. Algorithms,
references.authors: K. Brinker
references.title: Incorporating diversity in active learning with support vector machines
references.venue: In ICML,
references.authors: J. Carbonell J. Goldstein
references.title: The use of mmr, diversity-based reranking for reordering documents and producing summaries
references.venue: SIGIR ’98,
references.authors: L. Chen G. Zhang H.Zhou
references.title: Fast greedy map inference for determinantal point process to improve recommendation diversity
references.venue: In NeurIPS,
references.authors: C. Coleman C. Yeh S. Mussmann B. Mirzasoleiman P. Bailis P. Liang J. Leskovec M. Zaharia
references.title: Selection via proxy: Efficient data selection for deep learning, 2020
references.authors: Y. Cui M. Jia T.Y. Lin Y. Song S. Belongie
references.title: Class-balanced loss based on effective number of samples
references.venue: In CVPR,
references.authors: Abhimanyu Das David Kempe
references.title: Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection
references.venue: Journal of Machine Learning Research,
references.authors: S. Dasgupta D.J. Hsu C. Monteleoni
references.title: A general agnostic active learning algorithm
references.venue: In NeurIPS,
references.authors: J Devlin M.W. Chang K. Lee K. Toutanova
references.title: BERT: pre-training of deep bidirectional transformers for language understanding
references.authors: E. Elhamifar
references.title: Sequential facility location: Approximate submodularity and greedy algorithm
references.venue: In ICML,
references.authors: G.F. Elsayed D. Krishnan H. Mobahi K. Regan S. Bengio
references.title: Large margin deep networks for classification
references.venue: In NIPS,
references.authors: M.L. Fisher G.L. Nemhauser L.A. Wolsey
references.title: An analysis of approximations for maximizing submodular set functions-ii
references.venue: In Polyhedral Combinatorics. Mathematical Programming Studies,
references.authors: Amirata Ghorbani James Zou Andre Esteva
references.title: Data shapley valuation for efficient batch active learning, 2021
references.authors: R. Gilad-Bachrach A. Navot N. Tishby
references.title: Query by committee made real
references.venue: In NIPS,
references.authors: D. Golovin A. Krause
references.title: Adaptive submodularity: Theory and applications in active learning and stochastic optimization
references.venue: J. Artif. Int. Res.,
references.authors: Daniel Golovin Andreas Krause
references.title: Adaptive submodularity: Theory and applications in active learning and stochastic optimization
references.authors: R. Guo P. Sun E. Lindgren Q. Geng D. Simcha F. Chern S. Kumar
references.title: Accelerating large-scale inference with anisotropic vector quantization
references.venue: In ICML,
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Deep residual learning for image recognition
references.venue: In CVPR,
references.authors: G. Hinton L. Deng G.E. Dahl A. Mohamed N. Jaitly A. Senior V. Vanhoucke P. Nguyen T. Sainath B. Kingsbury
references.title: Deep neural networks for acoustic modeling in speech recognition
references.venue: IEEE Signal Processing Magazine,
references.authors: A. Holub P. Perona M.C. Burl
references.title: Entropy-based active learning for object recognition
references.venue: In CVPR Workshop,
references.authors: K J Joseph Vamshi Teja R Krishnakant Singh Vineeth N Balasubramanian
references.title: Submodular batch selection for training deep neural networks, 2019
references.authors: A.J. Joshi F. Porikli N. Papanikolopoulos
references.title: Multi-class active learning for image classification
references.venue: In CVPR,
references.authors: L. Kaufman P.J. Rousseeuw
references.title: Clustering by means of medoids
references.authors: V. Kaushal R. Iyer S. Kothawade R. Mahadev K. Doctor G Ramakrishnan
references.title: Learning from less data: A unified data subset selection and active learning framework for computer vision, 2019
references.authors: V. Kaushal S. Kothawade G. Ramakrishnan J.A. Bilmes R.K. Iyer
references.title: PRISM: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization
references.venue: CoRR, abs/2103.00128,
references.authors: B. Kim R. Khanna O. Koyejo
references.title: Examples are not enough, learn to criticize! criticism for interpretability
references.venue: In NIPS,
references.authors: Kwan-Young Kim Dongwon Park Kwang In Kim Se Young Chun
references.title: Task-aware variational adversarial active learning
references.venue: In CVPR,
references.authors: P. Kohli M.P. Kumar P.H.S. Torr
references.title: beyond: Solving energies with higher order cliques
references.venue: IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: V. Kolmogorov R. Zabin
references.title: What energy functions can be minimized via graph cuts
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: S. Kothawade N. Beck K. Killamsetty R.K. Iyer
references.title: SIMILAR: submodular information measures based active learning in realistic scenarios
references.venue: CoRR, abs/2107.00717,
references.authors: A. Krizhevsky I. Sutskever G.E. Hinton
references.title: Imagenet classification with deep convolutional neural networks
references.venue: In NeurIPS,
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.authors: Miroslav Kubat Stan Matwin
references.title: Addressing the curse of imbalanced training sets: One-sided selection
references.venue: In Proceedings of the International Conference on Machine Learning (ICML),
references.authors: D.D. Lewis W.A. Gale
references.title: A sequential algorithm for training text classifiers
references.venue: In SIGIR,
references.authors: H. Lin J. Bilmes
references.title: A class of submodular functions for document summarization
references.venue: In ACL,
references.authors: Douglas Lundholm Lars Svensson
references.title: Clifford algebra, geometric algebra, and applications
references.authors: Z. Mariet J. Robinson J. Smith S. Sra S. Jegelka
references.title: Optimal batch variance with second-order marginals
references.venue: In ICML Workshop,
references.authors: Aditya Krishna Menon Sadeep Jayasumana Ankit Singh Rawat Himanshu Jain Andreas Veit Sanjiv Kumar
references.title: Long-tail learning via logit adjustment, 2020
references.authors: G.L. Nemhauser L.A. Wolsey M.L. Fisher
references.title: An analysis of the approximations for maximizing submodular set functions
references.venue: Mathematical Programming,
references.authors: James Oxley
references.title: Matroid Theory
references.authors: H.S. Park C.H. Jun
references.title: A simple and fast algorithm for k-medoids clustering
references.venue: Expert Systems with Applications,
references.authors: A. Prasad S. Jegelka D. Batra
references.title: Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets
references.venue: In NIPS,
references.authors: Chao Qian Jing-Cheng Shi Yang Yu Ke Tang Zhi-Hua Zhou
references.title: Subset selection under noise
references.venue: Advances in Neural Information Processing Systems,
references.authors: S. Ramalingam C. Russell L. Ladicky P.H.S. Torr
references.title: Efficient minimization of higher order submodular functions using monotonic boolean functions
references.venue: Discrete Applied Mathematics,
references.authors: O. Russakovsky J. Deng H. Su Krause J S. Satheesh S. Ma Z. Huang A. Karpathy A. Khosla M. Bernstein A.C. Berg L. Fei-Fei
references.title: Imagenet large scale visual recognition
references.authors: T. Scheffer C. Decomain S. Wrobel
references.title: Active hidden markov models for information extraction
references.venue: In Advances in Intelligent Data Analysis,
references.authors: Ozan Sener Silvio Savarese
references.title: Active learning for convolutional neural networks: A core-set approach
references.venue: In ICML, 2018
references.authors: B. Settles
references.title: Active learning literature survey
references.venue: Technical report, University of Wisconsin-Madison,
references.authors: H.S. Seung M. Opper H. Sompolinsky
references.title: Query by committee
references.venue: In COLT,
references.authors: Changjian Shui Fan Zhou Christian Gagn’e Boyu Wang
references.title: Deep active learning: Unified and principled method for query and training
references.venue: In AISTATS,
references.authors: I. Simon N. Snavely S.M. Seitz
references.title: Scene summarization for online image collections
references.venue: In ICCV,
references.authors: E. Strubell A. Ganesh A. McCallum
references.title: Energy and policy considerations for deep learning in NLP
references.authors: I. Sutskever O. Vinyals Q.V. Le
references.title: Sequence to sequence learning with neural networks
references.venue: In NeurIPS,
references.authors: C. Szegedy W. Liu Y. Jia P. Sermanet S. Reed D. Anguelov D. Erhan V. Vanhoucke A. Rabinovich
references.title: Going deeper with convolutions
references.venue: In CVPR,
references.authors: S. Tong D. Koller
references.title: Support vector machine active learning with applications to text classification
references.authors: B.C. Wallace K.Small C.E. Brodley T.A
references.title: Trikalinos. Class imbalance, redux
references.venue: In Proc. ICDM,
references.authors: Z. Wang J. Ye
references.title: Querying discriminative and representative samples for batch mode active learning
references.venue: ACM Trans. Knowl. Discov. Data,
references.authors: K. Wei R. Iyer J. Bilmes
references.title: Submodularity in data subset selection and active learning
references.venue: In ICML,
references.authors: Gert W. Wolf
references.title: Facility location: Concepts, models, algorithms and case studies. series: Contributions to management science
references.authors: Fedor Zhdanov
references.title: Diverse mini-batch active learning
references.venue: CoRR, abs/1901.05954,
references.authors: Yuxun Zhou Costas J. Spanos
references.title: Causal meets submodular: Subset selection with directed information
references.venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,
sections.heading: 1 INTRODUCTION
sections.text: Deep learning has shown unprecedented success in many domains, such as speech (Hinton et al., 2012), computer vision (Krizhevsky et al., 2012; Szegedy et al., 2015; He et al., 2016), and natural language processing (Sutskever et al., 2014; Devlin et al., 2018). This success generally relies on access to significant computational resources and large human-annotated datasets. For example, energy consumption and carbon footprint of developing common NLP models are shown to be comparable to the lifetime emissions of a car (Strubell et al., 2019). Similarly, human annotation is also a time-consuming and expensive process; Badrinarayanan et al. (2010) reports that semantic labeling of a single video frame takes around 45-60 minutes.
  In this paper we ask the following question: Given a large unlabeled dataset along with a small labeled (seed) dataset and an annotation budget, how do we select a subset of the unlabeled dataset, which, when annotated, will achieve the best performance? While this is addressed by many classical active learning methods (Settles, 2009), in this work we focus on the modern deep learning setting with CNNs and very deep networks such as ResNets (He et al., 2016). Typical active learning methods employ an iterative process where a single image is labeled and used to update the model at each step. The updated model is then used to pick the next image and so on. Such an approach is not feasible for deep networks. We therefore choose to study this problem in a batch setting (Sener & Savarese, 2018; Zhdanov, 2019; Shui et al., 2020; Kim et al., 2021; Ghorbani et al., 2021). In this setting, we first train an initial model using the labeled seed dataset. We typically use
  a randomly selected 10% subset of the full dataset as seed. After this, as done in the standard batch-mode active learning setup, our algorithm uses this initial seed model to select a subset of the full dataset for which the labels will be revealed. We then train a new model with the selected subset. As shown in Fig. 1, our subset selection methods can identify subsets with 30% to 40% less data, which achieve performance similar to what we could get training with the full annotated dataset.
  Most existing methods for data subset selection use some notion of margin, representativeness, or diversity. For example, the classical margin-based sampling selects images for which the prediction of the class labels are most uncertain. These could, for example, be the images having smallest difference between the highest and the second highest label probabilities (Lewis & Gale, 1994). Clustering-based objectives such as k-center (Sener & Savarese, 2018) or k-medoids (Kaufman & Rousseeuw, 1987) select cluster centers with rich representativeness to model the entire dataset. Diverse subsets are identified by casting the problem as the maximization of submodular functions (Wei et al., 2015), which are discrete analogues of convex functions.
  We see two main limitations with existing methods. First, there is no single subset selection criterion that achieves the best performance on different classification datasets. For example we observe in our experiments (Sec. 6) that in certain datasets, diversity works better than margin, and vice versa. The second limitation is particularly relevant to margin-based methods where the selection is driven by the closeness of an image to a decision boundary. In a classification problem with L labels, we have ( L 2 ) possible decision boundaries. Most margin-based methods greedily select images close to decision boundaries. This often results in a selection of too many images representing a small number of classes and boundaries, while ignoring many others.
  To address the first limitation, we develop a unified algorithm based on maximization of a submodular function, which can combine different selection objectives. Importantly, we do this without sacrificing constant approximation guarantees. To address the second limitation, we incorporate class-balancing and boundary-balancing constraints in our optimization using intersection of matroids. Typical diversity promoting objective functions use an underlying nearest neighbor graph that models the distances between the training samples. In this work, We present an improved diversity objective function that models the simultaneous interaction of three nearby samples, while the standard approach typically considers the interaction of two nearby samples.
  To summarize, our contributions are: (1) We develop a unified algorithm to combine different objective functions along with class-balancing and boundary-balancing constraints using the intersection of matroids. (2) We propose an improved diversity objective function based on 3-clique interactions in the nearest neighbor graph. (3) We outperform baseline methods on three standard classification datasets (CIFAR-10, CIFAR-100, and ImageNet) and a long-tailed classification dataset (CIFAR-100LT).
sections.heading: 2 RELATED WORK
sections.text: Data summarization and submodularity: Submodularity (Nemhauser et al., 1978), often seen as the discrete analogue of convexity, can be used to model subset selection objectives associated with diversity and representativeness. While subset selection problems are mostly NP-hard, submodular optimization algorithms are efficient and come with constant approximation guarantees (Carbonell & Goldstein, 1998; Simon et al., 2007; Krause & Golovin; Golovin & Krause, 2010; Wei et al., 2015; Lin & Bilmes, 2011; Kaushal et al., 2019; Kim et al., 2016; Prasad et al., 2014; Golovin & Krause, 2010; 2011; Joseph et al., 2019; Zhou & Spanos, 2016; Qian et al., 2017; Das & Kempe, 2018; Elhamifar, 2019; Kothawade et al., 2021; Kaushal et al., 2021).
  A submodular function that promotes representativeness and diversity was utilized in document summarization (Lin & Bilmes, 2011). Discriminant point process (DPP) are probabilistic models capable of selecting diverse subsets. They were used for minibatch selection in Mariet et al. (2020), and the maximum a posteriori (MAP) inference for DPP is submodular (Chen et al., 2018).
  Uncertainty sampling and active learning: Active learning methods primarily focus on reducing the label annotation costs by selecting images to label that are more likely to yield the best model (See Settles (2009) for a detailed survey). Theoretical guarantees are usually about how quickly the version space, that maintains a set of good candidate classifiers, shrinks based on the availability of new data (Dasgupta et al., 2008). Uncertainty sampling selects the most challenging or uncertain
  images first, in the hope that this will eliminate the need to label other, easier ones. In a classification setting, predictions from the initial model can provide class probabilities that can help identify images with high uncertainty. Possibilities include simple uncertainty measures from the best and second best class probabilities (Lewis & Gale, 1994; Scheffer et al., 2001), entropy measure (Holub et al., 2008; Joshi et al., 2009), and geometric distance to the decision boundary (Tong & Koller, 2002; Brinker, 2003), selection via proxies (Coleman et al., 2020), and query by committee (Gilad-Bachrach et al., 2005; Seung et al., 1992), where a committee of models are used to identify images where they most disagree.
  Coresets: A coreset is a small set of points that approximates the shape of a larger point set. In an ML setting it is a small subset of images from a larger dataset such that the model trained on the coreset is competitive with the one learned from the entire dataset. It is shown in (Sener & Savarese, 2018; Wolf, 2011) that the average loss over any given subset of the dataset and the remaining points can be bounded, and that the minimization of this bound can be mapped to the k-center problem.
  Clustering: Other classical techniques for subset selection include clustering algorithms such as k-medoids (Kaufman & Rousseeuw, 1987; Park & Jun, 2009), which minimizes the sum of dissimilarities between images belonging to a cluster and a point designated as its center. Agglomerative clustering was used to select subsets in Birodkar et al. (2019), where it was shown that at least 10% of images are redundant in ImageNet and CIFAR-10 training. In this work, we show that at least 30-40% of the images in CIFAR-10, CIFAR-100 and ImageNet are redundant. In Ash et al. (2020), k-MEANS++ algorithm is used to find a set of diverse and uncertain samples using the gradients of the final layer of the network.
  In the context of interpretability, prototypes are subsets that best represent the entire dataset where a learned model performs the best, and criticisms are the images where a learned model does not do well. Both prototypes and criticisms can be modeled using maximum-mean discrepancy (MMD), that measures the difference between two distributions. The resulting optimization to compute the subsets can be cast as submodular maximization (Kim et al., 2016). Minimization of the MMD between the entire dataset and the selected subset can be seen as empirical risk minimization, and such an approach was used for batch mode active learning (Wang & Ye, 2015). Other classical techniques for prototype selection includes k-medoids (Bien & Tibshirani, 2011) clustering methods.
sections.heading: 3 PROBLEM STATEMENT
sections.text: We consider a classification setting with L classes and n training images U = {x1, . . . , xn}. Let G = {1, . . . , n} denote the indices in the dataset. Let ψ : X → RL be a (trained) neural network that maps an input image to a probability distribution over the L classes. The model ψ can be seen as the composition of an embedding function φ : X → RD that maps an input to an D-dimensional embedding, and a discriminator function h : RD → RL that maps the embedding to output probability predictions.
  Subset selection and model evaluation. We assume that we are given a small, annotated subset of U , which we refer to as the seed dataset (this is 10% of U in our experiments). We use this seed dataset to train an initial model ψseed. Our goal is to use this initial model to select a subset S of G, subject to a given annotation budget, such that when the images in S are annotated we can get the best classification performance training a new model with them. To this end, using the seed model, we generate embeddings and predictions for all the input images in U . Next, we construct a neighborhood graph (G,E) where E denotes the weighted set of edges associated with nearby training images in the embedding space RD. Our subset selection algorithm only depends on these embeddings, predictions, and the nearest-neighbor graph (G,E). As in the standard active learning settings, we do not use the groundtruth labels in U while selecting subsets. For modeling subset selection, we employ a submodular set function f : 2G → R that provides a utility value for every subset of G using notions of uncertainty and diversity. We show that the class and boundary balancing constraints can be enforced using intersections of partition matroids. With this modeling, subset selection is essentially the task of finding the subset with maximum utility value while satisfying the matroid constraints. This inference problem is combinatorial in the number of training samples, and the brute-force solution is infeasible. For efficient inference, we rely on the submodular property of the objective function and the use of matroids for modeling balancing
  constraints. Such an approach allows us to use an efficient greedy algorithm to maximize the objective function while satisfying matroid constraints with constant approximation guarantees.
  Once the subset S is computed, we request the groundtruth labels for the images in S. We use the annotated subset US ⊆ U to train a model ψS and evaluate its performance on a common held-out test set.
sections.heading: 4 BACKGROUND
sections.text: In Sec. 5 we show that our subset selection objective is both submodular and monotonic. We formally define these properties of a set function below.
  Definition 1. Let Ω be a finite set. A set function F : 2Ω → R is submodular if for all A,B ⊆ Ω with B ⊆ A and e ∈ Ω \A, we have F (A ∪ {e})− F (A) ≤ F (B ∪ {e})− F (B).
  This property is also referred to as diminishing returns since the gain diminishes as we add elements Nemhauser et al. (1978).
  Definition 2. A set function F is monotonically non-decreasing if F (B) ≤ F (A) when B ⊆ A.
  In Sec. 5.1 we show how to incorporate class balancing and boundary balancing priors in the subset selection algorithm. We use algebraic structures called matroids and their intersections. We formally define them below.
  Definition 3. A matroid is an ordered pair M = (Ω, I) consisting of a finite set Ω and a collection I of subsets of Ω satisfying three conditions. (1) The collection contains the empty set, i.e., ∅ ∈ I . (2) If I ∈ I and I ′ ⊆ I , then I ′ ∈ I. (3) If I1 and I2 are in I and |I1| < |I2|, then there is an element e in I2 \ I1 such that I1 ∪ {e} ∈ I.
  The members of I are called the independent sets of M . See Oxley (1992) for other, equivalent definitions of matroids.
  Definition 4. Let Ω1, . . . ,Ωn be a partition of the finite set Ω and let k1, . . . , kn be positive integers. The ordered pairM = (Ω, I) is a partition matroid if I = {I : I ⊆ Ω, |I∩Ωi| ≤ ki, 1 ≤ i ≤ n} Definition 5. Given two matroids M1 = (Ω, I1) and M2 = (Ω, I2) over the ground set Ω, the intersection of the matroids is given by M1 ∩M2 = (Ω, I1 ∩ I2).
sections.heading: 5 SUBSET SELECTION
sections.text: We propose a unified formulation for uncertainty and diversity using set functions of the form f : 2G → R, where 2G is the power set of the vertex set G. We show that our unified objective function is submodular and montonic, and that the balancing constraints could be incorporated as matroids (formally defined in Sec. 4). This implies that our efficient greedy algorithm comes with constant approximation guarantees (Nemhauser et al., 1978).
  We cast subset selection using a criterion f , as maximizing a corresponding set function under a budget constraint:
  S∗ = arg max S⊆G f(S) s.t. |S| = k. (1)
  Here S∗ is the optimal subset based on the selection criterion, and k is the budget. Our functions consist of a sum of terms, and the individual terms are modeled using the distances between embeddings. These embeddings are produced by the initial model ψseed, which we train using the annotated seed dataset.
  Our unified objective function is written as the conic combination of several individual functions based on uncertainty (funcertainty), diversity (fdiversity), and clique function (ftriple):
  f(S) = λ1funcertainty(S) + λ2fdiversity(S) + λ3ftriple(S), (2)
  where λi ≥ 0, i ∈ {1, . . . , 3}. Each of these constituent functions have simple geometric interpretations (See Fig. 2), and we provide their analytical expressions below:
  Uncertainty based sampling. We define the uncertainty-based utility function funcertainty as:
  funcertainty(S) = ∑ i∈S u(i), (3)
  where u(i) is a utility value for each example i ∈ G, based on its uncertainty. There are three popular choices for the utility functions using uncertainty: least confident, margin (Scheffer et al., 2001), and entropy. In this paper, we use margin, which is applicable in a multi-class setting, and gives preference to “hard to classify” or “low margin” examples (see Scheffer et al. (2001) for more details). More specifically:
  u(i) = 1− ( P (Y = bb|xi)− P (Y = sb|xi) ) ,
  (4) where bb and sb denote the best and the second best predicted class labels for xi according to our initial model ψseed. P (Y = ·|xi) denotes the class probabilities predicted by the same model for xi.
  Diversity. Given a budget on the size of the subset, the diversity criterion promotes selection of images that are diverse or spread apart in the embedding space. We define a set function fdiversity that evaluates diversity as follows:
  fdiversity(S) = ∑ i∈S unary(i)−γ ∑ i,j: (i,j)∈E, i,j∈S
  s(i, j). (5) The unary terms unary(i) capture the utility of an individual image and the pairwise terms s(i, j) are the similarity between a pair of images from the selected subset that have an edge (i, j) ∈ E in the nearest neighbor graph (G,E). As discussed in the Sec. 6, we use the cosine similarity in the embedding space as the similarity measure.
  The hyperparameter γ ≥ 0 determines the relative importance of the unary and pairwise terms. The pairwise term limits redundancy. If two points i and j with high similarity are both selected, we incur a penalty based on the similarity between them.
  To ensure monotonicity of fdiversity, we can use a constant unary term, unary(i) = maxl∈G ∑ j:(l,j)∈E s(l, j).
  Lemma 1. The function fdiversity is monotonically non-decreasing and submodular.
  The proof is available in the Appendix.
  Clique function. Given a nearest neighbor graph, we identify cliques of size three by checking for edges among the k-nearest neighbors of every sample. Given a set of cliques given by T , we define ftriple as follows:
  ftriple(S) = ∑ i∈S α(i)− η ∑ i,j,k: (i,j,k)∈T , i,j,k∈S t(i, j, k). (6)
  where α(i) denotes the number of triple cliques involving the sample i, and t(i, j, k) is 1 when the volume consumed by the embeddings of the triplet {i, j, k} is less than a threshold Tthresh, and 0 otherwise. The volume computation in higher dimensional space involves outer product (Lundholm & Svensson, 2009), similar to cross-product in 3-dimensional space. For computational efficiency, we approximate the volume using the area of triangle based on the three side lengths obtained from the nearest neighbor graph. We can extend the idea of triple cliques to higher orders (Kolmogorov &
  Zabin, 2004; Kohli et al., 2007; Ramalingam et al., 2017), but this can be computationally expensive when we consider millions of training samples.
  We prove the following lemma in the Appendix.
  Lemma 2. The function ftriple is monotonically non-decreasing and submodular.
  We note that there are other ways to maximize the diversity function. For example, by replacing the similarity term s(i, j) with a metric distance function, the diversity criteria can be seen as the max-sum k diversification problem, for which algorithms exist with constant approximation guarantees (Borodin et al., 2017).
  Any conic combination of submodular functions is submodular (Nemhauser et al., 1978), and thus f(S) is submodular.
sections.heading: 5.1 BALANCING CONSTRAINTS
sections.text: In this section we show how we incorporate balancing constraints in our unified formulation.
  Class balancing constraint. Subsets selected based on diversity or margin criteria can lead to severe class imbalance. Consequently, models trained using these imbalanced subsets can show superior performance on common classes, and inferior performance on rare classes Cui et al. (2019). A reweighted loss function can partially address this problem but performance on classes with no, or very few representatives will still suffer.
  To overcome this problem we incorporate explicit class-balancing constraints in our formulation. We do this using a partition matroid constraint, a choice that allows us to maintain our approximation guarantees. Consider a partition {G1, G2, . . . , GL} of the full dataset G. Here L denotes the number of classes and Gi consists of the images belonging to class i, where pseudo-labels are computed using the initial (seed) model. Let k1,. . . ,kL be user-defined positive integers specifying the sizes of the desired subsets. We choose subsets that are independent sets of the partition matroid M = (G, Ip):
  Ic = {I : I ⊆ G, |I ∩Gi| ≤ ki, 1 ≤ i ≤ L}. (7)
  Boundary balancing constraint. The initial model ψI that we trained using the seed dataset, defines a set of decision boundaries for every pair of classes. Formally, the decision boundary for a pair of classes {a, b} is given by:
  D{a,b} ∆ = {x;P (Y = a|x) = P (Y = b|x)}, (8)
  where P (y|x) are the posterior probabilities from the seed model. In other words, these are the set of points where the posterior class probabilities for two different classes agree. Decision boundaries can be defined in input space, output space, or in the space defined by the intermediate layers in the network Elsayed et al. (2018). Since we are only interested in associating an image to its closest decision boundary, our formulation does not require computation of the exact distance to the boundary. Instead we simply use predicted class probabilities.
  We define the margin score of an image xi (given predictions from the initial model) as m(xi) = 1− ( P (Y = bb|xi)− P (Y = sb|xi) ) , (9)
  where bb and sb correspond to best and the second best class labels, respectively. We associate xi with the boundary (bb, sb) if m(x) > τ , for some threshold τ .
  We observe that the number of class boundaries grows quadratically with the number of classes and conjecture that many datasets with a large number of classes do not contain any images close to many decision boundaries. Our goal is to design a subset selection algorithm that promotes selection of images near as many decision boundaries as possible.
  To quantify this observation, we use predictions from our initial model for ImageNet to associate any image in the dataset which has a margin score greater than τ = 0.05 to the corresponding class boundary. Since ImageNet has 1000 classes, we have ( 1000
  2
  ) boundaries. We found that 15% of all
  possible boundaries were covered.
  Let D = {b(x);x ∈ U} denote the set of all the decision boundaries associated with all the images in the training set U , and b(x) is a function that associates a given image to a certain decision boundary or to the empty set ∅, based on the margin score. In Fig. 3, we show the histogram of the number of images associated with different decision boundaries. We note that it is possible to associate an image to multiple decision boundaries, and defer exploring this option to future work.
  Similar to the class-balancing problem, we consider a partition {Gb1 , Gb2 , . . . , GbM } of the full dataset G, where Gbi denotes the set of images belonging to the decision boundary bi ∈ D. Let d1,. . . ,dM be user-defined positive integers specifying the maximum number of images near different boundaries. Let us consider the following partition matroid M = (G, Id):
  Id = {I : I ⊆ G, |I ∩Gbi | ≤ di, 1 ≤ i ≤M} (10)
  In order to impose both class-balancing and boundary-balancing constraints, our selected subset should be the independent set of both the partition matroids given by (G, Ic) and (G, Id). Note that the intersection of two matroids is not a matroid in general. However, Fisher et al. (1978) shows that applying the greedy algorithm to a submodular monotonic objective with matroid intersection constraints maintains approximation guarantees.
sections.heading: 5.2 GREEDY ALGORITHM
sections.text: Subset selection using class- and boundary-balancing constraints is given by: S∗ = arg max
  S⊆G f(S) s.t. |S| = k, S ∈ Ic, S ∈ Id, (11)
  where f is our unified objective. The greedy algorithm for selecting a subset of size k is given in Algorithm 1.
  Algorithm 1: Greedy algorithm 1. Initialize S = ∅; 2. Let s = arg maxs′∈G f(S ∪ {s′})− f(S) such that S ∪ {s′} ∈ Ic ∩ Id; 3. If s 6= ∅ and |S| < k then S = S ∪ {s}, go to 2.; 4. S is the required solution;
  Given that f is monotonic and submodular, a theorem from Fisher et al. (1978) implies that we have a constant approximation guarantee for the greedy algorithm according to the bound f(Sgreedy) ≥
  1 p+1f(SOPT ), where f(∅) = 0 and p is the number of matroid constraints. Since we have two matroids, we have f(Sgreedy) ≥ 13f(SOPT ).
sections.heading: 5.3 COMPUTATIONAL COMPLEXITY
sections.text: The greedy algorithm can be efficiently implemented using a priority queue. Given a k-nearest graph on the embeddings and the uncertainty estimates, the proposed algorithm has a complexity of O(|V |+ nk2log2(|V |)), where V is the set of all samples and n is the size of the subset. Without the triple cliques its complexity is O(|V |+ nklog(|V |)), which is the same as that of k-center. For implementation reference, we provide pseudo-code in Algorithm 2. In experiments, we choose k = 10, and the additional overhead from triple-clique constraint is minimal.
  Algorithm 2: Pseudocode for Subset Selection. 1. Input: k-NN graph G = (V,E). 2. Initialize an empty priority queue pq. 3. For all v ∈ V do pq ← ADD(v, w(v)), where the weight w(v) is based on unary such as uncertainty. 4. Initialize S = {c}, where (c, w) = POP(pq). 5. While |S| < k and NOT-EMPTY(pq) do:
  • 6. (c, w)← POP(pq). • 7. If S ∪ c satisfies balancing constraints, S ← S ∪ c. • 8. For all n1 ∈ NEIGHBOR(c) and n1 /∈ S, do pq ← UPDATE(n1, w(n1)− γs(n1, c)).
  – 9. For all n2 ∈ NEIGHBOR(c) and n2 ∈ S, do pq ← UPDATE(n1, w(n1)− γs(n1, c)− ηt(c, n1, n2)).
  9. Output S.
sections.heading: 6 EXPERIMENTS
sections.text: Datasets. We use four datasets: CIFAR10 (Krizhevsky et al., 2009), CIFAR100 (Krizhevsky et al., 2009), ImageNet (Russakovsky et al., 2014), and CIFAR100-LT (Menon et al., 2020). The last one is a long-tailed dataset where the head class is 100 times more frequent than the least-frequent class (Menon et al., 2020). We do not apply any long-tail techniques as we want to compare the performance of vanilla ERM across different methods.
  Initial model. For each of the datasets we select a random seed subset of size 10% and use it to train a ResNet-56 (He et al., 2016) initial model. We use the initial model to generate predictions and
  embeddings for all the images in the dataset. The embeddings are 64-dimensional for CIFAR and 2048-dimensional for Imagenet. We construct the neighborhood graph (G,E) by finding k = 10 nearest neighbors of each image in embedding space, using the fast similarity search of Guo et al. (2020). We evaluated different similarity measures such as cosine similarity, L1, and L2 distances, and found no significant differences. All the reported experiments use cosine similarities.
  Hyperparameters. For the CIFAR10, CIFAR100, and CIFAR100-LT experiments we used 450 epochs and the learning rate is divided by 10 at the following epochs:15, 200, 300, and 400. The base learning rate was set to 1.0. For ImageNet we used 90 epochs and the learning rate is divided by 10 at the following epochs: 5, 30, 60, and 80. The base learning rate was set to 0.1. In all the datasets, we used SGD with momentum 0.9 (with nestrov) for training. When trained with the full training set, the top-1 accuracies for CIFAR-10, CIFAR-100, ImageNet, and CIFAR-100-LT are 93.04%,71.37%, 76.39%, and 39.01%, respectively.
  Evaluation. We show four baselines: RANDOM, MARGIN, SUBMOD, and k-CENTER (Sener & Savarese, 2018). SUBMOD baseline is the function in Equation 2 without the triple clique term and the balancing constraints. The parameters (k1, . . . , kL) in the class-balancing partition matroid are set based on the desired subset size. In other words, ki sets an upper limit on the number of images from a specific class. In our experiments, we set this value to be ηnL , where n, η, and L denote the number of images, fraction of the training set, and the number of labels, respectively. In the case of boundary balancing matroid, we set the parameters di to be max(1, ηni), where ni denotes the number of images associated with the decision boundary bi ∈ D. For every subset, we train three models and averaged performance is shown in Fig 4. For our algorithm SUBMOD-BAL we use λ1 = 0.7, λ2 = 0.30, and λ3 = 1 in Equation 2. The baselines RANDOM and MARGIN do not have any hyperparameters. For k-CENTER and SUBMOD, we use the same nearest neighbor graph with the same number of neighbors.
  We outperform other methods marginally in standard datasets and significantly in the long-tailed dataset. The k-CENTER (Sener & Savarese, 2018) performs close to the proposed method and outperforms standard submdoular algorithm. Note that on all these datasets, accuracies with either 80% or 90% subsets, or both, exceed that with the full dataset. This is not surprising since completely eliminating some examples in the training set has shown to be beneficial in prior work (Kubat & Matwin, 1997; Wallace et al., 2011).
  Ablation study: The balancing constraints show an average improvement of 0.61% in CIFAR datasets, and 2.83% in CIFAR100-LT. The clique function shows an improvement of 0.49% in CIFAR and 1.13% in CIFAR100-LT dataset. We evaluated the role of k, the number of nearest neighbors in k-nearest neighbor graph construction. While we used k = 10 in all our experiments the marginal benefit in using k = 100 and k = 1000 are given by +0.15% and +0.25%, respectively.
sections.heading: 7 DISCUSSION
sections.text: We propose a triple-clique diversity objective and balancing constraints on class labels and decision boundaries. We showed that the incorporation of balancing constraints usually leads to better subsets compared to standard baselines, and the impact is highly significant in training with long-tailed datasets such as CIFAR100-LT. We also show that some popular image classification datasets have at least 30-40% redundant images.
  On standard datasets, the difference between our method and k-center is marginal, and this can be due to a deeper connection. The k-center algorithm can be reduced to a series of dominating set problems (Vazirani, 2001). Dominating set can be reduced to set cover, which is also a submodular problem. While k-center has connection to submodularity, our proposed framework does not generalize k-center. It will be beneficial to find a principled way to combine these methods.
  ETHICAL STATEMENT
  Training large models are resource intensive and labeling data sets is also extremely labor-intensive, requiring significant human effort. For example, detailed semantic segmentation for a single image can take up to 60 minutes. In this work, we develop subset selection methods that can lead to accurate models with less computations and data. This will eventually lead to reduced human labeling efforts, and less utilization of computational resources.
  REPRODUCIBILITY STATEMENT
  The basic algorithm to find the subset is a standard greedy algorithm and it is easy to implement. We also provided the pseudocode in Algorithm 2. This paper is only about subset computation and the training code is not changed. All the hyperparameters are listed in experiment section. We will release the code, the seed model, and the nearest neighbor graph for other researchers to compare their models.
sections.heading: A APPENDIX
sections.text: Lemma 1. The function fdiversity is monotonically non-decreasing and submodular.
  Proof. The function fdiversity is given by fdiversity(S) = ∑ i∈S max l∈G ∑ j:(l,j)∈E s(l, j)
  −γ ∑
  i,j: (i,j)∈E, i,j∈S
  s(i, j). (12)
  We will show that the function is monotonically non-decreasing and submodular when 0 ≤ γ ≤ 1. We will first show that the function is monotonically non-decreasing. Consider an element e ∈ G\S:
  fdiversity(S ∪ e)− fdiversity(S) = max l∈G ∑ j:(l,j)∈E s(l, j)−
  γ ∑
  j: (e,j)∈E, j∈S
  s(e, j) (13)
  In the first term, j ∈ G, whereas in the second j ∈ S. The first term is a maximum over all samples in G, including l = e. Since λ ≤ 1 and S ⊆ G, we have fdiversity(S ∪ e)− fdiversity(S) ≥ 0 and thus the function in Eq. 12 is monotonically non-decreasing.
  Next, we will show that the function fdiversity(S) is submodular. In order to do this, we show the following when A,B ⊆ G, B ⊆ A, and e ∈ G\A:
  fdiversity(A ∪ e)− fdiversity(A) ≤ fdiversity(B ∪ e)− fdiversity(B) (14)
  We expand the left hand side of the above expression using the definition of fdiversity(S):
  fdiversity(A ∪ e)− fdiversity(A) = max l∈G ∑ j:(l,j)∈E s(l, j)−
  λ ∑
  j: (e,j)∈E, j∈A
  s(e, j) (15)
  We expand the right hand side as follows:
  fdiversity(B ∪ e)− fdiversity(B) = max l∈G ∑ j:(l,j)∈E s(l, j)−
  γ ∑
  j: (e,j)∈E, j∈B
  s(e, j) (16)
  Subtracting Eq. 16 from Eq. 15 we have: (fdiversity(A ∪ e)− fdiversity(A)) − (fdiversity(B ∪ e)− fdiversity(B)) =
  γ ∑
  j: (e,j)∈E, j∈B
  s(e, j)− γ ∑
  j: (e,j)∈E, j∈A
  s(e, j) (17)
  Since γ ≥ 0, s(., .) >= 0, and B ⊆ A, we satisfy Eq. 14.
  Lemma 2. The function ftriple is monotonically non-decreasing and submodular.
  Proof. The function ftriple is given by ftriple(S) = ∑ i∈S α(i)− η ∑ i,j,k: (i,j,k)∈T , i,j,k∈S t(i, j, k). (18)
  We will show that the function is monotonically non-decreasing and submodular when 0 ≤ η ≤ 1. We will first show that the function is monotonically non-decreasing. Consider an element e ∈ G\S:
  ftriple(S ∪ e)− ftriple(S) = α(e)− η ∑
  e,j,k: (e,j,k)∈T , e,j,k∈S
  t(e, j, k) (19)
  The first term α(e) is the number of triple cliques associated with e, and the maximum value of the second term is α(e) since 0 ≤ η ≤ 1. Thus we have ftriple(S ∪ e) − ftriple(S) ≥ 0 and thus the function in Eq. 18 is monotonically non-decreasing.
  Next, we will show that the function ftriple(S) is submodular. In order to do this, we show the following when A,B ⊆ G, B ⊆ A, and e ∈ G\A:
  ftriple(A ∪ e)− ftriple(A) ≤ ftriple(B ∪ e)− ftriple(B) (20)
  We expand the left hand side of the above expression using the definition of ftriple(S): ftriple(A ∪ e)− ftriple(A) = α(e)−
  η ∑
  e,j,k: (e,j,k)∈T , e,j,k∈A
  t(e, j, k) (21)
  We expand the right hand side as follows: ftriple(B ∪ e)− ftriple(B) = α(e)−
  η ∑
  e,j,k: (e,j,k)∈T , e,j,k∈B
  t(e, j, k) (22)
  Subtracting Eq. 22 from Eq. 21 we have: (ftriple(A ∪ e)− ftriple(A)) − (ftriple(B ∪ e)− ftriple(B)) =
  η ∑
  e,j,k: (e,j,k)∈T , e,j,k∈B
  t(e, j, k)− (23)
  η ∑
  e,j,k: (e,j,k)∈T , e,j,k∈A
  t(e, j, k) (24)
  Since η ≥ 0, t(., ., .) >= 0, and B ⊆ A, we satisfy Eq. 20.