Revenue optimization with relevance constraint in sponsored search

ABSTRACT

Displaying sponsored ads alongside the search results is a key monetization strategy for search engine companies. Since users are more likely to click ads that are relevant to their query, it is crucial for search engine to deliver the right ads for the query and the order in which they are displayed. There are several works investigating on how to learn a ranking function to maximize the number of ad clicks. However, this ranking optimization problem is different from algorithmic search results ranking in that the ranking scheme must take received revenue into account in order to make more profit for the search engines. In this paper, we address a new optimization problem and aim to answer the question: how to construct a ranking model that can deliver high quality ads to the user as well as maximize search engine revenue? We introduce a novel tradeoff method from machine learning perspective, and through this method we have the privilege of choosing a tradeoff parameter to achieve highest relevance ranking or highest revenue ranking or the tradeoff between them. The algorithms are built upon the click-through log data with real ad clicks and impressions. The extensively experimental results verify that the proposed algorithm has the property that the search engine could choose a proper parameter to achieve high revenue(income) without losing to much relevance.

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 , Peter Ciccolo , Marcus Fontoura , Evgeniy Gabrilovich , Vanja Josifovski , Lance Riedel, Search advertising using web relevance feedback, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458217]
• 3: Deepayan Chakrabarti , Deepak Agarwal , Vanja Josifovski, Contextual advertising by combining relevance with click feedback, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367554]
• 4: Massimiliano Ciaramita , Vanessa Murdock , Vassilis Plachouras, Online learning from click data for sponsored search, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367529]
• 5: 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, 2008.
• 6: Yunzhang Zhu , Gang Wang , Junli Yang , Dakan Wang , Jun Yan , Jian Hu , Zheng Chen, Optimizing search engine revenue in sponsored search, Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, July 19-23, 2009, Boston, MA, USA [doi>10.1145/1571941.1572042]
• 7: Juan Feng , Hemant K. Bhargava , David M. Pennock, Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms, INFORMS Journal on Computing, v.19 n.1, p.137-148, January 2007 [doi>10.1287/ijoc.1050.0135]
• 8: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, 2000.
• 9: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 10: 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]
• 11: Filip Radlinski , Andrei Broder , Peter Ciccolo , Evgeniy Gabrilovich , Vanja Josifovski , Lance Riedel, Optimizing relevance and revenue in ad search: a query substitution approach, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390404]
• 12: M. Regelson and D. C. Fain. Predicting click-through rate using keyword clusters. In Proceedings of the 2nd Workshop on Sponsored Search Auctions, 2006.
• 13: 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]
• 14: S. E. Robertson. Overview of the okapi projects. Journal of Documentation, 53:3--7, 1997.
• 15: Chengxiang Zhai , John Lafferty, A study of smoothing methods for language models applied to Ad Hoc information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.334-342, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384019]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms, Design, Economics, Experimentation, Performance

Keywords:
machine learning, ranking, revenue optimization, sponsored search