← AI HoodmanNo. 002 · Ads

Negative Downsampling

How do you train on 10B rows when only 1% are clicks?

01of 06
Use the arrows, swipe or the arrow keys to turn the slides. Click a slide to read it page by page.
  1. Slide 1 of 6: 10 billion ad impressions a day. Only 1% get clicked. How do you handle the class imbalance?
  2. Slide 2 of 6: With this much data, the loss function handles the imbalance fine. The real problem is cost. Training data: ad impressions 10 billion rows / day Time User Ad Device Clicked 09:14:02 user_48213 ad_7731 iOS 0 09:14:02 user_90577 ad_1204 Android 0 09:14:03 user_11846 ad_7731 Web 0 09:14:03 user_66092 ad_3358 iOS 0 09:14:03 user_27410 ad_5126 Android 0 09:14:04 user_83355 ad_1204 iOS 0 09:14:04 user_50981 ad_9047 Web 0 09:14:05 user_38724 ad_3358 Android 0 09:14:05 user_71269 ad_7731 iOS 0 ...about 99 of every 100 rows look like this 9.9B 100M non-click rows a day click rows a day
  3. Slide 3 of 6: The standard fix: Negative Downsampling Keep every click. Keep only 10% of non-clicks. 10 clicks 99 non-clicks kept 891 thrown away Training gets ~10x cheaper, and model quality barely changes.
  4. Slide 4 of 6: But there is a catch. Take 1,000 impressions. Real data After downsampling 10 clicks 10 clicks 990 non-clicks 99 non-clicks 1% 9.2% true click rate what the model learns The model predicts 9.2%. That's 9x too high. Ad auctions combine this number with advertiser bids to rank and price ads, so it has to be accurate.
  5. Slide 5 of 6: The correction: Put the thrown-away nonclicks back. p = q / (q + (1 − q) / w) q the raw predicted click rate w the fraction of non-clicks you kept p the corrected predicted click rate Example: q = 10/109 (9.2%), w = 0.1 p = (10/109) / (10/109 + (99/109) / 0.1) = 10 / (10 + 990) = 1%
  6. Slide 6 of 6: Takeaway: Downsample negatives. Correct the predictions.

Keep reading

Negative Downsampling · 1 / 6
  1. Slide 1 of 6: 10 billion ad impressions a day. Only 1% get clicked. How do you handle the class imbalance?
  2. Slide 2 of 6: With this much data, the loss function handles the imbalance fine. The real problem is cost. Training data: ad impressions 10 billion rows / day Time User Ad Device Clicked 09:14:02 user_48213 ad_7731 iOS 0 09:14:02 user_90577 ad_1204 Android 0 09:14:03 user_11846 ad_7731 Web 0 09:14:03 user_66092 ad_3358 iOS 0 09:14:03 user_27410 ad_5126 Android 0 09:14:04 user_83355 ad_1204 iOS 0 09:14:04 user_50981 ad_9047 Web 0 09:14:05 user_38724 ad_3358 Android 0 09:14:05 user_71269 ad_7731 iOS 0 ...about 99 of every 100 rows look like this 9.9B 100M non-click rows a day click rows a day
  3. Slide 3 of 6: The standard fix: Negative Downsampling Keep every click. Keep only 10% of non-clicks. 10 clicks 99 non-clicks kept 891 thrown away Training gets ~10x cheaper, and model quality barely changes.
  4. Slide 4 of 6: But there is a catch. Take 1,000 impressions. Real data After downsampling 10 clicks 10 clicks 990 non-clicks 99 non-clicks 1% 9.2% true click rate what the model learns The model predicts 9.2%. That's 9x too high. Ad auctions combine this number with advertiser bids to rank and price ads, so it has to be accurate.
  5. Slide 5 of 6: The correction: Put the thrown-away nonclicks back. p = q / (q + (1 − q) / w) q the raw predicted click rate w the fraction of non-clicks you kept p the corrected predicted click rate Example: q = 10/109 (9.2%), w = 0.1 p = (10/109) / (10/109 + (99/109) / 0.1) = 10 / (10 + 990) = 1%
  6. Slide 6 of 6: Takeaway: Downsample negatives. Correct the predictions.