The Finite Model Theory of Bayesian Networks: Descriptive Complexity
Abstract
We adapt the theory of descriptive complexity to Bayesian networks, to quantify the expressivity of specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PP^(NP^...^NP), a result that does not seem to have equivalent in the literature.
Cite
Text
Cozman and Mauá. "The Finite Model Theory of Bayesian Networks: Descriptive Complexity." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/727Markdown
[Cozman and Mauá. "The Finite Model Theory of Bayesian Networks: Descriptive Complexity." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/cozman2018ijcai-finite/) doi:10.24963/IJCAI.2018/727BibTeX
@inproceedings{cozman2018ijcai-finite,
title = {{The Finite Model Theory of Bayesian Networks: Descriptive Complexity}},
author = {Cozman, Fábio Gagliardi and Mauá, Denis Deratani},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5229-5233},
doi = {10.24963/IJCAI.2018/727},
url = {https://mlanthology.org/ijcai/2018/cozman2018ijcai-finite/}
}