Mining user web search activity with layered bayesian networks or how to capture a click in its context

ABSTRACT

Mining user web search activity potentially has a broad range of applications including web result pre-fetching, automatic search query reformulation, click spam detection, estimation of document relevance and prediction of user satisfaction. This analysis is difficult because the data recorded by search engines while users interact with them, although abundant, is very noisy. In this work, we explore the utility of mining search behavior of users, represented by observed variables including the time the user spends on the page, and whether the user reformulated his or her query. As a case study, we examine the contribution this data makes to predicting the relevance of a document in the absence of document content models. To this end, we first propose a method for grouping the interactions of a particular user according to the different tasks he or she undertakes. With each task corresponding to a distinct information need, we then propose a Bayesian Network to holistically model these interactions. The aim is to identify distinct patterns of search behaviors. Finally, we join these patterns to a list of custom features and we use gradient boosted decision trees to predict the relevance of a set of query document pairs for which we have relevance assessments. The experimental results confirm the potential of our model, with significant improvements in precision for predicting the relevance of documents based on a model of the user's search and click behavior, over a baseline model using only click and query features, with no Bayesian Network input.

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: Matthew Brand, Structure learning in conditional probability models via an entropic prior and parameter extinction, Neural Computation, v.11 n.5, p.1155-1182, July 1, 1999 [doi>10.1162/089976699300016395]
• 3: Andrei Broder, A taxonomy of web search, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792552]
• 4: B. Carterette and R. Jones. Evaluating search engines by modeling the relationship between relevance and clicks. In NIPS 2007, 2007.
• 5: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via de EM algorithm. The Journal of Royal Statistical Society, 39:1--37, 1977.
• 6: D. Downey, S. T. Dumais, and E. Horvitz. Models of searching and browsing: Languages, studies, and application. In Proceedings of IJCAI 2007, pages 2740--2747, 2007.
• 7: G. Dupret and B. Piwowarski. User behavior and search engine query logs: a generative model to predict clickthrough rate. In Proceedings of SIGIR 2008, 2008.
• 8: J. H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189--1232, 2001.
• 9: Daqing He , Ayse Göker , David J. Harper, Combining evidence for automatic web session identification, Information Processing and Management: an International Journal, v.38 n.5, p.727-742, September 2002 [doi>10.1016/S0306-4573(01)00060-7]
• 10: Diane Kelly , Nicholas J. Belkin, Display time as implicit feedback: understanding task effects, 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.1009057]
• 11: Tessa Lau , Eric Horvitz, Patterns of search: analyzing and modeling Web query refinement, Proceedings of the seventh international conference on User modeling, p.119-128, June 1999, Banff, Canada
• 12: G. Miller, E. Galanter, and K. Pribram. Plans and the structure of behavior. Holt, Rhinehart, & Winston, New York, 1960.
• 13: S. Mizzaro. How many relevances in information retrieval? Interacting With Computers, 10(3):305--322, 1998.
• 14: Seda Ozmutlu, Automatic new topic identification using multiple linear regression, Information Processing and Management: an International Journal, v.42 n.4, p.934-950, July 2006 [doi>10.1016/j.ipm.2005.10.002]
• 15: Filip Radlinski , Thorsten Joachims, Query chains: learning to rank from implicit feedback, Proceedings 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]
• 16: G. Ridgeway. Generalized boosted models: A guide to the gbm package. http://i-pensieri.com/gregr/papers/gbm-vignette.pdf, 2005.
• 17: Xuehua Shen , Bin Tan , ChengXiang Zhai, Implicit user modeling for personalized search, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099747]
• 18: Bin Tan , Xuehua Shen , ChengXiang Zhai, Mining long-term search history to improve search accuracy, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150493]
• 19: Jaime Teevan , Eytan Adar , Rosie Jones , Michael A. S. Potts, Information re-retrieval: repeat queries in Yahoo's logs, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277770]
• 20: Ryen W. White , Steven M. Drucker, Investigating behavioral variability in web search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242576]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
click-through data, query log analysis, relevance prediction, user modelling, web retrieval