Graphical Models and Exponential Families

Dan GeigerUAI 1998

TL;DR

This paper classifies graphical models (like Bayesian networks) based on their relationship to exponential families, a fundamental concept in statistics. This classification helps unify understanding and provides a theoretical basis for model selection techniques, particularly for models with hidden variables.

What Problem Does This Paper Address?

Graphical models are powerful tools for representing complex probability distributions, especially in machine learning and statistics. However, understanding the precise mathematical structure of these models, particularly when they involve hidden (unobserved) variables, can be challenging. This lack of clarity hinders the development and justification of model selection methods – the process of choosing the "best" graphical model for a given dataset. Specifically, while methods like the Bayesian Information Criterion (BIC) are widely used for model selection, their theoretical justification for complex graphical models, especially those with hidden variables, has been incomplete. This paper aims to bridge this gap by providing a rigorous classification of graphical models within the framework of exponential families and by exploring how this classification can inform model selection.

Methods

The paper's core contribution lies in its classification of graphical models into three categories based on their representation as subfamilies of exponential families:

  • Linear Exponential Families (LEFs): Undirected graphical models without hidden variables are shown to be LEFs. This leverages well-established statistical theory for LEFs.
  • Curved Exponential Families (CEFs): Directed acyclic graphical models and chain graphs without hidden variables are identified as CEFs. CEFs are distributions that form a smooth manifold, and this classification allows the application of existing statistical results for CEFs, such as the asymptotic validity of BIC for model selection.
  • Stratified Exponential Families (SEFs): Graphical models with hidden variables are classified as SEFs. An SEF is a finite union of CEFs satisfying a "frontier condition." This is a generalization of CEFs, acknowledging that models with hidden variables might not form a single smooth manifold.

A key procedural contribution is the implicitization process. This technique takes a parametric definition of a graphical model (especially those with hidden variables) and derives a set of equality constraints on the observable variables. These constraints can reveal non-independence relationships that are not immediately obvious from the model's structure alone and can be used for model comparison.

Datasets

Not discussed in the paper. The paper focuses on theoretical classifications and procedures rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unifying Framework: Classifying graphical models as LEFs, CEFs, or SEFs provides a unified theoretical lens to understand their statistical properties and relationships.
  • Justifying Model Selection: By showing that many graphical models are CEFs, the paper provides a theoretical justification for using BIC for model selection in these cases, even when closed-form marginal likelihoods are unknown.
  • Hidden Variables are Trickier: Models with hidden variables are more complex (SEFs) and don't always form smooth manifolds, making direct application of CEF theory challenging.
  • Implicitization as a Discovery Tool: The implicitization procedure is a powerful way to uncover hidden constraints within graphical models, which can be crucial for distinguishing between models that are otherwise indistinguishable based on independence alone.
  • SEFs as a Generalization: Stratified Exponential Families offer a more general framework to encompass the complexity of graphical models with hidden variables, extending the reach of statistical theory.

Key Results

  • Undirected graphical models without hidden variables are LEFs.
  • Directed acyclic graphical models and chain graphs without hidden variables are CEFs.
  • Graphical models with hidden variables are SEFs.
  • The implicitization procedure can generate non-trivial independence and non-independence constraints for graphical models with hidden variables, which can be used for model selection. Examples include deriving the tetrad difference constraints and Verma constraints.

Limitations and Future Work

  • SEF Theory for BIC: While the paper classifies models with hidden variables as SEFs, it acknowledges that the proof of BIC's validity for SEFs is an open question and an area of ongoing research. The paper suggests that BIC is likely valid for SEFs, but the formal proof is not yet established.
  • Inequality Constraints: The implicitization procedure, as described, primarily handles equality constraints. The paper notes that inequality constraints (e.g., probabilities being positive) are ignored in the examples, and their handling in model selection is a future direction.
  • P-structure as CEF: It remains an open question whether the P-structure (a specific graphical model with a hidden variable) is a CEF, which would further justify BIC for that specific model.
  • Generalizing BIC to SEFs: The paper highlights the need to extend the theoretical justification of BIC to the broader class of Stratified Exponential Families.

Summary updated

BibTeX
@inproceedings{geiger1998graphical,
  author = {Dan Geiger},
  title = {{Graphical Models and Exponential Families}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure