Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Probabilistic Inference in Credal Networks: New Complexity Results

Texto completo
Autor(es):
Maua, Denis Deratani [1] ; de Campos, Cassio P. [2] ; Benavoli, Alessio [2] ; Antonucci, Alessandro [2]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Escola Politecn, BR-05508010 Sao Paulo - Brazil
[2] Ist Dalle Molle Studi Intelligenza Artificiale, CH-6928 Manno - Switzerland
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH; v. 50, p. 603-637, 2014.
Citações Web of Science: 11
Resumo

Credal networks are graph-based statistical models whose parameters take values in a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The computational complexity of inferences on such models depends on the irrelevance/independence concept adopted. In this paper, we study inferential complexity under the concepts of epistemic irrelevance and strong independence. We show that inferences under strong independence are NP-hard even in trees with binary variables except for a single ternary one. We prove that under epistemic irrelevance the polynomial-time complexity of inferences in credal trees is not likely to extend to more general models (e.g., singly connected topologies). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding their computational complexity. We show that these results remain valid even if we disallow the use of zero probabilities. We also show that the computation of bounds on the probability of the future state in a hidden Markov model is the same whether we assume epistemic irrelevance or strong independence, and we prove a similar result for inference in naive Bayes structures. These inferential equivalences are important for practitioners, as hidden Markov models and naive Bayes structures are used in real applications of imprecise probability. (AU)

Processo FAPESP: 13/23197-4 - Algoritmos eficientes para tomada de decisão sob incerteza baseada em grafos
Beneficiário:Denis Deratani Mauá
Linha de fomento: Bolsas no Brasil - Pós-Doutorado