Generalized loopy 2U: A new algorithm for approximate inference in credal networks |
| |
Authors: | Alessandro Antonucci Yi Sun Marco Zaffalon |
| |
Affiliation: | IDSIA, Istituto Dalle Molle di Studi sull’Intelligenza Artificiale, Galleria 2, CH-6928 Manno (Lugano), Switzerland |
| |
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. |
| |
Keywords: | Credal networks Credal sets Inference algorithms 2U Imprecise probability Bayesian networks Loopy belief propagation |
本文献已被 ScienceDirect 等数据库收录! |
|