Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity

Fábio Gagliardi Cozman, Denis Deratani Mauá

AAAI 2015 pp. 3519-3525

doi:10.1609/AAAI.V29I1.9680 /aaai/2015/cozman2015aaai-bayesian/

Abstract

We examine the inferential complexity of Bayesian networks specified through logical constructs. We first consider simple propositional languages, and then move to relational languages. We examine both the combined complexity of inference (as network size and evidence size are not bounded) and the data complexity of inference (where network size is bounded); we also examine the connection to liftability through domain complexity. Combined and data complexity of several inference problems are presented, ranging from polynomial to exponential classes.

PDF AAAI Semantic Scholar

Cite

Text

Cozman and Mauá. "Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9680

Markdown

[Cozman and Mauá. "Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/cozman2015aaai-bayesian/) doi:10.1609/AAAI.V29I1.9680

BibTeX

@inproceedings{cozman2015aaai-bayesian,
  title     = {{Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity}},
  author    = {Cozman, Fábio Gagliardi and Mauá, Denis Deratani},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {3519-3525},
  doi       = {10.1609/AAAI.V29I1.9680},
  url       = {https://mlanthology.org/aaai/2015/cozman2015aaai-bayesian/}
}