Relevance and irrelevance graph based marginal Fisher analysis for image search reranking

• This paper presents a novel “Ranking Dimensionality Reduction” scheme and two dimensionality reduction algorithms.
• The proposed scheme discovers the intrinsic structure of data and keeps the ordinal information in ranking and retrieval.
• The proposed RMFA algorithm models the pairwise constraints of relevance-link and irrelevance-link into the relevance graph and irrelevance graph.
• The proposed Semi-RMFA algorithm offers a more general solution for the real-world application.
• The promising results on two popular, real-world image datasets demonstrate the robustness and effectiveness of the proposed scheme and algorithms.

Learning-to-rank techniques have shown promising results in the domain of image ranking recently, where dimensionality reduction is a critical step to overcome the “curse of dimensionality”. However, conventional dimensionality reduction approaches cannot guarantee the satisfying performance because the important ranking information is ignored. This paper presents a novel “Ranking Dimensionality Reduction” scheme specifically designed for learning-to-rank based image ranking, which aims at not only discovering the intrinsic structure of data but also keeping the ordinal information. Within this scheme, a new dimensionality reduction algorithm called Relevance Marginal Fisher Analysis (RMFA) is proposed. RMFA models the proposed pairwise constraints of relevance-link and irrelevance-link into the relevance graph and the irrelevance graph, and applies the graphs to build the objective function with the idea of Marginal Fisher Analysis (MFA). Further, a semi-supervised RMFA algorithm called Semi-RMFA is developed to offer a more general solution for the real-world application. Extensive experiments are carried on two popular, real-world image search reranking datasets. The promising results demonstrate the robustness and effectiveness of the proposed scheme and methods.