Learning networks determined by the ratio of prior and data

Maomi UenoUAI 2010

TL;DR

This paper provides a theoretical explanation for why the "equivalent sample size" (ESS) in Bayesian network learning is so crucial. It reveals that the ESS, in conjunction with the sample size, dictates the penalty for adding new connections (arcs) in a network, effectively balancing prior knowledge against observed data. This work unifies several existing scoring metrics and clarifies the counterintuitive behavior of ESS in learning.

What Problem Does This Paper Address?

Learning Bayesian networks involves finding the most probable network structure given some data. A common approach uses a "marginal likelihood score," which incorporates prior beliefs about the network's parameters. A key component of this score is the "equivalent sample size" (ESS), a hyperparameter that quantifies the strength of the prior. Recent empirical studies have shown that the ESS has a surprisingly strong and sometimes counterintuitive impact on the learned network structure. For instance, very small ESS values can lead to simpler networks, while very large ESS values can lead to overly complex ones, contradicting the intuition that priors should prevent overfitting. This paper aims to provide a theoretical explanation for these observed phenomena and clarify the role of ESS in the learning process.

Methods

The authors employ asymptotic analysis of the log-marginal likelihood score. This involves deriving mathematical approximations of the score when the sample size and/or the ESS are very large. They decompose the score into a "log-posterior" term (related to data fit and variable dependencies) and a "penalty" term (which discourages overly complex structures). By analyzing how these terms change with ESS and sample size, they derive key insights. They also show how this general score unifies other common scoring metrics like AIC and BIC under specific conditions for the ESS and prior knowledge.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated data in its numerical examples.

Key Insights and Ideas

  • ESS as a Prior-Data Balancer: The core insight is that the ratio of ESS to sample size determines the penalty for adding arcs. This means ESS isn't just about prior strength but how that strength interacts with the evidence from the data.
  • Unified Scoring Metrics: The paper demonstrates that common scoring metrics like AIC and BIC are special cases of the general marginal likelihood score, achievable by setting the ESS and prior knowledge appropriately.
  • Counterintuitive ESS Behavior Explained: The paper explains why large ESS can lead to more arcs (overfitting) and small ESS can lead to fewer arcs (underfitting). This is due to a tradeoff: ESS influences both the data fit term (log-posterior) and the penalty term, with opposing effects on arc addition.
  • BDeu's Dual Role: For the BDeu score (a common default), ESS plays contradictory roles: it helps block extra arcs in the log-posterior term but also helps add arcs in the penalty term. This inherent tradeoff makes BDeu highly sensitive to ESS.
  • Skewness Matters: The "skewness" (non-uniformity) of conditional probability distributions significantly impacts learning. Skewed distributions make it easier for learning algorithms to detect dependencies, while uniform distributions can lead to underfitting.

Key Results

  • Asymptotic Analysis: The paper provides an asymptotic analysis of the log-marginal likelihood score, decomposing it into a log-posterior and a penalty term.
  • AIC and BIC Equivalence: It's shown that the marginal likelihood score converges to AIC when the prior is equivalent to the training data and to BIC when the hyperparameters are fixed at 1.
  • BDeu Decomposition: The log-BDeu score is shown to be composed of a term reflecting data fit and a penalty term that blocks extra arcs.
  • ESS Tradeoff: A crucial tradeoff is identified in ESS: it helps block arcs in one part of the score but encourages adding them in another, explaining its sensitivity.
  • Numerical Examples: Simulations with skewed and non-skewed distributions confirm that ESS values need to be adjusted based on the data's characteristics. Skewed data benefits from smaller ESS, while uniform data might require larger ESS.

Limitations and Future Work

  • Asymptotic Assumptions: The analysis relies on asymptotic approximations (large sample size and/or large ESS). The behavior for small sample sizes and small ESS might differ.
  • Computational Complexity: While the paper focuses on theoretical properties, finding the optimal ESS in practice can still be challenging due to the sensitivity of the score.
  • Future Work: The paper suggests that understanding the optimal ESS for specific tasks (like prediction or classification) beyond just finding the MAP structure would be a valuable next step. Further exploration of the tradeoff's impact on different types of data and network structures is also implied.

Summary updated

BibTeX
@inproceedings{ueno2010learning,
  author = {Maomi Ueno},
  title = {{Learning networks determined by the ratio of prior and data}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure