Problem Set 6

Assigned: Nov. 10
Due: Nov. 19.

Problem 1

A. Let D be a data set with three predictive attributes: P, Q, and R and one classification attributes C. Attributes P, Q, and C are Boolean. Attribute R has three values: 1, 2, and 3. The data is as follows

P Q R C Number of
instances.
Y Y 1 Y 1
Y Y 2 N 10
Y Y 3 Y 3
Y N 1 Y 2
Y N 2 Y 11
Y N 3 Y 0
N Y 1 Y 2
N Y 2 N 20
N Y 3 Y 3
N N 1 Y 1
N N 2 Y 15
N N 3 Y 3

Trace the execution of the ID3 algorithm UNTIL REACHING THE FIRST LEAF. At each stage, you should compute the average entropy AVG\_ENTROPY(A,C,T) for each attribute A. (The book calls this "Remainder(A)" (p. 660).)

Problem 2

Consider the following grammar (the same as in the programming assignment):

Grammar

S -> NP VP
NP -> Pronoun
NP -> Name
NP -> Noun
NP -> Article Noun
NP -> NP PP
VP -> VG
VP -> VG NP
VP -> VP PP
VG -> Verb
VG -> Modal Verb
PP -> Prep NP

Lexicon

a -- Article
Amy -- Name
ate -- Verb
can -- Modal, Verb, Noun
fish -- Noun, Verb
had -- Verb
I -- Pronoun
in -- Prep
John -- Name
king -- Noun
put --- Verb
of -- Prep
the -- Article
to -- Prep
stream -- Verb, Noun
swim -- Verb, Noun
swims -- Verb, Noun
Show all the parse trees for the following two sentences: