TL;DR
This paper proposes a more effective criterion for selecting Bayesian network models in classification tasks, moving beyond standard marginal likelihood to a "supervised marginal likelihood." They introduce two novel approaches for building classifiers using this criterion: mixtures of simple diagnostic Bayesian networks and an augmented Naive Bayes classifier, demonstrating improved performance, particularly for logarithmic loss.
What Problem Does This Paper Address?
In machine learning, particularly classification, the goal is to build models that accurately predict a class variable given a set of predictor variables. A common approach is to use Bayesian networks, which represent probability distributions through directed acyclic graphs. Model selection, or choosing the "best" Bayesian network, is often guided by criteria like the marginal likelihood. However, the authors argue that for supervised tasks like classification, the standard marginal likelihood is suboptimal because it can favor models that accurately predict the predictor variables themselves, which is irrelevant to the classification goal. Instead, they advocate for a "supervised marginal likelihood" that focuses on the conditional distribution of the class variable given the predictors. The challenge is that computing this supervised marginal likelihood is computationally infeasible for most general Bayesian networks.
Methods
The paper focuses on a specific subclass of Bayesian networks called diagnostic Bayesian network classifiers. In these models, all arcs pointing to the class variable are incoming. This structure makes computing the supervised marginal likelihood feasible. However, the number of parameters in such models grows exponentially with the number of predictor variables. To address this, the authors propose two main strategies:
- Mixtures of Diagnostic Bayesian Network Classifiers: They consider simple diagnostic models where only a small, fixed number of predictors are directly connected to the class variable. They then form a mixture of these simple models, where each model's contribution to the final prediction is weighted by its supervised marginal likelihood. This allows for a more robust classifier by averaging over several specialized models. They explore mixtures where predictor subsets can overlap or form partitions.
- Augmenting the Naive Bayes Classifier: They leverage the insight that diagnostic models with high supervised marginal likelihood identify subsets of predictors that are highly dependent on each other. Instead of using these diagnostic models directly, they use these identified predictor subsets to relax the strict independence assumption of the Naive Bayes classifier. In this "augmented Naive Bayes" (ANB) model, predictors within a subset are allowed to be dependent (forming a fully connected subnetwork), but these subsets are assumed to be independent of each other.
Datasets
The empirical evaluation was conducted on 15 classification datasets from the UCI repository. Continuous variables in these datasets were discretized using simple equal-frequency discretization into 3 bins, making all datasets effectively discrete for the purpose of this study.
Key Insights and Ideas
- Supervised Marginal Likelihood is Key for Classification: The core idea is that for classification, focusing on how well a model predicts the class variable given the predictors is more important than predicting the predictors themselves.
- Diagnostic Networks Offer a Tractable Path: By restricting Bayesian networks to a "diagnostic" structure (all arcs pointing to the class variable), the computationally expensive supervised marginal likelihood becomes tractable.
- Mixtures Mitigate Parameter Explosion: When diagnostic models become complex due to many predictors, using mixtures of simpler diagnostic models provides a way to leverage the supervised criterion without overwhelming parameter counts.
- Augmented Naive Bayes Balances Simplicity and Power: The ANB approach cleverly combines the computational efficiency and robustness of Naive Bayes with the ability to capture important predictor dependencies identified by diagnostic models.
Key Results
- Logarithmic Loss Performance: The diagnostic mixture models (OMi and PM) significantly outperformed the vanilla Naive Bayes classifier on average for the conditional logarithmic loss.
- 0/1-Loss Performance: The Augmented Naive Bayes (ANB) classifier was the most robust and, on average, the only classifier to consistently beat the vanilla Naive Bayes for the 0/1-loss. While diagnostic mixtures were not as strong on 0/1-loss, they performed well on log-loss.
- Robustness of ANB: The ANB classifier was noted for its robustness, never performing significantly worse than Naive Bayes and often performing substantially better.
Limitations and Future Work
- Computational Cost of Mixtures: For the mixture models (OMi), the exhaustive search over all overlapping predictor subsets becomes computationally infeasible for larger subset sizes (i). Future work could explore more efficient search strategies.
- 0/1-Loss for Mixtures: The diagnostic mixture models were designed with logarithmic loss in mind, which explains their weaker performance on 0/1-loss. Adapting model averaging for other utility functions, like entropification, is suggested.
- Real-World Domain Performance: The authors note that in a real-world medical problem domain, diagnostic approaches yielded much better results than ANB or NB, suggesting potential differences in data characteristics that warrant further investigation.
- Improving ANB Search: The search algorithm for finding good partitionings in the ANB approach was a simple stochastic greedy method. More elaborate search algorithms could further improve ANB's performance.
- Dependencies Between Subnetworks: An extension of the ANB model could involve allowing some dependencies between the fully connected subnetworks, further enhancing its modeling capacity.
Summary updated