Ad click prediction on social networks

01 · CONTEXT

Why predicting clicks underpins an ad system

In online advertising, the advertiser only bids and pays for measurable user responses, such as clicks. The efficiency of the ad auction depends on the accuracy and calibration of click prediction.

Facebook's paper starts from a clear requirement: the prediction system must be robust, adaptable, and able to learn from massive volumes of data. At Facebook, ads are not tied to a query; they specify demographic and interest targeting, and so the volume of eligible ads at each visit can be larger than in sponsored search.

To handle many candidate ads per request, the paper describes a cascade of classifiers of increasing computational cost. Its focus, and this case's, is the final stage: the click prediction model that generates the predictions for the final set of candidates.

02 · METRICS

Measuring well: normalized entropy and calibration

The paper evaluates prediction accuracy, not metrics tied directly to profit and revenue. The two main metrics are normalized entropy (NE) and calibration.

NE is the predictive log loss normalized by the entropy of the background CTR, and the lower the value, the better the prediction. Calibration, in turn, is the ratio of the average estimated CTR to the empirical CTR, that is, of expected clicks to clicks actually observed.

Calibration matters because an accurate, well-calibrated CTR prediction is essential to the success of online bidding and auctions. AUC measures only ranking quality, without considering calibration, while NE measures the quality of the predictions and reflects calibration implicitly.

03 · THE HYBRID MODEL

Boosted trees feeding a logistic regression

The paper's model concatenates boosted decision trees and a sparse, probabilistic linear classifier, and outperforms each of those methods alone by more than 3%.

Before the trees, the paper describes two simple transformations for a linear classifier. One is to discretize a continuous feature and treat the bin index as a categorical feature. The other is to create tuple features, which for categoricals means, in brute force, the Cartesian product; not every combination is useful and the useless ones can be pruned.

1. The visit to Facebook triggers a request for candidate ads to the ranker.

2. The impression's features pass through boosted decision trees, which work as a feature transformation.

3. Each tree's output becomes a categorical feature, whose value is the index of the leaf the instance falls into, and goes on as input to the sparse linear classifier.

4. Fitting the linear classifier to this binary vector is equivalent to learning weights for the set of rules that the trees' paths represent.

On their own, logistic regression and trees have comparable accuracy, with logistic regression slightly better; it is the combination that gives the jump in accuracy. The tree transformations reduce NE by more than 3.4% relative to the model without them, while most feature engineering experiments only reduce NE by a fraction of a percentage point.

04 · DATA FRESHNESS

Always retrain: the model ages

The paper trains a model on one day and evaluates it on the following days. Accuracy drops as the delay between training and testing grows, and training daily instead of weekly reduces NE by about 1%. The authors conclude that retraining daily is worth it.

The trees are trained in batch, which can take more than 24 hours on a single CPU core for hundreds of trees and hundreds of millions of instances; in practice, concurrency on a multicore machine reduces that to a few hours. The paper indicates that the trees can be trained every day or every couple of days, while the linear classifier can be trained in near real time with online learning.

For the online training of the linear classifier, the paper compares learning rate schemes for stochastic gradient descent. The per-coordinate rate had the best accuracy, with NE almost 5% lower than the per-weight rate, which performed worst among the options.

The paper also compares this logistic regression (LR) with BOPR, a Bayesian online learning scheme for probit regression.

Because BOPR gives the full predictive distribution, it can be used to compute percentiles used in explore-and-exploit schemes.

05 · ONLINE JOINER

Generating the click label in real time

To train the linear classifier online, you need to generate training data in real time. The paper presents an experimental system, the online joiner, whose critical operation is to join the labels (click or no click) to the training inputs (ad impressions) online, and which delivers the training fluxo to an infrastructure called Scribe.

The positive label is well defined, the click, but there is no such thing as a no-click button. An impression gets the negative label if the user does not click after a fixed, sufficiently long period, and the size of this waiting window needs to be tuned carefully. This is the problem of delayed labels: the negative label can only be decided after waiting.

1. When visiting Facebook, the user triggers an ad request to the ranker; in parallel, each ad and the features used in ranking enter the impression stream.

2. If the user clicks the ad, the click enters the click stream.

3. The joiner performs a distributed join between the two streams, using the request ID as the main key, and uses a HashQueue: a FIFO queue as the buffer window and a hash map to label impressions with fast access.

4. The labeled impression only goes out to the training stream after the join window expires; if no click was joined, it goes out as a negative example.

5. The trainer learns continuously from the training stream and periodically publishes new models to the ranker.

6. As a safeguard, the paper cites anomaly detection mechanisms, for example disconnecting the trainer from the joiner if the distribution of the training data changes suddenly.

A window that is too long delays real-time training data and increases the memory used to hold impressions waiting for the click. A window that is too short misses some clicks, because the corresponding impression may already have been discarded and labeled as no click.

This cutoff affects click coverage, the fraction of all clicks successfully joined to impressions. Without full coverage, the training set is biased, with an empirical CTR slightly lower than the truth. The paper reports that it is easy to reduce this bias to a fraction of a percentage point with windows of manageable memory.

In this experimental setup, the trainer learns continuously from the training stream and periodically publishes new models to the ranker. This forms a short, closed loop, in which changes in the feature distribution or in model performance can be captured, learned, and corrected in quick succession.

The paper suggests anomaly detection as a defense: for example, automatically disconnecting the online trainer from the joiner if the distribution of the training data changes abruptly.

06 · FEATURES, COST, AND CALIBRATION

What weighs the most and how to contain cost

The paper splits the features into two types. Contextual features depend only on current information about where the ad will be shown, such as the device or the current page. Historical features depend on previous interactions with the ad or the user, such as the ad's CTR over the last week or the user's average CTR.

A few features concentrate the explanatory power: the 10 most important account for about half of the total importance, and all of them are historical.

Prediction latency also grows with the number of trees: more trees make prediction slower, with diminishing returns, since almost all of the NE improvement comes from the first 500 trees.

To control training cost, a common technique is to reduce the data volume. Uniform subsampling of rows is easy to implement and the resulting model can be served without modification. With only 10% of the data, NE loses just 1% relative to the full set, with no loss of calibration.

1. One day of impressions can have an enormous number of instances, and reducing the volume of training data is a common technique to control cost.

2. Negative downsampling tackles class imbalance; the paper reports that it can speed up training and improve model performance.

3. A model trained with downsampled negatives also calibrates its prediction in the downsampled space.

4. The model must be recalibrated for live traffic, so that the ranker receives predictions mapped back to the real CTR.