Active Learning via Classifier Impact and Greedy Selection for Interactive Image Retrieval
Authors: Leah Bar
Boaz Lerner
Nir Darshan
Rami Ben-Ari
Venue: Accepted by TMLR ()

Abstract: Active Learning (AL) is a user-interactive approach aimed at reducing annotation costs by selecting the most crucial examples to label. Although AL has been extensively studied for image classification tasks, the specific scenario of interactive image retrieval has received relatively little attention. This scenario presents unique characteristics, including an open-set and class-imbalanced binary classification, starting with very few labeled samples. We introduce a novel batch-mode Active Learning framework named GAL (Greedy Active Learning) that better copes with this application. It incorporates new acquisition functions for sample selection that measure the impact of each unlabeled sample on the classifier. We further embed this strategy in a greedy selection approach, better exploiting the samples within each batch. We evaluate our framework with both linear (SVM) and non-linear MLP/Gaussian Process classifiers. For the Gaussian Process case, we show a theoretical guarantee on the greedy approximation. Finally, we assess our performance for the interactive content-based image retrieval task on several benchmarks and demonstrate its superiority over existing approaches and common baselines. Code is available at
https://github.com/barleah/GreedyAL.

Published in Transactions on Machine Learning Research (12/2024)
Active Learning via Classifier Impact and Greedy Selection for Interactive Image Retrieval
Leah Bar
Barleah.libro@@gme com
Department of Applied Mathematics Avi- Universily, Isruel
Boaz Lerner
boozl@originai.co
OriginAI, Ramat-Gary Israel
Nir Darshan
nir@originai.co co
OriginAl, Samaat-aan Israel
Rami Brn-Ari
ramab mami@@oriiini..oo
OriginAI, Ramat-Gar Israel
Reviewed on OpenReview: https: // opereevee.. net/ net/ forum? id- b68Q0enPly
Abstract
Active Learning (AL) is user-interactive approach aimed at reducing annotation costs by selecting the most erucial examples to label. Although AL has been extensively stud- ied for image classification tasks, the specific scenario of interactive image retrieval has received relatively little attention. This scenario presents unique characteristics, including an open-set and class-imbalan insalanebl binary classification, starting with very few labeled sam- ples. We introduce novel batch-mode Active Learning framework named GAL (Groedy Active Learning) that better copes with this application. It incorporates new acquisition functions for sample selection that measure the impact of each unlabeled sample on the classifier. We further embed this strategy in a greedy selection approach, better exploit- ing the samples within cach batch. We evaluate our framework with both lincar (SVM) and non-linear MLP/ M.a//aussian Process classifiers. For the Gaussian Process case, we show theoretical guarantee on the greedy approximation. Finally, we assess our performance for the interactive content-based image retrieval task several benchmarks and demon- strate its superiority over existing approaches and common baselines. Code is available at https://gi thtb. com/barleah/Creedyyae
1 Introduction
Annotated datasets are in high demand for many machine learning applications today. Active Learning (AL) aims to select the most valuable samples for annotation, which, when labeled and integrated into the training process, can significantly enhance performance
the target task (e.g. a classifier). Tn recent years, task- specific AI has gained popularity across various domains, including multi-class image classification Parvanch al. (2022); Emam al. (2021), few-shot learning Ayyad et al. (2021); Pezeshkpour et al. (2020), pose estimation Gong et al. (2022), person re- re-identiffcation Liu et al. (2019), object detection Wu et al. (2022), and interactive Content-Based Image Retrieval (CBIR) Barz & Denzler (2021); Gosselin & Cord (2008); Mehra et al. (2018); Ngo et al. (2016).
Image retrieval is a long-standing challenge in computer vision, crucial for data mining within large image collections and with applications fields such as c-commerce, social modia, and digital asset management. An interactive image retrieval system learns which images the database belong a user's query concept, by analyzing the example images and feedback provided by the user. The challenge is to retrieve the

---

Published in Transactions on Machine Learning Research (12/2024)
Labeled
unlabeled
candidates
Labeled
C₂
budget
Top K
Ci+1(0)
Xu
A
Oracle
(2) U.U.B.
Active Learning
Figure 1: Main flow of the AL cycle. The top-K candidate set at cycle determined by the classifier Ce(#), can be selected as the pool from the mnlabeled/seardo corpus. The AL. module extracts a batch set X, which is sent for annotation by a user (oracle) that generates the label set Vb. Based on the extended training set, a new classifier (+) trained for the next cycle.
relevant images with minimal user interaction Qazanfari al. (2017); Putzu et al. (2020); Banerjee et al. (2018); Roli et al. (2004); Lerner et al. (2023). This process involves iterative feedback, where users provide relevance feedback on set of images suggested by the model, which is then used to retrain the retrieval model, refining search results over time. Content-Based Image Retrieval (CBIR) relies on visual content for retrieval. In Interactive Image Retrieval (IIR) within CBIR, the search process usually begins with a small set user-provided query images (typically 1-5), which results in limited data for training an effective retricval model. Active learning techniques can then be applied through feedback rounds, to identify the most informative images, prompting the user to label them. The system then trains new retrieval model (typically classifier), guiding the search results toward the query concept. A general pipeline illustrating the AL process for IIR is shown in Fig. 1.
Active learning for image classification has traditionally been the focus of AL methods Karzand & Nowak (2020); Wang et al. (2022); Emam et al. (2021); Xie et al. (2021); Parvaneh et al. (2022); Kothawade et al. (2021); Citovsky et al. (2021), typically focusing on class-balanced, closed-set datasets and often starting with a relatively large number of labeled samples. More recent works address the challenge of starting the AL process with few labeled samples, known cold start. This issue is inherent in ITR use case, introducing challenge for selecting informative samples and train an effective retricval model. Some recent approaches address the cold start problem within the context of image classification Hacohen al. (2022); Yehuda et al. (2022). Others focus on issues like imbalance data Aggarwal et al. (2020); Kothawade et al. (2021) or rodundant examples Citovsky et al. (2021). However, these methods are generally not designed or tested for scenarios that combine multiple complexitiss, as seen in IIR, such as cold start, class imbalance, rare classes, and open-set setting.
Pose-based Active Learning is setting where the learner has access to a large pool of unlabeled data and can iteratively select samples from this pool for labeling. This is particularly useful when labeling is expensive, it allows the model to focus samples that are expected to provide the most information for improving performance. IIR naturally follows this strategy and operates within the framework of pool-based AL. In the context of pool-basee IIR, carly studies have used tuned SVMs with either engineered or deep features Gosselin & Cord (2008); Ngo et al. (2016); Rao et al. (2018); Tong & Chang (2001), leveraging the SVM's strong regularization for small training sets. For instance, Tong & Chang (2001) employed kernel SVM for binary classification.
AL in (content-based) interactive image retrieval has been used to improve retrieval performance, allowing users to find target images with minimal interactions. The system selects critical samples from a pool of unlabeled images, prompting the user to label them as relevant or irrelevant. These labels are then used to train more accurate retrieval model, iteratively refining its understanding user intent. In CBIR, the AL process typically follows a pool- approach Manjunath al. (2000), where the learner accesses pool of unlabeled data and requests labels for specific instances. This leads to binary classification task characterized by imbalanced classes and open-set scenario (where categories in the search domain are
2

---

Published in Transactions on Machine Learning Research (12/2024)
often unknown). The negative class includes irrelevant images from diverse classes, making the classification asymmetric. Batch Mode AL (BMAT.) Karzand & Nowak (2020); Tong & Koller (2001) selects batch of images at each iteration for user feedback, but traditional AL methods for standard image classification can struggle in this sctting due to model instability and unrelialee uncertainty cstimation Yuan et al. (2020); Jin et al. (2022); Ning et al. (2022).
Active Learning strategies aim to evaluate and select unlabeled samples to improve an objective metric, such classification accuracy or, in our case, retrieval performance. Common criteria for selection include uncertainty Brinker (2003); Sener & Savarese (2018). Uncertainty-based selection focuses on samples near the decision boundary to refine it, but it often overlooks the broader data distribution. Morcover, accurately measuring uncertainty requires sufficient number of labeled samples, which is often lacking, especially in the early cycles of Interactive Image Retrieval (IIR). In this context, many methods that begin with a cold start-having very few labeled samples- tend to be inefficient and may underperform compared to basic random selection processes Hacohen et al. (2022); Ychuda et al. (2022); Chandra et al. (2021). On the other hand, diversity-based selection aims to represent the entire data distribution, but it can introduce redundant selections include less informative samples that are far from the decision boundary, offering minimal improvement to the classifier. Recent studies have shown that hybrid approach, which integrates both uncertainty and diversity, can leverage the advantages of each strategy to yield better results Agarwal et al. (2020); Wang et al. (2016); Yang et al. (2015).
In this work, we introduce a novel hybrid AL algorithu specifically designed for Interactive Image Retrieval (IIR). IIR can be framed as a binary classification task with several unique characteristies: (i) Open-set: The number of classes and their categories in the pool are unknown. (ii) Imbalance: Often, less than 1% of the pool contains the query concept (positive class). (iii) Asymmetric sets; The positive set contains a single semantic class, while the negative set can include diverse samples from various categories. (iv) Cold start: Only a few labeled samples are available at each cycle, particularly in the initial and critical cycles. To address these challengos, we propose a Batch Mode Active Learning (BMAL) method for IIR that effectively handles the cold start in an open-set scenario. Our approach introduces acquisition functions that evaluate the global impact of potential samples on the decision boundary for both linear and non-linear classifiers. For SVM and MLP classifiers we evaluate the influence of each possible label (positive or negative), while for Gaussian Processes, Additionally, to cope with the scarcity of labeled samples, we introduce a greedy scheme that optimally exploits each sample in the subsequent selection of each batch. This method effectively combines both uncertainty and diversity, as demonstrated in Section 4, providing a robust solution to challenges in IIR. To summaarize, we present an innovative approach to Batch Mode Active Learning (BMAL) for IIR tasks with the following contributions:
aim to minimize the overall uncertainty of the classifier during sample selection.
1. We propose new acquisition functions that quantify the impact value on the classifier as a selection strategy, tailored to both linear and non-linear classifiers. Our framework is adaptable to different classifiers, where, for instance, the impact value can measure the global shift in the decision boundary or the level of global uncertainty of the classifier.
2. We propose novel greedy scheme to cope with very few labeled samples, focusing on only one class and operating in open-set regime with highly imbalanced classes.
3. For the Gaussian Process-based classifier, establish a lower bound on the performance of the greedy algorithm using the (1 1/ee)-Aproxiimation Theorem.
4. We present a more realistic lubti-label benchmark for the Content-Based Image Retrieval (CBIR) task, named FSOD, where the query concept involves an object within the input image.
5. We evaluate our framework using three classification methods (linear and non-linear) on four diverse datasets, showcasing superior results compared to previous methods and strong baselines.
2 Related Work
Two main characteristics drive the design of AL. methods, namely diversity and uncertainly.
3

---

Published in Transactions on Machine Learning Research (12/2024)
Few works address the batch (budget) size of the selected samples at each cycle of the AL procedure and the cold-start scenario. Recent studies such as Hacohen et al. (2022); Yehuda et al. (2022) have investigated the influence of budget size on active learning strategies and have also addressed the challenge of cold start, where the initial labeled training set is small Hacohen et al. (2022); Ychuda et al. (2022); Yuan et al. (2020); Gao et al. (2020). In the context of cold start, poor results are attributed to the inaccuracy of trained classifiers capturing uncertainty, a problem that becomes more pronounced with small labeled training sets Nguyen al. (2015); Gal & Ghahramani (2016). Some recent methods, address issues such as class imbalance, rare classes, and redundancy, e.g. in SIMILAR Kothawade et al. (2021). A different category of methods, utilize large batch sizes, aiming to reduce the number of training runs required to update heavy Deep Neural Networks (DNNs). For instance, Margter Citovsky et al. (2021) addresses the presence of redundant examples within a batch.
The literature suggests only few works for AL in the domain of IIR Barz et al. (2018); Gosselin & Cord (2008); Mchra et al. (2018); Ngo et al. (2016); Rao et al. (2018); Zhang ct al. (2002). In this respect, Gossolin & Cord (2008) proposed RETIN, a method that incorporates boundary correction to improve the representation of the database ranking objective in CBIR. In Ngo et al. (2016), the authors introduced an SVM- M-s-eaddd Batch Mode Active Learning approach that breaks down the problem into two stages. First, an SVM is trained to filter the images in the database. Then, a ranking function is computed to select the most informative samples, considering both the scores of the SVM function and the similarity metric between the ideal query and the images in the database. A more recent work by Rao et al. (2018) addresses the challenges related to the insufficiency of the training set and limited feedback information in each relevance feedback iteration. They begin with an initial SVM classifier for image retrieval and propose a feature subspace partition based a pscudo-labcling strategy
Zhang et al. (2002) proposed a method based on multiple instance learning and Fisher information, where they consider the most ambiguous picture as the most valuable one and utilize pseudo-labeling. In con- trast, Mchra et al. (2018) adopt a semi-supervised approach for the retrioval model, using the unlabeled data in the pool, for training their retrieval classifier. As for AL, they employ an uncertainly sampling strategy that selects the label of the point nearest to the decision boundary of the classifier, based on an adaptive thresholding hcuristic. However, as argue, uncertainty measures can often be unreliable during cold start, which may limit the effectiveness of this approach. Furthermore, to enhance their results, they incorporate semantic information extracted from WordNet, requiring additional textual input from the user. In comparison, Barz et al. (2018) proposes an AL method called ITAL that aims to maximize the mutual information (MI) between the expected user feodback and the relevance model. They utilize a non-lincar Gaussian process as the classifier for retrieval.
Kapoor et al. (2007) introduced an AL technique employing Gaussian processes for object categorization. In each cycle, the method selects a single point-specifieally, an unlabeled point characterized by the highest uncertainty in classification. This uncertainty is assessed by taking into account both the minimum posterior mean (closest to the boundary) and the maximum posterior variance. Zhao et al. (2021) introduced an efficient Bayesian active learning method for Gaussian Process classification. In this procedure, one sample is chosen in each cycle. In our method, however, we select a batch of samples by minimizing the overall uncertainty. Additionally, our approach does not rely on knowledge about the distribution of the negative set, which can be highly multimodal due to the presence of various class types.
Several studies have employed hybrid approach that combines uncertainty and diversity measures Ash et al. (2020); Yang et al. (2015); Karzand & Nowak (2020); Agarwal et al. (2020); Cardoso et al. (2017); Wang et al. (2016). For instance, the BADGE model Ash et al. (2020) is an active learning strategy that uses KMeans++ to create diverse batches, integrating model uncertainty and diversity without requiring hand- tuned hyperparameters similar to our approach. The CDAL method Agarwal et al. (2020) incorporates spatial context into active detection, selecting diverse samples based on distances to the labeled set and applying this diversity measure within core-set framework. The CEAL method Wang et al. (2016) proposes Cost-Effective Active Learning by selecting uncertain samples using three common methods: least confidence, margin sampling, and entropy. USDM Yang et al. (2015) introduces multi-class active learning strategy that explicitly optimizes for uncertainty sampling and diversity maximization, with diversity used as a regularizer. This approach evaluates uncertainty through a generated graph, which limits scalability. Despite their hybrid
4

---

Published in Transactions on Machine Learning Research (12/2024)
nature, these methods are often designed for specific tasks and conditions such as multi-class, balanced, and closed set scenarios Agarwal et al. (2020); Yang et al. (2015); Ash et al. (2020) may not be suited for cold start situations Wang et al. (2016); Ash et al. (2020) or scalable applications Yang et al. (2015) such as those existing in IIR.
Other methods such as MaxMin-based operators focus on the classifier parameters Tong & Koller (2001); Karzand & Nowak (2020). However, these methods are applied single sample budget, which is associated with increased computation time and user burden due to frequent interactions. Our work is closely related to the MaxiMin algorithm Karzand & Nowak (2020). Nonetheless, we extend and generalize this idea by introducing flexible framework that can be adapted to different classifiers and accommodate larger batch size. This is achieved through novel acquisition functions within the proposed greedy method. Ranked mad Active Learning (RBMAL) Cardoso et al. (2017) takes a different hybrid approach constructing a batches by adding samples with high uncertainty and low maximum similarity to any other already selected sample. We further compare our method to two hybrid methods of MaxiMin Karzand & Nowak (2020) and Ranked batch-mode AL (RBMAL) Cardoso et. al. (2017).
3 Algorithm Overview and Motivation
This section presents the motivation and key features of our Greedy Active Learning (GAL) algorithm. In the context of a cold start scenario, where the labeled dataset is exceptionally limited, the active learning procedure becomes notably more challenging. The complexity arises from the inability to rely on the classifier to estimate the label or uncertainty of a candidate data point. This scenario is a common challenge in active learning in general Hacohen et al. (2022) and AL-IIR in particular. Additionally, in AL-IIR, there is the open-set classification challenge, involving dealing with unknown classcs. The proposed GAL algorithm addresses these challenges through two key aspects: (i) A greedy method that optimally exploits the few labeled samples available and gradually expands the training set within the batch cycle. (ii) Formulating acquisition functions that prioritize data points with the most significant impact on reshaping the decision boundary or the global uncertainty measure. These acquisition functions facilitate improved selection of relevant samples as well as hard-irrelevant (i.e., hard-negative) points that may belong to different unknown categories. Therefore, we depart from the common hypothesis that relies on parameters estimated from a weak classifier (e.g., uncertainty or direct prediction), shifting instead to an approach that focuses on the impact of individual samples on the classifier. This approach is better suited to AL for a binary classifier with few positives and unknown open-set negatives.
In GAL, the samples in the batch are chosen greedily, aiming to maximize an acquisition function that reflects the change in the decision boundary in a MaxMin paradigm. To assess this change, one may require the truc labels of the candidate set, which are unavailable in practice. The method therefore calculates a pseudo-label, I, by measuring the change in the decision boundary, for both positive and negative options of each candidate sample. A false label is likely to lead to a larger change in the decision boundary. This is not desirable for the selection, as the importance of the point might be spurious. The true label, though, leads to smoother and more moderate behavior. This minimal shift, serving as an approximation for the true label, is treated as a pseudo-label. Subsequently, we mazimize these minimal shifts across the candidates. Figure 2 illustrates with a 2D toy example using an imbalanced dataset with Gaussian distributions in IR?, the rationale behind our pseudo-labeling approach. Positive (relevant) and negative (irrelevant) samples are represented by blue and red colors, respectively. The current training set is depicted in bold, with candidate points shown in a lighter shade. In this scenario, there is one labeled relevant point and 13 labeled irrelevant points. The black dashed line indicates the classifier trained with the whole dataset. Let the dashed green line represent the current boundary (based on the training set). Now, let's select candidate point (depicted in green). If we designate it positive and calculate the new boundary, we obtain the blue line; whereas if we designate it as nogative, we get the red linc. It's important to note that the true label (blue) results in a classifier that is closer to the original dashed green line. Therefore, selecting the label that minimiizss the boundary shift approximates the true label. For each candidate point, we determine the pseudo- label and calculate an acquisition function. The optimal point x* the one that maximizes this function, resulting in a score which we refer to as an impact value. Our algorithm then proceeds to find the next optimal sample. Subsequently, x² and I are added to the labeled set. The process repeats to select the next sample until
5

---

Published in Transactions on Machine Learning Research (12/2024)
2.00
cissifier with all data
classifier before selection
1.75
pseudo
pseudo label 1
1.50
1.25
1.00
0.75
0.50
0.25
-1.0
-0.5
0.0
0.5
1.0
3.5
2.0
Figure 2: Label proxy demonstration: The points are sampled from two Gaussian distributions, demonstrat- ing the change in the decision boundary for two label options. Red and blue denote negative and positive labels, respectively. Bold and light. points represent train and candidate samples, respectively, with their corresponding labels. The green dashed line represents the classifier based solely on the train set (bold circles). The blue and red lines signify the resulting classifier if the selected point (green circle) is labeled as blue or red. The blue classifier exhibits a lower deviation from the dashed green line, consistent with the true label (blue).
designated budget B is reached. This budget is then allocated for annotation in the next cycle, during which the pseudo-labels are discarded.
We now illustrate the behaviour of various traditional selection strtegiess, on our loy example in Fig. 3. This toy example demonstrates binary classification in the presence of an imbalanced dataset and a cold-start scenario (consisting of one tagged relevant point and 13 irrelevant points). For each case, we display the current linear classifier (SVM) as color dashed line and the updated classifier (color solid line) according to different AL selection strategies. For the sake of comparison, we present upper-bound (in terms of the size of the dataset used for training) of classifier trained all the samples with the true labels (dashed black). As observed, random selection achieves a reasonable improvement from the current classifier to the updated version after using the selected points for training. This result is achieved despite ignoring both uncortainty and diversity principles (sec also Hacohen et al. (2022)). Kmeans+ based solcly on diversity, selecting points well spread over the dataset. The uncertainty approach (highest Entropy). however, selects points near the current and an inaccurate boundary, caused by the extreme cold-start. Both Kmeans++ and Entropy methods yield an improvement expected.
However, our greedy method demonstrates the most significant enhancement in narrowing the gap towards the upper-bound classifier. In Fig. 3d, we showcase that our hybrid approach inherently incorporates both uncertainty and diversity. The selection sequence ranges from in to is, with io-i2 and i4 chosen far from the green dashed classifier margin and comply with the diversity principle. On the other hand, two points (is and ig) were selected within the classifier margin, tending to comply with the uncertainty principle. Note that, in contrast to Kmcans++ and Random, our approach avoids selecting any irrelevant samples due an abundance of labeled negatives in the current. training set. The combination of our novel acquisition function and greedy approach yields conditioned diversity, where the diversity depends the train-set distribution, better coping with the scarcity of labeled samples and the diversity of categories within the dataset.
We further demonstrate this crucial aspect quantitatively in Table 1, where we assess uncertainty, diversity, and accuracy errors. evident that Kmcans+ exhibits the highest diversity score, while Entropy demonstrates the highest uncertainty score. GAL, on the other hand, showeases intermediate values and the lowest. accuracy error. These metrics confirm that GAL suggests adaptive strategy that integrates

---

Published in Transactions on Machine Learning Research (12/2024)
Uncertainty
Diversity
||0 - fatt
Random
0.82
0.54
1.22
Kmeans++
0.86
0.78
0.98
Entropy
0.99
0.24
0.71
SVM-GAL (ours)
0.96
0.52
0.29
Table 1: Quantitative comparison of diversity versus uncertainty characteristics for various methods with an SVM classifier Uncertainty represents the mean entropy of the selected points, while diversity denotes the mean pairwise distances among the selected points. The third column indicates the distance wetween the resulting and the best classifier, where lower values are preferable. Note that GAL achieves a superior balance between uncertainty and diversity factors, effectively addressing both criteria.
both uncertainty and diversity, Throughout the greedy procedure, each subsequent sample is chosen to maximize the impact score, based on the psoudo-labels from the previons samples the batch. This method avoids choosing samples that have already been selected, as selecting a similar point would not maximize the impact value. Consequently, we achieve the diversity property. Conversely, at certain configurations, the most significant change in the decision boundary is induced by the samples in the classifier margin, specifically those near the boundary with high level of uncertainty. We also provide analysis of the cold start performance in Appendix A.
4 Algorithm Description
We follow the common strategy in few-shot learning where features are a-priori learned on a. large la- beled corpus (e.g. ImageNet). We then follow the assumption where all the images in the dataset are represented by feature vectors I; E Rd, (where d is the feature dimension) either engineered or coming from pretrained network. In this paper we derive our image features from pre-trained backbone. Tet X₂ (2,, ...,...,,mm mm) denote the set of unlabeled image features (representing the scarched dataset), and X = (m+t,, .., x1)+) the labeled set. Relevant (positive) and irrelevwnd (negalive) samples are labeled by Y E (+1,-1) respectively, and the label set is denoted by 3/. The initial labeled set X which defines the query concept, consists few (usually 1-3) query image features labeled by +1. In the course of the iterative process, the user receives an unlabeled batch set X, C X₂ of size B = |.%,, and is asked to label the relevant. (y = +1) and irrelevant (y = images. The AL procedure selects the set of B samples, such that when labeled and added to the training set, aims reach the maximum retrieval performance.
In this work, suggest greedy-based framework which consists of two phases at each AL cycle. Let C, be the classifier at cycle t. In the first phase, a candidate subset X, C X₁ of size K := K&el is selected out of the unlabeled pool. This set can be either the whole unlabeled dataset or a subset which is determined by the top-K relevance probabilities. The candidate set X, accommodates mostly irrelevant samples due to the natural data imbalance. In the second phase, the algorithm extracts a batch set. X, C X. by an AT. procedure. user (oracle) annotates the images selected in X, and adds their features and labels into the labeled set (1). Based on the new training set, a classifier C.4.1 is trained for the next cycle, illustrated in Fig. 1.
The selection process aims to choose samples that are most effective when labeled, meaning they maximize the improvement in classifier performance. At each greedy step, an impact value is computed for each unlabeled sample using an acquisition function, which evaluates the sample's contribution to enhancing the classifier. The sample with the highest impact value then added to X, as described in Algorithm We now demonstrate the GAL framework in three settings: linear (SVM) and non-linear (MLP and Gaussian Process) classifiers via the greedy approach.

---

Published in Transactions on Machine Learning Research (12/2024)
Diversity:
dassfer with data
dasotteer with al data
dazäfier before selection
dassilier before selection
1.75
dasöitee after selection
1.75
classifer ofter selection
letteed points
selected
1.50
1,50
125
1.25
-0.5
0.0
0.5
1.0
1.5
-0.
0.0
0.5
1.0
15
(a)
(b)
Uncertainty: Entropy
GAL
dosafler
dasafteer
desilie selection
claailler ore selection chssttter after selection
dassifer after selection
welccted points
selected points
1.50
1.50
125
1.25
1.00
1.00
3.75
-0.5
0.0
1.0 155
-05
0.0
0.5
1.0
(c)
(d)
Figure 3: In 2D Gaussian toy example, we illustrate binary class scenario characterized by imbalanced distribution of data, showcasing red samples representing irrelevant data and blue samples representing rele- vant data. We compare three fundamental selection strategies (a) Random, (b) Pure diversity (Kmeans++)) and (c) Pure uncertainty (maximal entropy) to (d), the suggested GAL method. Initially, one relevant and irrelevant samples are labeled. The initial SVM classifier is illustrated by a colored dashed line, followed by the corresponding solid line after updating the classifier with the addition of six samples (B 6). The dashed black line represents an "upper-bound", where the classifier is trained with all the data and their true labels. Notice the most significant improvement observed in the classifier with our GAL method, closing the gap toward the upper-bound and demonstrating a selection pattern that effectively combines diversity and uncertainty. The order of selection in GAL is depicted in (d) by iu to is, with corresponding impact scores of 1.75, 1.02, 0.80, 1. 1.06, 0.59, and 0.66. Note that although i3 and is are close, they are on opposite sides of the classifier and close to the boundary. This means they have significant uncertainty measures and therefore a substantial impact on the decision boundary.
4.1 Sample-wise Impact Value
Linear Classifier SVM: Let start with linear classification such as SVM. We define the outcome of a trained binary classifier C' parameterized by 0, the measure for the relevance of sample to query image. Effective or prominent samples are those that apply the most influcnce on the classifier's decision boundary. These sample points play a significant. role in the aclive learning process, shaping the classifier's evolution across iterative cycles. However, two primary challenges emerge with this approach: (i) When dealing with a scarch space that may encompass millions or even more samples, computational efficiency becomes critical concern. (ii) Due the scarcity of labels, shallow classifier such as SVM linear classifier favored Tong & Chang (2001); Gosselin & Cord (2008); Ngo al. (2016); Rao et al. (2018). Additionally, SVM has

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm Greedy Active Learning (GAL) Algorithm
function GAT((e, B)
Xs +0 for i + 1 to B do
x*, + NEXT(X,, N1)
D Find the point that maximizes the impact value S
X U 3/ U X. - N. x²
t + X (2*} end for return X end function
function NEXT (2,, M1) for i <- to [tc do
I; 4 Xe[i]
1 (z X1 by Algorithm 2
Acquisition function
end for 8' - arg max; S₁
return 14-,4-- 14- end function
Return the optimal point and its corresponding pseudo label
(1)
C(07
(M.
Classifier training
F;
S
min 1E(-1,+1)
C(0,7
(A)
Classifier training
[x -1)
Figure 4: To caleulate the score for point т; in the candidate set, we train classifier C(0:*) ) by assuming the sample is positíve. Similarly, train another classifier C(0T) with negative label. The impact value S; is then determined the minimum value obtained by applying function F to both options (4).
strong regularizer to avoid an overfit. Such a classifier also enables relatively rapid training durations. It's important to mention that single-layer feod-forward neural network (NN) can also be utilized, as is equivalent to Logistic Regression and is expected produce outcomes similar to those of SVM. However, the use of multi-layer perceptron (MLP) for classification carries the risk of overfitting due to the limited size of the training dataset, and potentially resulting in increased computational overhead during the search procedure. We therefore test MLP in the context of AL model (sce Sec. 5.2.3). Furthermore, we restrict our examination to samples within the candidate set, denoted as x E X,, which is notably smaller than the entire dataset. Regarding the second issue, given the absence of true labels, we employ pseudo labels. The core principle of our proposod algorithm is rooted in the MaxMin paradigm, where we aim to MAXimize the MINimal shift in the decision boundary. This minimal shift serves an approximation for the true label and is thus treated as pseudo label.
Let assume that z; has label 4, and 04 represents the parameters of classifier if the point æ; is included in the training set with label 4, One possible impact value could be the quantification of the decision boundary's change when 2; is added to the training set. Let Wa E Rd define the initial SVM hyperplane of the AL cycle, and W E ddd the hyperplane which was obtained with an additional candidate point 2; with label I, We then define an acquisition function as
Fsom (Wi Woll3-
(1)
9

---

Published in Transactions on Machine Learning Research (12/2024)
Note that theoretically, there are two unknowns involved in this process. The label, and the most effective point x² given the label. Ideally, if the labels of the candidate points were known, then
r argmax Fuu (I,,,4 0%:). 2,EX,
(2)
and 1" is the label of the optimal point. This selection is conditioned on the sample label which is unavailable in practice. We therefore suggest to estimate the label by the minimizer of Fsom such that
:= argmin Faom Faum(14,4 8%:.
(3)
4E(-1,+1)
We refer to 4 as pseudo-label. The acquisition function is therefore defined as
: = (Iz 1, 04)
min Fsom (Zi, 6%)). 4e(-1,1)
(4)
The index the selected point is then given by the largest value among the candidate points,
argmax St. 2x...2..../x.
(5)
where
S min Feom (1,, 24, 8¹.. 4
(6)
This selection procedure, referred to as NEXT, which utilizes the SVM acquisition function, is detailed in Algorithm 1, the first function in Algorithm 2 and illustrated in Fig. 4.
We will now consider a network that comprises layers, using a non-linear activation function (ReLUU. The classifier is trained using the cross-entropy loss function. As in the linear case, the acquisition function measures the extent of the change the decision boundary. The AL algorithm remains identical to Algorithm 2, with the only change of replacement of Fsum with Fmlpp
Nonlinear Classifter - MLP:
Fmip (v,,, 4)) Voll.
(7)
where V is vector of concatenated and flattened network weights. Specifically, To defines the initial MLP weights at the current active learning cycle, and (( i)) the weight vector as if the network was trained with x; and label 4,
Algorithm 2 Acquisition Functions
function ( (I1, Xi Di)
SVM
0+ + Classifier(2) X2 U nz, +1)
0- + Classifier XG U UIi 31 -1)
1 +- argmini,e(-1,4
(wi, 04) by (1) and (6)
S; + Fsom (,,,,,,0000
return S
end function
function (2i Xi, Jhi
D. Gaussian Process
S, F Xi) by (13)
return S,, Null
end function
4.1.1 Greedy Approach
The ultimate objective of the AL procedure extract batch consisting of B samples. Ideally, the optimal solution would search for all the permutations of positive and negative labels of the candidate set
10

---

Published in Transactions on Machine Learning Research (12/2024)
i0
0
0io
i1
i2
++
0 10
10.41
40.
13
i4
à5
26
Figure 5: In the SVM scenario, the GAL algorithm employs a binary tree structure. The initial point 2ío is chosen through the NEXT procedure NEXT, which are based on the corresponding pseudo-labels.
(Algeri (Algorithms 1). The red circles represent the results obtained from
such that. the impact value would be maximal. This is of course intractable. We therefore use the greedy active learning (GAL) approach which is illustrated in Fig. 5. In GAL, the sample zi, is initially selected by NEXT (Algorithms 1 and 2). We then insert its pseudo label into the train set, and calculate the next optimal point Ft,, In this illustration, lo +1 associated with the left child of the tree root. At the third iteration f -1 and i4 selected. Samples io, i1, (marked by the red circles in Fig. 5) are then inserted into the budget set Nr This procedure continues recursively until the budget. B is reached, described in Algorithm 1.
The selection sequence is demonstrated in Fig. 3d. The factors of uncertainty and diversity can drive to different selections. The uncertainty a by product of the MaxMin operator (5), (6). Points with high uncertainty (close to the boundary) will likely cause the maximum change in the separating hyperplane and therefore will be selected by (1) (sce i3 and i5 in Fig. 3d). As for diversity, selection of ncarby samples the embedding space (which are not close the boundary) are discouraged due to our approach. Note that whenever sample point is added to the labeled set, selection of a similar point will result in low impact value and will be discouraged due to the Max operation, promoting selection of distant points (see the global analysis in Table 1.)
Another theoretical aspect of the algorithm relies on the budget size B. The suggested algorithm is highly dependent on the pseudo label I, where the effectiveness the AL algorithm increases as the pseudo labels become more reliable. Let p be the probability for correct pseudo label. The normalized probability, denoted PN, of obtaining B accurate pseudo labels is given by
1 PN
Σ B
(8)
The normalized probability Pa is plotted in Fig. 6 for different B values and correct pseudo labels probabil- itics. It naturally suggests that a larger batch size is more sensitive to errors, while a smaller value of is preferred in each AL cycle. This reasoning will be demonstrated in the experimental results.
4.1.2 Complexity for SVM-Based GAL
Lastly, the complexity of training linear classifier such as SVM is approximately O(dr?), where n is the number of samples and is the feature dimension Chapelle (2007). Hence, the complexity of our algorithm cycle with K candidates and budget B given by
Complexity()) ((
(9)
11

---

Published in Transactions on Machine Learning Research (12/2024)
normalized mean correct vertices
1.0
B=1
B=3
0.8
B=7
0.6
0.4
0.2
0.0
0.0
0.4
1.0
Probability
Figure Theoretical results for the normalized probability of obtaining accurate pseudo-labels vs. the probability of correctly estimating one pscudo-label (see Eq. (8)).
4.2 Global Impact Value
Non-lincar Gaussian Process Classifier: Gaussian Processes (GP) Williams & Rasmuusen (2006) are generic supervised learning method designed to solve regression and probabilistic classification problems where the prediction interpolates the observations. Classification or regression by means of a GP, is a non- lincar and non-paramctric procedure that does not require iterative algorithms for updating. In addition, GP provides an estimate of the uncertainty for every test point, as illustrated Fig. 7. As can be seen, uncertainty (pink region) is significant as we get further away from the the train (black) points. A Gaussian process can be thought of as Gaussian distribution over functions f X R, where in our case f(x) represents the decision boundary. GP is fully specified by mean function μ X R and covariance function Σ X X + R (also known kernel function). The mean function represents the expected value of the function at any input point, while the covariance function determines the similarity between different input points. The Squared Exponential Kernel is defined as
K(x, x²) exp (- 1-22l 1-211===111 x'(1p)
(10)
Let := Xi be the train set of size L, and Xe the candidate is defines as (A) E L where every entry in the matrix is given by (10) for x, E A. Similarly, the train-test kernel matrix is defined as Σ1 E gLxK I E A,x' E Xe, and test kernel matrix is given by Enz E R x x, E Xe. Then, the mean function is expressed by
of size K. The training kernel matrix
MA = 2T (A)f(x),
(A)((x)) x = 12, E A,
and the covariance matrix is given by
Σ Exn Ez1 En (A)E
(11)
The variance point xf is given by the diagonal term
-
(12)
Equation (11) reflects the variance reduction of the test set due to the train set A. In setting, n (xx) and (I;) denote the decision boundary (red curve in Fig. 7), and uncertainty (pink area in Fig. 7) at point given the train set A. In the AL procedure, our goal is to identify samples that minimize the overall uncertainty. Now, At each AL cycle, if the current train set. is denoted by A, we define the acquisition function of a candidate point x; as the uncertainty area as x, was added into the train set,
Fop( == Σ
Euee (x) + a max 2 Auuz, (z) (
(13)
FEN.
X
12

---

Published in Transactions on Machine Learning Research (12/2024)
True
Predicted
Train points
20
fix)
-2
2
X
Figure 7: Gaussian Process: The true function is represented by a dashed blue line, while the prediction based on the training points is depicted by the red line. The uncertainty (std) of the prediction illustrated by the pink area, and the training points are denoted by black circles.
The first term describes the global extent of uncertainty across Xg in the integral average and is therefore insensitive to abrupt changes in the pointwise variation of oz On the other hand, the second term represents the Lx norm, [z0)(x))loo which is designed to manage potential points of discontinuity large deviations that we aim to minimize. Samples which maximize this function are considered informative'. Note that by (11), the uncertainty covariance does not depend on the labels of the training set,, avoiding the problem pseudo labeling. The aqcusition function for the GP is described in the second function in Algorithm
4.2.1 Theoretical Analysis
We now invostigate the conditions which guarantce a reasonable good approximation to the optimal batch selection. Nemhauser et al. (1978) established performance lower bound for a greedy algorithu when employed maximize a set function. Tet be a budget, X, a finite set and function F(AA with A C X. For the following maximization problem
A argmax F(A),
the greedy algorithm returns
F F(Agredy) 2 (1- F(A)).
under the following conditions:
F(A) 0.
2. F is non-negative and monotone, A C B implies F(4) < F(B).
F submodular if for all subsets S T C X, and all x E X'T, F(SUx)- F(S) 2
The submodularity property has the diminishing returns behavior: the gain of adding in a particular element x decrcases stays the same cach time another element added to the subset. By (11) and (12), the variance
The minus sign is used change the operator.
13

---

Published in Transactions on Machine Learning Research (12/2024)
at test point F; is given by The acquisition function given train batch A is then given by
(z+) Ee2li, d] (E2 (1))12))) [i,
(14)
F(A) =
Σ D
(x)) + + maxmmax ( =EX.
(15)
We now show that the conditions for the (1-11e) Approximapiooiiiiiinnn theorem are satisfied for (15).
The amount of variance reduction for every test point, 21 [ū, is guaranteed to be strictly positive due to the positive-defintte nature of the covariance matrix, which is an inherent property of GP modeling, and proved to be increasing monotone and submodular by Das & Kempe (2008). Based on the property that the class of submodular functions is closed under non-negative lincar combinations (Fujishige (2005)), (15) is submodular as well. Employing the same considerations implies that (15) exhibits monotonic increasing behavior. Consequently, acquisition function (15) satisfies the conditions of the (1 1/e)- Approximation theorem.
4.2.2 Complexity for Gaussian Process- Based GAL
Lastly, the complexity of a matrix of order n inversion is On²)) and two matrix multiplications in (14) are On K) and O(K²n). Hence for each AL cycle i with K candidates and budget B,
Complexity()) O BK (iB) + RiB)) ((BB)++(K())))))
(16)
5 Evaluation
Our evaluation includes comparison with ITAL, method based Mutual Information that has been shown to outperform numerous previous approaches. Moreover, we compare results with several well- established methods in active learning for classification tasks, such as COD, RBMAL, MaxiMin, as well as other strong baselines. We assess the GAL framework by employing three image retrieval lechniques, which utilize linear (SVM) and two non-linear (MLP, Gaussian Process) classifiers. The algorithm for SVM and MLP basod on the acquisition functions (1) and (7) respectively. In our evaluation, we compare our approach against various AL algorithms. (i) Random selection, (ii) Cyclic Output Discrepancy (COD) Huang et al. (2021), ) (iii) MaxiMin Karzand & Nowak (2020), (iv) Ranked batch-mode AL (RBMAL. Cardoso et al. (2017), and in the cases where B > 1, (v) Coreset Sener & Savarese (2018); Khakham (2019) and (vi) Kmeans++ Vassilvitskii & Arthur (2006). The COD Huang et al. (2021) method estimates the sample uncertainty by measuring the difference of model outputs between two consecutive active learning cycles,
Sood = =|C(r;; 02) C(1; 01-1)
(17)
where C(x) is the classifier prediction, 0g and 0 are its paramcter set in the current and previous active learning cycles, respectively. MaxiMin Karzand & Nowak (2020) algorithm maximizes the minimum norm of the classifier, dee. prioratizing smoother classifiers among the possible functions
SMaxiMin == min [I 1E(+1,-1)
(18)
[x) denotes the norm of interpolating function when training the classifier with positive and negative labels of x. In the linear SVM case, f(z) = [[ RBMAL method Cardoso et al. (2017) combines uncortainty and diversity by
SREMAL == a(1 6(x, mabelea)) + (1 a))(())
(19)
where @ is similarity measure, u(x) the uncertainty, and a | + &l). The batch set extracted by the above three methods, is obtained by selection of top-B score samples. Kmeans+ Vassilvitskii &
14

---

Published in Transactions on Machine Learning Research (12/2024)
Arthur (2006) and Coreset Khakham (2019); Sener & Savarese (2018) are diversity-based BMAL methods, and therefore applicable for B > 1. In Kmeans++; the batch samples are chosen as the closest points to each of the B centroids, and in Coreset, we ensure that the batch samples adequately represent the entire candidate pool based on the Lg norm distance.
In our third image retrieval approach, we incorporate a Gaussian Process (GP) technique, which was proposed in Barz et al. (2018) and referred to as ceenmaationThhhorete AL (TTAL). This method employs a selection strategy that aims to maximize the mutual information between the expected user feedback and the relevance model. To integrate the GP into our framework, we steer the active learning selection process towards data points that minimize the overall uncertainty of the GP classifier, as defined in (13).
5.1 Datasets
We evaluate GAL on wide range of scenarios including 4 datasets, representing image-level and object-level IIR. For instance-level retrieval, we used Paris-6K abbreviated as Paris, following the standard protocol as suggested in Radenović et al. (2018). This dataset contains 11 different monuments from Paris, plus 1M distractor images, from which we sampled a small subset, resulting in 9,994 images with 51-289 samples per- class and 8,204 distractors. Next, we built a benchmark based on Places365 Zhou et al. (2017), indicated as Places. It contains a larger lake size of 36,500 images with 365 different types of places such as 'restaurants', 'basements,, 'swimming pools' etc. Our Places dataset consists of the validation set of Places365. We used 30 classes queries (randomly sampled) with 100 samples per-class. Lastly, validated ourselves object- level retricval, a previously uncxplored task in CBIR-AL. To this end we built new benchmark from the FSOD dataset Fan et al. (2020), often used for few-shot object detection tasks, At this benchmark, images often include multiple objects (labels), therefore introducing a high challenge for a retrieval model. FSOD dataset is split into base and novel classes. We used the base set, for our benchmark. The base set contains 5. 2350 images with 800 objects categories where each object appears in 22-208 images. As our query pool, we randomly chose 30 object categories appearing in 50-200 images. We refer to this dataset as FSOD-IR and we intend to share the protocol publicly for future rescarch.
In all the above experiments, we used Resnet-50 backbone pre-trained on Imagenet-21K Ridnik el al. (2021). For the first iteration we used the top-K nearest neighbors by the cosine similarity. We used one query for Paris and Places benchmarks, and two queries for FSOD-IR (due to multiplicity of objects in images). We repeated the process for 5 random queries and calculated mAP at each AL cycle. For all these experimetns we used a pretrained ResNet50 features of 2048D.
To ensure fair comparison between our method and ITAL Barz et al. (2018) and Kapoor et al. (2007), we conducted our evaluation of the GAL framework on the identical dataset of MIRFLICKR-255 Huiskes & Lew (2008), which was also employed in ITAL. We followed the same protocol used in ITAL for consistency. This benchmark designed for retrieval consists of 25K images, with query images belonging to multiple categories. We further used the same feature extractor as ITAL (see Barz et al. (2018)). For all datasets we follow the same protocol: sample a query image from certain class, consider all images belonging to that class (or containing the same object in FSOD--IR) as relevant, while instances from different classes are considered irrelevant.
Our evaluation employs retrieval ranking results, typically measured by mean Average Precision (mAP) Barz et al. (2018); Rao et al. (2018); Mchra et al. (2018); Ngo et al. (2016). In all our experiments, we start with five different initial queries for each class and report mAP as the measure of retrieval performance. According to the standard Interactive Image Retrieval (IIR) process, retrieval is applied to the same corpus at every round, obtaining new ranked list of results. At each round, the tagged samples are used to update both the retrieval and AL models to be used for the next round. After calculation of mAP at each round we determine the (normalized) area under the curve as the overall score for AL performance.
5.2 Experimental Results
We quantified the AL methods by their learning curves, indicating the retrieval performance (measured in mAP) progress along the interactive cycles. The curves then aggregated by a. single measure of the
15

---

Published in Transactions on Machine Learning Research (12/2024)
Normalized Area under Learning Curve Barz et al. (2018) between 1,2 to 95 labeled samples. The results for SVM, MLP and GP are averaged over five different randomly selected queries.
As an ablation study, we conducted tests to evaluate the impact of our suggested acquisition functions for AL selection. Additionally, we tested our algorithm under non- non-greedy settings, indicated as GAL(batch), by selecting the top-B samples that maximize the impact values (1), (6), and (13), given a budget B. The non-greedy approach may encounter issues with redundant samples, as similar points could have similar scores. In contrast, the greedy algorithm prevents this scenario by ensuring that once sample is selected, it is added to the training set. This allows for the selection of new sample that maximizes the acquisition function, taking into account the updated training set.
5.2.1 Runtime and Pool of Selection Candidates
One factor affecting runtime is the ability to achieve high level of accuracy while scarching within small pool of candidates. We found that selecting from a pool of top-K ranked samples, according to the relevance probabilities obtained from the previous round, is beneficial in GAL and often in competitive methods. This subset X. is relatively rich in positive samples and hard negatives, thereby reducing the extreme imbalance in the general dataset. For example, our experiment on FSOD showed that, on average, 30% of the candidate set selected from the top-200 ranked samples were positive, compared to 0.5% in the general dataset. In our model, K can be viewed as a prrammerraeeter influenced by the topology of the data in the feature space, The value of K can be estimated through unsupervised analysis of the feature space topology, based on distances from various queries. Conducting this analysis by bootstrapping over randomly sampled queries from our datasets reveals a long tail distribution. We found that typical values around few percentage of the dataset size (up to 10%), present a reasonable cut-off on this long tail distribution and can also be used to set K. Alternatively, K can be set using a different labeled case with the same feature representation (see Sec. 5.2.2). Note that our training process can be easily parallelized by assigning each candidate to a separate process using multi-threading or multi-processing. We report the runtime in Sec. 5.2.2 and Appendix C.
5.2.2 SVM Classifier
We first present the global performance measure of Normalized Area Under Leurning Curve for the SVM- based scenario, tested for budget size B 1 and B = in tables 2 and 3. It is worth noting that the results obtained when B = 1 allow to assess the impact value independently from the greedy scheme. We indicate the top performing method in bold and the sccond place by an underline mark. Interestingly, random sampling often yields high performance. This is consistent to other AL studies in classification benchmarks in the literature, under cold-start conditions Hacohen et al. (2022) (as a diversity based strategy). Yet, in 8 out of 9 tests, GAL outperforms other methods and basclines for B = 1, where for B = 3, GAL is consistently the top performing method. Note that the top performance for all methods reached for K = 100 or 200 and there is no consistent competitor in the second place, indicating the robustness of GAL approach under different candidate pools.
Another interesting observation shows that considering a larger candidate pool (from 100 to the whole dataset) does not necessarily improve the performance. Often smaller candidate pool is preferred as observed in all the methods compared in our datasets for B = 3 (cf. Table 2 bottom), due to higher concentration of positive and hard negative samples, being better candidates for AL. For the majority of competitive methods, we discovered that a candidate set size of K = 200 optimal and can significantly roduce the computational cost, an important aspect in an interactive system. The results further show that GAL is relatively insensitive to K, above minimal value, and that this value of K generalizes to other datasets and domains.
Next, we present comparison of the learning curves by retricval mcan Average Precision (mAP) in figs. 8 and 9 for B = and B 3 3 with K = 200. These figures show the superior performance of GAL over previous methods and various baselines. The strongest competitor at B = 3 is found to be Kmeans which is purely basod on diversity, performing comparably to GAL in low the extreme cold start (up to 25 in FSOD-IR and up to 40 in Places). This result is consistent with the analysis in Hacohen et al. (2022) showing that diversity based models such as Kmeans+ or Coreset are top performing methods at extreme cold start. Yet, as more
16

---

Published in Transactions on Machine Learning Research (12/2024)
Paris
Places
FSOD
Candidate size
100
200
1k
100
all
100
200
all
Random
0.847
0.942
0.834
0.810
0.375
0.390
0.298
0.224
0.576
0.630
0.452
0.404
RBMAL
0.915
0.920
0.806
0.731
0.410
0.375
0.293
0.217
0.660
0.610
0.466
0.390
COD
0.909
0.924
0.881
0.716
0.399
0.391
0.359
0.221
0.630
0.639
0.606
0.410
MaxiMin
0.883
0.885
0.892
0.395
0.381
0.363
0.625
0.621
0.603
GAL (ours)
0.903
0.960
0.960
0.428
0.426
0.418
0.674
0.672
0.672
Table 2: Normalized Area under Learning Curve with B = 1 under different candidate settings. These results indicate the influence of our impact value of the selected samples. We indicate the top performing method in bold and the second place by the underline mark. We omit the test results for "all" in several cases due to increased computation cost and saturation. RBMAL: Cardoso et al. (2017), COD: Huang et al. (2021), MaxiMin: Karzand & Nowak (2020).
Paris
Places
FSOD
Candidate size
100
200
1k
all
100
200
1k
all
100
200
1k
all
Random
0.922
0.905
0.812
0.807
0.402
0.388
0.283
0.217
0.6377
0.633
0.473
0.404
RBMAL
0.923
0.888
0.785
0.718
0.397
0.355
0.295
0.213
0.652
0.592
0.467
0l389
COD
0.914
0.927
0.895
0.692
0.394
0.394
0.351
0.213
0.625
0.627
0.605
0.398
Kmeans++
0.922
0.941
0.935
0.744
0.416
0.417
0.394
0.205
0.661
0.666
0.632
0.393
Coreset
0.915
0.943
0.914
0.767
0.405
0.407
0.357
0.230
0.664
0.666
0.599
0.418
MaxiMin
0.906
0.926
0.916
0.906
0.409
0.402
0.368
0.657
0.648
0.612
GAL (ours)
0.946
0.960
0.952
0.430
0.427
0.419
0.681
0.686
0.675
GAL (batch)
0.943
0.957
0.955
0.431
0.421
0.417
0.679
0.678
0.675
Table 3: Normalized Area Under Learning Curve with B = 3, under different candidate settings. We indicate the top performing method in bold and the second place by the underline mark. GAL(batch) shows the result of our approach without the greedy component of our scheme. RBMAL: Cardoso et al. (2017), COD: Huang et al. (2021), Coreset: Khakham (2019), MaxiMin: Karzand & Nowak (2020).
labels are accumulated, Kmeans++ ceddorps GAL that leverages also uncertainty. Furthermore, we note substantial disparity, with 5-10% (absolute points) higher mAP when compared to MaxiMin (dark green) and around 5% better (from e.g. 0.75 to 0.80 in FSOD) compared to Kmeans+
We conducted an additional investigation using pure uncertainty-based method, in which the selection criterion involved identifying samples that are positioned closest to the decision boundary. This was achieved by selecting points greedily based on maximum entropy, referred to as Entropy. The results for budget size B = and 200 are presented Table It is evident that the results obtained using this Entropy
Paris
Places
F50D-IR
1.0
3.8
0.9
0.7
0.3
REMAL
0.5
COD
MaxtMin
labttd
number labelled
lobeted
Figure 8: mAP Learning Curves of SVM-based GAL with B = and K 200 for different datasets.
17

---

Published in Transactions on Machine Learning Research (12/2024)
Paris
Places
F50D-IR
1.0
0.9
0.7
0.8
GAL
2.6
Random
0.3
RBMAL
Kreans 1-1 Coresct
0.5
0.3
bbdied
number laaelee
lobeled
Figure 9: mAP Learning Curves of SVM-based GAL with B = 3 and K 200 for different datasets.
Parts
PLACES
FSOD-IR IR
1.0
0.8
0.5
0.9
0.7
0.4
0.8
0.7
dam
0.3
Maxinin
0.5
Km Kmeennppuice
Curnett
0.3
samples
number samples
sam pies
Figure 10: mAP Learning Curves of SVM-based GAL with B followed by B 7 and K 200 for different datasets.
method are considerably inferior to those of GAL across all the datasets. This experiment further strengthens our claim that GAL effectively combines both diversity and uncertainty. Methods that solely rely on one of these aspocts tend to exhibit lower performance.
Paris
Places
FSOD
Random
0.905
0.388
0.633
RBMAL Cardoso al. (2017)
0.888
0.355
0.592
COD Huang et al. (2021)
0.927
0.394
0.627
Kmeans++
0.941
0.417
0.666
Coreset Khakham (2019)
0.943
0.407
0.666
MaxiMin Karzand & Nowak (2020)
0.926
0.402
0.648
Entropy
0.903
0.329
0.586
GAL (ours)
0.960
0.427
0.686
GAL (batch)
0.957
0.421
0.678
Table 4: Normalized Area Under Learning Curve with = 3, K = 200. We indicate the top performing method in bold. Entropy shows a selection by the distance to the decision boundary.
As illustrated in Fig. 1la and supported our earlier analysis presented Fig. 6, larger budget sizes present more significant challenge, especially during the initial cycles. The challenge is demonstrated in Fig. 11b. During the initial cycles, the pseudo-label accuracy is inadequate, leading to accumulated errors, particularly for larger values of B. In response to this challenge, we conducted experiments where we set B = 3 for the first. 10 cycles, followed by B = 7. Nevertheless, our method is superior to other approaches, as shown in Table and Fig. 10. It is noteworthy that overall, although Kmeans++ performed better in the first cycles, our method still showcases superior performance. The greedy approach has a slight impact in the linear SVM case, presumably due to unreliable pscudo-labels, which mostly occur the initial cycles (see fig. 11b). This strategy is better manifested in the GP process, that is label independent.
18

---

Published in Transactions on Machine Learning Research (12/2024)
FSOD-IR
0.8
0-3
B=
0.7
0.7
correct label percentage
0.6
MAP
0.5
0.4
0.3
0.4
15
60 75
number labeled samples
number of labeled samples
(a)
(b)
Figure 11: (a) mAP Learning Curves of SVM-based GAL with B = 3 and B = 7. It evident that the larger batch size yields inferior results. (b) Pseudo-label accuracy tested on FSOD Benchmark, averaged over all classes and for candidate size of 200 and Random choice 50%.
Paris
Places
FSOD
Candidate size
100
200
500
100
200
500
100
200
500
Random
0.908
0.908
0.910
0.344
0.348
0.316
0.593
0.582
0.580
RBMAL Cardoso (2017)
0.906
0.876
0.811
0.332
0.310
0.281
0.590
0.534
0.487
COD Huang et al. (2021)
0.900
0.909
0.897
0.332
0.320
0.318
0.555
0.559
0.552
Kmeans+++
0.913
0.935
0.919
0.374
D.363
0.357
0.611
0.622
0.603
Coresct Khakham (2019)
0.900
0.902
0.880
0.347
0.342
0.326
0,583
0.581
0.569
MaxiMin Karzand & Nowak (2020)
0,910
0.925
0.919
0.355
0.353
0.323
0.589
0.591
0.563
GAL (ours)
0.929
0.939
0.932
0.366
0.369
0.369
0.618
0.625
0.612
GAL (batch)
0.930
0.941
0.927
0.366
0.361
0.361
0.619
0.614
0.615
Table 5: Normalized Area Under Learning Curve with B = 3 at first 10 cycles and then B = 7, under different candidate settings. We indicate the top performing method in bold and the second place by the underline mark.
Next, we present a qualitative result displayed in Figure 12. We take two query images belonging to the 'Tin Can' class in the FSOD-IR datasct and showcase the top-16 relevant images retrieved by the GAL and RBMAL methods al the fourth iteration, with a budget of = 3. In the visualization, green and red boxes are used indicate relevant and irrelevant results, respectively. It's worth noting that the right query image contains not only "Tin Can' but also monitor display. GAL successfully retrieves 15 out of 16 relevant images, with one visually reasonable error. In contrast, the RBMAL method selects few monitor images, which are exclusively present in the second query image. This example demonstrates common challenge in CBIR when dealing with images that contain multiple objects. While there may be initial ambiguity in the query, as the active learning cycles progress and the user lags positive examples, our model excels at selecting samples that capture the user intention concept (as shared pattern between the queries) more rapidly.
Finally, despite GAL evaluating classifier for each selection candidate, the computational cost of our method remains reasonable for several reasons.
We demonstrate that small candidate set of the dataset (obtained from the classifier's top-k), is sufficient the active learning selection pool. In many cases, this approach yields improved
19

---

Published in Transactions on Machine Learning Research (12/2024)
Query
Ours
DR
RBMAL
Image retrieval results for Tin Can in FSOD-IR datasct with B at itcration Green boxes stand for relevant results while red boxes account for false positives. The second query image has two objects: Can and Display monitor. The RBMAL method mistakenly retrieves images with monitor, where GAL succeeds to find the common pattern in the queries. This example illustrates how the initial ambiguity regarding the object is gradually resolved through the active learning cycles, allowing the algorithm to effectively capture the query concept.
Figure 12:
performance, as evidenced in Tables and 3. Consequently, there is no need to run our algorithm on the entire unlabeled set.
2. This allows for quick training and AL cycles, a practical requirement in interactive system such as IIR.
The average runtime for = 3 ranges from approximately 1.2-1.4 seconds per iterations on CPU, for 10 to 30 iterations (without parallelization. In comparison, for MaxiMin, the corresponding times range from 0.5-1 seconds. The remaining faster methods (approximately 0.1 seconds) involve a trade-off in accuracy (see Table 3). We also provide runtime comparison with ITAL in Appendix C.
5.2.3 AL with MLP Classifier
In this section, we present the outcomes of AL when applied to an additional non-linear classifier. It's important to note that the classifier in the context of AL-CBIR comprises two distinct stages: (i) the sample selection strategy (AL) and (ii) retricval. As discussed in section 4.1, it crucial to recognize that the utilization of non-linear classifiers in retrieval tasks may lead to immediate overfitting issues, primarily due to the significantly limited size of the training dataset. We therefore extended our work by employing three-layer MLP (10 neurons at the inner layers) with a ReLU activation function for the AL selection, while continuing to utilize the Gaussian Process (GP) method for retrieval. To make fair comparison we used the same retrieval method of GP in all compared methods. In this setting as well, the GAL method outperformed competitive algorithms as can be seon in Fig. 13a for the MIRFLICKR datasct with = 3 and 200.
5.2.4 AL with Gaussian Process
We further present the results of GAL utilizing a Gaussian Process (GP) classifier, which are compared to ITAL Barz et al. (2018). For this purpose, we replaced AL module of ITAL with GAL, employing our acquisition function (13). To make a fair comparison, we first ran ITAL with varying candidate pool sizes K. Fig. 13b illustrates the results of ITAL for B and K 200, 400, 1000, as well as the entire datasct (K = 20, 000). We present the results of ITAL for various settings in Appendix B, showing that the entire unlabeled dataset is needed for ITAL to reach it's best result.
20

---

Published in Transactions on Machine Learning Research (12/2024)
MIRFLICKR
MIRFLICKR
GAL
0.550
kmeans++
0.65
0.525
random
MaxiMin
0.500
0.55
mAP
0.475
MAP
0.50
0.450
0.45
0.425
0.40
ITAL 1k
0.400
ITAL 400
ITAL 200
10
20
30
40
50
number of labeled samples
40 number labeled samples
(a)
(b)
Figure 13: (a) mAP Learning Curves of MLP-based AL selection with B = 3 and K = 200 applied on
MIRFLICKR. (b) mAP Learning Curves of ITAL for B = 3 and different candidate set size K.
MIRFLICKR
MIRFLICKR
0.70
0.65
0.65
0.60
0.60
MAP
MAP
0.55
0.50
GAL 1.5K
0.45
ITAL all
0.45
GAL 1.5K
400
0.40
GAL 200
0.40
GAL 400
Kapoor et. al. 3K
GAL 200
0.35
0.35
10
20
30
40
50
60
70
10
20
30
40
50
60
70
number of labeled samples
number of labeled samples
(a) =
(b) B = 3
Figure 14: mAP Learning Curves of GP-based GAL with = 1 (a) and B = 3 (b) for MIRFLICKR. database. ITAL used the whole unlabeled set, while GAL and Kapoor el al. (2007) used different candidate set size K (see Table 6).
Next, we compared GAL and ITAL. Normalized Areas under Curve are summarized in the top panel of Table 6, where GAL outperforms ITAL even when considering only 1,500 points which are 7.5% of the unlabeled dataset as candidates. We further observe the impact of our greedy scheme component boosting the overall performance by nearly 7% (from 0.566 to 0.605) with respect to standard batch selection strategy (denoted by GbL(batch), i.c. choosing the top-B scores at cach round). Fig. 14 depicts the comparison between these two methods for 1 and B respectively with candidate pool K 200, 400, and 500. The figure shows 2-5% mAP improvement with K 1, 500.
Finally, we conducted comparison between GAL and another uncertainty-based approach proposed by Kapoor el al. (2007) which was designed for B = 1. This method aims to identify the sample which is closest to the decision boundary with the highest uncertainty a. We adapted this approach to our framework, evaluating its performance across various values of K, with the optimal performance observed GAL consistently outperformed this method across all tested values of K. The summarized results can be found in Table 6 and depicted in the left. part of Fig. 14.
3, 000.
21

---

Published in Transactions on Machine Learning Research (12/2024)
method
B =
= 3
ITAL Barz et al. (2018)
20,000 (all)
0.586
0.585
Kapoor et al. (2007)
1,500
0.517
Kapoor et al. (2007)
3,000
0.542
Kapoor et al. (2007)
20,000 (all)
0,457
GAL (ours)
200
0.584
0.570
GAL (ours)
400
0.593
0.583
GAL (ours)
1,500
0.608
0.605
GAL (batch)
200
0.584
0.553
GAL (batch)
400
0.593
0.573
GAL (batch)
1,500
0.608
0.566
Table Normalized Area under Learning Curves for MIRFLICKR database. Our GAL outperforms ITAL Barz et al. (2018) and Kapoor et al. (2007). Note that for B 1 there is no greedy process. The impact of our greedy scheme is manifested in B 3. 3.
6 Summary and Future Work
In this paper address the problem of active learning for Interactive Image Retrieval. This task introduces several unique challenges including, a process starting with only few labeled samples in hand and challenging open-set and asymmetric scenario (the negative set includes various unknown categories with different size). In this study, we suggested a new approach that copes with the above challenges by means of two main concepts. First, by considering the impact of each individual sample on the decision boundary as a cue for sample selection in the AL process. To this end, our acquisition functions, may evaluate pscudo-labels or directly optimize global uncertainty measure. Second, to belter cope with the scarcily of labeled samples in batch mode AL, embed approach in greedy framework where each selected sample in the batch is added to the train set, before selecting the subsequent best promising onc. This process is continued until the designated budget is reached, attempting to effectively extend the train set, and provide diversity within each batch. We demonstrate the properties of our method over a toy example, disentangling the two main attributes AL, namely diversity and uncertainty. We further showed that these attributes are inherently achieved in our approach. Additionally, we provide thcoretical analysis that supports the idea that our greedy scheme offers a reliable approximation (in the context of Gaussian Process). We assessed approach various large-scale image retrieval benchmarks, including new, challenging benchmark featuring small objects. Superior results obtained compared to previous methods, demonstrate the impact of our approach. In addition, we believe that our framework can pave the way for broader applications, particularly, the cold-start problem of AL, in realistic open-set scenarios.
7 Acknowledgments
The authors would like to express their gratitude Nir Sochen and Uri Itai for valuable comments and discussions.
Bibliography
Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan" Arora. Contextual diversity for active learning. In ECCV, 2020.
Umang Aggarwal, Adrian Popescu, and Celine Hudelot. Active learning for imbalanced datasets. WACV 2020, 2(1):1417-1426, 2020.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. ICLR, 2020.
22

---

Published in Transactions on Machine Learning Research (12/2024)
Ahmed Ayyad, Li Yuchen, Muaz Raden, Albarqouni Shadi, and Mohamed Elhossinn. Semi-supervised few-shot learning with prototypical random walk. In AAAT Workshop on Mela-Tearning and MelaDL, Challenge, 2021.
Imon Banerjec, Camille Kurtz, Alon Edward Devorah, Bao Do, Daniel Rubin, and Christopher F Beaulicu. Relevance feedback for enhancing content based image retrieval and automatic prediction of semantic image features: Application to bone tumor radiographs. Journal of biomedical informatics, 84:123-141 135, 2018.
Björn Barz and Joachim Deazler. Content-based image retrieval and the semantic gap in the deep learning era. In ICPR, pp.
2021.
Björn Barz, Christoph Käding, and Joachim Denzler. Information active learning for content- based image retrieval. In German Conference Pattern Recognition, pp. 650 666. Springer, 2018.
Klaus Brinker. Incorporating diversity in active learning with support vector machines. In JCML, pp. 59 66, 2003.
Thiago NC Cardoso, Rodrigo M Silva, Sérgio Canuto, Mirella M Moro, and Marcos A Gonçalves. Ranked batch-mode active learning. Information Sciences, 379:313-383 -377, 2017.
Akshay L Chandra, Sai Vikas Desai, Chailanya Devaguptapu, and Vineeth N Balasubramanian. On initial pools for deep active learning. In NewrIPS 2020 Workshop on Pre-registration in Machine Learning, pp. 14-32. PMLR, 2021.
O. Chapelle. Training a support vector machine in the primal. Neural Computation, 19(5):1155 1178, 2007.
Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch Active Learning Scale. NewrIPS, 2021.
A. Das and D. Kempe. Algorithms for subset selection in linear regression. In ACM Symposium on the Theory of Computing (STOC), pp. 43-54, 2008
Zeyad Emam, Sami Ali, Chu Hong-Min, Chiang Ping-Yehl Czaja Wojeiech, Leapman Richard, Goldblum Micah, and Goldstein Tom. Active Learning at the ImageNet Scale. In orXiv:2111.12880 2021.
Qi Fan, Wei Zhno, Chi-Keung Tang, and Yu-Wing Tai. Few-Shot Object Detection with Attention-RPN and Multi-Relation Detector. In CVPR, 2020.
Satoru Fujishige. Submodular Functions and Optimization. Elsevier, 2005.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. ICML, 2016.
Mingfei Gao, Zizhao Zhang, Guo Yu, Screan Ö Ari, Larry S Davis, and Tomas Pfister. Consistency-based semi-supervised active learning: Towards minimizing labeling cost. In ECCV, 2020.
Jia Gong, Zhipeng Fan, Qiuhong Ke, Hossein Rahmani, and Jun Liu. Meta agent teaming active learning for pose estimation. In CVPR, 2022.
Philippe Henri Gosselin and Matthieu Cord. Active learning methods for interactive image retrieval. IEEE Transactions on Image Processing, 1700):1200-1211, 2008.
Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on a budget: Opposite strategics suit high and low budgets. 1CML, 2022.
Siyu Huang, Tianyang Wang, Haoyi Xiong, Jun Huan, and Dejing Dou. Semi-supervised active learning with temporal output discrepancy. In ICCV, 2021.
Mark J Huiskes and Michael S Lew. The MIRFLICKR retrieval evaluation. In Proceedings of the 1st ACM international conference on Multimedia information retrieval, pp. 39 43,44, 2008.
23

---

Published in Transactions on Machine Learning Research (12/2024)
Qiuye Jin, Mingzhi Yuan, Shiman Li, Haoran Wang, Manning Wang, and Zhijian Song. Cold-start active learning for image classification. Information Sciences, 616:16-36, 2022.
A. Kapoor, K. Grauman, R. Urtasun, and T. Darrell. Active learning with gaussian processes for object categorization. In ICCV, 2007.
Mina Karzand and Robert D. Nowak. Maximin active learning in overparameterizze model classes. IEEE Journal on Selected Areas in Information Theory, 1(1):167-177, 2020. 2019. GitHub repository.
V. Khakham. K-segment. https:///gtthuu...co///aaaaaaaaa
Suraj Kothawade, Nathan Bock, Krishnateja Killamsetty, and Rishabh Iyer. SIMILAR: Submodular infor- mation measures based active learning realistic scenarios. NeurIPS, 2021.
Boaz Lerner, Nir Darshan, and Rami Ben-Ari. Advancing image retrieval with few-shot learning and relevance feedback. arXiv:2312. 11078, 2023.
Zimo Liu, Jingya Wang, Shaogang Gong, Dacheng Tao, and Huchuan Lu. Deep reinforcement active learning for human-in-the-loop person re-identification. In ICCV, 2019.
B.S. Manjunath, P. Wu, S. Newsam, and H.D. Shin. A texture descriptor for browsing and similarity retrieval. Signal Processing: Image Communication, 2000.
Akshay Mehra, Jihun Hamm, and Mikhail Belkin. Fast Interactive Image Retrieval using large-scale unla- beled data. KDD, 2018.
G.I. Nemhauser, L.A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-1. Mathematical Programming, 14:265 294, 1978.
Giang Truong Ngo, Tao Quoc Ngo, and Dung Duc Nguyen. Image Retrieval with relevance feedback using SVM active learning. International Journal of Electrical and Computer Engineering, 6(6):3238 3246,, 2016.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: predictions for unrecognizable images. CVPR, 2015.
High confidence
Kun-Peng Ning, Xun Zhao, Yu Li, and Sheng-Jut Huang. Active learning for open-set annotation. In CVPR, 2022.
Amin Parvaneh, Ehsan Abbasnejad, Damien Teney, Gholamreza Reza Haffari, Anton van den Hengel, and Javen Qinfeng Shi. Active learning by feature mixing. In CVPR, 2022.
Pouya Pezeshkpour, Zhengli Zhao, and Sameer Singh. On the utility of active instance selection for few-shot learning. NewrIPS HAMLETS, 2020.
Lorenzo Putzu, Luca Piras, and Giorgio Giacinto. Convolutional neural networks for relevance feedback in content based image retrieval. Multimedia Tools and Applications, 79:26995 27021, 2020.
Hamed Qazanfari, Hamid Hassanpour, and Kazem Qazanfari. A short-term learning framework based relevance foedback for content-based image retricval. In 2017 3rd Tranian Conference on Intelligent Systems and Signal Processing (ICSPIS), pp- 136 140. IEEE, 2017.
Filip Radenović, Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondřej Chum. Revisiting Oxford and Paris: Large-scale image retrieval benchmarking. In CVPR, 2018
Yunbo Rao, Wei Liu, Bojiang Fan, Jiali Song, and Yang Yang. A novel relevance feodback method for CBIR. World Wide Web, 21:1505-15 1522, 2018.
Tal Ridnik, Emanuel Ben-Baruch, Asal Noy, and Lihi Zelnik- Imagenet-211 pretraining for the masses. NewrIPS Datasets and Benchmarks Track, 2021.
Fabio Roli al. Instance-based relevance foodback for image retrieval. Advonces in neural information processing systems, 17, 2004.
24

---

Published in Transactions on Machine Learning Research (12/2024)
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A Core-Set approach. TCML, 2018.
Simon Tong and Edward Chang. Support vector machine active learning for image retrieval. In Proceedings of the ninth ACM international conference on Multimedia, pp- 107-118, 2001.
Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classifica- tion. Jourmal of machine learning research, 2(Nov):45 66, 2001.
Sergei Vassilvitski and David Arthur. k-means++: The advantages of careful seeding. In ACM-SIAM symposium on Discrete algorithms, pp. 1027 1035, 2006.
Keze Wang, Dongyu Zhang, Ya Li, Ruimao Zhang, and Liang Lin. Cost-effective active learning for deep image classification. IEEE Transactions Circuits and Systems for Video Technology. 27(12):251122000 2016.
Tianyang Wang, Xingjian Li, Pengkun Yang, Guosheng Hu, Xiangrui Zeng, Siyu Huang, Cheng SronggZZonggan Xu, and Min Xu. Boosting active learning via improving test performance. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 8566-8574, 2022.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume MIT press Cambridge, MA, 2006.
Jiaxi Wu, Jiaxin Chen, and Di Huang. Entropy-based active learning for object detection with progressive diversily constraint. In CVPR, 2022.
Yichen Xie, Tomizuka Masayoshi, and Zhan Wei. Towards general and efficient active learning. In wxXiv:112.00963, 2021.
Yi Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauplmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, 113(2): 113-127, 2015.
Ofer Yehuda, Avihu Dekel, Guy Hacohen, and Daphna Weinshall. Active learning through a covering lens. NewrIPS, 2022.
Michelle Yuan, Hsuan-Tien Lin, and Jordan Boyd-Graber. Cold-start active learning through self-supervised language modeling. arXiu:2010.0955 2020.
Q Zhang, S. A. Goldman, W. Yu, and J. Fritts. Content-based image retrieval using multiple-instance learning. In ICML, 2002.
G. Zhao, E. Dougherty, B.J. Yoon, F. Alexander, and X. Qian. Efficient active learning for gaussian process classification by error reduction. Tn NewrIPS, 2021.
Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEFE Transactions on Pattern Analysis and Machine Intelligenc, 40(6): 1452 1464, 2017.
25

---

Published in Transactions on Machine Learning Research (12/2024)
Appendices
A Cold Start Analysis
The cold start scenario in active learning refers to the initial phase where the model has small amount of labeled data to begin with. This lack of labeled data makes it challenging for the model to make accurate predictions or to understand the underlying data distribution. Due tho these challenges, random selection approach often selected Hacohen et al. (2022). We demonstrate the cold start scenario performance of GAL on the toy example and compare to the strong baseline of random selection (see discussion in Hacohen al. (2022) and references therein). Figure A1 shows the mean average precision of our toy example classification (Sec. 3) as the number of labeled points is increased by B 2, up to 100 training samples and 220 test samples. The light and dark blue lines show the performance of the random and GAL algorithms in cold start, where they start with only 7 labeled points. The light and dark red curves show the results when starting with 50 labeled samples. Clearly, in the cold start case, the classification task is more challenging. Nevertheless, the GAL algorithı outperforms the random selection.
0.9
0.8
MAP
0.7
0.6
Random cold
Random
0.5
GAL cold
GAL
40
100
number labeled samples
Figure A1: Cold start scenario demonstration. The classification results are shown against the number of labeled samples, where at each iteration, we increased the number by B = 2. In the cold start case (light and dark blue), we started with labeled samples, while in the other scenario (light and dark red), we started with 50 labeled samples. In both cases, the GAL algorithm outperforms the random selection.
B Analysis of ITAL Performance for Various Candidate Size
Table A1 provides an analysis of ITAL for various candidate set size on MIRFLICKR. It is evident that the entire unlabeled dataset is needed for ITAL to reach the best result.
Normalized AUC
200
0.547
400
0.552
1,000
0.564
20,000
0.585
Table A1: Normalized Areas under Curve of ITAL Barz et al. (2018) for B 3 at variety of candidate set sizes K. ITAL requires all the corpus for maximum performance.
26

---

Published in Transactions on Machine Learning Research (12/2024)
C Runtime Comparison and Analysis
Here, we show the runtime of GAL-Gaussian Process with ITAL Barz et al. (2018). For fair comparison, we select the settings for both methods such that they have a similar performance level. Figure A2 illustrates the results, showing that ITAL and GAL have comparable runtime. is important to note that our training process can easily be parallelized by assigning each candidate to a separate process using multi- threadine or multi palti-processing, thus achieving significant speed-ups.
The experimental data further fitted to third-degree polynomial (with respect to i in (16)) which is in accordance with the complexity equation (16).
30.0
Polynomial Fit GAL
Time [sed]
25.0
22.5
20.0
17.5
15.0
12.5
25
50
75
100
125
150
Rteraion Number
200, B 3. We further display the run-time of ITAL for comparison, under setting with the same accuracy level (approximately 0.57), which corresponds to K = 1000. GAL shows comparable run-time performance, predominantly due to the fact that GAL needs significantly lower candidate pool for sample selection. We also demonstrate agreement with the theoretical complexity (16) using a third-degree polynomial fit.
Figure A2: GAL run-time [see] for GP,
27


Reviews:
[{"review_id": "3KJqkCXiRg", "reviewer": "Reviewer_aK8m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed idea is intuitive and appears to address the active learning problem in IIR well.\n\n2. The proposed techniques seem to be quite effective.\n\n3.  Both illustrative toy examples and theoretical analysis have been provided to help understand the proposed method.\n\nWeaknesses:\n1. The paper is poorly written. It is hard to understand the significance of the proposed method to many other methods, like semisupervised learning, unsupervised learning, transfer learning methods, and the SOTA active learning method in IIR. Can the author explain why active learning is the most effective approach for addressing the problem of learning with a few labeled samples and a large amount of unlabeled data?\n\n2. It is hard to tell whether the proposed method works for mainstream models like ViTs. What are the SOTA models for IIR? Can the method work with these SOTA models? Any pre-trained models can be used to help address the problem.\n\n3. The writing of this paper can be improved. The current presentation is under-polished and thus is not ready for publication.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an active learning method called Greedy Active Learning (GAL) for Interactive Image Retrieval (IIR). AGL addresses two unique challenges: 1) open-set and 2) asymmetric. It uses acquisition functions to quantify the impact value on the classifier based on boundary shit while introducing a greedy method to deal with the scenario where they are a few labeled samples and many open-set samples. The proposed techniques are theoretically justified and empirically verified.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The proposed method can be better presented. First, summarizes existing works in all relevant fields, the problems they tackle, improvements, and remaining problems. The relationship between AL in image classification vs AL in IIR, how many techniques can be transferred to IIR, and how they perform. Are there any low-scale, mid-scale, and large-scale real-world datasets that can benchmark different IIR AL methods? Why did the authors propose extended datasets in the experiments? The entire methodology can be presented as one single framework, not separated techniques. Improving the presentation and writing quality of the paper.", "broader_impact_concerns": "No ethical concerns are identified.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CkofFaAWZJ", "reviewer": "Reviewer_h5uH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has several major strength:\n1. Originality - the proposed approach appears to be novel\n2. Relevance - active learning is an important area of research with practical applications\n3. Future Impact - this paper is likely to have a significant impact on future work on AL\n4. Empirical Evidence - the paper provides strong empirical evidence that GAL outperforms existing approaches on the four chosen tasks\n5. Overall the paper is well-written and reasonably easy to follow. In particular, Section 3 is extremely helpful in setting up the stage for the intuition behind the proposed. This reviewer wishes that more authors would take this approach in their papers! \n\nThe paper also has two main weaknesses:\n1. SCALABILITY: the authors should tackle this issue heads on. It is clear that the proposed approach is computationally expensive, so rather than \"drop hints\" of this limitation (eg, downsizing the Paris-6K dataset, or having un-computed cells in Table 2), the authors should add a section to analyze and discuss this issue\n2.  rather than staying with a crisp, simple message of \"GAL outperforms its competition,\" the authors are sometimes trying to make \"stretch claims\" that - in this reviewer's opinion - hurt, rather than help, this paper. For example, the claim that K=200 is an \"optimal size\" (bottom of page 17) is later refuted by the evaluation on MIRFLICKR (Table 7); it is also a counter-intuitive claim, especially for open-set, class-imbalanced domains. Even though the observation may be true on these 3 datasets, it is more likely that they all share a peculiar property that makes it so; unfortunately, this claim sounds more like a \"diversion\" from the bigger issue of scalability (especially in conjunction with  the bullet \"1\" close to the bottom of page 18). Another example is on page 21, where Fig 17 makes the claim that GAL is faster/comparable to ITAL; if that was truly the case, why not run GAL on all 20K examples?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces Greedy Active Learner (GAL), which is a novel Active Learning (AL) approach for Interactive Image Retrieval (IIR). GAL is robust and efficient when dealing with the challenges of cold-start, open-set, and class-imbalance in a binary classification setup. GAL uses (i) a novel acquisition function for sample selection that measures the impact of each unlabeled sample on the classifier, and (ii) a greedy selection approach that balances diversity and uncertainty within each batch of examples selected for annotation. The paper uses four datasets to evaluate GAL with both linear and non-linear classifiers, and it shows that GAL convincingly outperforms existing approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The top priority would be to address the two weaknesses above. There are smaller changes suggested below.\n\np 5: bottom paragraph\n- your intuitive argument on why GAL is NOT selecting examples similar to each other is fairly weak. It also seems to be invalidated by Figure 2.d, where there are AT LEAST two pairs of points that appear similar to each other\n- afirm --> confirm\n\np 15: in Fig 13, please add for each graph the horizontal line corresponding to best-known result when training the classifier on all available data; for the downscaled datasets, please also add the same for a classifier trained on the larger, original dataset. W/o these values, it is impossible to judge whether, say,  0.5 on PLACES is a good/mediocre/poor performance (ideally, the learning curve should continue until AL's performance is comparable to supervised training)\n\np 19: same as above for Fig 15\n\np 16: except for the first two sentences, the rest of the top paragraph belongs in a DISCUSSION section, rather than in the opening paragraph of the Experimental Results one", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "PL5WatiXYZ", "reviewer": "Reviewer_otno", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**：\n1. The paper effectively conveys ideas, exhibits a well-structured organization.\n2. The experimental demonstration section is comprehensive, providing evidence from multiple perspectives to prove the superior performance of the proposed method named Greedy Active Learning.\n3. The theoretical analysis section of the paper is meticulously comprehensive, offering conditions that ensure a reasonably accurate approximation to optimal batch selection.\n\n**Weaknesses**\n1. In Section 1, the paper acknowledges the existence of hybrid approaches that integrate uncertainty and diversity. It is necessary to introduce their limitations and highlight the advantages of the method proposed in this paper.\n2. Some parts of the paper's content are challenging to understand. For example, in Section 1, the statement \"On the other hand, diversity is ... the most effective points\" requires additional information to enhance readers' comprehension.\n3. The paper claims that the proposed active learning method performs well in cold-start scenarios in Section 1. To support this claim, please provide examples of experiments conducted in cold-start scenarios with various sizes of labeled samples.\n4. The paper contains some writing errors that need to be corrected. In Section 5, \"We asses the ...\" should be \"We assess the ...\". Please check the grammar and writing of the paper once again.\n5. The figures in the paper have certain limitations. To prevent distortion, please use vector graphics instead of bitmap images for figures, such as Figure 1, Figure 2, and Figure 7.\n6. The bibliography format needs to be corrected to ensure its completeness and consistency.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an innovative batch-mode active learning framework named Greedy Active Learning, designed to address interactive image retrieval. The key innovation of this work is twofold: the introduction of new acquisition functions that quantify the impact value, and the utilization of a greedy scheme to efficiently leverage each sample while coping with a limited number of labeled samples. The proposed framework, which employs different classification methods, outperforms previous approaches and demonstrates strong performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See **Weaknesses**.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers recommended acceptance, citing the novelty of the approach, its impact to interactive image retrieval, and solid empirical performance. The authors were responsive to reviewer concerns in their revisions, and reviewers marked their concerns as overall resolved.
Decision: Accept (poster)