6.034 Artificial Intelligence - Recitations, fall 2004 online slides on learning
	Decision Tree Learning Any concept that can be expressed as a propositional statement can be expressed using a decision tree No type of representation is efficient for all kinds of functions How represent $m$ of $n$? Once we know how to use a decision tree, the next question is, how do we automatically construct a decision tree? One possibility: search through the space of all possible decision trees All possible $n$ features at root For each root, $n-1$ possible features at each child $\cdots$ Keep the hypotheses that are consistent with training examples Among these, keep one that satisfies bias Too slow! Another possibility: construct one path for each positive example Not very general Another possibility: find smallest decision tree consistent with all examples Inductive Bias: Occam's Razor