Seminar on Computational Learning and Adaptation

Not So Naive Bayesian Classification

Geoff Webb
Faculty of Information Technology
Monash University

Naive Bayes is an extremely efficient classification learning technique. Despite its simplicity, naive Bayes has proved remarkably accurate for many tasks. In consequence, it has been widely deployed, even though its accuracy is known to be limited by its attribute independence assumption. Of numerous proposals to improve the accuracy of naive Bayes by weakening this assumption, both Lazy Bayesian Rules and SuperParent Tree-Augemented Naive Bayes have demonstrated remarkable accuracy. However, both methods obtain this accuracy advantage at a considerable computational cost. Motivated by both theoretical and practical considerations, we present a new approach to weakening the attribute independence assumption by averaging all members of a constrained class of semi-naive Bayesian classifiers. In extensive experiments, this technique delivers accuracy comparable to the best previous methods but with substantially improved computational efficiency. It has the desirable properties that it learns in time linear with respect to training set size, supports both parallel and anytime classification, and allows incremental learning.

Return to the seminar schedule