Matchbox: large scale online bayesian recommendations

ABSTRACT

We present a probabilistic model for generating personalised recommendations of items to users of a web service. The Matchbox system makes use of content information in the form of user and item meta data in combination with collaborative filtering information from previous user behavior in order to predict the value of an item for a user. Users and items are represented by feature vectors which are mapped into a low-dimensional `trait space' in which similarity is measured in terms of inner products. The model can be trained from different types of feedback in order to learn user-item preferences. Here we present three alternatives: direct observation of an absolute rating each user gives to some items, observation of a binary preference (like/ don't like) and observation of a set of ordinal ratings on a user-specific scale. Efficient inference is achieved by approximate message passing involving a combination of Expectation Propagation (EP) and Variational Message Passing. We also include a dynamics model which allows an item's popularity, a user's taste or a user's personal rating scale to drift over time. By using Assumed-Density Filtering (ADF) for training, the model requires only a single pass through the training data. This is an on-line learning algorithm capable of incrementally taking account of new data so the system can immediately reflect the latest user preferences. We evaluate the performance of the algorithm on the MovieLens and Netflix data sets consisting of approximately 1,000,000 and 100,000,000 ratings respectively. This demonstrates that training the model using the on-line ADF approach yields state-of-the-art performance with the option of improving performance further if computational resources are available by performing multiple EP passes over the training data.

REFERENCES

• 1: Netflix Cinematch: http://www.netflix.com.
• 2: Robert M. Bell , Yehuda Koren, Lessons from the Netflix prize challenge, ACM SIGKDD Explorations Newsletter, v.9 n.2, December 2007 [doi>10.1145/1345448.1345465]
• 3: J. S. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th ACM Conference on Uncertainty in Artificial Intelligence, pages 34--52, 1998.
• 4: Wei Chu , Zoubin Ghahramani, Gaussian Processes for Ordinal Regression, The Journal of Machine Learning Research, 6, p.1019-1041, 12/1/2005
• 5: P. Dangauthier, R. Herbrich, T. Minka, and T. Graepel. Trueskill through time: Revisiting the history of chess. In Advances in Neural Information Processing Systems 20, pages 337--344, 2008.
• 6: 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]
• 7: 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]
• 8: R. Herbrich, T. Minka, and T. Graepel. TrueSkill(TM): A Bayesian skill rating system. In Advances in Neural Information Processing Systems 20, pages 569--576, 2007.
• 9: M. K. Hughey , M. W. Berry, Improved Query Matching Using kd-Trees: A Latent Semantic Indexing Enhancement, Information Retrieval, v.2 n.4, p.287-302, May 2000 [doi>10.1023/A:1009915010963]
• 10: F. R. Kschischang, B. Frey, and H.-A. Loeliger. Factor graphs and the sum--product algorithm. IEEE Trans. Inform. Theory, 47(2):498--519, 2001.
• 11: Xuan Nhat Lam , Thuc Vu , Trong Duc Le , Anh Duc Duong, Addressing cold-start problem in recommendation systems, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea [doi>10.1145/1352793.1352837]
• 12: Y. J. Lim and Y. W. Teh. Variational Bayesian approach to movie rating prediction. In Proceedings of KDD Cup and Workshop, 2007.
• 13: Benjamin Marlin. Collaborative filtering: A machine learning perspective. Master's thesis, University of Toronto, 2004.
• 14: T. Minka. Divergence measures and message passing. Technical Report MSR-TR-2007-173, Microsoft Research Ltd., 2005.
• 15: T. Minka, J.M. Winn, J.P. Guiver, and A. Kannan. Infer.NET 2.2, 2009. Microsoft Research Cambridge. http://research.microsoft.com/infernet.
• 16: Thomas P. Minka , Rosalind Picard, A family of algorithms for approximate bayesian inference, Massachusetts Institute of Technology, 2001
• 17: Ruslan Salakhutdinov , Andriy Mnih , Geoffrey Hinton, Restricted Boltzmann machines for collaborative filtering, Proceedings of the 24th international conference on Machine learning, p.791-798, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273596]
• 18: J. Ben Schafer , Joseph Konstan , John Riedi, Recommender systems in e-commerce, Proceedings of the 1st ACM conference on Electronic commerce, p.158-166, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337035]
• 19: Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]
• 20: J. M. Winn. Variational message passing and its application. PhD thesis, Department of Physics, University of Cambridge, 2003.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
advertising, bayesian inference, collaborative filtering, machine learning, online services, recommender system