Using Tree-Decomposable Structures to Approximate Belief Networks
This work addresses the challenge of efficiently approximating belief networks for probabilistic reasoning, but it appears incremental as it builds on existing decomposition schemes and scoring rules.
The paper tackles the problem of finding an optimal approximating tree for belief networks, showing that tree-decomposable structures enhance the class of probability distributions that can support tree structures and developing greedy and exact techniques to find the optimal approximation using the logarithm scoring rule.
Tree structures have been shown to provide an efficient framework for propagating beliefs [Pearl,1986]. This paper studies the problem of finding an optimal approximating tree. The star decomposition scheme for sets of three binary variables [Lazarsfeld,1966; Pearl,1986] is shown to enhance the class of probability distributions that can support tree structures; such structures are called tree-decomposable structures. The logarithm scoring rule is found to be an appropriate optimality criterion to evaluate different tree-decomposable structures. Characteristics of such structures closest to the actual belief network are identified using the logarithm rule, and greedy and exact techniques are developed to find the optimal approximation.