summaries: The paper addresses the problem of open world object detection - a lifelong learning system where the object detector is required to detect objects belonging to all classes known so far and “unknown” objects. Unknown objects are annotated and available for training at a later stage. At a given time only a specific set of training data is available with annotations that involve all known classes so far, while all past training data are unavailable.    The proposed approach builds upon recent work [A], by incorporating a semantic topology in the object feature space (RoI features in Faster R-CNN). While [A] use contrastive clustering to group object features based on object category, and energy based out-of-distribution detection to detect “unknown” objects, the authors propose an end-to-end trainable approach. The proposed approach uses RoI features in two parallel streams, with one focused on clustering operation, while having object category prediction loss on both streams of features. Features are clustered around predetermined semantically meaningful object representations. Pre-trained word embeddings from a language model (CLIP) are used for this purpose. The use of pre-defined semantic anchors allows learned features of known objects to form consistent clusters during incremental learning.    Experiments are conducted using 80 categories from PASCAL-VOC and MSCOCO datasets. The problem is designed as 4 sequential tasks each involving 20 object categories (same setup as in [A]). Detection performance is measured using mAP, as well as measures that focus on unknown object detection.  [A] Towards Open World Object Detection, Joseph et al., CVPR 2021

summaries: This paper extends the recently-introduced object ORE object detector [A]. ORE is trained in an incremental fashion and was shown to minimize the confusion between classes presented in different task sets by adding a contrastive objective to the model training, that pushes features, representing different semantic classes, far away in the feature space. This paper presents the case that combining ORE detector with large-scale language models, trained by aligning textual queries and images, can significantly improve ORE detector results. This is not surprising: it was already shown that such multi-modal language models could be successfully used for detection of novel classes in a zero-shot setting (in which names of target classes are given, but image data for these classes is available during the model training, see [D]). To the best of my knowledge, the core idea of semantic anchoring using language models was introduced in [C] (see Sec. 3.3 Densely Sampled Embedding Space). In this work, the semantic embedding space is extended with additional data from external sources that contain semantic information about the unseen classes via language embedding to image embedding alignment. This method suggests using CLIP [B] instead (which makes sense and simplifies the knowledge transfer!)  [A] Joseph et al., CVPR’21 [B] Radford et al., ICLR’21 [C] Bansal et al., ECCV’18 [D] Xian et al., CVPR'17 [E] Zheng et al., CVPR’21

summaries: This paper proposes a semantic topology embedding for Open-World Object Detection (OWOD) where an object detector identifies objects of unknown classes and incrementally learns to classify them assuming that their annotations are progressively given by humans. To maintain discriminative and consistent relationships among object classes, the authors introduce a semantic topology for the feature space of the detector by constructing pre-deﬁned anchors for categories using a pretrained language model. During training, it enables the detector to distinguish unknown objects out of the known categories and also makes learned features of different classes undistorted during incremental learning. Eperimental results show that the semantic topology improves state-of-the-art open-world object detectors and help the open-world detectors preserve a discriminative and consistent feature space.

summaries: The paper proposes a novel method for open-world object detection, where instances of unknown categories need to be identified and annotated data for such new categories need to be integrated into the model in an incremental fashion. Prior work typically separate this problem into two tasks, out-of-distribution detection and incremental/continuous learning. This paper proposes to use fixed semantic anchors for each category, which are embedding vectors from a language model (or randomly generated vectors) for each category.  Importantly, when new data arrives, new embeddings are added while previous ones do not change. This encourages the feature representation to be compact (discriminative) and consistent (over time).

abstractText: A more realistic object detection paradigm, Open-World Object Detection, has arised increasing research interests in the community recently. A qualified openworld object detector can not only identify objects of known categories, but also discover unknown objects, and incrementally learn to categorize them when their annotations progressively arrive. Previous works rely on independent modules to recognize unknown categories and perform incremental learning, respectively. In this paper, we provide a unified perspective: Semantic Topology. During the life-long learning of an open-world object detector, all object instances from the same category are assigned to their corresponding pre-defined node in the semantic topology, including the ‘unknown’ category. This constraint builds up discriminative feature representations and consistent relationships among objects, thus enabling the detector to distinguish unknown objects out of the known categories, as well as making learned features of known objects undistorted when learning new categories incrementally. Extensive experiments demonstrate that semantic topology, either randomly-generated or derived from a well-trained language model, could outperform the current state-of-the-art open-world object detectors by a large margin, e.g., the absolute open-set error (the number of unknown instances that are wrongly labeled as known) is reduced from 7832 to 2546, exhibiting the inherent superiority of semantic topology on open-world object detection.

authors:
Ankan Bansal
Karan Sikka
Gaurav Sharma
Rama Chellappa
Ajay Divakaran

title: Zero-shot object detection

authors:
Abhijit Bendale
Terrance E Boult

title: Towards open set deep networks

venue: In CVPR,

authors:
Zhaowei Cai
Nuno Vasconcelos

title: Cascade R-CNN: Delving into high quality object detection

authors:
Nicolas Carion
Francisco Massa
Gabriel Synnaeve
Nicolas Usunier
Alexander Kirillov
Sergey Zagoruyko

title: End-to-End object detection with transformers

venue: In ECCV,

authors:
Arslan Chaudhry
Marc’Aurelio Ranzato
Marcus Rohrbach
Mohamed Elhoseiny

title: Efficient lifelong learning with a-gem

venue: arXiv preprint arXiv:1812.00420,

authors:
Karan Desai
Justin Johnson

title: Virtex: Learning visual representations from textual annotations

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: BERT: pre-training of deep bidirectional transformers for language understanding

venue: In NAACL-HLT,

authors:
Akshay Dhamija
Manuel Gunther
Jonathan Ventura
Terrance Boult

title: The overlooked elephant of object detection: Open set

venue: In WACV,

authors:
Akshay Raj Dhamija
Manuel Günther
Jonathan Ventura
Terrance E. Boult

authors:
Kaiwen Duan
Song Bai
Lingxi Xie
Honggang Qi
Qingming Huang
Qi Tian

title: CenterNet: Keypoint triplets for object detection

authors:
Mark Everingham
Luc. Van Gool
Christopher K.I. Williams
John Winn
Andrew Zisserman

title: The pascal visual object classes (VOC) challenge

authors:
Pedro Felzenszwalb
Ross Girshick
David McAllester
Deva Ramanan

title: Object detection with discriminatively trained part based models

authors:
Andrea Frome
Greg Corrado
Jonathon Shlens
Samy Bengio
Jeffrey Dean
Marc’Aurelio Ranzato
Tomas Mikolov

title: Devise: A deep visual-semantic embedding model

title: Fast R-CNN

venue: In ICCV,

authors:
Ross Girshick
Jeff Donahue
Trevor Darrell
Jitendra Malik

title: Rich feature hierarchies for accurate object detection and semantic segmentation

title: Artificial general intelligence: Concept, state of the art, and future prospects

venue: J. Artif. Gen. Intell.,

authors:
Xiuye Gu
Tsung-Yi Lin
Weicheng Kuo
Yin Cui

title: Zero-shot detection via vision and language knowledge distillation

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Borui Jiang
Ruixuan Luo
Jiayuan Mao
Tete Xiao
Yuning Jiang

title: Acquisition of localization confidence for accurate object detection

authors:
K J Joseph
Salman Khan
Fahad Shahbaz Khan
Vineeth N Balasubramanian

title: Towards open world object detection

authors:
KJ Joseph
Vineeth N Balasubramanian

title: Meta-consolidation for continual learning

venue: arXiv preprint arXiv:2010.00352,

authors:
Armand Joulin
Laurens Van Der Maaten
Allan Jabri
Nicolas Vasilache

title: Learning visual features from large weakly supervised data

venue: In European Conference on Computer Vision,

authors:
Ang Li
Allan Jabri
Armand Joulin
Laurens van der Maaten

title: Learning visual n-grams from web data

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Zhizhong Li
Derek Hoiem

title: Learning without forgetting, 2017

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C. Lawrence Zitnick

title: Microsoft COCO: Common objects in context

authors:
Tsung-Yi Lin
Priya Goyal
Ross Girshick
Kaiming He
Piotr Dollar

title: Focal loss for dense object detection

authors:
Wei Liu
Dragomir Anguelov
Dumitru Erhan
Christian Szegedy
Scott Reed
Cheng-Yang Fu
Alexander C. Berg

title: SSD: Single shot multibox detector

authors:
Weitang Liu
Xiaoyun Wang
John Owens
Yixuan Li

title: Energy-based out-of-distribution detection

venue: NeurIPS,

authors:
Weiyang Liu
Yandong Wen
Zhiding Yu
Meng Yang

title: Large-margin softmax loss for convolutional neural networks

venue: In ICML,

authors:
Ziwei Liu
Zhongqi Miao
Xiaohang Zhan
Jiayun Wang
Boqing Gong
Stella X Yu

title: Large-scale long-tailed recognition in an open world

title: Why?: What makes us curious

authors:
David Lopez-Paz
Marc’Aurelio Ranzato

title: Gradient episodic memory for continual learning

title: Wisdom and the context of knowledge: Knowing that one doesn’t know

venue: On the development of developmental psychology,

authors:
Dimity Miller
Lachlan Nicholson
Feras Dayoub
Niko Sünderhauf

title: Dropout sampling for robust object detection in open-set conditions

venue: In ICRA,

authors:
Dimity Miller
Niko Sünderhauf
Michael Milford
Feras Dayoub

title: Uncertainty for identifying open-set errors in visual object detection, 2021

authors:
Can Peng
Kun Zhao
Brian C. Lovell

title: Faster ILOD: incremental learning for object detectors based on faster RCNN

authors:
Alec Radford
Jong Wook Kim
Chris Hallacy
Aditya Ramesh
Gabriel Goh
Sandhini Agarwal
Girish Sastry
Amanda Askell
Pamela Mishkin
Jack Clark
Gretchen Krueger
Ilya Sutskever

title: Learning transferable visual models from natural language supervision. 2021a

venue: arXiv preprint arXiv:2103.00020,

authors:
Jathushan Rajasegaran
Salman Khan
Munawar Hayat
Fahad Shahbaz Khan
Mubarak Shah

title: itaml: An incremental task-agnostic meta-learning approach

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H. Lampert

title: icarl: Incremental classifier and representation learning, 2017

authors:
Joseph Redmon
Ali Farhadi

title: YOLOv3: An incremental improvement

venue: arXiv preprint arXiv:1804.02767,

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

title: You only look once: Unified, real-time object detection

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster R-CNN: Towards real-time object detection with region proposal networks

authors:
Konstantin Shmelkov
Cordelia Schmid
Karteek Alahari

title: Incremental learning of object detectors without catastrophic forgetting

authors:
Peize Sun
Yi Jiang
Enze Xie
Zehuan Yuan
Changhu Wang
Ping Luo

title: Onenet: Towards end-to-end one-stage object detection

venue: arXiv preprint arXiv:2012.05780,

authors:
Peize Sun
Rufeng Zhang
Yi Jiang
Tao Kong
Chenfeng Xu
Wei Zhan
Masayoshi Tomizuka
Lei Li
Zehuan Yuan
Changhu Wang
Ping Luo

title: Sparse r-cnn: End-to-end object detection with learnable proposals

venue: arXiv preprint arXiv:2011.12450,

authors:
Mingxing Tan
Ruoming Pang
Quoc V. Le

title: EfficientDet: Scalable and efficient object detection

authors:
Zhi Tian
Chunhua Shen
Hao Chen
Tong He

title: FCOS: Fully convolutional one-stage object detection

authors:
Yue Wu
Yinpeng Chen
Lijuan Wang
Yuancheng Ye
Zicheng Liu
Yandong Guo
Yun Fu

title: Large scale incremental learning

authors:
Yongqin Xian
Bernt Schiele
Zeynep Akata

title: Zero-shot learning - the good, the bad and the ugly

authors:
Shuo Yang
Wei Yu
Ying Zheng
Hongxun Yao
Tao Mei

title: Adaptive semantic-visual tree for hierarchical embeddings

venue: ACM MM,

authors:
Shuo Yang
Lu Liu
Min Xu

title: Free lunch for few-shot learning: Distribution calibration

venue: In ICLR,

authors:
Shuo Yang
Min Xu
Haozhe Xie
Stuart Perry
Jiahao Xia

title: Single-view 3d object reconstruction from shape priors in memory

authors:
Alireza Zareian
Kevin Dela Rosa
Derek Hao Hu
Shih-Fu Chang

title: Open-vocabulary object detection using captions

authors:
Hongkai Zhang
Hong Chang
Bingpeng Ma
Shiguang Shan
Xilin Chen

title: Cascade RetinaNet: Maintaining consistency for single-stage object detection

venue: In BMVC,

authors:
Xiaosong Zhang
Fang Wan
Chang Liu
Rongrong Ji
Qixiang Ye

title: FreeAnchor: Learning to match anchors for visual object detection

authors:
Xingyi Zhou
Dequan Wang
Philipp Krähenbühl

title: Objects as points

venue: arXiv preprint arXiv:1904.07850,

authors:
Xingyi Zhou
Jiacheng Zhuo
Philipp Krahenbuhl

title: Bottom-up object detection by grouping extreme and center points

heading: 1 INTRODUCTION

text:
Object detection, which aims at localizing and classifying objects in a given scene (Felzenszwalb et al., 2010; Everingham et al., 2010; Lin et al., 2014), is one of the most iconic abilities of biological intelligence. It was introduced to the artificial intelligence field to endow an intelligence agent with the ability of scene understanding. Although significant advances have been made to improve the object detection system in recent years (Girshick et al., 2014; Ren et al., 2015; Cai & Vasconcelos, 2018; Sun et al., 2020b; Redmon et al., 2016; Lin et al., 2017; Tian et al., 2019; Zhou et al., 2019a; Carion et al., 2020; Sun et al., 2020a), a strong assumption that all the objects of interest have been annotated in the training set, i.e., close-set learning, is always made but not holds well. All unknown objects are treated as background and ignored by current detectors, making such detectors cannot handle corner cases in many real-world applications such as autonomous driving, where some obstacles are not available during training, but must be detected when intelligent cars are running on the road. However, creating a large-scale dataset that contains annotations for all objects of interest at once is extremely expensive, even impossible.
Superior to current detectors, humans naturally have the ability to discover both known and unknown objects and gradually learn novel concepts motivated by their curiosity. Learning by discovering the unknown is crucial for human intelligence (Livio, 2017; Meacham, 1983), and has been considered as a key step to achieve artificial general intelligence (AGI) (Goertzel, 2014). Recently, a new object detection paradigm, named Open-World Object Detection, has been established (Joseph et al., 2021; Miller et al., 2021; 2018c; Liu et al., 2020) to mimic this learning procedure.
A qualified open-world object detector can not only identify known objects, but also discover object instances of unknown categories and gradually learn to recognize them when their annotations
∗corresponding author
progressively arrive. The learning of novel categories is always in an incremental fashion, where the detector cannot access all old data when training on new categories. This open-world learning setting is much more realistic but challenging than previous close-set object detection.
The open-world object detection poses two challenges on current detectors, i.e., recognition of unknown categories and incremental learning. On the one hand, previous close-set detectors do not explicitly encourage intra-class compactness (Liu et al., 2016b; Yang et al., 2021b). However, compact feature representation is highly required for unknown object recognition (discovery). If the known categories occupy most of the feature space, the detector will probably classify the unknown object as one of the known categories. On the other hand, the vanilla training strategy of the object detector lacks the mechanism to prevent ‘catastrophic forgetting’ in incremental learning (Joseph et al., 2021; Shmelkov et al., 2017a; Peng et al., 2020), i.e., previously-known objects features are severely distorted when learning new categories. Consequently, training on novel categories weakens the detector’s ability to detect previously-known objects.
Previous works have made efforts to endow the object detector with the capacity of unknown recognition and incremental learning. One of the representative works, ORE (Joseph et al., 2021), designs a clustering loss function to compact the object features, and involves an energy-based outof-distribution identification approach (Liu et al., 2020) to detect unknown objects. Combining these two independent technologies in a step-wise manner makes ORE a non-end-to-end framework. Such solutions for open-world object detection are far from the optimal status. Additionally, ORE (Joseph et al., 2021) doesn’t guarantee a feature space topology consistency, which is crucial for effective new class learning and avoidance of catastrophic forgetting, as shown in Figure 1.
This paper formalizes unknown recognition and incremental learning in a unified perspective and proposes a much simpler but more effective framework for open-world object detection than prior arts. We propose that an open-world object detector is desired to learn a feature space with such characteristics, including (a) discriminativeness: the unknown objects and the objects of new categories couldn’t be overlapped with any previously-known categories in the feature space, and (b) consistency: the feature topology of previously-known categories couldn’t be distorted severely when
learning new categories. Our key idea is to pre-define a unique and fixed centroid in feature space for each category, including the ‘unknown’ category, and to push object instances close to their belonging centroids during the life-long learning of an open-world object detector. The pre-defined centroids are named as ‘Semantic Anchors’, and all semantic anchors constitute the structure of ‘Semantic Topology’. As shown in Figure 2, all features are binded to their corresponding semantic anchors to satisfy the discriminativeness, previously-known objects feature topology is maintained when incrementally learning new categories to satisfy the consistency.
We introduce an off-the-shelf pre-trained language model to set up the semantic topology. The semantic anchor for each category is derived from the language model by embedding the corresponding category name. By incrementally registering new semantic anchors when new classes are involved, the semantic topology gradually grows. In the experiments, we show that by combining a current detector with our proposed semantic anchor head, a huge improvement in open-world object detection performance across the board is achieved. In addition to the consistent mAP improvement over the whole life of the detector, the ability of unknown recognition of our proposed method outperforms the current state-of-the-art methods by a large margin, e.g., the absolute open-set error is reduced by 2/3, from 7832 to 2546.
More importantly, we conduct a comparison experiment by randomly generating semantic anchors instead of leveraging language models. Although randomly-generated anchors do not provide semantic priors, their performance still surpasses state-of-the-art methods. This strongly proves that the topology consistency is the most key characteristic for open-world learning while introducing semantic relationships can further boost the performance.

heading: 2 RELATED WORKS

text:
Object detection
Modern object detection frameworks (Ren et al., 2015; Redmon et al., 2016; Liu et al., 2016a; Lin et al., 2017; Zhang et al., 2019a; Redmon et al., 2016; Redmon & Farhadi, 2018; Girshick, 2015; Duan et al., 2019; Tian et al., 2019; Tan et al., 2020; Zhou et al., 2019b; Jiang et al., 2018; Zhang et al., 2019b; Carion et al., 2020; Sun et al., 2020b) take advantage of the high-capacity representation in deep neural networks to localize and classify the target class object in given images and videos. These well-established detectors can achieve excellent performance in the close-set dataset such as PascalVOC (Everingham et al., 2010), MSCOCO (Lin et al., 2014). However, the detectors can
not handle open-world object detection, which is more common in the real world. To this end, ORE (Joseph et al., 2021) raises and formalizes the open-world object detection problem.
Class incremental learning Class incremental learning aims to learn a classifier incrementally to recognize all encountered classes met so far, including previously-known classes and novel classes. Knowledge distillation is commonly adopted to mitigate forgetting old classes, which stores some old class exemplars to fine-tune the model or compute the distillation loss. iCaRL (Rebuffi et al., 2017) maintains an ‘episodic memory’ of the exemplars and incrementally adds novel class examples into the memory. Then the nearest neighbor classifier can be obtained incrementally. LwF (Li & Hoiem, 2017) proposes a modified cross-entropy loss to preserve the knowledge in the previous task. BiC (Wu et al., 2019) points out the data imbalance between old classes and new classes causes the network’s prediction biased towards new classes. However, the existing class incremental methods cannot handle the open-world problem, where the classifier should identify those ‘unknown’ classes and incrementally learns to recognize them, but existing methods would recognize unknown objects as background.
Open-set Learning In open-set learning, the knowledge contained in the training set is incomplete, i.e., the examples encountered during inference may belong to a category that does not appear in the training set. OpenMax (Bendale & Boult, 2016) uses a Weibull distribution to identify unknown instances in the feature space of deep networks. OLTR (Liu et al., 2019) proposes to tackle the open-set recognition problem in a data imbalance setting by deep metric learning. Besides the open-set classification, Dhamija et al. (Dhamija et al., 2020b) found that the object detectors exhibit a high error rate that misclassifies unknown classes to known classes with high confidence. To solve this problem, many works (Miller et al., 2021; 2018a; Dhamija et al., 2020b) aims to measure the uncertainty of the detectors’ outputs to reject open-set error. Miller et al. (Miller et al., 2018a) uses Monte Carlo Dropout sampling to estimate the uncertainty in an SSD detector. After that, Miller et al. proposes to model a Gaussian Mixture distribution for each class in the detector’s feature space to reject unknown classes. ORE (Joseph et al., 2021) uses an energy-based out-of-distribution recognition method (Liu et al., 2020) to distinguish the known and unknown. However, such method needs to compute the energy score distribution among all instances, including known and unknown, during evaluation, making ORE a non-end-to-end method. We formulate the open-set recognition problem and the class incremental learning into a unified framework. Different from (Joseph et al., 2021), our method doesn’t access any unknown instances but achieves much superior performance.
Zero-shot Learning Aligning image and text into a common feature space has always been an active research topic (Frome et al., 2013; Joulin et al., 2016; Li et al., 2017; Desai & Johnson, 2021; Yang et al., 2019; 2021a), especially in zero-shot learning (Xian et al., 2017; Bansal et al., 2018; Zareian et al., 2021; Gu et al., 2021). Many researches in zero-shot learning leverage the information in language models to assist zero-shot image classification (Xian et al., 2017) or zero-shot object detection (Bansal et al., 2018; Zareian et al., 2021; Gu et al., 2021). However, this paper tackles a different problem and has a different usage of language models. We identify that a consistent feature manifold topology plays an essential role in open-world object detection, and the language model is used for generating growth-able and consistent semantic topology to constrain the feature space learning of an open-world detection. Also, this paper is the first one to incorporate a language model, e.g., CLIP, to assist open-world object detection, which results in a simple training framework and strong empirical performance.

heading: 3 METHODOLOGY

text: In this section, we introduce the Open World Object Detection problem definition in Section 3.1, the method overview in Section 3.2, and the details of the proposed method in Section 3.3 and Section 3.4.

heading: 3.1 PROBLEM DEFINITION

text:
An open world object detector should detect all the previously seen object classes, and can also identify if a testing instance known or unknown (belongs to previously seen classes or not). If unknown, the detector should gradually learn the unknown classes when their annotations progressively arrive without retraining from scratch. Formally, at each time point t, we assume there exists a set of known object classes Ctkn = {l1, l2, . . . , lC} and a set of unknown object classes Ctunk = {lC+1, lC+2, . . . }. The detector Dt at the time point t has only trained on classes in Ctkn while may encounter all classes
including Ctkn and Ctukn during evaluation. Besides correctly classifying an object instance from the known classes Ctkn, the detector Dt should also label all instances from the unknown class set Ctukn as unknown. At the time point t+ 1, the unknown instances will be forwarded to a human user who can select n novel classes of interest to annotate and return them back to the model. The detector Dt should incrementally learn these n novel classes and updates itself to Dt+1 without retraining from scratch on the whole dataset. The known class set Ct+1kn in the time point t+ 1 is also updated to Ct+1kn = Ctkn + {lC+1, . . . , lC+n}. The data instances in the known classes Ckn are assumed to be labeled in the form of {x, y}, where x indicates the image and y indicates the annotations including class label l and object coordinates, i.e., y = [l, x, y, w, h] where x, y, w, h denote the bounding box center coordinates, width and height respectively.

heading: 3.2 METHOD OVERVIEW

text: A Region Proposal Network (RPN) that can identify unknown and a discriminative and consistent feature space are two critical components for an open world detector. Here, we adopt the UnknownAware RPN proposed in (Joseph et al., 2021) and propose to constrain the detector’s feature space topology with a pre-defined Semantic Topology. Specifically, we create a unique and fixed centroid for each category in the feature space, named semantic anchor. The semantic anchors for all classes are derived by feeding forward their class names into a pre-trained language model. Our key idea is to manipulate the detector’s feature space to be consistent with the semantic topology constituted by semantic anchors during the whole life of the detector. Due to the feature dimension discrepancy, a fully connected layer (semantic projector) is used to align the dimension between RoI features and semantic anchors. At the training stage, the semantic features outputted by the semantic projector are forced to cluster around their corresponding semantic anchors by a designed ‘SA (semantic anchor) Head’. When incremental learning, the SA Head gradually registers new semantic anchors for novel classes and continually pulls close the novel class features and their semantic anchors. To mitigate ‘catastrophic forgetting’ caused by old class feature distortion, the SA Head also minimizes the distance between some stored old class exemplars and their semantic anchors when learning novel classes. To better leverage the well-constructed feature space, we attach an additional classification layer to classify the semantic features. Figure 3 shows the training pipeline of the proposed openworld object detector. At inference, we multiply the class posterior probabilities produced by the two classification heads and get the final prediction.

heading: 3.3 UNKNOWN-AWARE RPN

text: Open-world object detectors are required to separate potential unknown objects from the background. Therefore, we need some specific designs for the Region Proposal Network (RPN). In this paper, we adopt the unknown-ware RPN proposed in (Joseph et al., 2021) which selects the top-k background region proposals, sorted by its objectness scores, as unknown objects. The unknown-aware RPN relies on the fact that Region Proposal Network is class agnostic. Given an input image, the RPN generates bounding box predictions for foreground and background instances, along with the corresponding objectness scores. The unknown-aware RPN labels those proposals with a high objectness score but do not overlap with any ground-truth object as a potential unknown object.

heading: 3.4 SEMANTIC TOPOLOGY

text: We propose to pre-define a semantic topology for detectors’ feature space rather than learn from data. The semantic topology is constituted by semantic anchors. Each semantic anchor is a pre-defined feature centroid for an object class. The semantic anchors can be generated by embedding corresponding class names using a pre-trained language model. The semantic topology can dynamically grow as novel classes are introduced to the open-world detector.

heading: 3.4.1 SEMANTIC ANCHOR REGISTRATION

text:
We generate semantic anchors for all classes by feeding the class names into an off-the-shelf pretrained language model. Denote li ∈ Ctkn as class name of the i-th known class at time t andM as an off-the-shelf pre-trained language model. The semantic anchor for class li is defined as Ai =M(li), where Ai ∈ Rn, the dimension n depends on the pre-trained language model. The semantic anchor registration is performed repeatedly as long as known class set update Ctkn → C t+1 kn when novel classes are introduced at time t+ 1. Note we also register a semantic anchor for all instances labeled
as unknown by the unknown-aware RPN to better distinguish the unknown instances from the known instances. Follows the same strategy, the semantic anchor for class unknown is also generated by the word embedding of unknown text.

heading: 3.4.2 OBJECTIVE FUNCTION

text:
The RoI features f ∈ Rd are feature vectors generated by an intermediate layer of the object detector, which are used for category classification and bounding box regression. We manipulate the RoI features f to construct the detector’s feature manifold topology. Denote fi as an RoI feature of the i-th known class, we first align the dimension of fi as the dimension of its corresponding semantic anchor Ai, using a fully connected layer with d × n dimensional weights. The corresponding semantic feature is denoted as f̂i ∈ Rn. We constrain the detector’s feature manifold topology by clustering the semantic features around their corresponding semantic anchors, the learning objective is formalized as Lsa = ‖f̂i −Ai‖. (1) Minimizing this loss would ensure the desired feature space topology. To better leverage the constructed feature space, we use an additional classification head to classify the semantic features f̂i, with the same label space as RoI classification head. The total training objective is the combination of semantic anchor loss Lsa, semantic feature classification loss Lclsse , RoI feature classification loss and bounding box regression loss:
Ltotal = Lsa + Lclsse + Lclsroi + Lreg. (2)
At the inference stage, the classification results are computed by multiplying the two class posterior probability vectors predicted by the RoI feature classification head and the semantic feature classification head.

heading: 3.4.3 TOPOLOGY STABILIZATION

text: To store the detection ability on old classes, a balanced set of exemplars are stored and used to fine-tune the model after each incremental learning session as in the previous open-world object detection approach (Joseph et al., 2021). However, we argue that finetuning the detector ignoring the old knowledge topology as in (Joseph et al., 2021) still suffers from the severe ‘catastrophic forgetting’ problem. Benefitting from pre-defining the feature space topology, our method can guarantee a consistent feature space during the finetuning stage. The stored old class and new class instances are still forced to cluster around their pre-defined centroids to guarantee the feature space topology unchanged.

heading: 4 EXPERIMENTS

text: We introduce the evaluation protocol, including datasets and evaluation metrics, implementation details, and experimental results in this section.

heading: 4.1 DATASETS

text: Following (Joseph et al., 2021), the open-world detector is evaluated on all 80 object classes from Pascal VOC (Everingham et al., 2010) (20 classes) and MS-COCO (Lin et al., 2014) (20+60 classes). All categories are grouped into a set of tasks T = {T1, . . . , Tt, . . . }, where all categories of Tt will be introduced to the detector at a time point t. At the time point t, all categories from {Tτ |τ <= t} will be treated as known and {Tτ |τ > t} would be treated as unknown. As in (Joseph et al., 2021), T1 consists of all VOC classes, and the remaining 60 classes from MS-COCO are grouped into three successive tasks with semantic drifts. The open-world object detector is trained on the training set of all classes from Pascal VOC and MS-COCO, and evaluated on the Pascal VOC test split and MS-COCO val split. The validation set consists of 1k images from the training data of each task.

heading: 4.2 EVALUATION METRICS

text:
We introduce three metrics to evaluate the detection performance of an open-world object detector on known classes and unknown classes at each time point:
• Mean Average Precision (mAP) (Everingham et al., 2010; Lin et al., 2014). Following previous works (Joseph et al., 2021), we use mAP at IoU threshold of 0.5 to measure the performance on known classes. Since the object classes are continually involved, mAP is calculated on previouslyknown classes and currently-known classes.
• Absolute Open-Set Error (A-OSE) (Joseph et al., 2021; Miller et al., 2018b). A-OSE counts the absolute number of unknown instances that are wrongly classified as any of the known classes. A-OSE evaluates the detector’s ability to avoid misclassifying unknown instances as one of the known classes.
• Wilderness Impact (WI) (Joseph et al., 2021; Dhamija et al., 2020a). The definition is WI = PK PK∪U
− 1, where PK is the precision of the detector when evaluated on known classes and PK∪U refers to the precision when evaluated on all classes including known and unknown. The recall level R is set to be 0.8. WI evaluates the detector’s ability to successfully detect unknown objects and classify them as ’unknown’ class.

heading: 4.3 IMPLEMENTATION DETAILS

text:
We extend the traditional Faster R-CNN (Ren et al., 2015) object detector with a ResNet-50 (He et al., 2016) to be an open-world object detector. The RoI feature is extracted from the last residual block in the RoI head, which has a 2048 dimension. The 2048-dim RoI feature is used for computing traditional bounding box regression loss and classification loss as the same as in many previous works (Joseph et al., 2021; Ren et al., 2015). The semantic projector is a fully-connected layer to align the dimension of RoI features with the semantic anchors. The dimension of semantic anchors depends on the choice of pre-trained language model, e.g., the semantic anchor is 512-dim when using CLIP text encoder (Radford et al., 2021b) to embed categories names. The semantic feature outputted by the semantic projector is used for calculating semantic anchor loss Lsa and semantic feature classification Lclsse loss. The Lsa and the Lclsse are added to the standard regression loss and RoI classification loss to jointly optimize the detector. For the topology stabilization, we store 100 instances per class as the same as in (Joseph et al., 2021). To enable the classifier to handle a variable number of classes at different time points, we assume there exists a maximum number of classes to be added and set the classification logits of unseen classes to a large negative value to make their contribution to softmax output negligible, following (Joseph & Balasubramanian, 2020; Rajasegaran et al., 2020; Lopez-Paz & Ranzato, 2017; Chaudhry et al., 2018).
To make a fair comparison, we report experimental results obtained by re-running the ORE (Joseph et al., 2021) official code1. All the hyper-parameters and optimizers are also controlled to be exactly the same for all methods.

heading: 4.4 OPEN-WORLD OBJECT DETECTION

text:
Table 1 shows the open-world object detection performance of our proposed method and other baselines. At task 1, all methods are trained over all 20 Pascal-VOC classes. Twenty novel object classes are introduced gradually at the following task. WI and A-OSE are used to quantify how unknown instances are confused with known class objects after training on each task. WI and A-OSE are both the less the better. ORE (Joseph et al., 2021) used an extra clustering loss to separate class features, and an energy-based unknown identifier that learns shifted Weibull distributions from
1Official repository: https://github.com/JosephKJ/OWOD
ORE (T1) ORE (T4) Ours (T1) Ours (T4)
all class data (including known and unknown) in the validation set to reject open-set error. Our method doesn’t access any unknown data instances from the validation set and achieves much superior performance on WI and A-OSE than Faster R-CNN and ORE. In task 3, our proposed method achieves 1/3 A-OSE compared to ORE (2120 v.s. 6900) and 1/4 A-OSE compared to Faster R-CNN (2120 v.s. 9622). Our method also reduces the Wilderness Impact (WI) by a large margin than baselines. This indicates our method has a much better ability on unknown detection. Furthermore, our method also achieves consistent mAP improvement over the whole life of the detector. At incremental learning session (task 2,3,4), the performance of Faster R-CNN on old classes deteriorate severely (55.35 → 6.09). Faster R-CNN + Finetuning, ORE, and our method store some old class instances and fine-tune on them after learning new classes to restore the old class performance. However, the Faster R-CNN + Finetuning and ORE don’t guarantee the feature manifold topology consistent. The superior performance on old classes also proves that guaranteeing the feature manifold topology is critical.

heading: 4.5 INCREMENTAL OBJECT DETECTION

text: To verify the effectiveness of our proposed method, we also conduct experiments on class incremental object detection (iOD), where the detectors only need to continually recognize novel object classes without unknown identification. We use the standard iOD evaluation protocol as (Joseph et al., 2021; Shmelkov et al., 2017b) to evaluate all methods, where group of classes (10, 5, and the last class) from PASCAL VOC 2007 (Everingham et al., 2010) are incrementally learned by a detector trained on the remaining set of classes. Benefits from the well-constructed feature space using semantic anchors, our proposed method performs favorably well on the incremental object detection (iOD) task against several state-of-the-art 2. Notably, our method exhibits strong ability to incrementally learn new classes while not forget old classes. This is because our detector’s feature space is constrained to be incrementally growth-able by assigning each object class a unique feature space location.

heading: 4.6 ABLATION STUDY

text:
The effect of language model. We derive semantic topology from pre-trained language models. To explore the effect of the choice of semantic topology, we conduct ablation studies in this section. To be specific, we generate semantic anchors using two pre-trained language models, i.e., CLIPtext (Radford et al., 2021a) and BERT (Devlin et al., 2019). The dimensions of semantic anchor generated by CLIP-text and BERT are 512 and 768, respectively. The comparison results are shown in
Table 3. These two language models obtain similar results, which both outperform ORE, the previous state-of-the-art method in open-world object detection. To further explore the importance of semantic priors, we also generate semantic anchors by randomly and uniformly sampling, which means we assume the total number of classes is known which is not applicable in practice. Surprisingly, our experiment shows that semantic anchors as random vectors still surpass state-of-the-art methods. This demonstrates that a consistent topology, even without semantic priors, could also largely benefit the task of open-world object detection, which strongly proves that the discriminative and the consistent are two key characteristics for open-world learning. However, the randomly assigned class centers would hinder the learning ability of networks. Instead, a pretrained language model can perfectly overcome these problem.
The effect of semantic anchor loss. In this section, we explore the importance of unknown class anchor, semantic anchor clustering loss Lsa, semantic anchor classification loss Lclsse and the RoI feature classification loss Lclsroi . The experiments in Table 4 shows the semantic anchor clustering loss and the semantic anchor classification loss are both indispensable in identifying unknown objects.

heading: 5 CONCLUSION

text: Open world object detection raises two challenging problems on current detectors, unknown recognition and incremental learning. Different from previous methods which combine domain-dependent technologies to respectively solve these two problems, our work provides a unified perspective, i.e.semantic topology. In the framework of semantic topology, all object instances from the same category, including ‘unknown’ category, are assigned to their corresponding pre-defined centroids. Therefore, a discriminative and consistent feature representations are ensured during the whole life of an open-world object detector. Aided with our proposed semantic topology, a huge improvement in open-world object detection performance across the board is achieved.

heading: 6 ACKNOWLEDGEMENT

text: Ping Luo was supported by the General Research Fund of HK No.27208720 and the HKU-TCL Joint Research Center for Artificial Intelligence.


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.

summaries: 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.

summaries: 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).

summaries: 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.

authors:
J.T. Ash
C. Zhang
A. Krishnamurthy
J. Langford
A. Agarwal

title: Deep batch active learning by diverse, uncertain gradient lower bounds

authors:
V. Badrinarayanan
F. Galasso
R. Cipolla

title: Label propagation in video sequences

venue: In CVPR,

authors:
J. Bien
R. Tibshirani

title: Prototype selection for interpretable classification

venue: The Annals of Applied Statistics,

authors:
V. Birodkar
H. Mobahi
S. Bengio

title: Semantic redundancies in image-classification datasets: The 10% you don’t need, 2019

authors:
A. Borodin
A. Jain
H.C. Lee
Y. Ye

title: Max-sum diversification, monotone submodular functions, and dynamic updates

venue: ACM Trans. Algorithms,

title: Incorporating diversity in active learning with support vector machines

authors:
J. Carbonell
J. Goldstein

title: The use of mmr, diversity-based reranking for reordering documents and producing summaries

venue: SIGIR ’98,

authors:
L. Chen
G. Zhang
H.Zhou

title: Fast greedy map inference for determinantal point process to improve recommendation diversity

venue: In NeurIPS,

authors:
C. Coleman
C. Yeh
S. Mussmann
B. Mirzasoleiman
P. Bailis
P. Liang
J. Leskovec
M. Zaharia

title: Selection via proxy: Efficient data selection for deep learning, 2020

authors:
Y. Cui
M. Jia
T.Y. Lin
Y. Song
S. Belongie

title: Class-balanced loss based on effective number of samples

authors:
Abhimanyu Das
David Kempe

title: Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection

venue: Journal of Machine Learning Research,

authors:
S. Dasgupta
D.J. Hsu
C. Monteleoni

title: A general agnostic active learning algorithm

authors:
J Devlin
M.W. Chang
K. Lee
K. Toutanova

title: BERT: pre-training of deep bidirectional transformers for language understanding

title: Sequential facility location: Approximate submodularity and greedy algorithm

authors:
G.F. Elsayed
D. Krishnan
H. Mobahi
K. Regan
S. Bengio

title: Large margin deep networks for classification

venue: In NIPS,

authors:
M.L. Fisher
G.L. Nemhauser
L.A. Wolsey

title: An analysis of approximations for maximizing submodular set functions-ii

venue: In Polyhedral Combinatorics. Mathematical Programming Studies,

authors:
Amirata Ghorbani
James Zou
Andre Esteva

title: Data shapley valuation for efficient batch active learning, 2021

authors:
R. Gilad-Bachrach
A. Navot
N. Tishby

title: Query by committee made real

authors:
D. Golovin
A. Krause

title: Adaptive submodularity: Theory and applications in active learning and stochastic optimization

venue: J. Artif. Int. Res.,

authors:
Daniel Golovin
Andreas Krause

authors:
R. Guo
P. Sun
E. Lindgren
Q. Geng
D. Simcha
F. Chern
S. Kumar

title: Accelerating large-scale inference with anisotropic vector quantization

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

authors:
G. Hinton
L. Deng
G.E. Dahl
A. Mohamed
N. Jaitly
A. Senior
V. Vanhoucke
P. Nguyen
T. Sainath
B. Kingsbury

title: Deep neural networks for acoustic modeling in speech recognition

venue: IEEE Signal Processing Magazine,

authors:
A. Holub
P. Perona
M.C. Burl

title: Entropy-based active learning for object recognition

venue: In CVPR Workshop,

authors:
K J Joseph
Vamshi Teja R
Krishnakant Singh
Vineeth N Balasubramanian

title: Submodular batch selection for training deep neural networks, 2019

authors:
A.J. Joshi
F. Porikli
N. Papanikolopoulos

title: Multi-class active learning for image classification

authors:
L. Kaufman
P.J. Rousseeuw

title: Clustering by means of medoids

authors:
V. Kaushal
R. Iyer
S. Kothawade
R. Mahadev
K. Doctor
G Ramakrishnan

title: Learning from less data: A unified data subset selection and active learning framework for computer vision, 2019

authors:
V. Kaushal
S. Kothawade
G. Ramakrishnan
J.A. Bilmes
R.K. Iyer

title: PRISM: A unified framework of parameterized submodular information measures for targeted data subset selection and summarization

authors:
B. Kim
R. Khanna
O. Koyejo

title: Examples are not enough, learn to criticize! criticism for interpretability

authors:
Kwan-Young Kim
Dongwon Park
Kwang In Kim
Se Young Chun

title: Task-aware variational adversarial active learning

authors:
P. Kohli
M.P. Kumar
P.H.S. Torr

title: beyond: Solving energies with higher order cliques

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
V. Kolmogorov
R. Zabin

title: What energy functions can be minimized via graph cuts

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
S. Kothawade
N. Beck
K. Killamsetty R.K. Iyer

title: SIMILAR: submodular information measures based active learning in realistic scenarios

authors:
A. Krizhevsky
I. Sutskever
G.E. Hinton

title: Imagenet classification with deep convolutional neural networks

title: Learning multiple layers of features from tiny images

authors:
Miroslav Kubat
Stan Matwin

title: Addressing the curse of imbalanced training sets: One-sided selection

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
D.D. Lewis
W.A. Gale

title: A sequential algorithm for training text classifiers

venue: In SIGIR,

authors:
H. Lin
J. Bilmes

title: A class of submodular functions for document summarization

venue: In ACL,

authors:
Douglas Lundholm
Lars Svensson

title: Clifford algebra, geometric algebra, and applications

authors:
Z. Mariet
J. Robinson
J. Smith
S. Sra
S. Jegelka

title: Optimal batch variance with second-order marginals

venue: In ICML Workshop,

authors:
Aditya Krishna Menon
Sadeep Jayasumana
Ankit Singh Rawat
Himanshu Jain
Andreas Veit
Sanjiv Kumar

title: Long-tail learning via logit adjustment, 2020

authors:
G.L. Nemhauser
L.A. Wolsey
M.L. Fisher

title: An analysis of the approximations for maximizing submodular set functions

venue: Mathematical Programming,

title: Matroid Theory

authors:
H.S. Park
C.H. Jun

title: A simple and fast algorithm for k-medoids clustering

venue: Expert Systems with Applications,

authors:
A. Prasad
S. Jegelka
D. Batra

title: Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets

authors:
Chao Qian
Jing-Cheng Shi
Yang Yu
Ke Tang
Zhi-Hua Zhou

title: Subset selection under noise

venue: Advances in Neural Information Processing Systems,

authors:
S. Ramalingam
C. Russell
L. Ladicky
P.H.S. Torr

title: Efficient minimization of higher order submodular functions using monotonic boolean functions

venue: Discrete Applied Mathematics,

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

title: Imagenet large scale visual recognition

authors:
T. Scheffer
C. Decomain
S. Wrobel

title: Active hidden markov models for information extraction

venue: In Advances in Intelligent Data Analysis,

authors:
Ozan Sener
Silvio Savarese

title: Active learning for convolutional neural networks: A core-set approach

venue: In ICML, 2018

title: Active learning literature survey

venue: Technical report, University of Wisconsin-Madison,

authors:
H.S. Seung
M. Opper
H. Sompolinsky

title: Query by committee

venue: In COLT,

authors:
Changjian Shui
Fan Zhou
Christian Gagn’e
Boyu Wang

title: Deep active learning: Unified and principled method for query and training

venue: In AISTATS,

authors:
I. Simon
N. Snavely
S.M. Seitz

title: Scene summarization for online image collections

venue: In ICCV,

authors:
E. Strubell
A. Ganesh
A. McCallum

title: Energy and policy considerations for deep learning in NLP

authors:
I. Sutskever
O. Vinyals
Q.V. Le

title: Sequence to sequence learning with neural networks

authors:
C. Szegedy
W. Liu
Y. Jia
P. Sermanet
S. Reed
D. Anguelov
D. Erhan
V. Vanhoucke
A. Rabinovich

title: Going deeper with convolutions

authors:
S. Tong
D. Koller

title: Support vector machine active learning with applications to text classification

title: Trikalinos. Class imbalance, redux

venue: In Proc. ICDM,

authors:
Z. Wang
J. Ye

title: Querying discriminative and representative samples for batch mode active learning

venue: ACM Trans. Knowl. Discov. Data,

authors:
K. Wei
R. Iyer
J. Bilmes

title: Submodularity in data subset selection and active learning

title: Facility location: Concepts, models, algorithms and case studies. series: Contributions to management science

title: Diverse mini-batch active learning

authors:
Yuxun Zhou
Costas J. Spanos

title: Causal meets submodular: Subset selection with directed information

venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,

heading: 1 INTRODUCTION

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).

heading: 2 RELATED WORK

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.

heading: 3 PROBLEM STATEMENT

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.

heading: 4 BACKGROUND

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).

heading: 5 SUBSET SELECTION

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.

heading: 5.1 BALANCING CONSTRAINTS

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.

heading: 5.2 GREEDY ALGORITHM

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 ).

heading: 5.3 COMPUTATIONAL COMPLEXITY

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.

heading: 6 EXPERIMENTS

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.

heading: 7 DISCUSSION

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.

heading: A APPENDIX

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.