Bayes optimal classification for decision trees

We present an algorithm for exact Bayes optimal classification from a hypothesis space ofdecision trees satisfying leaf constraints. Ourcontribution is that we reduce this classification 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. In experiments we comparethe Bayes optimal predictions with those of the maximum a posteriori hypothesis.status: publishe