Bayes Optimal Classification for Decision Trees

We present the first algorithm for exact Bayes optimal classification from the hypothesis space of decision trees satisfying leaf constraints. Our contribution is that we reduce this problem to the problem of finding a rule-based classifier with appropriate weights. We show that these rules and weights can be computed in linear time from the output of a modified frequent itemset mining algorithm, which means that we can compute the classifier in practice, despite the exponential worst-case complexity. We perform experiments in which we compare the Bayes optimal predictions with those of the maximum a posteriori hypothesis.