Deep Learning over Multi-field Categorical Data: A Case Study on User Response Prediction

In plain words

Online ads are shown to users many times, and a system must guess how likely a given user is to click a given ad. The inputs are not numbers but labels such as the city, the device, the ad slot and the website. Each label is turned into a long row of 0s with one 1, and a model has to learn how labels from different columns combine. Older models mostly add up the labels one by one, which misses combinations such as "this city on this device".

The paper's idea is to let a neural network learn those combinations. First, a small learned vector is looked up for every label that is present, and the vectors of one column are placed in their own slot. A deep network then reads all slots together. The first version takes the slot vectors from a factorisation machine, a model that learns pairwise interactions. The second version learns the first layer from sampled parts of the sparse input, using either a small Boltzmann-style network or an autoencoder to start the weights.

The authors report that the first version beats the baselines on the pooled advertiser data they use, and that the second is competitive on several single advertisers. The gains are measured in AUC, a ranking score for clicks versus non-clicks.

TL;DR

• Targets: click-through and conversion prediction on multi-field categorical data, where each field is one-hot encoded §1 §3.
• FNN: a factorisation machine gives one dense slot per field; two tanh layers and a sigmoid output sit on top §3.1 fig. 1 eq. 1–eq. 5.
• SNN: a sigmoid first layer over all one-hot features, pre-trained with sampled negative units by an RBM (SNN-RBM) or a denoising autoencoder (SNN-DAE) §3.2 fig. 2.
• Author-reported AUC on iPinYou tab. 1: FNN is best on the pooled data (70.70%); SNN-DAE is best on advertiser 2997, and SNN-DAE and SNN-RBM tie for best on 2261.
• The public code is a Theano port on a small demo sample, and it differs from the paper in several places (see Paper vs code).

Problem

Ad click data is multi-field and categorical. Each record has many fields such as city, device type and ad category, and each field is one-hot encoded into a very large sparse vector. The paper reports about 937.67K binary features on the full iPinYou data §4.1. Linear models such as logistic regression cannot model interactions between fields without hand-built combination features §1 §2. Factorisation machines learn pairwise interactions but are shallow §1 §2. A fully connected deep network on the raw one-hot vector would need about 100 million weights for the first layer with 1M inputs and 100 units §1, which is expensive to train §1.

The paper assumes that deep networks can learn useful high-order patterns from these inputs once the first layer is initialised in a way that makes training tractable §1 §3.1 §3.2.

Method

Input encoding. Each field is one-hot encoded. Field i has one unit per value, exactly one of which is 1 §3.

FNN (factorisation-machine supported network).

1. Train a factorisation machine on the one-hot data. Each feature i gets a bias w_i and a K-dimensional vector v_i; pairwise interactions are inner products <v_i, v_j> §3.1 eq. 6.
2. Build the first-layer input z by concatenating the global bias w_0 and, for each field, the vector z_i = (w_i, v_i^1 … v_i^K) of the feature that is active in that field §3.1 eq. 4 eq. 5. The first layer is therefore sparsely connected: each hidden unit reads one field's slot only §3.1 fig. 1.
3. Hidden layer 1 is l1 = tanh(W1 z + b1) eq. 3. Hidden layer 2 is l2 = tanh(W2 l1 + b2) eq. 2. The output is the predicted click probability y_hat = sigmoid(W3 l2 + b3) eq. 1.
4. Initialise the hidden layers by layer-wise RBM pre-training with contrastive divergence, and train the FM weights by SGD §3.1.
5. Fine-tune all weights by back-propagation of cross-entropy loss eq. 7. Only the FM weights of active features receive an update §3.1 eq. 8 eq. 9.

SNN (sampling-based neural network).

1. The bottom layer is fully connected to the one-hot input with a sigmoid: z = sigmoid(W0 x + b0) §3.2 eq. 10. Because the input is one-hot, this is the sum of the rows of the active features.
2. Pre-train the bottom layer on a sampled version of the input. For each field, keep the positive unit and sample m negative units; all other units are ignored during pre-training §3.2 fig. 2b fig. 2c. Two samplers are used: an RBM trained with contrastive divergence (SNN-RBM) and a denoising autoencoder trained by SGD (SNN-DAE) §3.2.
3. Pre-train the upper hidden layers layer by layer. §3.1 describes this for the hidden layers in general; §3.2 describes pre-training only for the bottom layer §3.1 §3.2.
4. Fine-tune all layers by back-propagation of cross-entropy loss §3.2 eq. 7.

Regularisation. The L2 penalty over all weights and biases is added to the loss eq. 11. Dropout is compared against it and is reported to work better in all compared settings §3.3 §4.5 fig. 4a.

# FNN forward pass  [eq. 4] [eq. 5] [eq. 3] [eq. 2] [eq. 1]
# Input:  active feature index per field (one-hot)
# Output: predicted click probability in (0, 1)

def fnn_predict(active_features, fm_bias, fm_vectors):
    # Slot 0 holds the global bias w_0  [eq. 4]
    # Each field gets K + 1 slots: (w_i, v_i^1 .. v_i^K)  [eq. 5]
    # Fields with no active feature stay at zero  [§3.1]
    z = zeros(1 + num_fields * (K + 1))
    z[0] = fm_bias
    for feature in active_features:
        slot = field_of(feature) * (K + 1) + 1
        z[slot:slot + K + 1] = fm_vectors[feature]
    # First hidden layer, tanh  [eq. 3]
    l1 = tanh(W1 @ z + b1)
    # Second hidden layer, tanh  [eq. 2]
    l2 = tanh(W2 @ l1 + b2)
    # Sigmoid output  [eq. 1]
    return sigmoid(W3 @ l2 + b3)

# Factorisation machine: prediction and one SGD step  [eq. 6] [§3.1]
# Input:  active features (value 1 each), label y in {0, 1}
# Output: updated w0, w, v

def fm_predict(features, w0, w, v):
    # Pairwise term via the identity: half of the squared sum of the
    # vectors minus the sum of their squares  [eq. 6]
    summed = sum(v[i] for i in features)
    squared = sum(dot(v[i], v[i]) for i in features)
    pairwise = (dot(summed, summed) - squared) / 2
    linear = sum(w[i] for i in features)
    return sigmoid(w0 + linear + pairwise), summed

def fm_sgd_step(features, y, w0, w, v, eta, decay):
    # Prediction and the sum vector are computed before any update
    p, summed = fm_predict(features, w0, w, v)
    error = y - p
    # Global bias step  [code: python/fm.py#L197]
    w0 = w0 * (1 - decay) + eta * error
    for i in features:
        # Linear weight step, with the feature value equal to 1
        w[i] = w[i] * (1 - decay) + eta * error
        # Factor step: the other features' sum minus the feature itself
        v[i] = v[i] * (1 - decay) + eta * error * (summed - v[i])
    return w0, w, v

Hyperparameters

Values the paper states are cited to the paper. Values taken from the public code are marked as such and cited to the code; they are not stated in the paper.

Results

Author-reported. Setup: public iPinYou display-ad logs, one training set per advertiser (1458, 2259, 2261, 2997, 3386) and one pooled set; metric AUC; baselines logistic regression (LR) and factorisation machine (FM) §4.1 tab. 1. Hardware and training time are not stated. The table below is copied from tab. 1; the bold marks are the paper's own.

The paper also tested RMSE but does not report it: on unbalanced click data the authors say it barely changes between models §4.1 (footnote). The RMSE table is commented out in the LaTeX source.

Paper vs code

Code: the authors' repository at commit 229ad52 (cloned with --depth 1). Paper claims are cited to the paper, the code to the file and line.

1. Pre-training of FNN hidden layers. The paper says the hidden layers are initialised by layer-wise RBM pre-training §3.1. FNN.py draws all weights uniformly and multiplies them by 4 for tanh, with no pre-training step FNN.py FNN.py. Only the SNN scripts call an RBM or DAE pre-training routine SNN_RBM.py SNN_DAE.py.
2. Regularisation. The paper's penalty covers all weights and biases eq. 11. FNN penalises only the output weights and bias FNN.py. SNN-RBM and SNN-DAE penalise every layer except the bottom one SNN_RBM.py SNN_RBM.py SNN_RBM.py. The FNN code also decays the FM weights by a separate factor lambda_fm that the paper does not mention FNN.py FNN.py.
3. Dropout rate. The paper gives about 0.8 for FNN and about 0.99 for SNN §4.6. Advertiser 2997 uses 0.5 for FNN, with the same rate also applied to the input FNN.py FNN.py. SNN-RBM uses 0.98 SNN_RBM.py and SNN-DAE uses 0.99 SNN_DAE.py.
4. Learning-rate grid. The paper's grid is 1 to 0.0001 in decades §4.3. The code uses 0.002, 0.0006 and 0.0005 as defaults for some models FNN.py SNN_RBM.py SNN_DAE.py. These values are not on the grid.
5. Model selection set. The paper says early stopping and learning-rate choice use a validation set §4.3. All training scripts compute AUC on the test file each epoch and use it for stopping FNN.py SNN_RBM.py SNN_DAE.py. The FM script does the same fm.py fm.py. No validation split is present in the repository.
6. Negative sampling in the RBM sampler. The paper samples m negative units per field at random, and reports m = 2 as best §3.2 §4.3. The RBM sampler uses one deterministic negative per positive: the feature index one below it sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py.
7. Negative sampling in the DAE sampler. The DAE sampler draws k - 1 random negatives from the index gap before each positive, with k = 2 in the script, so one negative per field sampling_based_denosing_autoencoder.py sampling_based_denosing_autoencoder.py sampling_based_denosing_autoencoder.py sampling_based_denosing_autoencoder.py. That is one sampled negative, not the m = 2 of the text.
8. "Denoising" autoencoder. The paper calls the second sampler a denoising autoencoder §3.2. The corruption level defaults to 0 and is not passed by the pre-training call, so no input is corrupted sampling_based_denosing_autoencoder.py sampling_based_denosing_autoencoder.py sampling_based_denosing_autoencoder.py. The DAE learning rate defaults to 0.1 sampling_based_denosing_autoencoder.py.
9. Sparse RBM weight update. The sampled first-layer RBM applies its weight step twice per instance sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py. Its momentum buffer is indexed by the position of a feature in the sorted active list, not by the feature itself sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py.
10. Upper-layer RBM propagation. When pre-training the third weight matrix, the input passed through the first layer is a pre-activation. The sigmoid is applied once, after the second matrix sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py sampling_based_gaussian_binary_rbm_sparse.py. The fine-tuned network applies sigmoid after the bottom layer eq. 10. This reading is from the code only and was not run.
11. Data. The paper uses 19.50M instances and 937.67K features §4.1. The repository ships a demo sample with 133,465 features in the FM model fm.model.txt and a training file of about 26,800 lines train.fm.txt. The README calls it a tiny demo README.md.
12. Missing module. fm.py imports features, which is not in the repository, so the FM script cannot run as shipped fm.py.
13. Hidden-layer count. The paper says the best architecture has three hidden layers, five layers in total §4.4, and Figure 1 shows a four-layer FNN fig. 1. The FNN code has an FM layer and two hidden layers above it FNN.py FNN.py. The SNN code has three hidden layers SNN_RBM.py SNN_RBM.py SNN_RBM.py.

Pitfalls

• Text versus table. §4.2 says FNN and SNN beat LR and FM on all tested datasets §4.2. Table 1 does not support this for SNN: on advertiser 2259 both SNN variants are below LR and FM, and on 3386 both are below LR tab. 1. Only FNN is above LR on every row.
• Loss scale. The training loss is summed over the mini-batch, not averaged FNN.py FNN.py. Dense-layer steps therefore grow with batch size. The FM embedding update in FNN.py is applied per instance FNN.py FNN.py. A learning rate tuned at one batch size does not transfer to another. The paper does not state whether its loss is summed or averaged eq. 7.
• No inverted dropout. The dropped activations are not divided by the keep rate, and inference uses the undropped activations FNN.py FNN.py FNN.py. An implementation that scales at training time should keep the same pairing.
• Global bias is fixed in FNN. w_0 is set once and never updated; only features' embeddings change during fine-tuning FNN.py FNN.py. The paper does not say whether w_0 is trained.
• Checkpoint is one step stale. The stored best parameters are the values returned by the training call for the last mini-batch of an epoch, which are the values before that call's update FNN.py FNN.py. The difference is small but not zero.
• Initial best-weight bug. best_w3 is initialised from w1, which has the wrong shape FNN.py. It is overwritten after the first epoch in practice, but the initialisation is wrong.
• FM checkpoint. The FM script saves the model at the round where it stops, not the best round, and only when it is given ten arguments fm.py fm.py fm.py.
• Stopping rule. The FNN and SNN loops use a counter that rises on each improvement, up to three, and falls otherwise. Training stops when it drops below zero FNN.py FNN.py. Patience is therefore set by the counter's history, not by a fixed number of epochs.
• Hidden sizes are advertiser-specific. The code's sizes are set in branches for advertiser 2997 SNN_RBM.py FNN.py. Other advertisers keep the defaults (300, 300, 100 for SNN), which the paper does not justify.
• Feature-count dependence. The sparse RBM uses a fixed visible width of 32 for the momentum buffer and a hard-coded input dimension sampling_based_gaussian_binary_rbm_sparse.py SNN_RBM.py. Both assume the demo layout (16 fields, each with two indexes after sampling). A different field count needs both changed.
• Pre-training cache. Pre-trained weights are written to a file and reused if it exists, so a changed configuration keeps the old weights SNN_RBM.py SNN_RBM.py.
• Not stated in the paper. Batch size, momentum, number of pre-training epochs, CD steps, FM hyperparameters, FNN hidden sizes for the full data, and the L2 weight are all absent from the text.

Lineage

• Builds on: factorisation machines [rendle2012factorization] (named only; no card in this wiki). Also DNN pre-training [hinton2006reducing] and sampled RBM and autoencoder training as cited in §3.
• Compared against: logistic regression [richardson2007predicting] and the factorisation machine (both named in §4.1).
• Later work: the code README points to a TensorFlow code base by the same authors for product-based networks README.md.