An Effective Two-Stage Model for Exploiting Non-Local Dependencies in Named Entity Recognition

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 1121–1128, Sydney, July 2006. c⃝2006 Association for Computational Linguistics An Effective Two-Stage Model for Exploiting Non-Local Dependencies in Named Entity Recognition Vijay Krishnan Computer Science Department Stanford University Stanford, CA 94305 vijayk@cs.stanford.edu Christopher D. Manning Computer Science Department Stanford University Stanford, CA 94305 manning@cs.stanford.edu Abstract This paper shows that a simple two-stage approach to handle non-local dependen- cies in Named Entity Recognition (NER) can outperform existing approaches that handle non-local dependencies, while be- ing much more computationally efficient. NER systems typically use sequence mod- els for tractable inference, but this makes them unable to capture the long distance structure present in text. We use a Con- ditional Random Field (CRF) based NER system using local features to make pre- dictions and then train another CRF which uses both local information and features extracted from the output of the first CRF. Using features capturing non-local depen- dencies from the same document, our ap- proach yields a 12.6% relative error re- duction on the F1 score, over state-of-the- art NER systems using local-information alone, when compared to the 9.3% relative error reduction offered by the best systems that exploit non-local information. Our approach also makes it easy to incorpo- rate non-local information from other doc- uments in the test corpus, and this gives us a 13.3% error reduction over NER sys- tems using local-information alone. Ad- ditionally, our running time for inference is just the inference time of two sequen- tial CRFs, which is much less than that of other more complicated approaches that directly model the dependencies and do approximate inference. 1 Introduction Named entity recognition (NER) seeks to lo- cate and classify atomic elements in unstructured text into predefined entities such as the names of persons, organizations, locations, expressions of times, quantities, monetary values, percent- ages, etc. A particular problem for Named En- tity Recognition(NER) systems is to exploit the presence of useful information regarding labels as- signed at a long distance from a given entity. An example is the label-consistency constraint that if our text has two occurrences of New York sepa- rated by other tokens, we would want our learner to encourage both these entities to get the same la- bel. Most statistical models currently used for Named Entity Recognition, use sequence mod- els and thereby capture local structure. Hidden Markov Models (HMMs) (Leek, 1997; Freitag and McCallum, 1999), Conditional Markov Mod- els (CMMs) (Borthwick, 1999; McCallum et al., 2000), and Conditional Random Fields (CRFs) (Lafferty et al., 2001) have been successfully em- ployed in NER and other information extraction tasks. All these models encode the Markov prop- erty i.e. labels directly depend only on the labels assigned to a small window around them. These models exploit this property for tractable com- putation as this allows the Forward-Backward, Viterbi and Clique Calibration algorithms to be- come tractable. Although this constraint is essen- tial to make exact inference tractable, it makes us …

Content truncated to 500 words