  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.
