📄 Early results for Named Entity Recognition with Conditional Random Fields, Feature Induction and Web-Enhanced Lexicons

Summary

The paper tackles named entity recognition on the CoNLL-2003 shared task, which covers English and German news with PERSON, LOCATION, ORGANIZATION and MISC labels. It asks two practical questions: which feature combinations a Conditional Random Field should actually use, and where task-relevant word lists can be found. For the first, the authors adapt the Della Pietra et al. likelihood-gain feature induction from joint to conditional sequence models. Several approximations keep the search cheap enough to run. For the second, they introduce WebListing. This method takes entity seeds from the labeled data and expands them into large lexicons by exploiting HTML formatting regularities, implemented through GoogleSets. Built in only a few person-weeks, the system reaches 84.04% F1 on the English test set using roughly 6.4 thousand induced features. A fixed-conjunction baseline with about a million features scores far lower. German, which had only a handful of small lexicons, reaches 68.11%. The work shows that selecting features automatically can make models both more accurate and much more compact.

Key points

• Results on CoNLL-2003 test sets: English F1 is 84.04% with 6423 features, and German F1 is 68.11%. A baseline using fixed conjunction patterns gets F1 73.34% with about 1 million features.

• Induction starts from an empty model. Each round proposes candidates, which are single atomic tests or pairwise conjunctions with tests and existing features. The highest-gain candidates are added, and weights are retrained with L-BFGS.

• Two shortcuts make gain estimation tractable:

  • A mean-field approximation turns the sequence problem into per-token classification.
  • Only tokens the current model mislabels are scored.
  • Newton's method then finds each candidate's weight in about 12 iterations.

• English used several feature families, all applied in a window of −2 to +2:

  • the word itself;
  • 16 character-level regex patterns for capitalization and digits;
  • 8 hand-made lexicons;
  • 15 lexicons taken from specific websites;
  • 25 WebListing lexicons;
  • "firstmention" copies of these tests.

  German used only 5 small lexicons, with character bi- and tri-grams added instead.

• Setup: a first-order CRF implemented in Java took roughly 12 hours to train on a 1GHz Pentium machine, with Gaussian prior variance 0.5. Each round added at most 1000 features (gain threshold 5.0) and ran 10 L-BFGS iterations.

Interesting ideas

• I1. Grow features instead of enumerating all conjunctions. Adding only conjunctions that clearly raise conditional log-likelihood keeps the model small. It also lets designers propose a very large pool of atomic tests and wide context windows without a memory blowup. This is useful wherever feature templates explode, for example in morphologically rich languages.
• I2. Score candidates only on current errors. Most tokens are already labeled correctly early in training, so restricting the gain computation to mislabeled tokens saves a lot of time. This error-focused trick could carry over to other incremental feature or rule selection loops.
• I3. Add many features per round and stop training early. The authors add a batch of top-gain features at once, accepting some redundancy. They also run only a few optimizer iterations between rounds to limit overfitting. This is a pragmatic balance of speed and regularization for any greedy model-building procedure.
• I4. Expand lexicons from training seeds using web list formatting. Entities seen in labeled data serve as seeds. Other items that appear in the same HTML list structure are harvested as new lexicon entries. This is a cheap way to build domain gazetteers, such as sports teams or parties, for lower-resource languages, provided a suitable list-expansion tool exists for that language.
• I5. Use "first mention" features. Copying a word's features from its earlier capitalized occurrence in the document passes context from an unambiguous mention to later ambiguous ones. This document-level consistency trick is simple to add to any token tagger.