Ingemar J. Cox, Matthew L. Miller, Thomas P. Minka and Peter N. Yianilos,
An Optimized Interaction Strategy for Bayesian Relevance
Feedback,
In Proceedings of the 1998 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'98),
Santa Barbara, California, USA, pp. 553-558, June 1998.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 k-d 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 advantage is reflected by experiments with real users on a database of 1500 stock photographs.