Sampling dilemma: towards effective data sampling for click prediction in sponsored search

ABSTRACT

Precise prediction of the probability that users click on ads plays a key role in sponsored search. State-of-the-art sponsored search systems typically employ a machine learning approach to conduct click prediction. While paying much attention to extracting useful features and building effective models, previous studies have overshadowed seemingly less obvious but essentially important challenges in terms of data sampling. To fulfill the learning objective of click prediction, it is not only necessary to ensure that the sampled training data implies the similar input distribution compared with the real world one, but also to guarantee that the sampled training data yield the consistent conditional output distribution, i.e. click-through rate (CTR), with the real world data. However, due to the sparseness of clicks in sponsored search, it is a bit contradictory to address these two challenges simultaneously. In this paper, we first take a theoretical analysis to reveal this sampling dilemma, followed by a thorough data analysis which demonstrates that the straightforward random sampling method may not be effective to balance these two kinds of consistency in sampling dilemma simultaneously. To address this problem, we propose a new sampling algorithm which can succeed in retaining the consistency between the sampled data and real world in terms of both input distribution and conditional output distribution. Large scale evaluations on the click-through logs from a commercial search engine demonstrate that this new sampling algorithm can effectively address the sampling dilemma. Further experiments illustrate that, by using the training data obtained by our new sampling algorithm, we can learn the model with much higher accuracy in click prediction.

References

1. V. Abhishek and K. Hosanagar. Keyword generation for search engine advertising using semantic similarity between terms. In Proc. of EC, 2007.
2. J. Attenberg, S. Pandey, and T. Suel. Modeling and predicting user behavior in sponsored search. In Proc. of KDD, 2009.
3. A. Berger and V. Pietra. A maximum entropy approach to natural language processing. In Computational Linguistics, 1996.
4. H. Cheng and E. Cantu-Paz. Personalized click prediction in sponsored search. In Proc. of WSDM, 2010.
5. C. Clarke, E. Agichtein, S. Dumais, and R. White. The influence of caption features oh clickthrough patterns in web search. In Proc. of SIGIR, 2007.
6. K. Dembczynski, W. Kotlowski, and D. Weiss. Predicting ads click-through rate with decision rules. In Workshop on Targeting and Ranking in Online Advertising, 2008.
7. B. Edelman, M. Ostrovsky, and M. Schwarz. Internet adverstising and the generalized second-price auction: selling billions of dollars worth of keywords. In The American Economic Review, 2007.
8. D. Fain and J. Pedersen. Sponsored search: a brief history. In Proc. of 2nd Workshop on Sponsored Search Auctions, 2006.
9. T. Graepel, J. Candela, T. Borchert, and R. Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's bing search engine. In Proc. of ICML, 2010.
10. B. Jansen and T. Mullen. Sponsored search: an overview of the concept, history, and technology. In International Journal of Electric Business, 2008.
11. T. P. Minka. A comparison of numerical optimizers for logistic regression. In Technical report, Microsoft, 2003.
12. A. Mordecai. Nonlinear Programming: Analysis and Methods.
13. F. Radlinski, A. Broder, P. Ciccolo, E. Gabrilovich, V. Josifovski, and L. Riedel. Optimizing relevance and revenue in ad search: a query substitution approach. In Proc. of SIGIR, 2008.
14. H. Raghavan and R. Iyer. Evaluating vector-space and probabilistic models for query to ad matching. In Proc. of SIGIR Workshop on Information Retrieval for Advertising, 2008.
15. M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: estimating the click-through rate for new ads. In Proc. of WWW, 2007.
16. B. Shaparenko, O. Cetin, and R. Iyer. Data-driven text features for sponsored search click prediction. In Proc. of ADKDD, 2009.
17. C. Xiong, T. Wang, W. Ding, Y. Shen, and T.-Y. Liu. Relational click prediction for sponsored search. In Proc. of WSDM, 2012.
18. W. Xu, E. Manavoglu, and E. Cantu-Paz. Temporal click model for sponsored search. In Proc. of SIGIR, 2010.
19. W. Zhang, X. He, B. Rey, and R. Jones. Query rewriting using active learning for sponsored search. In Proc. of SIGIR, 2007.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval models and ranking

  • World Wide Web

    • Web applications

    • Web services