Nymble: a High-Performance Learning Name-finder

Nymble: a High-Performance Learning Name-finder Daniel M. Bikei BBN Corporation 70 Fawcett Street Cambridge, MA 02138 dbikel@bbn.com Scott Miller BBN Corporation 70 Fawcett Street Cambridge, MA 02138 szmiller@bbn.com Richard Schwartz BBN Corporation 70 Fawcett Street Cambridge, MA 02138 schwartz@bbn.com Ralph Weischedel BBN Corporation 70 Fawcett Street Cambridge, MA 02138 weisched@bbn.com Abstract This paper presents a statistical, learned approach to finding names and other non- recursive entities in text (as per the MUC-6 definition of the NE task), using a variant of the standard hidden Markov model. We present our justification for the problem and our approach, a detailed discussion of the model itself and finally the successful results of this new approach. 1. Introduction In the past decade, the speech recognition commu- nity has had huge successes in applying hidden Markov models, or HMM's to their problems. More recently, the natural language processing community has effectively employed these models for part-of- speech tagging, as in the seminal (Church, 1988) and other, more recent efforts (Weischedel et al., 1993). We would now propose that HMM's have success- fully been applied to the problem of name-finding. We have built a named-entity (NE) recognition system using a slightly-modified version of an HMM; we call our system "Nymble". To our knowledge, Nymble out-performs the best published results of any other learning name-finder. Further- more, it performs at or above the 90% accuracy level, often considered "near-human performance". The system arose from the NE task as specified in the last Message Understanding Conference (MUC), where organization names, person names, location names, times, dates, percentages and money amounts were to be delimited in text using SGML-markup. We will describe the various models employed, the methods for training these models and the method for "decoding" on test data (the term "decoding" borrowed from the speech recognition community, since one goal of traversing an HMM is to recover the hidden state sequence). To date, we have successfully gained and used the model on both English and Spanish, the latter for MET, the multi-lingual entity task. 2. Background 2.1 Name-finding as an Information- theoretic Problem The basic premise of the approach is to consider the raw text encountered when decoding as though it had passed through a noisy channel, where it had been originally marked with named entities. ~ The job of the generative model is to model the original process which generated the name-class-annotated words, before they went through the noisy channel. More formally, we must find the most likely sequence of name-classes (NC) given a sequence of words (W): Pr(NC I W) (2.1) In order to treat this as a generative model (where it generates the original, name-class-annotated words), we use Bayes' Rule: Pr(NC [ W)- Pr(W, NC) (2.2) Pr(W) and since the a priori probability of the word sequence--the denominator--is constant for any given sentence, we can maxi-mize Equation 2,2 by maximizing the numerator alone. 1 See (Cover and Thomas, 1991), ch. 2, for an excellent overview of the principles of information theory. 194 2.2 Previous …

Content truncated to 500 words