Timezone: »

Learning Chordal Markov Networks by Constraint Satisfaction
Jukka Corander · Tomi Janhunen · Jussi Rintanen · Henrik Nyman · Johan Pensar

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor #None

We investigate the problem of learning the structure of a Markov network from data. It is shown that the structure of such networks can be described in terms of constraints which enables the use of existing solver technology with optimization capabilities to compute optimal networks starting from initial scores computed from the data. 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 prove the optimality of networks which have been previously found by stochastic search.

Author Information

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