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:

• Gzipped pdf file
• pdf file

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

Denis Mauá		denis@idsia.ch
Cassio Campos		cassio@idsia.ch
Marco Zaffalon		zaffalon@idsia.ch