Query difficulty estimation via relevance prediction for image retrieval

Query difficulty estimation (QDE) attempts to automatically predict the performance of the search results returned for a given query. QDE has long been of interest in text retrieval. However, few research works have been conducted in image retrieval. Existing QDE methods in image retrieval mainly explore the statistical characteristics (coherence, specificity, etc.) of the returned images to derive a value for indicating the query difficulty degree. To the best of our knowledge, little research has been done to directly estimate the real search performance, such as average precision. In this paper, we propose a novel query difficulty estimation approach which automatically estimates the average precision of the image search results. Specifically, we first adaptively select a set of query relevant and query irrelevant images for each query via modified pseudo relevance feedback. Then a simple but effective voting scheme and two estimation methods (hard estimation and soft estimation) are proposed to estimate the relevance probability of each image in the search results. Based on the images׳ relevance probabilities, the average precision for each query is derived. The experimental results on two benchmark image search datasets demonstrate the effectiveness of the proposed method.