A New Algorithm for Finding MAP Assignments to Belief Networks
This addresses computational efficiency in probabilistic inference for AI, but it is incremental as it builds on existing belief network methods.
The paper tackles the problem of finding maximum a-posteriori (MAP) assignments in belief networks by compiling them into boolean networks and using best-first search, achieving exponential complexity in general but linear complexity for polytrees.
We present a new algorithm for finding maximum a-posterior) (MAP) assignments of values to belief networks. The belief network is compiled into a network consisting only of nodes with boolean (i.e. only 0 or 1) conditional probabilities. The MAP assignment is then found using a best-first search on the resulting network. We argue that, as one would anticipate, the algorithm is exponential for the general case, but only linear in the size of the network for poly trees.