Browsing by Author "Rantanen, Kari"

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.