Fast and Stable Maximum Likelihood Estimation for Incomplete Multinomial Models

Chenyang Zhang, Guosheng Yin
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:7463-7471, 2019.

Abstract

We propose a fixed-point iteration approach to the maximum likelihood estimation for the incomplete multinomial model, which provides a unified framework for ranking data analysis. Incomplete observations typically fall in a subset of categories, and thus cannot be distinguished as belonging to a unique category. We develop a minorization–maximization (MM) type of algorithm, which requires relatively fewer iterations and shorter time to achieve convergence. Under such a general framework, incomplete multinomial models can be reformulated to include several well-known ranking models as special cases, such as the Bradley–Terry, Plackett–Luce models and their variants. The simple form of iteratively updating equations in our algorithm involves only basic matrix operations, which makes it efficient and easy to implement with large data. Experimental results show that our algorithm runs faster than existing methods on synthetic data and real data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-zhang19o, title = {Fast and Stable Maximum Likelihood Estimation for Incomplete Multinomial Models}, author = {Zhang, Chenyang and Yin, Guosheng}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {7463--7471}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/zhang19o/zhang19o.pdf}, url = {https://proceedings.mlr.press/v97/zhang19o.html}, abstract = {We propose a fixed-point iteration approach to the maximum likelihood estimation for the incomplete multinomial model, which provides a unified framework for ranking data analysis. Incomplete observations typically fall in a subset of categories, and thus cannot be distinguished as belonging to a unique category. We develop a minorization–maximization (MM) type of algorithm, which requires relatively fewer iterations and shorter time to achieve convergence. Under such a general framework, incomplete multinomial models can be reformulated to include several well-known ranking models as special cases, such as the Bradley–Terry, Plackett–Luce models and their variants. The simple form of iteratively updating equations in our algorithm involves only basic matrix operations, which makes it efficient and easy to implement with large data. Experimental results show that our algorithm runs faster than existing methods on synthetic data and real data.} }
Endnote
%0 Conference Paper %T Fast and Stable Maximum Likelihood Estimation for Incomplete Multinomial Models %A Chenyang Zhang %A Guosheng Yin %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-zhang19o %I PMLR %P 7463--7471 %U https://proceedings.mlr.press/v97/zhang19o.html %V 97 %X We propose a fixed-point iteration approach to the maximum likelihood estimation for the incomplete multinomial model, which provides a unified framework for ranking data analysis. Incomplete observations typically fall in a subset of categories, and thus cannot be distinguished as belonging to a unique category. We develop a minorization–maximization (MM) type of algorithm, which requires relatively fewer iterations and shorter time to achieve convergence. Under such a general framework, incomplete multinomial models can be reformulated to include several well-known ranking models as special cases, such as the Bradley–Terry, Plackett–Luce models and their variants. The simple form of iteratively updating equations in our algorithm involves only basic matrix operations, which makes it efficient and easy to implement with large data. Experimental results show that our algorithm runs faster than existing methods on synthetic data and real data.
APA
Zhang, C. & Yin, G.. (2019). Fast and Stable Maximum Likelihood Estimation for Incomplete Multinomial Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:7463-7471 Available from https://proceedings.mlr.press/v97/zhang19o.html.

Related Material