### Denis Mauá, Cassio Campos, Marco Zaffalon

## A Fully Polynomial Time Approximation Scheme for Updating Credal Networks of Bounded Treewidth and Number of Variable States

### Abstract

Credal networks lift the precise probability assumption 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 algorithm which is an
extension of the well-known variable elimination algorithm for
computing posterior inferences in extensively specified credal
networks. The algorithm efficiency is empirically shown to
outperform a state-of-the-art algorithm. We then provide the first
fully polynomial time approximation scheme for inference in credal
networks with bounded treewidth and number of states per variable.

### Keywords

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

### Download area

The paper is available in the following formats:

Plenary talk:
file

Poster:
file

### Authors’ addresses

**Denis Mauá**

Galleria 2, CH-6928 Manno.

**Cassio Campos**

IDSIA

Galleria 2

6928 Manno-Lugano

Switzerland

**Marco Zaffalon**

Galleria 2

CH-6928 Manno

Switzerland

### E-mail addresses