Evaluating implicit feedback models using searcher simulations

ABSTRACT

In this article we describe an evaluation of relevance feedback (RF) algorithms using searcher simulations. Since these algorithms select additional terms for query modification based on inferences made from searcher interaction, not on relevance information searchers explicitly provide (as in traditional RF), we refer to them as implicit feedback models. We introduce six different models that base their decisions on the interactions of searchers and use different approaches to rank query modification terms. The aim of this article is to determine which of these models should be used to assist searchers in the systems we develop. To evaluate these models we used searcher simulations that afforded us more control over the experimental conditions than experiments with human subjects and allowed complex interaction to be modeled without the need for costly human experimentation. The simulation-based evaluation methodology measures how well the models learn the distribution of terms across relevant documents (i.e., learn what information is relevant) and how well they improve search effectiveness (i.e., create effective search queries). Our findings show that an implicit feedback model based on Jeffrey's rule of conditioning outperformed other models under investigation.

REFERENCES

• 1: Carol L. Barry, Document representations and clues to document relevance, Journal of the American Society for Information Science, v.49 n.14, p.1293-1303, Dec. 1998 [doi>10.1002/(SICI)1097-4571(1998)49:14<1293::AID-ASI7>3.3.CO;2-5]
• 2: Borlund, P. 2003. The IIR evaluation model: A framework for evaluation of interactive information retrieval systems. Inform. Res. 8, 3. Available online at http://informationr.net/ir/8-3/paper152.html R2.10.
• 3: Chris Buckley , Gerard Salton , James Allan, The effect of adding relevance information in a relevance feedback environment, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.292-300, July 03-06, 1994, Dublin, Ireland
• 4: Campbell, I. 2000. The Ostensive Model of Developing Information Needs. Unpublished doctoral dissertation. University of Glasgow, Glasgow, U.K.
• 5: Campbell, I. and Van Rijsbergen, C. J. 1996. The ostensive model of developing information needs. In Proceedings of the 3rd International Conference on Conceptions of Library and Information Science. 251--268.
• 6: Matthew Chalmers , Kerry Rodden , Dominique Brodbeck, The order of things: activity-centered information access, Computer Networks and ISDN Systems, v.30 n.1-7, p.359-367, April 1, 1998
• 7: Ed H. Chi , Peter Pirolli , Kim Chen , James Pitkow, Using information scent to model user information needs and actions and the Web, Proceedings of the SIGCHI conference on Human factors in computing systems, p.490-497, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365325]
• 8: Ed H. Chi , Adam Rosien , Gesara Supattanasiri , Amanda Williams , Christiaan Royer , Celia Chow , Erica Robles , Brinda Dalal , Julie Chen , Steve Cousins, The bloodhound project: automating discovery of web usability issues using the InfoScentπ simulator, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/642611.642699]
• 9: Erica Cosijn , Peter Ingwersen, Dimensions of relevance, Information Processing and Management: an International Journal, v.36 n.4, p.533-550, July 2000 [doi>10.1016/S0306-4573(99)00072-2]
• 10: Jonathan Furner, On recommending, Journal of the American Society for Information Science and Technology, v.53 n.9, p.747-763, August 2002 [doi>10.1002/asi.10080]
• 11: Hamming, R. W. 1950. Error-detecting and error-correcting codes. Bell Syst. Tech. J. 29, 147--160.
• 12: D. Harman, Towards interactive query expansion, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.321-331, May 1988, Grenoble, France [doi>10.1145/62437.62469]
• 13: Donna Harman, Overview of the first TREC conference, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.36-47, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160692]
• 14: Harper, D. J. 1980. Relevance Feedback in Document Retrieval Systems. Unpublished doctoral dissertation. University of Cambridge, Cambridge, U.K.
• 15: Bernard J. Jansen , Amanda Spink , Tefko Saracevic, Real life, real users, and real needs: a study and analysis of user queries on the web, Information Processing and Management: an International Journal, v.36 n.2, p.207-227, Jan.1.2000 [doi>10.1016/S0306-4573(99)00056-4]
• 16: Jeffrey, R. C. 1983. The Logic of Decision. Chicago: University of Chicago Press, Chicago, IL.
• 17: Joyce Diane Kelly , Nicholas J. Belkin, Understanding implicit feedback and document preference: a naturalistic user study, 2004
• 18: Diane Kelly , Jaime Teevan, Implicit feedback for inferring user preference: a bibliography, ACM SIGIR Forum, v.37 n.2, p.18-28, Fall 2003 [doi>10.1145/959258.959260]
• 19: W. Lam , S. Mukhopadhyay , J. Mostafa , M. Palakal, Detection of shifts in user interests for personalized information filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.317-325, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243279]
• 20: Mark Magennis , Cornelis J. van Rijsbergen, The potential and actual effectiveness of interactive query expansion, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.324-332, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 21: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 22: Masahiro Morita , Yoichi Shinoda, Information filtering based on user behavior analysis and best match text retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.272-281, July 03-06, 1994, Dublin, Ireland
• 23: Javed Mostafa , Snehasis Mukhopadhyay , Mathew Palakal, Simulation Studies of Different Dimensions of Users' Interests and their Impact on User Modeling and Information Filtering, Information Retrieval, v.6 n.2, p.199-223, April 2003 [doi>10.1023/A:1023932221048]
• 24: Tim Paek , Susan Dumais , Ron Logan, WaveLens: a new view onto Internet search results, Proceedings of the SIGCHI conference on Human factors in computing systems, p.727-734, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985784]
• 25: Peter Pirolli , Stuart Card, Information foraging in information access environments, Proceedings of the SIGCHI conference on Human factors in computing systems, p.51-58, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223911]
• 26: Robertson, S. E. 1986. On relevance weight estimation and query expansion. J. Documentat. 42, 182--188.
• 27: S. E. Robertson, On term selection for query expansion, Journal of Documentation, v.46 n.4, p.359-364, Dec. 1990 [doi>10.1108/eb026866]
• 28: Ian Ruthven, Re-examining the potential effectiveness of interactive query expansion, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860475]
• 29: Ian Ruthven , Mounia Lalmas , Keith Van Rijsbergen, Incorporating user search behavior into relevance feedback, Journal of the American Society for Information Science and Technology, v.54 n.6, p.529-549, April 2003 [doi>10.1002/asi.10240]
• 30: G. Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 31: Salton, G. and Buckley, C. 1990. Improving retrieval performance by relevance feedback. J. Amer. Soc. Inform. Sci. 41, 4, 288--297.
• 32: Saracevic, T. 1975. Relevance: A review of and a framework for thinking on the notion of information science. J. Amer. Soc. Inform. Sci. 26, 6, 321--343.
• 33: Siegel, S. and Castellan, N. J. 1988. Nonparametric Statistics for the Behavioural Sciences. McGraw-Hill, New York, NY.
• 34: Amanda Spink , Howard Greisdorf , Judy Bateman, From highly relevant to not relevant: examining different regions of relevance, Information Processing and Management: an International Journal, v.34 n.5, p.599-621, Sept. 1998 [doi>10.1016/S0306-4573(98)00025-9]
• 35: Anastasios Tombros , Mark Sanderson, Advantages of query biased summaries in information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.2-10, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290947]
• 36: C. J. van Rijsbergen, Probabilistic retrieval revisited, The Computer Journal, v.35 n.3, p.291-298, June 1992 [doi>10.1093/comjnl/35.3.291]
• 37: White, R. W. 2004. Implicit Feedback for Interactive Information Retrieval. Unpublished doctoral dissertation. University of Glasgow, Glasgow, U.K.
• 38: Ryen W. White , Joemon M. Jose, A study of topic similarity measures, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009100]
• 39: Ryen W. White , Joemon M. Jose , Ian Ruthven, An approach for implicitly detecting information needs, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956959]
• 40: Ryen W. White , Joemon M. Jose , Ian Ruthven, A task-oriented study on the influencing effects of query-biased summarisation in web searching, Information Processing and Management: an International Journal, v.39 n.5, p.707-733, September 2003 [doi>10.1016/S0306-4573(02)00033-X]
• 41: White, R. W., Jose, J. M., and Ruthven, I. 2004a. An implicit feedback approach for interactive information retrieval. Inform. Process. Manage. In press.
• 42: Ryen W. White , Joemon M. Jose , Ian Ruthven, Using top-ranking sentences to facilitate effective information access: Book Reviews, Journal of the American Society for Information Science and Technology, v.56 n.10, p.1113-1125, August 2005 [doi>10.1002/asi.v56:10]
• 43: White, R. W., Jose, J. M., Van Rijsbergen, C. J., and Ruthven, I. 2004c. A simulated study of implicit feedback models. In Proceedings of the 26th Annual European Conference on Information Retrieval. 311--326.
• 44: Ryen W. White , Ian Ruthven , Joemon M. Jose, Finding relevant documents using top ranking sentences: an evaluation of two alternative schemes, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564389]
• 45: Ryen White , Ian Ruthven , Joemon M. Jose, The Use of Implicit Evidence for Relevance Feedback in Web Retrieval, Proceedings of the 24th BCS-IRSG European Colloquium on IR Research: Advances in Information Retrieval, p.93-109, March 25-27, 2002
• 46: Polle T. Zellweger , Susan Harkness Regli , Jock D. Mackinlay , Bay-Wei Chang, The impact of fluid documents on reading and browsing: an observational study, Proceedings of the SIGCHI conference on Human factors in computing systems, p.249-256, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332440]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Evaluation/methodology

General Terms:
Experimentation

Keywords:
User simulations, evaluation, implicit feedback, relevance feedback