The effect of combination functions on the complexity of relational Bayesian networks

Denis Deratani Mau, Fabio Gagliardi Cozman

Resultado de la investigación: Contribución a una revistaArtículo de la conferenciarevisión exhaustiva

Resumen

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 #P-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 #P-equivalent to FPSPACE-complete to EXP-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 FEXP-complete even under a seemingly strong restriction.

Idioma originalInglés
Páginas (desde-hasta)333-344
Número de páginas12
PublicaciónJournal of Machine Learning Research
Volumen52
N.º2016
EstadoPublicada - 2016
Publicado de forma externa
Evento8th International Conference on Probabilistic Graphical Models, PGM 2016 - Lugano, Suiza
Duración: 6 sep 20169 sep 2016

Huella

Profundice en los temas de investigación de 'The effect of combination functions on the complexity of relational Bayesian networks'. En conjunto forman una huella única.

Citar esto