An Experimental Study of Prior Dependence in Bayesian Network Structure Learning

Alvaro Henrique Chaim Correia, Cassio P. de Campos, Linda C. van der GaagISIPTA 2019 · OpenReview

Abstract

The Bayesian Dirichlet equivalent uniform (BDeu) function is a popular score to evaluate the goodness of a Bayesian network structure given complete categorical data. Despite its interesting properties, such as likelihood equivalence, it is known to be highly sensitive to its only parameter: the equivalent sample size (ESS). This paper presents an experimental study on the sensitivity of the BDeu score to the ESS, quantifying the amount of data required to achieve robustness in the learned structure.

Introduction

When learning the structure of a Bayesian Network—a Directed Acyclic Graph (DAG) that represents probabilistic dependencies—researchers frequently rely on the Bayesian Dirichlet equivalent uniform (BDeu) score. This score is favored because it satisfies "likelihood equivalence," meaning it assigns the same score to different graphs that represent the same set of conditional independencies (Markov equivalence classes).

However, the BDeu score requires a user-defined parameter called the Equivalent Sample Size (ESS), denoted as $\alpha$. This parameter represents the strength of the researcher's prior belief. Despite its widespread use, there is no consensus on what value $\alpha$ should take. If the learned structure changes significantly when $\alpha$ is adjusted slightly, the resulting model may reflect prior assumptions more than the underlying data. This study quantifies exactly how much data is needed before the choice of $\alpha$ stops dictating the model's structure—a property defined as robustness.

Methodology

To ensure findings were not artifacts of heuristic search algorithms, the authors employed an exact structure learning approach using GOBNILP, a solver that finds mathematically optimal graphs via integer linear programming.

Sensitivity was measured using the Robust Interval (RI): the largest range of ESS values that results in the same optimal Markov equivalence class. A large RI indicates a robust learning process, while a small RI suggests high sensitivity to the prior. The study examined two scenarios: restricted search spaces with known variable orderings and unconstrained learning.

Datasets

The research utilized two primary data sources:

  1. Gold Standard Networks: Data sampled from the Sachs (11 variables), Child (20 variables), and Alarm (37 variables) networks.
  2. Real-world Benchmarks: 16 datasets from the UCI Machine Learning repository, ranging from 7 to 19 variables. Continuous variables were discretized by their median values.

ESS as a Complexity Dial

A primary finding is that the ESS acts as a regularizer for graph density. As $\alpha$ increases, the learned networks become monotonically denser. At very high $\alpha$ values, the algorithm eventually defaults to a complete graph, representing a clear case of overfitting driven by the prior.

Figure 2: The average number of arcs increases as the ESS (alpha) increases across different sample sizes (N), demonstrating the prior's role as a complexity dial.

The "Big Data" Illusion and Robustness

One might assume that the influence of the prior would vanish quickly as sample sizes increase. However, the experiments suggest the opposite. For the relatively small Sachs network (11 variables), robustness was only achieved at $N \ge 10^5$ observations. For the larger Child and Alarm networks, even 100,000 samples were insufficient to ensure prior-independence across the tested range.

This sensitivity is partly due to "parameter inflation." The ESS is not a typical Dirichlet prior; it also influences the number of parameters in the model. This dual role creates a complex trade-off between regularization and complexity that is difficult to overcome even with substantial sample sizes.

Real-World Performance and the Default Prior

Many researchers use $\alpha=1$ as a default "uninformative" prior. However, the study of UCI datasets revealed that for more than half of the cases, the Robust Interval did not even include 1.0. This indicates that the common default choice often sits on a "cliff" where a minor change in the prior would yield a different model.

Figure 3: Robust Intervals (RI) for UCI datasets. RIo represents ordered variables and RIf represents the unconstrained case. Most datasets fail to achieve robustness for the range (0.1, 4.0).

As shown in the table above, for almost all real-world datasets (with the exception of the car dataset), the available data was insufficient to guarantee robustness for $\alpha \in (0.1, 4.0)$.

Conclusion

The BDeu score's sensitivity to the ESS is a significant hurdle for reliable Bayesian Network structure learning. Achieving robustness requires a prohibitively large amount of data—often far exceeding what is available in practical applications. While this study focuses on the skeleton of the network, it highlights the need for either more robust scoring functions or a deeper investigation into how this structural sensitivity impacts predictive performance in parameter learning.

Summary updated

Abstract

The Bayesian Dirichlet equivalent uniform (BDeu) function is a popular score to evaluate the goodness of a Bayesian network structure given complete categorical data. Despite its interesting proper...
BibTeX
@inproceedings{correia2019experimental,
  author = {Alvaro Henrique Chaim Correia and Cassio P. de Campos and Linda C. van der Gaag},
  title = {{An Experimental Study of Prior Dependence in Bayesian Network Structure Learning}},
  booktitle = {ISIPTA},
  year = {2019},
  url = {https://openreview.net/forum?id=irVuWaMzvmg},
}
Figure