### 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 language | English |
---|---|

Pages (from-to) | 1183-1199 |

Number of pages | 17 |

Journal | International Journal of Approximate Reasoning |

Volume | 53(8) |

DOIs | |

Publication status | Published - 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

Mauá, D. D., de Campos, C. P., & Zaffalon, M. (2012). Updating Credal Networks is Approximable in Polynomial Time.

*International Journal of Approximate Reasoning*,*53(8)*, 1183-1199. https://doi.org/10.1016/j.ijar.2012.06.014