A low-order markov model integrating long-distance histories for collaborative recommender systems

ABSTRACT

Recommender systems provide users with pertinent resources according to their context and their profiles, by applying statistical and knowledge discovery techniques. This paper describes a new approach of generating suitable recommendations based on the active user's navigation stream, by considering long and short-distance resources in the history with a tractable model.

The Skipping Based Recommender we propose uses Markov models inspired from the ones used in language modeling while integrating skipping techniques to handle noise during navigation. Weighting schemes are also used to alleviate the importance of distant resources. This recommender has also the characteristic to be anytime.

It has been tested on a browsing dataset extracted from Intranet logs provided by a French bank. Results show that the use of exponential decay weighting schemes when taking into account non contiguous resources to compute recommendations enhances the accuracy. Moreover, the skipping variant we propose provides a high accuracy while being less complex than state of the art variants.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 3: L. Bahl, F. Jelinek, and R. Mercer. A Maximum Likelihood Approach to Continuous Speech Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 179--190, 1983.
• 4: Azer Bestavros, Using speculation to reduce server load and service time on the WWW, Proceedings of the fourth international conference on Information and knowledge management, p.403-410, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221653]
• 5: Geoffray Bonnin , Armelle Brun , Anne Boyer, Using Skipping for Sequence-Based Collaborative Filtering, Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, p.775-779, December 09-12, 2008 [doi>10.1109/WIIAT.2008.280]
• 6: A. Brun and A. Boyer. Usage Based Indexing of Web Resources with Natural Language Processing. Proceedings of the European Conference on Information Retrieval, 2007.
• 7: S. Chan and J. Goodman. An Empirical Study of Smoothing Techniques for Language Modeling. Technical report, 1998.
• 8: S. Chen and J. Goodman. An Empirical Study of Smoothing Techniques for Language Modeling. Computer Speech and Language, pages 359--394, 1999.
• 9: Y. Chen and K. Chan. Extended Multi-word Trigger Pair Language Model using Data Mining Technique. IEEE International Conference on Systems, Man and Cybernetics, pages 262--267, 2003.
• 10: Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242610]
• 11: Mukund Deshpande , George Karypis, Selective Markov models for predicting Web page accesses, ACM Transactions on Internet Technology (TOIT), v.4 n.2, p.163-184, May 2004 [doi>10.1145/990301.990304]
• 12: Xiaobin Fu , Jay Budzik , Kristian J. Hammond, Mining navigation history for recommendation, Proceedings of the 5th international conference on Intelligent user interfaces, p.106-112, January 09-12, 2000, New Orleans, Louisiana, United States [doi>10.1145/325737.325796]
• 13: Jianfeng Gao , Hisami Suzuki , Yang Wen, Exploiting headword dependency and predictive clustering for language modeling, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.248-256, July 06, 2002 [doi>10.3115/1118693.1118725]
• 14: David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
• 15: Xin Jin , Bamshad Mobasher , Yanzan Zhou, A Web Recommendation System Based on Maximum Entropy, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume I, p.213-218, April 04-06, 2005 [doi>10.1109/ITCC.2005.53]
• 16: L. Lu, M. Dunham, and Y. Meng. Mining Significant Usage Patterns from Clickstream Data. In 7th International Workshop on Knowledge Discovery on the Web, pages 1--17, 2005.
• 17: B. Mobasher. Data Mining for Web Personalization, chapter 3. 2007.
• 18: M. Nakagawa and B. Mobasher. Impact of Site Characteristics on Recommendation Models Based On Association Rules and Sequental Patterns. In Proceedings of the IJCAI'03 Workshop on Intelligent Techniques for Web Personalization, 2003.
• 19: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]
• 20: Dmitry Pavlov , Eren Manavoglu , David M. Pennock , C. Lee Giles, Collaborative Filtering with Maximum Entropy, IEEE Intelligent Systems, v.19 n.6, p.40-48, November 2004 [doi>10.1109/MIS.2004.59]
• 21: Peter L. T. Pirolli , James E. Pitkow, Distributions of surfers’ paths through the World Wide Web: Empirical characterizations, World Wide Web, v.2 n.1-2, p.29-45, 1999 [doi>10.1023/A:1019288403823]
• 22: James Pitkow , Peter Pirolli, Mining longest repeating subsequences to predict world wide web surfing, Proceedings of the 2nd conference on USENIX Symposium on Internet Technologies and Systems, p.13-13, October 11-14, 1999, Boulder, Colorado
• 23: R. Rosenfeld. Adaptive Statistical Language Modeling: A Maximum Entropy Approach. PhD thesis, Computer Science Department, Carnegie Mellon University, 1994.
• 24: R. Rosenfeld. Two decades of Statistical Language Modeling: Where do we go from here? Proceedings of the IEEE, pages 1270--1278, 2000.
• 25: Ronald Rosenfeld , Xuedong Huang, Improvements in stochastic language modeling, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York [doi>10.3115/1075527.1075552]
• 26: Badrul Sarwar , George Karypis , Joseph Konstan , John Riedl, Analysis of recommendation algorithms for e-commerce, Proceedings of the 2nd ACM conference on Electronic commerce, p.158-167, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352887]
• 27: Guy Shani , David Heckerman , Ronen I. Brafman, An MDP-Based Recommender System, The Journal of Machine Learning Research, 6, p.1265-1295, 12/1/2005
• 28: Mei-Ling Shyu , Choochart Haruechaiyasak , Shu-Ching Chen , Na Zhao, Collaborative Filtering by Mining Association Rules from User Access Sequences, Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration, p.128-135, April 08-09, 2005
• 29: L. Ungar and D. Foster. Clustering Methods for Collaborative Filtering. In Proceedings of the AAI98 Workshop on Recommendation Systems, 1998.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
markov models, recommender systems, skipping, weighting schemes