Generalized loopy 2U: A new algorithm for approximate inference in credal networks

A. Antonucci, Sun Yi, C. P. de Campos, M. Zaffalon

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

Credal networks generalize Bayesian networks by relaxing the requirement of precision of probabilities. Credal networks are considerably more expressive than Bayesian networks, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal networks. The algorithm is based on an important representation result we prove for general credal networks: that any credal network can be equivalently reformulated as a credal network with binary variables; moreover, the transformation, which is considerably more complex than in the Bayesian case, can be implemented in polynomial time. The equivalent binary credal network is then updated by L2U, a loopy approximate algorithm for binary credal networks. Overall, we generalize L2U to non-binary credal networks, obtaining a scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences with respect to other state-of-the-art algorithms is evaluated by extensive numerical tests.
Original languageEnglish
Pages (from-to)474-484
Number of pages11
JournalInternational Journal of Approximate Reasoning
Volume51
Issue number5
DOIs
Publication statusPublished - 2010

Keywords

  • Loopy belief propagation

Fingerprint

Dive into the research topics of 'Generalized loopy 2U: A new algorithm for approximate inference in credal networks'. Together they form a unique fingerprint.

Cite this