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.
|Title of host publication||Proceedings of the 4th European Workshop on Probabilistic Graphical Models|
|Number of pages||8|
|Publication status||Published - 2008|
|Event||4th European Workshop on Probabilistic Graphical Models - Hirtshals, Denmark|
Duration: 17 Sep 2008 → 19 Sep 2008
|Conference||4th European Workshop on Probabilistic Graphical Models|
|Period||17/09/2008 → 19/09/2008|