Question 3. Decision Tree Consider the following training set, where X = {0,1}* and Y = {0,1}: (1 1 1 1), 1) (O 1 0 1), 1) (O 1 1 0), 1) ((1 1 0 0), 1) (O 1 1 1), 0) (1 0 1 0), 0) (1 001), 0) (0000), 0) a) Suppose we run the ID3 algorithm up to depth 3. Assume that the subroutine used to measure the quality of each feature is based on information gain, and that if two features get the same score, one of them is picked arbitrarily. Show that the training error of the resulting decision tree is at least 1/8. [8 marks] b) Find a decision tree of depth 3 that attains zero training error. [7 marks] Question 3. Decision Tree Consider the following training set, where X = {0,1}* and Y = {0,1}: (1 1 1 1), 1) (O 1 0 1), 1) (O 1 1 0), 1) ((1 1 0 0), 1) (O 1 1 1), 0) (1 0 1 0), 0) (1 001), 0) (0000), 0) a) Suppose we run the ID3 algorithm up to depth 3. Assume that the subroutine used to measure the quality of each feature is based on information gain, and that if two features get the same score, one of them is picked arbitrarily. Show that the training error of the resulting decision tree is at least 1/8. [8 marks] b) Find a decision tree of depth 3 that attains zero training error. [7 marks]