📄 Extracting Relations with Integrated Information Using Kernel Methods

Summary

Zhao and Grishman address entity relation detection: deciding whether a pair of entity mentions in a sentence stands in one of the predefined ACE 2004 relation types. Deeper syntactic analysis can expose more general patterns, but it also makes more mistakes. The authors therefore avoid relying on a single representation. They encode evidence from three processing levels as separate kernel functions: the token sequence, a parse-based reduced "link" sequence from the Charniak parser, and deep dependency paths from NYU's GLARF analyzer. They then merge these kernels into composite kernels, combining them by summation and extending some with polynomial terms. An SVM trained on the composite kernel can draw on whichever level is reliable for a given example, so errors at one level can be offset by another. Experiments on the ACE RDR task with gold-annotated entities show that every level helps, and adding kernels one at a time steadily raises performance. On the official ACE test data the system reached a value score of 70.1, which the authors describe as very competitive.

Key points

• Kernels: five in total, two on surface tokens, one on the parse, and two on GLARF deep dependencies. A relation candidate bundles the two arguments, the token span between them, a parse-pruned "link" sequence (noun phrases reduced to their heads, stop-listed items such as time expressions dropped) and a dependency path, which may be empty.
• Task setup: ACE 2004 defines seven entity types (PER, ORG, FAC, GPE, LOC, WEA, VEH) and seven relation types (EMP-ORG, PHYS, PER-SOC, GPE-AFF, Other-AFF, ART, DISC). The paper targets types only, not the 27 subtypes, and uses hand-annotated entities.
• SVM vs KNN (k=3): the overall score was 70.35% for SVM with the full composite kernel Φ2. KNN reached 67.44% with only Ψ1+Ψ3 and dropped to 65.69% with Φ2. SVM won on the four frequent relation types, while KNN did better on the three rarer ones.
• Official ACE scores: the value score was 71.7 on nwire, 68.0 on bnews and 70.1 overall, with an unweighted F-score of 76.0%. For comparison, inter-annotator value agreement on similar tasks ranged from about 0.70 to 0.80.
• Classification scheme: one-against-all, with nearest neighbor used to decide argument order and subtype. Pairwise classification brought little gain, since the types were rarely confused with each other.

Interesting ideas

• I1. One kernel per pipeline stage, then add them up. Because sums of valid kernels are themselves valid kernels, noisy deep features and reliable shallow ones can coexist, and the learner decides which to trust. This could serve any language whose parsers are imperfect, Ukrainian included, where UD-based features can be mixed with plain token features.
• I2. A parse-pruned token sequence. The "link" view keeps only syntactically important words (phrase heads, no stop-listed constituents). It sits between raw n-grams and full trees and is a cheap way to shorten noisy contexts.
• I3. Collapsing entities into single tokens. Multiword names are merged into one token, and nominals are represented by their head word. This makes contexts more comparable across examples.
• I4. Polynomial expansion does nothing for KNN. A polynomial transform preserves the ranking of similarities, so it cannot change nearest neighbors. This is worth knowing before spending effort on kernel tuning for instance-based classifiers.
• I5. Picking the classifier by class frequency. SVM was stronger on frequent types, while KNN held up better on rare ones. Comparing classifiers per class, rather than only on the total, can reveal when a hybrid or a fallback for small classes would pay off.