A Graph-Based Approach to Named Entity Categorization in Wikipedia Using Conditional Random Fields

Yotaro Watanabe, Masayuki Asahara, Yuji MatsumotoEMNLP 2007

TL;DR

This paper introduces a novel graph-based approach to categorize named entities (NEs) in Wikipedia by leveraging the rich HTML structure of articles. By modeling anchor texts and their relationships as a graph and using Conditional Random Fields (CRFs) with a novel approximate inference method, the authors achieve significant improvements over traditional methods.

What Problem Does This Paper Address?

Named Entity Recognition (NER) is a fundamental task in Natural Language Processing (NLP) that aims to identify and classify named entities (like persons, locations, organizations) in text. While machine learning methods have advanced NER, they often struggle with the vastness and ambiguity of real-world text. Gazetteers (lists of known entities) can help, but they are incomplete. Wikipedia, with its extensive collection of articles, offers a rich source of NE information. However, simply treating each Wikipedia article independently for NE categorization misses the valuable structural information and interdependencies present in hyperlinked texts. This paper addresses the challenge of effectively utilizing Wikipedia's inherent structure to improve NE categorization by modeling relationships between anchor texts.

Methods

The core of this paper is a graph-based approach using Conditional Random Fields (CRFs). Here's a breakdown of their methodology:

  • Graph Construction: Anchor texts within Wikipedia articles are treated as nodes in a graph. Edges are defined based on three types of relationships derived from the HTML tree structure of the articles:
  • Sibling: Anchor texts appearing in the same list item.
  • Cousin: Anchor texts sharing a common ancestor at a certain depth.
  • Relative: A more complex relationship involving grandchild-parent structures. These relationships are formalized as "cliques" in the CRF model, allowing the model to capture dependencies between related anchor texts.

  • Conditional Random Fields (CRFs): CRFs are used to model the conditional probability distribution of NE categories given the observed features. The graph structure allows for the incorporation of these inter-dependencies into the CRF model.

  • Approximate Inference: Since the constructed graphs can contain cycles (loops), exact inference in CRFs becomes computationally expensive. The authors employ Tree-based Reparameterization (TRP), an approximate inference method, to efficiently compute marginal probabilities.
  • Feature Engineering: A variety of features are used, including textual features of anchor texts, their surrounding text, HTML tags, and relationships between labels of connected nodes.

Datasets

The dataset used in this research is derived from the Japanese version of Wikipedia.

  • Source: Approximately 2300 articles from Wikipedia as of October 2005.
  • Annotation: Anchor texts appearing under HTML <LI> tags were hand-annotated with NE class labels.
  • Labeling Guideline: The Extended Named Entity Hierarchy was used, but reduced to 13 classes to mitigate data sparseness.
  • Data Size: The dataset consists of 16,136 anchor texts with 14,285 NEs. The number of Sibling, Cousin, and Relative edges are |Es| = 4925, |Ec| = 13134, and |ER| = 746, respectively.

Key Insights and Ideas

  • Leveraging HTML Structure is Crucial: The paper strongly demonstrates that the hierarchical and linked structure of Wikipedia's HTML is a rich source of information for NE categorization, going beyond just the text content.
  • Dependencies Matter: Modeling dependencies between anchor texts (via graph structures like Sibling, Cousin, Relative) significantly improves categorization performance compared to treating each anchor text independently.
  • Cousin Cliques are Particularly Powerful: The "Cousin" relationship, which captures shared attributes among entities, provided the most significant accuracy improvement among the defined clique types. This highlights the importance of identifying entities that share common characteristics.
  • Dependency Information Helps Even Without Glosses: The "ALL (no articles)" row in Table 3 shows that dependency information is beneficial even for NEs that lack explicit gloss texts, suggesting its utility in inferring categories from context.
  • Marginal Probability for Confidence: The marginal probability of MAP assignments can be effectively used as a confidence measure for entity categorization, allowing for filtering and potentially improving precision.

Key Results

  • Significant Improvement: The proposed graph-based CRF models achieved significant improvements compared to baseline models using Support Vector Machines (SVMs).
  • Best Performing CRF Model: The "CR" model (which includes Cousin cliques) achieved the best F1-value among all CRF models.
  • Comparison with SVMs: The best CRF model (CR) outperformed the best SVM model (P) in terms of F1-value, with the difference being statistically significant (p < 0.01).
  • Class-Specific Performance: For classes with a larger number of examples (e.g., PERSON, PRODUCT, LOCATION), CRF models generally outperformed SVMs.
  • Precision-Recall Trade-off: A precision-recall curve showed that by varying a threshold on the marginal probability, it's possible to achieve high precision (0.97) at a reasonable recall (0.57), indicating effective filtering of NE candidates.
  • Training Time: While CRF training times were generally longer than SVMs, especially for models with complex graph structures (like SCR), the performance gains justified the computational cost.

Limitations and Future Work

  • Data Sparseness: The authors acknowledge that reducing the number of classes was necessary to avoid data sparseness, implying that a very fine-grained label set might be challenging with the current approach.
  • Parameter Tying: Attempts to tie SCR potential functions with particular observation features did not yield improved accuracy, suggesting that further exploration in this area might be needed.
  • Future Work:
    • More Fine-Grained Labels: Exploring NE categorization with a more extensive and fine-grained label set is a key future direction. This will likely require addressing the challenge of insufficient positive examples for a large number of classes.
  • Active Learning: The marginal probability can be used as a confidence estimator for active learning, where uncertain examples are selected for human annotation.
  • NLP Applications: The authors envision NE dictionaries with fine-grained labels being useful for NLP applications like Question Answering (QA).

Summary updated

BibTeX
@inproceedings{watanabe2007graph,
  author = {Yotaro Watanabe and Masayuki Asahara and Yuji Matsumoto},
  title = {{A Graph-Based Approach to Named Entity Categorization in Wikipedia Using Conditional Random Fields}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure