Using mixture models for collaborative filtering

ABSTRACT

A collaborative filtering system at an e-commerce site or similar service uses data about aggregate user behavior to make recommendations tailored to specific user interests. We develop recommendation algorithms with provable performance guarantees in a probabilistic mixture model for collaborative filtering proposed by Hoffman and Puzicha. We identify certain novel parameters of mixture models that are closely connected with the best achievable performance of a recommendation algorithm; we show that for any system in which these parameters are bounded, it is possible to give recommendations whose quality converges to optimal as the amount of data grows.All our bounds depend on a new measure of independence that can be viewed as an L1-analogue of the smallest singular value of a matrix. Using this, we introduce a technique based on generalized pseudoinverse matrices and linear programming for handling sets of high-dimensional vectors. We also show that standard approaches based on L2-spectral methods are not strong enough to yield comparable results, thereby suggesting some inherent limitations of spectral analysis.

REFERENCES

• 1: J. Breese, D. Heckerman, C. Kadie "Empirical Analysis of Predictive Algorithms for Collaborative Filtering," In Proc. 14th Conference on Uncertainty in Artificial Intelligence, 1998
• 2: Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia "Spectral analysis of data" Proc. ACM Symposium on Theory of Computing, 2000
• 3: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 4: Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509922]
• 5: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 6: Thomas Hofmann , Jan Puzicha, Latent Class Models for Collaborative Filtering, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.688-693, July 31-August 06, 1999
• 7: Jon Kleinberg , Mark Sandler, Convergent algorithms for collaborative filtering, Proceedings of the 4th ACM conference on Electronic commerce, p.1-10, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779929]
• 8: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
• 9: Greg Linden , Brent Smith , Jeremy York, Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, v.7 n.1, p.76-80, January 2003 [doi>10.1109/MIC.2003.1167344]
• 10: Geoffrey McLachlan, David Peel. Finite Mixture Models. Wiley, 2000.
• 11: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

General Terms:
Algorithms, Theory

Keywords:
clustering, collaborative filtering, latent class models, linear programming, mixture models, singular value decomposition, text classification