Catching the drift: learning broad matches from clickthrough data

ABSTRACT

Identifying similar keywords, known as broad matches, is an important task in online advertising that has become a standard feature on all major keyword advertising platforms. Effective broad matching leads to improvements in both relevance and monetization, while increasing advertisers' reach and making campaign management easier. In this paper, we present a learning-based approach to broad matching that is based on exploiting implicit feedback in the form of advertisement clickthrough logs. Our method can utilize arbitrary similarity functions by incorporating them as features. We present an online learning algorithm, Amnesiac Averaged Perceptron, that is highly efficient yet able to quickly adjust to the rapidly-changing distributions of bidded keywords, advertisements and user behavior. Experimental results obtained from (1) historical logs and (2) live trials on a large-scale advertising platform demonstrate the effectiveness of the proposed algorithm and the overall success of our approach in identifying high-quality broad match mappings.

REFERENCES

• 1: IAB Internet Advertising Revenue Report conducted by PricewaterhouseCoopers (PWC), November 2008. {online} http://www.iab.net/insights_research/530422/1357.
• 2: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, 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.1148177]
• 3: Mikhail Bilenko , Raymond J. Mooney, Adaptive duplicate detection using learnable string similarity measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956759]
• 4: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 5: R. C. Bunescu and M. Pasca. Using encyclopedic knowledge for named entity disambiguation. In Proceedings of EACL-06, 2006.
• 6: Huanhuan Cao , Daxin Jiang , Jian Pei , Qi He , Zhen Liao , Enhong Chen , Hang Li, Context-aware query suggestion by mining click-through and session data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401995]
• 7: B. Carterette and R. Jones. Evaluating search engines by modeling the relationship between relevance and clicks. In Proceedings of NIPS-07, 2007.
• 8: 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]
• 9: Kenneth Ward Church , Patrick Hanks, Word association norms, mutual information, and lexicography, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.76-83, June 26-29, 1989, Vancouver, British Columbia, Canada [doi>10.3115/981623.981633]
• 10: 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]
• 11: W. W. Cohen, P. Ravikumar, and S. E. Fienberg. A comparison of string distance metrics for name-matching tasks. In Proceedings of the IJCAI-03 Workshop on Information Integration on the Web, pages 73--78, 2003.
• 12: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 13: S. Cucerzan and E. Brill. Spelling correction as an iterative process that exploits the collective knowledge of web users. In Proceedings of EMNLP-04, pages 293--300, 2004.
• 14: Ofer Dekel , Shai Shalev-Shwartz , Yoram Singer, The Forgetron: A Kernel-Based Perceptron on a Budget, SIAM Journal on Computing, v.37 n.5, p.1342-1372, January 2008 [doi>10.1137/060666998]
• 15: Francois Fouss , Alain Pirotte , Jean-Michel Renders , Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 [doi>10.1109/TKDE.2007.46]
• 16: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062]
• 17: Ariel Fuxman , Panayiotis Tsaparas , Kannan Achan , Rakesh Agrawal, Using the wisdom of the crowds for keyword generation, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367506]
• 18: Qi Guo , Eugene Agichtein, Exploring mouse movements for inferring query intent, 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.1390462]
• 19: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 20: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, 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.1076063]
• 21: Thorsten Joachims , Filip Radlinski, Search Engines that Learn from Implicit Feedback, Computer, v.40 n.8, p.34-40, August 2007 [doi>10.1109/MC.2007.289]
• 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: Ron Kohavi , Randal M. Henne , Dan Sommerfield, Practical guide to controlled experiments on the web: listen to your customers not to the hippo, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281295]
• 24: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 25: Qiaozhu Mei , Duo Zhang , ChengXiang Zhai, A general optimization framework for smoothing language models on graph structures, 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.1390438]
• 26: D. Metzler, S. T. Dumais, and C. Meek. Similarity measures for short segments of text. In Proceedings of ECIR-07, 2007.
• 27: J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In A. J. Smola, P. Bartlett, B. Schölkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, pages 185--208. MIT Press, 1999.
• 28: 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]
• 29: M. Regelson and D. Fain. Predicting click-through rate using keyword clusters. In Proceedings of the Second Workshop on Sponsored Search Auctions, 2006.
• 30: 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]
• 31: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062]
• 32: 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]
• 33: Victor S. Sheng , Foster Provost , Panagiotis G. Ipeirotis, Get another label? improving data quality and data mining using multiple, noisy labelers, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401965]
• 34: Ellen M. Voorhees, Variations in relevance judgments and the measurement of retrieval effectiveness, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.315-323, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291017]
• 35: C. Wang, P. Zhang, and R. Choi. Understanding consumers attitude toward advertising. In Eighth Americas Conference on Information Systems, pages 1143--1148, 2002.
• 36: Ryen White , Ian Ruthven , Joemon M. Jose, The Use of Implicit Evidence for Relevance Feedback in Web Retrieval, Proceedings of the 24th BCS-IRSG European Colloquium on IR Research: Advances in Information Retrieval, p.93-109, March 25-27, 2002
• 37: W. T. Yih and C. Meek. Improving similarity measures for short segments of text. In Proceedings of AAAI-07, 2007.
• 38: Ding Zhou , Shenghuo Zhu , Kai Yu , Xiaodan Song , Belle L. Tseng , Hongyuan Zha , C. Lee Giles, Learning multiple graphs for document recommendations, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367517]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Experimentation

Keywords:
keyword similarity, keyword-based advertising, online learning