The complexity of Bayesian networks specified by propositional and relational languages

DOI10.1016/J.ARTINT.2018.06.001zbMATH Open1451.68257arXiv1612.01120OpenAlexW2560444858WikidataQ62046506 ScholiaQ62046506MaRDI QIDQ1711881

Fabio G. Cozman, D. D. Maua

Publication date: 18 January 2019

Published in: Artificial Intelligence (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1612.01120

zbMATH Keywords

Bayesian networkscomplexity theoryrelational logicplate modelsprobabilistic relational models

Mathematics Subject Classification ID

Probabilistic graphical models (62H22) Database theory (68P15) Logic in artificial intelligence (68T27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• MEBN: a language for first-order Bayesian knowledge bases
• A differential approach to inference in Bayesian networks
• 10.1162/jmlr.2003.3.4-5.993
• The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks
• Modeling and Reasoning with Bayesian Networks
• The DL-Lite Family and Relations
• The complexity of computing the permanent
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• Complexity classes defined by counting quantifiers
• Elements of finite model theory.
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• On probabilistic inference by weighted model counting
• Subtractive reductions and complete problems for counting complexity classes
• On the hardness of approximate reasoning
• The independent choice logic for modelling multiple agents under uncertainty
• Computational Complexity of Probabilistic Turing Machines
• The complexity of combinatorial problems with succinct input representation
• A note on succinct representations of graphs
• The complexity of counting in sparse, regular, and planar graphs
• PP is as Hard as the Polynomial-Time Hierarchy
• Probabilistic Horn abduction and Bayesian networks
• Holographic reduction, interpolation and hardness
• The Independent Choice Logic and Beyond
• Probabilistic Databases
• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• Logical and Relational Learning
• Managing and mining uncertain data
• The Parameterized Complexity of Counting Problems
• The complexity of weighted and unweighted \(\#\)CSP
• PRL: a probabilistic relational language
• Inductive Logic Programming
• Algorithmic Learning Theory
• Complexity results for classes of quantificational formulas
• A complexity theory for feasible closure properties
• Bayesian Networks
• Asymptotic Conditional Probabilities: The Unary Case
• Negative probabilities in probabilistic logic programs
• Answering queries from context-sensitive probabilistic knowledge bases
• The dichotomy of probabilistic inference for unions of conjunctive queries
• A Simple FPTAS for Counting Edge Covers
• Polynomial Space Counting Problems
• The complexity of problems for quantified constraints
• Complexity of DNF minimization and isomorphism testing for monotone formulas
• Phase transitions of PP-complete satisfiability problems
• Soft computing in ontologies and semantic web.
• The Bayesian Description Logic ${\mathcal{BEL}}$
• Complex probabilistic modeling with recursive relational Bayesian networks
• The effect of combination functions on the complexity of relational Bayesian networks
• FPTAS for Counting Weighted Edge Covers
• Lower complexity bounds for lifted inference
• On the Semantics and Complexity of Probabilistic Logic Programs
• Theory and Applications of Models of Computation

Cited In (5)

• The generalised distribution semantics and projective families of distributions
• Some thoughts on knowledge-enhanced machine learning
• The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
• A structured view on weighted counting with relations to counting, quantum computation and applications
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws

Uses Software

• MEBN
• BUGS
• IBAL
• MayBMS
• KnowRob
• PR-OWL
• BLOG
• BayesOWL
• Trio

This page was built for publication: The complexity of Bayesian networks specified by propositional and relational languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711881)