Elamur Research⌕
☰
home / papers / 2014 / Incremental Joint Extraction of Entity Mentions and Relations

Incremental Joint Extraction of Entity Mentions and Relations

Summary

The paper addresses end-to-end extraction of entity mentions and the relations between them from raw text. Instead of a pipeline, where a mention tagger feeds a separate relation classifier and errors flow downstream without correction, Li and Ji predict both layers with one model. Their framework uses a structured perceptron trained with beam search. It processes a sentence left to right, alternately adding typed mention segments and linking newly completed mentions to earlier ones with directed relation labels. Because hypotheses in the beam may have different mention boundaries, decoding works at the segment level, following the semi-Markov idea, rather than tagging tokens. Since search is inexact anyway, the authors can add global features that act as soft constraints over the whole output graph. On ACE'04 with 5-fold cross-validation, the joint model with global features beats a strong pipeline (CRF plus MaxEnt) on both mentions and relations. It also clearly surpasses the previous best end-to-end result (Chan and Roth, 2011). This shows that cross-task interaction and structure-level features pay off.

Key points

  • Data: ACE corpora. ACE'04 defines 7 entity types (PER, ORG, GPE, LOC, FAC, WEA, VEH) and 7 relation types. ACE'05 reorganizes these, for example by adding Part-Whole, dropping DISC and merging Other-AFF into EMP-ORG. Relations are treated as directed, so each direction counts as its own class.
  • Baseline pipeline:
    • Mentions: a linear-chain CRF with BILOU tagging, plus dependency-governor and Brown-cluster features (clusters learned on TDT5).
    • Relations: a MaxEnt classifier with phrase-label sequences, the syntactico-semantic patterns of Chan and Roth (2010), and cluster-based copies of lexical features.
  • ACE'04 results, F1:
    • Entity mentions: 77.6 (pipeline) → 78.8 (joint, local features) → 79.7 (joint, global features).
    • Relations: 40.8 for Chan and Roth (2011), 46.0 for the pipeline, 48.3 for the joint global model.
    • Mention + relation: 42.9 → 45.3.
  • The decoder's worst-case complexity is O(d̂·k·m²), where d̂ is the maximum segment length, k the beam size and m the sentence length.
  • Error analysis:
    • Human end-to-end relation F1 is only about 70%, and inter-annotator agreement F1 (51.9%) is just 2.4 points above the system.
    • Of 631 missed relations, 318 (50.3%) were caused by missing mention arguments, often rare nominal heads.

Interesting ideas

  • I1. Segment-level beam states. Each beam is indexed by the token where the last segment ends, so a half-built mention is never scored against a finished one. This trick suits any joint task in which span boundaries and span-level decisions must be compared fairly.
  • I2. Interleaving span and link actions. After each new segment, the decoder immediately tries linking it to every earlier mention. As a result, all hypotheses in a beam have gone through the same number of steps before being re-ranked. This is a useful general recipe for incremental graph construction over text.
  • I3. Global features as soft constraints. Inexact beam search makes features over the whole structure cheap to add. One example is a "triangle" feature encouraging conjoined mentions to share the same relation type to a common head. The same approach could encode consistency rules in other extraction tasks without hard ILP constraints.
  • I4. Benchmarking against annotator agreement. Reporting human and inter-annotator scores next to system scores, and tracing missed relations back to missed mentions, shows where the real bottleneck lies. Here it is relation recall driven by mention recall, which is a good evaluation habit for any new IE dataset.

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

Cited by

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

Cite

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

@inproceedings{li2014incremental,
  title = {{Incremental Joint Extraction of Entity Mentions and Relations}},
  author = {Li, Qi and Ji, Heng},
  booktitle = {Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2014},
  doi = {10.3115/v1/p14-1038},
  url = {https://doi.org/10.3115/v1/p14-1038}
}

References

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

  1. Razvan C. Bunescu and Raymond J. Mooney. 2005. A shortest path dependency kernel for relation extraction. In Proc. HLT/EMNLP, pages 724–731. find our card
  2. Yee Seng Chan and Dan Roth. 2010. Exploiting background knowledge for relation extraction. In Proc. COLING, pages 152–160. find
  3. Yee Seng Chan and Dan Roth. 2011. Exploiting syntactico-semantic structures for relation extraction. In Proc. ACL, pages 551–560. find
  4. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL, pages 111–118. find our card
  5. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP, pages 1–8. find our card
  6. Aron Culotta and Jeffrey Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. ACL, pages 423–429. find our card
  7. Radu Florian, Hany Hassan, Abraham Ittycheriah, Hongyan Jing, Nanda Kambhatla, Xiaoqiang Luo, Nicolas Nicolov, and Salim Roukos. 2004. A statistical model for multilingual entity detection and tracking. In Proc. HLT-NAACL, pages 1–8. find
  8. Radu Florian, Hongyan Jing, Nanda Kambhatla, and Imed Zitouni. 2006. Factorizing complex models: A case study in mention detection. In Proc. ACL. find
  9. Radu Florian, John F. Pitrelli, Salim Roukos, and Imed Zitouni. 2010. Improving mention detection robustness to noisy input. In Proc. EMNLP, pages 335– 345. find
  10. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In ACL, pages 1077–1086. find
  11. Liang Huang, Suphan Fayong, and Yang Guo. 2012. Structured perceptron with inexact search. In Proc. HLT-NAACL, pages 142–151. find our card
  12. Heng Ji and Ralph Grishman. 2005. Improving name tagging by reference resolution and relation detection. In Proc. ACL, pages 411–418. find
  13. Jing Jiang and ChengXiang Zhai. 2007. A systematic exploration of the feature space for relation extraction. In Proc. HLT-NAACL. find
  14. Nanda Kambhatla. 2004. Combining lexical, syntactic, and semantic features with maximum entropy models for information extraction. In Proc. ACL, pages 178–181. find
  15. Rohit J. Kate and Raymond Mooney. 2010. Joint entity and relation extraction using card-pyramid parsing. In Proc. ACL, pages 203–212. find
  16. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML, pages 282–289. find
  17. Qi Li, Heng Ji, and Liang Huang. 2013. Joint event extraction via structured prediction with global features. In Proc. ACL, pages 73–82. find our card
  18. Marie-Catherine De Marneffe, Bill Maccartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proc. LREC, pages 449,454. find our card
  19. Tomoko Ohta, Sampo Pyysalo, Jun’ichi Tsujii, and Sophia Ananiadou. 2012. Open-domain anatomical entity mention detection. In Proc. ACL Workshop on Detecting Structure in Scholarly Discourse, pages 27–36. find
  20. Barbara Plank and Alessandro Moschitti. 2013. Embedding semantic similarity in tree kernels for domain adaptation of relation extraction. In Proc. ACL, pages 1498–1507. find
  21. Longhua Qian and Guodong Zhou. 2010. Clustering-based stratified seed sampling for semi-supervised relation classification. In Proc. EMNLP, pages 346– 355. find
  22. Longhua Qian, Guodong Zhou, Fang Kong, Qiaoming Zhu, and Peide Qian. 2008. Exploiting constituent dependencies for tree kernel-based semantic relation extraction. In Proc. COLING, pages 697–704. find
  23. Lev Ratinov and Dan Roth. 2009. Design challenges and misconceptions in named entity recognition. In Proc. CONLL, pages 147–155. find our card
  24. Frank Reichartz, Hannes Korte, and Gerhard Paass. 2009. Composite kernels for relation extraction. In Proc. ACL-IJCNLP (Short Papers), pages 365–368. find
  25. Dan Roth and Wen-tau Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Proc. CoNLL. find our card
  26. Dan Roth and Wen-tau Yih. 2007. Global inference for entity and relation identification via a lin- ear programming formulation. In Introduction to Statistical Relational Learning. MIT. find
  27. Sunita Sarawagi and William W. Cohen. 2004. Semi-markov conditional random fields for information extraction. In Proc. NIPS. find
  28. Sameer Singh, Sebastian Riedel, Brian Martin, Jiaping Zheng, and Andrew McCallum. 2013. Joint inference of entities, relations, and coreference. In Proc. CIKM Workshop on Automated Knowledge Base Construction. find
  29. Ang Sun, Ralph Grishman, and Satoshi Sekine. 2011. Semi-supervised relation extraction with large-scale word clustering. In Proc. ACL, pages 521–529. find
  30. Bishan Yang and Claire Cardie. 2013. Joint inference for fine-grained opinion extraction. In Proc. ACL, pages 1640–1649. find
  31. Xiaofeng Yu and Wai Lam. 2010. Jointly identifying entities and extracting relations in encyclopedia text via a graphical model approach. In Proc. COLING (Posters), pages 1399–1407. find
  32. Yue Zhang and Stephen Clark. 2008. Joint word segmentation and pos tagging using a single perceptron. In Proc. ACL, pages 1147–1157. find
  33. Shubin Zhao and Ralph Grishman. 2005. Extracting relations with integrated information using kernel methods. In Proc. ACL, pages 419–426. find
  34. Guodong Zhou, Jian Su, Jie Zhang, and Min Zhang. 2005. Exploring various knowledge in relation extraction. In Proc. ACL, pages 427–434. find our card
  35. Guodong Zhou, Min Zhang, Dong-Hong Ji, and Qiaoming Zhu. 2007. Tree kernel-based relation extraction with context-sensitive structured parse tree information. In Proc. EMNLP-CoNLL, pages 728–736. find
  36. Imed Zitouni and Radu Florian. 2008. Mention detection crossing the language barrier. In Proc. EMNLP, pages 600–609. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2014-incremental-joint-extraction-entity-mentions/