Product-based Neural Networks for User Response Prediction

In plain words

Many web services have to guess whether a person will click something, such as an ad, a news item or a product. The information about that person and that item is a list of labelled categories, for example a city, a weekday and an ad slot. Such lists are usually turned into a very long row of on/off switches, one per possible category value. Simple models only catch simple patterns in that data, and ordinary neural networks have trouble with the sheer number of switches.

The paper's network, the Product-based Neural Network (PNN), first maps each category to a short list of numbers that is learned during training. It then multiplies pairs of these lists, so the network can see how two categories work together. A normal stack of layers combines everything into one click probability. Two versions differ in how each pair is multiplied: one gives a single number per pair, the other a small grid per pair.

The authors test on two real ad-click datasets, Criteo and iPinYou, and report that their models score higher than the baselines they compare against. These are the authors' own numbers.

TL;DR

• PNN predicts a click probability from multi-field categorical data: learned field embeddings, a product layer over pairs of fields, then ReLU layers and a sigmoid output §3.1 eq. 1.
• IPNN uses inner products (one value per field pair); OPNN uses outer products, here collapsed by a superposition trick §3.1.1 §3.1.2 eq. 14.
• Author-reported AUC: IPNN 77.79% on Criteo, OPNN 81.74% on iPinYou; the best baseline is CCPM on both (76.71% and 76.38%) tab. 1 tab. 2.
• The official code is a small TensorFlow demo whose defaults differ from the paper (one hidden layer, no dropout, no L2 on LR/FM, pairwise forms without the reduction). Implement from the paper and use the code only as a reference.

Problem

• Categorical data with many fields, one-hot encoded, is very sparse and high-dimensional. Plain DNNs cannot take such inputs directly because of the huge feature space [abstract] §1.
• LR, GBDT and FM depend on feature engineering to capture high-order patterns §1. FM models pairwise feature interactions §3, and the paper says such models are limited in mining high-order patterns §2.
• FNN learns embeddings by pre-training a factorization machine, so the quality of the embeddings is limited by that FM §1 §2.
• In an MLP the first layer adds its inputs, which the authors argue is a poor fit for interactions between fields §1.
• CCPM convolves only neighbouring fields, so it misses interactions between distant fields §2. PUNN does not learn local dependencies and does not give bounded outputs §2.
• Assumptions: binary click labels, a log-loss objective and one-hot inputs grouped by field §3 §3.1.

Method

The paper proposes one architecture with two product layers. Each step below cites the paper.

1. Embedding. Every field i is one-hot encoded, and its embedding is f_i = W0_i times its slice of the input, with M dimensions §3.1 eq. 8. The embeddings are learned from scratch, not pre-trained §1.
2. Linear signal. The embeddings are stacked into z = (f_1, ..., f_N) §3.1. The linear part of the first hidden layer uses l_z^n = W_z^n ⊙ z eq. 5 eq. 10.
3. Quadratic signal. A product g(f_i, f_j) is computed for every pair of fields, which defines the pairwise feature interaction §3.1. The quadratic part of the first hidden layer uses l_p^n = W_p^n ⊙ p eq. 5.
4. First hidden layer. l_1 = ReLU(l_z + l_p + b_1), with D_1 nodes §3.1 eq. 3. The paper names layer widths D_i but never gives values §3.1.
5. Further hidden layers. l_2 = ReLU(W_2 l_1 + b_2) §3.1 eq. 2. The experiments use three hidden layers in total §4.4.
6. Output. ŷ = σ(W_3 l_2 + b_3), a sigmoid on one unit §3.1 eq. 1.
7. Loss. Log loss against the click label, y = 1 for click and 0 otherwise §3.1 eq. 9.

IPNN (inner product) sets g(f_i, f_j) = ⟨f_i, f_j⟩, which is a scalar per pair §3.1.1. The full pairwise weights cost O(N²(D_1 + M)) time §3.1.1. The paper then assumes W_p^n = θ^n (θ^n)^T with θ^n ∈ R^N, so the quadratic term collapses into one squared norm per hidden node §3.1.1 eq. 11 eq. 12. Its stated cost becomes O(D_1 MN) §3.1.1. A more general K-order decomposition is mentioned but not evaluated §3.1.1 eq. 13.

OPNN (outer product) sets g(f_i, f_j) = f_i f_j^T, an M × M matrix per pair §3.1.2. Without superposition the cost is O(D_1 M² N²) §3.1.2. The paper replaces the sum of all pair products with the outer product of the summed embedding, p = f_Σ f_Σ^T with f_Σ = Σ_i f_i §3.1.2 eq. 14. Then W_p has shape D_1 × M × M, and the stated cost is O(D_1 M (M + N)) §3.1.2.

PNN* concatenates an inner-product layer and an outer-product layer §4.2. Its AUC is below IPNN and OPNN on both datasets tab. 1 tab. 2.

# PNN forward pass, shared by IPNN and OPNN  [§3.1] [eq. 1]
# Input:  x, one-hot over N fields; M = embedding size
# Output: y_hat, predicted click probability

def pnn_forward(x):
    # Embed field i: f_i = W0_i times its one-hot slice  [eq. 8]
    fields = [embed_field(x, i) for i in range(N)]    # (N, M)
    # Linear signal: all embeddings, flattened  [§3.1]
    linear = flatten(fields)                          # (N * M)
    # Quadratic signal: one product term per pair of fields  [§3.1]
    products = pair_products(fields)                  # g(f_i, f_j), i < j
    # First hidden layer, ReLU of linear and product parts  [eq. 3] [eq. 5]
    hidden = relu(linear_term(linear) + product_term(products) + b1)
    # Further hidden layers, three in total in the experiments  [§4.4]
    hidden = hidden_stack(hidden)
    # Sigmoid output  [eq. 1]
    return sigmoid(W3 @ hidden + b3)

# IPNN product term with the first-order reduction  [§3.1.1] [eq. 11]
# Input:  fields, N vectors of size M; thetas, D1 vectors of size N
# Output: l_p, one value per hidden node (D1,)

def ipnn_product_term(fields, thetas):
    # Weight each field by theta: delta_i^n = theta_i^n f_i  [§3.1.1]
    weighted = [[thetas[n][i] * fields[i] for i in range(N)]
                for n in range(D1)]
    # Sum the weighted fields for each hidden node  [eq. 11] [eq. 12]
    sums = [sum(weighted[n]) for n in range(D1)]     # (D1, M)
    # Squared norm of each sum, the form eq. 11 derives  [eq. 11]
    return [dot(s, s) for s in sums]                 # (D1,)

# OPNN product term with superposition  [§3.1.2] [eq. 14]
# Input:  fields, N vectors of size M
# Output: p, one M x M matrix shared by all hidden nodes

def opnn_product_term(fields):
    # Superpose all field vectors into one  [eq. 14]
    superposed = sum(fields)                          # (M)
    # Outer product of the superposed vector  [eq. 14]
    return outer(superposed, superposed)              # (M, M)

Key equations:

\hat{y} = \sigma(\mathbf{W}_3 \mathbf{l}_2 + b_3) eq. 1

\mathbf{l}_2 = \mathrm{relu}(\mathbf{W}_2 \mathbf{l}_1 + \mathbf{b}_2) eq. 2

\mathbf{l}_1 = \mathrm{relu}(\mathbf{l}_z + \mathbf{l}_p + \mathbf{b}_1) eq. 3

\mathbf{W}_p^n \odot \mathbf{p} = \Big\langle \sum_i \boldsymbol{\delta}_i^n, \sum_i \boldsymbol{\delta}_i^n \Big\rangle eq. 11

\mathbf{l}_p = \Big( \big\Vert \textstyle\sum_i \boldsymbol{\delta}_i^1 \big\Vert, \ldots, \big\Vert \textstyle\sum_i \boldsymbol{\delta}_i^{D_1} \big\Vert \Big) eq. 12

\mathbf{p} = \sum_{i=1}^{N} \sum_{j=1}^{N} \mathbf{f}_i \mathbf{f}_j^T = \mathbf{f}_\Sigma \mathbf{f}_\Sigma^T, \quad \mathbf{f}_\Sigma = \sum_{i=1}^{N} \mathbf{f}_i eq. 14

Hyperparameters

Results

Author-reported. Setup: Criteo and iPinYou (see Hyperparameters), trained with SGD and implemented in TensorFlow §4 §4.2. Baselines: LR, FM, FNN, CCPM §4.2. PNN* is the paper's concatenated variant §4.2. Tables are printed as TABLE I to III in the paper and are cited here as tab. 1 to 3.

Criteo tab. 1:

iPinYou tab. 2:

Significance, log loss only tab. 3: IPNN is below 1e-6 against LR, FM, FNN and CCPM; OPNN is below 1e-6 against LR, FNN and CCPM and below 1e-5 against FM. The test used is not named §4.4.

The paper's bold marks: on Criteo IPNN is best on all four metrics; on iPinYou OPNN is best on AUC, and PNN* is best on log loss, RMSE and RIG tab. 1 tab. 2.

Learning curves on iPinYou show the network models converging faster than LR and FM, and the PNNs converging faster than the other networks fig. 3.

Paper vs code

Official code: https://github.com/Atomu2014/product-nets, commit f0ba27444c89ed745fad27db1aa866e7b2ccabd8 (default branch, shallow clone). The paper's footnote links it §4. The README names the first author as its contact README.md, so the repository is attributed to the authors. The repository has no LICENSE file, so no code is quoted and every reference is by path and line. The code was read but not run: the data is not in the repo main.py.

Discrepancies:

• Depth. Paper: three hidden layers §4.4. Code: one hidden layer of 500 units plus a single linear unit that feeds the sigmoid [code: python/main.py#L151-L152].
• Dropout. Paper: 0.5 on hidden layers §4.4. Code: keep probability 1 everywhere main.py models.py.
• L2 on LR and FM. Paper: used §4.4. Code: coefficient 0 [code: python/main.py#L73] main.py.
• IPNN. Paper: the first-order reduction, eq. 11 and 12 §3.1.1. Code: it computes all N(N-1)/2 inner products and feeds them to a dense layer [code: python/models.py#L339-L363] models.py. That is the unreduced form. The README says the complexity-reducing tricks were removed because they restricted capacity README.md.
• OPNN. Paper: superposition, eq. 14, with W_p in R^(D_1 × M × M) §3.1.2. Code default ('mat'): one M × M kernel per field pair, of shape M × pairs × M models.py models.py. This is not the superposition. The 'vec' and 'num' options also work per pair [code: python/models.py#L415-L418] models.py.
• PNN*. Paper: concatenated inner and outer layers §4.2. Code: not implemented; only pnn1 and pnn2 are selectable main.py main.py.
• Metrics. Paper: AUC, RIG, log loss, RMSE §4.3. Code: only AUC is printed main.py.
• Criteo preprocessing. Paper: down-sampling, then recalibration §4.1.1. Code: reads pre-split files and predicts with no recalibration [code: python/main.py#L24-L25] main.py. The data preparation is in other repositories README.md.
• iPinYou setup. Paper: each advertiser's last 3 days are test §4.1.2. README example: a single advertiser, 2997 README.md.
• Stopping rule. Paper: not stated §4.4. Code: early stopping on test AUC main.py.
• Optimiser. Paper: SGD §4.2. Code: gradient descent, lr 0.1, batch 1024 main.py main.py.
• Initialisation. Paper: not stated. Code: uniform Xavier, zero biases [code: python/utils.py#L143-L147] models.py. The bound uses the sum of all dimensions utils.py, which matches the usual Glorot bound for 2-D weights but not for the 3-D 'mat' kernel.
• Shuffling. Code shuffles the training set seven times [code: python/utils.py#L53-L55]. Paper: not stated.
• Layer norm. The layer_norm option is accepted and set to True, but its code is commented out main.py models.py. It has no effect.

Consistent with the paper: embedding size 10 main.py, ReLU hidden activations main.py, sigmoid output with log loss models.py.

Pitfalls

• Eq. 11 and eq. 12 disagree in form. Eq. 11 derives the squared norm of each summed vector, but eq. 12 is printed with a single norm. The implementer should take the squared form, since eq. 11 is the derivation, and check it with a small test. This is my reading; the paper does not say so.
• Layer widths are missing. The network has three hidden layers §4.4, but D_1 and D_2 are never given §3.1. Any number reported as a PNN configuration is a guess unless it comes from the code, and the code's 500-unit demo is not the paper's network.
• Costs in the reduced forms. The paper's linear-in-N costs need the eq. 12 and eq. 14 reductions §3.1.1 §3.1.2. The official demo uses the unreduced forms, so the cost is quadratic in N models.py models.py.
• "Consistently outperform" is not uniform. On iPinYou the best AUC (OPNN) and the best log loss and RIG (PNN*) come from different models tab. 2. PNN* trails IPNN and OPNN on AUC on both datasets tab. 1 tab. 2.
• Single numbers. No seeds, repeats or variance are reported tab. 1 tab. 2. The baselines' tuning is not stated §4.2. Differences of a few tenths of a point cannot be separated from run-to-run noise with this evidence.
• Recalibration. The paper gives the Criteo recalibration formula §4.1.1, but does not say whether the reported Criteo numbers use it. The code has no recalibration main.py.
• Early stopping on test data. The demo chooses the stopping point by test AUC main.py. The paper does not say how its reported model was chosen §4.4.
• Dropout is part of the recipe. The demo runs without dropout [code: python/main.py#L153], so its behaviour differs from the paper's setting §4.4.
• Field count is hard-coded. The demo sets 26 categorical fields [code: python/utils.py#L17]. The paper does not state the field count for either dataset §4.1.
• Pre-training is only suggested. §3.2 suggests initialising from a trained FNN or FM part, but reports no experiment §3.2. The reported results use learned embeddings from scratch §1.
• Activation claim. The paper's comparison of activations covers FNN, IPNN and OPNN only fig. 5 §4.5.3. The text gives no numbers for it.
• Extended version. The README points to an extended version, arXiv:1807.00311 README.md. It is not part of this wiki and nothing from it is used here.
• TensorFlow version. The code uses the TensorFlow 1.x session API (for example tf.Session and tf.sparse_placeholder) models.py. The code was not run here.

Lineage

• Builds on: FNN, which uses pre-trained FM embeddings §1 §2; factorization machines, the pairwise inner-product model §3. Neither has a card in this wiki.
• Compared against: LR, FM, FNN, CCPM §4.2 tab. 1 tab. 2. CCPM is a convolutional click model over neighbouring fields §2.
• Superseded by: not in this wiki. The README points to an extended journal version, arXiv:1807.00311, which is not used here README.md.