1 This exercise considers 2 pruning of decision trees (Section 3.5). a. Create a data set with two input attributes, such that the information gain

1 This exercise considers χ2 pruning of decision trees (Section 3.5).

a. Create a data set with two input attributes, such that the information gain at the root of the tree for both attributes is zero, but there is a decision tree of depth 2 that is consistent with all the data. What would χ2 pruning do on this data set if applied bottom up? If applied top down?

b. Modify DECISION-TREE-LEARNING to include χ2-pruning. You might wish to consult Quinlan (1986) or Kearns and Mansour (1998) for details.