Identifying "best bet" web search results by mining past user behavior

ABSTRACT

The top web search result is crucial for user satisfaction with the web search experience. We argue that the importance of the relevance at the top position necessitates special handling of the top web search result for some queries. We propose an effective approach of leveraging millions of past user interactions with a web search engine to automatically detect "best bet" top results preferred by majority of users. Interestingly, this problem can be more effectively addressed with classification than using state-of-the-art general ranking methods. Furthermore, we show that our general machine learning approach achieves precision comparable to a heavily tuned, domain-specific algorithm, with significantly higher coverage. Our experiments over millions of user interactions for thousands of queries demonstrate the effectiveness and robustness of our techniques.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais , Robert Ragno, Learning user interaction models for predicting web search result preferences, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148175]
• 2: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 6: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 7: D. M. Chickering, The WinMine Toolkit, Microsoft Technical Report MSR-TR-2002-103, 2002
• 8: Mark Claypool , David Brown , Phong Le , Makoto Waseda, Inferring User Interest, IEEE Internet Computing, v.5 n.6, p.32-39, November 2001 [doi>10.1109/4236.968829]
• 9: Steve Fox , Kuldeep Karnawat , Mark Mydland , Susan Dumais , Thomas White, Evaluating implicit measures to improve web search, ACM Transactions on Information Systems (TOIS), v.23 n.2, p.147-168, April 2005 [doi>10.1145/1059981.1059982]
• 10: J. Goecks and J. Shavlick. Learning users' interests by unobtrusively observing their normal behavior. In the Proceedings of the IJCAI Workshop on Machine Learning for Information Filtering. 1999.
• 11: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 12: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 13: 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]
• 14: Uichin Lee , Zhenyu Liu , Junghoo Cho, Automatic identification of user goals in Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060804]
• 15: 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
• 16: D. Oard and J. Kim. Implicit feedback for recommender systems. In the Proceedings of the AAAI Workshop on Recommender Systems. 1998
• 17: D. Oard and J. Kim. Modeling information content using observable behavior. In Proceedings of the 64th Annual Meeting of the American Society for Information Science and Technology. 2001
• 18: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081899]
• 19: Daniel E. Rose , Danny Levinson, Understanding user goals in web search, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988675]
• 20: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 21: Xuehua Shen , ChengXiang Zhai, Active feedback in ad hoc information retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076047]
• 22: Xuehua Shen , Bin Tan , ChengXiang Zhai, Context-sensitive information retrieval using implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076045]
• 23: E. M. Voorhees, D. Harman, Overview of TREC, 2001
• 24: Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Yong Yu , Wei-Ying Ma , WenSi Xi , WeiGuo Fan, Optimizing web search using web click-through data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031192]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Relevance feedback
      H.3.5 On-line Information Services
          Subjects: Web-based services; Commercial services

General Terms:
Algorithms, Design, Measurement

Keywords:
user behavior mining, web search ranking, web usage mining