Collaborative recommendation: A robustness analysis

ABSTRACT

Collaborative recommendation has emerged as an effective technique for personalized information access. However, there has been relatively little theoretical analysis of the conditions under which the technique is effective. To explore this issue, we analyse the <i>robustness</i> of collaborative recommendation: the ability to make recommendations despite (possibly intentional) noisy product ratings. There are two aspects to robustness: recommendation <i>accuracy</i> and <i>stability</i>. We formalize recommendation accuracy in machine learning terms and develop theoretically justified models of accuracy. In addition, we present a framework to examine recommendation stability in the context of a widely-used collaborative filtering algorithm. For each case, we evaluate our analysis using several real-world data-sets. Our investigation is both practically relevant for enterprises wondering whether collaborative recommendation leaves their marketing operations open to attack, and theoretically interesting for the light it sheds on a comprehensive theory of collaborative recommendation.

REFERENCES

• 1: Albert, M. and Aha, D. 1991. Analyses of instance-based learning algorithms. In Proceedings of the 9th National Conference on Artificial Intelligence.
• 2: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• 3: 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]
• 4: Breese, J., Heckerman, D., and Kadie, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Conference on the Uncertainty in Artificial Intelligence.
• 5: 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]
• 6: 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]
• 7: Perry Groot , Frank van Harmelen , Annette ten Teije, Torture Tests: A Quantitative Analysis for the Robustness of Knowledge-Based Systems, Proceedings of the 12th European Workshop on Knowledge Acquisition, Modeling and Management, p.403-418, October 02-06, 2000
• 8: Haussler, D. 1990. Probably approximately correct learning. In National Conference on Artificial Intelligence. 1101--1108.
• 9: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 10: Hsu, C.-N. and Knoblock, C. A. 1995. Estimating the robustness of discovered knowledge. In Proceedings of the First International Conference on Knwledge Discovery and Data Mining. Montreal, Canada.
• 11: Hsu, C.-N. and Knoblock, C. A. 1996. Discovering robust knowledge from dynamic closed-world data. In Proceedings of AAAI'96.
• 12: http://movielens.umn.edu.
• 13: http://www.changingworlds.com.
• 14: IEEE. 1990. IEEE standard glossary of software engineering terminology. IEEE Standard 610.12-1990.
• 15: Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 17: 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
• 18: Ng, A., Zheng, A., and Jordan, M. 2001. Link analysis, eigenvectors and stability. In Proceedings of the 17th International Joint Conference on Artificial Intelligence.
• 19: David M. Pennock , Eric Horvitz , C. Lee Giles, Social Choice Theory and Recommender Systems: Analysis of the Axiomatic Foundations of Collaborative Filtering, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.729-734, July 30-August 03, 2000
• 20: 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]
• 21: 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]
• 22: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]

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:
Experimentation, Performance, Reliability

Keywords:
Collaborative recommendation, machine learning, robustness