On Supervised Selection of Bayesian Networks

Petri Kontkanen, Petri Myllymäki, Tomi Silander, Henry TirriUAI 1999

TL;DR

This paper investigates how to best select a Bayesian network model for supervised learning tasks like classification. They find that traditional methods optimized for general probability estimation perform poorly, and that a sequential, predictive approach (Dawid's prequential method) offers superior performance.

What Problem Does This Paper Address?

In machine learning, we often want to build models that can predict future outcomes. Bayesian networks are powerful tools for representing probabilistic relationships between variables. However, choosing the best Bayesian network structure from a set of possibilities is a critical step. Traditionally, model selection has focused on "unsupervised" criteria, aiming to find a model that best explains the entire joint probability distribution of the data. This paper highlights a crucial distinction: for supervised tasks (like classification, where we predict one variable given others), the model that best explains the joint distribution isn't necessarily the best for prediction. The authors argue that unsupervised criteria, like the marginal likelihood, are not optimized for the specific predictive distributions needed in supervised settings and can lead to suboptimal performance.

Methods

The paper compares several model selection criteria:

  • Unsupervised Marginal Likelihood (uEVI): The standard approach, aiming to maximize the probability of the data given the model.
  • Approximative Supervised Marginal Likelihood (~sEVI): A modification of the marginal likelihood to account for supervised tasks, but with a potentially crude approximation.
  • Empirical Cross-validation (fCV, looCV): Standard techniques where data is split to estimate predictive performance.
  • Dawid's Prequential Approach (PREQ, PREQ*): A sequential method that evaluates models by accumulating their predictive performance over time. This approach is adapted for classification tasks using a partial marginal likelihood. The PREQ* variant averages results over multiple data orderings.

The core innovation lies in rigorously comparing these methods in a supervised context and demonstrating the superiority of the prequential approach.

Datasets

The authors used 18 publicly available classification datasets from the UCI Machine Learning Repository. To ensure comparability and manage computational load, they focused on datasets with fewer than 15 variables. Continuous variables were discretized using K-means clustering, and missing values were imputed. For each dataset, a random sample of 500 instances was used, and the data was split into training and testing sets. To account for data ordering effects in sequential methods, experiments were repeated 50 times with different stratified random data orderings.

Key Insights and Ideas

  • Unsupervised vs. Supervised is a Crucial Distinction: The paper strongly demonstrates that optimizing for the joint probability distribution (unsupervised) does not guarantee optimal performance for specific predictive tasks (supervised).
  • Marginal Likelihood Falls Short: The standard marginal likelihood criterion, widely used, performs poorly in supervised model selection.
  • Prequential Methods Shine: Dawid's prequential approach, which evaluates models sequentially based on their predictive accuracy, emerges as the most effective method for supervised model selection.
  • Data Ordering Matters (but can be mitigated): For sequential methods like prequential approaches, the order of data can influence results. However, averaging over multiple data orderings (PREQ*) significantly improves performance and robustness.
  • Cross-validation is a Solid Performer: Empirical cross-validation methods also show good results, likely due to their inherent connection to estimating predictive performance.

Key Results

The paper presents results as "average relative prediction gains" compared to a standard Naive Bayes model.

  • uEVI (Unsupervised Marginal Likelihood): Performed poorly, with negative relative gains for the 0/1-loss, meaning it was worse than using no model selection at all.
  • ~sEVI (Approximative Supervised Marginal Likelihood): Did not improve results, likely due to its approximation method.
  • Cross-validation (fCV, looCV): Performed well, especially with the logarithmic loss.
  • PREQ* (Averaged Prequential): Achieved the best results for both 0/1-loss and logarithmic loss, consistently outperforming other methods. The average relative prediction gains were positive and substantial.

Limitations and Future Work

  • Model Family Restriction: The experiments were limited to "pruned Naive Bayes" network structures (where all arcs originate from the class variable). While this allowed for exhaustive model scoring, it might introduce a bias in the results. The authors acknowledge that a more general Bayesian network structure search would be necessary for broader applicability, but this would introduce search algorithm bias.
  • Small Sample Size Effects: The authors note that the performance of order-dependent methods (like PREQ) can be improved by simple averaging schemes. They suggest that developing more elaborate prequential schemes for small sample size domains is a promising area for future research.
  • Estimating Future Predictive Accuracy: The current study focused on comparing criteria for choosing between models, not on estimating the absolute future predictive accuracy of a chosen model. This remains a topic for future work.

Summary updated

BibTeX
@inproceedings{kontkanen1999supervised,
  author = {Petri Kontkanen and Petri Myllymäki and Tomi Silander and Henry Tirri},
  title = {{On Supervised Selection of Bayesian Networks}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure