The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
This work addresses the complexity challenges in probabilistic inference for AI systems using logical specifications, which is incremental as it builds on existing frameworks to provide detailed complexity classifications.
The paper investigates the computational complexity of inference in Bayesian networks expressed through logical languages, ranging from propositional fragments to first-order logic, covering models like plate and probabilistic relational models. It analyzes complexity across different input scenarios (inferential, query/data, domain) and finds results spanning from polynomial to exponential classes.
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.