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