A new algorithm for finding MAP assignments to belief networks

Solomon Eyal Shimony, Eugene CharniakUAI 1990

TL;DR

This paper introduces a novel algorithm for finding the most probable assignment of values (MAP) in belief networks. It achieves this by transforming the belief network into a weighted boolean-function directed acyclic graph (WBFDAG) and then employing a best-first search. This approach offers a more straightforward way to compute MAP assignments compared to existing methods, particularly for poly trees.

What Problem Does This Paper Address?

Belief networks, also known as Bayesian networks, are powerful tools for probabilistic reasoning. While algorithms exist for calculating posterior probabilities of nodes, finding the single most probable assignment of values to all nodes given some evidence (the MAP assignment) is a more challenging problem. Existing algorithms, like Pearl's, are described as complicated, and finding subsequent best assignments is not straightforward. This paper aims to provide a more efficient and conceptually simpler algorithm for computing MAP assignments.

Methods

The core of the paper's contribution lies in its novel transformation of a belief network into a Weighted Boolean-Function Directed Acyclic Graph (WBFDAG). This transformation involves creating new nodes and defining cost functions based on the conditional probabilities of the original belief network. Specifically:

  • Root Nodes: For each root node u in the belief network, a new node u' is created. The costs associated with u' are derived from the negative logarithm of the probabilities of u taking specific values, given its parents. The label function for u' is designed to act as an exclusive-or (XOR) gate.
  • Non-Root Nodes: For non-root nodes v with k parents, a more complex construction involves creating intermediate "cost" nodes and then a new node v' that acts as an image of v. This v' node's label function ensures that it takes on a specific value only if its parents (which are derived from the cost nodes) are set appropriately.
  • Evidence: Evidence is handled by constructing a special "sink" node s in the WBFDAG. If the evidence is a single value assignment to a node, s is the image of that node. If the evidence is more complex, s acts as an AND node, ensuring that its parents (representing the evidence) are assigned values consistent with the evidence.

Once the WBFDAG is constructed, the problem of finding the MAP assignment in the belief network is reduced to finding a minimum-cost satisfying model in the WBFDAG. This is achieved using a standard best-first search algorithm. The authors argue that this approach is more efficient than existing methods, especially for poly trees (networks without cycles).

Datasets

Not discussed in the paper. The paper focuses on the algorithmic transformation and its theoretical properties, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Belief Network to WBFDAG Transformation: The key insight is that the problem of finding a MAP assignment in a belief network can be elegantly reformulated as a minimum-cost assignment problem on a specially constructed WBFDAG. This transformation simplifies the search process.
  • Cost as Negative Log-Probability: The paper ingeniously uses the negative logarithm of probabilities as costs in the WBFDAG. This allows the minimization of costs to directly correspond to the maximization of probabilities, a fundamental principle in probabilistic reasoning.
  • Best-First Search Applicability: By transforming the problem into a WBFDAG, the authors can leverage existing efficient search algorithms like best-first search, which are well-suited for finding minimal cost solutions.
  • Poly Tree Efficiency: The algorithm's efficiency on poly trees (linear time) is a significant advantage, as poly trees are a common structure in many belief network applications.

Key Results

  • Theoretical Equivalence: The paper proves that a minimal cost satisfying model for the constructed WBFDAG induces a unique MAP assignment for the original belief network given the evidence.
  • Complexity: The WBFDAG is linear in the size of the Bayesian network. For poly trees, the best-first search runs in linear time. For general belief networks, the algorithm is exponential in the worst case but can be efficient in practice.
  • Next-Best Assignments: The best-first search approach naturally extends to enumerating successive next-best MAP assignments by continuing the search after finding the first MAP.

Limitations and Future Work

  • General Case Complexity: The authors acknowledge that the algorithm is exponential in the general case, particularly in the in-degree of nodes in the belief network.
  • Heuristic Improvement: The paper mentions that the admissible heuristic used in their implementation was "trivial," suggesting that a better heuristic could further improve performance.
  • Empirical Evaluation: While results are described as "optimistic," the paper calls for more extensive empirical data and timing tests, especially on randomly generated belief networks and for specific cases like those generated by WIMP.
  • Improved Implementation: The authors note an improved implementation that avoids explicit construction of all WBFDAG nodes, which can handle noisy ORs and ANDs more effectively. Further research into this modified algorithm is suggested.

Summary updated

BibTeX
@inproceedings{shimony1990new,
  author = {Solomon Eyal Shimony and Eugene Charniak},
  title = {{A new algorithm for finding MAP assignments to belief networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1990},
}
Figure