22.1.2 NER as Sequence Labeling

The standard way to approach the problem of named entity recognition is as a word-by-word sequence labeling task, where the assigned tags capture both the boundary and the type of any detected named entities. Viewed in this light, named entity recognition looks very much like the problem of syntactic base-phrase chunking. In fact, the dominant approach to NER is based on the same statistical sequence labeling techniques introduced in Ch. 5 for part of speech tagging and Ch. 13 for syntactic chunking.

In the sequence labeling approach to NER, classifiers are trained to label the tokens in a text with tags that indicate the presence of particular kinds of named entities. This approach makes use of the same style of IOB encoding employed for syntactic chunking. Recall that in this scheme an I is used to label tokens inside of a chunk, B is used to mark the beginning of a chunk, and O labels tokens outside any chunk of interest. Consider the following sentence from our running example.

[ORG American Airlines], a unit of [ORG AMR Corp.], immediately matched the move, spokesman [PERS Tim Wagner] said.

This bracketing notation provides us with the extent and the type of the named entities in this text. Fig. 22.5 shows a standard word-by-word IOB-style tagging that captures the same information. As with syntactic chunking, the tagset for such an encoding consists of 2 tags for each entity type being recognized, plus 1 for the O tag outside any entity, or $ (2 \times N) + 1 $ tags.

Having encoded our training data with IOB tags, the next step is to select a set of features to associate with each input example (i.e. each of the tokens to be labeled in Fig. 22.5). These features should be plausible predictors of the class label and should be easily and reliably extractable from the source text. Recall that such features can be based not only on characteristics of the token to be classified, but also on the text in a surrounding window as well.

Fig. 22.6 gives a list of standard features employed in state-of-the-art named entity recognition systems. We've seen many of these features before in the context of part-of-speech tagging and syntactic base-phrase chunking. Several, however, are particularly important in the context of NER. The shape feature includes the usual upper case, lower case and capitalized forms, as well as more elaborate patterns designed to capture expressions that make use of numbers (A9), punctuation (Yahoo!) and atypical case alternations (eBay). It turns out that this feature by itself accounts for a considerable part of the success of NER systems for English news text. And as we'll see in Sec. 22.5, shape features are also particularly important in recognizing names of proteins and genes in biological texts. Fig. 22.7 describes some commonly employed shape feature values.

The presence in a named entity list feature can be very predictive. Extensive

| Words | Label |

| --- | --- |

| American Airlines, a unit of AMR Corp., immediately matched the move, spokesman Tim Wagner said. | $ B_{ORG} $\n $ I_{ORG} $\nO\nO\nO\n $ B_{ORG} $\n $ I_{ORG} $\nO |

lists of names for all manner of things are available from both publicly available and commercial sources. Lists of place names, called gazetteers, contain millions of entries for all manner of locations along with detailed geographical, geologic and political information. $ ^{1} $ The United States Census Bureau provides extensive lists of first names and surnames derived from its decadal census in the U.S. $ ^{2} $ Similar lists of corporations, commercial products, and all manner of things biological and mineral are also available from a variety of sources.

This feature is typically implemented as a binary vector with a bit for each available kind of name list. Unfortunately, such lists can be difficult to create and maintain, and their usefulness varies considerably based on the named entity class. It appears that gazetteers can be quite effective, while extensive lists of persons and organizations are not nearly as beneficial (Mikheev et al., 1999).

Finally, features based on the presence of predictive words and N-grams in the context window can also be very informative. When they are present, preceding

and following titles, honorifics, and other markers such as Rev., MD and Inc. can accurately indicate the class of an entity. Unlike name lists and gazetteers, these lists are relatively short and stable over time and are therefore easy to develop and maintain.

The relative usefulness of any of these features, or combination of features, depends to a great extent on the application, genre, media, language and text encoding. For example, shape features, which are critical for English newswire texts, are of little use with materials transcribed from spoken text via automatic speech recognition, materials gleaned from informally edited sources such as blogs and discussion forums, and for character-based languages like Chinese where case information isn't available. The set of features given in Fig. 22.6 should therefore be thought of as only a starting point for any given application.

Once an adequate set of features has been developed, they are extracted from a representative training set and encoded in a form appropriate to train a machine learning-based sequence classifier. A standard way of encoding these features is to simply augment our earlier IOB scheme with more columns. Fig. 22.8 illustrates the result of adding part-of-speech tags, syntactic base-phrase chunk tags, and shape

| Features | Label | | | |

| --- | --- | --- | --- | --- |

| American Airlines, a | NNP | $ B_{NP} $ | cap | $ B_{ORG} $ |

| NNPS | $ I_{NP} $ | cap | $ I_{ORG} $ | |

| PUNC | O | punc | O | |

| DT | $ B_{NP} $ | lower | O | |

| unit of AMR Corp. | NN | $ I_{NP} $ | lower | O |

| IN | $ B_{PP} $ | lower | O | |

| NNP | $ B_{NP} $ | upper | $ B_{ORG} $ | |

| NNP | $ I_{NP} $ | cap_punc | $ I_{ORG} $ | |

| PUNC | O | punc | O | |

| immediately matched the move, | RB | $ B_{ADVP} $ | lower | O |

| VBD | $ B_{VP} $ | lower | O | |

| DT | $ B_{NP} $ | lower | O | |

| NN | $ I_{NP} $ | lower | O | |

| PUNC | O | punc | O | |

| spokesman Tim Wagner said. | NN | $ B_{NP} $ | lower | O |

| NNP | $ I_{NP} $ | cap | $ B_{PER} $ | |

| NNP | $ I_{NP} $ | cap | $ I_{PER} $ | |

| VBD | $ B_{VP} $ | lower | O | |

| PUNC | O | punc | O | |

information to our earlier example.

Given such a training set, a sequential classifier can be trained to label new sentences. As with part-of-speech tagging and syntactic chunking, this problem can be cast either as Markov-style optimization using HMMs or MEMMs as described in Ch. 6, or as a multi-way classification task deployed as a sliding-window labeler as described in Ch. 13. Figure Fig. 22.9 illustrates the operation of such a sequence labeler at the point where the token Corp. is next to be labeled. If we assume a context window that includes the 2 preceding and following words, then the features available to the classifier are those shown in the boxed area. Fig. 22.10 summarizes the overall sequence labeling approach to creating a NER system.