Convergent algorithms for collaborative filtering

ABSTRACT

A collaborative filtering system analyzes data on the past behavior of its users so as to make recommendations --- a canonical example is the recommending of books based on prior purchases. The full potential of collaborative filtering implicitly rests on the premise that, as an increasing amount of data is collected, it should be possible to make increasingly high-quality recommendations. Despite the prevalence of this notion at an informal level, the theoretical study of such convergent algorithms has been quite limited.To investigate such algorithms, we generalize a model of collaborative filtering proposed by Kumar et al., in which the recommendations made by an algorithm are compared to those of an omniscient algorithm that knows the hidden preferences of users. Within our generalized model, we develop a recommendation algorithm with a strong convergence property --- as the amount of data increases, the quality of its recommendations approach those of the optimal omniscient algorithm. We also consider a further generalization, a mixture model proposed by Hofmann and Puzichaomt; here we prove that, in a natural sense, no recommendation algorithm can achieve convergent behavior with respect to the optimum.

REFERENCES

• 1: Amazon.com, Amazon.com Services: Recommendations, at http://www.amazon.com/exec/obidos/tg/browse/-/help/508506/ref=pd_ir_how_nav/.
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: Avrim Blum , Joel Spencer, Coloring random and semi-random k-colorable graphs, Journal of Algorithms, v.19 n.2, p.204-234, Sept. 1995 [doi>10.1006/jagm.1995.1034]
• 4: R. Boppana, "Eigenvalues and graph bisection: An average-case analysis," Proc. IEEE Symp. on Foundations of Computer Science, 1987.
• 5: J.S. Breese, D. Heckerman, C. Kadie. "Empirical analysis of predictive algorithms for collaborative filtering," Proc. Conf. on Uncertainty in Artificial Intelligence, 1998.
• 6: 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]
• 7: EachMovie EachMovie collaborative filtering data set, at http://www.research.compaq.com/SRC/eachmovie/
• 8: FTC Federal Trade Commission, Privacy Online: A Report to Congress, 1998.
• 9: L. Getoor, M. Sahami, "Using Probabilistic Relational Models for Collaborative Filtering," WebKDD'99, 1999.
• 10: 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]
• 11: GroupLens home page, http://www.cs.umn.edu/Research/GroupLens/index.html
• 12: Will Hill , Larry Stead , Mark Rosenstein , George Furnas, Recommending and evaluating choices in a virtual community of use, Proceedings of the SIGCHI conference on Human factors in computing systems, p.194-201, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223929]
• 13: 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
• 14: 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
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: Alexandrin Popescul , Lyle H. Ungar , David M. Pennock , Steve Lawrence, Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.437-444, August 02-05, 2001
• 17: 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]
• 18: 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]
• 19: Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
• 20: ACM SIGGROUP, Resources on Collaborative Filtering, at http://www.acm.org/siggroup/collab.html.
• 21: Stanford Legal Review, 52 (July 2000), special issue on privacy.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Theory

Keywords:
clustering, collaborative filtering, latent class models, mixture model