✦ LIBER ✦
Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks
✍ Scribed by Solomon E Shimony; Carmel Domshlak
- Book ID
- 104105283
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 249 KB
- Volume
- 151
- Category
- Article
- ISSN
- 0004-3702
No coin nor oath required. For personal study only.
✦ Synopsis
Directed-path (DP) singly-connected Bayesian networks are an interesting special case that, in particular, includes both polytrees and two-level networks. We analyze the computational complexity of these networks. The prediction problem is shown to be easy, as standard message passing can perform correct updating. However, diagnostic reasoning is hard even for DP singly-connected networks. In addition, finding the most-probable explanation (MPE) is hard, even without evidence. Finally, complexity of nearly DP singly-connected networks is analyzed.