Asymptotic Model Selection for Naive Bayesian Networks

Dmitry Rusakov, Dan GeigerUAI 2002

TL;DR

This paper tackles the challenge of selecting the best naive Bayesian network model when some variables are unobserved (hidden). They derive a new, more accurate formula for approximating the marginal likelihood of data, which is crucial for Bayesian model selection, and show that the standard BIC score is often insufficient for these complex models.

What Problem Does This Paper Address?

Choosing the right statistical model is a fundamental problem in machine learning and statistics. When dealing with complex models like Bayesian networks, especially those with hidden variables, selecting the best model can be tricky. The standard approach for Bayesian model selection relies on approximating the marginal likelihood of the data given a model. The Bayesian Information Criterion (BIC) is a popular approximation, but it's known to be valid for simpler model classes like linear or curved exponential families.

However, naive Bayesian networks with hidden variables fall into a more complex category called Stratified Exponential (SE) models. For these models, the standard BIC approximation can be inaccurate. This paper addresses this gap by developing a more precise asymptotic formula for the marginal likelihood of naive Bayesian networks with two hidden states and binary features. This new formula accounts for the specific "singularities" that arise in these models, which the standard BIC score overlooks, leading to potentially incorrect model choices.

Methods

The core of this paper lies in applying advanced mathematical techniques to approximate complex integrals that represent the marginal likelihood. Specifically, they leverage Watanabe's method for asymptotic analysis of integrals. This method is particularly suited for situations where the integrand has "singularities" or degenerate points, which is common in SE models.

The authors first transform the model parameters into a more convenient "joint space" representation. Then, they analyze the behavior of the log-likelihood function near its maximum (which corresponds to the minimum of the negative log-likelihood). Unlike the standard Laplace approximation (which assumes a single, non-degenerate maximum), Watanabe's method allows for the analysis of integrals where the maximum might occur on a set of points (a "zero set") or involve complex intersections.

They categorize the types of singularities based on the structure of the naive Bayesian network and derive specific asymptotic formulas for each case. This involves identifying the "largest pole" and its multiplicity of a related complex function, which directly informs the coefficients in the asymptotic expansion of the marginal likelihood.

Datasets

Not discussed in the paper. The paper focuses on theoretical derivations and asymptotic analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • BIC is not universally valid: The paper provides a concrete example where the standard BIC score is demonstrably incorrect for naive Bayesian networks with hidden variables, highlighting its limitations for Stratified Exponential models.
  • Singularities matter: The key insight is that the "singularities" in the parameter space of these models significantly impact the marginal likelihood approximation. The standard BIC score, which assumes smooth behavior, fails to capture these effects.
  • New asymptotic formulas: The paper introduces novel asymptotic formulas for the marginal likelihood that are tailored to different types of singularities. These formulas include terms that depend on the specific data statistics (Y) and can even involve "ln ln N" terms, which are absent in the standard BIC.
  • Geometric interpretation: The coefficients in the new asymptotic formulas are related to the geometric structure of the log-likelihood function near singular points, offering a deeper understanding of why these models behave differently.
  • Watanabe's method is powerful: The application of Watanabe's advanced mathematical tools proves effective in tackling these complex integral approximations, opening doors for analyzing other SE models.

Key Results

The paper presents Theorem 3, which provides asymptotic approximations for the marginal likelihood of naive Bayesian networks with two hidden states and binary features. These approximations are categorized based on the type of "singularity" of the data statistics (Y):

  1. Regular points (Y ∈ Y \ S): The formula is similar to the standard BIC, with the log-marginal likelihood being approximately $N f_Y - \frac{2n+1}{2} \ln N + O(1)$.
  2. Type 1 singularity (Y ∈ S \ S'): The formula becomes $N f_Y - \frac{2n-1}{2} \ln N + O(1)$.
  3. Type 2 singularity (Y ∈ S'): The formula is $N f_Y - \frac{n+1}{2} \ln N + O(1)$.

For degenerate models (n=1 or n=2), specific formulas are also derived, with one case (n=2 and Y ∈ S') even including a $2 \ln \ln N$ term in the $O(1)$ approximation. These results explicitly show how the asymptotic approximation deviates from the standard BIC score, particularly in the presence of singularities.

Limitations and Future Work

Limitations:

  • Specific model class: The results are derived for naive Bayesian networks with two hidden states and binary features. Extending these formulas to models with more hidden states or different feature types is an open problem.
  • Assumptions: The proofs rely on certain assumptions about the density being bounded and away from zero, and positive statistics. While the authors note these can be modified, they simplify the current proofs.
  • Computational complexity: While the formulas are asymptotic, their practical implementation might still require careful handling of the statistics Y and identifying their singularity type.

Future Work:

The authors outline several promising directions:

  1. Generalizing to all statistics Y: Developing closed-form asymptotic formulas for marginal likelihood integrals for all types of statistics Y, not just specific singularity types.
  2. Uniform asymptotic formulas: Extending the analysis to handle "converging statistics" (i.e., when Y itself depends on N), which is more realistic for large datasets.
  3. Algorithmic implementation: Developing an algorithm that can automatically determine the singularity type of the data statistics for a given naive Bayesian network and apply the appropriate asymptotic formula.
  4. Broader applicability: Extending these methods to general Bayesian networks with hidden variables, not just the naive structure.

Summary updated

BibTeX
@inproceedings{rusakov2002asymptotic,
  author = {Dmitry Rusakov and Dan Geiger},
  title = {{Asymptotic Model Selection for Naive Bayesian Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2002},
}
Figure