Optimizing Visual Search Reranking via Pairwise Learning

Visual search reranking is defined as reordering visual documents (images or video clips) based on the initial search results or some auxiliary knowledge to improve the search precision. Conventional approaches to visual search reranking empirically take the “classification performance” as the optimization objective, in which each visual document is determined relevant or not, followed by a process of increasing the order of relevant documents. In this paper, we first show that the classification performance fails to produce a globally optimal ranked list, and then we formulate reranking as an optimization problem, in which a ranked list is globally optimal only if any arbitrary two documents in the list are correctly ranked in terms of relevance. This is different from existing approaches which simply classify a document as “relevant” or not. To find the optimal ranked list, we convert the individual documents to “document pairs,” each represented as a “ordinal relation.” Then, we find the optimal document pairs which can maximally preserve the initial rank order while simultaneously keeping the consistency with the auxiliary knowledge mined from query examples and web resources as much as possible. We develop two pairwise reranking methods, difference pairwise reranking (DP-reranking) and exclusion pairwise reranking (EP-reranking), to obtain the relevant relation of each document pair. Finally, a round robin criterion is explored to recover the final ranked list. We conducted comprehensive experiments on an automatic video search task over TRECVID 2005-2007 benchmarks, and showed consistent improvements over text search baseline and other reranking approaches.