Representing Random Utility Choice Models with Neural Networks

In plain words

Companies often need to predict which of several options a customer will pick, for example which hotel from a search page or which travel mode. Classic models for this assume a specific mathematical form for how people weigh the options, and they can miss real behaviour. Other approaches throw a generic machine learning classifier at the problem, which can be flexible but may predict choices that no consistent customer would make.

This paper builds a neural network that keeps the classic idea of "each customer gives every option a random value and picks the best one", but lets the network learn the value function. Randomness for unseen product and customer traits is handled by averaging over several sampled versions of those traits. The authors show that this structure can get as close as wanted to any model of this kind, and that the result can be fit with standard deep learning tools. On two real choice datasets it predicted the chosen option better than the benchmarks the authors tried, while a random forest did better on one dataset's log-likelihood.

TL;DR

• RUMnet is a feed-forward network that outputs choice probabilities. It averages K^2 softmax outputs over sampled unobserved product and customer attributes §2.2 §2.3.
• Any random utility maximization (RUM) choice model can be approximated arbitrarily closely by a RUMnet, and the reverse holds too §3 [Proposition 1].
• Trained with negative log-likelihood, RUMnet gets the best accuracy on Swissmetro (0.793) and Expedia (0.425) among the tested models tab. 1.
• Results are author-reported. There is an official MIT-licensed repository that was checked against the paper; it differs from the paper in epochs, patience and activation [Paper vs code].

Problem

A choice model predicts, for a customer with attributes z and an offered set (assortment) A of products with attributes x, the probability that each product is picked §1. Parametric RUM models such as multinomial logit (MNL), nested logit and latent-class MNL depend on the modeller's chosen utility function and distributional assumptions §1 §2.1. Model-free classifiers such as random forests and vanilla neural networks drop the RUM structure. The authors argue this can hurt generalisation when the number of attributes or distinct products is large §1 §6.4.

The paper asks three questions: whether the full class of RUM models can be approximated by a compact neural architecture, whether it can be trained from limited choice data, and how it compares with model-free methods §1.

Assumptions: attributes are continuous or categorical and lie in a compact set §2.1; the unobserved product and customer attributes are independent (independence of unobserved attributes, IUA) §2.1; ties have probability zero §2.1; attributes are pre-normalised to [-1, 1] for the theory §4.1; the assortment size is bounded by kappa §2.1. The theory does not assume realizability, so the model may be misspecified §4.1.

Method

The RUM model draws unobserved product attributes eps(x) and customer attributes nu(z) at random. The utility U(x, eps(x), z, nu(z)) is bounded and uniformly continuous, and the chosen product is the one with the highest utility §2.1. Choice probabilities are the probability that a product's utility is the maximum §2.1.

RUMnet replaces the random fields by sample averages. Draw K samples of each field and approximate the choice probability by an average over the K^2 sample pairs, where each sample is a deterministic function §2.2. Each sampled function is a feed-forward network N_eps_k1 (products) or N_nu_k2 (customers), and utilities come from a network N_U §2.2. The argmax indicator is replaced by a softmax over alternatives, which is the Gumbel-noise smoothing of the choice probability §2.2.

The resulting probability for alternative x in assortment A is

\pi^{\sf RUMnet}_N(x, z, A) = \frac{1}{K^2} \sum_{k_1=1}^{K} \sum_{k_2=1}^{K} \Pr_{\delta}\left[ N_U(x, N_{\epsilon_{k_1}}(x), z, N_{\nu_{k_2}}(z)) + \delta_x > \dots \right] §2.2

With standard Gumbel noise the inner probability is a softmax §2.2. Each network in the architecture is a ReLU feed-forward network in the theory §4.1, while the experiments use ELU activations §6.2 app. E.

The architecture has four meta-layers §2.3:

1. Concatenate the observed product attributes of the assortment and the customer attributes into one input vector §2.3.
2. Pass each product through N_eps_k1 and the customer through N_nu_k2, and form h = x_i, N_eps_k1(x_i), z, N_nu_k2(z) for each pair (k1, k2) §2.3 fig. 1.
3. Pass each h through N_U to get one utility per alternative and per sample pair, then apply a softmax over the alternatives §2.3 fig. 2.
4. Average the probabilities over the K^2 sample pairs §2.3.

Training uses empirical risk minimisation with the negative log-likelihood of the observed choice §4.1 eq. 2:

L_S(\pi) = -\frac{1}{T} \sum_{t=1}^{T} \log\left(\pi(y_t, z_t, A_t)\right) eq. 2

Estimation is ordinary multi-label classification training in Keras with an Adam optimiser §4.1 §6.2 app. E. The paper uses early stopping and label smoothing as regularisers app. E.

# RUMnet choice probabilities for one choice event  [§2.2] [§2.3]
# Input:  products (kappa, d_x), customer (d_z,), K product and K customer nets
# Output: choice probabilities (kappa,), summing to 1

def rumnet_choice_probs(products, customer, eps_nets, nu_nets, utility_net):
    # Accumulate softmax outputs over the K^2 sample pairs  [§2.2]
    total = zeros(products.shape[0])                     # (kappa,)
    for eps_net in eps_nets:
        # Unobserved product attributes, one sample per alternative  [§2.3]
        product_samples = eps_net(products)              # (kappa, d_eps)
        for nu_net in nu_nets:
            # Unobserved customer attributes, one sample per customer  [§2.3]
            customer_sample = nu_net(customer)           # (d_nu,)
            # Stack [x_i, N_eps(x_i), z, N_nu(z)] for each alternative  [§2.3]
            inputs = concat(
                products,
                product_samples,
                repeat(customer, products.shape[0]),
                repeat(customer_sample, products.shape[0]),
            )                                            # (kappa, d)
            # Utility of each alternative under this sample pair  [§2.3]
            utilities = utility_net(inputs)              # (kappa,)
            # Softmax over alternatives replaces the argmax  [§2.2] [§2.3]
            total = total + softmax(utilities)           # (kappa,)
    # Average over the K^2 sample pairs  [§2.2] [§2.3]
    return total / (len(eps_nets) * len(nu_nets))

# Empirical negative log-likelihood over T choice events  [§4.1] [eq. 2]
# Input:  chosen (T,), products (T, kappa, d_x), customers (T, d_z)
# Output: scalar loss

def choice_nll(chosen, products, customers, available):
    # Choice probabilities, unavailable items masked  [app. E]
    probs = batch_choice_probs(products, customers, available)  # (T, kappa)
    # Log-probability of each observed choice  [eq. 2]
    chosen_probs = probs[arange(T), chosen]                    # (T,)
    # Average negative log-likelihood  [eq. 2]
    return -mean(log(chosen_probs))

# Training loop with validation-based early stopping  [app. E] [§6.2]
# Input:  train and validation splits, max_epochs, patience, batch size 32
# Output: model with the best validation loss

def fit(model, train, valid, max_epochs, patience):
    # Track the best validation loss and the weights that reached it  [app. E]
    best_loss = inf
    best_weights = model.get_weights()
    epochs_since_best = 0
    for epoch in range(max_epochs):
        # One pass of Adam over shuffled mini-batches  [app. E]
        train_epoch(model, train)
        # Stop after `patience` epochs with no validation gain  [app. E]
        loss = choice_nll_on(model, valid)
        if loss < best_loss:
            best_loss = loss
            best_weights = model.get_weights()
            epochs_since_best = 0
        else:
            epochs_since_best += 1
            if epochs_since_best > patience:
                break
    # Restore the weights from the epoch with the best validation loss  [app. E]
    model.set_weights(best_weights)
    return model

Result of the paper's theory in words: the set of RUMnet choice models is dense in the set of RUM models, so the approximation error can be made arbitrarily small with enough sample pairs and a large enough network §3 [Proposition 1]. For estimation, the generalisation gap does not grow with K but does grow exponentially with depth §4.2 [Proposition 2].

Hyperparameters

The paper has no separate training hyperparameters for the theory. The table gives the settings for the experiments. Values come from the appendix table of training parameters app. E and the main-text benchmark description §6.2.

Results

Author-reported. Setup: Swissmetro (about 10K observations, three alternatives: Swissmetro, train, car) and Expedia (about 398K search queries, up to 39 alternatives including no-purchase), 10-fold cross-validation, log-likelihood loss (lower is better) and accuracy (higher is better) on test folds §6.3 app. E. Standard errors are in parentheses tab. 1.

Headline numbers, as the paper states them §6.3:

• RUMnet has the highest accuracy on both datasets among the benchmarks, and the lowest Expedia loss. The random forest has the lowest Swissmetro loss tab. 1.
• All neural models beat MNL by more than 20% in log-likelihood on both datasets §6.3.
• Differences between RUMnet and DeepMNL are called statistically significant by paired t-tests, with p = 5.4e-2 on Swissmetro and 9.33e-10 on Expedia §6.3 (footnote).
• Random forests show a high level of overfitting on Expedia, which the paper ties to the larger input dimension §6.3 §6.4 fig. 5.
• Synthetic Setting 1 (MNL truth): RUMnet almost recovers ground truth loss §5.2 fig. 3.
• Synthetic Setting 4 (independence of unobserved attributes): RUMnet has a gap of about 4% in log-likelihood over latent-class MNL at T = 10^3 in favour of RUMnet; the two converge at T about 10^4 §5.2 fig. 4.
• Ranking-based synthetic data (10 products, 10 rankings): RUMnet with K = 20 reaches a test loss of 1.3840 and accuracy 0.3867, against a ground-truth test loss of 1.3743 and accuracy 0.3868 app. E, ranking table.

The paper gives a single number for largest training time: about 45 minutes for the largest RUMnet on Swissmetro and about 36 hours on Expedia app. E.

Paper vs code

The official repository is antoinedesir/RUMnet (MIT License, copyright 2023 antoinedesir), at commit d14fd77497537036c919d7b69c1557cef8f1acf9. The owner is one of the paper's authors. The repository was found through a GitHub repository search for "RUMnet". The paper itself has no code link; the arXiv page lists no code, only site-wide service links.

• Gumbel noise. The paper motivates the softmax as Gumbel-noise smoothing of the argmax §2.2. The code applies a softmax to the utilities and adds no explicit noise models.py. The paper's theory allows other noises, so this is a choice the code makes, not a contradiction.
• Averaging over K^2. The code loops over all pairs of product and customer samples and averages the softmax outputs models.py, matching meta-layer 4 §2.3.
• Activation. The theory uses ReLU §4.1; the experiments and the code use ELU §6.2 app. E models.py.
• Epochs and patience. The Swissmetro configuration uses 2,000 epochs and patience 300 config_general.json, while the paper's table gives 1,000 epochs and patience 200 app. E. The Expedia configuration uses 50 epochs and patience 10 config_general.json, while the paper's table gives 100 epochs and patience 10 app. E. The paper's reported numbers may come from a different run than the shipped configs.
• Label smoothing. The code passes the configured label smoothing to Keras' categorical cross-entropy experiment_auxiliary.py. Values match the paper for both real datasets. A separate loss in the same file uses a fixed 0.03 smoothing experiment_auxiliary.py; which of the two the reported experiments used is not checked.
• Mixing with the uniform distribution. Each model multiplies the softmax by (1 - tol) and adds tol / n; the config sets tol = 0 for both datasets, so this term is off models.py config_general.json config_general.json. The paper does not mention it.
• Extra variant. The Swissmetro configs include a RUMnet_hybrid with 1 product sample and 40 customer samples [code: src/swiss_metro/modelsArchitecture/RUMnet_hybrid/config_modelsArchitecture.json#L17-L18]. It is not in the paper's tables.
• Synthetic experiments. The repository has experiment synthetic HTML files; the synthetic configs were not checked against §5.1 and app. D.
• Not checked. Data preprocessing for Expedia and Swissmetro, the exact optimizer call for the RUMnet builder, and the normalisation to [-1, 1] were not verified in code.

Pitfalls

• Reproducibility of the real-data numbers. The code's configs do not match the paper's tables for epochs and patience [Paper vs code]. An implementer should expect a gap if they follow the paper's table alone.
• Random seed. The paper does not state a seed app. E. The code uses seed 1234 config_general.json.
• Masking unavailable items. For neural models the paper masks unavailable products in training so they are not picked app. E. Random forests need fixed-size assortments, so the paper fills them with dummy products whose log-price is 10^4 and whose other features are zero, then renormalises probabilities app. E. The Expedia outside option has all product features zero except is_no_purchase = 1 app. E.
• Depth penalty. The generalisation bound grows exponentially in depth l and does not depend on K §4.2 [Proposition 2]. The sample size needed to estimate small choice probabilities is Omega(kappa e^{2M}) §4.2.
• Sample size K is a bias-variance knob, not free. The representation result says K can be chosen of order 1/eps^2 times a polynomial in log(1/eps), l, kappa and e^M §4.2 [Proposition 3]. The paper gives no concrete K for the experiments beyond the table values §6.2.
• Compute. Training is an order of magnitude slower than random forests. The paper says it is unclear whether this is inherent or an implementation issue, and it does not use distributed computing app. E.
• Label smoothing formula. The paper names label smoothing as the regulariser app. E but does not give the formula. The code relies on Keras' implementation experiment_auxiliary.py.
• Loss direction. The paper's Table 1 reports log-likelihood loss where lower is better and accuracy where higher is better tab. 1. Do not mix the two when ranking models.
• Section and equation numbers were counted from the LaTeX source, in source order (sections 1 to 7; appendix A to E). They were not checked against a compiled PDF. Figure numbers follow the order of the floats in the source.

Lineage

• Builds on: the mixed-MNL result of McFadden and Train, which the paper uses for the approximation proof §2.1 §3; the ranking-based choice models of Farias et al. §2.4; TasteNet §2.4 and DeepMNL §2.4, which are special cases of RUMnet with K = 0 or a linear utility.
• Compared against: MNL, latent-class MNL, TasteNet, DeepMNL, a vanilla neural network and random forests tab. 1 §6.1. Ranking-based models estimated with EM and mixed-integer programming in the appendix app. E.
• Superseded by: not stated in the paper.