A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features

Min Zhang, Jie Zhang, Jian Su, Guodong ZhouACL 2006 · OpenReview

Abstract: Min Zhang, Jie Zhang, Jian Su, GuoDong Zhou. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.

2006.

Introduction

Relation Extraction (RE) is the task of identifying semantic relationships between entities in text—for example, recognizing that "Bill Gates" has an EMPLOYMENT.exec relationship with "Microsoft." Historically, researchers have approached this problem through two primary lenses:

  1. Feature-based methods: These rely on manually defining "flat" features like word types or distances. While effective, they require tedious feature engineering and often fail to capture the complex, hierarchical nature of language.
  2. Kernel-based methods: These use tree kernels to compare sentence structures. However, early kernels were often too rigid, requiring exact path lengths or specific node alignments, which led to high precision but poor recall.

Researchers from the Institute for Infocomm Research developed a "composite kernel" to bridge this gap, combining flat entity data with structured syntactic parse trees to automate extraction without exhaustive manual engineering.

Methodology: The Composite Kernel

The core innovation is a kernel that merges two distinct types of information via polynomial expansion:

  • The Entity Kernel: A linear kernel focusing on "flat" features of the entities, such as headwords, entity types (e.g., Person, Organization), and mention types.
  • The Convolution Parse Tree Kernel: This kernel counts common subtrees between two parse trees. It is "convolutional" because it decomposes large trees into all possible sub-structures to find similarities, allowing for flexible matching across different tree depths.

Relation Instance Spaces

A critical question in this research was determining the optimal amount of syntactic context needed. The authors experimented with several Relation Instance Spaces, which define how much of a sentence's parse tree is included in the model:

Comparison of different Relation Instance Spaces: Minimum Complete Tree (MCT), Path-enclosed Tree (PT), Context-Sensitive PT (CPT), and Flattened PT (FPT).

These variations range from the Minimum Complete Tree (MCT), which includes the entire subtree rooted at the nearest common ancestor, to the Path-enclosed Tree (PT), which is the smallest subtree including both entities.

Key Insights and Results

The study utilized the ACE 2003 and 2004 corpora to benchmark performance. Several key findings emerged:

  • The "Goldilocks" Tree: The researchers found that the Path-enclosed Tree (PT) is the most effective representation. As shown in the performance table below, including the entire subtree (MCT) introduces "noise" that hurts performance, while stripping the tree too much (Flattened PT) loses vital syntactic cues.
Performance comparison of different instance spaces, showing that the Path-enclosed Tree (PT) achieves the highest F-measure.
  • Complementary Features: Combining the entity kernel with the tree kernel provided a significant boost, suggesting that syntactic structure provides context that flat features cannot capture alone.
  • Polynomial Interaction: Using a polynomial expansion ($d=2$) to combine kernels allowed the model to learn that specific combinations of entity types are strong predictors for specific relations.

Overall, the composite kernel achieved state-of-the-art F-measures of 70.9 on ACE 2003 and 72.1 on ACE 2004, significantly outperforming older dependency-based kernels.

Limitations and Future Work

Despite its success, the convolution kernel is computationally expensive due to recursive matching. Additionally, the current model requires exact matches between subtrees, which can struggle with synonyms or varied phrasing (e.g., "a car" vs. "a red car"). Error analysis revealed that ~85% of mistakes occur during relation detection (identifying if a relation exists) rather than characterization (typing the relation). Future work will focus on addressing data imbalances and incorporating semantic kernels, such as WordNet, to handle deeper linguistic meanings.

Summary updated

BibTeX
@inproceedings{zhang2006composite,
  author = {Min Zhang and Jie Zhang and Jian Su and Guodong Zhou},
  title = {{A Composite Kernel to Extract Relations between Entities with Both Flat and Structured Features}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=C4OSQdOnok},
}
Figure