Subsequence Kernels for Relation Extraction

Razvan C. Bunescu, Raymond J. MooneyNeurIPS 2005

Identifying semantic relationships between entities in text—such as determining that "Protein A interacts with Protein B"—is a core challenge in Information Extraction known as Relation Extraction (RE). While identifying the entities themselves (Named Entity Recognition) is a well-studied problem, extracting the relationships between them is notoriously difficult because natural language allows for an infinite variety of expressions.

In their 2005 paper, Razvan Bunescu and Raymond Mooney present a robust approach to RE. By generalizing string kernels to work with word classes and linguistic patterns, they developed a system that outperformed both manually crafted rules and complex dependency-tree models, achieving state-of-the-art results without relying on error-prone syntactic parsing.

The Problem with Traditional Approaches

Prior to this work, methods for Relation Extraction generally fell into two extremes:

  1. Manual Rules: These systems offer high precision but suffer from low coverage and are extremely labor-intensive to build.
  2. Dependency Parsing: These models leverage the "tree" structure of a parsed sentence. However, parsers trained on standard newspaper text often fail miserably when applied to specialized domains like biomedical research.

The authors sought a middle ground: a method capable of capturing the "gappy" nature of language—where important relational words are often separated by irrelevant ones—while remaining robust to the noise common in specialized text.

Methods: The Generalized Subsequence Kernel

The core innovation of this paper is the Generalized Subsequence Kernel. Instead of explicitly defining every possible feature (which would result in an infinite list of word combinations), the authors use the "kernel trick" to efficiently calculate the similarity between two sentences based on their shared subsequences.

Crucially, they don't look at every subsequence. They restrict their focus using several key constraints:

  • Anchored Subsequences: The model only counts subsequences that are "anchored" on the two specific entities of interest.
  • The Three Patterns: Based on linguistic observation, the authors argue that relations are almost always expressed in one of three ways relative to the entities:
  • [FB] Fore-Between: Words before and between entities (e.g., "interaction of P1 with P2").
  • [B] Between: Only words between entities (e.g., "P1 interacts with P2").
  • [BA] Between-After: Words between and after entities (e.g., "P1-P2 complex").
Visual representation of the anchored subsequences (fore, between, and after) used to define the relation patterns.
  • Generalization: The kernel doesn't just match exact words. It matches "word classes," such as Part-of-Speech (POS) tags, entity types, or WordNet synsets. This allows the model to recognize that "binds" and "attaches" are semantically similar.
  • Decay Factor ($\lambda$): A penalty is applied for "gaps." The more irrelevant words that sit between the key relationship words, the less that subsequence contributes to the final similarity score.

Datasets and Evaluation

The authors evaluated their method on two distinct types of narrative text:

  1. AImed Corpus: A dataset of 225 Medline abstracts used for protein-protein interaction extraction. This represents a "hard" domain where standard parsers often fail.
  2. ACE (Automated Content Extraction) 2002: A newspaper corpus containing top-level relations like ROLE, PART, LOCATED, NEAR, and SOCIAL.

Key Insights and Results

The paper demonstrates that "flatter" subsequence models can actually outperform "deeper" dependency tree models. This is significant because subsequence kernels are easier to compute and less reliant on the perfect accuracy of a parser. Furthermore, unlike "black box" kernels, the dimensions of this subsequence kernel correspond directly to linguistic patterns, making the model's logic highly interpretable.

Performance Highlights: * Biomedical Domain: On the AImed corpus, the Extraction Relation Kernel (ERK) significantly outperformed previous rule-based systems (Manual) and the ELCS system (which used a greedy learning procedure).

Precision-Recall curve comparing the Extraction Relation Kernel (ERK) against ELCS and manual baselines.
  • News Domain: On the ACE corpus, the ERK achieved an F-measure of 47.7, significantly beating the best-performing dependency tree kernel of the time, which scored 38.0.
  • Ablation Study: By comparing the full ERK against a version that didn't use the three specific linguistic patterns (ERK-A), the authors proved that restricting the kernel to the FB, B, and BA patterns was crucial for maintaining high precision at higher recall levels. This "linguistic pruning" reduced noise and prevented overfitting.

Limitations and Future Work

While highly effective, the system assumes that entities have already been correctly identified by a Named Entity Recognition (NER) system; any errors in NER naturally propagate to the relation extraction phase. Additionally, the authors noted low recall on the ACE corpus due to highly unbalanced data (many more "no-relation" examples than "relation" examples), suggesting a cascaded approach for future iterations. Finally, the decay factor $\lambda$ was set to a fixed 0.75, but tuning this parameter on a per-dataset basis could yield even stronger results.

Summary updated

BibTeX
@inproceedings{bunescu2005subsequence,
  author = {Razvan C. Bunescu and Raymond J. Mooney},
  title = {{Subsequence Kernels for Relation Extraction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
}
Figure