Updating Credal Networks is Approximable in Polynomial Time

D. D. Mauá, C. P. de Campos, M. Zaffalon

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

Credal networks relax the precise probability requirement of Bayesian networks, enabling a richer representation of uncertainty in the form of closed convex sets of probability measures. The increase in expressiveness comes at the expense of higher computational costs. In this paper, we present a new variable elimination algorithm for exactly computing posterior inferences in extensively specified credal networks, which is empirically shown to outperform a state-of-the-art algorithm. The algorithm is then turned into a provably good approximation scheme, that is, a procedure that for any input is guaranteed to return a solution not worse than the optimum by a given factor. Remarkably, we show that when the networks have bounded treewidth and bounded number of states per variable the approximation algorithm runs in time polynomial in the input size and in the inverse of the error factor, thus being the first known fully polynomial-time approximation scheme for inference in credal networks.
Original languageEnglish
Pages (from-to)1183-1199
Number of pages17
JournalInternational Journal of Approximate Reasoning
Volume53(8)
DOIs
Publication statusPublished - 2012

Keywords

  • Probabilistic graphical models, credal networks, approximation scheme, valuation algebra

Fingerprint Dive into the research topics of 'Updating Credal Networks is Approximable in Polynomial Time'. Together they form a unique fingerprint.

  • Cite this