Bayesian network learning by compiling to weighted MAX-SAT

TY - GEN

T1 - Bayesian network learning by compiling to weighted MAX-SAT

AU - Cussens, James

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77958576004&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0-9749039-4-9

SP - 105

EP - 112

BT - Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI 2008)

A2 - McAllester, David

A2 - Myllymaki, Petri

PB - AUAI Press

CY - Corvallis, Oregon

T2 - 24th Conference on Uncertainty in Artificial Intelligence

Y2 - 9 July 2008 through 12 July 2008

ER -