Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
41,443 characters · 12 sections · 42 citation commands
Deep Learning for Choice Modeling
\onehalfspacing
\let\thefootnote\relax\footnotetext{$^*$ Equal contribution.}
Choice models are used to explain or predict the choice behaviour of an individual or segment among a set of alternatives. It has been widely studied in various fields including economics, marketing, operations research, and psychology. In practice, choice models help the firm to understand customer behaviour and serve as pillar for revenue management to support decisions of assortment, marketing, and pricing. In this paper, we develop deep learning-based choice models with an emphasis on learning the choice model from data. Specifically, we consider two settings of choice modeling: (i) the feature-free setting where no additional feature is available and (ii) the feature-based setting to utilize the product and customer features.
\paragraph{Probabilistic choice models}\
There is a rich literature on choice modeling under the feature-free setting. The choice models aim to characterize the probability of choosing a product given an assortment (a set of offered products). The prevalent choice models include multinomial logit model (MNL) , Markov chain choice model (MCCM) blanchet2016markov, non-parametric choice model (NP) farias2009data, mixture choice model mcfadden2000mixed, etc. The existing literature focuses mainly on the analytical properties of these models and the corresponding revenue optimization problems. However, the learning/parameter estimation of these models remains less studied and the solutions so far have been unsatisfactory.
Existing methods to learn a choice model include:
Compared to the classic choice models, our deep learning-based choice models have two advantages. First, it has a large model capacity, and empirically, we show that one neural network model with a fixed architecture is capable of recovering both simple choice models such as MNL and complex choice models such as MCCM and NP. Second, it enables an effective learning procedure with better sample and computation efficiency than the above listed methods.
\paragraph{Neural network models in utility modeling}\
Another line of literature well utilizes the availability of the product and customer features. The works along this line usually model the latent utility of each product as a parameterized (neural network) function of the features and then relate the choice probabilities with the latent utilities through an MNL model. The learning of these models is essentially to recover the function parameters through the observations of customer's choice behaviour.
The idea is originated from bentz2000neural which uses neural network to capture the non-linear effects of features on the latent utility. A few recent works wang2020deep,han2020neural,sifringer2020enhancing, wong2021reslogit,aouad2022representing study different application contexts and explore different neural network architectures for the feature-utility mapping. In addition to the product and customer features, gabel2022product also encode history purchase information. chen2021estimating take a different route and consider the random forest model as the mapping function.
We term this line of works as deep learning-based utility modeling instead of choice modeling, because these works mainly focus on predicting the unobserved product utilities with the observed features. However, unlike the classic literature on choice modeling, this line of works pays little attention to the assortment effect -- the interactions between the products within (and possibly outside) the set of offered products. This brings two negative implications. First, some of these existing neural network models require all the training samples to have a fixed-size assortment. This requirement can be hardly met in many application contexts due to reasons such as product availability and profitability. Second, it fails to capture the effect that the assortment has on the choice probability (see Table (ref) in the next section for a real-world example). Intuitively, a customer's choice behaviour is not only determined by product and customer features, but also affected by the assortment offered to the customer in a complicated manner. In fact, to model the assortment effect is one of the main theme of the feature-free choice modeling literature.
Another common drawback of the existing deep learning approaches is that they all require the availability of some product or customer features. When there is no feature available, these models will degenerate and output a uniform choice probability. Differently, our paper proposes the first deep learning-based choice model to handle the feature-free setting. Also, we propose the first neural network models to explicitly capture the assortment's effect on choice probabilities and thus allow the training data to have variable assortment size. Importantly, we make a distinction between the feature-free model and the feature-based model not by the availability of the features, but by whether the downstream application is interested in a population-level or personalized choice model.
To summarize, our contributions are as follows:
Consider a set of $n$ potential products $\mathcal{N}=\{1,2,...,n\}$ that can be offered to customers. A discrete choice model is a probabilistic model that describes the customers' choice behaviour under various assortments. An assortment $\mathcal{S}\subset \mathcal{N}$ is a subset of $\mathcal{N}$ and it denotes the products offered to the customer to choose from. Practically, the assortment can be determined by the product availability (such as hotel rooms and flights), and the seller may also decide the assortment to maximize the profits (by removing less profitable products from the assortment). The choice model prescribes the probability of choosing product $i$ conditional on the assortment $\mathcal{S}$: $$\mathbb{P}(i|\mathcal{S}) \text{ for all } i\in\mathcal{N} \text{ and } \mathcal{S}\subset \mathcal{N}.$$ In particular, $\mathbb{P}(i|\mathcal{S})=0$ for $i\notin \mathcal{S},$ i.e., the customer cannot choose a product not offered in the assortment. In this way, a choice model
dictates $2^n-1$ probability distributions, each of which corresponds to one possible assortment. In practical contexts, there is usually a “no-purchase” option where the customer ends up with purchasing no product from the offered assortment. The no-purchase option can be captured by one product (say, $n$-th) in $\mathcal{N}.$ If no purchase is allowed, then we always have $n\in \mathcal{S}.$
A tabular parameterization of the choice model $\mathcal{M}$ generally requires $\Omega(n\cdot 2^n)$ parameters. Additional structures are introduced to facilitate efficient learning and inference.
The random utility model (RUM) is the most prevalent class of choice models. It assigns a utility for each product and models the choice behavior according to the principle of utility maximization. Specifically, the utility of the $i$-th product $$U_i=u_i+\epsilon_i \text{ for } i\in\mathcal{N}.$$ Here $u_i$'s are deterministic and represent the mean utility of purchasing the $i$-th product among the population. $\epsilon_i$ are mean-zero, possibly dependent random noises that capture the utility heterogeneity among the customers. Under the RUM,
For simplicity, we assume $\epsilon_i$'s are continuous random variables so that the utility maximizer is always unique. Different distributions of $\epsilon_i$'s specialize the general-form RUM into different concrete choice models. In this paper, we use the following two as running examples of RUM.
Multinomial Logit Model (MNL). The celebrated multinomial logit model assumes $\epsilon_i$'s take mean-zero Gumbel distribution (with scale parameter 1). With the Gumbel-max trick gumbel1954statistical, the choice probability follows,
When there is a feature vector $f_i$ associated with each product, then one can represent the deterministic utility $u_i=\theta^\top f_i$ and obtain the linear MNL model javanmard2020multi. Also, several works replace $u_i$ with a neural network function of $f_i$ to obtain the DeepMNL model bentz2000neural,sifringer2020enhancing,wang2020deep.
Markov Chain Choice Model (MCCM). The MCCM blanchet2016markov defines a discrete-time Markov chain on the space of products $\mathcal{N}$ and models each customer's choice through the realization of a sample path. Specifically, it assumes a customer arrives to product $i$ with probability $\lambda_i$ (interpreted as the initial state of the Markov chain). Then if the product is in the assortment $\mathcal{S}$, the customer purchases it and leaves. Otherwise, the customer transitions from product $i$ to product $j$ with probability $\rho_{ij}$. Naturally, $\sum_{i\in\mathcal{N}} \lambda_i=1$ and $\sum_{j\in\mathcal{N}} \rho_{ij}=1$ for all $i\in\mathcal{N}.$ Let $X_t\in\mathcal{N}$ denote the product (state) that the customer visits at time $t$, and define the first hitting time $\tau=\{t\ge0: X_t\in\mathcal{S}\}.$ Then, under the MCCM, $$\mathbb{P}(i|\mathcal{S}) \coloneqq \mathbb{P}(X_{\tau}=i).$$ The MCCM is proved as a generalization of MNL; with more number of parameters, the MCCM has a larger model capacity to capture more complex choice behavior.
Both MNL and MCCM can be viewed as a RUM. This fact is evident for MNL based on its definition, but no so much for MCCM at first sight. berbeglia2016discrete first establishes MCCM as a RUM through a random walk argument.
Under the RUM, although the choice probability is determined jointly by the utilities and the assortment, the contributions of these two aspects are separate. Specifically, the assortment will only affect the final choice through the constraint on the candidate products (to obtain the maximum utility in (ref)), but it will not affect the utilities, neither $u_i$ nor $\epsilon_i$. In other words, RUM assumes that the utility $U_i$'s distribution are independent from and not affected by the assortment $\mathcal{S}.$ A probabilistic statement of this principle is known as the regularity property gallego2019revenue.
However, as remarked by chen2022decision, there is an increasing body of experimental evidence, arising in the various fields, which suggests that the aggregate choice behavior of customers is not always consistent with this regularity property and thus often violates the principle of the RUM. For instance, the following table summarizes a behavioral experiment involving subscriptions to The Economist (reproduced from ariely2008predictably).
In Case I, an assortment with two products (options) are available, while in Case II, a clearly inferior option of Print-Only is added. The addition of Print-Only twists customer utilities for the other two options, which is reflected by the change in the numbers of subscribers. Generally, it means that the assortment $\mathcal{S}$ will not only determine the products to choose from, but also affect the intrinsic utility of each product $U_i$'s.
The practical example above motivates the study of non-parametric choice models such as farias2009data and chen2022decision. Also, it distinguishes our models with the existing deep learning-based choice/utility models in that our models take into account this assortment effect when predicting the choice probabilities. In the following, we introduce the permutation-based non-parametric choice model as a representative that does not belong to the class of RUM.
Non-parametric (NP) Choice Model. The NP choice model farias2009data, farias2013nonparametric assumes that there exists a distribution $\lambda: \text{Perm}_\mathcal{N} \rightarrow[0,1]$ over the set $\text{Perm}_\mathcal{N}$ of all possible permutations of the products. There are $n!$ customer types and each customer type has a preference list of the products corresponding to one permutation in $\text{Perm}_\mathcal{N}$. Customers always purchase the most preferred product in the perference list. Then the choice probability is given by $$\mathbb{P}(i|\mathcal{S}) \coloneqq\sum_{\sigma \in \text{Perm}_i(\mathcal{S})} \lambda(\sigma) $$ where the set $$\text{Perm}_i(\mathcal{S})\coloneqq\{\sigma\in\text{Perm}_{\mathcal{N}}: \sigma(i)<\sigma(j)\text{ for all } j\neq i \in \mathcal{S}\}$$ contains all customer types/permutations under which product $i$ is the most preferable product in the assortment $\mathcal{S}.$
The NP choice model has exponentially many parameters and thus a larger model capacity than MNL and MCCM. There are also other choice models include mixed multinomial logit model mcfadden2000mixed, nested logit model wen2001generalized, tree-based choice model chen2022decision, etc.
An important application of choice modeling is the assortment optimization problem. The seller aims to find the assortment that maximizes the profits
where $r_i$ is the profits/revenue of selling one unit of product $i$. For choice models such as MNL and MCCM, there exist polynomial-time algorithms to solve the problem. For general choice models, heuristic algorithms are proposed, such as the revenue-ordered strategy talluri2004revenue and the greedy strategy jagabathula2014assortment.
The learning of a choice model refers to the identification of a choice model $\mathcal{M}$ from the available data
Here each observation consists of a choice $i_k$ made under the assortment $\mathcal{S}_k.$ Throughout this paper, we use $n=|\mathcal{N}|$ to denote the number of products, and $m$ to denote the number of samples. We make the following two remarks.
First, the learning of a choice model should be viewed as a generative modeling task rather than discriminative modeling. Notably, exponentially many probability distributions -- one for each assortment as in (ref) -- need to be learned simultaneously from the data. This challenge can be further exaggerated when the choice model contains exponentially many parameters such as farias2009data, chen2022decision.
Second, the learning task suffers from the efficiency issue in the rare-event probability estimation asmussen2007stochastic. Consider learning a choice model with $n$ products. The probability of choosing each product is on the order of $1/n$ under a large assortment. Consequently, the standard deviation of the estimator is also on the order of $1/\sqrt{n}$ (taking Bernoulli variable as an example), which is significantly larger than the mean. Thus it inevitably requires a larger amount of samples to reduce the variance and accurately estimate such small probability.
We first discuss the plain setting where there is no feature associated with each product or each customer, and the training data is $\mathcal{D}$ (as in (ref)). This is the most straightforward and widely studied setting in the literature of choice modeling. We use this setting to illustrate the prototypes of our two neural network models and will incorporate the product and customer features in the later sections.
Mathematically, a neural network maps the assortment input $S \in \{0,1\}^n$ to the output $Y\in [0,1]^n$, $$Y=g_\theta(S)$$ where $\theta$ encapsulates all the model parameters. Here $S=(s_1,...,s_n)$ is a binary encoding of an assortment $\mathcal{S}$ where $s_i=1$ if $i\in\mathcal{S}$ and $s_i=0$ if $i\notin\mathcal{S}$. The output $Y=(Y_1,...,Y_n)$ is a vector supported on the probability simplex with $Y_i=\mathbb{P}(i|\mathcal{S})$.
Figure (ref) describes our two neural network models:
Gated-Assort-Net (GAsN): It takes the assortment vector $S$ as its input layer and runs through a number of fully connected layers. Finally, it uses the assortment $S$ again to create an output gate to ensure $\mathbb{P}(i|\mathcal{S})=0$ if $i\notin \mathcal{S}$.
Res-Assort-Net (RAsN): It implements the idea of residual learning he2016deep and involves the input assortment $S$ recursively throughout the propagation. As in the Gated-Assort-Net, it uses the assortment to create an output gate to ensure $\mathbb{P}(i|\mathcal{S})=0$ if $i\notin \mathcal{S}$.
Throughout the paper, we use the cross-entropy (CE) loss to train all our neural network models.
Table (ref) summarizes our first group of experiments. We compare the performance of GAsN and RAsN against several benchmark methods of learning choice models, as well as the oracle performance of the true distribution (equivalently, the negative entropy of the true distribution). The training data are generated from the true models of MNL, MCCM, and NP. We make the following observations. First, both GAsN and RAsN benefit from a larger sample size, while the performances of maximum likelihood estimation (MLE) and expectation maximization (EM) do not improve as the sample size increases. Second, when the true model is MNL, we know the method of MLE is provably asymptotically optimal and this is unsurprisingly verified from our experiment. But when the true model becomes more complex, such as MCCM and NP, the neural network models show their advantage. Third, it requires a large sample size to learn a complex true model. For example, under the true model of MCCM or NP, none of these methods give a satisfactory performance when the sample size is $1,000$. Overall, GAsN and RAsN perform consistently well in recovering these true models with sufficiently amount of data such as $m=5000$. They have the model capacity to capture complex structures and they are also capable of fitting a simpler true model such as MNL. In comparison, the existing choice models either suffer from too little model capacity such as MNL, or have no reliable method for parameter estimation such as MCCM or NP. It is widely acknowledged that the models of MCCM and NP enjoy good analytical properties, but without an effective learning/estimation algorithm, these models can only provide qualitative insights but not reliable decision support.
Two other important aspects are (i) the assortment distribution in the training data and (ii) the depth and width of the two network models. For (i), we find the performance of the neural network model is quite robust in terms of the generalization on the assortment domain. Specifically, we train the neural network model with one distribution to generate the assortments $\mathcal{S}_k$'s (in training data $\mathcal{D}$) and find that it performs well on the test data where the assortments are generated from a different assortment distribution (also known as the out-of-domain performance). For (ii), we vary the depth and width of the neural network models and test their performances under the settings of (i) feature-free and (ii) with features. The default design of GAsN and RAsN has the intermediate layers of the same dimension $n$ as the input layer. We find that to fit a moderate size choice model with 20-50 products, a depth of 1-2 hidden layers for GAsN or 2-3 residual blocks for RAsN is sufficient. And also, the performance of the model remains stable with wider width for the intermediate layers. We defer the details of these two aspects to Appendix A.1 and A.2 respectively.
Now we extend our neural network models to the setting of choice modeling with features. We first make a distinction between product feature and customer feature:
Figure (ref) and Figure (ref) describe our choice networks with features. The neural networks inherit the architectures in the feature-free setting, but both take an additional vector of inputs which we call as the latent utilities. Both feature-based networks of GAsN(f) and RAsN(f) encode product features and customer features to obtain one latent utility for each product. The product encoder is an $l$-layer fully-connected network shared by all the products ($l=1$ in our experiments). By default, the number of nodes in the intermediate layers of the encoder is the same as the dimension of the encoder's input. When there is no available customer feature, we can simply treat the customer feature as 1 for all the samples.
Table (ref) presents a synthetic experiment with only product (static) features to illustrate a new insight for choice modeling with features. The experiment first ignores all the product features and trains GAsN and RAsN as in the feature-free setting. Then it takes into account the product features and trains the feature-based version of the two neural networks. We find that both versions of the networks are capable of recovering the true model from the comparison against the oracle performance, and that the two versions of each neural network achieve a similar performance. This might be counter-intuitive at the first sight, because the product features may contain useful information about the product's utility, and ignoring the features may accordingly hurt the performance. However, we argue that the product utilities are essentially encoded in the choice data $(i_k, \mathcal{S}_k)$'s but not in the product features. In fact, the experiment shows that such utilities can be learned by the neural networks of GAsN and RAsN without explicitly accessing the product features. An alternative interpretation is that the product utility here should be viewed as a population-level utility that reflects the preference or popularity of a product over the whole population. Things become different when customer features are also available. In that case, the choice behaviour of each data sample is determined by the personalized utilities, and thus the product and customer features become indispensable.
We emphasize that whether to include the (dynamic) customer features in choice modeling is determined not by the availability of the features, but by the downstream application. Recall that the assortment optimization problem (ref) aims to find an assortment that maximizes profits under a choice model. For a brick-and-mortar store or an online retailer where the personalized assortment is not allowed, customer features should not be used to fit the choice model even if they are available, because one is more interested in the population-level choice behavior. This explains why the majority of the literature on choice modeling has been devoted to feature-free models. And it also underscores the potential wide applicability of feature-free networks of GAsN and RAsN despite their simple architectures.
In this section, we conduct numerical experiments on two real datasets -- SwissMetro (\url{https://transp-or.epfl.ch/pythonbiogeme/examples_swissmetro.html}) and Expedia Search (\url{https://www.kaggle.com/competitions/expedia-personalized-sort/overview}). These two datasets contain dynamic customer/product features; that is, the features associated with each training samples may be different with each other. The SwissMetro dataset is a public survey data set to analyze traveller preference among three transportation modes, and the Expedia dataset consists of hotel search records and the associated customer choices. We refer more details of these two datasets to Appendix (ref).
We implement a number of benchmark models: MNL, feature-based MNL, TasteNet han2020neural, DeepMNL wang2020deep, sifringer2020enhancing, random forest chen2021estimating. The MNL and feature-based MNL are learned by MLE. For both TasteNet and DeepMNL, it models the product utility $u_i$ as a function of the product and customer features and maps the utility to choice probability via the model of MNL (ref). Tastenet assumes the utility $u_i$ as a linear function of product features and uses the customer feature to determine the coefficients of the linear function, while DeepMNL concatenates the customer and product features and feeds both into a fully-connected network to obtain the utility $u_i$. Both models do not utilize the assortment other than the MNL part.
From the results in Table (ref), our two neural networks give a better performance than the benchmark models. In fact, our neural network models take the most natural architectures, and the key difference is that our models explicitly take the assortment as an input. This experiment result shows that even with the presence of product and customer features, the assortment can help to better explain customer choices. Comparing the two datasets, the Gated-Assort-Net(f) performs better on SwissMetro, while Res-Assort-Net(f) performs better on Expedia. Recall that the Res-Assort-Net(f) has a stronger usage of the assortment vector throughout the architecture than Gated-Assort-Net(f). Accordingly, one explanation can be that for the transportation setting, customer choices are less affected by the available options but more by their personal preference, but for the hotel search, the customer choices are more affected by the provided assortment which gives Res-Assort-Net(f) more advantage. As for the random forest model, it is trained as a discriminative model using both features and assortment as input, so we believe it also better potential with some further model recalibration.
Model Calibration. Another important aspect of probabilistic model is model calibration. Ideally, we hope the predicted probability matches the empirical/true probability. For deep learning models, a high accuracy may often come with an overconfidence in predictions (overestimation of the true probabilities) guo2017calibration, which is called miscalibration. Figure (ref) is the calibration plot of predicting Metro for the SwissMetro dataset, and we observe that all the neural network models stay mostly below the 45-degree reference line, i.e., suffer from an over-confidence in predicting the probability. The result points to more future study on other proper metric than CE loss and accuracy for evaluating choice model learning and effective methods for recalibrating choice models. We defer more visualizations of to Appendix C.
The existing literature of choice modeling on the feature-free setting and that on the feature-based setting have been largely separate with each other. In this paper, we propose a unified deep learning-based framework that applies to both settings through a binary representation of the assortment and feature encoders. We believe there is still large room for performance improvement by further tuning the neural network architectures. We summarize our findings into the following three points. First, the deep learning-based choice models are capable of recovering existing choice models with an effective learning procedure. They become particularly effective when the underlying model/training data is too complex to be described by a simple model such as MNL and when there is a sufficient amount of training data (such as 5,000 samples for 20-50 products). Second, the modeling of assortment effect has always been a key component of choice models, which can be verified by both empirical evidence such as Table (ref) and all the numerical experiments in this paper. Third, whether to include features in choice models is determined by the downstream application rather than feature availability, and feature-free choice models should be used when one is interested in understanding population-level choice behaviour.
We conclude with the following two future directions.
Multiple-purchase choice model. The existing choice models focus exclusively on modeling the single-choice behavior where only one product is chosen from the offered assortment. The multiple-purchase choice model is usually studied under an inverse optimization framework in the literature of revealed preference zadimoghaddam2012efficiently,amin2015online,birge2022learning. The deep learning-based choice models provide a natural framework to study the multiple-choice behavior, and they can fit to such training data by twisting the loss function.
Pricing and assortment optimization. In a retailing context, the product price is another important factor that affects customer choice. Our current models did not account for this factor. One option is to include the price vector as another input to the neural network models. We believe it deserves more future works to study the associated price and assortment optimization problems.
The authors thank Antoine Desir for helpful discussions and pointing to the two datasets for numerical experiments.