Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity
Abstract
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 #\mathsf{P}, #\mathsf{NP}, and even #\mathsf{EXP}. 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.
Cite
Text
Cozman and Mauá. "Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity." Proceedings of the Eighth International Conference on Probabilistic Graphical Models, 2016.Markdown
[Cozman and Mauá. "Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity." Proceedings of the Eighth International Conference on Probabilistic Graphical Models, 2016.](https://mlanthology.org/pgm/2016/cozman2016pgm-probabilistic/)BibTeX
@inproceedings{cozman2016pgm-probabilistic,
title = {{Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity}},
author = {Cozman, Fabio Gagliardi and Mauá, Denis Deratani},
booktitle = {Proceedings of the Eighth International Conference on Probabilistic Graphical Models},
year = {2016},
pages = {110-122},
volume = {52},
url = {https://mlanthology.org/pgm/2016/cozman2016pgm-probabilistic/}
}