Bayesian network learning by compiling to weighted MAX-SAT
  The problem of learning discrete Bayesian networks from data is encoded as a
weighted MAX-SAT problem and the MaxWalkSat local search algorithm is used to
address it. For each dataset, the per-variable summands of the (BDeu) marginal
likelihood for different choices of parents ('family scores') are computed
prior to applying MaxWalkSat. Each permissible choice of parents for each
variable is encoded as a distinct propositional atom and the associated family
score encoded as a 'soft' weighted single-literal clause. Two approaches to
enforcing acyclicity are considered: either by encoding the ancestor relation
or by attaching a total order to each graph and encoding that. The latter
approach gives better results. Learning experiments have been conducted on 21
synthetic datasets sampled from 7 BNs. The largest dataset has 10,000
datapoints and 60 variables producing (for the 'ancestor' encoding) a weighted
CNF input file with 19,932 atoms and 269,367 clauses. For most datasets,
MaxWalkSat quickly finds BNs with higher BDeu score than the 'true' BN. The
effect of adding prior information is assessed. It is further shown that
Bayesian model averaging can be effected by collecting BNs generated during the
search.
