Solving the “Who’s Mark Johnson Puzzle”: Information Extraction Based Cross Document Coreference

Jian Huang, Sarah M. Taylor, Jonathan L. Smith, Konstantinos A. Fotiadis, C. Lee GilesNAACL 2009

TL;DR

This paper tackles the challenge of identifying the same person across multiple documents, even when they have common names like "Mark Johnson." They introduce a novel approach that leverages advanced information extraction (IE) techniques to understand relationships and attributes of individuals, going beyond simple keyword matching. This IE-driven method leads to more accurate cross-document coreference, a crucial step for building comprehensive knowledge bases from the web.

What Problem Does This Paper Address?

The internet is awash with information, but it's often fragmented and difficult to piece together. A prime example is the ambiguity of common names: searching for "Mark Johnson" can yield dozens of individuals. Cross-Document Coreference (CDC) aims to solve this by linking mentions of the same real-world entity across different documents. This is essential for tasks like building social networks, understanding organizational structures, or creating unified profiles of individuals. Previous CDC methods often relied on simpler techniques like co-occurrence or basic textual similarity, which struggle with the nuances of real-world data and the sheer volume of information. This paper addresses the need for a more sophisticated CDC system that can effectively disambiguate entities, particularly people, by deeply understanding the information within documents.

Methods

The authors propose a framework that first uses an Information Extraction (IE) tool called AeroText to identify named entities (like people) and construct "Within-Document Coreference" (WDC) chains. Crucially, AeroText also extracts relational information between these entities (e.g., employment, family ties, co-locations).

The core of their innovation lies in how they measure the similarity between these WDC chains:

  • Specialist Similarity Functions: They employ a suite of "specialist" functions, each designed to assess similarity based on specific types of extracted information. These include:
  • Text Similarity: Using SoftTFIDF (a combination of TFIDF and Jaro-Winkler distance) for inexact name matching, accounting for variations and errors.
  • Semantic Similarity: Leveraging WordNet and Jiang-Conrath semantic distance to understand relationships where textual overlap is minimal but meaning is similar (e.g., "U.S. President" and "Commander-in-chief").
  • Rule-Based Similarity: Handling specific cases like nicknames, acronyms, and geographical locations.
  • Specialist Exponentiated Gradient (SEG) Learning: To combine the predictions of these specialists, they use the SEG algorithm. This algorithm learns to weight the specialists based on their effectiveness, allowing the system to adapt to the availability of different types of information. A specialist is "awake" only when the relevant information is present for a pair of WDC chains.
  • Density-Based Clustering (DBSCAN): After computing a similarity matrix between WDC chains using the learned specialist weights, they use DBSCAN for clustering. DBSCAN is chosen because it doesn't require a predefined number of clusters (unlike K-means) and is robust to noise, making it suitable for the varied and potentially sparse nature of the data.

Datasets

The authors evaluate their methods on the ACL SemEval-2007 web person search task (WePS) benchmark test collection. This collection comprises three sets of documents:

  1. Wikipedia: Sampled famous people.
  2. ACL 2006 Conference: Computer scientists.
  3. US Census Data: Common names.

For each ambiguous name, the top 100 search results from Yahoo! were annotated by humans, resulting in an average of 45 real-world entities per name and approximately 3,000 documents in total. The WePS annotation makes a simplifying assumption that each document refers to only one real-world person. The authors adapt this by using document labels to annotate WDC chains.

Key Insights and Ideas

  • IE is Key to Disambiguation: The paper strongly argues that moving beyond simple text matching and leveraging structured information extracted by IE tools is crucial for accurate person disambiguation.
  • Specialists for Nuanced Similarity: The idea of using specialized functions for different types of relationships (textual, semantic, rule-based) and then learning how to combine their outputs is a powerful way to handle diverse information.
  • DBSCAN's Advantage for CDC: Choosing a density-based clustering algorithm like DBSCAN avoids the sensitive parameter of "K" (number of clusters), which is a significant practical advantage for real-world CDC tasks where the number of entities is unknown.
  • Trade-off Between Purity and Inverse Purity: The evaluation highlights a common trade-off: increasing purity (correctly grouping entities) can sometimes decrease inverse purity (keeping entities within the same category together), suggesting that finding the right balance is important.

Key Results

The proposed system, referred to as AT-CDC, achieved a macro-averaged F0.5 score of 0.708 on the WePS test sets. This performance is comparable to the top-tier systems in the official SemEval evaluation. The paper also notes that the system's performance is relatively stable across datasets with varying levels of ambiguity (number of entities per name), generally staying within the 0.6 to 0.8 band for the harmonic mean.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • IE Tool Limitations: The effectiveness of their system is dependent on the quality of the IE tool. Developing a general-purpose IE tool that works across diverse document formats and styles remains a challenge.
  • Relationship Matching: Even with perfect extraction, relationships from different documents might be of different types (e.g., family vs. geo-location) and not directly comparable.
  • Complementary Information: They propose incorporating additional information to improve coreference:
  • Context-Aided CDC: Leveraging the context surrounding named entities.
  • Topic-Based CDC: Using document topics to help differentiate ambiguous names (e.g., "Michael Jordan" the basketball player vs. the professor).
  • Feature Development: Improving the set of similarity specialists by leveraging large knowledge bases is a key area for future work.
  • Broader Applicability: While developed for web person search, the methods are applicable to other domains like building structured databases from enterprise documents and news articles.

Summary updated

BibTeX
@inproceedings{huang2009solving,
  author = {Jian Huang and Sarah M. Taylor and Jonathan L. Smith and Konstantinos A. Fotiadis and C. Lee Giles},
  title = {{Solving the “Who’s Mark Johnson Puzzle”: Information Extraction Based Cross Document Coreference}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure