Budget-Constrained Item Cold-Start Handling in Collaborative Filtering Recommenders via Optimal Design

ABSTRACT

It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand.

References

1. Deepak Agarwal and Bee-Chung Chen. Regression-based latent factor models. In Proc. KDD, 2009.
2. Michal Aharon, Amit Kagian, Yehuda Koren, and Ronny Lempel. Dynamic personalized recommendation of comment-eliciting stories. In Proc. RecSys, 2012.
3. Natalie Aizenberg, Yehuda Koren, and Oren Somekh. Build your own music recommender by modeling internet radio streams. In Proc. WWW, 2012.
4. A. C. Atkinson and A. N. Donev. Optimum Experimental Designs. Oxford Univ. Press, 1992.
5. J. Bennett and S. Lanning. The net ix prize. In Proc. KDD Cup and Workshop, 2007.
6. Gideon Dror, Noam Koenigstein, and Yehuda Koren. Yahoo! music recommendations: Modeling music ratings with temporal dynamics and item. In Proc. RecSys, 2011.
7. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 12:2121--2159, 2011.
8. Nadav Golbandi, Yehuda Koren, and Ronny Lempel. On bootstrapping recommender systems. In Proc. CIKM, 2010.
9. Nadav Golbandi, Yehuda Koren, and Ronny Lempel. Adaptive bootstrapping of recommender systems using decision trees. In Proc. WSDM, 2011.
10. Asela Gunawardana and Christopher Meek. Tied boltzmann machines for cold start recommendations. In Proc. RecSys, 2008.
11. Asela Gunawardana and Christopher Meek. A unified approach to building hybrid recommender systems. In Proc. RecSys, 2009.
12. Victor P. Il'ev. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Applied Mathematics, 114(1):131--146, 2001.
13. Arnd Kohrs and Bernard Merialdo. Improving collaborative filtering for new users by smart object selection. In Proc. International Conference on Media Features (ICMF), 2001.
14. Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In Proc. KDD, 2008.
15. Yehuda Koren. Collaborative filtering with temporal dynamics. Commun. of the ACM, 53(4):89--97, 2010.
16. Yehuda Koren, Robert M. Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, IEEE, 42(8):30--37, 2009.
17. Andreas Krause and Carlos Guestrin. Near-optimal observation selection using submodular functions. In AAAI, volume 7, pages 1650--1654, 2007.
18. Shao-Lun Lee. Commodity recommendations of retail business based on decision tree induction. Expert Systems with Applications, 37(5):3685--3694, 2010.
19. Seung-Taek Park and Wei Chu. Pairwise preference regression for cold-start recommendation. In Proc. RecSys, 2009.
20. Arkadiusz Paterek. Improving regularized singular value decomposition for collaborative filtering. In Proc. KDD cup and workshop, 2007.
21. Al Mamunur Rashid, Istvan Albert, Dan Cosley, Shyong K Lam, Sean M McNee, Joseph A Konstan, and John Riedl. Getting to know you: learning new user preferences in recommender systems. In Proc. International Conference on Intelligent User Interfaces, 2002.
22. Al Mamunur Rashid, George Karypis, and John Riedl. Learning preferences of new users in recommender systems: an information theoretic approach. ACM SIGKDD Explorations Newsletter, 10(2):90--100, 2008.
23. Guillaume Sagnol. Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs. Discrete Applied Mathematics, 161(1):258--276, 2013.
24. Chien-Fu Wu. Some algorithmic aspects of the theory of optimal designs. Annals of Statistics, 6(6):1286--1301, 1978.
25. Kai Yu, Jinbo Bi, and Volker Tresp. Active learning via transductive experimental design. In Proc. ICML, 2006.
26. Ke Zhou, Shuang-Hong Yang, and Hongyuan Zha. Functional matrix factorizations for cold-start recommendation. In Proc. SIGIR, 2011.

Index Terms

• Information systems

  • Information systems applications

    • Data mining