The Effect of Combination Functions on the Complexity of Relational Bayesian Networks

Denis Deratani Mauá, Fabio Gagliardi Cozman
Proceedings of the Eighth International Conference on Probabilistic Graphical Models, PMLR 52:333-344, 2016.

Abstract

We study the complexity of marginal inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is #\sc\MakeLowercaseP-equivalent, displaying the same complexity as standard Bayesian networks (this is so even when relations have unbounded arity and when the domain is succinctly specified in binary notation). By allowing increasingly more expressive probability formulas using only maximization as combination, we obtain inferential complexity that ranges from #\sc\MakeLowercasep-equivalent to \sc\MakeLowercasefpspace-complete to \sc\MakeLowercaseexp-hard. In fact, by suitable restrictions to the number of nestings of combination functions, we obtain complexity classes in all levels of the counting hierarchy. Finally, we investigate the use of arbitrary combination functions and obtain that inference is \sc\MakeLowercasefexp-complete even under a seemingly strong restriction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v52-maua16, title = {The Effect of Combination Functions on the Complexity of Relational {B}ayesian Networks}, author = {Mauá, Denis Deratani and Cozman, Fabio Gagliardi}, booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models}, pages = {333--344}, year = {2016}, editor = {Antonucci, Alessandro and Corani, Giorgio and Campos}, Cassio Polpo}, volume = {52}, series = {Proceedings of Machine Learning Research}, address = {Lugano, Switzerland}, month = {06--09 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v52/maua16.pdf}, url = {https://proceedings.mlr.press/v52/maua16.html}, abstract = {We study the complexity of marginal inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is #\sc\MakeLowercaseP-equivalent, displaying the same complexity as standard Bayesian networks (this is so even when relations have unbounded arity and when the domain is succinctly specified in binary notation). By allowing increasingly more expressive probability formulas using only maximization as combination, we obtain inferential complexity that ranges from #\sc\MakeLowercasep-equivalent to \sc\MakeLowercasefpspace-complete to \sc\MakeLowercaseexp-hard. In fact, by suitable restrictions to the number of nestings of combination functions, we obtain complexity classes in all levels of the counting hierarchy. Finally, we investigate the use of arbitrary combination functions and obtain that inference is \sc\MakeLowercasefexp-complete even under a seemingly strong restriction.} }
Endnote
%0 Conference Paper %T The Effect of Combination Functions on the Complexity of Relational Bayesian Networks %A Denis Deratani Mauá %A Fabio Gagliardi Cozman %B Proceedings of the Eighth International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2016 %E Alessandro Antonucci %E Giorgio Corani %E Cassio Polpo Campos} %F pmlr-v52-maua16 %I PMLR %P 333--344 %U https://proceedings.mlr.press/v52/maua16.html %V 52 %X We study the complexity of marginal inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is #\sc\MakeLowercaseP-equivalent, displaying the same complexity as standard Bayesian networks (this is so even when relations have unbounded arity and when the domain is succinctly specified in binary notation). By allowing increasingly more expressive probability formulas using only maximization as combination, we obtain inferential complexity that ranges from #\sc\MakeLowercasep-equivalent to \sc\MakeLowercasefpspace-complete to \sc\MakeLowercaseexp-hard. In fact, by suitable restrictions to the number of nestings of combination functions, we obtain complexity classes in all levels of the counting hierarchy. Finally, we investigate the use of arbitrary combination functions and obtain that inference is \sc\MakeLowercasefexp-complete even under a seemingly strong restriction.
RIS
TY - CPAPER TI - The Effect of Combination Functions on the Complexity of Relational Bayesian Networks AU - Denis Deratani Mauá AU - Fabio Gagliardi Cozman BT - Proceedings of the Eighth International Conference on Probabilistic Graphical Models DA - 2016/08/15 ED - Alessandro Antonucci ED - Giorgio Corani ED - Cassio Polpo Campos} ID - pmlr-v52-maua16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 52 SP - 333 EP - 344 L1 - http://proceedings.mlr.press/v52/maua16.pdf UR - https://proceedings.mlr.press/v52/maua16.html AB - We study the complexity of marginal inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is #\sc\MakeLowercaseP-equivalent, displaying the same complexity as standard Bayesian networks (this is so even when relations have unbounded arity and when the domain is succinctly specified in binary notation). By allowing increasingly more expressive probability formulas using only maximization as combination, we obtain inferential complexity that ranges from #\sc\MakeLowercasep-equivalent to \sc\MakeLowercasefpspace-complete to \sc\MakeLowercaseexp-hard. In fact, by suitable restrictions to the number of nestings of combination functions, we obtain complexity classes in all levels of the counting hierarchy. Finally, we investigate the use of arbitrary combination functions and obtain that inference is \sc\MakeLowercasefexp-complete even under a seemingly strong restriction. ER -
APA
Mauá, D.D. & Cozman, F.G.. (2016). The Effect of Combination Functions on the Complexity of Relational Bayesian Networks. Proceedings of the Eighth International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 52:333-344 Available from https://proceedings.mlr.press/v52/maua16.html.

Related Material