TL;DR
This paper investigates how sensitive the "most probable" Bayesian network structure is to a crucial parameter, the equivalent sample size ($\alpha$), in the BDeu scoring metric. They demonstrate that even small changes in $\alpha$ can lead to significantly different network structures, highlighting a potential fragility in model selection that needs careful consideration.
What Problem Does This Paper Address?
Learning Bayesian network structures from data is a fundamental task in machine learning. A popular method for this is using scoring metrics, such as the BDeu (Bayesian Dirichlet equivalence uniform) score, to find the "most probable" network structure (MAP - Maximum A Posteriori). The BDeu score, however, relies on a parameter called the "equivalent sample size" ($\alpha$). This parameter is meant to represent prior belief about the uniformity of conditional probability distributions. The problem is that there's no universally agreed-upon "uninformative" value for $\alpha$. This lack of guidance is concerning because the authors hypothesize, and then empirically show, that the choice of $\alpha$ can drastically alter the resulting MAP structure, even when $\alpha$ is not directly tied to the structure prior itself. This sensitivity raises questions about the robustness and interpretability of MAP structures learned using BDeu.
Methods
The core of the paper involves empirical experiments. The authors use an exact Bayesian network structure learning software (bene) to learn MAP structures for various datasets. They systematically vary the equivalent sample size parameter $\alpha$ across a wide range, from very small values (e.g., $2 \times 10^{-20}$) to very large values (e.g., $10^6$). They then analyze how the number of arcs and the specific structure of the learned Bayesian networks change as $\alpha$ is varied.
To understand why this sensitivity occurs, they delve into the mathematical formulation of the BDeu score. They analyze the numerator and denominator of the score, particularly focusing on how the denominator acts as a complexity penalty and how this penalty is influenced by $\alpha$. They also explore two Bayesian approaches to address the uncertainty in $\alpha$: integrating out $\alpha$ using a uniform prior and finding the $\alpha$ that maximizes the prequential score.
Datasets
The authors evaluated their findings on 20 different UCI datasets. They mention that some datasets contained continuous values and missing values, which were preprocessed by discretizing continuous variables into three equal-width bins and imputing missing values randomly based on empirical distributions.
Specific datasets mentioned include:
- Yeast
- Balance
- Iris
- Thyroid
- Liver
- Ecoli
- Abalone
- Diabetes
- Post op
- Cancer
- Shuttle
- Tictac
- Be wisc
- Glass
- Page
- Heart cl
- Heart hu
- Heart st
- Wine
- Adult
Key Insights and Ideas
- High Sensitivity to $\alpha$: The most striking finding is that the MAP Bayesian network structure is highly sensitive to the equivalent sample size parameter $\alpha$. Even small changes in $\alpha$ can lead to different network structures, and a wide range of $\alpha$ values can produce networks with varying numbers of arcs.
- Non-Monotonicity: The relationship between $\alpha$ and the number of arcs is not always monotonic. While larger $\alpha$ values generally tend to produce more arcs, there are exceptions where increasing $\alpha$ can lead to fewer arcs or different independence relationships even if the arc count remains the same.
- Complexity Penalty and $\alpha$: The denominator of the BDeu score acts as a complexity penalty. Crucially, increasing $\alpha$ makes this penalty smaller, which can favor more complex structures (more arcs).
- Zero Sufficient Statistics Matter: The paper highlights that zero sufficient statistics (Nijk) can lead to unusual behavior in the numerator of the BDeu score, particularly when $\alpha$ is small, aligning with asymptotic findings by Steck and Jaakkola.
- Bayesian Approaches for $\alpha$: The authors explore two Bayesian methods to handle the uncertainty in $\alpha$:
- Integrating out $\alpha$: Assigning a uniform prior to $\alpha$ and averaging over possible structures. This approach often selects a MAP model that is also favored by reasonable, non-extreme values of $\alpha$.
- Prequential Score Maximization: Finding the $\alpha$ that maximizes the prequential score. This method also tends to select models that are MAP for reasonable $\alpha$ values.
- Practical Implications: The findings suggest that simply picking an arbitrary "uninformative" value for $\alpha$ (like 1.0) might be misleading. It underscores the need for careful validation and potentially exploring a range of $\alpha$ values or using Bayesian integration methods.
Key Results
- For the Yeast dataset (9 variables), varying $\alpha$ from $2 \times 10^{-20}$ to $34000$ resulted in MAP structures with arc counts ranging from 0 to 36.
- Across 20 datasets, significant variation in MAP structures was observed for different $\alpha$ values, even within "realistic" ranges (e.g., 1-100).
- For the Liver dataset, $\alpha$ values of 0.01, 0.05, 0.10, 1.00, 2.00, 3.00, 9.00, and 13.00 all yielded different MAP models with varying numbers of arcs.
- The paper found that integrating out $\alpha$ (with a uniform prior) and maximizing the prequential score often selected the same MAP model, and these models were typically those favored by reasonable $\alpha$ values (between 1 and 100).
Limitations and Future Work
- Computational Cost: Exact structure learning and integrating out $\alpha$ are computationally expensive, limiting their application to smaller datasets or requiring heuristic search methods for larger ones.
- Prior Specification for $\alpha$: While integrating out $\alpha$ or maximizing the prequential score are Bayesian approaches, they still require specifying a prior distribution for $\alpha$ (P($\alpha$|G)), which is not straightforward and can also influence the results.
- Future Work: The authors suggest further research into:
- Determining the "correct" prior distribution for $\alpha$ and its impact on model selection.
- Comparing the predictive performance of models selected by integrating out $\alpha$ versus those selected by maximizing the prequential score.
- Investigating alternative score equivalence criteria like the Normalized Maximum Likelihood (NML), which do not require parameter priors but are computationally challenging for general Bayesian networks.
- Developing more efficient algorithms for calculating NML.
Summary updated