Ranking Distributions based on Noisy Sorting

Adil El Mesaoudi-Paul, Eyke Hüllermeier, Robert Busa-Fekete
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3472-3480, 2018.

Abstract

We propose a new statistical model for ranking data, i.e., a new family of probability distributions on permutations. Our model is inspired by the idea of a data-generating process in the form of a noisy sorting procedure, in which deterministic comparisons between pairs of items are replaced by Bernoulli trials. The probability of producing a certain ranking as a result then essentially depends on the Bernoulli parameters, which can be interpreted as pairwise preferences. We show that our model can be written in closed form if insertion or quick sort are used as sorting algorithms, and propose a maximum likelihood approach for parameter estimation. We also introduce a generalization of the model, in which the constraints on pairwise preferences are relaxed, and for which maximum likelihood estimation can be carried out based on a variation of the generalized iterative scaling algorithm. Experimentally, we show that the models perform very well in terms of goodness of fit, compared to existing models for ranking data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-mesaoudi-paul18a, title = {Ranking Distributions based on Noisy Sorting}, author = {Mesaoudi-Paul, Adil El and H{\"u}llermeier, Eyke and Busa-Fekete, Robert}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3472--3480}, 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/mesaoudi-paul18a/mesaoudi-paul18a.pdf}, url = {https://proceedings.mlr.press/v80/mesaoudi-paul18a.html}, abstract = {We propose a new statistical model for ranking data, i.e., a new family of probability distributions on permutations. Our model is inspired by the idea of a data-generating process in the form of a noisy sorting procedure, in which deterministic comparisons between pairs of items are replaced by Bernoulli trials. The probability of producing a certain ranking as a result then essentially depends on the Bernoulli parameters, which can be interpreted as pairwise preferences. We show that our model can be written in closed form if insertion or quick sort are used as sorting algorithms, and propose a maximum likelihood approach for parameter estimation. We also introduce a generalization of the model, in which the constraints on pairwise preferences are relaxed, and for which maximum likelihood estimation can be carried out based on a variation of the generalized iterative scaling algorithm. Experimentally, we show that the models perform very well in terms of goodness of fit, compared to existing models for ranking data.} }
Endnote
%0 Conference Paper %T Ranking Distributions based on Noisy Sorting %A Adil El Mesaoudi-Paul %A Eyke Hüllermeier %A Robert Busa-Fekete %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-mesaoudi-paul18a %I PMLR %P 3472--3480 %U https://proceedings.mlr.press/v80/mesaoudi-paul18a.html %V 80 %X We propose a new statistical model for ranking data, i.e., a new family of probability distributions on permutations. Our model is inspired by the idea of a data-generating process in the form of a noisy sorting procedure, in which deterministic comparisons between pairs of items are replaced by Bernoulli trials. The probability of producing a certain ranking as a result then essentially depends on the Bernoulli parameters, which can be interpreted as pairwise preferences. We show that our model can be written in closed form if insertion or quick sort are used as sorting algorithms, and propose a maximum likelihood approach for parameter estimation. We also introduce a generalization of the model, in which the constraints on pairwise preferences are relaxed, and for which maximum likelihood estimation can be carried out based on a variation of the generalized iterative scaling algorithm. Experimentally, we show that the models perform very well in terms of goodness of fit, compared to existing models for ranking data.
APA
Mesaoudi-Paul, A.E., Hüllermeier, E. & Busa-Fekete, R.. (2018). Ranking Distributions based on Noisy Sorting. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3472-3480 Available from https://proceedings.mlr.press/v80/mesaoudi-paul18a.html.

Related Material