Bayesian network learning by compiling to weighted MAX-SAT

James CussensUAI 2008

TL;DR

This paper introduces a novel approach to learning Bayesian networks by framing the problem as a weighted MAX-SAT (Maximum Satisfiability) problem. By leveraging the MaxWalkSat local search algorithm, they demonstrate that it's possible to discover Bayesian network structures with higher marginal likelihood scores than the true underlying networks, even for complex datasets.

What Problem Does This Paper Address?

Learning the structure of Bayesian networks from data is a computationally challenging combinatorial optimization problem. The goal is to find a network structure that best explains the observed data, often measured by a score like the marginal likelihood. Traditional methods can be computationally expensive, especially as the number of variables and data points increases. This paper explores whether a powerful SAT solver, specifically MaxWalkSat, can be effectively adapted to tackle this complex learning task.

Methods

The core innovation lies in encoding the Bayesian network learning problem into a weighted MAX-SAT formulation. Here's a breakdown:

  • Encoding Bayesian Networks: Each possible "family" (a variable and its set of parents) is represented by a distinct propositional atom. The "score" of a family (derived from the BDeu marginal likelihood) is translated into a "soft" weighted clause. This means that satisfying these clauses contributes positively to the overall objective.
  • Enforcing Acyclicity: A crucial constraint in Bayesian networks is that they must be Directed Acyclic Graphs (DAGs). The paper explores two methods to enforce this:
  • Ancestor Encoding: This involves creating atoms to represent ancestor relationships between variables and then adding "hard" clauses that prevent cycles based on these relationships.
  • Total Order Encoding: This approach encodes a total ordering of the variables and uses clauses to ensure this order is maintained, which indirectly prevents cycles. The "Total Order" method proved to be more effective.
  • MaxWalkSat Algorithm: The MaxWalkSat algorithm, a local search heuristic for MAX-SAT, is then applied to this encoded problem. It iteratively flips the truth values of atoms to maximize the sum of weights of satisfied clauses, effectively searching for the best Bayesian network structure.

Datasets

The authors evaluated their approach on 21 synthetic datasets generated from 7 known Bayesian networks. These networks vary in size, with the largest dataset containing 10,000 data points and 60 variables. The datasets were generated by forward sampling from these "true" BNs, ensuring complete data (no missing values).

Key Insights and Ideas

  • MAX-SAT as a Powerful Framework: The paper demonstrates that complex combinatorial optimization problems like Bayesian network learning can be effectively mapped to the MAX-SAT framework, opening doors for leveraging existing powerful solvers.
  • Surpassing "True" Networks: Surprisingly, MaxWalkSat often found Bayesian networks with higher BDeu scores than the original "true" networks from which the data was sampled. This suggests that the learned networks might be better explanations of the data, or that the search algorithm is adept at navigating the likelihood landscape.
  • Encoding Matters: The choice of encoding for acyclicity significantly impacts performance. The "Total Order" encoding yielded better results than the "Ancestor" encoding, highlighting the importance of how constraints are represented.
  • Bayesian Model Averaging Potential: The paper hints at the possibility of using MaxWalkSat for Bayesian Model Averaging (BMA) by collecting the BNs generated during the search, suggesting a novel way to approximate posterior distributions over network structures.

Key Results

  • MaxWalkSat quickly found Bayesian networks with higher BDeu scores than the "true" networks for most datasets.
  • The "Total Order" encoding for acyclicity consistently outperformed the "Ancestor" encoding.
  • For a large dataset (hailfinder, 10,000 data points, 60 variables), the "Ancestor" encoding resulted in a weighted CNF input file with 19,932 atoms and 269,367 clauses.
  • The "Long" runs (using Total Order encoding, 10% noise, and disallowing breaking hard clauses) were particularly successful, often finding BNs with significantly better scores.

Limitations and Future Work

  • Prior Knowledge Integration: The paper notes that while adding prior knowledge about independent variables had little effect, incorporating known ancestor relations improved results, suggesting future work could explore more sophisticated prior integration.
  • BMA Challenges: While promising, Bayesian Model Averaging using this search-based approach faced challenges. For most datasets, the posterior distribution was heavily concentrated on a few BNs, making it difficult to reliably estimate probabilities for a wider range of structures.
  • Encoding Alternatives: The authors suggest exploring alternative encodings for acyclicity and other constraints.
  • Beyond BDeu Score: Future work will investigate the learned BNs using other metrics and compare this learning approach to existing systems.

Summary updated

BibTeX
@inproceedings{cussens2008bayesian,
  author = {James Cussens},
  title = {{Bayesian network learning by compiling to weighted MAX-SAT}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure