Light RUMs
Authors: Flavio Chierichetti, Ravi Kumar, Andrew Tomkins
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our Results. This paper closes the question to within logarithmic factors, as follows. For a universe of n items, any RUM may be approximated arbitrarily closely on all slates as either a mixture of (n) permutations or as a mixture of e (n) MNLs, and both these bounds are tight up to logarithmic factors. Either type of model may be represented using e (n2) bits; such a representation is also tight, in the strict sense that no representation of asymptotically fewer bits is sufficient to approximate a generic RUM, no matter the form of the representation. We perform some experiments to explore the implications of these theoretical results. In our first set of experiments we study a dataset in which users provide their total ordering of different sushi variants, essentially encoding a complete RUM. This allows us to study exactly how well the construction in our upper bound approximates a RUM in a practical setting. We show that the quality of approximation is almost perfectly predicted by our theoretical results, and that a representation based on just 1% of the data provides an accurate approximation of the overall RUM. In our second set of experiments we consider the setting of Ragain & Ugander (2016), who present an interesting non-rational choice model that is incomparable to the class of RUMs. In this setting we are able to compare the nonrational choice models learned by Ragain & Ugander (2016) against RUMs we learn based on a simple linear program. RUMs perform well, outperforming the MNL mixtures model of Ragain & Ugander (2016), and in some cases outperforming the non-rational choice model, as well. This suggests that, at least in some settings, our findings on expressive power of permutation mixtures may point to new algorithmic approaches to RUM discovery. The paper is structured as follows. Section 2 introduces the notation. Sections 3 and 4 give, respectively, the upper and lower bound on the bit complexity of arbitrary representations. Section 5 gives the corresponding bounds for MNL mixtures. Section 6 compares the RUM, and the mixture of MNLs, representations. Section 7 extends the results to the setting of slates of bounded size. Section 8 gives our experimental results. The Supplementary Material contains each proof missing from the main body of this paper, along with an exponential lower bound on the bit complexity of exact representations of RUMs, and comparisons of RUMs with several other choice models. |
| Researcher Affiliation | Collaboration | 1Dipartimento di Informatica, Sapienza University of Rome, Italy 2Google, Mountain View, CA, USA. |
| Pseudocode | No | No structured pseudocode or algorithm blocks are explicitly presented. |
| Open Source Code | No | No explicit statement or link is provided for open-source code for the methodology described in the paper. |
| Open Datasets | Yes | We consider the Sushi 3A dataset (Kamishima, 2003)... we consider the setting of Ragain & Ugander (2016), who present an interesting non-rational choice model that is incomparable to the class of RUMs. In this setting we are able to compare the nonrational choice models learned by Ragain & Ugander (2016) against RUMs we learn based on a simple linear program. RUMs perform well, outperforming the MNL mixtures model of Ragain & Ugander (2016), and in some cases outperforming the non-rational choice model, as well. This suggests that, at least in some settings, our findings on expressive power of permutation mixtures may point to new algorithmic approaches to RUM discovery. The paper is structured as follows. Section 2 introduces the notation. Sections 3 and 4 give, respectively, the upper and lower bound on the bit complexity of arbitrary representations. Section 5 gives the corresponding bounds for MNL mixtures. Section 6 compares the RUM, and the mixture of MNLs, representations. Section 7 extends the results to the setting of slates of bounded size. Section 8 gives our experimental results. The Supplementary Material contains each proof missing from the main body of this paper, along with an exponential lower bound on the bit complexity of exact representations of RUMs, and comparisons of RUMs with several other choice models. Choices Representation. In our second experiment, we compare the quality of the predictions given by a RUM representation with that of the PCMC model6 of Ragain & Ugander (2016; 2021), for the SFwork and the SFshop datasets (Koppelman & Bhat, 2006). |
| Dataset Splits | Yes | As in (Ragain & Ugander, 2021), for each dataset M, we split the events: a u.a.r. part M tr of the dataset, conditioned on having a fixed size (in the 5% 75% range), was used for training; a u.a.r. part M te of the dataset disjoint from M tr, conditioned on having size 25%, was used for testing. |
| Hardware Specification | Yes | We ran them on a 8-Core i9 Mac Book Pro with 64Gi B of RAM |
| Software Dependencies | No | The paper states: 'The experiments were coded in Python and used IBM cplex.' It does not provide specific version numbers for Python or IBM cplex in the text. |
| Experiment Setup | No | The paper describes how training data was split and mentions using a linear program (LP) to minimize total variation distance. However, it does not provide specific hyperparameter values (e.g., learning rate, batch size, number of epochs) or other system-level training settings for a model. |