Towards context-aware search by learning a very large variable length hidden markov model from search logs

ABSTRACT

Capturing the context of a user's query from the previous queries and clicks in the same session may help understand the user's information need. A context-aware approach to document re-ranking, query suggestion, and URL recommendation may improve users' search experience substantially. In this paper, we propose a general approach to context-aware search. To capture contexts of queries, we learn a variable length Hidden Markov Model (vlHMM) from search sessions extracted from log data. Although the mathematical model is intuitive, how to learn a large vlHMM with millions of states from hundreds of millions of search sessions poses a grand challenge. We develop a strategy for parameter initialization in vlHMM learning which can greatly reduce the number of parameters to be estimated in practice. We also devise a method for distributed vlHMM learning under the map-reduce model. We test our approach on a real data set consisting of 1.8 billion queries, 2.6 billion clicks, and 840 million search sessions, and evaluate the effectiveness of the vlHMM learned from the real data on three search applications: document re-ranking, query suggestion, and URL recommendation. The experimental results show that our approach is both effective and efficient.

REFERENCES

• 1: Baeza-Yates, R.A., et al. Query recommendation using query logs in search engines. In EDBT 2004 Workshop on Clustering Information over the Web, pages 588--596, 2004.
• 2: Ricardo Baeza-Yates , Alessandro Tiberi, Extracting semantic relations from query logs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281204]
• 3: Jing Bai , Jian-Yun Nie , Guihong Cao , Hugues Bouchard, Using query contexts in information retrieval, 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.1277747]
• 4: Baum, L.E., et al. A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains. Ann. Math. Statist., 41(1):164--171, 1970.
• 5: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 6: Huanhuan Cao , Daxin Jiang , Jian Pei , Qi He , Zhen Liao , Enhong Chen , Hang Li, Context-aware query suggestion by mining click-through and session data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401995]
• 7: Paul - Alexandru Chirita , Claudiu S. Firan , Wolfgang Nejdl, Personalized query expansion for the web, 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.1277746]
• 8: Chu, C.T., et al. Map-reduce for machine learning on multicore. In NIPS, pages 281--288, 2006.
• 9: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 10: Dempster, A.P., et al. Maximal Likelihood from Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society, Ser B(39):1--38, 1977.
• 11: Durbin, R., et al. Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.
• 12: Bruno M. Fonseca , Paulo Golgher , Bruno Pôssas , Berthier Ribeiro-Neto , Nivio Ziviani, Concept-based interactive query expansion, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099726]
• 13: Chien-Kang Huang , Lee-Feng Chien , Yen-Jen Oyang, Relevant term suggestion in interactive web search based on contextual information in query session logs, Journal of the American Society for Information Science and Technology, v.54 n.7, p.638-649, May 2003 [doi>10.1002/asi.10256]
• 14: 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]
• 15: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 16: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, 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.1009026]
• 17: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 18: Rocchio, J. Relevance feedback information retrieval. Prentice-Hall Inc., 1971.
• 19: Kazunari Sugiyama , Kenji Hatano , Masatoshi Yoshikawa, Adaptive web search based on user profile constructed without any effort from users, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988764]
• 20: Tao Tao , ChengXiang Zhai, A two-stage mixture model for pseudo feedback, 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.1009083]
• 21: Yi Wang , Lizhu Zhou , Jianhua Feng , Jianyong Wang , Zhi-Qiang Liu, Mining Complex Time-Series Data by Learning Markovian Models, Proceedings of the Sixth International Conference on Data Mining, p.1136-1140, December 18-22, 2006 [doi>10.1109/ICDM.2006.105]
• 22: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Clustering user queries of a search engine, Proceedings of the 10th international conference on World Wide Web, p.162-168, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371974]
• 23: Ryen W. White , Mikhail Bilenko , Silviu Cucerzan, Studying the use of popular destinations to enhance web search interaction, 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.1277771]
• 24: Jun Xu , Hang Li, AdaRank: a boosting algorithm for information retrieval, 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.1277809]
• 25: Zhao, M., et al. Adapting document ranking to users preferences using click-through Data. In AIRS'06, pages 26--42, 2006.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
context-aware search, variable length hidden Markov model