Learning Chordal Markov Networks by Constraint Satisfaction

Title

Learning Chordal Markov Networks by Constraint Satisfaction

 

Abstract

We have investigated reducing the structure learning problem for Markov networks to various constraint satisfaction problems, and shown the resulting method to be competitive with an earlier stochastic local search method in finding good networks and also being capable of showing the networks to be optimal with respect to a quality measure (when the networks are small).

To achieve efficient encodings, we develop a novel characterization of Markov network structure using a balancing condition on the separators between cliques forming the network. The resulting translations into propositional satisfiability and its extensions such as maximum satisfiability, satisfiability modulo theories, and answer set programming, enable us to use existing solver technology for these formalisms.

 

Authors

Jukka Corander (University of Helsinki), Tomi Janhunen (Aalto University), Jussi Rintanen (Aalto University), Henrik Nyman (Åbo Akademi University), Johan Pensar (Åbo Akademi University)

 

About the presenter

Tomi is a Docent in Information and Computer Science at Aalto University.  His research interests include knowledge representation, automated reasoning and answer set programming.  He is a senior member of the Computational Logic Group at Aalto.