Learning Optimal Augmented Bayes Networks

Details Learning Optimal Augmented Bayes Networks Learning Optimal Augmented Bayes Networks

2005-09-19

arxiv.org/abs/cs/0509055v1

Computer Science

Learning

4 pages, 1 figure

Scientific paper

Naive Bayes is a simple Bayesian classifier with strong independence assumptions among the attributes. This classifier, desipte its strong independence assumptions, often performs well in practice. It is believed that relaxing the independence assumptions of a naive Bayes classifier may improve the classification accuracy of the resulting structure. While finding an optimal unconstrained Bayesian Network (for most any reasonable scoring measure) is an NP-hard problem, it is possible to learn in polynomial time optimal networks obeying various structural restrictions. Several authors have examined the possibilities of adding augmenting arcs between attributes of a Naive Bayes classifier. Friedman, Geiger and Goldszmidt define the TAN structure in which the augmenting arcs form a tree on the attributes, and present a polynomial time algorithm that learns an optimal TAN with respect to MDL score. Keogh and Pazzani define Augmented Bayes Networks in which the augmenting arcs form a forest on the attributes (a collection of trees, hence a relaxation of the stuctural restriction of TAN), and present heuristic search methods for learning good, though not optimal, augmenting arc sets. The authors, however, evaluate the learned structure only in terms of observed misclassification error and not against a scoring metric, such as MDL. In this paper, we present a simple, polynomial time greedy algorithm for learning an optimal Augmented Bayes Network with respect to MDL score.

Affiliated with

Also associated with

No associations

Rating

Learning Optimal Augmented Bayes Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning Optimal Augmented Bayes Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning Optimal Augmented Bayes Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-298163