Learning Mixed Multinomial Logit Model from Ordinal Data
Motivated by generating personalized recommendations using ordinal (or preference) data, we study the question of learning a mixture of MultiNomial Logit (MNL) model, a parameterized class of distributions over permutations, from partial ordinal or preference data (e.g. pair-wise comparisons). Despite its long standing importance across disciplines including social choice, operations research and revenue management, little is known about this question. In case of single MNL models (no mixture), computationally and statistically tractable learning from pair-wise comparisons is feasible. However, even learning mixture with two MNL components is infeasible in general. Given this state of affairs, we seek conditions under which it is feasible to learn the mixture model in both computationally and statistically efficient manner. We present a sufficient condition as well as an efficient algorithm for learning mixed MNL models from partial preferences/comparisons data. In particular, a mixture of r MNL components over n objects can be learnt using samples whose size scales polynomially in n and r (concretely, r 3.5 n 3 (log n)
This paper studies a rank data model as a mixture of Luce (or Plackett-Luce) Model. They provide conditions for estimating parameters of this model along with a moment-based algorithm. They further relate their theory to the algorithm.This paper has nice technical results and they are presented well. I have a couple of concerns/suggestions with the following pieces of the presentation:1-    The authors state that they are learning Mixture Multinomial Logit models. Despite being closely related, their model is only considering Mixture of Luce model. The concerning differences are as follows:      i) MNL originally and traditionally, is used when you also observe alternative characteristics (also named as Multinomial logit regression) and the significance of research on Mixed MNL and MNL are due to the econometrics application. However, this paper does not get into that aspect and does not relate the results to an econometric setting.      ii) In most of applications, MNL is used for choice data, where we observe top 1 choice of agents (in fact their market shares). However, the theories and algorithms in this paper do not talk about this case. In fact, this paper only concerns pairwise data either observed directly as independent pairs or after the pre-process from full rankings. Therefore, I suggest clarifying the beam of this paper and its implications in MNL and MMNL. 2-    Since theorem 3 guarantees the correctness with high probability, isn’t the correctness of the algorithm an approximate correctness? Also, a condition (ASSUMPTION 1) in David Hunter’s paper (MM algorithms for generalized Bradley-Terry models. In The Annals of Statistics , volume 32, pages 384–406, 2004) depicts that there are cases that can lead to irreducibility of the defined graph, with the data. From Hunter et al.: "As noted by Ford (1957), if it is possible to partition the set of individuals [alternatives] into two groups A and B such that there are never any inter group comparisons, then there is no basis for rating any individual in A with respect to any individual in B. On the other hand, if all the intergroup comparisons are won by an individual from the same group, say group A, then if all parameters belonging to A are doubled and the resulting vector renormalized, the likelihood must increase; thus, the likelihood has no maximizer. The following assumption [Ford (1957)] eliminates these possibilities." And I wonder if Hunter's assumption 1 is not needed for the correctness of the proposed algorithms?3-     I can’t make sense of proposition 2.14-     There are no experiments comparing the proposed algorithm with former works and there are no experiments describing the performance which is claimed theoretically. There is a large body of work and algorithms for Mixed Multinomial Logit model (as the authors indicated in introduction) and I really liked to see a comparison with some real data or a synthetic setting.The problem and results of the paper are presented clearly.1-    As the authors indicate, there is a lot of work done in this line of research and there are some papers which algorithmically address the exact same estimation problem as this paper and in terms of application it is not clear what the gain of the new algorithm is. For example, the following papers proposed algorithms for estimating mixture of placket-Luce Model:A mixture of experts model for rank data with applications in election studies Authors: Isobel Claire Gormley, Thomas Brendan MurphyClustering ranked preference data using sociodemographic covariatesAuthors: Isobel Claire Gormley, Thomas Brendan MurphyGeneralized Random Utility Models with Multiple Types Authors: Hossein A. Soufiani, Hansheng Diao , Zhenyu Lai, David C. Parkes,A Markov Chain Approximation to Choice Modeling Authors: Jose Blanchet, Guillermo Gallego, Vineet Goyal2-    The results on identifying conditions for the mixture of PL models is original and interesting. Authors mention their results as “identifiable” in the discussion. However, it is not clear whether this is a formal statistical identifiablity claim.3-    Combining moment-based methods for ranks in order to find efficient estimators is interesting, and have been used in the following paper: Azari et al., Computing Parametric Ranking Models via Rank-Breaking and same authors, Generalized Method-of-Moments for Rank Aggregation. It is interesting to see how this work relates and compares to their methods experimentally and theoretically.The interest in this work can be two folds, from an operations research aspect or rank aggregation aspect.From the operation research point of view, this work lacks clear connection between the claims and an application through computational experiments to illustrate the implications of the new model for the specific OR problem.From the rank aggregation aspect, and viewing the model as mixture of PL or BTL, the conditions and results are interesting, and with clear presentation this is an original contribution.