Structured Generative Models for Unsupervised Named-Entity Clustering

Micha Elsner, Eugene Charniak, Mark JohnsonNAACL 2009

TL;DR

This paper introduces a novel unsupervised generative model for clustering named entities, achieving state-of-the-art results on the MUC-7 dataset. By modeling both the internal structure of named entities and their contextual relationships, the system effectively groups mentions of the same entity without requiring any labeled data.

What Problem Does This Paper Address?

Named Entity Recognition (NER) and clustering are crucial tasks in Natural Language Processing (NLP) for identifying and grouping mentions of real-world entities (like people, organizations, and locations) in text. While supervised and semi-supervised methods have achieved high performance, they rely on significant amounts of labeled data. This paper tackles the challenge of performing unsupervised named-entity clustering, aiming to build a system that can group entities without any prior human annotation. This is particularly important for tasks like coreference resolution, where understanding entity relationships is key, and unsupervised methods can be more readily integrated. The authors also highlight the difficulty of accurately matching named entities, especially when they appear in different forms (e.g., "President Clinton" vs. "Bill Clinton"), which requires understanding the role of words within an entity mention.

Methods

The core of this work is a structured generative model built using adaptor grammars. Adaptor grammars are a framework for non-parametric Bayesian inference over context-free grammars, allowing for flexible modeling of structured data.

The model has several key components:

  • Core NP Model: This part models the internal structure of named entities. It uses a grammar where each named entity class (Person, Organization, Location) has associated symbols that represent semantic parts of the name (e.g., titles, first names, last names). These symbols are "adapted" to expand to strings of words, allowing the model to learn collocations and the order of words within an entity.
  • Consistency Model: To enforce consistency between different mentions of the same entity, a "consistency-enforcing grammar" is introduced. This model assumes that two names are consistent if they belong to the same class and don't have conflicting assignments of words to lexical symbols. This is achieved by introducing "entity" nonterminals that enforce a weak notion of consistency.
  • Modifiers, Prepositions, and Pronouns: The model incorporates contextual features derived from Collins and Singer (1999), including nominal modifiers (e.g., "vice president" in "Maury Cooper, a vice president") and prepositional phrases (e.g., "sewage plant in Georgia"). Crucially, it also integrates information from an unsupervised coreference algorithm that models pronoun types, number, and gender. This pronoun information helps disambiguate entities and provides a more robust matching mechanism.

The inference process uses a modified Metropolis-within-Gibbs algorithm, which is adapted to handle the potentially infinite number of entities. To improve mobility and avoid local minima, they employ data merging and run multiple samplers with different initializations.

Datasets

  • MUC-7 Dataset: This is the primary dataset used for evaluation. It's a standard benchmark for named entity recognition and clustering tasks. The authors use the training set for development and the formal test set for final evaluation.
  • North American News Corpus (NANC): This corpus is used to augment the MUC-7 data, providing additional examples of NPs headed by proper nouns. This helps create larger datasets for training and inference.

Key Insights and Ideas

  • Unsupervised Structure Matters: The paper demonstrates that modeling the internal structure of named entities (e.g., the order of titles, names, and suffixes) is crucial for effective unsupervised clustering.
  • Context is King (Even Unsupervised): Incorporating contextual features like modifiers and prepositions significantly boosts performance, showing that external information is vital even without explicit labels.
  • Pronoun Information is Powerful: Leveraging unsupervised pronoun resolution provides a strong signal for entity matching and disambiguation, leading to substantial performance gains.
  • Consistency as a Constraint: The consistency model, which enforces that different mentions of the same entity should have compatible internal structures, is a key innovation for improving clustering quality.
  • Adaptor Grammars for Flexibility: The use of adaptor grammars provides a flexible and principled Bayesian framework for building these complex generative models.

Key Results

  • The proposed unsupervised model achieved an accuracy of 87.1% on the development data when incorporating pronoun features, significantly outperforming previous unsupervised methods.
  • On the MUC-7 test data, the final model achieved an accuracy of 86.0%.
  • The authors report this as the best score for a fully unsupervised model on the MUC-7 dataset and the best score for a generative model.
  • Adding features incrementally (Core NPs without consistency, Core NPs with consistency, Context Features, Pronouns) showed consistent performance improvements.
  • The confusion matrix reveals that "organization" entities are most frequently confused with "location" and "person," while "person" entities are the easiest to identify.

Limitations and Future Work

  • Inference Challenges: The authors acknowledge that their inference process is vulnerable to falling into local minima, especially with a large number of clusters. They are exploring more advanced sampling techniques like split-merge and permutation samplers.
  • Search Errors: The model can make mistakes in parsing, leading to incorrect consistency judgments (e.g., misanalyzing "William F." as a multiword string).
  • Limited Context for Some Models: Some of their earlier models were evaluated only on entities with specific features (prepositional or modifier), whereas their final model labels all entities in the test set.
  • Future Work:
    • Integrating with generative coreference systems for joint inference.
  • Incorporating name-specific features (e.g., abbreviations, family names) into the prior.
  • Developing more robust inference techniques to handle local minima.
  • Exploring how these techniques can improve coreference resolution performance.

Summary updated

BibTeX
@inproceedings{elsner2009structured,
  author = {Micha Elsner and Eugene Charniak and Mark Johnson},
  title = {{Structured Generative Models for Unsupervised Named-Entity Clustering}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure