Learning Extended Tree Augmented Naive Structures

Cassio P. de Campos, Giorgio Corani, Mauro Scanagatta, Marco Cuccu, Marco Zaffalon

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)
518 Downloads (Pure)


This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds' algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). We enhance our procedure with a new score function that only takes into account arcs that are relevant to predict the class, as well as an optimization over the equivalent sample size during learning. These ideas may be useful for structure learning of Bayesian networks in general. A range of experiments shows that we obtain models with better prediction accuracy than naive Bayes and TAN, and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator (AODE). We release our implementation of ETAN so that it can be easily installed and run within Weka.
Original languageEnglish
Pages (from-to)153-163
Number of pages11
JournalInternational Journal of Approximate Reasoning
Early online date23 Apr 2015
Publication statusPublished - Jan 2016


Dive into the research topics of 'Learning Extended Tree Augmented Naive Structures'. Together they form a unique fingerprint.

Cite this