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

Summary

The paper tackles relation extraction, which means deciding which predefined semantic relation, if any, links a pair of entity mentions in a sentence. The authors build a composite kernel with two parts. The first is a linear entity kernel that counts shared entity attributes: headword, type, subtype and mention type, plus LDC mention type for ACE 2004. The second is the Collins and Duffy convolution parse tree kernel, which scores syntactic similarity by implicitly counting common sub-trees. They join the two by a weighted sum of normalized kernels, or by first applying a degree-2 polynomial expansion to the entity kernel. They also compare five ways of cutting a relation instance out of a full parse tree.

Experiments on the ACE 2003 and ACE 2004 corpora show that the composite kernel beats the best previously reported feature-based systems. It also clearly outperforms two earlier dependency tree kernels, which suffered from low recall. The work matters because it shows that rich syntactic structure can be used with little manual feature engineering, and that more knowledge sources can be added simply by adding more kernels.

Key points

• The entity kernel counts identical feature values between corresponding entities. The tree kernel uses a decay factor λ and runs in O(|N1|·|N2|) worst case, though in practice it behaves nearly linearly.
• Weights tuned on the development set:
  • linear combination: α = 0.4;
  • polynomial version: α = 0.23, with K_p = (K + 1)².
• Five relation instance spaces were studied, including the Minimum Complete Tree (MCT). The smaller PT portion represented instances well and sped up training considerably.
• Training on a P4 3.0 GHz machine with 2 GB RAM took roughly:
  • 110 minutes on ACE 2003 (about 77k instances);
  • 30 minutes on ACE 2004 (about 33k instances).
• Error analysis of the polynomial kernel:
  • about 83.5% (2004) and 85.8% (2003) of errors came from relation detection rather than relation typing;
  • negative training examples outnumbered positives roughly 8 to 1.

Interesting ideas

• I1. Combine kernels instead of hand-merging features. Sums, products, normalization and polynomial expansion of valid kernels remain valid kernels. This makes it straightforward to fuse heterogeneous evidence, such as flat attributes and tree structure, in other classification tasks.
• I2. Normalize each kernel before combining. Normalizing every component prevents one kernel with larger raw values from swamping the other. This is a cheap safeguard whenever similarity scores on different scales are merged.
• I3. Use polynomial expansion to get feature conjunctions for free. Squaring the entity kernel implicitly creates pairwise features across the two entities without enumerating them. The same trick could model feature interactions in other pairwise tasks.
• I4. Treat the choice of tree region as a design variable. Testing which part of the parse tree to feed the kernel improved both accuracy and speed. Pruning input structures this way is worth trying for any structure-based model.
• I5. Split errors by stage. Separating detection errors from type-classification errors showed that detection and class imbalance were the real bottleneck. This kind of breakdown helps decide where future effort should go.