Search advertising using web relevance feedback

ABSTRACT

The business of Web search, a $10 billion industry, relies heavily on sponsored search, whereas a few carefully-selected paid advertisements are displayed alongside algorithmic search results. A key technical challenge in sponsored search is to select ads that are relevant for the user's query. Identifying relevant ads is challenging because queries are usually very short, and because users, consciously or not, choose terms intended to lead to optimal Web search results and not to optimal ads. Furthermore, the ads themselves are short and usually formulated to capture the reader's attention rather than to facilitate query matching.

Traditionally, matching of ads to queries employed standard information retrieval techniques using the bag of words approach. Here we propose to go beyond the bag of words, and augment both queries and ads with additional knowledge-rich features. We use Web search results initially returned for the query to create a pool of relevant documents. Classifying these documents with respect to an external taxonomy and identifying salient named entities give rise to two new feature types. Empirical evaluation based on over 9,000 query-ad pairwise judgments confirms that using augmented queries produces highly relevant ads. Our methodology also relaxes the requirement for each ad to explicitly specify the exhaustive list of queries ("bid phrases") that can trigger it.

REFERENCES

• 1: Eugene Agichtein , Steve Lawrence , Luis Gravano, Learning search engine specific query transformations for question answering, Proceedings of the 10th international conference on World Wide Web, p.169-178, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371976]
• 2: Peter Anick, Using terminological feedback for web search refinement: a log-based study, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860453]
• 3: Lisa Ballesteros , W. Bruce Croft, Phrasal translation and query expansion techniques for cross-language information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.84-91, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 4: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David Grossman , David D. Lewis , Abdur Chowdhury , Aleksandr Kolcz, Automatic web query classification using labeled and unlabeled training data, 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.1076138]
• 5: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David D. Lewis , Abdur Chowdhury , Aleksander Kolcz, Improving Automatic Query Classification via Semi-Supervised Learning, Proceedings of the Fifth IEEE International Conference on Data Mining, p.42-49, November 27-30, 2005 [doi>10.1109/ICDM.2005.80]
• 6: P. N. Bennett, S. T. Dumais, and E. Horvitz. Inductive transfer for text classification using generalized reliability indicators. In Proceedings of the ICML-2003 Workshop on The Continuum from Labeled to Unlabeled Data, 2003.
• 7: Andrei Z. Broder , Marcus Fontoura , Evgeniy Gabrilovich , Amruta Joshi , Vanja Josifovski , Tong Zhang, Robust classification of rare queries using web knowledge, 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.1277783]
• 8: 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]
• 9: 61 billion searches conducted worldwide in August. comscore, October 2007. Available from http://www.comscore.com/press/release.asp?press=1802.
• 10: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Probabilistic query expansion using query logs, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511489]
• 11: Fernando Diaz , Donald Metzler, Improving the estimation of relevance models using large external corpora, 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.1148200]
• 12: C. Do and A. Ng. Transfer learning for text classification. In Proceedings of Neural Information Processing Systems (NIPS), 2005.
• 13: R. Duda and P. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, 1973.
• 14: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
• 15: E. Efthimiadis and P. Biron. UCLA-okapi at TREC-2: Query expansion experiments. In Proceedings of TREC-2, 1994.
• 16: D. Fain and J. Pedersen. Sponsored search: A brief history. In Second Workshop on Sponsored Search Auctions, 2006.
• 17: E. Gabrilovich and S. Markovitch. Feature generation for text categorization using world knowledge. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, pages 1048--1053, Edinburgh, Scotand, August 2005.
• 18: Luis Gravano , Vasileios Hatzivassiloglou , Richard Lichtenstein, Categorizing web queries according to geographical locality, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956925]
• 19: Eui-Hong Han , George Karypis, Centroid-Based Document Classification: Analysis and Experimental Results, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.424-431, September 13-16, 2000
• 20: Daqing He , Yefei Peng, Comparing two blind relevance feedback techniques, 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.1148299]
• 21: Xin Jin , Ying Li , Teresa Mah , Jie Tong, Sensitive webpage classification for content advertising, Proceedings of the 1st international workshop on Data mining and audience intelligence for advertising, p.28-33, August 12-12, 2007, San Jose, California [doi>10.1145/1348599.1348604]
• 22: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 23: Zsolt T. Kardkovács , Domonkos Tikk , Zoltán Bánsághi, The Ferrety algorithm for the KDD Cup 2005 problem, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.111-116, December 2005 [doi>10.1145/1117454.1117468]
• 24: Adam Kilgarriff , Gregory Grefenstette, Introduction to the special issue on the web as corpus, Computational Linguistics, v.29 n.3, p.333-347, September 2003 [doi>10.1162/089120103322711569]
• 25: P. Kowalczyk, I. Zukerman, and M. Niemann. Analyzing the effect of query class on document retrieval performance. In Proceedings of the Australian Conference on Artificial Intelligence, pages 550--561, 2004.
• 26: 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]
• 27: Marc Langheinrich , Atsuyoshi Nakamura , Naoki Abe , Tomonari Kamba , Yoshiyuki Koseki, Unintrusive customization techniques for Web advertising, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1259-1272, May 17, 1999
• 28: Yinghao Li , Wing Pong Robert Luk , Kei Shiu Edward Ho , Fu Lai Korris Chung, Improving weak ad-hoc queries using wikipedia asexternal corpus, 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.1277914]
• 29: Ying Li , Zijian Zheng , Honghua (Kathy) Dai, KDD CUP-2005 report: facing a great challenge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.91-99, December 2005 [doi>10.1145/1117454.1117466]
• 30: D. Metzler, S. Dumais, and C. Meek. Similarity measures for short segments of text. In Proceedings of the 29th European Conference on Information Retrieval, pages 16--27, 2007.
• 31: Mandar Mitra , Amit Singhal , Chris Buckley, Improving automatic query expansion, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290995]
• 32: M. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 33: Rajat Raina , Andrew Y. Ng , Daphne Koller, Constructing informative priors using transfer learning, Proceedings of the 23rd international conference on Machine learning, p.713-720, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143934]
• 34: 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]
• 35: S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. In Proceedings of TREC-3, 1995.
• 36: S. E. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. okapi at TREC-3. In Proceedings of the 3rd Text REtrieval Conference, 1994.
• 37: J. J. Rocchio. Relevance feedback in information retrieval. In The SMART Retrieval System: Experiments in Automatic Document Processing, pages 313--323. Prentice Hall, 1971.
• 38: Mehran Sahami , Timothy D. Heilman, A web-based kernel function for measuring the similarity of short text snippets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135834]
• 39: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 40: G. Salton and C. Buckley. Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science, 41(4):288--297, 1990.
• 41: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 42: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 43: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 44: Dou Shen , Jian-Tao Sun , Qiang Yang , Zheng Chen, Building bridges for web query classification, 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.1148196]
• 45: Amanda Spink , Dietmar Wolfram , Major B. J. Jansen , Tefko Saracevic, Searching the Web: the public and their queries, Journal of the American Society for Information Science and Technology, v.52 n.3, p.226-234, Feb. 1, 2001 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1591>3.3.CO;2-I]
• 46: C. Sutton and A. McCallum. Composition of conditional random fields for transfer learning. In Emprical Methods in Natural Language Processing (HLT/EMNLP), 1998.
• 47: David Vogel , Steffen Bickel , Peter Haider , Rolf Schimpfky , Peter Siemen , Steve Bridges , Tobias Scheffer, Classifying search engine queries using the web as background knowledge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.117-122, December 2005 [doi>10.1145/1117454.1117469]
• 48: Ellen M. Voorhees, Query expansion using lexical-semantic relations, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.61-69, July 03-06, 1994, Dublin, Ireland
• 49: C. Wang, P. Zhang, R. Choi, and M. D. Eredita. Understanding consumers attitude toward advertising. In 8th Americas Conference on Information Systems, 2002.
• 50: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]
• 51: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]
• 52: 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]
• 53: Justin Zobel , Alistair Moffat, Exploring the similarity space, ACM SIGIR Forum, v.32 n.1, p.18-34, Spring 1998 [doi>10.1145/281250.281256]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Performance

Keywords:
online advertising, relevance, web search