Min Zhang, Jie Zhang, Jian Su Proceedings of the Human Language Technology Conference of the NAACL, Main Conference. 2006.
Abstract
This paper demonstrates that hierarchical syntactic structures are highly effective for Relation Extraction (RE) when captured using a convolution tree kernel. By representing relations as specific sub-trees—most notably the "Path-enclosed Tree"—the authors outperform both traditional feature-based methods and previous, more restrictive dependency tree kernels on the ACE 2003 benchmark.
Introduction
Relation Extraction (RE) is the task of identifying semantic relationships between entities in text (e.g., recognizing that "George Bush" is the "President" of the "United States"). Historically, researchers used two main approaches:
- Feature-based methods: These rely on manually "flattening" linguistic information into vectors. While effective, they struggle to capture the rich, hierarchical nature of parse trees.
- Kernel-based methods: These compute similarity between structured objects (like trees) directly. However, early dependency tree kernels were often too rigid—for example, requiring matching nodes to be at the exact same depth—leading to high precision but very low recall.
The authors set out to prove that syntactic features are incredibly useful for RE, provided you use a kernel that can flexibly explore the sub-tree space without the "hard" constraints of previous models.
Methodology
The core of the paper is the application of a Convolution Tree Kernel to the RE task. Unlike previous kernels that looked for exact path matches, this kernel counts the number of common sub-trees between two parse trees, effectively capturing structural similarity at multiple levels of abstraction.
The authors systematically explored seven different "Relation Feature Spaces" (sub-sets of the full parse tree) to find the optimal representation for a relation:
- Minimum Complete Tree (MCT): The full sub-tree rooted at the nearest common ancestor of the two entities.
- Path-enclosed Tree (PT): The smallest sub-tree that includes the two entities.
- Chunking Tree (CT): A simplified version using only base phrases.
- Context-Sensitive and Flattened variations: Variations like CPT, CCT, FPT, and FCPT that add context or prune redundant nodes.
They integrated this kernel into a Support Vector Machine (SVM) classifier, using a composite approach that combines the tree kernel with entity-specific features like entity type and mention level.
Experimental Setup
The study uses the ACE 2003 corpus, a standard benchmark for information extraction.
- Scope: 5 major relation types (e.g., ROLE, PART, AT) and 24 subtypes.
- Data: 674 training documents (9,683 instances) and 97 test documents (1,386 instances).
- Parsing: Sentences were processed using Charniak’s parser.
Results and Discussion
The convolution tree kernel achieved an F-measure of 69.02 on the 5 ACE major types, slightly outperforming the best feature-based SVMs of the time. It also crushed previous dependency tree kernels by a massive margin—roughly 16 points higher in F-measure.
The "Path-enclosed Tree" (PT) is the Sweet Spot
The authors found that the PT outperformed the larger MCT. This suggests that while syntax is vital, including too much of the surrounding parse tree introduces "noise" that can confuse the model.
Syntax vs. Chunks
The PT significantly outperformed the Chunking Tree (CT). This proves that high-level hierarchical information (the "middle" of the tree) provides critical cues for relation extraction that flat chunking misses. Furthermore, adding entity types (e.g., knowing that "Bush" is a PERSON) to the tree nodes boosted the F-measure by about 7 points.
Conclusion
Error analysis showed that 85.9% of errors occurred during relation detection rather than characterization. The authors suggest a two-step model might improve results. Additionally, while the kernel captures syntax well, integrating deeper semantic features (like WordNet) directly into the tree nodes could further boost performance.
Summary updated