The Finite Model Theory of Bayesian Networks: Descriptive Complexity

Autor(es)

Cozman, Fabio Gagliardi ; Maua, Denis Deratani ; Lang, J

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE; v. N/A, p. 5-pg., 2018-01-01.

Resumo

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)

• Processo FAPESP: 15/21880-4 - PROVERBS -- Sistemas Booleanos Probabilísticos Super-restritos: ferramentas de raciocínio e aplicações
• Beneficiário: Marcelo Finger
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 16/18841-0 - Algoritmos para inferência e aprendizado de programas lógicos probabilísticos
• Beneficiário: Fabio Gagliardi Cozman
• Modalidade de apoio: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
• Processo FAPESP: 16/01055-1 - Aprendizagem de Modelos Probabilísticos Tratáveis e seu Uso na Classificação Multirrótulo
• Beneficiário: Denis Deratani Mauá
• Modalidade de apoio: Auxílio à Pesquisa - Regular