PCMC-Net: Feature-based Pairwise Choice Markov Chains
Authors: Alix Lhéritier
Venue:  (2020)
Keywords: choice modeling
pairwise choice Markov chains
deep learning
amortized inference
automatic differentiation
airline itinerary choice modeling

Abstract: Pairwise Choice Markov Chains (PCMC) have been recently introduced to overcome limitations of choice models based on traditional axioms unable to express empirical observations from modern behavior economics like context effects occurring when a choice between two options is altered by adding a third alternative. The inference approach that estimates the transition rates between each possible pair of alternatives via maximum likelihood suffers when the examples of each alternative are scarce and is inappropriate when new alternatives can be observed at test time. In this work, we propose an amortized inference approach for PCMC by embedding its definition into a neural network that represents transition rates as a function of the alternatives' and individual's features. We apply our construction to the complex case of airline itinerary booking where singletons are common (due to varying prices and individual-specific itineraries), and context effects and behaviors strongly dependent on market segments are observed. Experiments show our network significantly outperforming, in terms of prediction accuracy and logarithmic loss, feature engineered standard and latent class Multinomial Logit models as well as recent machine learning approaches.

Published as a conference paper at ICLR 2020
PCMC-NET:
FEATURE-BASED PAIRWISE CHOICE MARKOV CHAINS
Alix Lhéritier Amadeus SAS
F-06902 Sophia-Antipolie France alix. 1 it ieeeeeeadduu.com com
ABSTRACT
Pairwise Choice Markov Chains (PCMC) have been recently introduced to over- come limitations of choice models based on traditional axioms unable to express empirical observations from modern behavior economics like context effects oc- curring when choice between two options is altered by adding a third alternative. The inference approach that estimates the transition rates between each possible pair alternatives via maximum likelihood suffers when the examples each alternative scarce and is inappropriate when new alternatives can be observed at test time. In this work, we propose an amortized inference approach for PCMC by embedding its definition into neural network that represents transition rates a function of the alternatives' and individual's features. We apply our construction the complex case of airline itinerary booking where singletons are common (due to varying prices and individual-speccffc itineraries), and context effects and behaviors strongly dependent on market segments are observed. Experiments show our network significantly outperforming, in terms of prediction accuracy and logarithmic loss, feature engineered standard and latent class Multinomial Logit models well as recent machine learning approaches.
INTRODUCTION
Choice modeling aims at finding statistical models capturing the human behavior when faced with set of alternatives. Classical examples include consumer purchasing decisions, choices of schooling or employment, and commuter choices for modes of transportation among available options. Traditional models are based on different assumptions about human decision making, e.g. Thurstone's Case V model (Thurstone) 1927) or Seadley-Terry-Bae
(BTL) model (Bradley & Terry 1952). Nevertheless, in complex scenarios, like online shopping sessions presenting numerous alternatives to user-specific queries, these assumptions often too restrictive provide accurate predictions.
Formally, there is a universe of alternatives U, possibly infinite. In each choice situation, some finite choice set S C U is considered. A choice model is distribution choice set S. where the probability of choosing the item among S is denoted as Pt))). These models can be further parameterized by the alternatives' features and by those of the individual making the choice.
the alternatives of given
An important class of choice models is the Multinomial Logit (MNL), generalization of the BTL model-defined for pairwise choices only-to larger sets. MNL models satisfy Luce's 's axiom also known as independence of irrelevant alternatives (Luce) 1959). which states that the probability of selecting one alternative over another from a set of many alternatives is not affected by the presence or absence of other alternatives in the set. Moreover, any model satisfying Luce's axiom is equivalent to some MNL model (Luce 1977). Equivalently, the probability of choosing some item from a given set can be expressed as Ps(i) = w See wy where w; is the latent value of the item i. Luce's 's axiom implies stochastic transitivity i.e. if P(a b) 1/2 and P(b D- c) > 1/2, then P(a D c) 2 max (P(a D b), (b > c)) where P(i D = P(. (1) (Luce 1977). Stochastic transitivity implies the necessity of total order across all elements and also prevents from expressing cyclic preference situations like the stochastic rock-paper- paper-scissors game described in Section 3.2
Thurstone's is Case V model exhibits striet stochastic transitivity but does not satisfy Luce's axiom

---

Published as a conference paper at ICLR 2020
(Adams & Messick 1958). Luce's axiom and stochastic transitivity strong assumptions that often do not hold for empirical choice data (see (Ragain & Ugander] (2016) and references therein). For example, Luce's axiom prevents models from expressing context effects like the attraction effect (also know as asymmetric dominance or decoy effect), the similarity effect and the compromise effect. The attraction effect occurs when two alternatives are augmented with asymmetrically dominated one (i.e., a new option that is inferior in all aspects with respect to one option, but inferior in only some aspects and superior in other aspects with respect to the other option) and the probability of selecting the better, dominant alternative increases (Huber et al. 1982). The similarity effect arises from the introduction of an alternative that is similar to, and competitive with, one of the original alternatives, and causes decrease in the probability of choosing the similar alternative (Tversky 1972). The compromise effect occurs when there is an increase the probability of choosing an alternative that becomes the intermediate option when a third extreme option is introduced (Simonson 1989). Examples of these effects are visualized in Section 4
A larger class of models is the one of Random Utility Models (RUM) (Block & Marschak 1960 Manski 1977). which includes MNL but also other models satisfying neither Luce's 's axiom nor stochastic transitivity. This class affiliates with each i E U a random variable X; and defines for each subset S C U the probability (t) = P(X; 2 X,. Vj E S). RUM exhibits regularity i.e. if A S B then PA(x) > (x)). Regularity also prevents models from expressing context effects (Huber et al.. 1982). The class of Nested MNL. (McFadden) 1980) allows to express RUM models but also others that do not obey regularity. Nevertheless, inference is practically difficult for Nested MNL models.
Recently, a more flexible class of models called Pairwise Choice Markov Chains has been introduced in Ragain & Ugander (2016). This class includes MNL but also other models that satisfy neither Luce's s axiom, nor stochastic transitivityy nor regularity. This class defines the choice distribution as the stationary distribution of continuous time Markov chain defined by some transition rate matrix. Still, it satisfies a weakened version of Luce's 's axiom called uniform expansion stating that if we add "copies" (with no preference between them), the probability of choosing one element of the copies is invariant to the number of copies. Although the flexibility of this class is appealing, the proposed inference is based on maximizing the likelihood of the rate matrix for the observed choices which is prone to overfitting when the number of observations for each possible alternative is small and is inappropriate when new alternatives can be seen at test time.
Alternatives and individuals making choices can be described by set of features that can be then used to understand their impact on the choice probability. A linear-in-fee in-features MNL assumes that the latent value is given by linear combination of the parameters of the alternatives and the individual. Features of the individual can be taken into account by these models but inference suffers from scareity and is inappropriate when new alternatives can be seen at test time. The latent class MNL (LC-MNL) model Greene & Hensher, 2003) takes into account individual heterogeneity by using a Bayesian mixture over different latent classes-whose number must be specified-in which homogeneity and linearity is assumed. A Ainear-in-featiie
parameterization of PCMC, for features in Rd was suggested in (Ragain & Ugander| 2016 Appendix) but requires fitting a weight matrix of size |U] x d, which makes it scale poorly and does not allow to predict unseen alternativss. In this work, we propose an amortized inference approach for PCMC in the sense that the statistical parameters are reused for any pair of alternatives and their number is thus independent of the size of the universe. In addition, we allow non-linear modeling by using a neural network.
In complex cases like airline itinerary choice, where the alternatives are strongly dependent on an individual-specific query and some features, like price, can be dynamic, the previous approaches have limited expressive power or are inappropriate. Two recently introduced methods allow complex feature handling for alternatives and individuals. Mottini & Acuna-Agost (2017) proposes a recurrent neural network method consisting in learning to point, within sequence of alternatives, to the chosen one. This model is appealing because of its feature learning capability but neither its
properties have been studied nor its dependence on the order of the sequence. [héritier et al. (2019) proposes to train a Random Forest classifier to predict whether an alternative is going to be predicted or not independently of the rest of the alternatives of the choice set. This approach does not take into account the fact that in each choice set exactly one alternative is chosen. For this reason, the probabilities provided by the model are only used as scores to rank the alternatives, which can be interpreted as latent values-making it essentially equivalent to a non-linear MNL. To escape this limitation and make the latent values dependent on the choice set, relative features are added (e.g. the
2

---

Published as a conference paper at ICLR 2020
price for i-th alternative price, is converted to price,/ minjes price, ). The con-parametric nature of this model is appealing but its theiorct properties have not been studied either.
In this work, we propose to enable PCMC with neural networks based feature handling, therefore enjoying both the good theoretical properties of PCMC and the complex feature handling of the previous neural network based and non-parametric methods. This neural network parameterization of PCMC makes the inference amortized allowing to handle large (and even infinite) size universes as shown in our experiments for airline itinerary choice modeling shown in Section
BACKGROUND: PAIRWISE CHOICE MARKOV CHAINS
2.1 DEFINITION
A Pairwise Choice Markov Chain (PCMC) (Ragain & Ugander 2016) defines the choice probability (i( as the probability mass on the alternative E S of the stationary distribution of continuous time Markov chain (CTMC) whose set of states corresponds to S. The model's s parameters are the off-diagonal entries Іi 2 0 of a rate matrix Q indexed by pairs of elements in U. Given choice set S. the choice distribution is the stationary distribution of the continuous time Markov chain given by the matrix Qs obtained by restricting the rows and columns of Q to elements in and setting qa Ejesrs 4ij for each E S. Therefore, the distribution P's is parameterized by the |S] (IS) 1) transition rates of Qs.
The constraint
4 qj >
imposed in order guarantee that the chain has single closed communicating class which implies the existence and the unicity of the stationary distribution IT (see, e.g., 18.ris (1997)) obtained by solving
T g
where and are row vectors zeros and ones, respectively. Since any column of Q2 is the opposite of the sum of the rest of the columns, it is equivalent to solve
IT O's 0 1]
where O's = [===[
(
I
2.2 PROPERTIES
In Ragain & Ugander 2016). it is shown that PCMC allow to represent any MNL model, but also models that are non-regular and do not satisfy stochastic transitivity (using the rock-scissor-paper example of Section 3.2).
In the classical red bus/blue bus example (see, e.g.. Train (209)), the color of the bus is irrelevant to the preference of the transportation mode "bus" with respect to the "car" mode. Nevertheless, MNL models reduce the probability of choosing the "car" mode when color variants of buses are added, which does not match empirical behavior. PCMC models allows model this kind of situations thanks to a property termed contractibility, which intuitively means that we can "contract" subsets A, U to single "type" when the probability of choosing element of A, is independent of the pairwise probabilities between elements within the subsets. Formally, a partition of U into non-empty sets A A1...., A is contractible partition if Qaza, Xiς for all a, Ai, A₁ for some A = { for i E {l...., k}. Then, the following proposition is shown.
Proposition (Ragain & Ugander (2016)). For a given A, let Ai...., Ay be a contractible partition for two PCMC models on U represented by Q, Q' with stationary distributions n, n². Then, for any A,
Σ Po(i) Σ PbG) JEA:
JEA:
Then it is shown, that contractibility implies uniform expansion formally defined follows.
3

---

Published as a conference paper at ICLR 2020
Definition (Uniform Expansion). Consider choice between elements in set 5(1) (in..... )n1). ), and another choice from set S(k) containing k copies of each of the elements: ((h) = fi11,.... ,01,, f21..... 12k. .2....... bnl..... bnk The axiom of uniform expansion states that for each m E {l,..., n and all k 2 1,
Pst (im1) =
Σ ==1
Pooa (ims)-
2.3 INFERENCE
Given dataset D, the inference method proposed in Ragain & Ugander (2016) consists in maximizing the log likelihood of the rate matrix Q indexed by
log L(Q:D) = Eis((D log (s)
(4)
SEUiES
where (1) denotes the probability that i is selected from S as a function of Q and Cis (D) denotes number of times the data that was chosen out of set
This optimization is difficult since there is general closed form expression for P (i) and the implicit definition also makes difficult to derive gradients for log L with respect the parameters quj. The authors propose to Sequential Least Squares Programming (SLSQP) to maximize log L(Q:)), which nonconcave general. However, in their experiments, they encounter numeri- cal instabilities leading violations (qij qjz 0) of the PCMC definition, which were solved with additive smoothing at the cost of some efficacy of the model. In addition, when the examples each alternative scarce like in the application of Section this inference approach is prone to severe overfitting and is inappropriate to predict unseen alternatives. These two drawbacks motivate the amortized inference approach introduce next.
PCMC-NET
We propose an amortized inference approach for PCMC based on a neural network architecture called PCMC-Net that uses the alternatives' and the individual's features to determine the transition rates and can be trained using standard stochastic gradient descent techniques.
3.1 ARCHITECTURE
Input layer For PCMC, the choice S were defined set of indices. For PCMC-Net, since is feature-based, the choice sets $ are defined as sets of tuples of features. Let St be the tuple of features of the i-th alternative of the choice set S belonging given feature space F, and / be the tuple of the individual's 's features belonging to a given feature space Fo. The individual's features are allowed be an empty tuple.
Representation layer features
The first layer is composed of a representation function for the alternatives'
Puc. F. Rd
and representation function for the individual's I's features
Pro Fo dRd
where wi and w. are the sets of weights parameterizing them and do, d, N are hyperparameters. These functions can include, e.g., embedding layers for categorical variables, a convolutional network for images text, etc., depending the inputs' types.
Cartesian product layer In order to build the transition rate matrix, all the pairs of different alternatives need to be considered, this is accomplished by computing the cartesian product
(pw. (Si),. . Pvr, { {pw., (Si),-..,Pk (S1s)))-
4

---

Published as a conference paper at ICLR 2020
Puu
Pin, (2)
lineur solver
S,
Pay, (Si)
hz
E
Pas
X
(5,)
0
Figure I: PCMC-Net. x denotes the cartesian product and + vector concatenation.
The combinations embedded alternatives are concatenated together with the embedded features of the individual, i.e.
Rij Pwo (T) @ Pwu (S,) @ Pw. (S,)
(8)
where denotes vector concatenation.
Transition rate layer
The component is model of the transition rate (Qs)ıj, i j:
Φ max(0, fw. (Re))) +
(9)
where fie, consists of multiple fully connected layers parameterized by set of weights wy and is a hyperparameter. Notice that taking the maximum with 0 and adding guarantees non-negativity and the condition of Eq. The transition rate matrix Q is then obtained as follows:
if i
Qu
(10)
Ejtt 1 45
otherwise
Stationary distribution layer The choice probabilities correspond to the stationary distribution स that is guaranteed to exist and be unique by the condition of Eq. [ and can obtained by solving the system
#
(2.)
1"
-
1
(11)
by, e.g., partially-pivoter LU decomposition which can be differentiated with automatic differentia- tion.
The whole network is represented in Fig.
3.2 PROPERTIES
Non-regularity As shown in Ragain & Ugander (2016), non-regular models can obtained by certain rate matrices. For example, the stochastic tock-paper-scissors game can be described by non-regular model obtained with the following transition rate matrix with 2 < a $ 1:
-1
1
Q
=
α 1-a
1-a a
(12)
-1
PCMC-Net can represent such model by setting the following design parameters. In this case, the individual's s features correspond to an empty tuple yielding an empty vector as representation, By setting Pv.. to one-hot hot representation of the alternative (thus d, = 3), fully connected network fw, consisting of one neuron (i.e. six coefficients and one bias) is enough to represent this matrix since six combinations of inputs of interest.
non-paraeetric limit More generally, the following theorem shows that any PCMC model can be arbitrarily well approximated by PeMC-Net.
Theorem 1. If P... and fwo are given enough capacity, PCMC-Net can approximate any PCMC model arbitrariyy well.

---

Published as a conference paper at ICLR 2020
Proof. A PCMC model jointly specifies family of distributions Ts for each S 2 obtained by subsetting a single rate matrix Q indexed by U. Therefore, it is sufficient to prove that PCMC-Net can approximate any matrix Q since qtj. with * j, does not depend on S. PCMC-Net forces the transition rates to be at least 6, whereas the PCMC definition allows any dig 2 0 as long as Ki + Oja > O. Since multiplying all the entries of rate matrix by some 0 does not affect the stationary distribution of the corresponding CTMC, let us consider, without loss of generality, an arbitrary PCMC model given by transition rate matrix Q", whose entries are either at least e or zero. Let '' be its stationary distribution. Then, let us consider the matrix Q(c, c) obtained by replacing the null entries of Q* by and by multiplying the non-null entries by some > 0, and let (TC,, c()) be its stationary distribution. Since, by Cramer's rule, the entries of the stationary distribution are continuous functions of the entries of the rate matrix, for any 6 >> 0, there exist c(6) > 0 such that (m(e, c(5) - -=' < 6.
Since deep neural networks are universal function approximators (Hornik et al., 1989). PCMC-Net allows to represent arbitrarily well any Q(e, c) if enough capacity is given to the network, which completes the proof.
Contractibility Let Q, Q' be the rate matrices obtained after the transition rate layer of two different PCMC-Nets on a finite universe of alternatives U. Then, Proposition I can be applied. Regarding uniform expansion, when copies added to choice set, their transition rates to the other elements of the choice set will be identical since they only depend on their features. Therefore, PCMC-Net allows uniform expansion.
3.3 INFERENCE
The logarithmic loss is used to assess the predicted choice distribution म given by the model parame- terized by w = wp U wa U Wy on the input ST against the index of actual choice Ys.
loss (w,, S, Ys) = log Rys-
(13)
Training can be performed using stochastic gradient descent and dropout to avoid overfitting, which is stable unlike the original inference approach.
EXPERIMENTS ON SYNTHETIC DATA WITH CONTEXT EFFECTS
To illustrate the ability of PCMC and PCMC-Net models of capturing context effects we simulate them using the multiattribut linear ballistic accumulator (MLBA) model of Trueblood et al. (2014) that is able to represent attraction, similarity and compromise effects. MI.BA models choice as process where independent accumulators are associated to each alternative and race toward threshold. The alternative whose accumulator reaches the threshold first is selected. The speed of each acculumator determined by a number of parameters modeling human psychology notably, weights that determine the attention paid to each comparison and a curvature parameter determining a function that gives the subjective value of each alternative from its objective value.
We consider the example of (Trueblood et al., 2014, Figure 7) reproduced in Figure 2() where a choice set of two fixed alternatives {a, b) is augmented with a third option e and the preference of over b, i.e. (() is computed. The model considers two attributes such that higher
(a)
values are more preferable. The two original alternatives are a = (4, 6). b = (6, 4).. For example, these can correspond two different laptops with RAM capacity and battery life as attributes, and is a third laptop choice influencing the subjective value of with respect to b.
In order to generate synthetic choice sets, we uniformly sample the coordinates of e in [1, 9|2 Then, we compute the choice distribution given by the MLBA mode]" that is used to sample the choice.
We instantiate PCMC-Net with an identity representation layer with d, and do 0 and transition rate layer with h E (1,2,3} hidden layers of y = 16 nodes with Leaky ReLU activation
Using the code available at
ce-node1

---

Published as a conference paper at ICLR 2020
Fc
FA
Ground truth.
MNL
(iii) PCMC
(iv) PCMC-Net 3 16
Figure 2: Preference for a over for different attributes (coordinates of each pixel) of the third alternative c. Lighter shades indicate higher preference for a. Models were trained on 20000 choice sets. In Fig- (i) the points ca, cş and ec show examples of, respectively, attraction, similarity and compromise effects with respect to a.
(slope = 0.01) and 0.5 In order to use the original PCMC mode we discretize the attributes of the third option using 8 bins on each attribute, obtaining different alternatives in addition to identified and b. We also compare to linear-in-features MNL mode Figure shows how the different models represent the preference for a over Table I shows Monte Carlo estimation of the expected Kullback-Leibler divergence comparing each model to the true MLBA model
P(a.h.e()) (1) Plabbet (i) dc. P ((a.be)(1)
(o-uu(( (PI
Σ
(14)
64
[1.9] (E(a,,.))
As expected, MNL is unable to represent context effects due the independence of irrelevant al- ternatives. After discretization, the original PCMC provides good approximation of the MLBA model. Nevertheless, it is difficult to further refine it since the number of statistical parameters grows biquadratically with the number of bins for each feature. As shown in Table the amortized inference approach of PCMC-Net allows better approximation of the original model with significantly fewer statistical parameters than the discretized PCMC.
Table 1: Monte Carlo estimate of the expected KL divergence between the different models and the true MLBA model. A set of 10000 points c, different from the training one, was used.
P MNL. PCMC
h x v
#parameters Ee DeL. (P]
.119
4290
.022
PCMC-Net
1 x
97
.018
PCMC-Net
2 X 16
369
.011
PCMC-Net 3 x 16
641
.009
EXPERIMENTS ON AIRLINE ITINERARY CHOICE MODELING
In this section, we instantiate PCMC-Net for the case of airline itinerary choice modeling. As shown in Babutsidze et al. 2219), this kind of data often exhibit attraction effects, calling for more flexible models such as PCMC. Nevertheless, in the considered dataset, alternatives rarely repeat themselves, which makes the original inference approach for PCMC inappropriate.
We trained it with the Adam optimizer with one choice set per iteration, learning rate of 0.001 and no dropout, for 100 epochs. Code is available https:://giiie http:///wwwo....a///////t/a///ae Net used the implementation available at httpt:: /gi thub. com s ragai pesgann/pmmae /ppcc-----omemmmm///p// ni nips with addi- tive smoothing = 0.1 and maximum of 50 iterations. The hest model over 20 restarts was considered.
com
UUsing Larch available at htttps: //tt:p:://iii thub. com/ jpn- 1ooon-11arcph /larch

---

Published as a conference paper at ICLR 2020
5.1 DATASET
We used the dataset from Mottini & Acuna-Agost (2017) consisting of flight bookings sessions on of European origins and destinations. Each booking session contains up 50 different itineraries, one of which has been booked by the customer. There are 815559 distinct alternatives among which 84% are singletons and 99% are observed at most seven times. In total, there are 33951 choice sessions of which 27160 were used for training and 6791 for testing. The dataset has total of 13 features, both numerical and categorical, corresponding to individuals and alternatives (see Table 4).
5.2 INSTANTIATION OF PCMC-NET
PCMC-Net was implemented in PyTorrch (Paszke al., 2017 During training, mini-batch com- posed of a number of sessions whose number of alternatives can be variable. Dynamic computation graphs are required in order adapt the varying session size. Stochastic gradient optimization is performed with Adam (Kingma & Ba 2013). In our experiments, numerical variables are unidi- mensional and thus are not embedded. They were standardized during a preprocessing step. Each categorical input of cardinality G is passed through an embedding layer, such that the resulting dimension is obtained by the rule of thumb d, := min( ([; 50). We maximize regularization by using a dropout probability of 0.5 (see, e.g.. Ba.Bi & Sadowski (013)). The additive constant was set to 0.5. The linear solver was implemented with torch. sol lve, which uses LU decomposition. Table 2 shows the hyperparameters and learning parameters that were optimized by performing 25 iterations of Bayesian optimization (using GPyOpt lauthors (2016).. Early stopping is performed during training if no significant improvement (greater than 0.01 with respect the best log loss obtained so far) is made on a validation set (a random sample consisting of 10% the choice sessions from the training set) during 5 epochs. Using the hyperparameters values returned by the Bayesian optimization procedure and the number of epochs at early stopping (66), the final model is obtained by training on the union of the training and validation sets.
Table Hyperparameters optimized with Bayesian optimization.
parameter
range
best value
learning rate
110
li=
0.001
batch size (in sessions) hidden layers in sm, nodes per layer in fwr activation
{2) 0
16
1,2,3]
2
{2' 1-5...9
512
(ReLU, Sigmoid, Tanh, LeakyRel.U)
LeakyReL.U
5.3 RESULTS
We compare the performance of the PCMC-Net instantiation against three simple baselines:
Uniform: probabilities are assigned uniformly to each alternative.
Cheapest (non-probabillsticc:: alternatives are ranked by increasing price.
Shortest (non (non-probabilistic): alternatives are ranked by increasing trip duration.
We also compare against the results presented Lhéritier et al. (2019)
Multinomial Logit (MNL): choice probabilities are determined from the alternatives features only, using some feature transformations to improve the performance.
Latent Class Multinomial Logit (LC-MNL): in addition to the alternatives' features, it uses in- dividual's 's features which are used model the probability of belonging some latent classes whose number is determined using the Akaike Information Criterion. Feature transformations are also used to improve the performance.
Random Forest (RF): classifier is trained the alternatives as if they were independent, considering both individual's s and alternatives' features and using as label whether each alternative was chosen or not. Some alternatives' features transformed to make them relative to the values of each choice set. Since the classifier evaluates each alternative
*Code available at httttpp::/gghhbbbbbbb com/ htc.th
8

---

Published as a conference paper at ICLR 2020
independently, the probabilities within given session generally do not add to one, and therefore are just interpreted as scores to rank the alternatives.
And, finally, we compare to
Deep Pointer Networks (DPN) (Mottini Acuna-Agosi 2017); a recurrent neural network that uses both the features of the individual and those of the alternatives learn to point to the chosen alternative from the choice sets given as sequences. The results are dependent on the order of the alternatives, which was taken in the original paper, that is, they were shown to the user.
We compute the following performance measures the test set T of choice sets and corresponding individuals:
Normalized Log Loss (NLL): given probabilistic choice model P.
NL. ग E(s.neT log (T)
TOP N accuracy: proportion of choice sessions where the actual choice was within the top N ranked alternatives. In case of ties, they are randomly broken. We consider N {1,5}.
Table shows that PCMC-Net outperforms all the contenders all the considered metrics. It achieves a 21.3% increase in TOP-1 1 accuracy and 12.8% decrease in NLL with respect to the best contender for each metric. In particular, we observe that the best in TOP N accuracy among the contenders LC-MNL and RF, both requiring manual feature engineering to achieve such performances whereas PCMC-Net automatically learns the best representations. We also observe that our results are significantly better than those obtained with the previous deep learning approach DPN, showing the importance of the PCMC definition in our deep learning approach to model the complex behaviors observed in airline itinerary choice data.
Table 3: Results on airline itinerary choice prediction. indicates cases with feature engineering.
method
TOP 1
TOP 5
NLL
Uniform
.063
.255
3.24
Cheapest
.164
.471
Shortest
.154
.472
MNL*
.224
.624
2.44
LC-MNL*
.271
.672
2.33
RF.
.273
.674
DPN
.257
.665
2.33
PCMC-Net
.331
.745
2.03
CONCLUSIONS
We proposed PCMC-Net, a generic neural network architecture equipping PCMC choice models with amortized and automatic differentiation based inference using alternatives' features. As a side benefit, the construction allows to condition the probabilities on the individual's features. We showed that PCMC-net is able to approximate any PCMC model arbitrarily well and, thus, maintains the flexibility (e.g., allowing to represent non-regular models) and the desired property of uniform expansion. Being neural network based, PCMC-Net allows complex feature handling as previous machine learning and deep learning based approaches but with the additional thcoretical guarantees.
We proposed practical implementation showing the benefits of the construction on the challenging problem of airline itinerary choice prediction, where attraction effects often observed and where alternatives rarely appear more than once- maaein the original inference approach for PCMC inappropriate.
As future work, we foresee investigating the application of PCMC-Net on data with complex features (e.g. images, texts, graphs ...) assess the impact of such information preferences and choice.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
Thanks María Zuluaga, Eoin Thomas, Nicolas Bondoux and Rodrigo Acuña-Agost for their insightful comments and to the four anonymous reviewers whose suggestions have greatly improved this manuscript.
REFERENCES
Emest Adams and Samuel Messick. An axiomatic formulation and generalization of successive intervals scaling. Psychometrika, 23(4):355-368, Dec 1958. ISSN 1860-0980. doi: 10.1007/ BF02289784.
The GPyOpt authors. Gpyopt: A bayesian optimization framework python. http://githu>
com/ SheffieldML MMt/dM/L/PPPR 2016.
Zakaria Babutsidze, William Rand, Emil Mirzayev, Ismael Rafai, Nobuyuki Hanaki, Thierry Delahaye, and Rodrigo Acuna-Agost. Asymmetric dominance in airfare choice. In 6th International Conference of Choice Modelling. ICMC, 2019.
Pierre Baldi and Peter J Sadowski. Understanding dropout. In Advances in neural information processing systems, pp. 28 14-22222, 2013.
HD Block and Jacob Marschak. Random orderings and stochastic theories of response. Contributions to Probability and Statistics, 2:97-132, 1960.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345 1952.
William H Greene and David A Hensher. A latent class model for discrete choice analysis: contrasts with mixed logit. Transportation Research Part B: Methodological, 37(8):681-698, 2003.
Kurt Horiik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Joel Huber, John W Payne, and Christopher Puto. Adding asymmetrically dominated alternatives: Violations of regularity and the similarity hypothesis. Journal of consumer research, 911):90-98, 1982.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Alix Lhéritier, Michael Bocamazo, Thierry Delahaye, and Rodrigo Acuna-Agost, Airline itinerary choice modeling using machine learning. Journal of Choice Modelling. 11:198-209, 2019.
R. Duncan Luce. Individual Choice Behavior: A Theoretical analysis. Wiley, New York, NY, USA, 1959.
Duncan Luce. The choice axiom after twenty years. Journal of mathematical 215-233, 1977.
psyceeoollcappyyylloogggy psychology, 15(3):
Charles F Manski. The structure of random utility models. Theory and decision, 8(3):229-254, 1977.
Daniel McFadden. Econometric models for probabilistic choice among products. Journal of Business, pp. S13-S29, 1980.
Alejandro Mottini and Rodrigo Acuna-Agost. Deep choice model using pointer networks for airline itinerary prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1575-1583. ACM, 2017.
R. Noris. Markov Chains. Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, 1997. doi: 10.1017/C1097805111 1810031
10

---

Published as a conference paper at ICLR 2020
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Stephen Ragain and Johan Ugander. Pairwise choice markov chains. In Advances in Neural Information Processing Systems, pp. 3198-3206, 2016.
Itamar Simonson. Choice based on reasons: The case of attraction and compromise effects. Journal of consumer research, 16(2):158- 174, 1989.
Louis Thurstone. law of comparative judgment. Psychological review, 34(4):273, 1927.
Kenneth E Train. Discrete choice methods with simulation. Cambridge university press, 2009.
Jennifer S Trueblood, Scott D Brown, and Andrew Heathcote. The multiattribute linear ballistic accumulator model of context effects in multialternative choice. Psychological review, 121(2):179, 2014.
Amos Tversky, Elimination by aspects: A theory of choice. Psychological review, 79(4):281, 1972.
A
FEATURES OF THE AIRLINE ITINERARY CHOICE DATASET
Table 4: Features of the airline itinerary choice dataset.
Type
Feature
Range/Cardinality
Origin/Destination
97
Categorical
Search Office
11
Departure weekday
[0,6]
Individual
Stay Saturday
[0.1]
Numerical
Continental Trip
[0,1]
Domestic Trip
[0.1]
Days to departure
[0, 343]
Categorical
Airline (of first flight)
Price
[77.15,16781.5]
Stay duration (minutes)
[121,434000]
Trip duration (minutes)
[105, 4314]
Alternative
Numerical
Number connections
[2.6]
Number airlines
[1,4]
Outbound departure time (in from midnight)
[0, 84000]
Outbound arrival time (in from midnight)
[0. 84000]


Reviews:
[{"review_id": "rJxDQbYstS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an approach for choice modeling that leverages neural network features in a continuous-time Markov Chain whose stationary distribution represents the choice distribution. Nonlinear features can be computed for both alternatives and individuals, and the resulting model beats all baselines in terms of log-likelihood and accuracy on an airline itinerary choice prediction task.\n\nOverall, this paper presented a simple but effective approach for using neural networks in the PCMC class of models. The experimental section is too limited, with results on only one dataset and no comparison of different architectural choices for how to incorporate neural networks into PCMC models, or analysis pointing toward what the features are learning that allows them to improve over earlier approaches. The text was also confusing in a number of places (possibly due to my lack of knowledge in choice modeling), and there’s no discussion of related work incorporating neural networks into ranking-based models.\n\nComments:\n* Knowing nothing about choice modeling, I found the introduction hard to follow with lots of jargon that may be inaccessible to the broader ML community. It may be useful to specify the set of desired properties for these models up front, and then highlight how the different existing models do or don’t satisfy these properties (e.g. uniform expansion, regularity, efficiency,  framing effects, etc.)\n* How is the proposed approach “amortized inference”? \n* What’s the triangle notation in P(a |> c) ?\n* It’d be useful to say more as to why contractability/uniform expansion are useful components of a choice model.\n* “Additive smoothing at the cost of some efficacy” - efficacy in what sense? Expressivity? Or worse performance? The same smoothing technique (minimum of epsilon) seems to be used in this approach.\n* Theorem 1 and proof do not consider some of the architectural choices of PCMC-Net (e.g. cartesian product layers, does d_a have to go to infinity?)\n* Contractability: why is this property desirable if you don’t take advantage of it computationally?\n* Why is SGD + dropout training stable but the original MLE problem not?\n* Comparison to baselines using low-rank or other simple parameterizations of Q?\n* Table 1 should be moved to supplement\n* “Usual rule of thumb” -> cite something here? Not familiar with this\n* What is the impact of \\epsilon and dropout probability on model performance? From proofs I had expected \\epsilon tiny (1e-9) but you use 0.5\n* Would be useful to show how model performs on smaller dataset to gain intuition", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1xv9y4k5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:  This paper enables a feature-based parametrization and amortized inference of Pairwise Choice Markov Chains (PCMCs), a model for decisions in the face of a set of alternative choices (e.g. the rock-paper-scissors game).  Previous approaches to fitting PCMCs have leveraged sequential least squares programming, making optimization unstable, the model prone to overfitting, and test-time inference difficult.  The authors propose parametrizing PCMCs with neural networks to fix these issues.  Relying on universal function approximation results, the authors show that their PCMC-Net can represent arbitrary transition matrices.  The experiments report results on a dataset of airline booking behavior, comparing PCMC-Net with four other baselines from the literature.\n\nPros:  Although I was previously unfamiliar with the PCMC model, using a neural network parametrization seems novel and well motivated.  Moreover, the airline data experiment seems to validate that PCMC-Net is indeed effective, besting the other baselines in all three metrics.  \n\nCons:  I have two main concerns over the paper’s experimental rigor…\n\n#1 Lack of Simulation Studies: The paper makes claims about the representation properties of PCMC-Net but fails to validate them with simulation studies.  \n\n#2 Lack of data sets: Only one experiment on one data set is reported. \n\nFinal Evaluation:  While I found the paper’s methodology well motivated and sensible, the experiments do not thoroughly validate the method as they contain no simulation studies and only one data set.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1xfZCnTKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a novel approximate inference method, called PCMC-Net, for models from the family of Pairwise Choice Markov Chains (PCMC). The method relies on training a neural network. Consequently, the authors claim that inference is amortized, but its computational complexity is still quadratic in the number of choice alternatives due to separate processing of all pairs of alternatives. PCMC-Net bakes the definition of PCMC into the neural net structure and therefore satisfies the theoretical properties of contractability and uniform expansion, which are desired properties of choice models\nMoreover, since choice probabilities are a function of choice candidates’ features (and features of an individual making the choice), this method allows for new (unseen) choice candidates at test time, which was not possible with previously proposed maximum-likelihood (ML) inference. The approach is evaluated on modelling the choice of airline itinerary, on which it outperforms all considered baselines by a significant margin.\n\nI recommend REJECTing this paper. This paper tackles the problem of efficient inference and test-time generalization (to unseen choice alternatives) for choice modelling, and the proposed approach is interesting, seems to be theoretically sound, and outperforms evaluated baselines. Experimental evaluation is insufficient, however, with the method assessed only on a single dataset---in which case it is unclear if the method is better than baselines in general, or whether it is a quirk of the considered dataset. Moreover, the authors do not compare to ML inference in PCMC, which seems to be the closest possible baseline; instead, the authors only mention that ML would overfit on this dataset. Finally, the paper is full of complicated terms and cumbersome notation, which makes it difficult to read. Technical terms are often used without definition (e.g. framing effects, Luce’s axiom, asymmetric dominance), which makes the paper inaccessible to an inexperienced reader like myself.\n\nI think that this work could be improved in the following ways. The exposition should be made simpler and easier to follow (especially section 2), and all technical terms should be appropriately defined. Additionally, the method should be evaluated on at least one more dataset and compared to ML inference for PCMC. I am happy to increase my score if (all) the above points are addressed.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1l2wrZ_cr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1.The goal of the paper is to connect flexible choice modeling with a modern approach to ML architecture to make said choice modeling scalable, tractable, and practical. \n2. The approach of the paper is well motivated intuitively, but could more explicitly show that PCMC-Net is needed to fix inferential problems with PCMC and that e.g. SGD and some regularization + the linear parameterization suggested by the original PCMC authors isn't scalable in itself. \n3. The approximation theorem is useful and clean, and the empirical results are intriguing. While consideration of more datasets would improve the results, the metrics and baselines considered demonstrate a considerable empirical case for this method. \n\nMy \"weak accept\" decision is closer to \"accept\" than \"weak reject.\" (Edit 11/25/19: I raised my score in to accept in conjunction with the author's improvements in the open discussion phase)\n\nImprovement areas(all relatively minor):\n- While I personally enjoy the choice axioms focused on by the PCMC model and this paper, stochastic transitivity, IIA, and regularity are probably more important to emphasize than Contractibility. Because the properties of UE and contractibility were not used, it may be more appropriate to use this space to introduce more of the literature on neural-nets-as-feature-embeddings stuff. \n- This paper could be improved by generalizing to a few other choice models- in particular the CDM (https://arxiv.org/abs/1902.03266) may be a good candidate for your method. This is more a suggestion for future work if you expand this promising initial result. \n- Hyper-parameter tuning: I noticed that several of your hyper parameters were set to extremal values for the ranges you considered. If you tuned the other algorithms' hyper parameters the same way, it could be the case that the relative performance is explained by the appropriateness of those ranges. Would be interesting to have a more in-depth treatment of this, but I do understand that it's a lot of work. \n\n\nSpecific Notes:\nTheorem 1 is nice, and the proof is clean, but doesn't explicitly note that a PCMC model jointly specifies a family of distributions \\pi_S for each S \\in 2^U obtained by subsetting a single rate matrix Q indexed by U. It's clear that PCMC-Net will still approximate under this definition, as \\hat q_ij  approximates each q_ij because \\hat q_ij doesn't depend on S. While the more explicit statement is true with the same logic in the theorem, the notational choice to have \"X_i\" represent the \"i-th\" element in S is confusing at first, as e.g. X_1 is a different feature vector for S = {2,3} and S={1,3}. I don't see this issue as disqualifying, but it took me a while to realize that there wasn't more than a notational abuse problem when I returned to the definitions where the indexing depended on the set S under consideration. \n\n\nTypos/small concerns:\n-Above equation (1), the number of parameters in Q_S is |S|(|S|-1) rather than (|S|-1)^2, as each of the |S| alternatives has a transition rate to the other |S|-1 alternatives. \n-Below equation (3), I think you mean j \\in S rather than 1<= j <= |S|, as S may not be {1,2,...,|S|}. Later I noticed that you always index S with {1,\\dots,|S|}, but using i \\in S in combination with 1<=j<=|S| was a bit confusing. \n-X_i as the i-th element of S is a bit of an abuse of notation, as it surpasses dependence on S\n-In Figure 1, you show X_0 in a vector that is referred to as \"S.\" It is my understanding that X_0 represents user features. As the user is not in the set, this is confusing. The use of a vertical ellipsis to connect \\rho(X_0) to \\rho(X_1) is also confusion, as \\rho(X_1) is input into the Cartesian product while X_0 is input into the direct sum. \n\nOverall, nice job! Really enjoyed the paper and approach, good to see connections made between these literatures so that progress in discrete choice can be used at scale. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission proposes to use neural networks in combination with pairwise choice markov chain models for choice modelling. The deep network is used to parametrize the PCMC and in so doing improve generalization and inference.

Strengths:
The formulation and theoretical justifications are convincing.
The improvements are non-trivial and the approach is novel.

Weaknesses:
The text was not always easy to follow.
The experimental validation is too limited initially. This was addressed during the discussion by adding an additional experiment.

All reviewers recommend acceptance.

Decision: Accept (Poster)