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 journalArticle

9 Citations (Scopus)
192 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 pages18
JournalInternational Journal of Approximate Reasoning
Volume58
Early online date04 Nov 2014
DOIs
Publication statusPublished - Mar 2015

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