Optimal sub-graphical models
Mukund Narasimhan, Jeff Bilmes · 2004
Abstract We investigate the problem of reducing the complexity of a graphicalmodel ( G, PG) by finding a subgraph H of G, chosen from a class ofsubgraphs H, such that H is optimal with respect to KL-divergence. Wedo this by first defining a decomposition tree representation for G, whichis closely related to the junction-tree representation for G. We then givean algorithm which uses this representation to compute the optimal H 2H. Gavril [2] and Tarjan [3] have used graph separation properties to solve several combinatorial optimization problems when the size of theminimal separators in the graph is bounded. We present an extension of this technique which applies to some important choices of H even whenthe size of the minimal separators of G are arbitrarily large. In particular,this applies to problems such as finding an optimal subgraphical model over a (k- 1)-tree of a graphical model over a k-tree (for arbitrary k)and selecting an optimal subgraphical model with (a constant)