Learning Chordal Markov Networks by Constraint Satisfaction
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 optimal certain networks which have been previously found by stochastic search.
The authors formulate the problem of learning an 
      undirected graphical model in terms of a large (intractable) constraint 
      satisfaction problem (CSP)In particular, given observations of the 
      variables, X, they focus on finding the junction tree, T, that with the 
      largest marginal likelihood p(X|T). Rather than blindly searching in the 
      space of all junction trees, they formulate a weighted constraint 
      satisfaction problem and propose to use off-the-shelf CSP solver to find 
      the best junction tree. The majority of the paper is on 
      formulating the CSP, including characterizing a junction tree as a 
      collection of cliques and separators over a balanced max weight spanning 
      tree. While this paper is very well written and appears to be novel it may 
      be of little practical value simply because formulating the CSP problem 
      requires an exponential number of constraints - in other words, what do we 
      gain by casting the structure learning problem as a CSP? I would liked to 
      have seen an approximate CSP that relaxes some conditions but remains 
      tractable, or a bounded form of the CSP that learns the most likely 
      junction tree with bounded clique size. Last, I'm not sure how a 
      non-uniform prior on graph structures could be incorporated, but we would 
      prefer a means to learn sparse/low treewidth 
      models.