Learning a Mixture of Two Multinomial Logits

Flavio Chierichetti, Ravi Kumar, Andrew Tomkins
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:961-969, 2018.

Abstract

The classical Multinomial Logit (MNL) is a behavioral model for user choice. In this model, a user is offered a slate of choices (a subset of a finite universe of $n$ items), and selects exactly one item from the slate, each with probability proportional to its (positive) weight. Given a set of observed slates and choices, the likelihood-maximizing item weights are easy to learn at scale, and easy to interpret. However, the model fails to represent common real-world behavior. As a result, researchers in user choice often turn to mixtures of MNLs, which are known to approximate a large class of models of rational user behavior. Unfortunately, the only known algorithms for this problem have been heuristic in nature. In this paper we give the first polynomial-time algorithms for exact learning of uniform mixtures of two MNLs. Interestingly, the parameters of the model can be learned for any $n$ by sampling the behavior of random users only on slates of sizes 2 and 3; in contrast, we show that slates of size 2 are insufficient by themselves.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-chierichetti18a, title = {Learning a Mixture of Two Multinomial Logits}, author = {Chierichetti, Flavio and Kumar, Ravi and Tomkins, Andrew}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {961--969}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/chierichetti18a/chierichetti18a.pdf}, url = {https://proceedings.mlr.press/v80/chierichetti18a.html}, abstract = {The classical Multinomial Logit (MNL) is a behavioral model for user choice. In this model, a user is offered a slate of choices (a subset of a finite universe of $n$ items), and selects exactly one item from the slate, each with probability proportional to its (positive) weight. Given a set of observed slates and choices, the likelihood-maximizing item weights are easy to learn at scale, and easy to interpret. However, the model fails to represent common real-world behavior. As a result, researchers in user choice often turn to mixtures of MNLs, which are known to approximate a large class of models of rational user behavior. Unfortunately, the only known algorithms for this problem have been heuristic in nature. In this paper we give the first polynomial-time algorithms for exact learning of uniform mixtures of two MNLs. Interestingly, the parameters of the model can be learned for any $n$ by sampling the behavior of random users only on slates of sizes 2 and 3; in contrast, we show that slates of size 2 are insufficient by themselves.} }
Endnote
%0 Conference Paper %T Learning a Mixture of Two Multinomial Logits %A Flavio Chierichetti %A Ravi Kumar %A Andrew Tomkins %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-chierichetti18a %I PMLR %P 961--969 %U https://proceedings.mlr.press/v80/chierichetti18a.html %V 80 %X The classical Multinomial Logit (MNL) is a behavioral model for user choice. In this model, a user is offered a slate of choices (a subset of a finite universe of $n$ items), and selects exactly one item from the slate, each with probability proportional to its (positive) weight. Given a set of observed slates and choices, the likelihood-maximizing item weights are easy to learn at scale, and easy to interpret. However, the model fails to represent common real-world behavior. As a result, researchers in user choice often turn to mixtures of MNLs, which are known to approximate a large class of models of rational user behavior. Unfortunately, the only known algorithms for this problem have been heuristic in nature. In this paper we give the first polynomial-time algorithms for exact learning of uniform mixtures of two MNLs. Interestingly, the parameters of the model can be learned for any $n$ by sampling the behavior of random users only on slates of sizes 2 and 3; in contrast, we show that slates of size 2 are insufficient by themselves.
APA
Chierichetti, F., Kumar, R. & Tomkins, A.. (2018). Learning a Mixture of Two Multinomial Logits. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:961-969 Available from https://proceedings.mlr.press/v80/chierichetti18a.html.

Related Material