Learning Score-Optimal Chordal Markov Networks via Branch and Bound

Show full item record



Permalink

http://urn.fi/URN:NBN:fi:hulib-201711145696
Title: Learning Score-Optimal Chordal Markov Networks via Branch and Bound
Author: Rantanen, Kari
Contributor: University of Helsinki, Faculty of Science, Department of Computer Science
Publisher: Helsingfors universitet
Date: 2017
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-201711145696
http://hdl.handle.net/10138/228846
Thesis level: master's thesis
Abstract: Graphical models are commonly used to encode conditional independence assumptions between random variables. Here we focus on undirected graphical models called chordal Markov networks. Specifically, we will consider the chordal Markov network structure learning problem (CMSL), where the aim is to find (or "learn") a graph structure that best fits the given data with respect to a given decomposable scoring function. We introduce a branch and bound search algorithm for CMSL which represents chordal Markov network structures as decomposable DAGs. We show how revisiting equivalent solution candidates can be avoided in the search by detecting symmetries among graph structures. For the symmetry breaking we apply specific rules by van Beek and Hoffman (CP 2015), and also propose a new rule that takes advantage of the special nature of decomposable DAGs. In addition, we show how we can achieve on-the-fly score pruning for CMSL. We also propose methods for obtaining strong upper bounds for CMSL that help us close branches in the search tree. We implement a dynamic programming algorithm to find the optimal Bayesian network structures and then use the scores of those graphs as upper bounds. We also show how we can relax the requirement for decomposability in decomposable DAGs in order to achieve even stronger upper bounds. Furthermore, we propose a method for obtaining an initial lower bound in CMSL by turning a Bayesian network structure into a chordal Markov network structure. Empirically we show that our approach is competitive with the recently proposed CMSL algorithms by being able to sometimes scale up to 20 variables within 24 hours with unbounded treewidth. We also report that our branch and bound requires considerably less memory than the fastest of the recently proposed algorithms for CMSL.


Files in this item

Total number of downloads: Loading...

Files Size Format View
gradu_27_9.pdf 709.9Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record