Source-linked AI summary
Nymble: a High-Performance Learning Name-finder
Daniel M. Bikel, Scott Miller, Richard Schwartz, Ralph Weischedel
TL;DR
Name-finding identifies entity-bearing spans that matter for information extraction and downstream processing. Nymble applies a slightly modified HMM with within-class bigram models; the authors report near-human performance and efficient training, including on Spanish answer keys marked by native speakers.
Problem
Name-finding delimits entity-bearing spans that capture who, where, when, and how-much information and can support further processing.
Source: §2.3 · p. 2Method
Nymble uses a slightly modified HMM with a statistical bigram language model inside each name-class state.
Source: §1 · p. 1, §3.1 · p. 2Results
The authors report near-human performance, often likened to an F of 90 or above, and efficient training, including on Spanish answer keys marked by native speakers.
Source: §6 · p. 8Takeaways & Limitations
The authors conclude that this learned stochastic approach lends credence to using probabilistic finite-state methods for name-finding.
Source: §6 · p. 8The paper identifies a remaining gap between learned and rule-based name-finding systems and proposes lists, aliasing, and longer-distance information as potential improvements.
Source: §5 · p. 8
Abstract
from arXiv · showhide
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
The paper applies a slightly modified hidden Markov model to named-entity recognition in the MUC task. It reports performance above prior published learning name-finders, often at or above 90% accuracy, and training on English and Spanish.
1. Introduction
- Nymble outperforms the best published results of other learning name-finders and often reaches at least 90% accuracy.The authors describe this level as often considered near-human performance.Source: §1 · p. 1
- Nymble is a named-entity recognition system built with a slightly modified hidden Markov model.Source: §1 · p. 1
- The MUC task delimits organization, person, and location names, as well as times, dates, percentages, and money amounts, in text using SGML markup.Source: §1 · p. 1
- The model was trained and used on English and Spanish, with Spanish used for the multilingual entity task.Source: §1 · p. 1
2. Background
The background frames name-finding as identifying entity classes in text and contrasts learned methods with manually written patterns. It also motivates name-finding as both a useful extraction step and a tool for information retrieval.
2.1 Name-finding as an Informationtheoretic Problem
- The model seeks the most likely name-class sequence given the observed words, and maximizing the joint probability suffices because the word-sequence probability is constant for a sentence.Source: §2.1 · p. 1
2.2 Previous Approaches to Name-finding
- Earlier approaches used manually constructed finite-state patterns, requiring new rules for each new language and information class.A Brill-rule variant was also applied to the problem.Source: §2.2 · p. 2
2.3 Interest in Problem and Potential Applications
- Name-finding delimits token sequences that answer who, where, when, and how-much questions, and can serve as a first step toward relating entities or assigning semantics.Source: §2.3 · p. 2
- Name-finding can also support better-formed Internet queries and be used directly for link analysis and other information-retrieval problems.Source: §2.3 · p. 2
3. Model
The paper presents its model first informally and then as a formal HMM, noting a resemblance to work on the ATIS task.
3.1 Conceptual Model
Nymble uses an ergodic HMM whose name-class states contain bigram language models. Its generation scheme conditions class choices and word emissions on classes and neighboring words, while Viterbi decoding searches for the highest-probability assignment.
3.1 Conceptual Model
- The model has eight internal states for name classes, including NOT-A-NAME, plus special START- and END-OF-SENTENCE states.Source: §3.1 · p. 2
- Each name-class state uses a bigram language model with one word per state, so the number of word-states in each class equals vocabulary size V.Source: §3.1 · p. 2
- The model selects classes conditioned on the previous class and word, generates the first word from the current and previous classes, then conditions later words on their immediate predecessor.Source: §3.1 · p. 2
- Viterbi decoding searches possible name-class assignments to maximize the joint probability of the words and classes.Source: §3.1 · p. 2
- If a transition in the interior bigram model was never observed, the trained model backs off to a less powerful model.Source: §3.1 · p. 3
3.2 Words and Word-Features
The model represents words as pairs of lexical items and deterministic word-features, which encode numeric forms, capitalization, and other distinctions. Feature order resolves overlaps, and feature computation is the model’s language-dependent component.
3.2 Words and Word-Features
- Words are represented as pairs of a word and a deterministic word-feature selected from fourteen possible values.Feature computation is roughly ten lines of code and is the model’s language-dependent component.Source: §3.2 · p. 3
- The fourteen features distinguish numeric forms, capitalization types, and other words, including punctuation.The first eight features address monetary amounts, percentages, times, and dates.Source: §3.2 · p. 3
- When feature classes overlap, the listed computation order gives precedence to the earlier feature.For example, containsDigitAndAlpha takes precedence over containsDigitAndDash.Source: §3.2 · p. 3
- Capitalization provides useful name evidence in Roman languages, while the firstWord feature handles sentence-initial capitalization with no clear cause.allCaps and capPeriod are computed before firstWord and therefore take precedence.Source: §3.2 · p. 3
3.3 Formal Model
The formal model generates name-classes and their words using conditional probabilities, estimated from training counts and backed off when observations are sparse. It also uses a held-out unknown-word model and a weighted fallback scheme to address unseen events.
3.3.1 Top Level Model
- The first word of a name-class is generated by factoring its probability into two parts: a name-class transition and a word likelihood.The transition is conditioned on the preceding name-class and word, while the first-word probability uses the current and previous name-classes.Source: §3.3.1 · p. 3
- For Spanish, comma and period usage reverses their English roles, but changing their feature precedence had little effect on decoding.The passage also notes that Spanish organization names often contain lowercase words.Source: §3.3.1 · p. 3
- Subsequent words in a name-class are generated using a bigram probability conditioned on the preceding word and its feature.The model does not condition this probability on the previous word’s feature; the passage motivates this with title words such as “Mr.”Source: §3.3.1 · p. 4
- A special “+end+” word lets the model compute whether a current word is the final word of its name-class.The relevant conditioning uses the previous real word rather than the “+end+” word.Source: §3.3.1 · p. 4
3.3.2 Calculation of Probabilities; 3.3.3 Back-off Models and Smoothing
- Conditional probabilities are estimated from training-event counts, but sparse observations make accurate estimates difficult on new data.The model consequently backs off from its most powerful model to less powerful models and ultimately to unigram probabilities.Source: §3.3.1 · p. 3, §3.3.2 · p. 4, §3.3.3 · p. 4
3.3.3.1 Unknown Words
- For unknown words, a separate model trained on held-out data supplies estimates whenever either word in a bigram is unknown.The training procedure holds out each half of the data in turn, allowing unknown-word likelihoods to use all available training data.Source: §3.3.3.1 · p. 4
3.3.3.2 Further Back-off Models and Smoothing
- The back-off scheme weights the direct probability by λ and the fallback by 1 − λ, with the weight computed on the fly.The method tends to work well with three or four back-off levels; if the models have roughly equal training, its first factor puts all weight on the primary model, and more levels might require more sophisticated smoothing.Source: §3.3.3.2 · p. 5
3.4 Comparison with a traditional HMM
The model uses a bigram language model within each name-class rather than traditional semantic substates. The authors favor this less semantically appealing approach because it works well in practice and avoids presupposing name structure.
3.4 Comparison with a traditional HMM
- Within each name-class, each word-state emits its own word with probability 1, while the bigram model captures word patterns.A traditional alternative could use semantic substates, such as first, middle, and last names for PERSON.Source: §3.4 · p. 5
- The authors choose an n-gram model because such models work remarkably well in practice and do not presuppose a specific structure for names.The passage describes this choice as less semantically appealing than the traditional alternative.Source: §3.4 · p. 5
- Either modeling approach is mathematically valid provided transitions out of each state sum to one.Source: §3.4 · p. 5
3.5 Decoding
The system uses Viterbi decoding to recover the name-class state sequence efficiently. Dynamic programming merges paths that converge on the same state, and the implementation pursues eight theories at each step.
3.5 Decoding
- Viterbi decoding reduces the search from N^m possible state sequences to time linear in sentence length, O(m).The passage attributes this efficiency to dynamic programming and merging theories that converge on a state.Source: §3.5 · pp. 5–6
- The decoding algorithm seeks the optimal state sequence to recover the sentence’s name-class sequence.Source: §3.5 · pp. 5–6
- The system pursues eight theories at every step of the algorithm.Source: §3.5 · p. 6
4. Implementation and Results
Nymble replaces a part-of-speech-mediated representation with direct word features, then evaluates the final system on blind English and Spanish test sets and examines training-data size. The reported results include a higher F-measure than other learned systems and strong performance with reduced training data.
4.1 Development History
- The model shifted from POS-tag back-off to direct word features, including an expanded feature set that modestly improved performance on every test.The change brought capitalization into the model more directly than the earlier POS-tag approach.Source: §4.1 · p. 6
4.2 Current Implementation
- Nymble was implemented in C++ to support rapid experimentation; on a Sparc20 or SGI Indy, it compiled in 10 minutes, trained in 5 minutes, and ran at 6 MB/hour.The paper argues that runtime efficiency enables more experiments and faster performance improvement.Source: §4.2 · p. 6
4.3 Results of evaluation
- The final software was evaluated on held-out blind test sets for English and Spanish.Held-out development sets were also available, but only blind-test results are reported.Source: §4.3 · p. 6
4.3.1 F-measure
- F-measure combines precision and recall as their weighted harmonic mean, with β² typically set to 1.Recall counts hits against possible correct answers; precision measures the correctness of delivered answers.Source: §4.3.1 · p. 6
- Nymble achieved a higher F-measure than any other learned system when compared with state-of-the-art manual systems on similar data.The paper describes this as its result to the authors’ knowledge.Source: §4.3.1 · p. 6
4.3.2 English and Spanish Results
- Table 4.1 compares Nymble’s category-level F-measure scores with the best reported scores for each category.The English test set comprises 30 Wall Street Journal documents; the Spanish test set uses articles from AFP.Source: §4.3.2 · p. 6, Table 4.1 · p. 7
4.3.3 The Amount of Training Data Required
- Using half as much training data produced almost equivalent performance; reducing training to one quarter, approximately 100,000 words, degraded performance slightly, by only about 1–2 percent.At 50,000 words, the decrease was more significant, though performance was still described as impressive.Source: §4.3.3 · p. 7
- For Spanish, performance changed almost not at all when training data fell from 223,000 words to slightly more than 100,000.Figure 4.2 presents the Spanish training-size results; the paper concludes that results in both languages were comparable and that 100,000 words produced performance nearly comparable to handcrafted systems.Source: §4.3.3 · p. 7, Figure 4.2 · p. 8
5. Further Work
Nymble’s authors identify additions they hope will improve performance and help close the gap with rule-based name-finding.
5. Further Work
- The authors propose adding longer-distance information to find names their bigram model misses.They also identify organization, person, and location lists, plus an aliasing algorithm, as possible additions.Source: §5 · p. 8
- Lists of organizations, people, and locations are proposed for incorporation into the current model.Source: §5 · p. 8
- An aliasing algorithm that dynamically updates the model, such as linking IBM to International Business Machines, is another proposed addition.Source: §5 · p. 8
6. Conclusions
The authors conclude that a fairly simple probabilistic model can find MUC-specified names and numerical entities with near-human performance. They present the model as the novel contribution and argue that this example supports exploring probabilistic finite-state methods for NLP.
6. Conclusions
- The authors report that a fairly simple probabilistic model finds MUC-specified names and numerical entities with “near-human performance,” often likened to an F of 90 or above.Source: §6 · p. 8
- Nymble was trained efficiently and, with appropriately and consistently marked answer keys, on Spanish by trainers who did not speak the language.The authors give their own Spanish training as the example.Source: §6 · p. 8
- The authors locate the novelty in the approach to name-finding—the model itself—not in the formalisms or techniques.Source: §6 · p. 8
- The authors argue that this example lends credence to pushing learned, stochastic approaches to find the limits of phenomena captured by probabilistic finite-state methods.Source: §6 · p. 8