Learning Bayesian Networks with Restricted Causal Interactions

Julian R. Neil, Chris S. Wallace, Kevin B. KorbUAI 1999

TL;DR

This paper introduces a more efficient way to learn Bayesian Networks (BNs) by modeling local interactions within conditional probability tables (CPTs) using log-linear models. By employing the Minimum Message Length (MML) principle, they demonstrate that these "first-order models" (FOMs) can significantly reduce model complexity and improve learning accuracy, especially when combined in a "dual network" that intelligently selects the best local model for each node.

What Problem Does This Paper Address?

Learning Bayesian Networks (BNs) is a powerful tool for representing probabilistic relationships between variables, but it faces a significant challenge: the exponential growth in the number of parameters needed to define the Conditional Probability Tables (CPTs) for each node. This "curse of dimensionality" makes learning and inference computationally intractable for complex networks, especially with limited data. While previous research has explored ways to simplify CPTs by modeling local structure, these approaches have often been confined to specific models like naive Bayes or haven't been rigorously evaluated for structure learning. This paper aims to address this by proposing and evaluating a more flexible log-linear local model approach for both parameter and structure learning in BNs.

Methods

The core of this paper lies in the introduction and evaluation of First-Order Models (FOMs), a type of restricted logit model that assumes causal independence among the direct causes of a variable. This restriction significantly reduces the number of parameters needed for a CPT. The authors leverage the Minimum Message Length (MML) principle, a sophisticated information-theoretic approach to model selection and parameter estimation, to:

  • Select between local CPT models: MML is used to compare the message length (a proxy for posterior probability) of a FOM against the traditional full CPT for each node.
  • Discover network structure: An MML-based "MML-Sampling" algorithm, a variant of Metropolis sampling, is used to explore the space of possible network structures and identify those with high posterior probability.
  • Introduce a "Dual Network": This novel approach combines FOMs and full CPTs by using MML to select the most appropriate local model (FOM or full CPT) for each node on a case-by-case basis. This allows for flexibility, using the simpler FOM where appropriate and the more expressive full CPT when necessary.

Datasets

The authors evaluated their methods on six real-world datasets commonly used in machine learning:

  • Zoo
  • ICU
  • Flarel
  • Voting
  • Popularity
  • Nursery

These datasets vary in size, number of variables, and attribute arity. The Nursery dataset is noted as being synthetic and representing a hierarchical decision model.

Key Insights and Ideas

  • Log-linear models are powerful for local structure: The paper demonstrates that log-linear models, specifically the restricted FOM, can effectively capture causal interactions without the exponential parameter explosion of full CPTs.
  • MML is a robust framework for BN learning: The MML principle proves to be a powerful tool for both selecting local models and discovering network structures, providing a principled way to balance model complexity and data fit.
  • The "Dual Network" offers significant advantages: By intelligently choosing between restricted (FOM) and full CPTs at each node, the dual network often achieves better predictive accuracy and model fit than either approach alone. This highlights the importance of adaptive local modeling.
  • Causal independence assumption is not always restrictive: While FOMs assume causal independence, the paper shows that they can still perform well even when some non-monotonic interactions exist, by implicitly modeling them through additional connections.
  • FOMs can lead to more interpretable structures: The reduced parameterization of FOMs can lead to networks with more inferred arcs, potentially offering a more detailed view of causal relationships, especially when interactions are monotonic.

Key Results

  • Improved Model Fit: In five out of six datasets, the FOM and dual networks showed statistically significant improvements in message length (indicating higher posterior probability) compared to traditional Bayesian Networks (TBNs).
  • Enhanced Predictive Accuracy: While not always coinciding with the shortest message length, the dual network often achieved competitive or significantly better predictive accuracy (-LL) on unseen test data.
  • Nursery Dataset Example: The dual network and FOM significantly outperformed the TBN on the Nursery dataset, identifying a network structure that was prohibitively expensive for the TBN to represent. This highlights the efficiency gains of FOMs.
  • Parameter Reduction: Table 3 shows that FOMs and dual networks often infer more arcs but manage to fit a similar or even fewer number of parameters compared to TBNs, demonstrating their efficiency.

Limitations and Future Work

  • Causal Interpretation of FOMs: The paper acknowledges that the causal interpretation of FOMs is most straightforward when underlying causal interactions are monotonic. When non-monotonic interactions are present, FOMs might infer additional connections to approximate these, which could complicate direct causal interpretation.
  • Parameter Priors: The choice of parameter priors for FOMs can influence results, and the paper notes that a symmetric conjugate prior for arbitrary arity is difficult to define. They used independently normally distributed priors with a fixed variance.
  • Bias in Cleaning Procedure: The "cleaning" procedure used to identify MML-equivalence classes has a bias due to the order in which parents are considered for removal.
  • Future Work: The authors suggest extending the approach to less restrictive logit models than the first-order model considered here and investigating the impact of different parameter priors. They also plan to address the discrepancy in posterior estimates between FON and dual networks.

Summary updated

BibTeX
@inproceedings{neil1999learning,
  author = {Julian R. Neil and Chris S. Wallace and Kevin B. Korb},
  title = {{Learning Bayesian Networks with Restricted Causal Interactions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure