NIPS 2010 Workshop: Machine Learning in Online ADvertising (MLOAD 2010)

Updates

The slides of keynotes and invited talks will be shared soon. Thanks for the contributions of keynote speakers and invited speakers!

Important Dates

Submission deadline: Oct. 23, 2010 Oct. 30, 2010
Notification of Acceptance: Nov. 11, 2010 Nov. 12, 2010
Camera ready: Nov. 22, 2010 Nov. 25, 2010
Workshop Date: Dec. 10, 2010

Online proceeding is available now!

Schedule

7:30-7:45 Opening Remarks
7:45-8:30 Keynote: Machine Learning for Display Advertising [slides]
Foster Provost
8:30-9:00 Invited talk: AdPredictor - Large Scale Bayesian Click-Through Rate Prediction in Microsoft's Bing Search Engine [slides]
Thore Graepel, Joaquin Quinonero Candela
9:00-9:30 Coffee Break
9:30-10:00 Invited talk: Hybrid Bidding for Keyword Auctions [slides]
Ashish Goel
10:00-10:30 Poster Boaster and Discussion Sessions
10:30-15:30 Ski Break
15:30-16:15 Keynote: Visualization and Modeling of the Joint Behavior of Two Long Tailed Random Variables [slides]
Art Owen
16:15-16:45 Invited talk: Click Modeling in Search Advertising: Challenges and Solutions [slides]
Jianchang Mao
16:45-17:05 Invited talk: Digital Advertising: Going from Broadcast to Personalized Advertising [slides]
James Shanahan
17:05-17:30 Coffee Break
17:30-17:50 Invited talk: Machine Learning for Advertiser Engagement [slides]
Tao Qin
17:50-18:30 Panel Discussions


Overview

Online advertising, a form of advertising that utilizes the Internet and World Wide Web to deliver marketing messages and attract customers, has seen exponential growth since its inception over 15 years ago, resulting in a $65 billion market worldwide in 2008; it has been pivotal to the success of the World Wide Web. This success has arisen largely from the transformation of the advertising industry from a low-tech, human intensive, ``Mad Men'' (ref AMC TV Series) way of doing work (that were common place for much of the 20th century and the early days of online advertising) to highly optimized, mathematical, machine learning-centric processes (some of which have been adapted from Wall Street) that form the backbone of many current online advertising systems.

The dramatic growth of online advertising poses great challenges to the machine learning research community and calls for new technologies to be developed. Online advertising is a complex problem, especially from machine learning point of view. It contains multiple parties (i.e., advertisers, users, publishers, and ad platforms such as ad exchanges), which interact with each other harmoniously but exhibit a conflict of interest when it comes to risk and revenue objectives. It is highly dynamic in terms of the rapid change of user information needs, non-stationary bids of advertisers, and the frequent modifications of ads campaigns. It is very large scale, with billions of keywords, tens of millions of ads, billions of users, millions of advertisers where events such as clicks and actions can be extremely rare. In addition, the field lies at intersection of machine learning, economics, optimization, distributed systems and information science all very advanced and complex fields in their own right. For such a complex problem, conventional machine learning technologies and evaluation methodologies are not be sufficient, and the development of new algorithms and theories is sorely needed.

The goal of this workshop is to overview the state of the art in online advertising, and to discuss future directions and challenges in research and development, from a machine learning point of view. We expect the workshop to help develop a community of researchers who are interested in this area, and yield future collaboration and exchanges.

Possible topics include:

  • Dynamic/non-stationary/online learning algorithms for online advertising
  • Large scale machine learning for online advertising
  • Learning theory for online advertising
  • Learning to rank for ads display
  • Auction mechanism design for paid search, social network advertising and microblog advertising
  • System modeling for ad platform
  • Traffic and click through rate prediction
  • Bids optimization
  • Metrics and evaluation
  • Yield optimisation
  • Behavioral targeting modeling
  • Click fraud detection
  • Privacy in advertising
  • Crowd sourcing and inference
  • Mobile advertising and social advertising
  • Public datasets creation for research on online advertising
The above list is not exhaustive, and we welcome submissions on highly related topics too.


Accepted Papers

The papers can be found in workshop online proceeding.

CTR prediction based on click statistic
Konstantin Bauman, Anna Kornetova, Valeriy Topinskiy, Dmitry Leshiner

The Business Next Door: Click-Through Rate Modeling for Local Search
Suhrid Balakrishnan, Sumit Chopra, I. Dan Melamed

Planning-based Approach for Optimizing the Display of Online Advertising Campaigns
Sertan Girgin, Jeremie Mary, Philippe Preux, Olivier Nicol

Pricing Externalities in Real-Time Bidding Markets
Joseph Reisinger, Michael Driscoll

Similarity Models for Ad Relevance Measures
Scott Wen-tau Yih, Ning Jiang

Determining optimal ad frequency capping policy via Markov decision processes to maximize click through rates [poster]
James Shanahan, Dirk Van den Poel

Predictive Client-side Profiles for Keyword Advertising
Mikhail Bilenko, Matthew Richardson

Keynotes

Machine Learning for Display Advertising
Foster Provost (New York University)
Abstract
Most on-line advertisements are display ads, yet as compared to sponsored search, display advertising has received relatively little attention in the research literature. Nonetheless, display advertising is a hotbed of application for machine learning technologies. In this talk, I will discuss some of the relevant differences between online display advertising and traditional advertising, such as the ability to profile and target individuals and the associated privacy concerns, as well as differences from search advertising, such as the relative irrelevance of clicks on ads and the concerns over the content next to which brands' ads appear. Then I will dig down and discuss how these issues can be addressed with machine learning. I will focus on two main results based on work with the successful machine-learning based firm Media6degrees. (i) Privacy-friendly ``social targeting'' can be quite effective, based on identifying browsers that share fine-grained interests with a brand's existing customers--as exhibited through their browsing behavior. (ii) Clicks often are a poor surrogate for conversions for training targeting models, but there are effective alternatives.
This work was done in collaboration with Brian Dalessandro, Rod Hook, Alan Murray, Claudia Perlich, and Xiaohan Zhang.
Foster Provost is Professor, NEC Faculty Fellow, and Paduano Fellow of Business Ethics (Emeritus) at the NYU Stern School of Business. He just retired as Editor-in-Chief of the journal Machine Learning, and in 2001 he co-chaired the program of the ACM KDD conference. He is Chief Scientist for Coriolis Ventures, a NYC-based early stage venture and incubation firm focusing to a large extent on advertising technology. One of his main research interests is predictive modeling with social network data, most recently for on-line advertising. This work won the 2009 INFORMS Design Science Award. His other main research interest these days is the focused intervention of human resources for machine learning, especially based on micro-outsourcing (e.g., Mechanical Turk). Foster has applied these ideas in practice to applications including on-line advertising, targeted marketing, network diagnosis, fraud detection, counterterrorism, and others.

Visualization and Modeling of the Joint Behavior of Two Long Tailed Random Variables
Art Owen (Stanford University)
Abstract
Many of the variables relevant to online advertising have heavy tails. Keywords range from very frequent to obscure. Advertisers span a great size range. Host web sites range from very popular to rarely visited.
Much is known about the statistical properties of heavy tailed random variables. The Zipf distribution and Zipf-Mandelbrot distribution are frequently good approximations.
Much less attention has been paid to the joint distribution of two or more such quantities. In this work, we present a graphical display that shows the joint behavior of two long tailed random variables. For ratings data (Netflix movies, Yahoo songs) we often see a strong head to tail affinity where the major players of one type are over-represented with the minor players of the other. We look at several examples which reveal properties of the mechanism underlying the data. Then we present some mathematical models based on bipartite preferential attachment mechanisms and a Zipf-Poisson ensemble.
This is joint work with Justin Dyer.
Art Owen is Professor of Statistics, Stanford University. He has spent sabbaticals at the University of Chicago, ATT Bell Labs, MSRI and Google Inc. His research interests include statistical inference for high dimensional problems in Internet applications and bioinformatics. Owen is the inventor of empirical likelihood, now widely used in econometrics, and scrambled net quadrature, now widely used in computational finance and in computer graphics. He is an elected fellow of the Institute of Mathematical Statistics.

Invited Talks

Hybrid Bidding for Keyword Auctions
Ashish Goel (Stanford University)
Abstract
Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid auctions where an advertiser can make a per-impression as well as a per-click bid, and the auctioneer then chooses one of the two as the pricing mechanism. We assume that the advertiser and the auctioneer both have separate beliefs (called priors) on the click-probability of an advertisement. We first prove that the hybrid auction is truthful, assuming that the advertisers are risk-neutral. We then show that this auction is different from the existing per-click auction in multiple ways: 1) It takes into account the risk characteristics of the advertisers. 2) For obscure keywords, the auctioneer is unlikely to have a very sharp prior on the click- probabilities. In such situations, the hybrid auction can result in significantly higher revenue. 3) An advertiser who believes that its click-probability is much higher than the auctioneer's estimate can use per-impression bids to correct the auctioneer's prior without incurring any extra cost. 4) The hybrid auction can allow the advertiser and auctioneer to implement complex dynamic programming strategies. As Internet commerce matures, we need more sophisticated pricing models to exploit all the information held by each of the participants. We believe that hybrid auctions could be an important step in this direction.

AdPredictor – Large Scale Bayesian Click-Through Rate Prediction in Microsoft’s Bing Search Engine
Thore Graepel and Joaquin Quiñonero Candela
Abstract>
In the past years online advertising has grown at least an order of magnitude faster than advertising on all other media. Bing and Yahoo! have recently joined forces: all ads on both search engines are now served by Microsoft adCenter and all search results on Yahoo! are powered by Bing. Accurate predictions of the probability that a user clicks on an advertisement for a given query increase the efficiency of the ads network and benefit all three parties involved: the user, the advertiser, and the search engine. This talk presents the core machine learning model used by Microsoft adCenter for click prediction: an online Bayesian probabilistic classification model that has the ability to learn efficiently from terabytes of web usage data. The model explicitly represents uncertainty allowing for fully probabilistic predictions: 2 positives out of 10 instances or 200 out of 1000 both give an average of 20%, but in the first case the uncertainty about the prediction is larger. We discuss some challenges in machine learning for online systems, such as valid metrics, causal loops and biases in the training data.

Click Modeling in Search Advertising: Challenges and Solutions
Jianchang Mao (Yahoo! Labs)
Abstract
Sponsored search is an important form of online advertising that serves ads that match user's query on search result page. The goal is to select an optimal placement of eligible ads to maximize a total utility function that captures the expected revenue, user experience and advertiser return on investment. Most search engines use a pay-per-click model where advertisers pay the search engine a cost determined by an auction mechanism (e.g., generalized second price) only when users click on their ad. In this case, the expected revenue is directly tied to the probability of click on ads. Click is also often used as a proxy for measuring search user experience, and is a traffic driver for advertisers. Therefore, estimation of the probability of click is the central problem in sponsored search. It affects ranking, placement, quality filtering and price of ads.
Estimating click probability given a query-ad-user tuple is a challenging statistical modeling problem for a large variety of reasons, including click sparsity for the long tail of query-ad-user tuples, noisy clicks, missing data, dynamic and seasonal effects, strong position bias, selection bias, and externalities (context of an ad being displayed). In this talk, I will provide an overview on some of the machine learning techniques recently developed in Advertising Sciences team at Yahoo! Labs to deal with those challenges in click modeling. In specific, I will briefly describe: (i) a temporal click model for estimating positional bias, externalities, and unbiased user-perceived ad quality in a combined model; (ii) techniques for reducing sparsity by aggregating click history for sub-queries extracted with a CRF model and by leveraging data hierarchies; and (iii) use of a generative model for handling missing click history features. The talk is intended to give a flavor of how machine learning techniques can help solve some of the challenging click modeling problems arising in online advertising.
Dr. Jianchang (JC) Mao is a Vice President and the head of Advertising Sciences at Yahoo! Labs, overseeing the R&D of advertising technologies and products, including Search Advertising, Contextual Advertising, Display Advertising, Targeting, and Categorization. He was also a Science/Engineering director responsible for development of backend technologies for several Yahoo! Social Search products, including Y! Answers and Y! MyWeb (Social Bookmarks). Prior to joining Yahoo!, Dr. Mao was Director of Emerging Technologies & Principal Architect at Verity Inc., a leader in Enterprise Search (acquired by Autonomy), from 2000 to 2004. Prior to this, Dr. Mao was a research staff member at the IBM Almaden Research Center from 1994 to 2000. Dr. Mao's research interest includes Machine Learning, Data Mining, Information Retrieval, Computational Advertising, Social Networks, Pattern Recognition and Image Processing. He received an Honorable Mention Award in ACM KDD Cup 2002, IEEE Transactions on Neural Networks Outstanding Paper Award in 1996, and Honorable Mention Award from the International Pattern Recognition Society in 1993. Dr. Mao served as an associate editor of the IEEE Transactions on Neural Networks, 1999-2000. He received his Ph.D. degree in Computer Science from Michigan State University in 1994.

Digital Advertising: Going from Broadcast to Personalized Advertising
James G. Shanahan (Independent Consultant)
Abstract
Online advertising is a form of promotion that uses the Internet and World Wide Web for the expressed purpose of delivering marketing messages to attract customers. Examples of online advertising include text ads that appear on search engine results pages, banner ads, in-text ads, or Rich Media ads that appear on regular web pages, portals or applications. Since it inception over 15 years ago, online advertising has grown rapidly and currently accounts for 10\% of the overall advertising spend (which is approximately \$600 billion worldwide)). A large part of the more recent success in this field has come from the following key factors:
* Personalization: offline advertising (via broadcast TV, radio, newspaper etc.) is largely a broadcast form of communication where as digital advertising is much more targeted and thus enables a personalized, and possibly informative, message to consumers.
* Interactivity: internet advertising is becoming increasingly interactive with the advent of new forms of advertising such as social advertising; this is enables advertises and consumers to operate in a more conversant manner.
* Engagement: consumers are spending more time online than with any other form of media thereby enabling a broader reach and deeper connection with consumers.
* Explainabilty: advertisers are beginning to understand their consumers better.
This shift in focus in digital advertising from location (i.e., publisher web pages) to personalization has brought with it numerous challenges some of which have received a lot of research attention in the data mining and machine learning communities over the past 10-20 years. In this talk I will review, along the dimensions outlined above, some of these key technical problems and challenges that arise when adverting becomes personal. This will be done within the context of the elaborate (and ever-evolving) ecosystems of modern day digital advertising where one has to capture, store, and process petabytes of data within the constraints of a, sometimes, sequential workflow. The ultimate goal to is provide millisecond-based decision-making at each step of this workflow that enables customizable and engaging consumer experiences.

Machine Learning for Advertiser Engagement
Tao Qin (Microsoft Research Asia)
Abstract
Advertiser engagement, which goal is to attract more advertisers, make them loyal to the ad platform, and make them willing to spend more money on (online) advertising, is very important for an ad platform to boost its long-term revenue. Industry has paid more and more attention to advertiser engagement. For example, many search engines have provided tools to help advertisers, including keyword suggestion, traffic (number of impressions/clicks) estimation, and bid suggestion. However, from the research point of view, the effort on advertiser engagement is still limited.
In this talk, we discuss the challenges in advertiser engagement, especially from the machine learning perspective. Actually machine learning algorithms can be used in many aspects of online advertising, such as CTR prediction. We propose a number of principles that should be considered when using machine learning technologies to help advertiser engagement.
(1) Accurate. The results of learning algorithms should be as accurate as possible. This principle is the same as that in other machine learning tasks.
(2) Socially fair. The learning algorithms should promote diversity and be fair to even tail advertisers. In this way, more advertisers will feel engaged and the entire ads eco-system will become more healthy.
(3) Understandable. The evaluation metrics and learned models should be easy to interpret. In this way, it is easier for advertisers to diagnose their campaigns and identify the key aspects to improve. This will also make the ad platform more transparent to advertisers and increase their trust in the ad platform.
(4) Actionable. The learning algorithms should provide actionable suggestions/feedback to advertisers. In this way, the advertisers can take effective actions to improve their performances, and therefore stick to the ad platform in a more loyal fashion.
We will show several example problems in online advertising (such as effectiveness evaluation and auction mechanism) and discuss possible solutions based the above principles.
This is joint work with Bin Gao and Tie-Yan Liu.

Paper Submissions

Submissions to the MLOAD workshop should be in the format of extended abstracts; 4-6 pages formatted in the NIPS style. The submission does not need to be blind. Please upload submissions in PDF to this website. Accepted extended abstracts will be made available online at the workshop website. In addition, we plan to invite extended versions of selected papers for a special issue of a top-tier machine learning or information retrieval journal (under discussion).

Program Committee

Misha Bilenko (Microsoft)
Olivier Chapelle (Yahoo! Research)
Jon Feldman (Google)
Bin Gao (Microsoft Research Asia)
Thore Graepel (Microsoft Research Cambridge)
Diane Lambert (Google)
S. Muthukrishnan (Google)
Kishore Papineni (Yahoo! Research)
Dou Shen (Microsoft)
Dirk Van den Poel (University Gent)
Jun Wang (University College London)
Hwanjo Yu (POSTECH)

Organizers

Deepak K. Agarwal (Yahoo! Research)
Tie-Yan Liu (Microsoft Research Asia)
Tao Qin (Microsoft Research Asia)
James G. Shanahan (Independent Consultant)

Contact US

taoqin AT microsoft DOT com