Learning bayesian networks consistent with the optimal branching
See where this sits in the topic map →Summary AI-generated
- TL;DR
- We introduce a polynomial-time algorithm to learn Bayesian networks whose structures are restricted by an optimal branching and a maximum in-degree $k$, resulting in what we call consistent $k$-graphs (CkGs).
- Problem
- Not specified in the abstract.
- Method
- The optimal branching is used as a heuristic for a primary causality order between network variables, which is then refined according to a specific score into an optimal CkG Bayesian network. This approach expands the search space exponentially relative to trees while maintaining a polynomial-time bound.
- Results
- We show that the induced classifier consistently scores better than or equal to both Naive Bayes and Tree Augmented Naive Bayes classifiers.
- Contributions
- Not specified in the abstract.
- Limitations
- Not specified in the abstract.
- Takeaways
- Experiments using the UCI repository demonstrate that these improved scores frequently translate into increased classification accuracy.
- Applications
- The proposed algorithm can be applied to scores that decompose over the network structure, including LL, MDL, AIC, BIC, K2, BD, BDe, BDeu, and MIT scores.
- Topics
- Not specified in the abstract.
- For industry
- Not specified in the abstract.
- Why it matters
- Not specified in the abstract.
Abstract
We introduce a polynomial-time algorithm to learn Bayesian networks whose structure is restricted to nodes with in-degree at most k and to edges consistent with the optimal branching, that we call consistent k-graphs (CkG). The optimal branching is used as an heuristic for a primary causality order between network variables, which is subsequently refined, according to a certain score, into an optimal CkG Bayesian network. This approach augments the search space exponentially, in the number of nodes, relatively to trees, yet keeping a polynomial-time bound. The proposed algorithm can be applied to scores that decompose over the network structure, such as the well known LL, MDL, AIC, BIC, K2, BD, BDe, BDeu and MIT scores. We tested the proposed algorithm in a classification task. We show that the induced classifier always score better than or the same as the Naive Bayes and Tree Augmented Naive Bayes classifiers. Experiments on the UCI repository show that, in many cases, the improved scores translate into increased classification accuracy.