Solution Set 6 Problem 1: ID3(T,C) T1=SUBTABLE(T,P,Y) = lines 1-6. ENTROPY(C,T1) = -(10/27 log(10/27) + 17/27 log(17/27)) = 0.9510 T2=SUBTABLE(T,P,N) = lines 7-12 ENTROPY(C,T2) = -(20/44 log(20/44) + 24/44 log(24/44)) = 0.9940 AVG_ENTROPY(P,C,T) = (27/71)*0.9510 + (44/71)*0.9940 = 0.9776 T3=SUBTABLE(T,Q,Y) = lines 1-3, 7-9. ENTROPY(C,T3) = (30/39) log(30/39) + (9/39) log(9/39) = 0.7794 T4=SUBTABLE(T,Q,N) = lines 4-6, 10-12 ENTROPY(C,T4) = (32/32) log(32/32) + 0 log 0 = 0. AVG_ENTROPY(Q,C,T) = (39/71) * 0.7794 + (32/71) * 0 = 0.4281 T5=SUBTABLE(T,R,1) = lines 1,4,7,10 ENTROPY(C,T5) = -(6/6 log(6/6) + (0/6) log(0/6)) = 0. T6 = SUBTABLE(T,R,2) = lines 2,5,8,11 ENTROPY(C,T6) = -((30/56) log(30/56) + (26/56) log(26/56)) = 0.9963 T7 = SUBTABLE(T,R,3) = lines 3,6,9,12 ENTROPY(C,T7) = -(0/9 log(0/9) + 9/9 log(9/9)) = 0 AVG_ENTROPY(R,C,T) = 0 + (56/71)*0.9963 + 0 = 0.7858 ENTROPY(C,T) = -((30/71) log(30/71) + (41/71) log(41/71)) = 0.9827 Decide to split on attribute Q. Recursive call: ID3(T4,C) All the instances in T4 have C=Y This is base case 2, therefore construct a leaf labelled "C=Y" This is as far as I asked you to trace the algorithm. The tree at this point is Q | _______N_______|_________Y_________ | | C=Y Not yet constructed. If the algorithm continues, it proceeds as follows. Recursive call: ID3(T3,C) T8=SUBTABLE(T3,P,Y) = lines 1-3 ENTROPY(C,T8) = -((10/14) log(10/14) + (4/14) log(4/14)) = 0.8631 T9=SUBTABLE(T3,P,N) = lines 7-9 ENTROPY(C,T9) = -((20/25) log(20/25) + (5/25) log(5/25)) = 0.7219 AVG_ENTROPY(P,C,T3) = (14/39)*0.8631 + (25/39)*0.7219 = 0.7726 T10=SUBTABLE(T3,R,1) = lines 1,7 ENTROPY(C,T10) = 0. T11 = SUBTABLE(T3,R,2) = lines 2,8 ENTROPY(C,T11) = 0 T12 = SUBTABLE(T3,R,3) = lines 3,9 ENTROPY(C,T12) = 0 Decide to split on R. ID3(C,T10) C is Y on every instance in the table. Base case 2. ID3(C,T11) C is N on every instance in the table. Base case 2. ID3(C,T12) C is Y on every instance in the table. Base case 2. Final tree Q | _______N_______|_________Y_________ | | C=Y R | __________|_________ | | | 1 2 3 | | | C=Y C=N C=Y Problem 2 "I can fish in the stream" S ---- NP ---- Pron ---- "I" | |-- VP ---- VP ---- VG ---- Modal ---- "can" | | | |-- Verb ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Article ---- "the" | |-- Noun ---- "stream" S ---- NP ---- Pron ---- "I" | |-- VP ---- VP ---- VG ---- Verb ---- "can" | | | |---NP ---- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Article ---- "the" | |-- Noun ---- "stream" S ---- NP ---- Pron ---- "I" | |-- VP ---- VG ---- Verb ---- "can" | |---NP ---- NP ---- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Article ---- "the" | |-- Noun ---- "stream" "John put the king of the fish in the stream" 1. S ---- NP ---- Pron ---- "John" | |-- VP ---- VG ---- Verb ---- "put" | |---NP ---- NP ---- Det ---- "the" | | | |-- Noun ---- "king" | |-- PP ---- Prep ---- "of" | |-- NP ---- NP ---- Det ---- "the" | | | |-- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Det ---- "the" | |-- Noun ---- "stream". 2. S ---- NP ---- Pron ---- "John" | |-- VP ---- VG ---- Verb ---- "put" | |-- NP ---- NP ---- NP ---- Det ---- "the" | | | | | |-- Noun ---- "king" | | | |-- PP ---- Prep ---- "of" | | | |-- NP ---- Det ---- "the" | | | |-- Noun ---- "fish" | | -- PP ---- Prep ---- "in" | |-- NP ---- Det ---- "the" | |-- Noun ---- "stream". 3. S ---- NP ---- Pron ---- "John" | |-- VP ---- VP ---- VG ---- Verb ---- "put" | | | |-- NP ---- NP ---- Det ---- "the" | | | | | |-- Noun ---- "king" | | | |-- PP ---- Prep ---- "of" | | | |-- NP ---- Det ---- "the" | | | |-- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Det ---- "the" | |-- Noun ---- "stream". 4. S ---- NP ---- Pron ---- "John" | |-- VP ---- VP ---- VG ---- Verb ---- "put" | | | |-- NP ---- Det ---- "the" | | | |-- Noun ---- "king" | |-- PP ---- Prep ---- "of" | |-- NP ---- NP ---- Det ---- "the" | | | |-- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Det ---- "the" | |-- Noun ---- "stream". 5. S ---- NP ---- Pron ---- "John" | |-- VP ---- VP ---- VP ---- VG ---- Verb ---- "put" | | | | | |---NP ---- Det ---- "the" | | | | | |-- Noun ---- "king" | | | |-- PP ---- Prep ---- "of" | | | |-- NP ---- Det ---- "the" | | | |-- Noun ---- "fish" | |-- PP ---- Prep ---- "in" | |-- NP ---- Det ---- "the" | |-- Noun ---- "stream". These five parses all correspond to the grammar. However, only parse tree (3) is actually grammatical in English. First, in actual English, "of" almost always attaches to an NP; it is allowed to attach to verbs of communication (e.g. "The time has come to talk of many things") but certainly not to "put". That rules out parses (4) and (5). Second, in English, the verb "put" requires some indication of where the object is being put; one can say "I put the box on the table", but not "I put the box." This rules out parses (1), (2), and (4). v