TY - JOUR
T1 - The effect of combination functions on the complexity of relational Bayesian networks
AU - Mauá, Denis Deratani
AU - Cozman, Fabio Gagliardi
PY - 2017/6/1
Y1 - 2017/6/1
N2 - © 2017 Elsevier Inc. We study the complexity of inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is PP-complete, displaying the same complexity as standard Bayesian networks (this is so even when the domain is succinctly specified in binary notation). Using only maximization as combination function, we obtain inferential complexity that ranges from PP-complete to PSPACE-complete to PEXP-complete. And by combining mean and threshold combination functions, we obtain complexity classes in all levels of the counting hierarchy. We also investigate the use of arbitrary combination functions and obtain that inference is EXP-complete even under a seemingly strong restriction. Finally, we examine the query complexity of Relational Bayesian Networks (i.e., when the relational model is fixed), and we obtain that inference is complete for PP.
AB - © 2017 Elsevier Inc. We study the complexity of inference with Relational Bayesian Networks as parameterized by their probability formulas. We show that without combination functions, inference is PP-complete, displaying the same complexity as standard Bayesian networks (this is so even when the domain is succinctly specified in binary notation). Using only maximization as combination function, we obtain inferential complexity that ranges from PP-complete to PSPACE-complete to PEXP-complete. And by combining mean and threshold combination functions, we obtain complexity classes in all levels of the counting hierarchy. We also investigate the use of arbitrary combination functions and obtain that inference is EXP-complete even under a seemingly strong restriction. Finally, we examine the query complexity of Relational Bayesian Networks (i.e., when the relational model is fixed), and we obtain that inference is complete for PP.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85017457991&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85017457991&origin=inward
U2 - 10.1016/j.ijar.2017.03.014
DO - 10.1016/j.ijar.2017.03.014
M3 - Article
SP - 178
EP - 195
JO - International Journal of Approximate Reasoning
JF - International Journal of Approximate Reasoning
SN - 0888-613X
ER -