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 proceedingChapterAcademicpeer-review

10 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 ternary variables. 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 networks). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding computational complexity.

Original languageEnglish
Title of host publication29th Conference on Uncertainty in Artificial Intelligence (UAI)
PublisherMorgan Kaufmann Publishers, Inc.
Pages391-400
Number of pages10
Publication statusPublished - 28 Nov 2013
Externally publishedYes
Event29th Conference on Uncertainty in Artificial Intelligence, UAI 2013 - Bellevue, WA, United States
Duration: 11 Jul 201315 Jul 2013

Conference

Conference29th Conference on Uncertainty in Artificial Intelligence, UAI 2013
Country/TerritoryUnited States
CityBellevue, WA
Period11/07/1315/07/13

Bibliographical note

(best student paper award, 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