Elamur Research⌕
☰
home / papers / 2004 / Dependency Tree Kernels for Relation Extraction

Dependency Tree Kernels for Relation Extraction

Summary

The paper addresses relation extraction: deciding whether two already-tagged entity mentions in one sentence are linked by a relation, and which relation it is. The authors use the ACE newswire corpus with five top-level relation types (AT, NEAR, PART, ROLE, SOCIAL) and 24 subtypes. Each candidate entity pair becomes the smallest dependency subtree that covers both mentions. Every node in that subtree carries a feature vector: word, POS, chunk tag, entity type and level, WordNet hypernyms, and argument role. The trees are compared with a tree kernel that generalizes Zelenko et al. (2003), and the kernel is plugged into an SVM. Structured kernels clearly beat a bag-of-words kernel, with roughly a 20% F1 gain, and the improvement comes mostly from recall. Recall remains the main weakness. A cascade works best: first detect relations with a binary classifier, then classify the detected ones. The work shows that syntactic structure is a useful similarity signal for relations, and that this signal can be used without hand-engineering explicit structural features.

Key points

  • Kernels compared:
    • K0: sparse tree kernel
    • K1: contiguous tree kernel
    • K2: bag-of-words kernel
    • K3: K0 + K2
    • K4: K1 + K2
  • Tooling: MXPOST produced the parses, which were converted to dependency trees with link labels ignored. LibSVM was extended to support the tree kernel.
  • Multi-class results: Fewer than 15% of candidate pairs are true relations, so recall was low. K4 reached an average F1 of 38.0, compared with 14.2 for K2.
  • Binary detection results: K4 reached 63.2 F1, compared with 51.7 for bag-of-words.
  • Cascade results: Using K4 for both detection and classification gave the best average F1 of 45.8, against 38.1 for K2. Unlike in Zelenko et al., the sparse kernel did worse than the contiguous one, and tuning the decay factor λ did not change this.

Interesting ideas

  • I1. Prune the tree to the smallest subtree joining the two entities. Cutting away the rest of the sentence reduces noise and focuses the comparison on local context. This is a cheap preprocessing step that fits any pairwise task built on parses.
  • I2. Split node features into two groups. One subset must match exactly for two nodes to be compared at all, while the other subset only adds graded similarity. This makes it easy to set strict gates (e.g. entity type) next to soft evidence (e.g. word or hypernym), which is useful in many structure-matching kernels.
  • I3. Add a structural kernel to a bag-of-words kernel. The sum (K4) beat either kernel alone. Composite kernels are a simple way to fight the sparsity of exact structure matches.
  • I4. Detect first, then classify. Pooling all relation types into one positive class gives the detector more examples to learn from, and the detector's threshold can be tuned to a chosen operating point. This helps any task where negatives dominate.
  • I5. Mark which entity is the first argument. A node feature for argument order lets a symmetric similarity measure learn directional relations such as X owns Y. It is a minimal trick that carries over to other pairwise encodings.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Dependency parsing

Cited by

184 papers of our library cite it (of the 140884 whose bibliographies we read); 11 of them have a page here, 173 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/1218955.1219009

@inproceedings{culotta2004dependency,
  title = {{Dependency Tree Kernels for Relation Extraction}},
  author = {Culotta, Aron and Sorensen, Jeffrey},
  booktitle = {Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)},
  year = {2004},
  doi = {10.3115/1218955.1219009},
  url = {https://doi.org/10.3115/1218955.1219009}
}

References

18 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Eugene Agichtein and Luis Gravano. 2000. Snowball: Extracting relations from large plain-text collections. In Proceedings of the Fifth ACM International Conference on Digital Libraries. find
  2. Sergey Brin. 1998. Extracting patterns and relations from the world wide web. In WebDB Workshop at 6th International Conference on Extending Database Technology, EDBT’98. find
  3. M. Collins and N. Duffy. 2002. Convolution kernels for natural language. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, Cambridge, MA. MIT Press. find
  4. Corinna Cortes and Vladimir Vapnik. 1995. Support-vector networks. Machine Learning, 20(3):273–297. find
  5. N. Cristianini and J. Shawe-Taylor. 2000. An introduction to support vector machines. Cambridge University Press. find
  6. Chad M. Cumby and Dan Roth. 2003. On kernel methods for relational learning. In Tom Fawcett and Nina Mishra, editors, Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA. AAAI Press. find
  7. K. Fukunaga. 1990. Introduction to Statistical Pattern Recognition. Academic Press, second edition. find
  8. D. Haussler. 1999. Convolution kernels on discrete structures. Technical Report UCS-CRL-99-10, University of California, Santa Cruz. find
  9. Thorsten Joachims, Nello Cristianini, and John Shawe-Taylor. 2001. Composite kernels for hypertext categorisation. In Carla Brodley and Andrea Danyluk, editors, Proceedings of ICML-01, 18th International Conference on Machine Learning, pages 250–257, Williams College, US. Morgan Kaufmann Publishers,… find
  10. Huma Lodhi, John Shawe-Taylor, Nello Cristianini, and Christopher J. C. H. Watkins. 2000. Text classification using string kernels. In NIPS, pages 563–569. find
  11. A. McCallum and B. Wellner. 2003. Toward conditional models of identity uncertainty with application to proper noun coreference. In IJCAI Workshop on Information Integration on the Web. find
  12. S. Miller, H. Fox, L. Ramshaw, and R. Weischedel. 2000. A novel use of statistical parsing to extract information from text. In 6th Applied Natural Language Processing Conference. find
  13. H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. 2002. Identity uncertainty and citation matching. find
  14. Dan Roth and Wen-tau Yih. 2002. Probabilistic reasoning for entity and relation recognition. In 19th International Conference on Computational Linguistics. find
  15. Sam Scott and Stan Matwin. 1999. Feature engineering for text classification. In Proceedings of ICML-99, 16th International Conference on Machine Learning. find
  16. Erik F. Tjong Kim Sang and Fien De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In Walter Daelemans and Miles Osborne, editors, Proceedings of CoNLL-2003, pages 142– 147. Edmonton, Canada. find
  17. Vladimir Vapnik. 1998. Statistical Learning Theory. Whiley, Chichester, GB. find
  18. D. Zelenko, C. Aone, and A. Richardella. 2003. Kernel methods for relation extraction. Journal of Machine Learning Research, pages 1083– 1106. find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/culotta-2004-dependency-tree-kernels-relation-extraction/