Tree Kernel-Based Relation Extraction with Context-Sensitive Structured Parse Tree Information

Guodong Zhou, Min Zhang, Dong-Hong Ji, Qiaoming ZhuEMNLP 2007 · OpenReview

Abstract

Automated relation extraction (RE) identifies semantic relationships between entities in text. While tree kernel-based methods are effective at capturing structural information, they often suffer from limited context within fixed tree spans and a "context-free" nature that ignores ancestral information. This paper introduces a dynamic tree span to capture essential predicates and a novel context-sensitive convolution tree kernel that incorporates ancestral paths. Evaluated on ACE RDC benchmarks, the proposed approach significantly outperforms previous state-of-the-art methods.

Introduction

Relation Extraction (RE) is a critical task in natural language processing, involving the detection of semantic links between entities (e.g., recognizing an "EMPLOYMENT" relationship between "Bill Gates" and "Microsoft"). Existing approaches typically fall into two categories: feature-based methods, which rely on manual linguistic features, and tree kernel-based methods, which measure similarity between parse trees directly.

Standard tree kernels face two primary limitations. First, they often utilize a "Shortest Path-enclosed Tree" (SPT) that excludes vital contextual information. Second, these kernels are traditionally "context-free," treating sub-trees identically regardless of their position or grammatical role in the overall sentence structure.

Methodology

Dynamic Context-Sensitive Tree Span

To address the limitations of rigid tree spans, the authors propose a dynamic expansion strategy. Entity pairs are categorized into five structural types: Embedded, PP-linked, Semi-structured, Descriptive, and Predicate-linked. For "predicate-linked" relations, the algorithm expands the tree span beyond the SPT to include the predicate-headed phrase and its path to the entities, ensuring the kernel sees the "action" defining the relationship.

Illustration of a predicate-linked relation where the standard SPT (dashed line) is expanded to include the predicate 'married'.

Context-Sensitive Convolution Tree Kernel

Traditional convolution kernels count common sub-trees but ignore their broader context. The authors modify this by incorporating ancestor node paths. By including the path from the root down to a sub-tree, the kernel can distinguish between identical structures serving different grammatical functions.

Comparison of context-free (a) and context-sensitive (b, c) sub-trees incorporating ancestral path information.

The study found that looking up to three levels of ancestors ($m=3$) provides an optimal balance between providing necessary context and avoiding noise from potential parsing errors.

Composite Kernel

The new tree kernel is combined with a state-of-the-art linear kernel using polynomial interpolation. This composite approach leverages both the specific linguistic "rules of thumb" from the linear model and the broad structural patterns captured by the tree kernel.

Evaluation and Results

The approach was evaluated on the ACE RDC 2003 and 2004 datasets using 5-fold cross-validation and standard Precision/Recall/F-measure metrics.

Key Insights

  • Context Matters: Approximately 25% of relations require context outside the standard SPT for correct identification.
  • Semantic Grounding: Integrating entity type information (e.g., "PERSON") directly into tree nodes improved the F-measure by ~6.0 points, highlighting the importance of semantic grounding.
  • Performance Gains: The context-sensitive kernel improved the F-measure by 2.3 points over context-free versions, while the dynamic span added another 1.2 points.

Benchmark Performance

The composite kernel set new performance records on the ACE datasets:

  • ACE 2003: Achieved an F-measure of 74.1 on major types, significantly higher than previous benchmarks like Zhang et al. (70.9).
  • ACE 2004: Achieved an F-measure of 75.8 on major types.

Conclusion

By introducing dynamic tree spans and context-sensitive kernels, this work effectively addresses the "context-free" limitations of previous structural methods. While the approach is sensitive to initial parsing accuracy, it demonstrates that structural ancestry and dynamic context are vital for high-performance relation extraction. Future work will explore expansion strategies for non-predicate-linked categories and address data sparsity in rare relation subtypes.

Summary updated

BibTeX
@inproceedings{zhou2007tree,
  author = {Guodong Zhou and Min Zhang and Dong-Hong Ji and Qiaoming Zhu},
  title = {{Tree Kernel-Based Relation Extraction with Context-Sensitive Structured Parse Tree Information}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
  url = {https://openreview.net/forum?id=z5scKgoLDWI},
}
Figure