User language model for collaborative personalized search

ABSTRACT

Traditional personalized search approaches rely solely on individual profiles to construct a user model. They are often confronted by two major problems: data sparseness and cold-start for new individuals. Data sparseness refers to the fact that most users only visit a small portion of Web pages and hence a very sparse user-term relationship matrix is generated, while cold-start for new individuals means that the system cannot conduct any personalization without previous browsing history. Recently, community-based approaches were proposed to use the group's social behaviors as a supplement to personalization. However, these approaches only consider the commonality of a group of users and still cannot satisfy the diverse information needs of different users. In this article, we present a new approach, called collaborative personalized search. It considers not only the commonality factor among users for defining group user profiles and global user profiles, but also the specialties of individuals. Then, a statistical user language model is proposed to integrate the individual model, group user model and global user model together. In this way, the probability that a user will like a Web page is calculated through a two-step smoothing mechanism. First, a global user model is used to smooth the probability of unseen terms in the individual profiles and provide aggregated behavior of global users. Then, in order to precisely describe individual interests by looking at the behaviors of similar users, users are clustered into groups and group-user models are constructed. The group-user models are integrated into an overall model through a cluster-based language model. The behaviors of the group users can be utilized to enhance the performance of personalized search. This model can alleviate the two aforementioned problems and provide a more effective personalized search than previous approaches. Large-scale experimental evaluations are conducted to show that the proposed approach substantially improves the relevance of a search over several competitive methods.

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: Allan, J., Carbonell, J., Doddington, G., Yamron, J., and Yang, Y. 1998. Topic detection and tracking pilot study: Final report. In Proceedings of the ARPA Broadcast News Transcription and Understanding Workshop, 194--218.
• 3: Rodrigo B. Almeida , Virgilio A. F. Almeida, A community-aware search engine, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988728]
• 4: Anand, S. S. and Mobasher, B. 2005. Intelligent techniques for web personalization. In Intelligent Techniques for Web Personalization. Bamshad Mobasher and Sarabjot Singh Anand (Eds), Lecture Notes in Artificial Intelligence (3169), Springer, 1--37.
• 5: Peter Anick, Using terminological feedback for web search refinement: a log-based study, 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.860453]
• 6: 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]
• 7: Beaulieu, M., Thien, D., Payne, A., and Jones, S. 1996. Enquire okapi project. British Library Resear. Innov. Rep. 17, 103.
• 8: Belkin, N., Cool, C., Koenemann, J., NG, K. B., and Park, S. 1996. Using relevance feedback and ranking in interactive searching. In Proceedings of 4th Text Retrieval Conference (TREC-4). Harman, D.K., ed. NIST, 181--188.
• 9: Bharat, K. and Kamba, T. 1995. An interactive personalized newspaper on the WWW. In Proceedings of the 4th International Conference on World Wide Web. ACM Press, New York, NY, 159--170.
• 10: Daniel Billsus , Michael J. Pazzani, A hybrid user model for news story classification, Proceedings of the seventh international conference on User modeling, p.99-108, June 1999, Banff, Canada
• 11: Breese, J. S., Heckerman, D., and Kadie, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. 43--52.
• 12: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 13: 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]
• 14: Chen, S. and Goodman, J. 1998. An empirical study of smoothing techniques for language modeling. Tech. Rep. TR-10-98, Computer Science Group, Harvard University.
• 15: Paul Alexandru Chirita , Wolfgang Nejdl , Raluca Paiu , Christian Kohlschütter, Using ODP metadata to personalize search, 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.1076067]
• 16: Mark Claypool , Phong Le , Makoto Wased , David Brown, Implicit interest indicators, Proceedings of the 6th international conference on Intelligent user interfaces, p.33-40, January 14-17, 2001, Santa Fe, New Mexico, United States [doi>10.1145/359784.359836]
• 17: Dempster, A., Laird, N., and Rubin, D. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc. 39, 1, Series B, 1--38.
• 18: Susan Dumais , Edward Cutrell , JJ Cadiz , Gavin Jancke , Raman Sarin , Daniel C. Robbins, Stuff I've seen: a system for personal information retrieval and re-use, 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.860451]
• 19: Danyel Fisher , Kris Hildrum , Jason Hong , Mark Newman , Megan Thomas , Rich Vuduc, SWAMI (poster session): a framework for collaborative filtering algorithm development and evaluation, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.366-368, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345658]
• 20: 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]
• 21: W. B. Frakes, Stemming algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 22: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 23: Hartigan, J. A. and Wong, M. A. 1979. A K-means clustering algorithm. Appl. Statist. 28, 100--108.
• 24: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 25: Thomas Hofmann , Jan Puzicha, Statistical Models for Co-occurrence Data, Massachusetts Institute of Technology, Cambridge, MA, 1998
• 26: Kalervo Järvelin , Jaana Kekäläinen, IR evaluation methods for retrieving highly relevant documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.41-48, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345545]
• 27: Rong Jin , Alex G. Hauptmann , Cheng Xiang Zhai, Title language model for information retrieval, 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.564386]
• 28: 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]
• 29: 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]
• 30: Kerschberg, L., Kim, W., and Scime, A. 2001. WebSifer: Personalizable meta-search agent based on semantic weighted taxonomy tree. In Proceedings of the International Conference on Internet Computing. 14--20.
• 31: Jürgen Koenemann , Nicholas J. Belkin, A case for interaction: a study of interactive information retrieval behavior and effectiveness, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.205-212, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238487]
• 32: Joseph A. Konstan , Bradley N. Miller , David Maltz , Jonathan L. Herlocker , Lee R. Gordon , John Riedl, GroupLens: applying collaborative filtering to Usenet news, Communications of the ACM, v.40 n.3, p.77-87, March 1997 [doi>10.1145/245108.245126]
• 33: Kritikopoulos, A. and Sideri, M. 2003. The compass filter: Search engine results personalization using web communities. In Proceedings of the Workshop on Intelligent Techniques for Web Personalization (ITWP'03), 229--240.
• 34: Krulwich, B. 1997. Lifestyle finder—Intelligent user profiling using large-scale demographic data. AI Mag. 18, 2, 37--45.
• 35: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 36: Victor Lavrenko , W. Bruce Croft, Relevance based language models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.120-127, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383972]
• 37: Xiaoyan Li , W. Bruce Croft, Time-based language models, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956951]
• 38: Lieberman, H. 1995. Letizia: An agent that assists Web browsing. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. 924--929.
• 39: Fang Liu , Clement Yu , Weiyi Meng, Personalized web search by mapping user queries to categories, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584884]
• 40: 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]
• 41: Udi Manber , Ash Patel , John Robison, Experience with personalization of Yahoo!, Communications of the ACM, v.43 n.8, p.35-39, Aug. 2000 [doi>10.1145/345124.345136]
• 42: McLachlan, G. J. and Basford, K. E. 1988. Mixture Models: Inference and Applications to Clustering. Marcel Dekker, New York.
• 43: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 44: Mladenic, D. 1996. Personal Webwatcher: Design and implementation, Tech. Rep. ijs-dp-7472, School of Computer Science, Carnegie-Mellon University, Pittsburgh.
• 45: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 46: Michael J. Pazzani, A Framework for Collaborative, Content-Based and Demographic Filtering, Artificial Intelligence Review, v.13 n.5-6, p.393-408, Dec. 1999 [doi>10.1023/A:1006544522159]
• 47: Pazzani, M., Muramatsu, J., and Billsus, D. 1996. Syskill & Webert: Identifying interesting Web sites. In Proceedings of the 13th National Conference on Artificial Intelligence, 54--61.
• 48: James Pitkow , Hinrich Schütze , Todd Cass , Rob Cooley , Don Turnbull , Andy Edmonds , Eytan Adar , Thomas Breuel, Personalized search, Communications of the ACM, v.45 n.9, September 2002 [doi>10.1145/567498.567526]
• 49: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 50: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 51: S. E. Robertson , S. Walker, Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.232-241, July 03-06, 1994, Dublin, Ireland
• 52: S. E. Robertson , C. J. van Rijsbergen , M. F. Porter, Probabilistic models of indexing and searching, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.35-56, June 23-27, 1980, Cambridge, England
• 53: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 54: Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl, J. T. 2000. Application of dimensionality reduction in recommender system—A case study. In Proceedings of the ACM WebKDD Web Mining for E-Commerce Workshop, 82--90.
• 55: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 56: Shahabi, C. and Chen, Y. S. 2003. Web information personalization: Challenges and approaches. In Proceedings of Databases in Networked Information Systems. 5--15.
• 57: 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]
• 58: Smyth, B., Balfe, E., Briggs, P., Coyle, M., and Freyne, J. 2003. Collaborative Web search. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03).
• 59: Spitters, M. and Kraaij, W. 2001. TNO at TDT2001: Language model-based topic detection. In Topic Detection and Tracking Workshop Report.
• 60: 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]
• 61: Sullivan, D. 2004. Eurekster launches personalized social search. Search engine watch. http://searchenginewatch.com/searchday/article.php/3301481.
• 62: James Surowiecki, The Wisdom of Crowds, Anchor, 2005
• 63: Jaime Teevan , Susan T. Dumais , Eric Horvitz, Personalizing search via automated analysis of interests and activities, 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.1076111]
• 64: Wang, J., de Vries, A. P., and Reinders, M. J. 2006. A user-item relevance model for log-based collaborative filtering. In Proceedings of 28th European Conference on Information Retrieval. 37--48.
• 65: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 66: Gui-Rong Xue , Chenxi Lin , Qiang Yang , WenSi Xi , Hua-Jun Zeng , Yong Yu , Zheng Chen, Scalable collaborative filtering using cluster-based smoothing, 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.1076056]
• 67: Yamron, J. P., Carp, I., Gillick, L., Lowe, S. A., and van Mulbregt, P. 1999. Topic tracking in a news stream. In Proceedings of the DARPA Broadcast News Workshop, San Francisco: Morgan Kaufmann.
• 68: Chun Zeng , Chun-Xiao Xing , Li-Zhu Zhou, Similarity measure and instance selection for collaborative filtering, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775243]
• 69: Chengxiang Zhai , John Lafferty, Model-based feedback in the language modeling approach to information retrieval, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502654]
• 70: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to information retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.179-214, April 2004 [doi>10.1145/984321.984322]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
Collaborative personalized search, clustering, cold-start, data Sparseness, smoothing, user language model