Timezone: »

Learning Chordal Markov Networks via Branch and Bound
Kari Rantanen · Antti Hyttinen · Matti J√§rvisalo

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #45 #None

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.

Author Information

Kari Rantanen (University of Helsinki)
Antti Hyttinen (University of Helsinki)
Matti Järvisalo (University of Helsinki)

More from the Same Authors