Fast Algorithm for Generalized Multinomial Models with Ranking Data
Jiaqi Gu · Guosheng Yin

Thu Jun 13th 11:35 -- 11:40 AM @ Room 201

We develop a framework of the generalized multinomial model, which includes both the popular Plackett--Luce model and Bradley--Terry model as special cases. We theoretically prove that the maximum likelihood estimator (MLE) under the generalized multinomial model corresponds to the stationary distribution of an inhomogeneous Markov chain uniquely. Based on this Markov chain, we propose an iterative algorithm that is easy to implement and interpret and certain to converge. Numerical experiments on synthetic data and real data demonstrate the advantages of our Markov chain based algorithm over existing ones that it converges to the MLE with fewer iterations and faster convergence rate. The new algorithm is readily applicable for problems such as page ranking, sports ranking data.

Author Information

Jiaqi Gu (The University of Hong Kong)
Guosheng Yin (University of Hong Kong)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors