×

Recommendation systems: A probabilistic analysis. (English) Zbl 0984.68152

Summary: A recommendation system tracks past actions of a group of users to make recommendations to individual members of the group. The growth of computer-mediated marketing and commerce has led to increased interest in such systems. We introduce a simple analytical framework for recommendation systems, including a basis for defining the utility of such a system. We perform probabilistic analyses of algorithms within this framework. These analyses yield insights into how much utility can be derived from knowledge of past user actions.

MSC:

68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, R. B., User models: Theory, method and practice, Internat. J. Man-Machine Studies, 32, 511-543 (1990)
[2] Berry, M. J.; Linoff, G., Data Mining Techniques (1997), Wiley: Wiley New York
[3] Bettman, J., An Information Processing Theory of Consumer Choice (1979), Addison-Wesley: Addison-Wesley Reading
[4] Blattberg, R. C.; Glazer, R.; Little, J. D.C, The Marketing Information Revolution (1994), Harvard Business School Press: Harvard Business School Press Cambridge
[5] Bollobas, B., Random Graphs (1985), Academic Press: Academic Press New York
[6] Boppana, R., Eigenvalues and graph bisection: An average-case analysis, Proc. IEEE Symp. on Foundations of Computer Science (1987)
[7] Charikar, M.; Kumar, S. R.; Raghavan, P.; Rajagopalan, S.; Tomkins, A., On targeting Markov segments, Proc. ACM Symposium on Theory of Computing (1999) · Zbl 1345.90104
[8] Deerwester, S.; Dumais, S. T.; Landauer, T. K.; Furnas, G. W.; Harshman, R. A., Indexing by latent semantic analysis, J. Soc. Inform. Sci., 41, 391-407 (1990)
[9] Drezner, Z., Facility Location: A Survey of Applications and Methods (1995), Springer-Verlag: Springer-Verlag Berlin/New York
[10] Glazer, R., Marketing in an information-intensive environment: Strategic implications of knowledge as an asset, J. Marketing, 55, 1-19 (1991)
[11] Goldberg, D.; Nichols, D.; Oki, B. M.; Terry, D., Using collaborative filtering to weave an information tapestry, Comm. Assoc. Comput. Mach., 35, 51-60 (1992)
[12] Golub, G.; Van Loan, C. F., Matrix Computations (1989), Johns Hopkins Univ. Press: Johns Hopkins Univ. Press Baltimore · Zbl 0733.65016
[13] Hill, W.; Stead, L.; Rosenstein, M.; Furnas, G., Recommending and evaluating choices in a virtual community of use, Proceedings of ACM CHI (1995), p. 194-201
[14] Hoffman, D. L.; Novak, T. P., Marketing in hypermedia computer-mediated environments: Conceptual foundations, J. Marketing, 60, 50-68 (1996)
[15] Howard, J., Consumer Behavior in Marketing Strategy (1989), Prentice Hall: Prentice Hall Englewood Cliffs
[16] Kleinberg, J.; Papadimitriou, C. H.; Raghavan, P., Segmentation problems, Proceedings of the ACM Symposium on Theory of Computing (1998) · Zbl 1027.68532
[17] Miller, B. N.; Riedl, J. T.; Konstan, J. A., Experiences with GroupLens: Making usenet useful again, Proceedings of the USENIX Conference (1997)
[18] Papadimitriou, C. H.; Raghavan, P.; Tamaki, H.; Vempala, S., Latent semantic indexing: A probabilistic analysis, Proceedings of the ACM Symposium on Principles of Database Systems (1998) · Zbl 0963.68063
[19] Resnick, P.; Iacovou, N.; Suchak, M.; Bergstrom, P.; Riedl, J., Report WP (1994)
[20] Shardanand, U., Social Information Filtering for Music Recommendation (1994), Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science
[21] Shardanand, U.; Maes, P., Social information filtering: Algorithms for automating “word of mouth”, Proceedings of the ACM Conference on Human Factors in Computing Systems (May 1995), p. 210-217
[22] ACM SIGGROUP resource page on collaborative filtering, http://www.acm.org/siggroup/collab.html; ACM SIGGROUP resource page on collaborative filtering, http://www.acm.org/siggroup/collab.html
[23] Valiant, L. G., A theory of the learnable, CACM, 27, 1134-1142 (1984) · Zbl 0587.68077
[24] H. R. Varian, Resources on collaborative filtering, http://www.sims.berkeley.edu/resources/collab/; H. R. Varian, Resources on collaborative filtering, http://www.sims.berkeley.edu/resources/collab/
[25] Varian, H. R.; Resnick, P., CACM Special issue on recommender systems, CACM, 40 (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.