Flexible learning of k-dependence Bayesian network classifiers

In this paper we present an extension to the classical k-dependence Bayesian network classifier algorithm. The original method intends to work for the whole continuum of Bayesian classifiers, from naïve Bayes to unrestricted networks. In our experience, it performs well for low values of k. However, the algorithm tends to degrade in more complex spaces, as it greedily tries to add k dependencies to all feature nodes of the resulting net. We try to overcome this limitation by seeking for optimal values of k on a feature per feature basis. At the same time, we look for the best feature ordering. That is, we try to estimate the joint probability distribution of optimal feature orderings and individual number of dependencies. We feel that this preserves the essence of the original algorithm, while providing notable performance improvements.