Assignment 5

To do:

• Do Jurafsky and Martin, Exercise 3.6 (FST for Soundex). Turn in a hardcopy showing your FST as a state machine.

• Find three names, e.g. from recent news coverage, that could be spelled (or misspelled) in at least two different ways, and simulate your Soundex FST by hand on the inputs. For each spelling variant, show (a) the sequence of states and (b) the output of the FST. For example (don't use this one!): "Reznick" and "Resnik" would both have output R252.

• Suppose you had partially part-of-speech tagged training data for a large corpus of English. How might one adapt the Forward-Backward algorithm for training an HMM-based POS tagger in order to take advantage of this information?

  This is actually a question that might be of practical interest. For example, you could imagine one of the following scenarios:

  • Someone has tagged all the unambigious words (e.g. "the", "happily", "destruction", etc.)
  • Someone has tagged all the nouns.
  • Someone has run an automatic POS tagger and gone through the output by hand, keeping the tags they quickly agree with and removing the tags where it's not a fast, easy decision.

  Please make your answer as specific as possible. E.g., referring to specific aspects of the algorithm (or, even better, stating a revised algorithm) is worth more than stating your answer at a high level -- the less general and vague you are, the better.

  In fact, let me be more specific myself: you can get full credit by repeating back the original statement of the algorithm with relatively small modifications to the forward and backward equations.

  You may wish to wait until after Rebecca Hwa's guest lecture Wednesday to do this one.