Fast Learning of MNL Model from General Partial Rankings with Application to Network Formation Modeling
This work addresses a long-standing technical challenge in learning MNL models from real-world partial ranking data, with applications in network formation modeling, though it is incremental as it builds on existing MNL frameworks.
The authors tackled the intractable likelihood calculation for Multinomial Logit (MNL) models with partial ranking data by developing a scalable polynomial-time approximation method, which they extended to mixture models and applied to network formation modeling, achieving more accurate parameter estimation and better data fit compared to conventional methods in experiments on synthetic and real-world data.
Multinomial Logit (MNL) is one of the most popular discrete choice models and has been widely used to model ranking data. However, there is a long-standing technical challenge of learning MNL from many real-world ranking data: exact calculation of the MNL likelihood of \emph{partial rankings} is generally intractable. In this work, we develop a scalable method for approximating the MNL likelihood of general partial rankings in polynomial time complexity. We also extend the proposed method to learn mixture of MNL. We demonstrate that the proposed methods are particularly helpful for applications to choice-based network formation modeling, where the formation of new edges in a network is viewed as individuals making choices of their friends over a candidate set. The problem of learning mixture of MNL models from partial rankings naturally arises in such applications. And the proposed methods can be used to learn MNL models from network data without the strong assumption that temporal orders of all the edge formation are available. We conduct experiments on both synthetic and real-world network data to demonstrate that the proposed methods achieve more accurate parameter estimation and better fitness of data compared to conventional methods.