Probabilistic inference in credal networks: New complexity results

Denis Deratani Mauá, Cassio Polpo de Campos, Alessio Benavoli, Alessandro Antonucci

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)603-637
Number of pages35
JournalJournal of Artificial Intelligence Research
Volume50
DOIs
Publication statusPublished - Jul 2014
Externally publishedYes

Fingerprint

Hidden Markov models
Computational complexity
Bayesian networks
Topology
Polynomials
Statistical Models

Cite this

Mauá, Denis Deratani ; de Campos, Cassio Polpo ; Benavoli, Alessio ; Antonucci, Alessandro. / Probabilistic inference in credal networks : New complexity results. In: Journal of Artificial Intelligence Research. 2014 ; Vol. 50. pp. 603-637.
@article{9a2db7296a2d407585623f2d19880fb2,
title = "Probabilistic inference in credal networks: New complexity results",
abstract = "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.",
author = "Mau{\'a}, {Denis Deratani} and {de Campos}, {Cassio Polpo} and Alessio Benavoli and Alessandro Antonucci",
year = "2014",
month = "7",
doi = "10.1613/jair.4355",
language = "English",
volume = "50",
pages = "603--637",
journal = "Journal of Artificial Intelligence Research",
issn = "1076-9757",
publisher = "Morgan Kaufmann Publishers, Inc.",

}

Probabilistic inference in credal networks : New complexity results. / Mauá, Denis Deratani; de Campos, Cassio Polpo; Benavoli, Alessio; Antonucci, Alessandro.

In: Journal of Artificial Intelligence Research, Vol. 50, 07.2014, p. 603-637.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Probabilistic inference in credal networks

T2 - New complexity results

AU - Mauá, Denis Deratani

AU - de Campos, Cassio Polpo

AU - Benavoli, Alessio

AU - Antonucci, Alessandro

PY - 2014/7

Y1 - 2014/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84907362949&partnerID=8YFLogxK

U2 - 10.1613/jair.4355

DO - 10.1613/jair.4355

M3 - Article

VL - 50

SP - 603

EP - 637

JO - Journal of Artificial Intelligence Research

JF - Journal of Artificial Intelligence Research

SN - 1076-9757

ER -