Approximate credal network updating by linear programming with applications to decision making

Alessandro Antonucci, Cassio P. de Campos, David Huber, Marco Zaffalon

Research output: Contribution to journalArticleAcademicpeer-review

28 Citations (Scopus)
1 Downloads (Pure)

Abstract

Credal nets are probabilistic graphical models which extend Bayesian nets to cope with sets of distributions. An algorithm for approximate credal network updating is presented. The problem in its general formulation is a multilinear optimization task, which can be linearized by an appropriate rule for fixing all the local models apart from those of a single variable. This simple idea can be iterated and quickly leads to accurate inferences. A transformation is also derived to reduce decision making in credal networks based on the maximality criterion to updating. The decision task is proved to have the same complexity of standard inference, being NPPP-complete for general credal nets and NP-complete for polytrees. Similar results are derived for the E-admissibility criterion. Numerical experiments confirm a good performance of the method.

Original languageEnglish
Pages (from-to)25-38
Number of pages14
JournalInternational Journal of Approximate Reasoning
Volume58
DOIs
Publication statusPublished - Mar 2015
Externally publishedYes

Keywords

  • Bayesian networks
  • Credal networks
  • Decision making
  • E-admissibility
  • Linear programming
  • Maximality

Fingerprint

Dive into the research topics of 'Approximate credal network updating by linear programming with applications to decision making'. Together they form a unique fingerprint.

Cite this