Syntactic Tree-based Relation Extraction Using a Generalization of Collins and Duffy Convolution Tree Kernel

Mahdy Khayyamian, Seyed Abolghasem Mirroshandel, Hassan AbolhassaniNAACL 2009

TL;DR

This paper introduces a generalized convolution tree kernel that significantly improves syntactic feature extraction for relation extraction tasks. By allowing customizable weights on tree nodes and sub-trees, their novel kernels outperform the original Collins and Duffy kernel on the ACE-2005 dataset, demonstrating the power of more flexible syntactic feature representation.

What Problem Does This Paper Address?

Information extraction, particularly identifying semantic relations between entities in text, is a crucial task in Natural Language Processing (NLP). While syntactic features have proven effective, existing methods like the Collins and Duffy (CD'01) convolution tree kernel, while powerful, are somewhat rigid. The challenge lies in creating more adaptable and effective syntactic kernels that can better capture the nuances of linguistic structure relevant to relation extraction, especially when dealing with complex sentence structures and diverse relation types.

Methods

The core contribution is a generalized convolution tree kernel. This generalization builds upon the CD'01 kernel by introducing customizable weights for internal and external nodes of parse tree sub-trees. These weights, defined by inw(n) (internal node weight) and enw(n) (external node weight), allow for a more nuanced representation of a sub-tree's importance. The kernel's value for a given tree is then a weighted sum of common sub-trees, where the weights are derived from these node-specific values.

From this generalized kernel, the authors propose three novel syntactic sub-kernels:

  • Argument Ancestor Path Kernel (AAP): This kernel focuses on weighting nodes along the ancestor path between the two entities involved in a relation, and their direct children. It uses a decaying parameter α to reduce the influence of nodes further away from this path.
  • Argument Ancestor Path Distance Kernel (AAPD): Similar to AAP, but it normalizes the distance of nodes from the closest argument's ancestor path using a MAX_DIST parameter.
  • Threshold Sensitive Argument Ancestor Path Distance Kernel (TSAAPD): This kernel introduces a threshold-based decaying mechanism, applying a sharp cutoff rather than a smooth decay for nodes beyond a certain distance from the ancestor path.

The generalized kernel can be converted back to the original CD'01 kernel by setting specific weight values.

Datasets

The proposed kernels are evaluated on the ACE-2005 multilingual corpus. For evaluation, the authors specifically use the more formal "news wire" and "broadcast news" sections of the corpus, consistent with prior work.

Key Insights and Ideas

  • Flexibility is Key: The generalization of the CD'01 kernel by introducing tunable weights is the central innovation. This allows for tailoring syntactic features to specific relation extraction tasks, moving beyond a one-size-fits-all approach.
  • Proximity Matters: The proposed sub-kernels highlight that syntactic features closer to the relation arguments (specifically, along their ancestor paths) are more informative for relation extraction.
  • Decay Mechanisms Influence Performance: Different decay strategies (smooth vs. threshold-based) for weighting nodes based on their distance from the relevant syntactic path can lead to varying performance improvements.
  • Sub-tree Importance Can Be Targeted: By weighting nodes, the kernel can implicitly prioritize sub-trees that are more relevant to the semantic relation being identified.

Key Results

The proposed kernels generally outperform the original CD'01 kernel on the ACE-2005 dataset across several relation types.

  • TSAAPD-1 achieved the best performance in ORG-AFF and PER-SOC relations, with a notable F₁-measure of 0.73 for PER-SOC.
  • AAPD showed a remarkable improvement over the Collins kernel for the GEN-AFF relation type, though overall performance on GEN-AFF was low due to a very small number of annotated instances.
  • The paper demonstrates that nodes closer to the ancestor path of relation arguments contain the most useful syntactic features.

Limitations and Future Work

  • Limitations: The paper notes that the GEN-AFF relation type exhibits low performance across all kernels due to its extremely small number of annotated instances in the training set. The current weighting mechanisms are solely based on node location in the parse tree.
  • Future Work:
    • Explore using larger tree portions beyond the path-enclosed tree (PT) to incorporate more contextual syntactic features.
  • Incorporate other useful information, such as node labels, into the weighting mechanisms.
  • Apply the generalized kernel to other NLP tasks, such as co-reference resolution.

Summary updated

BibTeX
@inproceedings{khayyamian2009syntactic,
  author = {Mahdy Khayyamian and Seyed Abolghasem Mirroshandel and Hassan Abolhassani},
  title = {{Syntactic Tree-based Relation Extraction Using a Generalization of Collins and Duffy Convolution Tree Kernel}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure