Max-sum diversification on image ranking with non-uniform matroid constraints

Different from conventional retrieval methods that focus on presenting users with relevant results, diversified ranking algorithms aim to provide a non-redundant and rich topic coverage of information in the top ranked list. Most existing approaches for diversified image ranking require a two-step process: (1) a set of potentially relevant images is determined; (2) these images are re-ranked to be diverse. However, the diversified ranking lists obtained from these methods are under the uniform constraint, which treats each image equally important. As such, the final diversified ranking list may come from one or several limited number of categories, where they are the most relevant to the query, rather than exhibiting a wide range of categories to the users. Motivated by this, in this paper, we propose a novel diversified ranking algorithm on image retrieval associated with a non-uniform matroid constraint (each image is weighted differently according to the category it belongs to, and the partition matroid constraints are posed on each category) to leverage the relevance and diversity in an optimized fashion, which jointly captures the relevance and diversity. We introduce hardness coefficient that can automatically set the weight parameters regarding each image to meet the requirement of non-uniform matroid partition constraints. We study our method regarding both in-sample queries and out-of-sample queries. For in-sample queries, we prove that maximizing the proposed objective function is NP-hard. As a result, we find a near-optimal solution with a guaranteed approximation ratio. To tackle the case of out-of-sample queries, four strategies are investigated. Extensive experimental evaluations on real image data sets demonstrate the effectiveness and efficiency of our method.

Research highlights
► A novel diversified ranking algorithm associated with a non-uniform matroid constraint.
► The algorithm leverages the relevance and diversity in an optimized way.
► A submodular function is proposed to capture the relevance and diversity directly and jointly.
► The partition matroid is used to ensure retrieved images come from a variety of different sources.
► We present fruitful theoretical proof and analysis.