Solutions to the problem sets should be turned in at the beginning of class on the dates indicated. You may work on these problems in groups of two. (In fact, you are encouraged to do so.) Just put two names on the paper when you submit it.
-
1. Due on February 2nd. Problem 2.6 from J&M: Write an FSA for time-of-day expressions like eleven o’clock, twelve-thirty, midnight, or a quarter to ten, and others.
-
2. Due on February 9th. Problem 3.3 from J&M: Write a transducer(s) for the K insertion spelling rule in English. (Note: Use Figure 3.17 for a model. See also Slide 48 from Lecture 02. The spelling rules are shown on p. 63 and on Slide 47.)
-
3. Due on February 16th. Problem 5.7 from J&M: Recall that the Church (1988) tagger is not an HMM tagger since it incorporates the probability of the tag given the word:
P(tag|word) * P(tag|previous n tags) (5.59)
rather than using the likelihood of the word given the tag, as an HMM tagger does:
P(word|tag) * P(tag|previous n tags) (5.60)
Interestingly, this use of a kind of “reverse likelihood” has proven to be useful in the modern log-linear approach to machine translation (see page 903). As a gedanken-experiment, construct a sentence, a set of tag transition probabilities, and a set of lexical tag probabilities that demonstrate a way in which the HMM tagger can produce a better answer than the Church tagger, and create another example in which the Church tagger is better.
-
4. Due on February 23rd. (1) Problem 6.1 from J&M: Implement the Forward algorithm and run it with the HMM in Fig. 6.3 to compute the probability of the observation sequences 331122313 and 331123312. (2) Problem 6.2 from J&M: Implement the Viterbi algorithm and run it with the HMM in Fig. 6.3 to compute the most likely weather sequences for each of the two observation sequences above, 331122313 and 331123312. (Note: Figure 6.3 is reproduced on Slide 33 from Lecture 05.)
-
5. Due on March 2nd. (1) Problem 12.6 from J&M: Assume a grammar that has many VP rules for different subcategorizations, as expressed in Section 12.3.5, and differently subcategorized verb rules like Verb-with-NP-complement. How would the rule for postnominal relative clauses [at the bottom of page 397] need to be modified if we wanted to deal properly with examples like the earliest flight that you have? Recall that in such examples the pronoun that is the object of the verb get. Your rules should allow this noun phrase but should correctly rule out the ungrammatical S: * I get. (2) Problem 12.7 from J&M: Does your solution to the previous problem correctly model the NP: the earliest flight that I can get? How about: the earliest flight that I think my mother wants me to book for her? Hint: this phenomena is called long-distance dependency.
-
6. Due on March 9th. Problem 14.4 from J&M: Fill out the rest of the probabilistic CKY chart in Fig. 14.4. (Note: Figure 14.4 is reproduced on Slide 22 from Lecture 07.)
