Generalized Loopy 2U: A New Algorithm for Approximate Inference in Credal Networks

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Credal nets generalize Bayesian nets by relaxing the requirement of precision of probabilities. Credal nets are considerably more expressive than Bayesian nets, but this makes belief updating NP-hard even on polytrees. We develop a new efficient algorithm for approximate belief updating in credal nets. The algorithm is based on an important representation result we prove for general credal nets: that any credal net can be equivalently reformulated as a credal net 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 net is updated by L2U, a loopy approximate algorithm for binary credal nets. Thus, we generalize L2U to non-binary credal nets, obtaining an accurate and scalable algorithm for the general case, which is approximate only because of its loopy nature. The accuracy of the inferences is evaluated by empirical tests.
Original languageEnglish
Title of host publicationProceedings of the 4th European Workshop on Probabilistic Graphical Models
Pages17-24
Number of pages8
Publication statusPublished - 2008
Event4th European Workshop on Probabilistic Graphical Models - Hirtshals, Denmark
Duration: 17 Sep 200819 Sep 2008

Conference

Conference4th European Workshop on Probabilistic Graphical Models
CountryDenmark
CityHirtshals
Period17/09/200819/09/2008

Bibliographical note

(selected in top 15% after the conference, oral presentation, blind peer reviewed by multiple reviewers)

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