A Bayesian Method Reexamined

Derek D. AyersUAI 1994

TL;DR

This paper scrutinizes the widely-used K2 metric for scoring Bayesian network structures, revealing counterintuitive results where the metric favors reversed causal relationships over the true generating structure, especially as data complexity increases. The authors propose that this bias stems from the metric's underlying assumptions about prior probabilities and suggest that careful selection of priors is crucial for accurate network inference.

What Problem Does This Paper Address?

Constructing Bayesian networks from data is a fundamental task in machine learning and artificial intelligence. A key challenge is efficiently searching the vast space of possible network structures to find the one that best explains the observed data. The K2 algorithm, a popular heuristic approach, relies on a scoring metric (the K2 metric) to evaluate candidate network structures. While the K2 algorithm is effective, the paper questions the behavior of its core scoring metric, particularly when applied to simple networks, suggesting it might not always align with our intuitive understanding of causality or data generation.

Methods

The paper focuses on analyzing the K2 metric, which calculates the joint probability of a network structure and the observed data, P(BS, D). This metric is derived under several assumptions, including discrete variables, independent cases given the model, no missing values, and a uniform prior over numerical probabilities. The authors then explore a generalized version of the K2 metric, which allows for non-uniform Dirichlet priors. This generalization is achieved by replacing factorials with Gamma functions, enabling more flexible prior specifications. The core of their analysis involves applying these metrics to carefully constructed synthetic datasets to observe their behavior.

Datasets

The paper uses synthetic datasets generated to specifically test the behavior of the K2 metric.

  • Table 1: A small, nine-case database with two discrete variables (x1, x2) designed to illustrate the metric's behavior with a simple functional relationship (x2 = |x1|).
  • Table 2: A generalized version of the database from Table 1, parameterized by an integer vector A (case counts) and an integer ω (number of value assignments). This allows for systematic exploration of how data complexity and size affect the K2 metric's scoring.

Key Insights and Ideas

  • K2 Metric's Bias Against Determinism: The K2 metric consistently scores a reversed causal relationship higher than the true generating structure, even when the true structure perfectly explains the data. This is particularly evident when the relationship between variables approaches determinism.
  • The Role of Priors: The paper strongly suggests that the counterintuitive results are rooted in the metric's assumptions about prior probabilities, specifically the uniform prior in the original K2 metric.
  • Sensitivity to Data Complexity: As the number of possible value assignments for variables increases (approaching continuous variables), the K2 metric's bias becomes more pronounced, with the posterior probability of the true generating structure approaching zero.
  • Generalization Offers Flexibility: The extended K2 metric, using Dirichlet priors, offers a way to mitigate this bias by allowing for more informed prior specifications that can give equivalent networks equivalent scores.

Key Results

  • In the initial example (Table 1), the structure {x1 → x2} was scored as almost twice as likely as {x1 ← x2}, and nearly fifteen times as likely as {x1 x2} (independent), despite the data being generated by x2 = |x1|.
  • With the generalized database (Table 2), as the number of occurrences of each case (A10, A100, etc.) increased, the posterior probability of the structure {x1 → x2} decreased, while the probability of {x1 ← x2} increased, often approaching 1. For instance, with ω=4 and A100, P(BS1|D) = 0.0305 and P(BS2|D) = 0.9695.
  • Table 4 demonstrates how choosing specific prior parameters (α) in the generalized K2 metric can lead to equivalent networks receiving equal scores, e.g., for α=45, P(BS1|D) = 0.3680 and P(BS2|D) = 0.3680.

Limitations and Future Work

  • Limitations: The paper highlights that the K2 metric's bias is particularly problematic when dealing with deterministic or near-deterministic relationships and when the number of possible values for variables increases. The authors also note that the search methods used with K2 (e.g., requiring a node order) might not be as affected if they locate high-probability structures, but the relative scores are highly dependent on prior choices.
  • Future Work: The authors suggest that researchers should not solely focus on searching for high-probability network structures but also on improving the scoring methods themselves and carefully choosing priors. The paper implicitly points towards the need for more robust scoring metrics or prior specification techniques that are less susceptible to the observed biases.

Summary updated

BibTeX
@inproceedings{ayers1994bayesian,
  author = {Derek D. Ayers},
  title = {{A Bayesian Method Reexamined}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
}
Figure