Description
5. Consider a learning problem where the examples are described by n Boolean attributes,
and the hypothesis space is the space of all Boolean functions on n variables. How many
distinct examples (feature vectors) can you have in this setting? (9/18)
6. Consider the same setting as above. How many distinct decision trees can you construct
in this setting? “Distinct” means that each tree must represent a different hypothesis in
the space. Give a rigorous justification for your answer. (9/18)
7. Consider the following table of examples over Boolean attributes, annotated with the
target concept’s label. Ignore the “Weight” column and use information gain to find the
first split in a decision tree (remember that ID3 stops if there is no information gain).
(9/18)
8. Now from the same table, find another split using “weighted” information gain. In this
case, instead of counting the examples for each label in the information gain calculation,
add the numbers in the Weight column for each example. (9/18)
9. Is there a difference between the splits for Q7 and Q8? Can you explain what is
happening? (9/18)
A1 A2 A3 A4 Label Weight
F F F F 0 1/256
F F F T 0 3/256
F F T F 1 3/256
F F T T 1 9/256
F T F F 1 3/256
F T F T 1 9/256
F T T F 0 9/256
F T T T 0 27/256
T F F F 1 3/256
T F F T 1 9/256
T F T F 0 9/256
T F T T 0 27/256
T T F F 0 9/256
T T F T 0 27/256
T T T F 1 27/256
T T T T 1 81/256