📄 A Shortest Path Dependency Kernel for Relation Extraction

Summary

The paper tackles relation extraction: deciding whether, and how, two named entities in one sentence are related. The authors argue that nearly all the useful syntactic evidence lies on the shortest path linking the two entities in the undirected dependency graph, which is a much smaller structure than the minimal subtrees used by earlier tree kernels. Each path is a chain of words and arrows showing dependency direction. To reduce lexical sparsity, every position on the path is expanded into a set of word classes: the word itself, its POS tag, a coarser category, and the entity type at the endpoints. The feature space is the Cartesian product of these sets. An SVM compares examples through a kernel computed over these chains. Dependencies come from either a CCG parser or a CFG parser. On the five top-level ACE relation types, the shortest-path kernel beats the dependency tree kernel of Culotta and Sorensen (2004). The method is also fast and easy to interpret, which shows that a compact, well-chosen input representation can reduce overfitting while making the model more transparent.

Key points

• Task: extract the 5 top-level relation types from the ACE newspaper corpus, with the entities assumed to be given. Two setups were tested: S1 uses a single multi-class SVM with an extra no-relation class, and S2 first detects a relation with a binary SVM and then classifies it.
• Results (F-measure): SP-CFG reaches 50.5 (S1) and 52.5 (S2), SP-CCG reaches 48.0 and 50.2, and the baseline K4 kernel reaches 38.0 and 45.8. Most of the gain comes from recall, for example 43.8 vs 35.0 in S2.
• SP-CFG did better than SP-CCG. Error analysis credited this to Collins' parser capturing local dependencies more accurately, even though CCG can also recover long-distance ones.
• One example path, "protesters → seized ← stations", expands into 4×1×3×1×4 = 48 features.
• Efficiency: each SP kernel run took 2–3 hours for training and testing on a 2.6GHz Pentium IV. Paths longer than 10 words were given a kernel value of 0. Normalizing the kernel slightly lowered accuracy.

Interesting ideas

• I1. Cut the input down to the shortest dependency path. Removing everything except the connecting path acts as strong, linguistically motivated feature selection. It could help any pairwise task over parsed text, such as event–argument linking or entity linking within a sentence.
• I2. Back off each path position to word classes. Letting every node appear as the word, its POS tag or a broad category produces generalized patterns, including partial ones, without hand-writing templates. This is a practical way to fight sparsity in morphologically rich languages, where exact word forms seldom repeat.
• I3. Mark negation directly on path nodes. Adding a "(-)" suffix to verbs or nouns modified by words like "not", "never" or "no" keeps polarity inside the path representation at almost no cost. Without it, a relation and its denial would look identical.
• I4. Use a transparent kernel. Every dimension corresponds to an explicit path feature, so the kernel can be restricted to pattern types considered relevant. That makes models easier to inspect and adjust than opaque tree kernels.
• I5. Detect first, then classify, when data are skewed. Splitting the task into binary detection followed by multi-class typing improved recall when no-relation cases dominate. This setup could transfer to other imbalanced extraction tasks.