A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states

Denis D. Maúa, Cassio P. de Campos, Marco Zaffalon

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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 wellknown 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.

Original languageEnglish
Title of host publicationISIPTA 2011 - Proceedings of the 7th International Symposium on Imprecise Probability
Subtitle of host publicationTheories and Applications
Pages277-286
Number of pages10
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011 - Innsbruck, Austria
Duration: 25 Jul 201128 Jul 2011

Conference

Conference7th International Symposium on Imprecise Probability: Theories and Applications, ISIPTA 2011
CountryAustria
CityInnsbruck
Period25/07/1128/07/11

Keywords

  • Approximation scheme
  • Credal networks
  • Probabilistic graphical models
  • Valuation algebra

Fingerprint

Dive into the research topics of 'A fully polynomial time approximation scheme for updating credal networks of bounded treewidth and number of variable states'. Together they form a unique fingerprint.

Cite this