Advanced search
Start date
Betweenand


The Finite Model Theory of Bayesian Networks: Descriptive Complexity

Author(s):
Cozman, Fabio Gagliardi ; Maua, Denis Deratani ; Lang, J
Total Authors: 3
Document type: Journal article
Source: PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE; v. N/A, p. 5-pg., 2018-01-01.
Abstract

We adapt the theory of descriptive complexity to encompass Bayesian networks, so as to quantify the expressivity of Bayesian network specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ firstorder quantification capture the complexity class P P; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PPNP...NP, a result that does not seem to have equivalent in the literature.(1) (AU)

FAPESP's process: 15/21880-4 - PROVERBS -- PRobabilistic OVERconstrained Boolean Systems: reasoning tools and applications
Grantee:Marcelo Finger
Support Opportunities: Regular Research Grants
FAPESP's process: 16/18841-0 - Inference and learning algorithms for probabilistic logic programming
Grantee:Fabio Gagliardi Cozman
Support Opportunities: Research Grants - Research Partnership for Technological Innovation - PITE
FAPESP's process: 16/01055-1 - Learning of Tractable Probabilistic Models with Application to Multilabel Classification
Grantee:Denis Deratani Mauá
Support Opportunities: Regular Research Grants