Entropy as a predictor of phrase boundaries


This is an extra credit assignment due Monday March 14 at 5pm, for which full credit is worth 50% of a homework assignment. For this extra credit assignment, turning the assignment in late will not be accepted.

Dating back to Zellig Harris in the mid 1950s ("From Phoneme to Morpheme", Language 31(2):190-222), authors have noted that there is a correspondence between linguistic bounaries and positions of high entropy, which may be useful for doing automatic segmentation or phrase boundary detection. You can find bunches of references related to this by searching the Web on terms Harris entropy segmentation. (One short example is by David Ward Powers, on Chinese Word Segmentation Based on Contextual Entropy.)

In this assignment, you will implement and explore the idea empirically, using corpus data that I have identified for you in an e-mail message to the class. (These corpora are not publicly available, so please do not redistribute them or link to the file on the Web.) Specifically, let's look at some data and see to what extent points of high entropy seem to correspond to our intuitions about syntactic phrase boundaries.

  1. Take the English training corpus (corpus.train.en) and build an n-gram language model at the word level. For this assignment I want you to get hands-on experience with a language modeling tool widely used in NLP research. For one used frequently in speech recognition and machine translation, I recomment that you use the SRI language modeling toolkit (srilm); other recommendations would include the CMU SALM (suffix array language model) toolkit and the software for Bloom filter language models (David Talbot and Miles Osborne, Smoothed Bloom filter language models: Tera-Scale LMs on the Cheap, EMNLP 2007). Srilm is the most widely used, but the Bloom filter language models are newer, more scalable, and have a greater coolness factor.

    Note that the machine serving the SRILM package appears to be down. There are some alternative suggestions above, plus you could search the Web for "language modeling toolkit" and see what alternatives come up. Feel free to share what you find with the class. Meanwhile I'll see if I can find a download for it somewhere else.

    For this assignment, I don't want you to implement a language model from scratch. The point is to get a state of the art research tool to work and trying it out on some real data. If you have some other state of the art language modeling tools available to you, let me know in advance and I'll decide if it's ok to use it.

  2. Create an output file called english.out.txt where, for each sentence in the English test corpus (corpus.test.mt03.en), you show the entropy at each position, i.e. the entropy of P(Word|context) according to the n-gram model, where P(Word|context) is the distribution over the vocabulary of the next word position given the context. Left-context only (i.e., conditioning on the previous n-1 words) is fine, although if you read some of the background literature you'll see discussion of using right-context also (i.e. building another language model from the end of the sentence to the beginning). For the output file you create, place token <tab> entropy pairs on each line, i.e. one token per line with the entropy for the corresponding position. Separate sentences by blank lines.

  3. Answer this question: Do spikes in entropy indeed tend to correspond to natural segments according to phrase structure? (Your judgments about phrases are fine, but if you want an objective source of phrase boundaries, you can run a parser on the input sentences, e.g. the online Stanford parser.) Illustrate the answer to your question using a few sentences in your output file.

  4. Do the exercise again with Chinese, creating chinese.out.txt and answering the same question as above (and illustrating with a few sentences from the test corpus).

    Note that for the training data, the Chinese is already segmented into words. If you don't know Chinese, that's ok, you can still run your code and answer the question -- you can either get help from a Chinese speaker, or you can use the corresponding English sentences (since corpus.test.mt03.{en,zh} are parallel translations) along with an online translation tool like Google Translate to identify what you think are natural phrases in the Chinese. (Part of the point of this exercise, for non-Chinese speakers, is to get you to play around with working with some data in a language you don't understand. This happens a fair amount in NLP research.)

I encourage you to talk to each other, and to use the mailing list. As on all other homeworks, if you work together with someone, make sure to let me know, and make it clear who contributed what.

To turn in: Send a .tar.gz or .zip file to the TAs following the usual conventions. It should contain code and scripts (with a README so we can run it), your writeup, and the {english,chinese}.out.txt files. You can assume we have our own copies of any software you've downloaded (e.g. a language modeling package). Just make sure you tell us what you used and where you got it, together with any instructions, in your README.