Bayesian inference for vertex-series-parallel partial orders

Chuxuan Jiang, Geoff K. Nicholls, Jeong Eun Lee
Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, PMLR 216:995-1004, 2023.

Abstract

Partial orders are a natural model for the social hierarchies that may constrain “queue-like” rank-order data. However, the computational cost of counting the linear extensions of a general partial order on a ground set with more than a few tens of elements is prohibitive. Vertex-series-parallel partial orders (VSPs) are a subclass of partial orders which admit rapid counting and represent the sorts of relations we expect to see in a social hierarchy. However, no Bayesian analysis of VSPs has been given to date. We construct a marginally consistent family of priors over VSPs with a parameter controlling the prior distribution over VSP depth. The prior for VSPs is given in closed form. We extend an existing observation model for queue-like rank-order data to represent noise in our data and carry out Bayesian inference on “Royal Acta” data and Formula 1 race data. Model comparison shows our model is a better fit to the data than Plackett-Luce mixtures, Mallows mixtures, and “bucket order” models and competitive with more complex models fitting general partial orders.

Cite this Paper

BibTeX
@InProceedings{pmlr-v216-jiang23b, title = {Bayesian inference for vertex-series-parallel partial orders}, author = {Jiang, Chuxuan and Nicholls, Geoff K. and Lee, Jeong Eun}, booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence}, pages = {995--1004}, year = {2023}, editor = {Evans, Robin J. and Shpitser, Ilya}, volume = {216}, series = {Proceedings of Machine Learning Research}, month = {31 Jul--04 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v216/jiang23b/jiang23b.pdf}, url = {https://proceedings.mlr.press/v216/jiang23b.html}, abstract = {Partial orders are a natural model for the social hierarchies that may constrain “queue-like” rank-order data. However, the computational cost of counting the linear extensions of a general partial order on a ground set with more than a few tens of elements is prohibitive. Vertex-series-parallel partial orders (VSPs) are a subclass of partial orders which admit rapid counting and represent the sorts of relations we expect to see in a social hierarchy. However, no Bayesian analysis of VSPs has been given to date. We construct a marginally consistent family of priors over VSPs with a parameter controlling the prior distribution over VSP depth. The prior for VSPs is given in closed form. We extend an existing observation model for queue-like rank-order data to represent noise in our data and carry out Bayesian inference on “Royal Acta” data and Formula 1 race data. Model comparison shows our model is a better fit to the data than Plackett-Luce mixtures, Mallows mixtures, and “bucket order” models and competitive with more complex models fitting general partial orders.} }
Endnote
%0 Conference Paper %T Bayesian inference for vertex-series-parallel partial orders %A Chuxuan Jiang %A Geoff K. Nicholls %A Jeong Eun Lee %B Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2023 %E Robin J. Evans %E Ilya Shpitser %F pmlr-v216-jiang23b %I PMLR %P 995--1004 %U https://proceedings.mlr.press/v216/jiang23b.html %V 216 %X Partial orders are a natural model for the social hierarchies that may constrain “queue-like” rank-order data. However, the computational cost of counting the linear extensions of a general partial order on a ground set with more than a few tens of elements is prohibitive. Vertex-series-parallel partial orders (VSPs) are a subclass of partial orders which admit rapid counting and represent the sorts of relations we expect to see in a social hierarchy. However, no Bayesian analysis of VSPs has been given to date. We construct a marginally consistent family of priors over VSPs with a parameter controlling the prior distribution over VSP depth. The prior for VSPs is given in closed form. We extend an existing observation model for queue-like rank-order data to represent noise in our data and carry out Bayesian inference on “Royal Acta” data and Formula 1 race data. Model comparison shows our model is a better fit to the data than Plackett-Luce mixtures, Mallows mixtures, and “bucket order” models and competitive with more complex models fitting general partial orders.
APA
Jiang, C., Nicholls, G.K. & Lee, J.E.. (2023). Bayesian inference for vertex-series-parallel partial orders. Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 216:995-1004 Available from https://proceedings.mlr.press/v216/jiang23b.html.

Related Material