jmlr jmlr2005 jmlr2005-12 jmlr2005-12-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Guy Shani, David Heckerman, Ronen I. Brafman
Abstract: Typical recommender systems adopt a static view of the recommendation process and treat it as a prediction problem. We argue that it is more appropriate to view the problem of generating recommendations as a sequential optimization problem and, consequently, that Markov decision processes (MDPs) provide a more appropriate model for recommender systems. MDPs introduce two benefits: they take into account the long-term effects of each recommendation and the expected value of each recommendation. To succeed in practice, an MDP-based recommender system must employ a strong initial model, must be solvable quickly, and should not consume too much memory. In this paper, we describe our particular MDP model, its initialization using a predictive model, the solution and update algorithm, and its actual performance on a commercial site. We also describe the particular predictive model we used which outperforms previous models. Our system is one of a small number of commercially deployed recommender systems. As far as we know, it is the first to report experimental analysis conducted on a real commercial site. These results validate the commercial value of recommender systems, and in particular, of our MDP-based approach. Keywords: recommender systems, Markov decision processes, learning, commercial applications
F. Bacchus, C. Boutilier, and A. J. Grove. Rewarding behaviors. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Vol. 2, pages 1160–1167, Portalnad, OR, 1996. M. Balabanovic and Y. Shoham. Combining content-based and collaborative recommendation. Communications of the ACM, 40(3):62—72, March 1997. R. E. Bellman. Dynamic Programming. Princeton University Press, 1962. T. Bohnenberger and A. Jameson. When policies are better than plans: decision-theoretic planning of recommendation sequences. In IUI ’01: Proceedings of the 6th international conference on Intelligent user interfaces, pages 21–24, New York, NY, USA, 2001. ACM Press. ISBN 1-58113325-1. 1292 A N MDP-BASED R ECOMMENDER S YSTEM B. Bonet and H. Geffner. Faster heuristic search algorithms for planning with uncertainty and full feedback. In G. Gottlob, editor, 18th International Joint Conf. on Artificial Intelligence, pages 1233–1238, Acapulco, Mexico, 2003. Morgan Kaufmann Publishers Inc. C. Boutilier. A POMDP formulation of preference elicitation problems. In Eighteenth national conference on Artificial intelligence, pages 239–246, Edmonton, Alberta, Canada, 2002. American Association for Artificial Intelligence. C. Boutilier, R. Dearden, and M. Goldszmidt. Stochastic dynamic programming with factored representations. Artificial Intelligence, 121(1-2):49–107, 2000. J. S. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th conference on Uncertainity in Artificial Inteligence, pages 43–52, San Francisco, California, 1998. Morgan Kaufmann Publishers Inc. R. Burke. Knowledge-Based Recommender Systems, volume 69 of Encyclopedia of Library and Information Systems, supplement 32. A. Kent, New York, 2000. R. Burke. Hybrid recommender systems: Survey and experiments. User Modeling and UserAdapted Interaction, 12(4):331–370, 2002. S. F. Chen and J. Goodman. An empirical study of smoothing techniques for language modeling. In Arivind Joshi and Martha Palmer, editors, Proceedings of the Thirty-Fourth Annual Meeting of the Association for Computational Linguistics, pages 310–318, San Francisco, 1996. Morgan Kaufmann Publishers Inc. M. Claypool, P. Le, M. Wased, and D. Brown. Implicit interest indicators. In IUI ’01: Proceedings of the 6th international conference on Intelligent user interfaces, pages 33–40, Santa Fe, New Mexico, United States, 2001. ACM Press. N. Good, J. Ben Schafer, J. A. Konstan, A. Borchers, B. M. Sarwar, J. L. Herlocker, and J. Riedl. Combining collaborative filtering with personal agents for better recommendations. In AAAI ’99/IAAI ’99: Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, pages 439–446, Orlando, Florida, United States, 1999. American Association for Artificial Intelligence. D. Heckerman, D. M. Chickering, C. Meek, R. Rounthwaite, and C. M. Kadie. Dependency networks for inference, collaborative filtering, and data visualization. Journal of Machine Learning Research, 1:49–75, 2000. R. A. Howard. Dynamic Programming and Markov Processes. MIT Press, 1960. C. M. Kadie, C. Meek, and D. Heckerman. CFW: A collaborative filtering system using posterios over weights of evidence. In 18th Conference on Uncertainty in AI (UAI’02), pages 242–250, 2002. L. P. Kaelbling, M. L. Littman, and A. P. Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4:237–285, 1996. 1293 S HANI , B RAFMAN AND H ECKERMAN B. Kitts, D. Freed, and M. Vrieze. Cross-sell: a fast promotion-tunable customer-item recommendation method based on conditionally independent probabilities. In KDD ’00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 437–446, Boston, Massachusetts, United States, 2000. ACM Press. D. Koller and R. Parr. Policy iteration for factored mdps. In UAI ’00: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, pages 326–334, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. Microsoft. Recommendation score. Microsoft Commerce Server 2002 Documentation, 2002. R. J. Mooney and L. Roy. Content-based book recommending using learning for text categorization. In DL ’00: Proceedings of the fifth ACM conference on Digital libraries, pages 195–204, San Antonio, Texas, United States, 2000. ACM Press. M. Puterman. Markov Decision Processes. Wiley, New York, 1994. P. Resnick, N. Iacovou, M. Suchak, P. Bergstorm, and J. Riedl. GroupLens: An Open Architecture for Collaborative Filtering of Netnews. In Proceedings of ACM 1994 Conference on Computer Supported Cooperative Work, pages 175–186, Chapel Hill, North Carolina, 1994. ACM. P. Resnick and H. R. Varian. Recommender systems. Special issue of Communications of the ACM, pages 56–58, March 1997. B. Sarwar, G. Karypis, J. Konstan, and J. Riedl. Application of dimensionality reduction in recommender systems: a case study. In ACM WebKDD 2000 Web Mining for E-Commerce Workshop, August 2000a. B. Sarwar, G. Karypis, J. A. Konstan, and J. Riedl. Analysis of recommendation algorithms for e-commerce. In EC ’00: Proceedings of the 2nd ACM conference on Electronic commerce, pages 158–167, New York, NY, USA, 2000b. ACM Press. ISBN 1-58113-272-7. J. B. Schafer, J. A. Konstan, and J. Riedle. E-commerce recommendation applications. Data Mining Knowledge Discovery, 5(1-2):115–153, 2001. Z. Su, Q. Yang, and H. J. Zhang. A prediction system for multimedia pre-fetching in internet. In MULTIMEDIA ’00: Proceedings of the eighth ACM international conference on Multimedia, pages 3–11, Marina del Rey, California, United States, 2000. ACM Press. R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998. S. Thi´ baux, F. Kabanza, and J. Slaney. Anytime state-based solution methods for decision proe cesses with non-Markovian rewards. In 18th Conference on Uncertainty in AI (UAI’02), pages 501–510, Edmonton, Canada, July 2002. Morgan Kaufmann. A. Yeh. More accurate tests for the statistical significance of result differences. In Proceedings of the 17th conference on Computational linguistics, pages 947–953, Saarbrcken, Germany, 2000. Association for Computational Linguistics. 1294 A N MDP-BASED R ECOMMENDER S YSTEM A. Zimdars, D. M. Chickering, and C. Meek. Using temporal data for making recommendations. In UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pages 580–588, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. 1295