Skip to yearly menu bar Skip to main content


Poster

Learning Chordal Markov Networks via Branch and Bound

Kari Rantanen · Antti Hyttinen · Matti Järvisalo

Pacific Ballroom #45

Keywords: [ Combinatorial Optimization ] [ Model Selection and Structure Learning ] [ Graphical Models ]


Abstract:

We present a new algorithmic approach for the task of finding a chordal Markov network structure that maximizes a given scoring function. The algorithm is based on branch and bound and integrates dynamic programming for both domain pruning and for obtaining strong bounds for search-space pruning. Empirically, we show that the approach dominates in terms of running times a recent integer programming approach (and thereby also a recent constraint optimization approach) for the problem. Furthermore, our algorithm scales at times further with respect to the number of variables than a state-of-the-art dynamic programming algorithm for the problem, with the potential of reaching 20 variables and at the same time circumventing the tight exponential lower bounds on memory consumption of the pure dynamic programming approach.

Live content is unavailable. Log in and register to view live content