On the Complexity of Strong and Epistemic Credal Networks

Denis D. Mauá, Cassio P. de Campos, Alessio Benavoli, Alessandro Antonucci

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Citations (Scopus)

Abstract

Credal networks are graph-based statistical models whose parameters take values on a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The result of inferences with such models depends on the irrelevance/independence concept adopted. In this paper, we study the computational complexity of inferences under the concepts of epistemic irrelevance and strong independence. We strengthen complexity results by showing that inferences with strong independence are NP-hard even in credal trees with ternary variables, which indicates that tractable algorithms, including the existing one for epistemic trees, cannot be used for strong independence. We prove that the polynomial time of inferences in credal trees under epistemic irrelevance is not likely to extend to more general models, because the problem becomes NP-hard even in simple polytrees. These results draw a definite line between networks with efficient inferences and those where inferences are hard, and close several open questions regarding the computational complexity of such models.
Original languageEnglish
Title of host publication29th Conference on Uncertainty in Artificial Intelligence (UAI)
PublisherMorgan Kaufmann
Pages391-400
Number of pages10
Publication statusPublished - 2013

Bibliographical note

(best student paper award, top 11% papers, plenary presentation, double-blind peer reviewed by >3 reviewers)

Fingerprint Dive into the research topics of 'On the Complexity of Strong and Epistemic Credal Networks'. Together they form a unique fingerprint.

Cite this