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. Angluin, D. and Laird, P. 1988. Learning from noisy examples. Machine Learning 2, 4, 343--370.]]
3. Azar, Y., Fiat, A., Karlin, A., McSherry, F., and Saia, J. 2001. Spectral analysis of data. In Proceedings of the 32nd ACM Symposium on the Theory of Computing.]]
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. Drineas, P., Kerenidis, I., and Raghavan, P. 2002. Competetive recommender systems. In Proceedings of the 32nd ACM Symposium on the Theory of Computing.]]
6. Goldberg, D., Nichols, D., Oki, B., and Terry, D. 1992. Using collaborative filtering to weave an information tapestry. Comm. ACM 35, 12, 61--70.]]
7. Groot, P., van Harmelen, F., and ten Teije, A. 2000. Torture tests: a quantitative analysis for the robustness of knowledge-based systems. In European Workshop on Knowledge Acquisition, Modelling and Management (EKAW'00). LNAI Springer-Verlag.]]
8. Haussler, D. 1990. Probably approximately correct learning. In National Conference on Artificial Intelligence. 1101--1108.]]
9. Herlocker, J., Konstan, J., Borchers, A., and Riedl, J. 1999. An algorithmic framework for performing collaborative filtering. In Proceedings of ACM SIGIR'99.]]
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. Kearns, M. and Li, M. 1988. Learning in the presence of malicious errors. In Proceedings of the ACM Symposium on the Theory of Computing.]]
16. Kleinberg, J. 1998. Authoritative sources in a hyperlinked environment. In Proceedings of the ACM SIAM Symposium on Discrete Algorithms.]]
17. Kumar, R., Raghavan, P., Rajagopalan, S., and Tompkins, A. 1998. Recommender systems: A probabilistic analysis. In Proceedings of the 39th IEEE Symposium on the Foundations of Computer Science.]]
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. Pennock, D., Horvitz, E., and Giles, L. 2000. Socal choice theory and recommender systems: Analysis of the axiomatic foundations of collabortative filtering. In National Conference on Artificial Intelligence. 729--734.]]
20. Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., and Riedl, J. 1994. An open architecture for collaborative filtering of netnews. In ACM Conference on Computer Supported Cooperative Work.]]
21. Shardanand, U. and Maes, P. 1994. Social information filtering: Algorithms for automating "word of mouth". In Proceedings of the Conference on Human Factors in Computing Systems.]]
22. Valiant, L. 1984. A theory of the learnable. Comm. ACM, 1134--1142.]]

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction