Learning discrete decomposable graphical models via constraint optimization

Statistical model learning problems are traditionally solved using either heuristic greedy optimization or stochastic simulation, such as Markov chain Monte Carlo or simulated annealing. Recently, there has been an increasing interest in the use of combinatorial search methods, including those based on computational logic. Some of these methods are particularly attractive since they can also be successful in proving the global optimality of solutions, in contrast to stochastic algorithms that only guarantee optimality at the limit. Here we improve and generalize a recently introduced constraint-based method for learning undirected graphical models. The new method combines perfect elimination orderings with various strategies for solution pruning and offers a dramatic improvement both in terms of time and memory complexity. We also show that the method is capable of efficiently handling a more general class of models, called stratified/labeled graphical models, which have an astronomically larger model space.

Keywords

Answer set programming, Constraint programming, Graphical models, MAXSAT, Satisfiability, Structure learning

DOI

10.1007/s11222-015-9611-4

Citation

Janhunen, T, Gebser, M, Rintanen, J, Nyman, H, Pensar, J & Corander, J 2017, ' Learning discrete decomposable graphical models via constraint optimization ', STATISTICS AND COMPUTING, vol. 27, no. 1, pp. 115-130 . https://doi.org/10.1007/s11222-015-9611-4

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201812106381

Collections

[article-cris] Perustieteiden korkeakoulu / SCI

Show all metadata

Learning discrete decomposable graphical models via constraint optimization

Access rights

URL

Journal Title

Journal ISSN

Volume Title

Authors

Date

Department

Major/Subject

Mcode

Degree programme

Language

Pages

Series

Abstract

Description

Keywords

Other note

DOI

Citation

Permanent link to this item

Collections