Learning multiple-question decision trees for cold-start recommendation

ABSTRACT

For cold-start recommendation, it is important to rapidly profile new users and generate a good initial set of recommendations through an interview process --- users should be queried adaptively in a sequential fashion, and multiple items should be offered for opinion solicitation at each trial. In this work, we propose a novel algorithm that learns to conduct the interview process guided by a decision tree with multiple questions at each split. The splits, represented as sparse weight vectors, are learned through an L_1-constrained optimization framework. The users are directed to child nodes according to the inner product of their responses and the corresponding weight vector. More importantly, to account for the variety of responses coming to a node, a linear regressor is learned within each node using all the previously obtained answers as input to predict item ratings. A user study, preliminary but first in its kind in cold-start recommendation, is conducted to explore the efficient number and format of questions being asked in a recommendation survey to minimize user cognitive efforts. Quantitative experimental validations also show that the proposed algorithm outperforms state-of-the-art approaches in terms of both the prediction accuracy and user cognitive efforts.

References

1. D. Agarwal and B. Chen. Regression-based latent factor models. In Proc. of the ACM SIGKDD, pages 19--28. ACM, 2009.
2. C. Boutilier, R. Zemel, and B. Marlin. Active collaborative filtering. In Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence, pages 98--106, 2003.
3. J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proc. of Uncertainty in Artificial Intelligence, 1998.
4. L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
5. N. Golbandi, Y. Koren, and R. Lempel. On bootstrapping recommender systems. In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 1805--1808. ACM, 2010.
6. N. Golbandi, Y. Koren, and R. Lempel. Adaptive bootstrapping of recommender systems using decision trees. In Proceedings of the fourth ACM international conference on Web search and data mining, pages 595--604. ACM, 2011.
7. A. Gunawardana and C. Meek. Tied boltzmann machines for cold start recommendations. In Proceedings of the 2008 ACM conference on Recommender systems, pages 19--26. ACM, 2008.
8. A. Harpale and Y. Yang. Personalized active learning for collaborative filtering. In Proc. of ACM SIGIR Conference, pages 91--98. ACM, 2008.
9. L. He, N. Liu, and Q. Yang. Active dual collaborative filtering with both item and attribute feedback. In AAAI, 2011.
10. J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In Proc. of ACM SIGIR Conference, 1999.
11. T. Hofmann. Latent semantic models for collaborative filtering. ACM Transactions on Information Systems, 22(1):115, 2004.
12. R. Jin and L. Si. A bayesian approach toward active learning for collaborative filtering. In Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 278--285, 2004.
13. Y. Koren. Factor in the neighbors: Scalable and accurate collaborative filtering. ACM Transactions on Knowledge Discovery from Data, 4(1):1--24, 2010.
14. N. D. Lawrence and R. Urtasun. Non-linear matrix factorization with gaussian processes. In Proc. of the ICML, 2009.
15. D. M. Pennock, E. Horvitz, S. Lawrence, and C. L. Giles. Collaborative filtering by personality diagnosis: A hybrid memory- and model-based approach. In Proc. of the Conference on UAI, 2000.
16. P. Pu and L. Chen. User-involved preference elicitation for product search and recommender systems. AI Magazine, 29(4):93, 2009.
17. A. Rashid, I. Albert, D. Cosley, S. Lam, S. McNee, J. Konstan, and J. Riedl. Getting to know you: learning new user preferences in recommender systems. In Proceedings of the 7th international conference on Intelligent user interfaces, pages 127--134. ACM, 2002.
18. A. Rashid, G. Karypis, and J. Riedl. Learning preferences of new users in recommender systems: an information theoretic approach. ACM, 2008.
19. J. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proc.\ of the International Conference on Machine Learning, 2005.
20. P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, and J. Riedl. Grouplens: an open architecture for collaborative filtering of netnews. In Proc. of the Conference on CSCW, 1994.
21. B. Sarwar, G. Karypis, J. Konstan, and J. Reidl. Item-based collaborative filtering recommendation algorithms. In Proc. of the International Conference on World Wide Web, 2001.
22. A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock. Methods and metrics for cold-start recommendations. In Proc. of ACM SIGIR Conference, pages 253--260. ACM, 2002.
23. M. Schmidt. Graphical Model Structure Learning with L1-Regularization. PhD thesis, The University of British Columbia, 2010.
24. M. Sun, G. Lebanon, and P. Kidwell. Estimating probabilities in recommendation systems. In Proc.\ of the International Conference on Artificial Intelligence and Statistics, 2011.
25. S. Yang, B. Long, A. Smola, and H. Zha. Collaborative-competitive ltering: Learning recommender using context of user choice. In Proc. of ACM SIGIR Conference, 2011.
26. K. Yu, S. Zhu, J. Lafferty, and Y. Gong. Fast nonparametric matrix factorization for large-scale collaborative filtering. In Proc. of ACM SIGIR Conference, 2009.
27. K. Zhou, S. Yang, and H. Zha. Functional matrix factorizations for cold-start recommendation. In Proc. of the ACM-SIGIR conference, pages 315--324, 2011.

Index Terms

• Computing methodologies

  • Machine learning

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction