Material Detail

Bayes Optimal Classification for Decision Trees

Bayes Optimal Classification for Decision Trees

This video was recorded at 25th International Conference on Machine Learning (ICML), Helsinki 2008. 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.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.