Decision Trees

• A decision tree consists of interior nodes and leaves, as with any tree:
  • Interior nodes contain a single feature which can either be true or false.
  • Leaf nodes contain a single category label. (Multiple leaf nodes can correspond to the same category.)
  • When an example is presented to an interior node:
    • The feature value for that example is checked.
    • If it is true, send the example to the left child.
    • If it is false, send the example to the right child.
  • When an example is presented to a leaf node:
    • The algorithm returns, with the leaf’s label as the example’s label.
• Inductive bias of decision trees:
  • Occam’s Razor:
    • “Plurality must not be posited without necessity.”
  • For decision trees, avoid a “plurality” of nodes.

Learning Decision Trees

• Start with a single root node containing all training examples.
• While there are any leaf nodes containing examples with different labels:
  • Arbitrarily select a feature for which some examples have different values.
    • If no such feature exists, assign the plurality label to the leaf node.
  • Replace the current leaf node with an interior node and two child leaf nodes.
    • Use the arbitrarily selected feature as the interior node’s feature.
    • Place all examples where the feature is false in the left child.
    • Place all other examples in the right child.

Computational Complexity

• How do we measure input size?
• What if we want the aboslute minimum tree nodes?