Back to overview

Updating credal networks is approximable in polynomial time

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Mauá D.D., de Campos C.P., Zaffalon M.,
Project Multi Model Inference for dealing with uncertainty in environmental models
Show all

Original article (peer-reviewed)

Journal International Journal of Approximate Reasoning
Volume (Issue) 53(8)
Page(s) 1183 - 1199
Title of proceedings International Journal of Approximate Reasoning
DOI 10.1016/j.ijar.2012.06.014


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.