CVPR'98 1998

An Optimized Interaction Strategy for Bayesian Relevance Feedback

Ingemar J. Cox and Matthew L. Miller and Thomas P. Minka and Peter N. Yianilos

Abstract: A new algorithm and systematic evaluation is presented for searching a database via relevance feedback. It represents a new image display strategy for the PicHunter system [2,1]. The algorithm takes feedback in the form of relative judgments ("item A is more relevant than item B") as opposed to the stronger assumption of categorical relevance judgments ("item A is relevant but item B is not"). It also exploits a learned probabilistic model of human behavior to make better use of the feedback it obtains. The algorithm can be viewed as an extension of indexing schemes like the kd-tree to a stochastic setting, hence the name "stochastic comparison search". In simulations, the amount of feedback required for the new algorithm scales like log_2 |D|, where |D| is the size of the database, while a simple query-by-example approach scales like |D|^a, where a < 1 depends on the structure of the database. This theoretical advantae is reflected by experiments with real users on a database of 1500 stock photographs.