Contextual advertising by combining relevance with click feedback

ABSTRACT

Contextual advertising supports much of the Web's ecosystem today. User experience and revenue (shared by the site publisher and the ad network) depend on the relevance of the displayed ads to the page content. As with other document retrieval systems, relevance is provided by scoring the match between individual ads (documents) and the content of the page where the ads are shown (query). In this paper we show how this match can be improved significantly by augmenting the ad-page scoring function with extra parameters from a logistic regression model on the words in the pages and ads. A key property of the proposed model is that it can be mapped to standard cosine similarity matching and is suitable for efficient and scalable implementation over inverted indexes. The model parameter values are learnt from logs containing ad impressions and clicks, with shrinkage estimators being used to combat sparsity. To scale our computations to train on an extremely large training corpus consisting of several gigabytes of data, we parallelize our fitting algorithm in a Hadoop framework [10]. Experimental evaluation is provided showing improved click prediction over a holdout set of impression and click events from a large scale real-world ad placement engine. Our best model achieves a 25% lift in precision relative to a traditional information retrieval model which is based on cosine similarity, for recalling 10% of the clicks in our test data.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Andrei Z. Broder , David Carmel , Michael Herscovici , Aya Soffer , Jason Zien, Efficient query evaluation using a two-level retrieval process, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956944]
• 3: Andrei Broder , Marcus Fontoura , Vanja Josifovski , Lance Riedel, A semantic approach to contextual advertising, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277837]
• 4: Patrali Chatterjee , Donna L. Hoffman , Thomas P. Novak, Modeling the Clickstream: Implications for Web-Based Advertising Efforts, Marketing Science, v.22 n.4, p.520-541, October 2003 [doi>10.1287/mksc.22.4.520.24906]
• 5: Chih-Jen Lin , Ruby C. Weng , S. Sathiya Keerthi, Trust region Newton methods for large-scale logistic regression, Proceedings of the 24th international conference on Machine learning, p.561-568, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273567]
• 6: C. R. Rao. Linear Statistical Inference and its Applications. Wiley-Interscience, 2002.
• 7: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 8: S. Derksen and H. J. Keselman. Backward, forward and stepwise automated subset selection algorithms: Frequency of obtaining authentic and noise variables. British Journal of Mathematical and Statistical Psychology, 45:265--282, 1992.
• 9: Online ad spending to total $19.5 billion in 2007. eMarketer, February 2007. Available from http://www.emarketer.com/Article.aspx?id=1004635.
• 10: A. Foundation. Apache hadoop project. In lucene.apache.org/hadoop.
• 11: G. King and L. Zeng. Logistic regression in rare events data. Political Analysis, 9:137--162, 2001.
• 12: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 13: Anísio Lacerda , Marco Cristo , Marcos André Gonçalves , Weiguo Fan , Nivio Ziviani , Berthier Ribeiro-Neto, Learning to advertise, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148265]
• 14: P. McCullagh and J. A. Nelder. Generalized Linear Models. Chapman and Hall, 1989.
• 15: M. J. Silvapulle. On the existence of maximum likelihood estimates for the binomial response models. Journal of the Royal Statistical Society, Series B, 43:310--313, 1981.
• 16: Paul Komarek , Andrew W. Moore, Making Logistic Regression a Core Data Mining Tool with TR-IRLS, Proceedings of the Fifth IEEE International Conference on Data Mining, p.685-688, November 27-30, 2005 [doi>10.1109/ICDM.2005.90]
• 17: M. Regelson and D. Fain. Predicting click-through rate using keyword clusters. In In Proc. of the Second Workshop on Sponsored Search Auctions, 2006.
• 18: Berthier Ribeiro-Neto , Marco Cristo , Paulo B. Golgher , Edleno Silva de Moura, Impedance coupling in content-targeted advertising, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076119]
• 19: Matthew Richardson , Ewa Dominowska , Robert Ragno, Predicting clicks: estimating the click-through rate for new ads, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242643]
• 20: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 21: C. Wang, P. Zhang, R. Choi, and M. D. Eredita. Understanding consumers attitude toward advertising. In Eighth Americas conf. on Information System, pages 1143--1148, 2002.
• 22: Wen-tau Yih , Joshua Goodman , Vitor R. Carvalho, Finding advertising keywords on web pages, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135813]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
clickthrough rate, interaction effects, modeling