The Use of Binary Choice Forests to Model and Estimate Discrete Choices

The Use of Binary Choice Forests to Model and Estimate Discrete Choices

\RUNAUTHOR{Chen et al.}

\RUNTITLE{The Use of BCF to Model and Estimate Discrete Choices}

\TITLE{The Use of Binary Choice Forests to Model and Estimate Discrete Choices}

\ARTICLEAUTHORS{ \AUTHOR {Ningyuan Chen} \AFF{Rotman School of Management, University of Toronto, Toronto, Ontario M5S 1A1, Canada, \EMAIL{[email removed]}}

\AUTHOR {Guillermo Gallego} \AFF{School of Data Science, The Chinese University of Hong Kong, Shenzhen, China, 518172, \EMAIL{[email removed], }}

\AUTHOR {Zhuodong Tang} \AFF{Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai, China, 200030, \EMAIL{[email removed]}} }

\ABSTRACT{ Problem definition. In retailing, discrete choice models (DCMs) are commonly used to capture the choice behavior of customers when offered an assortment of products. When estimating DCMs using transaction data, flexible models (such as machine learning models or nonparametric models) are typically not interpretable and hard to estimate, while tractable models (such as the multinomial logit model) tend to misspecify the complex behavior represeted in the data. Methodology/results. In this study, we use a forest of binary decision trees to represent DCMs. This approach is based on random forests, a popular machine learning algorithm. The resulting model is interpretable: the decision trees can explain the decision-making process of customers during the purchase. We show that our approach can predict the choice probability of any DCM consistently and thus never suffers from misspecification. Moreover, our algorithm predicts assortments unseen in the training data. The mechanism and errors can be theoretically analyzed. We also prove that the random forest can recover preference rankings of customers thanks to the splitting criterion such as the Gini index and information gain ratio. Managerial implications. The framework has unique practical advantages. It can capture customers' behavioral patterns such as irrationality or sequential searches when purchasing a product. It handles nonstandard formats of training data that result from aggregation. It can measure product importance based on how frequently a random customer would make decisions depending on the presence of the product. It can also incorporate price information and customer features. Our numerical experiments using synthetic and real data show that using random forests to estimate customer choices can outperform existing methods. }

\KEYWORDS{machine learning, online retailing, discrete choice model, data-driven, random forest}

Introduction

In retailing, firms collect data on the choice behavior of past customers when they are offered an assortment of products. The data can be used to predict the choice behavior of future customers, which in turn can help firms to develop effective assortment strategies to improve profits or market shares. Discrete choice models (DCMs) play a central role in describing and estimating the choice behavior from the data.

To understand and predict consumers' choice behavior, academics and practitioners have proposed several frameworks, some of which are widely adopted in the industry. One ubiquitous framework is to first propose a DCM that potentially captures the underlying choice behavior of customers. The DCM has a number of parameters that can be estimated with historical data. Once the model has been appropriately estimated, it can be used as a workhorse to predict the choice behavior of future consumers. The well-known multinomial logit (MNL) model McFa73 and its maximum likelihood estimation is a classic example of this framework.

In this framework, there is a trade-off between flexibility and accuracy. A flexible DCM has a large number of parameters and incorporates a wide range of consumers' behavior, but it may be difficult to estimate and may overfit the training data. On the other hand, a parsimonious model may fail to capture complex choice patterns in the data. Such misspecification may lead to poor performance in prediction. The key to a successful model is to reach a delicate balance between flexibility and predictability. Not surprisingly, it is not straightforward to find the “sweet spot” when selecting the DCM. For this reason, firms usually estimate and test various models using cross-validation to find the best DCM, which is often repeated as more data is collected.

Another framework favored by data scientists is to apply advanced machine learning algorithms to the historical data and predict future choice behavior. This framework skips “modeling” entirely and does not attempt to understand the rationality (or irrationality) hidden behind the patterns observed in the training data. With engineering tweaks, the algorithms can be implemented efficiently and capture various choice behavior. This approach may sound appealing: if an algorithm achieves impressive accuracy when predicting the choice behavior of consumers, why do we care about the actual rationale in consumers' minds when they make choices? There are two counterarguments. First, the firm may be interested in not only making accurate predictions but also in other goals such as finding an optimal assortment that maximizes the expected revenue, which may not have appeared in the data. Without a proper model, it is unclear if revenue maximization can be formulated as an optimization problem. Second, when the market environment is subject to secular changes, having a reasonable model often provides a certain degree of generalizability, while black-box algorithms may fail to capture an obvious pattern just because the pattern has not appeared frequently in the past.

In this paper, we introduce a data-driven framework combining machine learning with interpretable behavioral models, retaining the strengths of both frameworks mentioned previously. We propose to use random forests, a popular machine learning algorithm breiman2001random that is fully nonparametric, to fit the data and predict future customer behavior. Hence, it differs from the first framework because it does not postulate a parametric DCM upfront. It also differs from the second framework by providing an interpretable model to describe customers' decision-making process. Random forests are easy to implement using R or Python scikit-learn,rrandomforest and have been shown to have extraordinary predictive power in other applications. The resulting predictive model, which we refer to as binary choice forests, is a mixture of decision trees, each of which reflects the decision-making process of a potential customer. We provide theoretical analyses for the framework. First, as the sample size increases, random forests can successfully recover any DCM underlying the data. Although the proof technique is standard, this is the first estimator for DCMs to be shown to have such a property. Second, we show that random forests serve as adaptive nearest neighbors and effectively use historical data to extrapolate the choice of future customers. Viewing random forests as adaptive nearest neighbors has been proposed in the statistics literature, and we have adapted the analysis of sampling error (Section (ref)) to our setting. However, due to the special structure of DCMs (the domain of predictors is not continuous), the analysis of the distance to the nearest neighbors is combinatorial in nature (Section (ref)) and has not appeared in the random forest literature. Third, we show the splitting criterion used by the random forest is intrinsically connected to the preference ranking of customers. That is, when each customer is endowed with a preference ranking of the products and always chooses the most preferred product in the offered assortment, the random forest can recover the ranking from the data by representing it as a decision tree. To the best of our knowledge, the third set of results is new to both streams of literature on DCMs and random forests.

Besides the theoretical properties, we explore the practical advantages of the framework thanks to random forests: (1) It can capture patterns of behavior that elude other models, such as irregularity and sequential searches weitzman1979optimal, whose details can be found in Section (ref). (2) It can return an importance index for all products based on how frequently a random customer would make decisions depending on the presence of the product. The details can be found in Section (ref). (3) It can incorporate prices and reflect the information in consumers' decision-making. The details can be found in Section (ref). (4) It can naturally incorporate customer features and is compatible with personalized online retailing. The details can be found in Section (ref). (5) It can deal with nonstandard historical data formats, which is a major challenge in practice. The details can be found in Appendix (ref). Therefore, we propose random forests as an effective approach to learning consumer choice behavior when the data is abundant and parametric models cannot capture the complex and potentially irrational patterns in the data.

Literature Review

We first review DCMs proposed in the literature, in the increasing order of flexibility and the difficulty of estimation. The independent demand model and the MNL model McFa73 have very few parameters (one per product), which are easy to estimate train2009discrete. Although the MNL model is still widely used, its inherent property of independence of irrelevant alternatives (IIA) has been criticized for being unrealistic (see anderson1992discrete). The nested logit model, the Markov chain DCM, the mixed logit model and the rank-based DCM (see, e.g., williams1977formation,train2009discrete,farias2013nonparametric,blanchet2016markov) are able to capture more complex choice behavior than the MNL model. The mixed logit model can approximate any random utility model (RUM), encompassing an important class of DCMs. Although there has been exciting progress in recent years farias2013nonparametric,van2014market,van2017expectation,csimcsek2018expectation,jagabathula2018conditional, the computational feasibility and susceptibility to overfitting remain a challenge in practice. In addition, the class of RUM belongs to the class of regular DCMs: the probability of choosing an alternative cannot increase if the offered set is enlarged. Experimental studies show strong evidence that regularity may be violated in practice simonson1992choice. Several models are proposed to capture more general behavior than RUM natarajan2009persistency,flores2017assortment,berbeglia2018generalized,feng2017relation, liu2020assortment, yousefi2020choice, but it is not yet clear if such models can be estimated efficiently.

The binary choice forest in this paper can be seen as a mixture of customer segments, where each segment has the choice behavior represented by a decision tree. In this sense, it is related to recent studies on consumer segmentation such as bernstein2018dynamic,jagabathula2018model,aouad2023market, feng2021robust. This paper focuses on the estimation of DCMs and the segments emerge as a byproduct to improve the predictive accuracy: the trees have equal weights and we do not control for the number of trees (segments). In contrast, bernstein2018dynamic,jagabathula2018model,aouad2023market, feng2021robust design algorithms to cluster customers so the objectives differ. It is worth noticing that aouad2023market also use the tree structure for market segmentation. However, the tree splits on the customer features instead of the products.

The specifications of random forests used in this paper are introduced by breiman2001random, although many of the ideas were discovered earlier. The readers may refer to hastie2009elements for a general introduction. Although random forests have been very successful in practice, little is known about their theoretical properties relatively. Most studies focus on stylized assumptions or simplified versions of the random forest algorithm used in practice. biau2016random provide an excellent survey of the recent theoretical and methodological developments in the field. {\color{black} \Copy{rev:lite}{ There are recent papers on theoretical properties (e.g., consistency and asymptotic normality) under less restrictive assumptions. For example, lin2006random study the effect of terminal node sizes on the mean squared error (MSE) of random forest predictions. scornet2015consistency establish the $L^2$ consistency of random forests in regression problems. wager2014asymptotic, wager2018estimation show that asymptotic normality can be established from the “honest” assumption: a tree is honest if it uses separate samples in a node to determine respectively the split points and the prediction. This assumption is typically violated by random forest algorithms used in practice. Although our paper borrows some ideas from the existing literature, its contributions differ substantially in several key aspects:

A recent paper by chen2019decision proposes a similar tree-based DCM. Our study differs substantially in how to estimate the tree from the data and key results. We use random forests algorithm, while chen2019decision rely on mixed-integer programming to estimate the tree structure. On the theoretical side, chen2019decision mainly characterize the depth of the forest needed to fit a training dataset of assortments. In contrast, we focus on explain why the algorithm works well for unseen assortments, which refer to the assortments having not appeared in the training data, and investigate the impact of the splitting criteria. For the numerical studies, chen2019decision benchmark their model against MNL and rank-based DCMs, and focus mainly on datasets with around 10 products. By constrast, we conduct a more comprehensive and extensive numerical studies. We find that random forests are quite robust and have good performance even compared with the Markov chain model estimated using the expectation-maximization (EM) algorithm, which has been shown to have outstanding empirical performance compared to MNL, the nested logit, the mixed logit and rank-based DCM berbeglia2022comparative, especially when the training data is large. We also compare the performance of random forests to chen2019decision in real and synthetic datasets, and show random forests perform better and more robust. We also evaluate settings with a large number of products (up to 400), and explore aspects such as parameter tuning, assortment variation, and extensions to pricing and customer features. }} It is worth noticing that some recent studies on optimization frameworks (e.g., assortment optimization) under tree ensemble models greatly extend the applicability of the tree-based modeling frameworks mivsic2020optimization, biggs2023constrained, perakis2021umotem.

{\color{black} To help readers clearly distinguish our work from the existing literature, we summarize the key differences from representative literature in Table (ref).}

Data and Estimation

Consider a set $[N]\triangleq\left\{1,\ldots,N\right\}$ of $N$ products and define $[N]_+ \triangleq [N] \cup \{0\}$ where $0$ represents the no-purchase option. We use $\bm x \in \left\{0,1\right\}^N$, a binary vector, to represent an assortment of products, where $\bm x(i) = 1$ indicates the inclusion of product $i$ in the assortment and $\bm x(i) = 0$ otherwise. A {\bf discrete choice model} (DCM) is a non-negative mapping $p(i,\bm x): [N]_+\times \left\{0,1\right\}^N \to [0,1]$ such that

Here $p(i,\bm x) \in [0,1]$ represents the probability that a customer selects product $i$ from assortment $\bm x$. We refer to a subset $S\subseteq [N]$ as an assortment associated with $\bm x \in \{0,1\}^N$, i.e., $i\in S$ if and only if $\bm x(i) = 1$. In the remaining paper, we use $p(i,S)$ and $p(i,\bm x)$ interchangeably.

We assume that arriving consumers make choices independently based on an unknown DCM $p(i, \bm x)$. The firm collects data of the form $(i_t, \bm x_t)$ (or equivalently $(i_t,S_t)$) where $\bm x_t$ is the assortment offered to the $t$th consumer and $i_t \in S_t \cup \{0\}$ is the choice made by consumer $t = 1,\ldots, T$. Our goal is to use the data to estimate the underlying DCM $p(i,\bm x)$. We view the problem as a classification problem. Given the input $\bm x$, we would like to provide a classifier that maps the input to a probability distribution over the class labels $i\in [N]_+$, which is referred to as the class probability.

To this end, we use a random forest as a classifier. The output of a random forest consists of $B$ individual classification and regression trees (CARTs), $\left\{t_b(\bm x)\right\}_{b=1}^B$, where $B$ is a tunable hyper-parameter. Here $t_b\colon \{0,1\}^N\to [N]_+$ is the output of CART $b$. The choice probability of item $i$ in the assortment $\bm x$ is estimated as

which measures the fraction of trees that assign label $i \in [N]_+$ to the input assortment $\bm x$. Note that although a single tree only outputs a deterministic class label for each assortment $\bm x$, the aggregation of the trees, i.e., the forest, is naturally equipped with the class probabilities.

We briefly review the basic mechanism of CART and describe how it is used to fit the data $\{(i_t, \bm x_t)\}_{t=1}^T$. CART recursively splits the input space $[0,1]^N$ (a hypercube), which is a continuous extension to $\left\{0,1\right\}^N$, along its $N$ dimensions. In the first iteration, it selects a product $i\in [N]$ and a split point $s_i\in[0,1]$ to split the input space. More precisely, the split $(i,s_i)$ divides the samples to $ \left\{(i_t,\bm x_t): \bm x_t(i)\le s_i\right\}$ and $\left\{(i_t,\bm x_t): \bm x_t(i)> s_i\right\}$. In our problem, because the predictor $\bm x_t \in \left\{0,1\right\}^N$ is at the corner of the hypercube, all split points between 0 and 1 create the same partition of the observations, and thus we simply set $s_i\equiv 0.5$. To select a product dimension for splitting, an empirical criterion is optimized to favor splits that create “purer” regions (or child nodes in the language of decision trees). Each of the resulting two regions, $R_1$ and $R_2$, should contain observations that mostly belong to the same class. We use a common criterion called Gini index to demonstrate the idea. (Other splitting criteria and their theoretical properties are discussed in Section (ref).) With the Gini index, $(i,s_i)$ is chosen to minimize $\sum_{j=1,2} {t_j}/{T}\sum_{k=0}^N \hat p_{jk}(1-\hat p_{jk})$ where $t_j$ is the number of observations in region $R_j$ and $\hat p_{jk}$ is the empirical frequency of class $k$ in $R_j$. The splitting procedure is then applied recursively to the two regions and their subregions. Finally, the outcome of the tree $t_b(\bm x)$ is typically defined as the majority class label in the leaf node (the smallest region after the splits) $\bm x$ belongs to.

Next, we explain the details of random forests on top of CART. To create $B$ CARTs, for each $b=1,\dots,B$, we randomly choose $z$ samples with replacement from the $T$ observations (bootstrap samples). Only the sub-sample of $z$ observations is used to train the $b$th CART. Splits are performed only on a random subset of $[N]$ of size $m$ to optimize a criterion such as the Gini index. The random sub-sample of training data and random products to split are two key ingredients in creating less correlated CARTs in the random forest. The depth of the tree is controlled by the minimal number of observations, say $l$, in a leaf node for the tree to keep splitting. These steps are formalized in Algorithm (ref). {\SingleSpacedXI

}

The use of random forests as a generic classifier has a few benefits: (1) Many machine learning algorithms such as neural networks have numerous hyper-parameters to tune and the performance crucially depends on the suitable choice of hyper-parameters. Random forests, on the other hand, have only a few hyper-parameters. In the numerical studies in this paper, we simply choose a set of hyper-parameters that are commonly used for classification problems, without cross-validation or tuning, in order to demonstrate the robustness of the algorithm. In particularly, we mostly use $B=1000$, $z=T$, $m=\sqrt{N}$ and $l=50$. The effect of the hyper-parameters is studied in Online Appendix (ref). (Due to page limit, Online Appendix is available in online version or upon request.) (2) The implementation of the generic algorithm is included in packages of R and Python. In Appendix (ref), we demonstrate the algorithm using scikit-learn, a popular machine learning package in Python that implements random forests, to estimate consumer choices. It usually takes less than 20 lines to implement the procedure.

More specifically, because of the application structure, there are a few observations. (1) Because the entries of $\bm x$ are binary $\left\{0,1\right\}$, the split position of decision trees is always $0.5$. Therefore, along a branch of a decision tree, there can be at most one split on a particular product, and the depth of a decision tree is at most $N$. (2) The output random forest is not necessarily a DCM. {\color{black} \Copy{rev:normalization}{In particular, the probability of class $i$, or the choice probability of product $i$ given assortment $\bm x$, may be positive even when $\bm x(i)=0$, i.e., product $i$ is not included in the assortment. To fix the issue, we adjust the probability of class $i$ by conditioning on the trees that output reasonable class labels: $\sum_{b=1}^B\frac{1}{\sum_{j:\bm x(j)=1} \sum_{b=1}^B \ensuremath{\mathbb{I}_{\left\{t_b(\bm x)=j\right\}}}}\ensuremath{\mathbb{I}_{\left\{t_b(\bm x)=i, \bm x(i)=1\right\}}}.$}} (3) We slightly modify the generic algorithm. In particular, when returning the class label of a leaf node in a decision tree, we use a randomly chosen observation instead of taking a majority vote (Step (ref) in Algorithm (ref)). While not a typical choice, it is crucial in deriving our consistency result (Theorem (ref)). In practice, such adjustments are minimal and hardly change the predictive accuracy. In the experiments, we fix $l=50$ for the terminal leaf regardless of the sample size. It implies that the trees in the random forest are deep for large datasets. This is a feature of random forests that average out the high variance and reap the benefit of low bias of individual deep trees.

Interpretability

Next, we connect the random forest fitted from Algorithm (ref) to the context of customer choices. Consider a simple scenario of $N=2$ products. Suppose one CART resulting from Step (ref) of Algorithm (ref) is illustrated in the left panel of Figure (ref). It can be equivalently represented by a decision tree in the right panel of Figure (ref). The decision tree can be interpreted as follows: a customer first checks the presence of product one ($\bm x(1)\ge 0.5$). If it is present, then product one is purchased ($c_2=1$). Otherwise, she proceeds to check product two, and purchases it if it is present ($c_3=2$). We refer to the decision tree and the associated behavior as a {\bf binary choice tree}.

As Algorithm (ref) aggregates the outputs of $B$ binary choice trees in (ref), the class probability can be interpreted as randomly following the choice of one of $B$ customers, each of which makes a decision based on a binary choice tree $t_b(\bm x)$. We refer to such a mixture of binary choice trees as a {\bf binary choice forest} (BCF). Therefore, Algorithm (ref) not only allows us to predict the choice behavior from the data, but also provides a modeling tool to capture the behavior. See Section (ref) for more details.

Why Do Random Forests Work Well?

Many machine learning algorithms, including random forests, have strong performances in practice. However, with a few exceptions, there is little theoretical understanding of the impressive performance. For example, consistency and asymptotic normality, the two most fundamental properties a statistician would demand, are only recently established for random forests under restrictive assumptions wager2014asymptotic,scornet2015consistency,wager2018estimation. The lack of theoretical understanding may worry practitioners when stakes are high and the failure may have harmful consequences. In this section, we attempt to answer the “why” question. The section consists of three major results: (1) random forests are consistent for any DCM, (2) random forests can be viewed as nearest neighbors, whose performance is explained by a few crucial factors, and (3) the choice of the splitting criterion can help random forests recover a class of widely used DCMs called rank-based models. Note that all three theoretical explanations depend specifically on the structure of the discrete choice and do not hold for general classification or regression problems. Therefore, our findings reveal the benefits of applying random forests to DCMs specifically.

Random Forests are Consistent for Any DCM

We now show that given enough data, random forests can recover the choice probability of any DCM. To obtain our theoretical results, we impose mild assumptions on how the data is generated.

Notice that the assumption only requires consumers to make choices independently. We do not assume that the offered assortments $\bm x_t$s are IID, and allow the sequence of assortments offered $\bm x_t$ to be arbitrary as the assortments are chosen by the firm and are typically not randomly generated. Such a design reflects how firms select assortments to maximize expected revenues or to explore customer preferences.

For a given assortment $\bm x$, let $k_T(\bm x) \triangleq \sum_{t=1}^T \ensuremath{\mathbb{I}_{\left\{\bm x_t=\bm x\right\}}}$ be the number of consumers who have seen assortment $\bm x$. We are now ready to establish the consistency of random forests.

All technical proofs are provided in Appendix (ref). {\color{black} \Copy{rev:thm1_compare}{ chen2019decision show that decision forests can represent any general choice model, and our Theorem (ref) demonstrates that the forest generated by the random forest algorithm can accurately predict any choice model as $T \rightarrow \infty$. The consistency of {\em individual} decision trees has been shown under certain conditions, typically including the diminishing diameter and the increasing number of data points in terminal nodes. See Theorem 13.1 in gyorfi2006distribution or Chapters 20 and 21 of devroye2013probabilistic. While these conditions hold in our setting, because of the clustering of data points at the corners, we have to handle the additional resampling issue in Step (ref) in Algorithm (ref). The proof is based on standard concentration inequalities.}}

According to Theorem (ref), the random forest can accurately predict the choice probability of any DCM, given that the firm has offered the assortment many times. Practically, the result can guide us about the choice of parameters. In fact, we just need to generate many trees in the forest ($B_T\to\infty$), resample many observations in a decision tree ($z_T\to\infty$), and keep the terminal leaf small ($l_T$ is fixed). The requirement is easily met by choice of parameters in the remarks following Algorithm (ref), i.e., $z=T$, $m=\sqrt{N}$ and $l=50$. Theorem (ref) guarantees good performance of the random forest when the seller has collected a large dataset. This is a typical case in online retailing, especially in the era of “big data.” Random forests thus provide a novel data-driven approach to model customer choices. In particular, the model is first trained from data, then used to interpret the inherent thought process of consumers when they make purchases. By Theorem (ref), when the historical data has a large sample size, the model can accurately predict how consumers make decisions in reality.

Random Forests and Nearest Neighbors

In Section (ref), we state that when an assortment is offered frequently, the choice probabilities estimated by random forests of this assortment are consistent. However, this doesn't explain the strong performance of random forests on assortments that have not been offered frequently in the training data (so-called unseen assortments). In this section, following the intuition provided in lin2006random, we attempt to provide a unique perspective based on nearest neighbors. To motivate, consider the following examples.

The examples reveal the intrinsic connection between random forests and nearest neighbors. Namely, if an assortment is not offered in the training data, then random forests would look for its neighboring assortments in the training data, by grouping them in the same leaf node, to predict the choice probabilities of the unseen assortment. Unlike nearest neighbors, random forests don't always find the nearest one, as the chosen neighbor is determined by layers of mechanisms such as splitting and randomization. Arguably, this difference leads to the improved performance of random forests, as well as its intractability.

{\color{black} Based on this perspective, three crucial factors determine the performance of random forests when predicting unseen assortments:

Next, we analyze the impact of the three factors on the performance of random forests.

Distance to Neighbors in the Training Data

For two assortments (subsets) $S_1$ and $S_2$, the symmetric difference is defined as $ S_1 \ominus S_2 \triangleq S_1 \cup S_2 - S_1 \cap S_2 = (S_1 - S_2) \cup (S_2-S_1)$. We define the distance between $S_1$ and $S_2$, $d(S_1,S_2)$, by the cardinality of the symmetric difference:

The distance defined in equation (ref) is the number of different products mentioned in Examples (ref) and (ref).

We first attempt to study what assortments in the training data can potentially be a neighbor to the unseen assortment, i.e., they fall into the same leaf node in some trees in the forest. Let $\mathcal{T} \subseteq 2^{[N]}$ denote the set of assortments observed in training data. For an unseen assortment $S$ and an assortment $S_1\in \mathcal T$, we define the concept of Potential Nearest Neighbor (PNN). {\color{black} Let $\ell$ denote the maximum number of distinct assortments in a leaf node ($\ell \ge 1$). Note that $\ell$ differs from the leaf node size $l$, since multiple observations may correspond to the same assortment. Roughly speaking, $l = \ell \times \#$ observations in each assortment.}

In other words, $S_1$ is an $\ell$-PNN of $S$ if at most $\ell-1$ assortments observed in the training data dominate $S_1$ in terms of the similarity to $S$ at the product level.

Based on Proposition (ref), the distance of an unseen assortment $S$ to the training data is essentially the distance to its $\ell$-PNNs. We next provide an estimate of this distance when a fraction of assortments are observed in the training data. In particular, we show that for all $\ell$-PNNs of an unseen assortment to be close, the training set only needs to have $\Big\lceil2^{N+2} \cdot c_0 \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$ assortments for constant $c_0 \ge 1$.

In other words, if a fraction $O(\log(N)^2/N)$ of assortments appear in the training set and $\ell = O(\log N)$, then the distance of $S$ to its $\ell$-PNNs is guaranteed (in a probabilistic sense) to be of order $O(\log N)$. However, this is a strong condition. In practice, even if there are a few trees that predict $S$ by a PNN that is “far” from the unseen assortment (including a very different set of products), random forests are able to mitigate the bias by averaging them with other closer trees. This is one of the reasons why random forests perform much better than CARTs in general.

To explore such an effect, we explore the expected distance of a PNN. To simplify the analysis, we consider a stylized splitting rule called random splitting, that is, $m=1$ in Algorithm (ref). Random splitting is commonly used to shed theoretical insights about the performance of random forests biau2016random. It also satisfies the “honest tree” assumption in wager2014asymptotic, wager2018estimation. We can derive the following result.

Although the order of magnitude seems to be similar to Proposition (ref), i.e., with $\tilde{O}(2^N/N)$ assortments\footnote{The notation $\tilde O$ represents the asymptotic order neglecting the logarithmic factors.} and $\ell = O(\log_2(N))$, the distance is bounded by $\tilde{O}(\log_2(N))$, the constants and logarithmic factors may play a role in explaining why random forests (the average distance) perform better than individual trees. We have also conducted numerical studies showing the bound in Proposition (ref) is more or less tight: If $M$ grows at a slower rate, for example, polynomially in $N$ or $M=O(N^{\log N})$, then the average distance cannot be bounded by $O(\log_2(N))$. See Online Appendix (ref).

If the $M$ assortments in the training data are selected by the firm to minimize the distance to all unseen assortments, then how do the results change? This is similar to the setting of the experimental design. For this question, we refer to the literature on the so-called Covering Code problem, see cohen1997covering, ostergaard1998new. The Covering Code problem aims to find the minimum number of binary vectors in $\{0,1\}^N$, such that every other element in the set is within distance $r$ to some selected ones. To our knowledge, the covering code problem is still an open problem, and numerous bounds are established. In general, when $M = O(2^N / N)$, these binary vectors can cover all the binary vectors within distance 1. This improves the distance in Proposition (ref) from $\log_2(N)$ to $1$. This literature may provide some useful heuristics and algorithms on how to design assortments in a new market in order to explore customers' choices efficiently.

We summarize the main results in this section below. When $M =\Big\lceil2^{N+2} \cdot c_0 \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$ and $\ell \le c_0 \log_2 (N)$, where $c_0 \ge 1$, it is guaranteed that the distance of all PNNs for an unseen assortment to be less than $\lceil \log_2 N \rceil-1$ with high probability. Under random splitting instead of the Gini index, then for $M = \lceil2^N/N\rceil$, the average distance is bounded by $\log_2 \ell +\log_2 N + 2.56$. When the firm can design assortments to minimize the distance, $M = O(2^N / N)$ assortments are sufficient to guarantee that every other assortment has a PNN of distance 1. }

Continuity of DCMs

Having established bounds on the distance to PNNs of an unseen assortment, we next explore the continuity of DCMs. The continuity is a crucial property for DCMs: the estimated choice probabilities for an assortment appearing frequently in the training data can be used to extrapolate an unseen assortment, only if choice probabilities do not vary significantly when the assortment changes slightly. However, the notion of continuity is specific to DCMs and deviates from the literature on random forests. First, the $\bm x$-space of our problem is not continuous and consists of extreme points of a hypercube. Second, the “$y$” variable is a vector of choice probabilities.

To formalize the notion, define the following quantity between the choice probabilities of two assortments $S_1, S_2$ under a given DCM $p(i,S)$:

The quantity is similar to $(f(x)-f(y))/(x-y)$ for continuous functions: how close are their choice probabilities relative to the distance of $S_1$ and $S_2$? If $\Phi(S_1, S_2)$ can be bounded, then the DCM is more or less “Lipschitz continuous” and the proximity of the unseen assortments to PNNs (results in Section (ref)) leads to a good performance of random forests.

By the triangular inequality, it is sufficient to show a DCM is $c$-continuous if (ref) holds for all $S_1, S_2$ such that $d(S_1, S_2) = 1$. If a DCM is $c$-continuous, then roughly speaking, the difference in the choice probabilities of two neighboring assortments with distance one is $c/N$. Combining the results with Section (ref), if the distance between two assortments is $O(\log N)$ (e.g., Proposition (ref)), then the error in the extrapolation of the choice probabilities is $O(\log N/N)$. We next consider the continuity of popular DCMs.

The MNL model. Suppose $p(i,S)= v_i/(v_0+\sum_{j\in S}v_j)$ where $\{v_l\}_{l \in [N]_+}$ represents the attraction of the products. Then for $\emptyset \subsetneq S \subsetneq [N]$ and $j \notin S$ we have that

If the size of $S$ is $\epsilon N$, then it is easy to verify that $\Phi(S, S \cup \{j\})\le 2v_{\max}/(v_0+v_{\max}+\epsilon v_{min}N)$.

Rank-based DCMs. Suppose $\pi$ is a permutation of $[N]$ and $\pi(i)$ denotes the rank of product $i$ in $\pi$. Define $\pi^*(S)\triangleq \argmin_{i \in S_+} \pi(i)$ to be the top choice in $\pi$ when $S$ is offered. The rank-based model is represented by $w_{\pi}$, the weight of customers whose preference is consistent with $\pi$ in the population. One can show that

If the fraction of customers who rank $j$ as the top choice in $S\cup \left\{j\right\}$ is small, then the DCM is more continuous according to Definition (ref).

Sampling Error

Another source of error stems from the empirical distribution used to estimate the choice probabilities of the assortments in the training data. In the terminal leaf node, suppose a tree uses the choice probabilities of $S'$ to predict those of the unseen $S$. Moreover, let $k$ denote the number of observations for $S'$ in the training data. For each $i \in S \cap S'$, the frequency of customers choosing $i$ from the assortment $S'$ can be approximated by a normal distribution with mean $p(i,S')$ as the sample size increases. The standard deviation is bounded by $\sqrt{p(i,S')(1-p(i,S'))/k} \leq 1/(2\sqrt{k})$. Fortunately, the sampling error is more or less independent of the other two sources of errors articulated in Section (ref) and (ref) and can be controlled using the standard concentration inequalities. In particular, when an assortment has $O(|S|^2 \cdot N^2 / (\log N)^2)$ samples, the error in using the frequencies to approximate the choice probabilities is at most $O(\log N / (N \cdot |S|))$.

{\color{black}

Combining the Errors

In this section, we provide a unified bound combining the three sources mentioned above. It provides a finite sample result for the performance of random forests predicting unseen assortment. The error of prediction in the following theorem is defined as $\sum_{i \in [N]_+} \big|p(i, S) - \hat{p}(i, S)\big|$, where $S$ is the unseen assortment and $\hat{p}(i, S)$ is the estimated probability by random forests.

Roughly speaking, when the maximum number of distinct assortments in a leaf node is $O(\log N)$, the number of assortments in the training data is $\tilde O(2^N/N)$ and the transactions of each assortment is $O(N^2)$, the estimation error of random forests is $\tilde O(1/N)$. In Theorem (ref), we assume that only one assortment from the training data is used to predict an unseen assortment. However, if there are $\ell' \le \ell$ distinct assortments in the same leaf node, the error bound still holds, and the number of transactions required for each assortment $S'$ is reduced to $1/ \ell'$ of that required in Theorem (ref). Note that the result only provides an upper bound for the error and we have seen much better performance of random forests in practice.

\Copy{rev:thm2_compare}{ chen2019decision use mixed-integer programming to show that decision forests can represent historical assortments, whereas Theorem (ref) analytically establishes an error bound for unseen assortments. Theorem (ref) differs from existing random forests literature in several key aspects: (1) prior work studies regression for continuous $\bm{x} \in [0,1]^d$, whereas we address classification for discrete $\bm{x} \in \{0,1\}^N$; (2) instead of assuming continuity, positive density, and honest trees, we introduce $c$-continuity tailored to DCMs; (3) we bound prediction error for unseen assortments in classification, $\sum_{i \in [N]_+} |p(i, S) - \hat{p}(i, S)|$, while prior work focuses on MSE for regression; (4) methodologically, we exploit the combinatorial structure of DCMs and apply concentration inequalities to handle the discrete setting. } }

Splitting Criteria and the Recovery of Rank-based DCMs

In this section, we discuss a few commonly used splitting criteria for Step (ref) in Algorithm (ref) and their implications in a theoretical framework. Suppose a parent node with dataset $\mathcal{D}$ splits into $K$ child nodes $\{\mathcal{D}_k\}_{k=1}^K$ along dimension $i$, corresponding to $K$ regions $\{R_k\}_{k=1}^K$, i.e., $\mathcal{D}_k = \{(i_t, \bm x_t): \bm x_t \in R_k\}$. In Algorithm (ref), we choose $K=2$ and $i$ is the product on which the split is performed, thus grouping observations based on whether product $i$ is included in the assortment. With a slight abuse of notation, let $T$ denote the number of samples in the parent node, denoted as $\mathcal{D}$, and $t_k$ the number of observations in the child node $R_k$. Let $\hat{p}_{jk}$ denote the empirical purchase frequency of product $j$ in $R_k$, i.e., $\hat{p}_{jk} = \sum_{\bm x_t \in R_k} \ensuremath{\mathbb{I}_{\left\{i_t=j\right\}}}/t_k$. Similarly, we use $\hat p_{j0}$ to denote the empirical purchase frequency in the parent node.

The Gini index is one of the most widely used criteria, defined as

Replacing the purity measure in the Gini index $\hat{p}_{jk} (1-\hat{p}_{jk})$ by entropy-related measures, $H(\mathcal{D}_k) \triangleq -\sum_{j=0}^N \hat{p}_{jk} \ln(\hat{p}_{jk})$, we can obtain another common splitting criterion, the information gain, measuring the reduction of entropy by the split:

A similar criterion normalizes the information gain by the number of samples in the child nodes.

The above criteria use slightly different notions of the purity of a region. More details about the splitting criteria can be found in zhou2021machine.

To explore the impact of the splitting criteria, we consider a specific DCM that generates the data. In particular, we assume that the underlying DCM is a rank-based model characterized by a single preference ranking: the consumers always prefer product $i$ to $i+1$, for $i=1,\dots,N-1$, and product $N$ to the no-purchase option. The following result demonstrates that the ranking can be recovered from the random forest using the Gini index with high probability.

{\color{black}

} Since the error probability converges to zero exponentially in $T$, the predictive accuracy improves tremendously with data size. The proof of the theorem reveals an intrinsic connection between the Gini index and the recovery of the preference ranking. We analyze the deterministic output of the theoretical random forest when the data size is infinite. It allows us to show that the theoretical Gini index leads to a sequence of splits consistent with the ranking, i.e., the ranking is recovered under the theoretical random forest. For example, if the first split is on product $i$, then the resulting theoretical Gini index is $(2-2^{2-2i})/3$. In other words, the first split would occur on product one under the theoretical random forest. Then we analyze the difference between empirical and theoretical Gini indices and bound the probability of incorrect splits using concentration inequalities. The recursive splits are analyzed using the union bound.

The proof provides the following insight into why random forests may work well in practice: The Gini index criterion tends to find the products that are ranked high in the rankings because they create “purer” splits that lower the Gini index. As a result, the topological structure of the decision trees trained in the random forest is likely to resemble that of the binary choice trees underlying the DCM generating the data. Moreover, we also complement the results in Theorem (ref) by additional numerical studies in Online Appendix (ref). We numerically show the result still holds when the training data is not uniform. We also provide the insights for random forests when the rank-based DCM consists of more than one rankings.

One restrictive assumption in Theorem (ref), reflecting the weakness of the Gini index, is the uniform sampling of the assortments. In practice, it is likely that the most popular products could be offered more or less often than other products. In this case, even though it is the most preferred product, the random forest under the Gini index may fail to recognize it as the first split. Next, we show that using the information gain ratio in Definition (ref) as the splitting criterion, Algorithm (ref) can recover the preference ranking with a much milder assumption.

Theorem (ref) highlights the benign theoretical property of splitting using the information gain ratio. The conditions in Theorem (ref) are rather mild: we only require at least one sample satisfying each of the conditions. As a result, the minimum sample requirement for the training data is $2N-1$. That is, the data includes the offering of individual products $\{i\}_{i=1}^N$ and consecutive pairs $\{(i, i+1)\}_{i=1}^{N-1}$. The following numerical example shows that the information gain ratio can recover the DCM, while other criteria cannot. The numerical example provides insights into the benefit of using the information gain ratio as a splitting criterion.

Since the actual ranking is unknown, the condition in Theorem (ref) that requires the pairs of $i$th and $(i+1)$th preferred products to be offered in an assortment may not be verifiable. A sufficient condition for Theorem (ref) is that all pairs of products are offered in an assortment, as well as individual products. This corresponds to at least ${N(N+1)}/{2}$ assortments in the training data to recover the preference ranking. On the other hand, this is almost necessary.

{\color{black} \Copy{rev:sec3.3}{ In summary, Theorems (ref) and (ref) in this section highlight the interpretability of the random forest algorithm and the theoretical performance of different splitting criteria for classification problems. They show that random forests can capture the underlying decision-making process of a single preference ranking customer, a feature not studied in the random forests literature. Unlike most literature studies on regression that use MSE as the splitting criterion, we examine the Gini index and information gain ratio for classification problems. Theorem (ref) demonstrates that the information gain ratio, rarely studied before, can recover the single preference ranking model with only $2N - 1$ samples.}}

Flexibility and Practical Benefits of Random Forests

In this section, we demonstrate the flexibility of random forests and how the method can be adapted in practice to handle different situations.

Behavioral Issues

Theorem (ref) shows random forests can estimate any DCMs. For example, there is empirical evidence showing that behavioral considerations of consumers may distort their choice, e.g., the decoy effect ariely2008predictably, comparison-based choices huber1982adding,russo1983strategies, search cost weitzman1979optimal and context effects yousefi2020choice. It implies that regular (see Section (ref)) DCMs cannot predict the choice behavior well. It is already documented in chen2019decision that the decision forest can capture the decoy effect. In this section, we use choice forests to model consumer search.

weitzman1979optimal proposes a sequential search model with search costs. Before the search process, consumers only know the distribution of $V_j$, the net utility of product $j \in [N]$, and the cost $c_j$ to learn the realization of $V_j$. Let $z_j$ be the root of the equation $E[(V_j - z_j)^+] = c_j$ and suppose that products are sorted in the descending order of the $z_j$s. weitzman1979optimal shows that it is optimal not to purchase if the realized value of the no-purchase alternative, $ V_0$, exceeds $z_1$. Otherwise, the consumer searches product one at a cost $c_1$ and $W_1 = \max(V_1, V_0)$ is computed. The search process stops when $W_i$ exceeds $z_{i+1}$ for the first time, with the consumer selecting the best product among those that were searched.

We next show that binary choice trees can represent this search process. Consider three products ($N=3$). Suppose the products are sorted so that $z_1>z_2>z_3>0$, so the consumer searches in the order of product one $\to$ product two $\to$ product three. Suppose an arriving customer has realized utilities satisfying $v_2> z_3 > v_1>v_3$. Then the decision process is illustrated by the tree in Figure (ref). For example, suppose products $\{1,3\}$ are offered. The customer first searches product 1 because the reservation price of product one $z_1$ is the highest. However, the realized valuation of product 1 is not satisfactory ($v_1<z_3 < z_1$). Hence, the customer keeps searching for the product with the second-highest reservation price in the assortment, product 3. However, the search process results in an even lower valuation of product 3, i.e., $v_3<v_1$. As a result, the customer stops and chooses product one. Clearly, a customer with different realized valuations would conduct a different search process, corresponding to another decision tree.

{\color{black}

Product Importance

\Copy{rev:MDI}{Random forests can be used to assign scores to each product and rank the importance of products. A common score, mean decrease impurity (MDI), is based on the total decrease in node impurity from splitting on the product, averaged over all trees biau2016random. The score for product $m$ is defined as

In other words, if consumers make decisions frequently based on the presence of product $m$ (a lot of splits occur on product $m$), or their decisions are more consistent after observing the presence of product $m$ (the Gini index is reduced significantly after splitting on $m$), then the product gains more score in MDI and is regarded as important. To illustrate this measure, we provide examples in Online Appendix (ref).

The identification of important products provides simple yet powerful insights into the behavioral patterns of consumers. Consider the following use cases: (1) An retailer wants to promote its “flagship” products that significantly increase the conversion rate. By computing the MDI from the historical data, important products can be identified without extensive A/B testing. (2) Due to limited capacity, a firm plans to reduce the available types of products to cut costs. According to the historical data, it could simply remove the products with low sales. However, some products, while not looking attractive themselves, serve as decoys or references and boost the demand for other products. Removing these products would distort consumers' choice behavior and may lead to unfavorable consequences. The importance score provides an ideal solution: if a product is ranked low based on MDI, then it does not strongly influence the decision-making of consumers. Therefore, it is safe to leave them out. (3) When designing a new product, a firm attempts to decode the impact of various product features on customer choices. Which product feature is drawing the most attention? What do attractive products have in common? To conduct successful product engineering, first, it needs to use historical data to nail down a set of attractive products. Moreover, a numerical score of product importance is necessary to quantify and separate the contribution of various features. The importance score is a more reasonable criterion than sales volume because the latter cannot capture the synergy between the products. }}

{\color{black}

Incorporating Price Information

\Copy{rev:pricing}{One benefit of a parametric DCM, such as the MNL or nested logit model, is the ability to account for covariates. For example, in the MNL model, the firm can estimate the price sensitivity of each product, and extrapolate/predict the choice probability when the product is charged at a new price that has never been observed in the historical data. Many nonparametric DCMs cannot easily be extended to new prices. In this section, we show that while enjoying the benefit of a nonparametric formulation, random forests can also accommodate the price information.

Consider the data of the following format: $\left\{(i_t,\bm p_t)\right\}_{t=1}^T$, where $\bm p_t\in [0,+\infty]^N$ represent the prices of all products. For product $j$ not included in the assortment offered to customer $t$, we set $\bm p_t(j)=+\infty$. This is because when a product is priced at $+\infty$, no customer would be willing to purchase it, and it is equivalent to the scenario that the product is not offered at all. Therefore, compared to the binary vector $\bm x_t$ that only records whether a product is offered, the price vector $\bm p_t$ encodes more information.

However, the predictor $\bm p$ can not be readily used in random forests. The predictor space $[0,+\infty]^{N}$ is unbounded, and the value $+\infty$ added to the extended real number line is not implementable in practice. To apply Algorithm (ref), we introduce link functions that map the input into a compact set.

The link function can be used to transform a price $p\ge 0$ into $(0,1]$. Moreover, because of property (3), we can naturally define $g(+\infty)=0$. Thus, if product $j$ is not included in assortment $\bm x_t$, then $g(\bm p_t(j))=g(+\infty)=0=\bm x_t(j)$. If product $j$ is offered at the low price, then $g(\bm p_t(j))\approx g(0)= 1$. After the transformation of inputs, $\bm p_t\to g(\bm p_t)$\footnote{When $g(\cdot)$ is applied to a vector $\bm p$, it is interpreted as applied to each component of the vector.}, we introduce a continuous scale to the problem in Section (ref). Instead of binary status (included or not), each product now has a spectrum of presence, depending on the price of the product. Now we can directly apply Algorithm (ref) to the training data $\left\{(i_t,g(\bm p_t))\right\}_{t=1}^T$ after modifying Step (ref), because the algorithm needs to find not only the optimal product to split but also the optimal split location. The slightly modified random forests are demonstrated in Algorithm (ref).} {\SingleSpacedXI

}

\Copy{rev:pricing2}{ Because of the nature of the decision trees, the impact of prices on the choice behavior is piecewise constant. For example, Figure (ref) illustrates a possible binary choice tree with $N=3$.}

\Copy{rev:pricing3}{ It is not surprising that there are numerous link functions to choose from. For instance, $g(x) = e^{-x}$ or $g(x) = 1- \frac{2}{\pi}\arctan(x)$. In fact, the survival function of any non-negative random variables with positive PDF is a candidate for the link function. This extra degree of freedom may concern some academics and practitioners: How sensitive is the estimated random forest to the choice of link functions? What criteria may be used to pick a “good” link function? Our next result guarantees that the choice of link functions does not matter. For any two link functions $g_1(x)$ and $g_2(x)$, we can run Algorithm (ref) for training data $\left\{(i_t,g_1(\bm p_t))\right\}_{t=1}^T$ and $\left\{(i_t,g_2(\bm p_t))\right\}_{t=1}^T$. We use $t_b^{(j)}(\bm x)$ to denote the returned $b$th tree of the algorithm for link function $g_j(x)$, $j=1,2$.}

\Copy{rev:pricing4}{ It is worth pointing out that although the random forests using two link functions output identical class labels for $\bm p_t$ in the training data, they may differ when predicting a new price vector $\bm p$. This is because the splitting operation that minimizes the Gini index in Step (ref) is not unique. Any split between two consecutive observations\footnote{If the algorithm splits on product $m$, then $\bm p_{t_1}$ and $\bm p_{t_2}$ are consecutive if there does not exist $\bm p_{t_3}$ in the same leaf node such that $(\bm p_{t_1}(m)-\bm p_{t_3}(m))(\bm p_{t_2}(m)-\bm p_{t_3}(m))<0$.} results in an identical class composition in the new leaves and thus the same Gini index. Usually, the algorithm picks the middle between two consecutive observations to split, which may differ for different link functions. }}

{\color{black}

Incorporating Customer Features

\Copy{rev:feature1}{A growing trend in online retailing and e-commerce is personalization. Due to the increasing access to personal information and computational power, retailers are able to implement personalized policies, including pricing and recommendation, for different customers based on his/her observed features. Leveraging personal information can greatly increase the garnered revenue of the firm.

The first step to offering a personalized assortment is incorporating the feature information into the choice model. It has been considered in many classic DCMs by including a linear term in the features. See train2009discrete for a general treatment. In this section, we demonstrate that it is natural for random forests to capture customer features and return a binary choice forest that is aware of such information. Suppose the collected data of the firm have the form $(i_t, \bm x_t, \bm f_t)$ for customer $t$, where in addition to $(i_t, \bm x_t)$, the choice made and the offered set, the customer feature $\bm f_t\in [0,1]^M$ is also recorded (possibly normalized). The procedure in Section (ref) can be extended naturally. In particular, we may append $\bm f_t$ to $\bm x_t$, so that the predictor $(\bm x,\bm f)\in [0,1]^{M+N}$. Algorithm (ref) can be modified accordingly.

The resulting binary choice forest consists of $B$ binary choice trees. The splits of the binary choice tree now encode not only whether a product is offered, but also predictive feature information of the customer. For example, a possible binary choice tree illustrated in Figure (ref) may result from the algorithm.}

\Copy{rev:feature2}{ Compared with other DCMs with linear features, the framework introduced in this paper has the following benefits: (1) The estimation is straightforward (same as the algorithm without customer features) and can be implemented efficiently. (2) The nonparametric nature of the model allows for capturing complex interaction between products and customer features, and among customer features. For example, “offering a high-end handbag” may become a strong predictor when the combination of features “female” and “age$\ge 30$” are activated. In a binary choice tree, the effect is captured by three splits (one for the product and two for the customer features) along a branch. It is almost impossible to capture in a parametric (linear) model. (3) The framework can be combined with the aforementioned adjustments, such as pricing and product importance. For example, the measure MDI introduced in Section (ref) can be used to identify predictive customer features. }}

Numerical Experiments

{\color{black} We conduct a comprehensive numerical study based on both synthetic and real datasets. We find that (1) random forests are quite robust and the performance is stable for different underlying DCMs varying in complexity. In particular, random forests only underperform the correctly specified parametric models by a small margin and do not overfit; (2) the standard error of random forests is small compared to other estimation procedures; (3) random forests scale well to hundreds of products without requiring excessively large training samples; (4) random forests benefit tremendously from increasing sample size compared to other DCMs; (5) the computation time of random forests almost does not scale with the size of the training data; (6) random forests have a robust performance even if the training set only includes less than $1/30$ of all available assortments; (7) random forests handle training data with nonstandard format reasonably well, such as price information and aggregated data (see Section (ref) and Appendix (ref) and for more details), which cannot be handled easily by other frameworks.}

For the experiments, we compare the estimation results of random forests with the MNL model, the Markov chain model blanchet2016markov, and the decision forest chen2019decision\footnote{The MNL model is estimated using the maximum likelihood estimator. The Markov chain model is estimated using the EM algorithm, the same as the implementation in csimcsek2018expectation. The random forest is estimated using the Python package “scikit-learn”.}. We mainly choose the MNL and the Markov Chain models as benchmarks because the MNL model is one of the most widely used DCM and the Markov chain model has been shown berbeglia2022comparative to have outstanding empirical performance compared to MNL, the nested logit, the mixed logit, and rank-based DCMs. For the decision forest, our implementation is based on the code repository of chen2019decision on GitHub.

When conducting numerical experiments, we set the hyper-parameters of the random forest as follows: $B=1000$, $z=T$, $m=\sqrt{N}$, $l=50$. The investigation of the sensitivity to hyper-parameters is shown in Online Appendix (ref). Choosing the hyper-parameters optimally using cross-validation would further improve the performance of random forests.

Real Data: IRI Academic Dataset

In this section, we compare different models on the IRI Academic Dataset bronnenberg2008database. The IRI Academic Dataset collects weekly transaction data from 47 U.S. markets from 2001 to 2012, covering more than 30 product categories. Each transaction includes the week and the store of purchase, the universal product code (UPC) of the purchased item, the number of units purchased, and the total paid dollars.

The preprocessing follows the same steps as in jagabathula2018limit and chen2019decision. In particular, we regard the products sharing the same vendor code as the same product. Each assortment is defined as a unique combination of stores and weeks. Such an assortment includes all the products available in the store during that week. We conduct the analysis for 31 categories separately using the data for all weeks in 2007. We only focus on the top nine purchased products from all stores in each category throughout the year and treat all other products as the no-purchase alternative.

All sales data after preprocessing has the form $\{(i_t, S_t)\}_{t=1}^T$, where $S_t$ is the offered product set and $i_t \in S_t \cup \{0\}$ is the purchased product in period $t$. Let $\mathcal{S}$ denote the set of unique assortments. The dataset can be aggregated by the same assortment $S$ that $\{n_t, \bm \tilde\ensuremath{\mathsf{P}}_t, S_t\}_{t=1}^{|\mathcal{S}|}$, where $n_t$ is the total sales under assortment $S_t$, and $\bm \tilde\ensuremath{\mathsf{P}}_t$ is the empirical choice probability for each product in $S_t \cup \{0\}$. We only focus on assortments with more than 30 transactions, i.e., $n_t \geq 30$. However, the sales data for most categories are too large for the EM algorithm to estimate the Markov chain model. For computational efficiency, we sample 30 samples with replacement for each unique assortment. This re-sampling procedure does not significantly increase the sampling variability, as most transactions in the original data are repeated entries.

To compare different estimation procedures, we use five-fold cross-validation for each unique assortment to examine the out-of-sample performance. We follow chen2019decision and divide the unique assortments into five (approximately) equal-sized subsets $\mathcal{S}_1, \ldots, \mathcal{S}_5$. For each $i = 1, \ldots, 5$, the testing set is $\mathcal{S}_i$ and the remaining four subsets serve as the training data. Following berbeglia2022comparative, the empirical performance is evaluated by the empirical root mean squared error (RMSE) in the testing set. That is, for estimated choice probabilities $\hat\ensuremath{\mathsf{P}}$ and testing set $\mathcal{S}_i$, we define

The result is shown in Table (ref) comparing random forests, MNL, the Markov chain model and the decision forest (based on column generation). Random forests outperform the others in 20 of 31 categories. According to berbeglia2022comparative, the Markov chain choice model has already shown strong performance in synthetic and real-world studies. Table (ref) fully demonstrates the potential of random forests as a framework to model and estimate consumer behavior in practice. {\color{black} \Copy{rev:IRI}{For robustness, we also test the result when considering the top seven/fifteen products instead of nine. The results are shown in Tables (ref) and (ref) in Online Appendix (ref). Random forests perform the best among the three models in 18 and 27 out of 31 categories, respectively. (Due to the computational issues, we only compare our model with MNL and the Markov chain model in the additional experiments.) In general, random forests show stronger performance when applied to more products.}}

Real Data: Hotel

In this section, we apply the random forest algorithm to a public dataset bodea2009data. The dataset includes transient customers (mostly business travelers) who stayed in one of five continental U.S. hotels between March 12, 2007, and April 15, 2007. The minimum booking horizon for each check-in date is four weeks. Rate and room type availability and reservation information are collected via the hotel and/or customer relationship officers (CROs), the hotel's websites, and offline travel agencies. Since there is no direct competition among these five hotels, we process the data separately. A product is uniquely defined by the room type (e.g., suite). For each transaction, the purchased room type and the assortment offered are recorded.

When processing the dataset, we remove products with less than 10 transactions. We also remove the transactions whose offered assortments are unavailable for technical reasons. For the transactions that none of the products in the available sets are purchased by the customer, we assume customers choose the no-purchase alternative.

We use five-fold cross-validation and RMSE defined in (ref) to examine the out-of-sample performance. That is, for estimated choice probabilities $\hat\ensuremath{\mathsf{P}}$ and testing set $\ensuremath{\mathcal T} \triangleq \{(i_t, S_t)\}_{t=1}^T$, we define

In Table (ref), we show the summary statistics of the five datasets after preprocessing. We also show the out-of-sample RMSE for each hotel (average and standard deviation). In addition, we show the performance of the independent demand model (ID), which does not incorporate the substitution effect and is expected to perform poorly, in order to provide a lower bound for the performance.

The random forest algorithm outperforms the parametric methods for large datasets (Hotel 1, 2 and 3). For smaller data sizes (Hotel 4 and 5), the random forest is on par with the best parametric estimation procedure (Markov chain) according to berbeglia2022comparative.

{\color{black}

Generalizability to Unseen Assortments

\Copy{rev:variation1}{ One of the major challenges in the estimation of the DCM, compared to other statistical estimation problems, is the limited coverage of the training data. In particular, the seller tends to offer a few assortments that they believe are profitable. As a result, in the training data $\{\bm x_t\}_{t=1}^T$ only makes up a small fraction of the total $2^N$ available assortments. Any estimation procedure needs to address the following issue: can the DCM estimated from a few assortments generalize to the assortments that have never been offered in the training data?

While the theoretical foundation has been studied in Section (ref), we show the numerical performance in this section. Consider $N=10$ products. We randomly choose $T_1$ assortments to offer in the training set and thus there are $T/T_1$ transactions for each assortment on average. We use the rank-based DCM to generate the data with $k=4$ and 10 customer types. The rank-based DCM is shown to be equivalent to RUM block1959random. Consumers are divided into $4$ or $10$ different types, each with a random preference permutation of all the products and the no-purchase alternative (see, e.g., farias2013nonparametric). We randomly generate the fractions of customer types as follows: draw uniform random variables $u_i$ between zero and one for $i=1,...,k$, and then set ${u_i}/{\sum_{j=1}^k u_j}$ to be the proportion of type $i$, $i=1,...,k$.

The performance is evaluated by the root mean squared error (RMSE), which is also used in berbeglia2022comparative:

where $\ensuremath{\mathsf{P}}$ denotes the actual choice probability and $\hat\ensuremath{\mathsf{P}}$ denotes the estimated choice probability. Because the actual choice probability is known, we can compute the RMSE theoretically by enumerating all the assortments. For each setting, we generate 100 independent training datasets and compute the average and standard deviation of the RMSE.

The results are shown in Tables (ref) and (ref). Notice that there are $2^N-1=1023$ possible available assortments. Therefore, for example, $T_1=30$ implies that less than $1/30$ of the total assortments have been offered in the training data. In general, the random forest outperforms the MNL model and the decision forest, and is on par with the Markov chain DCM when $T$ is large. Except for the MNL, which does not improve significantly with higher assortment variation (larger $T_1$), all other models benefit from it. For small sample sizes, the Markov chain model performs better. It is likely due to the similarity between the rank-based model and the Markov chain model, e.g., both are regular choice models (definition in Section (ref)). As we shall see, when the underlying model is irregular, the random forest tends to have the best performance (see Table (ref)). Moreover, in the real datasets, when the underlying model is unknown and likely to be irregular, the random forest performs better than the Markov chain model (see Table (ref)).}

\Copy{rev:variation2}{ When the DCM is outside the scope of RUM and the regularity is violated, the Markov chain and MNL model may fail to specify the choice behavior correctly. Next, we generate choice data using the comparison-based DCM huber1982adding, described below. Consumers implicitly score various attributes of the products in the assortment. Then they undergo an internal round-robin tournament of all the products. When comparing two products from the assortment, the customer checks their attributes and counts the number of preferable attributes of both products. Eventually, the customer counts the total number of “wins” in the pairwise comparisons. Here we assume that customers choose with equal probability if there is a tie.

In the experiment, we consider $N = 10$ products. Consumers are divided into $k=2$ different types, whose proportions are randomly generated between 0 and 1. Each type assigns uniform random variables between 0 and 1 to the five attributes of all the products (including the no-purchase option). Again we use the RMSE in (ref) to compare the predictive accuracy. Like in the previous experiment, each setting is simulated 100 times. The result is shown in Table (ref).}

\Copy{rev:variation3}{ Because of the irregularity, both the MNL and the Markov chain DCM are outperformed by the random forest, especially when the data size increases. Notice that as $T\to\infty$, the random forest is able to achieve diminishing RMSE, while the other two models do not improve because of the misspecification error. Like the previous experiment, the random forest achieves stable performances with small standard deviations.

We run our algorithm on a server with 2.50GHz dual-core Inter Xeon CPU E5-2680 and 256GB memory. The running time is shown in Table (ref). In terms of computation time, the random forest is the most efficient, while the EM algorithm used to estimate the Markov chain model takes much longer. When $T = 20000$, the random forest spends 1/160 of the computation time of the Markov chain model. Notice that the running time of random forests only increases slightly for large training sets.}}

{\color{black}

Scalability to a Large Number of Products

\Copy{rev:scalability1}{ A major challenge in discrete choice models (DCMs) is scalability, as many models become increasingly complex and difficult to estimate when the number of products $N$ is large. In this section, we demonstrate that random forests remain practical and effective even when applied to settings with a large number of products.

We test the random forest when $N = 30$ and $50$. Here we assume the number of observed assortments $T_1 = 300$. All assortments cannot be enumerated to compute the RMSE. We thereby randomly sample 10,000 assortments as a testing set $\mathcal{T}_{test}$ and approximate the RMSE as follows.

Tables (ref) and (ref) show the result from 100 simulated datasets under the rank-based model with 4 and 10 rankings, respectively. The random forest significantly outperforms MNL and shows an improvement in performance for larger $N$. Notice that the RMSE is typically smaller when $N$ is large because the denominator of (ref) increases in $N$. We do not test the Markov chain model and the decision forest due to high computational cost for the problem scale. The EM algorithms converge slowly for more than 900 and 2,500 parameters under the Markov chain model.} }

{\color{black} \Copy{rev:scalability2}{ We also consider $N \in \{13, 25, 50, 100, 200, 400\}$ products and generate data using a rank-based DCM with $k = 10$ customer types. For the training set, we test $T_1 \in \{130, 250, 500, 1000, 2000, 4000\}$, generating 10 transactions per assortment, so that the total number of transactions is $T = 10T_1$. Performance is evaluated using RMSE in (ref), with a test set of 10,000 randomly generated assortments. For each configuration, we generate 100 independent training and test datasets and report the mean and standard deviation of the RMSE in Table (ref). The results show that RMSE decreases with larger $T$ for all $N$, clearly illustrating convergence. We also find that random forests scale well to hundreds of products without requiring excessively large training samples. Table (ref) reports the running times. Random forests remain highly efficient even for large $N$ and $T$. In summary, for large-scale problems with large $N$ and $T$, random forests outperform MNL in predictive accuracy while maintaining comparable computational efficiency. }}

{\color{black}

Numerical Experiments for Incorporating Pricing Information

\Copy{rev:pricing_numerical1}{ In this section, we test the performance of random forests when the price information is incorporated. We use the MNL model to generate the choice data. Let $\bm u$ denote the expected utility of the products and $\bm p$ their prices. For given assortment $S$, the choice probabilities of product $i \in S$ and the outside option are:

Consider $N=10$ products. We generate $u_i$ as uniform random variables between 0 and 5 for each product. Then we generate a price uniformly on $[0,5]$ for each product. Note that in this experiment, all products are available in an assortment. As explained in Section (ref), we use the link function $g(x) = \exp(-x)$. The customer's choice then follows the choice probability (ref). The RMSE in (ref) is no longer applicable because the assortments and prices cannot be exhausted. To evaluate the performance, we randomly generate $1000$ assortments and prices according to the same distribution as the training data. Then we evaluate the empirical RMSE in the test data.

In addition to the MNL model, we also use linear demand as a benchmark. Under the linear demand, a customer purchases product $i$ with probability $p(i,\bm p)=(a_i + \sum_{j\in N} b_{ij} p_j)^+$ for some coefficients $a_i$ and $b_{ij}$. The no-purchase probability is thus $1-\sum_{i=1}^N p(i, \bm p)$. We estimate the coefficients using linear regression. Note that linear demand is very popular in modeling demand for multiple products with price information. We investigate the performance of random forests and the two benchmarks for different sizes of training data $T \in \{300,1500,5000\}$.}

\Copy{rev:pricing_numerical2}{ From Table (ref), it is not surprising that MNL has the best performance, because the data is generated by the MNL model. However, when $T=1500$ and 5000, random forests are able to outperform the linear model, which is believed to be fairly robust and used widely. We believe it is due to the model misspecification of the linear model. It further demonstrates the benefit of random forests.

We also test the performance when the ground truth model is linear demand, as shown in Table (ref). The coefficient $a_i$ is uniformly generated on $[0, 0.3]$ and price sensitivity $b_{ii}$ is uniform on $[-0.1, 0]$. The cross-sensitivity $b_{ij}, j \neq i$ is uniform on $[-0.03, 0.03]$ to capture the possibility of substitution or complementary. The linear model has the best performance, followed by random forests. Moreover, random forests significantly outperform the MNL as $T$ increases. From the cross-validation results of Tables (ref) and (ref), we can conclude that random forests have robust performance and benefit from large data sizes for different underlying models.} Moreover, we also numerically show random forests can handle aggregated data in Online Appendix (ref).

}

Concluding Remarks

This paper demonstrates some theoretical and practical benefits of using random forests to estimate discrete choice models, especially when the data is relatively abundant. We also provide comprehensive numerical experiments in Section (ref). It opens up a series of exciting new research questions:

We hope to address some of these questions in future research.

\theendnotes