Learning Chordal Markov Networks by Dynamic Programming
We present an algorithm for finding a chordal Markov network that maximizes any given decomposable scoring function. The algorithm is based on a recursive characterization of clique trees, and it runs in O(4 n ) time for n vertices. On an eight-vertex benchmark instance, our implementation turns out to be about ten million times faster than a recently proposed, constraint satisfaction based algorithm (Corander et al., NIPS 2013). Within a few hours, it is able to solve instances up to 18 vertices, and beyond if we restrict the maximum clique size. We also study the performance of a recent integer linear programming algorithm (Bartlett and Cussens, UAI 2013). Our results suggest that, unless we bound the clique sizes, currently only the dynamic programming algorithm is guaranteed to solve instances with around 15 or more vertices.
This work develops a new exact algorithm for structure learning of chordal Markov networks (MN) under decomposable score functions. The algorithm implements a dynamic programming approach by introducing recursive partition tree structures, which are junction tree equivalent structures that well suit the decomposition of the problem into smaller instances so to enable dynamic programming. The authors review the literature, prove the correctness of their algorithm and compare it against a modified version of GOBNILP, which is implements an state-of-the-art method for Bayesian network exact structure learning.The paper is well-written, relevant for NIPS and technically sound. As far as I can tell, it is also novel and presents an important contribution to the area. The only main issue I find is the lack of a proper motivation for learning _chordal_ Markov networks. I assume the restriction to chordal networks is to allow for efficient exact inference and smaller sample complexity. The author could enlighten us with a discussion on that. Below are some minor issues:page 2, lines 67: There are recent publications on learning Bayesian networks of bounded treewidth which should be added as related work:P. Parkaviainen et al. Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming. In AISTATS 2014.J. Berg et al. Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability. In AISTATS 2014.In particular, the first publication shows an integer programming formulation of the problem which could be adapted to learn chordal MNs, similarly to the way the authors adapted the work of Barlett and Cussens (probably even easier. As the implementation of the code is freely available, the authors are suggested to compare against it.)There is a similarity in learning maximum likelihood BNs of bounded treewidth to learning chordal maximum likelihood MNs of bounded treewidth. If that is the case, then algorithms for the former could be tested against the proposed method as well. It would also provide a better connection between these two tasks.page 3, lines 108-110: By assuming that the scores are given as input, you implicitly assume that w (the width of the network decomposition) is small. Hence, I see little value later on in the experiments section when w is taken to infinity; the way I see it, the current approach is designed for handling cases of "small" w (perhaps up to 30 or so). A warning note here would be helpful.same page, definition 1: it is better to give names to the conditions (1), (2) and (3), otherwise it gets confusing when following the proofs, which also contains enumerations of their own (something like RPT1, RPT2, RTP3 would do).page 5, line 245: the enumeration (0), (1) and (3) slightly confuses the reader (which expects to see a (2) somewhere). Try renumbering the conditions.page 7, line 370: better or additional references for score pruning rules areC.P. de Campos, Q. Ji: Properties of Bayesian Dirichlet Scores to Learn Bayesian Network Structures. In AAAI 2010C.P. de Campos, Q. Ji: Efficient Structure Learning of Bayesian Networks using Constraints. Journal of Machine Learning Research 12: 663-689 (2011)pages 7-8, Experiments sec.: drawing CPTs uniformly at random seems unrealistic. It would be better to draw distributions from a symmetric Dirichlet with hyper-parameter < 1 so that it gets relatively high entropy and mimics real-world distributions. As the performance of GOBNILP is strongly affected by the parameters, using unrealistic models might bias the comparison.page 9: write full name of JMLR in Ref. 13.