📄 Kernel Methods for Relation Extraction

Summary

The paper addresses relation extraction: deciding whether a semantic relation holds between two entity mentions in text. The authors frame it as classification over structured objects. Instead of turning sentences into hand-built feature vectors, they define kernels that compare shallow parse trees directly. Each candidate relation is a piece of a shallow parse whose nodes carry attributes such as phrase type, text and entity role. Similarity is computed by recursively matching nodes and their child sequences. Two variants are proposed. The contiguous subtree kernel counts only adjacent child subsequences, while the sparse kernel also allows gapped ones, down-weighted by a decay factor. Both are computed efficiently with dynamic programming.

The kernels are plugged into Support Vector Machines and the Voted Perceptron. They are tested on person-affiliation and organization-location relations in news text, against feature-based learners. The kernel approaches beat the feature-based baselines. This matters because it shows that structural similarity can replace much manual feature engineering in information extraction.

Key points

• Two target relations: person-affiliation and organization-location, annotated in a corpus of news articles.
• Examples are built from shallow parses. Each node has a type and a role (for example, which entity argument it represents).
• Two tree kernels are introduced:
  • contiguous subtree kernel, which matches adjacent child subsequences only;
  • sparse subtree kernel, which matches gapped subsequences penalised by a decay parameter λ.
• Both kernels run in polynomial time via dynamic programming.
• Learners: SVM and Voted Perceptron with the new kernels.
• Baselines: Naive Bayes, Winnow and a feature-vector SVM.
• Results: kernel-based models gave higher F-measure than the feature-based ones, and the sparse kernel with SVM was generally strongest.
• Caveat: the supplied PDF extraction is largely unreadable, so exact corpus sizes and scores are omitted here. Check them against the original paper.

Interesting ideas

• I1. Compare structures instead of engineering features. A kernel over parse fragments avoids building huge explicit feature spaces. This is attractive for under-resourced languages like Ukrainian, where good hand-crafted features are scarce.
• I2. Gapped matching with a decay penalty. The sparse kernel tolerates inserted modifiers or extra words between matching elements while still preferring tight matches. The same trick suits noisy or morphologically rich text.
• I3. Shallow parsing is enough. Using chunk-level structure rather than full parses keeps the pipeline cheap and robust. This is a sensible design choice when a strong treebank-trained parser is unavailable.
• I4. Entity roles as node attributes. Marking which node plays which argument lets one generic kernel serve different relation types. It is a reusable pattern for multi-relation extraction, for example in trade or geography data.
• I5. Keep the learner separate from the similarity function. The same kernel works with both SVM and Voted Perceptron. Comparing them against feature-based baselines cleanly isolates the contribution of the representation.