Learning to advertise

ABSTRACT

Content-targeted advertising, the task of automatically associating ads to a Web page, constitutes a key Web monetization strategy nowadays. Further, it introduces new challenging technical problems and raises interesting questions. For instance, how to design ranking functions able to satisfy conflicting goals such as selecting advertisements (ads) that are relevant to the users and suitable and profitable to the publishers and advertisers? In this paper we propose a new framework for associating ads with web pages based on Genetic Programming (GP). Our GP method aims at learning functions that select the most appropriate ads, given the contents of a Web page. These ranking functions are designed to optimize overall precision and minimize the number of misplacements. By using a real ad collection and web pages from a newspaper, we obtained a gain over a state-of-the-art baseline method of 61.7% in average precision. Further, by evolving individuals to provide good ranking estimations, GP was able to discover ranking functions that are very effective in placing ads in web pages while avoiding irrelevant ones.

REFERENCES

• 1: Giuseppe Attardi , Andrea Esuli , Maria Simi, Best bets: thousands of queries in search of a client, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013506]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: J. J. Carrasco, D. Fain, K. Lang, and L. Zhukov. Clustering of bipartite advertiser-keyword graph. In Workshop on Clustering Large Datasets, 3th IEEE International Conference on Data Mining, Melbourne, Florida, USA, November 2003. IEEE Computer Society Press. Available at http://research.yahoo.com/publications.xml .
• 4: O. Cordon, F. Moya, and C. Zarco. A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems. Soft Computing-A Fusion of Foundations, Methodologies and Applications, 6(5): 308--319, Aug. 2002.
• 5: E. Eneva. Detecting invalid clicks in online paid search listings: a problem description for the use of unlabeled data. In T. Fawcett and N. Mishra, editors, Workshop on the Continuum from Labeled to Unlabeled Data, 20th International Conference on Machine Learning, Washington DC, USA, August 2003. AAAI Press.
• 6: Weiguo Fan , Edward A. Fox , Praveen Pathak , Harris Wu, The effects of fitness functions on genetic programming-based ranking discovery for Web search: Research Articles, Journal of the American Society for Information Science and Technology, v.55 n.7, p.628-636, May 2004 [doi>10.1002/asi.v55:7]
• 7: Weiguo Fan , Michael D. Gordon , Praveen Pathak, Discovery of Context-Specific Ranking Functions for Effective Information Retrieval Using Genetic Programming, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.523-527, April 2004 [doi>10.1109/TKDE.2004.1269663]
• 8: Weiguo Fan , Michael D. Gordon , Praveen Pathak, A generic ranking function discovery framework by genetic programming for information retrieval, Information Processing and Management: an International Journal, v.40 n.4, p.587-602, May 2004 [doi>10.1016/j.ipm.2003.08.001]
• 9: W. Fan, M. D. Gordon, and P. Pathak. Genetic programming-based discovery of ranking functions for effective web search. Journal of Management Information Systems, 21(4): 37--56, Spring 2005.
• 10: Weiguo Fan , Michael D. Gordon , Praveen Pathak , Wensi Xi , Edward A. Fox, Ranking Function Optimization for Effective Web Search by Genetic Programming: An Empirical Study, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 4, p.40105, January 05-08, 2004
• 11: J. Feng, H. Bhargava, and D. Pennock. Implementing paid placement in Web search engines: computational evaluation of alternative mechanisms. INFORMS Journal on Computing, 2006. To be published.
• 12: David Gleich , Leonid Zhukov, SVD based Term Suggestion and Ranking System, Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04), p.391-394, November 01-04, 2004
• 13: M. Gordon, Probabilistic and genetic algorithms in document retrieval, Communications of the ACM, v.31 n.10, p.1208-1218, Oct. 1988 [doi>10.1145/63039.63044]
• 14: M. D. Gordon. User-based document clustering by redescribing subject descriptions with a genetic algorithm. JASIS, 42(5): 311--322, 1991.
• 15: D. K. Harman. Overview of the fourth text retrieval conference TREC-4. In D. K. Harman, editor, Proceedings of the Fourth Text REtrieval Conference (TREC-4), pages 1--24, Gaithersburg, Maryland, USA, November 1996. NIST Special Publication 500--236.
• 16: D. Hawking, N. Craswell, and P. B. Thistlewaite. Overview of TREC-7 very large collection track. In The Seventh Text REtrieval Conference (TREC-7), pages 91--104, Gaithersburg, Maryland, USA, November 1998.
• 17: Jorng-Tzong Horng , Ching-Chang Yeh, Applying genetic algorithms to query optimization in document retrieval, Information Processing and Management: an International Journal, v.36 n.5, p.737-759, Sept. 2000 [doi>10.1016/S0306-4573(00)00008-X]
• 18: IAB and PricewaterhouseCoopers. IAB internet advertising revenue report, April 2005. Available at http://www.iab.net/2004adrevenues.
• 19: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 20: William B. Langdon , Koza John R, Genetic Programming and Data Structures: Genetic Programming + Data Structures = Automatic Programming!, Kluwer Academic Publishers, Norwell, MA, 1998
• 21: K. Lee. The SEM content conundrum. ClickZ Experts, July 2003. Available at http://www.clickz.com/experts/search/strat/article.php/2233821.
• 22: Cristina López-Pujalte , Vicente P. Guerrero-Bote , Félix de Moya-Anegón, Order-based fitness functions for genetic algorithms applied to relevance feedback, Journal of the American Society for Information Science and Technology, v.54 n.2, p.152-160, January 2003 [doi>10.1002/asi.10179]
• 23: K. Maddox. Forrester reports advertising shift to online, May 2005. Available at http://www.btobonline.com/article.cms?articleId=24191.
• 24: T. M. Mitchell. Machine learning. McGraw Hill, New York, US, 1996.
• 25: OneUpWeb. How keyword length affects conversion rates, January 2005. Available at http://www.oneupweb.com/landing/keywordstudy_landing.htm .
• 26: Jeffrey Parsons , Katherine Gallagher , K. Dale Foster, Messages in the Medium: An Experimental Investigation of Web Advertising Effectiveness and Attitudes toward Web Content, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 6, p.6050, January 04-07, 2000
• 27: P. Pathak, M. Gordon, and W. Fan. Effective information retrieval using genetic algorithms based matching function adaptation. In Proceedings of the 33rd Hawaii International Conference on System Science, Hawaii, USA, 2000.
• 28: 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]
• 29: M. Weideman. Ethical issues on content distribution to digital consumers via paid placement as opposed to website visibility in search engine results. In The 17th ETHICOMP, pages 904--915. Troubador Publishing Ltd, April 2004.
• 30: Melius Weideman , Timothy Haig-Smith, An investigation into search engines as a form of targeted advert delivery, Proceedings of the 2002 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology, September 16-18, 2002, Port Elizabeth, South Africa
• 31: Baoping Zhang , Yuxin Chen , Weiguo Fan , Edward A. Fox , Marcos Gonçalves , Marco Cristo , Pável Calado, Intelligent GP fusion from multiple sources for text classification, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099688]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation

Keywords:
genetic programming, web advertising