TY - JOUR
T1 - The complexity of Bayesian networks specified by propositional and relational languages
AU - Cozman, Fabio G.
AU - Mauá, Denis D.
PY - 2018/9/1
Y1 - 2018/9/1
N2 - © 2018 We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.
AB - © 2018 We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85048332148&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85048332148&origin=inward
U2 - 10.1016/j.artint.2018.06.001
DO - 10.1016/j.artint.2018.06.001
M3 - Article
SN - 0004-3702
SP - 96
EP - 141
JO - Artificial Intelligence
JF - Artificial Intelligence
ER -