Personalized click shaping through lagrangian duality for online recommendation

ABSTRACT

Online content recommendation aims to identify trendy articles in a continuously changing dynamic content pool. Most of existing works rely on online user feedback, notably clicks, as the objective and maximize it by showing articles with highest click-through rates. Recently, click shaping was introduced to incorporate multiple objectives in a constrained optimization framework. The work showed that significant tradeoff among the competing objectives can be observed and thus it is important to consider multiple objectives. However, the proposed click shaping approach is segment-based and can only work with a few non-overlapping user segments. It remains a challenge of how to enable deep personalization in click shaping. In this paper, we tackle the challenge by proposing personalized click shaping. The main idea is to work with the Lagrangian duality formulation and explore strong convexity to connect dual and primal solutions. We show that our formulation not only allows efficient conversion from dual to primal for online personalized serving, but also enables us to solve the optimization faster by approximation. We conduct extensive experiments on a large real data set and our experimental results show that the personalized click shaping can significantly outperform the segmented one, while achieving the same ability to balance competing objectives.

References

1. D. Agarwal and B.-C. Chen. Regression-based latent factor models. In KDD, 2009.
2. D. Agarwal, B.-C. Chen, and P. Elango. Spatio-temporal models for estimating click-through rate. In WWW, 2009.
3. D. Agarwal, B.-C. Chen, P. Elango, and et al. Online models for content optimization. In NIPS, 2008.
4. D. Agarwal, B.-C. Chen, P. Elango, and X. Wang. Click shaping to optimize multiple objectives. In KDD, 2011.
5. P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 2002.
6. D. A. Berry and B. Fristedt. Bandit Problems: Sequential Allocation of Experiments. Chapman and Hall, 1985.
7. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
8. G. Buscher, L. van Elst, and A. Dengel. Segment-level display time as implicit feedback: a comparison to eye tracking. In SIGIR, 2009.
9. Y. Chen, P. Berkhin, B. Anderson, and N. R. Devanur. Real-time bidding algorithms for performance-based display ad allocation. In KDD, 2011.
10. A. Das, M. Datar, A. Garg, and S. Rajaram. Google news personalization: scalable online collaborative filtering. In WWW, 2007.
11. R. Fain and J. Pederson. Sponsored search: A brief history. Bulletin of American Society of Information and Technology, 2006.
12. P. V. Hentenryck and R. Bent. Online Stochastic Combinatorial Optimization. The MIT Press, 2006.
13. J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In SIGIR, 1999.
14. T. Jambor and J. Wang. Optimizing multiple objectives in collaborative filtering. In RecSys, 2010.
15. Y. Koren. Collaborative filtering with temporal dynamics. In KDD, 2009.
16. J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. In NIPS, 2008.
17. L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bandit approach to personalized news article recommendation. In WWW, 2010.
18. L. Li, W. Chu, J. Langford, and X. Wang. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In WSDM, 2011.
19. L. Li, D. Wang, T. Li, D. Knox, and B. Padmanabhan. Scene: a scalable two-stage personalized news recommendation system. In SIGIR, 2011.
20. J. Liu, P. Dolan, and E. R. Pedersen. Personalized news recommendation based on click behavior. In IUI, 2010.
21. D. Sculley, R. G. Malkin, S. Basu, and R. J. Bayardo. Predicting bounce rates in sponsored search advertisements. In KDD, 2009.
22. D. H. Stern, R. Herbrich, and T. Graepel. Matchbox: large scale online bayesian recommendations. In WWW, 2009.
23. R. Steuer. Multi-criteria optimization: theory, computation, and application. Wiley, 1986.
24. K. M. Svore, M. N. Volkovs, and C. J. C. Burges. Learning to rank with multiple objective functions. In WWW, 2011.
25. E. Vee, S. Vassilvitski, and J. Shanmugasundaran. Optimal online assignment with forecasts. In EC, 2010.
26. J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical evaluation. In ECML, 2005.
27. Y. Zhang, J. P. Callan, and T. P. Minka. Novelty and redundancy detection in adaptive filtering. In SIGIR, 2002.

Index Terms

• Human-centered computing

  • Collaborative and social computing

    • Collaborative and social computing systems and tools

• Information systems

  • World Wide Web