Open Information Extraction with Tree Kernels

Ying Xu, Mi-Young Kim, Kevin Quinn, Randy Goebel, Denilson BarbosaNAACL 2013

TL;DR

This paper tackles the challenge of Open Information Extraction (Open IE) by proposing a novel approach that goes beyond traditional verb-centric relation extraction. They introduce two tasks – identifying if a relation exists between entities and confirming the correctness of extracted relation triples – and leverage SVMs with dependency tree kernels to achieve state-of-the-art results on multiple datasets, outperforming existing systems like REVERB and OLLIE.

What Problem Does This Paper Address?

Traditional Relation Extraction (RE) systems are designed to identify specific, predefined semantic relationships between entities (e.g., <Obama, president, United States>). This requires manually annotated training data for each relation, making it difficult to scale and adapt to new domains. Open Information Extraction (Open IE) aims to overcome this by extracting a broader range of relations without a fixed schema. However, this generalization raises a fundamental question: what constitutes a "relation"? Is it limited to verbs, or can it include nouns, prepositions, or even implicit connections? Existing Open IE systems often focus on verbal relations, potentially missing a significant portion of meaningful information. Furthermore, evaluating and comparing different Open IE systems is challenging due to the ambiguity in defining what a relation is and the lack of standardized evaluation benchmarks. This paper addresses this ambiguity by proposing a more comprehensive approach to Open IE, including both implicit and explicit relations, and by introducing a robust evaluation framework.

Methods

The authors propose a two-task framework for Open IE:

  1. Binary Task: This task determines whether a potential relation exists between two entities in a sentence. It's designed to be more inclusive, considering implicit relations that might not be explicitly signaled by verbs.
  2. Triple Task: This task aims to confirm the correctness of extracted relation triples (<Entity1, Relation, Entity2>).

For both tasks, they employ Support Vector Machines (SVMs) enhanced with dependency tree kernels. Specifically, they adapt the partial tree kernel (PTK), which allows for the calculation of inner products between dependency parse trees without explicitly extracting features. This approach is particularly useful for semantic tasks where feature engineering can be complex.

  • Unlexicalized Tree Structure: A key innovation is the use of an unlexicalized dependency tree structure for Open IE. This means they don't rely on specific lexical items to define relations, making the system more robust to the vast and varied vocabulary of relations in Open IE.
  • Relation Pattern Extraction (Triple Task): For the Triple task, they extract relation word candidates using regular expression patterns based on POS tags, expanding beyond just verbs to include noun phrases.
  • Unsupervised Rule-Based Method: In addition to the supervised SVM approach, they also propose an unsupervised method based on heuristic rules derived from dependency parse links. This serves as a strong baseline and an alternative when labeled data is scarce.

Datasets

The paper uses the following datasets:

  • Penn Treebank: A portion of the Penn Treebank was used to create custom training, development, and test sets for evaluating their system. This dataset was manually annotated for the Binary task (presence of a relation) and the Triple task (relation words).
  • REVERB Dataset: The authors evaluate their system on the test set provided by the REVERB system.
  • OLLIE Dataset: Similarly, they evaluate on the test set provided by the OLLIE system.

The creation of custom data from the Penn Treebank allowed them to control for parsing quality and to specifically annotate for implicit relations, which is a key differentiator from previous work.

Key Insights and Ideas

  • Implicit Relations are Crucial: The paper strongly emphasizes that a significant portion of relations in natural language are implicit (around 28% in their Penn Treebank analysis), and current Open IE systems often miss these by focusing solely on verbal relations.
  • Two-Task Approach is Effective: Separating the problem into "is there a relation?" (Binary task) and "is this relation correct?" (Triple task) allows for a more nuanced and comprehensive approach to Open IE.
  • Tree Kernels for Open IE: Applying SVMs with dependency tree kernels to Open IE is a novel contribution. This method effectively captures structural information from dependency parses without the need for manual feature engineering, which is challenging given the open-ended nature of relations.
  • Unlexicalized Representation Matters: The unlexicalized tree structure is key to handling the vast and diverse set of relations in Open IE, moving beyond the limitations of fixed lexicons.
  • Unsupervised Baseline is Strong: The proposed unsupervised method provides a robust baseline, demonstrating that even rule-based approaches can achieve competitive performance, especially for noise filtering.

Key Results

  • Superior Performance: The proposed SVM system with dependency tree kernels outperforms state-of-the-art systems like REVERB and OLLIE on multiple datasets for both the Binary and Triple tasks.
  • Nominal Relation Improvement: The system achieved a significant 33% improvement on nominal relation extraction over OLLIE.
  • Robustness Across Datasets: The system's performance was evaluated on three different datasets, demonstrating its robustness and generalizability.
  • Binary Task Performance: The SVM method achieved the best performance on the Binary task, with heuristic rules ranking second.
  • Triple Task Performance: On the Triple task, the SVM system also showed superior results, with specific improvements noted for nominal relations.

Limitations and Future Work

  • Conjunction and Apposition Structures: The paper acknowledges that conjunction and apposition structures pose a challenge, leading to missed relations (e.g., failing to link "Robert Louis-Dreyfus" to "joins Saatchi" in a sentence describing an executive). They attempted to address this by adding features to the SVM kernel but found it didn't significantly improve performance.
  • Non-Consecutive Relation Words: Verbal relations where words are non-consecutive (e.g., a preposition far from the verb) can lead to recall loss for their system and REVERB. OLLIE's use of dependency link patterns helps mitigate this.
  • Entity Detection Limitations: For some relations, the system's focus on the head of an entity might lead to incorrect entity identification in certain complex cases.
  • Future Work: The authors plan to improve Open IE by tackling conjunction and apposition structures. They also aim to extend their work to extract relation words for implicit relations, such as "locate" in "Washington, U.S."

Summary updated

BibTeX
@inproceedings{xu2013open,
  author = {Ying Xu and Mi-Young Kim and Kevin Quinn and Randy Goebel and Denilson Barbosa},
  title = {{Open Information Extraction with Tree Kernels}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2013},
}
Figure