Handling Uncertainty in Information Extraction

Maurice van Keulen, Mena B. HabibURSW 2011

Abstract

Traditional Information Extraction (IE) systems often force deterministic decisions early in the pipeline, leading to error propagation when initial guesses are incorrect. This paper presents a theoretical framework that treats IE as a process of eliminating impossible interpretations rather than finding a single "correct" one. By starting with a complete set of all possible annotations and applying ontological constraints through probabilistic conditioning, the proposed model aims to maintain and manage uncertainty throughout the extraction process.

Introduction: The Problem of Early Commitment

Natural language is inherently ambiguous. For instance, approximately 46% of place names in the GeoNames database refer to multiple locations. Despite this, standard IE systems typically make "hard choices" early on—deciding, for example, that "Paris" is a city before considering context that might suggest it is a person. If this initial classification is wrong, the error cascades through the rest of the data pipeline. This paper addresses the challenge of building systems that "happily deal with doubt" by maintaining a mathematical representation of all possible interpretations until sufficient evidence is gathered to narrow them down.

The "Sherlock Holmes" Extraction Framework

The authors propose an approach inspired by the famous quote: "When you have eliminated the impossible, whatever remains, however improbable, must be the truth." The framework operates on four key pillars:

  1. The "No Knowledge" Starting Point: Unlike standard extractors that start with an empty set of results, this model starts with a "complete" set. Every possible substring in a sentence is initially considered a potential candidate for every entity type in the ontology.
  2. Uncertain Annotation Model: Annotations are treated as random variables in a probabilistic database (specifically referencing the MayBMS system).
  3. Knowledge as Conditioning: The user or developer defines an ontology with constraints, such as the dnc ("does not contain") relation.
  4. Probability Redistribution: When a constraint is applied, the system performs "conditioning." It removes the impossible scenarios (e.g., where a phrase is both a Person and a City) and redistributes their probability mass among the remaining valid interpretations.

Illustrating Complexity: The Paris Hilton Example

To demonstrate the complexity of overlapping annotations, the authors use the sentence: "Paris Hilton stayed in the Paris Hilton."

Overlapping candidate annotations for the sentence 'Paris Hilton stayed in the Paris Hilton'.

In this example, phrases like "Paris," "Hilton," and "Paris Hilton" overlap, creating a dense web of dependencies. The initial set of all possible annotations (labeled a1 through a28) grows linearly with text length, but the number of potential combinations of these annotations can grow exponentially, leading to a "combinatorial explosion."

Ontological Constraints and Pruning

The pruning process relies on a defined ontology. Constraints such as the "does not contain" (dnc) relation allow the system to eliminate impossible configurations. For example, a rule might state that a Person entity cannot contain a City entity.

Example ontology with 'does not contain' (dnc) and 'is-a' (isa) relations.

Applying these rules transforms the extraction task from "finding a needle in a haystack" to "pruning the haystack" itself. The vision is an interactive loop where a developer adds ontological knowledge, and the system immediately shows how that knowledge cleans up the uncertain data by adjusting probabilities.

Challenges and Future Directions

The primary hurdle identified is computational complexity. A single rule applied to a short sentence can result in a massive state space—the authors estimate up to $2^{56}$ possible cases to track in some scenarios. While the starting point is scalable, the subsequent conditioning is computationally expensive.

The authors point toward two potential solutions for the scaling problem:

  • Using the conditioning techniques found in the MayBMS probabilistic database.
  • Exploring shared correlations, a method for managing dependencies more efficiently in large-scale probabilistic data.

As a conceptual position paper, this work formalizes the Uncertain Annotation Model, proving that while the initial set of annotations is manageable, the real work lies in optimizing the conditioning process to make this "doubt-friendly" IE system a practical reality.

Summary updated

BibTeX
@inproceedings{keulen2011handling,
  author = {Maurice van Keulen and Mena B. Habib},
  title = {{Handling Uncertainty in Information Extraction}},
  booktitle = {URSW},
  year = {2011},
}
Figure