Fast nonparametric matrix factorization for large-scale collaborative filtering

ABSTRACT

With the sheer growth of online user data, it becomes challenging to develop preference learning algorithms that are sufficiently flexible in modeling but also affordable in computation. In this paper we develop nonparametric matrix factorization methods by allowing the latent factors of two low-rank matrix factorization methods, the singular value decomposition (SVD) and probabilistic principal component analysis (pPCA), to be data-driven, with the dimensionality increasing with data size. We show that the formulations of the two nonparametric models are very similar, and their optimizations share similar procedures. Compared to traditional parametric low-rank methods, nonparametric models are appealing for their flexibility in modeling complex data dependencies. However, this modeling advantage comes at a computational price--it is highly challenging to scale them to large-scale problems, hampering their application to applications such as collaborative filtering. In this paper we introduce novel optimization algorithms, which are simple to implement, which allow learning both nonparametric matrix factorization models to be highly efficient on large-scale problems. Our experiments on EachMovie and Netflix, the two largest public benchmarks to date, demonstrate that the nonparametric models make more accurate predictions of user ratings, and are computationally comparable or sometimes even faster in training, in comparison with previous state-of-the-art parametric matrix factorization models.

REFERENCES

• 1: J. Abernethy, F. Bach, T. Evgeniou, and J.-P. Vert. Low-rank matrix factorization with attributes. Technical report, Ecole des Mines de Paris, 2006.
• 2: R. M. Bell, Y. Koren, and C. Volinsky. The BellKor solution to the Netflix prize. Technical report, AT&T Labs, 2007.
• 3: E. J. Cand`es and T. Tao. The power of convex relaxation: Near-optimal matrix completion. Submitted for publication, 2009.
• 4: Dennis DeCoste, Collaborative prediction using ensembles of Maximum Margin Matrix Factorizations, Proceedings of the 23rd international conference on Machine learning, p.249-256, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143876]
• 5: M. Kurucz, A. A. Benczur, and K. Csalogany. Methods for large scale SVD with missing values. In Proceedings of KDD Cup and Workshop, 2007.
• 6: Y. J. Lim and Y. W. Teh. Variational Bayesian approach to movie rating prediction. In Proceedings of KDD Cup and Workshop, 2007.
• 7: Carl Edward Rasmussen , Christopher K. I. Williams, Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning), The MIT Press, 2005
• 8: Jasson D. M. Rennie , Nathan Srebro, Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd international conference on Machine learning, p.713-719, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102441]
• 9: Sam Roweis , Zoubin Ghahramani, A unifying review of linear Gaussian models, Neural Computation, v.11 n.2, p.305-345, Feb. 15, 1999 [doi>10.1162/089976699300016674]
• 10: Ruslan Salakhutdinov , Andriy Mnih, Bayesian probabilistic matrix factorization using Markov chain Monte Carlo, Proceedings of the 25th international conference on Machine learning, p.880-887, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390267]
• 11: B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, 2002.
• 12: N. Srebro, J. D. M. Rennie, and T. S. Jaakola. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems 18 (NIPS), 2005.
• 13: G. Takacs, I. Pilaszy, B. Nemeth, and D. Tikk. On the gravity recommendation system. In Proceedings of KDD Cup and Workshop, 2007.
• 14: M. E. Tipping and C. M. Bishop. Probabilistic principal component analysis. Journal of the Royal Statisitical Scoiety, B(61):611--622, 1999.
• 15: M. Wu. Collaborative filtering via ensembles of matrix factorizations. In Proceedings of KDD Cup and Workshop, 2007.
• 16: Kai Yu , John Lafferty , Shenghuo Zhu , Yihong Gong, Large-scale collaborative prediction using a nonparametric random effects model, Proceedings of the 26th Annual International Conference on Machine Learning, p.1185-1192, June 14-18, 2009, Montreal, Quebec, Canada [doi>10.1145/1553374.1553525]
• 17: K. Yu and V. Tresp. Learning to learn and collaborative filtering. In NIPS workshop on "Inductive Transfer: 10 Years Later", 2005.
• 18: Yi Zhang , Jonathan Koren, Efficient bayesian hierarchical user modeling for recommendation system, 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.1277752]

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
collaborative filtering, matrix factorization, nonparametric models