Scalable clustering and keyword suggestion for online advertisements

ABSTRACT

We present an efficient Bayesian online learning algorithm for clustering vectors of binary values based on a well known model, the mixture of Bernoulli profiles. The model includes conjugate Beta priors over the success probabilities and maintains discrete probability distributions for cluster assignments. Clustering is then formulated as inference in a factor graph which is solved efficiently using online approximate message passing. The resulting algorithm has three key features: a) it requires only a single pass across the data and can hence be used on data streams, b) it maintains the uncertainty of parameters and cluster assignments, and c) it implements an automatic step size adaptation based on the current model uncertainty. The model is tested on an artificially generated toy dataset and applied to a large scale real-world data set from online advertising, the data being online ads characterized by the set of keywords to which they have been subscribed. The proposed approach scales well for large datasets, and compares favorably to other clustering algorithms on the ads dataset. As a concrete application to online advertising we show how the learnt model can be used to recommend new keywords for given ads.

REFERENCES

• 1: Vibhanshu Abhishek , Kartik Hosanagar, Keyword generation for search engine advertising using semantic similarity between terms, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA [doi>10.1145/1282100.1282119]
• 2: K. Bartz, V. Murthi, and S. Sebastian. Logistic regression and collaborative filtering for sponsored search term recommendation. In Proceedings of the Second Workshop on Sponsored Search Auctions, 2006.
• 3: P. Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA, 2002.
• 4: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003
• 6: Yifan Chen , Gui-Rong Xue , Yong Yu, Advertising keyword suggestion based on concept hierarchy, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341564]
• 7: B. J. Frey, F. R. Kschischang, H. A. Loeliger, and N. Wiberg. Factor Graphs and Algorithms. In Proceedings of the annual Allerton Conference on Communication, Control and Computing, volume 35, pages 666--680, 1997.
• 8: Amruta Joshi , Rajeev Motwani, Keyword Generation for Search Engine Advertising, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.490-496, December 18-22, 2006 [doi>10.1109/ICDMW.2006.104]
• 9: F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2):498--519, 2001.
• 10: P. F. Lazarsfeld and N. W. Henry. Latent Structure Analysis. Houghton Mifflin, 1968.
• 11: G. McLachlan and D. Peel. Finite Mixture Models. Wiley, 2000.
• 12: C. E. Metz. Basic principles of ROC analysis. Seminars in Nuclear Medecine, 4(8), 1978.
• 13: Thomas P. Minka , Rosalind Picard, A family of algorithms for approximate bayesian inference, Massachusetts Institute of Technology, 2001
• 14: David H. Stern , Ralf Herbrich , Thore Graepel, Matchbox: large scale online bayesian recommendations, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526725]

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
          Subjects: Clustering
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Design, Performance