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

Alessandro Antonucci, Sun Yi, C.P. de Campos, Marco Zaffalon

Research output: Contribution to journalArticleAcademicpeer-review

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
Externally publishedYes

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