ABSTRACT
Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from fine-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and efficient solution to BT using Hadoop MapReduce framework. With our parallel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo's user base within one day, the scale that one can not even imagine with prior systems. Moreover, our approach has yielded 20% CTR lift over the existing production system by leveraging the well-grounded probabilistic model fitted from a much larger training dataset.
Specifically, our major contributions include: (1) A MapReduce statistical learning algorithm and implementation that achieve optimal data parallelism, task parallelism, and load balance in spite of the typically skewed distribution of domain data. (2) An in-place feature vector generation algorithm with linear time complexity O(n) regardless of the granularity of sliding target window. (3) An in-memory caching scheme that significantly reduces the number of disk IOs to make large-scale learning practical. (4) Highly efficient data structures and sparse representations of models and data to enable fast model updates. We believe that our work makes significant contributions to solving large-scale machine learning problems of industrial relevance in general. Finally, we report comprehensive experimental results, using industrial proprietary codebase and datasets.
Supplemental Material
- http://hadoop.apache.org/.Google Scholar
- S. Agarwal, P. Renaker, and A. Smith. Determining ad targeting information and/or ad creative information using past search queries. U.S. Patent 10/813,925, filed: Mar 31, 2004.Google Scholar
- A. C. Cameron and P. K. Trivedi. Regression Analysis of Count Data. Cambridge University Press, 1998.Google ScholarCross Ref
- J. Canny. GaP: a factor model for discrete data. ACM Conference on Information Retrieval (SIGIR 2004), pages 122--129, 2004. Google ScholarDigital Library
- J. Canny, S. Zhong, S. Gaffney, C. Brower, P. Berkhin, and G. H. John. Granular data for behavioral targeting. U.S. Patent Application 20090006363.Google Scholar
- E. Chang. Scalable collaborative filtering algorithms for mining social networks. In The NIPS 2008 Workshop on "Beyond Search: Computational Intelligence for the Web, 2008.Google Scholar
- Y. Chen, D. Pavlov, P. Berkhin, and J. Canny. Large-scale behavioral targeting for advertising over a network. U.S. Patent Application 12/351,749, filed: Jan 09, 2009.Google Scholar
- C. Y. Chung, J. M. Koran, L.-J. Lin, and H. Yin. Model for generating user profiles in a behavioral targeting system. U.S. Patent 11/394,374, filed: Mar 29, 2006.Google Scholar
- J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. Communications of the ACM, 51(1):107--113, 2008. Google ScholarDigital Library
- N. E. Gibbs, W. G. Poole, Jr., and P. K. Stockmeyer. A comparison of several bandwidth and profile reduction algorithms. ACM Transactions on Mathematical Software (TOMS), 2(3):322--330, 1976. Google ScholarDigital Library
- D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. Advances in Neural Information Processing Systems (NIPS), 13:556--562, 2000.Google Scholar
- D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 2004. Google ScholarDigital Library
Index Terms
- Large-scale behavioral targeting
Recommendations
Is Combining Contextual and Behavioral Targeting Strategies Effective in Online Advertising?
Online targeting has been increasingly used to deliver ads to consumers. But discovering how to target the most valuable web visitors and generate a high response rate is still a challenge for advertising intermediaries and advertisers. The purpose of ...
Large-scale behavioral targeting with a social twist
CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge managementBehavioral targeting (BT) is a widely used technique for online advertising. It leverages information collected on an individual's web-browsing behavior, such as page views, search queries and ad clicks, to select the ads most relevant to user to ...
Behavioral Targeting: The Art of Scaling Up Simple Algorithms
Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from fine-grained user behavioral data and predicts click-through rate ...
Comments