Click-probability prediction (CTR models)

Deep dive

How it works

Parts:

• feature hasher — maps (field, value) to one of 2^b buckets (feature hashing); crosses are hashed pairs
• embedding tables — one d-float row per bucket; nearly all parameters
• interaction layer — FM dot products, cross network or MLP over the looked-up rows
• online trainer — updates on fresh logs, e.g. FTRL per-coordinate rates
• calibrator — fixes the scale after downsampling or drift (calibration)

1. Featurize. Each impression has ~10-100 active categorical features (user segment, item ID, hour, device); dense values are bucketized.
2. Baseline. σ(w₀ + Σ wᵢ) on hashed one-hot features plus hand-picked crosses; a rarely seen pair gets no weight.
3. Factorization machine (Rendle 2010). Each feature gets vᵢ∈ℝᵏ; pair weight ⟨vᵢ,vⱼ⟩, so rare pairs share strength. Σ_{i<j}⟨vᵢ,vⱼ⟩ = ½ Σ_f[(Σᵢ v_if)² − Σᵢ v_if²] makes scoring O(k·n), not O(k·n²).
4. Field-aware FM (Juan 2016). One vector per (feature, other field): more parameters, O(k·n²) scoring, often more accurate.
5. Wide & Deep (Cheng 2016). A linear part over crosses memorizes; an MLP over embeddings generalizes; logits summed, trained jointly. DeepFM (Guo 2017) makes the wide part an FM sharing the embeddings.
6. DCN / DCN-V2 (Wang 2017, 2021). Cross layers x_{l+1} = x₀ ⊙ (W x_l + b) + x_l give explicit bounded-degree crosses; V2 uses a full or low-rank W.
7. DLRM (Naumov 2019). Dense features pass a bottom MLP, categoricals their embedding tables; all pairwise dot products feed a top MLP. Tables are sharded (model parallel), MLPs replicated.
8. Serve: correct, calibrate, fixed position.

 ids ──hash──► embedding rows (memory-bound) ─┐
 dense ──bottom MLP───────────────────────────┤
                interaction: FM dot / cross net / MLP
                                 │
                        top layer ► σ ► q ─correct+calibrate─► p
 downstream: bid × p  |  send if p·value > cost  |  rank by p·margin

Training concerns.

• Fresh data. Inventory and tastes drift in hours: update online on recent logs; FTRL-Proximal gives rare and common features different rates.
• Delayed feedback. Installs and purchases arrive hours to days late; counting "not yet" as negative biases p down. Wait a window, model the delay (Chapelle 2014), or insert late positives.
• Negative downsampling. Keep all positives, each negative with rate w; odds scale by 1/w, so invert with the formula above.
• Metrics. Log loss or normalized cross-entropy (log loss ÷ entropy of the base rate); AUC sees order only, blind to a 2× scale error. Also mean(p)/mean(y) per slice (metrics).
• Position bias. Top slots get clicks regardless of item. Train with position (or a position tower) as input, serve all candidates at one fixed position.

Code

Hashed FM versus logistic regression on the same features, SGD on log loss, plus the downsampling correction. The synthetic label depends on a user × item latent affinity that a linear model cannot express (by construction).

const NB: usize = 1 << 12; // hash buckets shared by all fields
const K: usize = 4;        // FM factor dimension
struct Rng(u64);
impl Rng {
    fn next(&mut self) -> f64 { self.0 ^= self.0 << 13; self.0 ^= self.0 >> 7; self.0 ^= self.0 << 17; (self.0 >> 11) as f64 / (1u64 << 53) as f64 }
    fn gauss(&mut self) -> f64 { (0..12).map(|_| self.next()).sum::<f64>() - 6.0 }
    fn below(&mut self, n: usize) -> usize { (self.next() * n as f64) as usize }
}
/// Hash (field, raw category id) -> bucket; the "hashing trick" (splitmix64 finalizer).
fn bucket(field: u64, v: u64) -> usize {
    let mut z = (field << 32 | v).wrapping_add(0x9E3779B97F4A7C15);
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
    ((z ^ (z >> 31)) % NB as u64) as usize
}
fn sigmoid(z: f64) -> f64 { 1.0 / (1.0 + (-z).exp()) }

/// Label depends on a user x item interaction (latent affinity), not only on main effects.
struct World { user: Vec<[f64; 2]>, item: Vec<[f64; 2]> }
fn sample(w: &World, rng: &mut Rng) -> ([usize; 3], f64) {
    let (u, i, c) = (rng.below(w.user.len()), rng.below(w.item.len()), rng.below(24));
    let aff: f64 = (0..2).map(|d| w.user[u][d] * w.item[i][d]).sum();
    let y = (rng.next() < sigmoid(-1.5 + 2.5 * aff)) as u8 as f64;
    ([bucket(0, u as u64), bucket(1, i as u64), bucket(2, c as u64)], y)
}

/// Factorization machine over active (value 1) hashed features:
/// y = w0 + sum_i w_i + 1/2 sum_f [ (sum_i v_if)^2 - sum_i v_if^2 ]   -> O(k n), not O(k n^2)
struct Fm { w0: f64, w: Vec<f64>, v: Vec<[f64; K]>, use_v: bool }
impl Fm {
    fn new(use_v: bool, rng: &mut Rng) -> Self {
        Fm { w0: 0.0, w: vec![0.0; NB], v: (0..NB).map(|_| std::array::from_fn(|_| 0.1 * rng.gauss())).collect(), use_v }
    }
    fn logit(&self, x: &[usize]) -> (f64, [f64; K]) {
        let mut z = self.w0 + x.iter().map(|&i| self.w[i]).sum::<f64>();
        let mut s = [0.0; K]; // s_f = sum_i v_if
        if self.use_v {
            let mut sq = 0.0;
            for &i in x { for f in 0..K { s[f] += self.v[i][f]; sq += self.v[i][f] * self.v[i][f]; } }
            z += 0.5 * (s.iter().map(|a| a * a).sum::<f64>() - sq);
        }
        (z, s)
    }
    fn step(&mut self, x: &[usize], y: f64, lr: f64, l2: f64) {
        let (z, s) = self.logit(x);
        let g = sigmoid(z) - y; // d logloss / d logit
        self.w0 -= lr * g;
        for &i in x {
            self.w[i] -= lr * (g + l2 * self.w[i]);
            if self.use_v { for f in 0..K { // d logit / d v_if = s_f - v_if
                let gv = g * (s[f] - self.v[i][f]) + l2 * self.v[i][f];
                self.v[i][f] -= lr * gv;
            } }
        }
    }
}
fn logloss(m: &Fm, data: &[([usize; 3], f64)]) -> f64 {
    data.iter().map(|(x, y)| { let p = sigmoid(m.logit(x).0).clamp(1e-12, 1.0 - 1e-12); -(y * p.ln() + (1.0 - y) * (1.0 - p).ln()) }).sum::<f64>() / data.len() as f64
}

/// Model trained on negatives kept with rate `w` outputs q; this restores the base-rate probability.
fn uncorrect(q: f64, w: f64) -> f64 { q / (q + (1.0 - q) / w) }

fn main() {
    let mut rng = Rng(0x2545F4914F6CDD1D);
    let world = World { user: (0..200).map(|_| [rng.gauss(), rng.gauss()]).collect(), item: (0..200).map(|_| [rng.gauss(), rng.gauss()]).collect() };
    let train: Vec<_> = (0..200_000).map(|_| sample(&world, &mut rng)).collect();
    let test: Vec<_> = (0..50_000).map(|_| sample(&world, &mut rng)).collect();
    let rate = test.iter().map(|t| t.1).sum::<f64>() / test.len() as f64;
    let base = -(rate * rate.ln() + (1.0 - rate) * (1.0 - rate).ln()); // entropy of the base rate
    let (mut lr_m, mut fm) = (Fm::new(false, &mut rng), Fm::new(true, &mut rng));
    for _ in 0..8 { for (x, y) in &train { lr_m.step(x, *y, 0.05, 1e-6); fm.step(x, *y, 0.05, 1e-6); } }
    let (l_lr, l_fm) = (logloss(&lr_m, &test), logloss(&fm, &test));
    println!("held-out log loss: constant {base:.4}  LR {l_lr:.4}  FM {l_fm:.4}");
    assert!(l_fm < l_lr - 0.01, "FM must capture the user x item interaction");

    // Negative downsampling: keep every positive, each negative with probability w.
    let (p0, w) = (0.05, 0.1);
    let (mut pos, mut kept) = (0usize, 0usize);
    for _ in 0..400_000 {
        let click = rng.next() < p0;
        if click || rng.next() < w { kept += 1; pos += click as usize; }
    }
    let q = pos as f64 / kept as f64; // inflated training rate, ~0.34
    let p = uncorrect(q, w);
    println!("train rate {q:.4} -> corrected {p:.4} (true {p0})");
    assert!((p - p0).abs() < 0.003);
    assert!((uncorrect(p0 / (p0 + (1.0 - p0) * w), w) - p0).abs() < 1e-12); // exact inverse of the sampling
}

Output (measured, Apple M4 Pro): held-out log loss constant 0.628, LR 0.624, FM 0.416; 4 other seeds: FM 0.409-0.416, LR 0.607-0.624. Corrected rate 0.0501 (true 0.05).

Complexity and constants

• FM: O(k·n) per score or step. Measured (n=3, k=4, tables in cache, one M4 Pro core): 2.7 ns per score, about 24 ns per SGD step (LR 20-24 ns).
• At scale memory decides: a row costs 4d bytes in fp32; 10⁸ rows at d=64 is 25.6 GB (arithmetic), so each lookup is a likely DRAM miss (order of 100 ns).
• Cost drivers: features per request, d, rows, MLP width. DLRM's dot interaction is O(n²d); its Criteo benchmark has 26 categorical and 13 dense features.

Efficiency

• Cost: one score = n row reads (n·4d bytes fp32) + interaction + MLP; n=50, d=64 is ~13 KB of random reads. Bound: memory latency and bandwidth, not FLOPs. Ranking 10³ candidates multiplies it by 10³.
• Levers:
  • int8/fp16 rows — 2-4× smaller tables and traffic (arithmetic) — memory-bound tables (weight quantization); recheck calibration
  • cache hot rows — heavy-tailed IDs, so few rows take most lookups (practice) — skewed frequencies
  • shard by table or row — beyond one host (DLRM paper) — embedding-table sharding
  • user-side vectors once per request — saves lookups per candidate — many candidates per user
  • fewer hash buckets — memory ∝ buckets, some accuracy lost — unbounded ID spaces
• Naive → standard → state of the art:
  • one-hot dictionary, hand-written crosses · memory ∝ distinct features and crosses
  • hashed LR/FM with FTRL · O(n) per score, small tables
  • sharded DLRM/DCN-V2, quantized and cached rows · lookup-bound, tables across hosts or GPUs

Implementation notes

• Hash with a seed per field; 2^b buckets make the modulo a mask.
• Initialize v small and random: s_f − v_if is 0 for a lone feature, so a zero v never moves. Use Adagrad or FTRL; plain SGD suits the toy.
• Keep a calibration layer (isotonic or Platt) fitted on recent logs, separate from the net.
• Log served p, features and position (off-policy evaluation).

Pitfalls

• Forgetting the downsampling correction: here 0.345 instead of 0.05, and an auction overpays.
• Scoring candidates at different positions.
• AUC up, log loss up: ordering improved, scale drifted, and the auction multiplies the scale.
• Calibrated overall, 2× off for a new advertiser, country or device: check per slice.

Variants and alternatives

In production

Display and search ads, feeds, notification and send-time models, app stores (Wide & Deep on Google Play, over a billion users per its abstract), shops and job boards. Auctions price with the output (GSP).

Implementations

Sources

• Rendle, Factorization Machines, ICDM 2010. DOI · code
• Juan et al., Field-aware Factorization Machines for CTR Prediction, RecSys 2016. DOI · code
• Cheng et al., Wide & Deep Learning for Recommender Systems, DLRS 2016. arXiv
• Guo et al., DeepFM, IJCAI 2017. arXiv
• Wang et al., Deep & Cross Network for Ad Click Predictions, ADKDD 2017. DOI
• Wang et al., DCN V2, WWW 2021. arXiv
• Naumov et al., Deep Learning Recommendation Model for Personalization and Recommendation Systems, 2019. arXiv · code
• He et al., Practical Lessons from Predicting Clicks on Ads at Facebook, ADKDD 2014. DOI
• McMahan et al., Ad Click Prediction: a View from the Trenches, KDD 2013. DOI
• Chapelle, Modeling Delayed Feedback in Display Advertising, KDD 2014. DOI