Best-First AND/OR Search for Most Probable Explanations
This work addresses computational efficiency for probabilistic inference in Bayesian networks, representing an incremental improvement over existing methods.
The paper tackled the Most Probable Explanation task in Bayesian networks by evaluating best-first search over AND/OR search spaces, demonstrating its empirical superiority over depth-first approaches on various networks.
The paper evaluates the power of best-first search over AND/OR search spaces for solving the Most Probable Explanation (MPE) task in Bayesian networks. The main virtue of the AND/OR representation of the search space is its sensitivity to the structure of the problem, which can translate into significant time savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-first strategies are known to be superior to depth-first when memory is utilized, exploring the best-first control strategy is called for. The main contribution of this paper is in showing that a recent extension of AND/OR search algorithms from depth-first Branch-and-Bound to best-first is indeed very effective for computing the MPE in Bayesian networks. We demonstrate empirically the superiority of the best-first search approach on various probabilistic networks.