Optimality Issues in Constructing a Markov Tree from Graphical Models
Russell G. Almond, Augustine Kong · 2006
Several recent papers have described probability models which used graph and hypergraphs to represent relationships among the variables. Two related computing algorithms are commonly used to manipulate such models: the peeling algorithm which eliminates variables one at a time to find the marginal distribution of a single variable, and the fusion and propagation algorithm which simultaneously solves for many marginal distributions by passing messages in a Tree of Cliques whose nodes correspond to subsets of variables. The peeling algorithm requires an elimination order. As demonstrated in this paper, the elimination order can in turn be used to construct a Tree of Cliques for propagation and fusion. This paper addresses three computational issues: 1) The choice of elimination order determines the size of the largest node of the Tree of Cliques, which dominates the computational cost for the probability model using either peeling or fusion and propagation. We review heuristics for choosing an elimination order. (2) Inserting intersection nodes into the tree of cliques produces a junction tree which has a lower computational cost. We present an algorithm which produces a junction trees with a high computational efficiency. (3) Augmenting the tree of cliques with additional nodes can lead to a new tree structure which more clearly expresses the relationship between the original graphical model and the tree model.