📄 A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text

Summary

The paper addresses part-of-speech tagging for arbitrary English text. The motivation comes from applications such as speech synthesis, where pronunciation and stress depend on word class, and from making very large corpora more useful to researchers. Church builds a statistical tagger trained on the hand-annotated Tagged Brown Corpus (about one million words). For each sentence, a linear-time dynamic programming search picks the tag sequence that maximizes the product of two quantities: the probability of each tag given its word, and the probability of each tag given the two neighbouring tags (a trigram model). A second component brackets simple non-recursive noun phrases using learned probabilities of phrase boundaries between tag pairs. The tagger reaches roughly 95–99% accuracy, depending on how correctness is defined. Most remaining errors come from gaps in the lexicon, not from the very simple grammar. The work showed that shallow, frequency-driven models can handle lexical ambiguity in practice, even though n-gram models are known to be inadequate as full grammars.

Key points

• Training data is the Tagged Brown Corpus (~1M words). A 400-word sample in the appendix was judged 99.5% correctly tagged.
• On Brown, the uncertainty of a tag given its word is about 0.25 bits. The uncertainty of a tag given its neighbouring tags is about 2 bits. Lexical ambiguity is therefore smaller than intuition suggests.
• The noun phrase bracketer was trained on about 40,000 words (11,000 noun phrases) of semi-automatically parsed Brown text. Preparing this data took about a man-week, with help from Eva Ejerhed. The bracketer missed only 5 of 243 brackets in the appendix sample.
• A Fidditch-style hand-written disambiguation rule can be replaced by counts. In Brown, the preposition+determiner sequence occurs 43,924 times, while noun+determiner occurs only 1,135 times.
• For comparison, the Lancaster group (Leech, Garside, Atwell) reported 96.7% on the LOB Corpus with a heuristically extended bigram model.

Interesting ideas

• I1. Separate "possible" from "likely". Dictionaries list every conceivable tag for a word, such as "see" as a noun. Corpus frequencies show which readings actually occur. Weighting readings by frequency avoids an explosion of improbable analyses, and the same idea applies to morphological analyzers for richly inflected languages like Ukrainian.
• I2. Smooth with the dictionary. Add one count to every tag a dictionary or morphology module allows. Rare words then keep their unseen but legitimate readings (e.g., "cans" as a verb), while impossible tags stay at zero. This is a cheap way to combine a lexicon with sparse annotated data.
• I3. Turn hand-written rules into statistics. Many diagnostic rules in rule-based parsers can be restated as bigram or trigram preferences. Estimating these from a tagged corpus is far less laborious than writing and debugging the rules by hand.
• I4. Use entropy to measure task difficulty. Comparing conditional entropy of tags given words with tags given context shows where the real ambiguity lies before any model is built. This diagnostic transfers easily to new languages and tagsets.
• I5. Treat capitalized words carefully. Drop rare capitalized lexicon entries, derive counts for capitalized forms from their lowercase versions plus a proper-noun option, and run a prepass that marks proper nouns from adjacent capitalized words or consistent capitalization within a document. This guards against sentence-initial and title-case noise in any corpus.