Timezone: »

 
Poster
Learning Chordal Markov Networks by Dynamic Programming
Kustaa Kangas · Mikko Koivisto · Teppo Niinimäki

Thu Dec 11 11:00 AM -- 03:00 PM (PST) @ Level 2, room 210D #None

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.

Author Information

Kustaa Kangas (University of Helsinki)
Mikko Koivisto (Helsinki Institute for Information Technology)
Teppo Niinimäki (Aalto University)