The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages

Autor(es)

Maua, Denis D. ; de Campos, Cassio P. ; Cozman, Fabio G. ; Yang, Q ; Wooldridge, M

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI); v. N/A, p. 7-pg., 2015-01-01.

Resumo

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as context-sensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone. (AU)

• Processo FAPESP: 13/23197-4 - Algoritmos Eficientes para Tomada de Decisão sob Incerteza Baseada em Grafos
• Beneficiário: Denis Deratani Mauá
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado