Representing Conditional Independence Using Decision Trees

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 20

Machine Learning

While the representation of decision trees is fully expressive theoretically, it has been observed that traditional decision trees has the replication problem. This problem makes decision trees to be large and learnable only when sufficient training data are available. In this paper, we present a new representation model, conditional independence trees (CITrees), to tackle the replication problem from probability perspective. We propose a novel algorithm for learning CITrees. Our experiments show that CITrees outperform naive Bayes, C4.5, TAN, and AODE significantly in classification accuracy.