Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity


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


We look at probabilistic logic programs as a specification language for probabilistic models, and study their interpretation and complexity. Acyclic programs specify Bayesian networks, and, depending on constraints on logical atoms, their inferential complexity reaches complexity classes #\mathsfP, #\mathsfNP, and even #\mathsfEXP. We also investigate (cyclic) stratified probabilistic logic programs, showing that they have the same complexity as acyclic probabilistic logic programs, and that they can be depicted using chain graphs.

Related Material