Web-Scale Bayesian Click-Through rate Prediction for Sponsored Search Advertising in Microsoft's Bing Search Engine

Published 21 June 2010

Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, Ralf Herbrich

Citations460

TL;DR

A new Bayesian click-through rate (CTR) prediction algorithm used for Sponsored Search in Microsoft's Bing search engine is described, based on a probit regression model that maps discrete or real-valued input features to probabilities.

Abstract

We describe a new Bayesian click-through rate\n(CTR) prediction algorithm used for Sponsored\nSearch in Microsoft's Bing search engine. The\nalgorithm is based on a probit regression model\nthat maps discrete or real-valued input features to\nprobabilities. It maintains Gaussian beliefs over\nweights of the model and performs Gaussian\nonline updates derived from approximate\nmessage passing. Scalability of the algorithm is\nensured through a principled weight pruning\nprocedure and an approximate parallel\nimplementation. We discuss the challenges\narising from evaluating and tuning the predictor\nas part of the complex system of sponsored\nsearch where the predictions made by the\nalgorithm decide about future training sample\ncomposition. Finally, we show experimental\nresults from the production system and compare\nto a calibrated Naïve Bayes algorithm.

Keywords

Computer ScienceDecision SciencesBusiness, Management and Accounting

IEEE Transactions on Neural NetworksReinforcement Learning: An Introduction

25,692 Citations2005

MIT Press eBooksIntroduction to Reinforcement Learning

6,868 Citations1998Richard S. Sutton, Andrew G. Barto

In Reinforcement Learning, Richard Sutton and Andrew Barto provide a clear and simple account of the key ideas and algorithms of reinforcement learning.

IEEE Transactions on Information TheoryFactor graphs and the sum-product algorithm

6,481 Citations2001Frank R. Kschischang, Brendan J. Frey +1 more

A generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, that computes-either exactly or approximately-various marginal functions derived from the global function.

BiometrikaON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLES

2,302 Citations1933W. R THOMPSON

American Economic ReviewInternet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords

1,633 Citations2007Benjamin Edelman, Michael Ostrovsky +1 more

The MIT Press eBooksMap-Reduce for Machine Learning on Multicore

1,253 Citations2007Cheng-Tao Chu, Sang Kyun Kim +5 more

This work shows that algorithms that fit the Statistical Query model can be written in a certain "summation form," which allows them to be easily parallelized on multicore computers and shows basically linear speedup with an increasing number of processors.

Predicting clicks

1,043 Citations2007Matthew Richardson, Ewa Dominowska +1 more

This work shows that it can be used to use features of ads, terms, and advertisers to learn a model that accurately predicts the click-though rate for new ads, and shows that using this model improves the convergence and performance of an advertising system.

DSpace@MIT (Massachusetts Institute of Technology)A family of algorithms for approximate bayesian inference

902 Citations2001Thomas P. Minka, Rosalind W. Picard

This thesis presents an approximation technique that can perform Bayesian inference faster and more accurately than previously possible, and is found to be convincingly better than rival approximation techniques: Monte Carlo, Laplace's method, and variational Bayes.

View PDF

International Statistical ReviewIdiot's Bayes—Not So Stupid After All?

872 Citations2001David J. Hand, Keming Yu

Obtaining calibrated probability estimates from decision trees and naive Bayesian classifiers

656 Citations2001Bianca Zadrozny, Charles Elkan

It is concluded that binning succeeds in significantly improving naive Bayesian probability estimates, while for improving decision tree probability estimates the recommend smoothing by -estimation and a new variant of pruning that is called curtailment.