Comparative Analysis of Relevance Feedback Techniques for Image Retrieval

This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. Comparative Analysis of Relevance Feedback Techniques for Image Retrieval Lucia Vadicamo1⋆, Francesca Scotti1,2⋆, Alan Dearle3, and Richard Connor3 1Institute of Information Science and Technologies, CNR, Pisa, Italy 2Department of Computer Science, University of Pisa, Italy 3University of St Andrews, St Andrews, Scotland, UK [email protected], [email protected], [email protected], [email protected] Abstract. Relevance feedback mechanisms have garnered significant attention in content-based image and video retrieval thanks to their effectiveness in refining search results to better meet user information needs. This paper provides a comprehensive comparative analysis of four techniques: Rocchio, PicHunter, Polyadic Query, and linear Support Vector Machines, representing diverse strategies encompassing query vector modification, relevance probability estimation, adaptive similarity metrics, and classifier learning. We conducted experiments within an interactive image retrieval system, with varying amounts of user feedback: full feedback, limited positive feedback, and mixed feedback. In particular, we introduce novel enhanced versions of PicHunter and Polyadic search incorporating negative feedback. Our findings highlight the benefits of integrating both positive and negative examples, demonstrating significant performance improvements. Overall, SVM and our improved PicHunter outperformed the other approaches for ad-hoc search, especially in cases in which the feedback process is iterated several times. Keywords: Content-Based Image Retrieval ·Relevance Feedback ·PicHunter ·Rocchio ·Polyadic Query ·SVM 1 Introduction Relevance feedback mechanisms, initially introduced in information retrieval, have gained significant attention in content-based image and video retrieval. These mechanisms refine search results to better match the user’s needs by iteratively adjusting search parameters based on user-selected relevant (positive) and/or non-relevant (negative) examples from an initial set of results. This paper compares four techniques for updating search results: 1. Rocchio algorithm [20], which adjusts the query vector to be closer to relevant results and further from non-relevant ones; ⋆Co-first authors This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. 2 L. Vadicamo et al. 2. PicHunter [5], which estimates data object relevance using Bayesian decision theory; 3. Polyadic Query [3], which refines the search using a set of multiple independent query objects determined by user feedback; 4. Linear Support Vector Machines (SVMs) [25], trained on user feedback to distinguish relevant from non-relevant data objects. These techniques were selected as they represent different approaches used in modern search retrieval systems [2,18,12,14], including query modification, relevance estimation, similarity adaptation, and classifiers. Our study is conducted within an interactive content-based image retrieval system, using a finite dataset S={o1, . . . , on} ⊂ D, where each oirepresents an image and Dis a data domain with a given metric function d:D ×D → R+. We focus on m-dimensional vector spaces with a Euclidean distance metric as is typically the case when oiare feature vectors extracted using state-of-theart deep neural networks [19,17]. At each search iteration t, the system displays nD< n images to the user, forming the display Dt. Users can select positive (relevant) examples and negative (non-relevant) examples from those in the display. The system uses these selections to update results iteratively with a relevance feedback algorithm. To understand how different feedback strategies impact the effectiveness of the various approaches, we considered three scenarios: i) Complete feedback, labeling all images in the display; ii) Limited positive feedback, selecting only a few positives; iii) Limited mixed feedback, selecting a few positives and negatives. The key contributions of our work are threefold. First, we present a comparative analysis of commonly used relevance feedback approaches for interactive image retrieval, addressing a gap in the existing literature. Second, we introduce an enhanced version of the PicHunter algorithm called PicHunter⋆which augments the original algorithm with the addition of negative feedback. Finally, we provide a revised version of the Polyadic Query approach that also incorporates negative feedback. Experimental results show significant retrieval performance improvements from these modifications, demonstrating the efficacy of integrating both positive and negative feedback. Moreover, we identified SVM and PicHunter⋆as the most effective approaches across all feedback scenarios analyzed. The remainder of this paper is structured as follows: Section 2 discusses related work, Section 3 describes the methods and their enhancements, Section 4 presents the experimental results, and Section 5 concludes the paper. 2 Related Work Relevance feedback in content-based multimedia retrieval has seen substantial advancements over the years. Researchers have developed numerous methods to refine search results based on user feedback, ensuring that the system better aligns with user preferences. One common strategy is using a query shifting method, which aims to construct a new query point closer to relevant results and further from non-relevant This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. Comparative Analysis of Relevance Feedback Techniques for Image Retrieval 3 ones. Rocchio’s algorithm is a classical example, refining the query by weighting the contributions of relevant and non-relevant images [20,24]. Another approach uses Bayesian decision theory to compute the new query by considering probabilistic measures of relevance [8]. Additionally, methods such as those proposed by [16] estimate the probability densities of individual features for relevant and non-relevant images to dynamically adjust the query point. Another significant strategy involves estimating relevance or probabilistic scores for each data object. For example, [21] determines a relevance score based on the dissimilarity between each data object and its nearest relevant and nonrelevant examples. Other approaches, such as those by [5], [7], and [28], employ Bayesian decision theory to estimate the probability of each image being relevant, thereby guiding the retrieval process. Moreover, [13] uses logistic regression analysis to evaluate the relevance probability. Some approaches focus on modifying the (dis)similarity function. For instance, [23] implemented a generalized Euclidean distance and [11] leveraged user feedback to learn the parameters of a quadratic distance function, creating a new dissimilarity measure that better reflects the user’s criteria. In [3,2], a dissimilarity measure between data object and a query set formed from the positive examples (polyadic query) is employed to refine the search. Lastly, classifiers, particularly linear SVMs, have been widely used in this context. Zhou et al [29] aims to find a hyperplane that effectively separates relevant and non-relevant images, while Tong et al [25] extended this by proposing an active learning method, enhancing the classifier’s ability to adapt to user feedback. Min et al [15] addressed potential biases in SVM-based techniques by introducing Fuzzy SVMs. Linear SVMs remain a popular choice in relevance feedback applications due to their straightforward implementation, ease of interpretation, and the ability to deliver accurate results with a limited number of annotated samples. They also efficiently scale to manage large collections [12]. 3 Methods Used for Comparison In this work, we focus on an interactive retrieval system designed to assist users in searching for target images. This system operates iteratively, refining its display of images based on user feedback to efficiently converge on the target images. We denote the set of relevant (positive) examples selected by the user during iteration tas A+ t, and the set of non-relevant (negative) examples as A− t. These sets are referred to as positive and negative actions. For each method, we implemented an incremental and a batch update version of the algorithm. At each iteration the “incremental” version only uses the feedback provided in that iteration to update the results. In the “batch” versions the knowledge of all positive and negative examples selected by the user is considered in each iteration. We use the notation A+ ≤t=St′≤tA+ t′and A− ≤t=St′≤tA− t′to indicate the set of positive and negative examples up to iteration t. For batch updates, we assume that the images selected at a given iteration cannot be re-selected as positive or negative examples in the subsequent iterations. For in- This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. 4 L. Vadicamo et al. cremental updates, the user can select any image present in the results, therefore re-selection of previous positive or negative examples is permitted. 3.1 Rocchio Algorithm The Rocchio algorithm [20] is a widely adopted method, initially proposed for document retrieval systems. It adjusts the query vector towards the centroid of relevant documents and away from the centroid of non-relevant documents, with the magnitude of the adjustment determined by specific weight parameters. This method, adapted for use with features from images and videos, updates the query vector as qnew =α q +β1 |A+|Poj+∈A+oj+−γ1 |A−|Poj−∈A−oj−, where α,β, and γare weight parameters that control the influence of the initial query q, positive examples A+, and negative examples A−. Let qobe the initial user query at iteration t= 0 (which can be zero if the display starts with a random selection of images). At each iteration t, we build a new query vector qt+1 using the Rocchio formula either on –the previous query (q=qt) and the user feedback at that iteration (A+= A+ t,A−=A− t), referred to as incremental update; or –the initial query (q=qo) with the knowledge of all positive and negative examples selected by the user up to that iteration (A+=A+ ≤t,A−=A− ≤t), referred to as batch update. The new query qt+1 is used to search the original space and create the new display as Dt+1 =kNN(qt+1)with k=nD, where the nearest-neighbour search is performed using the original metric d. 3.2 PicHunter PicHunter [6,5] utilizes a Bayesian framework to model the probability distribution of the user’s ideal target images. The algorithm begins with a prior probability distribution over the image dataset, such as P(T=oi) = 1 nfor all oi∈S, where the random variable Tdenotes user’s target image. As users provide positive feedback on displayed images, this distribution is updated to reflect the likelihood of each image being the target. For each iteration t, the system displays a set Dtof nDimages. Each user feedback (action At), is recorded and used to update the posterior probability P(T=oi|Ht), where Htrepresents the history of displayed images and feedback up to iteration t. This probability distribution is then used to select the next set Dt+1 of images to display, choosing the nDwith the highest posterior probability. The posterior probability P(T=oi|Ht)is computed incrementally from P(T=oi|Ht−1)using the Bayes’ Theorem [5]: P(T=oi|Ht) = P(At|T=oi, Ht−1, Dt)P(T=oi|Ht−1) Pn j=1 P(At|T=oj, Ht−1, Dt)P(T=oj|Ht−1)(1) This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. Comparative Analysis of Relevance Feedback Techniques for Image Retrieval 5 Here, the conditional probability P(At|T=oi, Ht−1, Dt), known as the user model, predicts the user’s action Atgiven the current display Dt, the previous history Ht−1, and assuming oiis the target. The original PicHunter algorithm assumes a time-invariant user model based on relative similarity, where users consistently select images more similar to the target as positive examples (At=A+ t). This model implies that user actions are stable over time and independent of Ht−1. Moreover, the user model is typically calculated assuming independent selection [5,18]: P(A+ t|T=oi, Dt) = Y oja∈A+ t P(A+ t=oja|T=oi, Dt)(2) Commonly, P(A+ t=oja|T=oi, Dt)is computed using a softmin version of the original distance function: Psoftmin(A+ t=oja|T=oi, Dt) = exp(−d(oja, oi)/τ) Poj∈Dtexp(−d(oj, oi)/τ)(3) where τis a temperature hyperparameter. In our work, we extended PicHunter to accommodate both positive and negative feedback, referring to this enhanced version as PicHunter⋆. In this case, the action set Atas composed of two subsets: A+ tfor positive examples and A− tfor negative examples. The updated posterior probabilities P(T=oi|Ht)are then computed using Eq. 1, where user model P(At|T=oi, Dt)is calculated as Y oja∈A+ t Psoftmin(A+ t=oja|T=oi, Dt)Y oja∈A− t Psoftmax(A− t=oja|T=oi, Dt)(4) where Psoftmax(A− t=oja|T=oi, Dt) = exp(d(oja, oi)/τ) Poj∈Dtexp(d(oj, oi)/τ)(5) The rationale behind using softmin for positive examples and softmax for negative examples is that the likelihood of selecting an image as a positive example decreases with distance from the target, while the likelihood of selecting it as negative example increases. The computations for Psoftmin and Psoftmax can be optimized and calculated together by noting that e−x=1 ex. PicHunter is designed for incremental updates only, as it relies on the current display to compute the user model, excluding previously displayed images. To overcome this limitation and facilitate comparisons with other methods that use batch updates (incorporating all feedback up to a given iteration), we developed a hybrid incremental-batch update version of PicHunter and PicHunter⋆. This hybrid approach maintains the incremental update of posterior probabilities as in Eq. (1) but calculates the user model based on all positive and negative examples selected up to the current iteration that are also present in the current display. This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. 6 L. Vadicamo et al. 3.3 Polyadic Search In [3], Connor et al. introduced the concept of polyadic queries, which allows for similarity searches using multiple independent query objects. This approach leverages a dissimilarity function to query with a set of elements rather than a single query object. It is particularly useful in relevance feedback scenarios, where users can refine searches interactively using a set of selected images as a polyadic query. Connor et al. [3] proposed using the MSED [4] divergence function to measure the distance between a polyadic query and data objects. MSED is an extension of the Structural Entropic Distance (SED) originally applied to labeled tree structures, which compares Shannon entropy Hof probability vectors with their arithmetic mean: SED(v,w) = C(v+w 2) pC(v)·C(w)−1(6) MSED(V) = 1 m−1   C1 mPvi∈Vvi m qQvi∈VC(vi)−1 (7) where C(x) = eH(x),H(x) = −Pixiln xiand V={v1,...,vm}is a set of m vectors. Here an outcome of 0 implies all elements of Vare identical, and an outcome of 1 implies that all elements of Vare mutually orthogonal. In a polyadic search, the dissimilarity between a query set Q={q1, ..., qm} and a data object o∈Sis assessed using: dMSED(Q, o) = MSED ({f(q1), f(q2), . . . , f(qm)}∪{f(o)})(8) where fis a function that transforms the original data vector into probabilistic vectors, such as the softmax function. Originally, polyadic search was used with explicit positive feedback. We extend this concept to an iterative algorithm that can handle both positive and negative examples, similar to the Rocchio approach. We call this method similarity reweighting with polyadic queries. It updates relevance scores ρt+1(oi)for each data object oiusing either –abatch update of an initial score ρ0(oi) = sPoly(q0, oi), with ρ0(oi) = 0 if there is not an initial query qo, using all positive and negative examples selected by the user up to that iteration: ρt+1(oi) = α ρ0(oi) + β sPoly(A+ ≤t, oi)−γ sPoly(A− ≤t, oi); (9) –or an incremental update, where the previous score ρt(oi)is updated with the feedback from the current iteration: ρt+1(oi) = α ρt(oi) + β sPoly(A+ t, oi)−γ sPoly(A− t, oi)(10) Here ρt+1scores are used to rank the dataset and select the top nDitems for the new display Dt+1. In addition to the similarity derived from MSED, i.e., sMSED = 1−dMSED, we also tested sSED(Q, o)=1−SED Pq∈Qf(q)/|Q|, f(o)using the softmax function as f. This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. Comparative Analysis of Relevance Feedback Techniques for Image Retrieval 7 3.4 Linear SVM Support vector machines (SVMs) are a core machine learning technique used across various tasks and domains, including image recognition and text classification. Tong and Chang [25] proposed combining SVMs with an active learning algorithm for effective relevance feedback for image retrieval. They used user feedback to train a linear binary SVM classifier, leveraging the distance from the hyperplane separating relevant from non-relevant examples to refine the search. In our experiments, we train a linear SVM using user feedback and then create a new display by selecting the nDimages that are furthest from the hyperplane on the relevant side. Computationally, this involves performing an inner product search using the hyperplane coordinates. Because SVM cannot be trained without negative examples, if no negative examples were selected, we randomly sample 10 images in the dataset and not in the current display to serve as negative examples without true knowledge of their relevance. The SVM method is designed to work with batch updates, where all positive and negative examples collected up to the current iteration are used to train the SVM classifier. We also tested an incremental update version, where the linear SVM classifier is trained using only the feedback from the current iteration. In this latter case, the score associated with each image oiat iteration t+ 1 is calculated as: ρt+1(oi) = αρt(oi) + β(⟨oi,w⟩+b)(11) where ρt(oi)is the score from the previous iteration, wand bare the coefficients and intercept of the learned hyperplane, and αand βare hyperparameters. 4 Experimental Evaluation We performed a comparative study in the context of an ad-hoc search task, aimed at finding as many relevant items as possible for a specific query (e.g., “A person wearing gloves whilst cycling”). This type of task is commonly assessed in established interactive video search benchmarking campaigns, such as the Video Browser Showdown [27,14] and the Lifelog Search Challenge [9,26]. We used an automatic feedback protocol to simulate user selection, therefore we required a dataset with a well-defined ground truth. While classification datasets might be used, they often do not capture the complexities of information needs in interactive image or video retrieval. Therefore, we utilized the ground truth from the Ad-hoc Video Search (AVS) task in the TREC Video Retrieval Evaluation (TRECVID) collection4. Specifically, we employed the 89 AVS queries and judgments from TRECVID 2019 to 2023 on the V3C1+V3C2 video collection [22]. The TRECVID-AVS ground truth includes judgments for video shots, so we used around 2.6 million keyframes extracted from these shots and mapped the judgments to the corresponding keyframes. CLIP ViT-H/14 - LAION-2B [10,19] features were used for image representation. The timestamp 4https://www-nlpir.nist.gov/projects/trecvid/trecvid.data.html This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. 8 L. Vadicamo et al. of the keyframes and their CLIP features were sourced from VISIONE [1] repository at https://zenodo.org/records/8188570. Since the TRECVID ground truth is not complete (only a subset of video segments were manually judged for each query), we selected queries with at least 200 positive and 1400 negative annotations. This resulted in 80 datasets, one for each query, containing 1500 images each, with 10% labeled as relevant and the remaining 90% as non-relevant. We initiated each search with the same random display of nD= 50 images, containing only 5 relevant images. In our simulated interactive search, at each iteration, k+positive and k−negative examples are selected from those in the display. Various combinations of k+and k−were tested to evaluate the performance of different techniques. After each iteration, we evaluate the recall@nD, i.e., the fraction of relevant images that are visualized in the updated display. An automatic protocol was used to randomly select positive and negative examples in the display based on ground truth at each iteration, providing a baseline performance estimate. Future work will investigate other selection criteria, such as top positive/negative examples, to assess performance under different user behaviors. We measured recall at each iteration, for up to 10 iterations, across all datasets. Each scenario started with the same randomly selected initial display, resulting in an initial query q0or score s0of zero. We evaluated 10 different display initializations for each case. We tested each method under various feedback scenarios: all positive examples in the display (excluding negative examples from calculations), all positive and negative examples, some positive examples with no negative examples, and some positive examples with some negative examples. We considered various configurations of each method, including different hyperparameters, update strategies, and similarity functions. Due to space constraints, only the principal results are presented, with additional observations summarized in the next subsection. The datasets and the code to reproduce the experiments are available at https: // github. com/ vadicamo/ relevance-feedback . Configuration and Hyperparameter Tuning. A grid search was employed for hyperparameter tuning, using 5 different initializations for the display. For comparisons involving similarity functions and incremental/batch update types, we used 10 different display initializations. Statistical significance was determined using ANOVA and pairwise Tukey’s tests with a significance level of 0.05. The grid search for hyperparameters α,β, and γwas conducted with values in {0,0.25,0.5,0.75,1}, ensuring α+β−γ= 1 or α+β= 1 when only positive feedback is considered. We arbitrarily selected the parameters providing the best recall at the third iteration for each method and update type to keep the experimental space tractable, which varied based on the type of feedback: –Rocchio: For cases with only positive examples, the optimal parameters were (α, β, γ) = (0.75,0.25,0). When all positive and negative examples were used, (1,0.25,0.25) were chosen. For scenarios involving some positive and This is a pre-copyedit version of this article. The final authenticated version is available online at: https://doi.org/10.1007/978-981-96-2054-8_16. Comparative Analysis of Relevance Feedback Techniques for Image Retrieval 9 negative examples, (0.75,1,0.75) were selected for incremental updates, and (0.75,0.75,0.5) for batch updates. –Polyadic Search: With only positive examples, the best parameters were (α, β, γ) = (0.75,0.25,0) for SED, and (0.25,0.75,0) for MSED. When all images in the display were labeled as either positive or negative, (1,0.25,0.25) were optimal for both SED and MSED. For some positive and negative examples, (0.75,0.1,0.75) were used for both SED and MSED. –SVM with the incremental updates: α= 0.5and β= 0.5were optimal for positive examples only, while α= 0.75 and β= 0.25 were best for cases involving both positive and negative examples. –PicHunter/PicHunter⋆: the parameter τin the user model affects the entropy of the probability distribution generated by applying the softmax (or softmin) function to the distances between each data object oiand the displayed images. A high τleads to a near-uniform distribution, while a low τmakes the distribution concentrate on a single element. We estimated τ using η=µ√nD, where µis the average distance between a query and nD random images. We tested τ∈ {0.1η, η, 10η, 100η}, finding that τ= 10η performed best, with ηand 100ηproviding comparable outcomes (no statistically significant differences). Results with τ= 0.1ηyielded poorer results from the second iteration onwards, especially with many positive examples. Therefore, we select τ= 10η(where η= 8.211 for CLIP features). Regarding update types, we made the following observations. For PicHunter, incremental updates showed better performance at iteration 2 when selecting a few new positive examples per iteration, but performed worse from iteration 5 onwards. For PicHunter⋆, there was no statistically significant difference between the incremental and batch updates when all positive and negative images in the display were used. However, incremental updates performed better at iteration 2 but slightly worse from iteration 8 onwards in other scenarios. Consequently, we present results using the batch update for both PicHunter and PicHunter⋆. For Rocchio, when only positive feedback was considered, there were no significant differences between batch and incremental updates. However, with negative feedback included, incremental updates yielded statistically better results in most iterations. Therefore, we used incremental updates for Rocchio. For Polyadic Search, batch and incremental updates generally showed similar performance with only positive feedback, with no significant differences. However, when a few positive and negative examples were used, the batch update had statistically better results than the incremental update for both SED and MSED. This also applies when using MSED with all positive and negative examples in the display. The only exception is SED in this latter feedback scenario, where the incremental updates significantly outperformed batch updates. Given the overall results, we present batch updates for Polyadic Search. For SVM, batch updates consistently provided the best results due to the advantage of training on more data at each iteration.