CS 159

Lab 1: Tokenization and Segmentation

In this next part of the lab, you will write a simple sentence segmenter.

The /courses/cs159/data/brown/ directory includes three English-language text files taken from the Brown Corpus:

  • editorial.txt
  • fiction.txt
  • lore.txt

These files represent large strings of natural language text, with no line breaks nor other special symbols to annotate where sentence splits occur. In the data set you are working with, sentences can only end with one of 5 characters: period, colon, semi-colon, exclamation point and question mark.

However, there is a catch: not every period represents the end of a sentence. Many abbreviations (U.S.A., Dr., Mon., etc., etc.) that can appear in the middle of a sentence, and the period does not indicate the end of the sentence. (If you have a phone that uses autocomplete to type, you may already have had annoying experiences where it automatically capitalized words after these abbreviations!) These text also has many examples where colon is not the end of the sentence. The other three punctuation marks are all nearly unambiguously the ends of a sentence (yes, even semi-colons).

For each of the above files, we have also provided a file in the same directory containing the character index (counting from 0 for the first character) of each of the actual locations of the ends of sentences:

  • editorial-eos.txt
  • fiction-eos.txt
  • lore-eos.txt

Your job is to write a sentence segmenter, and to output the predicted token number of each sentence boundary.

This part of the assignment will be more open-ended and thus there aren't as many opportunities to test for specific expected outputs. Nonetheless, we still provide some basic tests in test-segmenter.py that check that your functions are following the specified interface (i.e., take the right arguments and return the right type of output). Make sure you pass these basic tests, as the evaluation script you'll be using depends on your code producing correctly-formatted output!

Part 3a: The Segmenter Framework

The given segmenter.py has some starter code, and can be run from the command line. When it’s called from the command line, it takes one required argument and two optional arguments:

$ python segmenter.py --help
usage: segmenter.py [-h] --textfile FILE [--hypothesis_file FILE] 

Sentence Segmenter for NLP Lab

optional arguments:
  -h, --help            show this help message and exit
  --textfile FILE, -t FILE
                        Unlabled text is in FILE.
  --hypothesis_file FILE, -y FILE
                        Write hypothesized boundaries to FILE

Make sure you understand how this code uses the argparse module to process command-line arguments. In addition to the module documentation, you may also find the argparse tutorial useful.

As in the past, all print statements should be in your main() function, which should only be called if segmenter.py is run from the command line.

The segmenter.py starter code imports the tokenize function from the last section.

Confirm that your Python program can open the file /courses/cs159/data/brown/editorial.txt and that your code from the previous part splits it into 63,333 tokens.

Note: Do not filter out punctuation, since those tokens will be exactly the ones we want to consider as potential sentence boundaries!

Part 3b: write_sentence_boundaries

The starter code contains a function called baseline_segmenter that takes a list of tokens as its only argument. It returns a list of tokenized sentences; that is, a list of lists of tokens, with one list per sentence.

>>> baseline_segmenter(tokenize('I am Sam. Sam I am.'))
[['I', 'am', 'Sam', '.'], ['Sam', 'I', 'am', '.']]

Remember that every sentence in our data set ends with one of the five tokens ['.', ':', ';', '!', '?']. Since it’s a baseline approach, baseline_segmenter predicts that every instance of one of these characters is the end of a sentence.

Fill in the function write_sentence_boundaries. This function takes two arguments: a list of lists of tokens (like the one returned by baseline_segmenter) and a pointer to a stream to write output (either an open write-enabled file or stdout). You will need to loop through all of the sentences in the document. For each sentence, you will want to write the index of the last token in the sentence to the filepointer on a new line. Remember that python lists are 0-indexed!

Confirm that when you run baseline_segmenter on the file /courses/cs159/data/brown/editorial.txt, it predicts 3278 sentence boundaries, and that the first five predicted boundaries are at tokens 22, 54, 74, 99, and 131.

Part 3c: Evaluation

To evaluate your system, we have provided you a program called evaluate.py that compares your hypothesized sentence boundaries with the ground truth boundaries. This program will report to you the true positives, true negatives, false positives and false negatives, along with some other metrics (precision, recall, F-measure), which may be new to you. You can run evaluate.py with the -h option to see all of the command-line options that it supports.

If you had run segmenter.py on editorial.txt using the provided baseline segmenter and wrote the results to a file names editorial.hyp, you could then run evaluate.py like so:

python evaluate.py -d /courses/cs159/data/brown/ -c editorial -y editorial.hyp

Confirm that if you this, you get the following results:

TP:    2719 FN:       0
FP:     559 TN:   60055

PRECISION: 82.95%   RECALL: 100.00% F: 90.68%

(A quick aside: this is a good case for why we like to think about F1 score to help reason about acceptable tradeoffs of precision and recall. If only 25% of the punctuation marks we retrieve were true sentence boundaries, we would get recall of 100% still, precision of 25%, and an F1 of 40%: much lower than the arithmetic average of 62.5% we would get from precision and recall. The further either precision or recall gets from 1, the more it affects the F1 score.)

Part 3d: Building a Better Segmenter

Now it’s time to improve the baseline sentence segmenter. We don’t have any false negatives (since we’re predicting that every instance of the possibly-end-of-sentence punctuation marks is, in fact, the end of a sentence), but we have quite a few false positives.

There’s a placeholder for a second segmentation function defined in the starter code. You will fill in that my_best_segmenter function to do a (hopefully!) better job identifying sentence boundaries. The specifics of how you do so are up to you. (If you need inspiration, you may think back to the in-class exercise where you reasoned about edge cases for a tokenizer; a lot of the same logic probably applies here!)

You can see the type of tokens that your system is incorrectly characterizing by setting the verbosity of evaluate.py to something greater than 0 using the command line arguments. Setting it to 1 will print out all of the false positives and false negatives, which will help you identify specific cases that your segmenter is still getting wrong so you can address them (and discuss them in your journal!).

Analysis Question #4

Describe (using the metrics from the evaluation script) the performance of your final segmenter. Specifically, give at least 3 things your final segmenter does better than the baseline segmenter, and at least 3 places where your segmenter still makes mistakes. What cases are you most proud of catching in your segmenter (be specific)? If you had another week to work on this, what would you change? What if you had the whole semester?

IMPORTANT: In part 3(e), you will be asked to run your segmenter "as is" with no further changes. In other words, you are not allowed to make any further changes to my_best_segmenter once you go past this point! If there's still any changes you're just itching to make, make them now; once you move on to Part 3(e), your code is considered "final"...

Part 3e: Your Time to Experiment!

Did you read the above note? At this point, you are not allowed to make any further code changes. Turn back now if you're not ready to commit! Once you're ready, come back here and continue...

In part 3(d), you developed rules for your segmenter by (presumably) looking at cases it got wrong on editorial.txt, fiction.txt, and lore.txt. But how generalizable are the rules you came up with? In this final part of the assignment, you'll explore this question by running your segmenter on other parts of the Brown Corpus you haven't seen up until this point!

The directory /courses/cs159/data/brown-hidden contains additional categories from the Brown Corpus:

  • adventure.txt
  • belleslettres.txt
  • government.txt
  • hobbies.txt
  • news.txt
  • romance.txt

As before, each data file is accompanied by a -eos file that contains the ground-truth end-of-sentence locations.

Pick two of these additional categories and run your segmenter and the evaluation script on them. Just as a reminder of the command-line syntax, if you wanted to run on adventure.txt, you would first run the segmenter as:

python segmenter.py -t /courses/cs159/data/brown-hidden/adventure.txt -y adventure.hyp

Then run the evaluation script as:

python evaluate.py -d /courses/cs159/data/brown-hidden/ -c adventure -y adventure.hyp

Then, answer the following analysis question:

Analysis Question #5

Please paste the metrics (i.e., the output of the evaluation script) for both of the two additional categories you ran on. How do the metrics look compared to the ones from Part 3(d)? Better? Worse? A mix of both? Are there any new edge cases that tripped up your segmenter here that you didn't see while you were developing the rules in Part 3(d)? What might this imply about the generalizability of your segmenter, or of rule-based segmenters overall?

The End!

This is the end of the assignment. Return to the assignment main page for instructions on how to submit your journal.

(When logged in, completion status appears here.)