Elamur Research⌕
☰
home / papers / 2015 / Joint Mention Extraction and Classification with Mention Hypergraphs

Joint Mention Extraction and Classification with Mention Hypergraphs

Paper · 2015 · Wei Lu and Dan Roth

Summary

The paper tackles mention extraction and classification: finding text spans that refer to entities (named, nominal or pronominal) and assigning each a semantic type. Standard sequence models such as linear-chain CRFs and semi-Markov CRFs struggle when mentions overlap or nest and can be arbitrarily long. The main existing alternative, the constituency-parser approach of Finkel and Manning (2009), handles nesting but runs in cubic time. Lu and Roth introduce mention hypergraphs, a compact structure built from five node types that encodes exponentially many combinations of overlapping, unbounded-length mentions. Learning and inference run in time linear in both sentence length and the number of mention types. The same framework also predicts mention heads jointly with boundaries and types, at no extra complexity cost. On GENIA the model outperforms a semi-CRF and comes close to the parser-based system while using no external word clusters. On the non-overlapping CoNLL2003 data it roughly matches the baseline Illinois NER. This matters because overlap-aware extraction becomes fast enough for large corpora.

Key points

  • Hypergraph structure: the hypergraph uses A, E, T, I and X nodes. Each I node has three hyperedges, covering a word that is inside a mention, ends a mention, or does both at once (overlapping mentions of the same type).
  • Representation guarantee: any set of mentions maps to exactly one sub-hypergraph. The reverse does not hold, so some distinct overlapping combinations share a representation.
  • GENIA results: the setup used a 90/10 split, collapsed subtypes into DNA, RNA and protein, and kept cell line and cell type. F1 was:
    • MH (F): 68.7
    • semi-CRF: 68.2
    • Finkel & Manning (2009): 70.3, though the two baselines used word clusters learned from 200M extra PubMed words.
  • CoNLL2003 test F1: MH scored 83.3, MH (F) scored 83.8, and the Illinois baseline without external resources scored 83.7.
  • Speed: the model tagged over 5,000 words/second on GENIA. The earlier paper reported roughly 38 words/second for the parser model and 45 for the semi-CRF, but the authors caution that hardware differences make this comparison loose. Code is available at statnlp.org/research/ie/.

Interesting ideas

  • I1. Encode structure in the graph topology. The model represents overlapping spans by designing the graph itself, rather than through a cubic-time parser. This keeps exact inference linear, and the same approach could suit other span tasks such as nested NER in morphologically rich languages.
  • I2. Check what the representation can express. The authors prove that every mention set has a unique encoding and openly admit that the reverse mapping is ambiguous. Stating this trade-off explicitly is a good habit when designing any compact structured representation.
  • I3. Predict heads jointly. Heads are predicted together with boundaries and types, and evaluation counts a mention as correct only if all three match exactly. The paper compares this against simple head heuristics (whole span, first word, last word) and a cascaded pipeline, which is a reusable set of baselines for head-aware tasks.
  • I4. Test on simpler data too. An overlap-capable model is also evaluated on CoNLL2003, where nothing overlaps, to show that the extra expressiveness costs no accuracy. Running this kind of check against the simpler setting makes it easier to justify adopting a more general model.

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

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

Cite

Cite as Wei Lu and Dan Roth. 2015. Joint Mention Extraction and Classification with Mention Hypergraphs. Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d15-1102

@inproceedings{lu2015joint,
  title = {{Joint Mention Extraction and Classification with Mention Hypergraphs}},
  author = {Wei Lu and Dan Roth},
  booktitle = {Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing},
  year = {2015},
  doi = {10.18653/v1/d15-1102},
  url = {https://doi.org/10.18653/v1/d15-1102}
}

References

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

  1. Beatrice Alex, Barry Haddow, and Claire Grover. 2007. Recognising nested named entities in biomedical text. In BioNLP, pages 65–72. Association for Computational Linguistics. find
  2. Phil Blunsom, Trevor Cohn, and Miles Osborne. 2008. A Discriminative Latent Variable Model for Statistical Machine Translation. In ACL, pages 200–208. our card
  3. Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press. find
  4. Xavier Carreras, Lluis Marquez, and Lluı́s Padró. 2002. Named entity extraction using adaboost. CONLL, pages 167–170. find
  5. Kai-Wei Chang, Rajhans Samdani, and Dan Roth. 2013. A Constrained Latent Variable Model for Coreference Resolution. In EMNLP, pages 601– 612. our card
  6. Wanxiang Che, Mengqiu Wang, Christopher D Manning, and Ting Liu. 2013. Named Entity Recognition with Bilingual Constraints. In NAACL-HLT, pages 52–62. find
  7. Martin Cmejrek, Haitao Mi, and Bowen Zhou. 2013. Flexible and efficient hypergraph interactions for joint hierarchical and forest-to-string decoding. In EMNLP, pages 545–555. find
  8. Alessandro Cucchiarelli and Paola Velardi. 2001. Unsupervised named entity recognition using syntactic and semantic contextual evidence. Computational Linguistics, 27(1):123–131. find
  9. Aron Culotta and Andrew McCallum. 2004. Confidence estimation for information extraction. In HLT-NAACL, pages 109–112. find
  10. Oren Etzioni, Michael Cafarella, Doug Downey, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S Weld, and Alexander Yates. 2005. Unsupervised named-entity extraction from the web: An experimental study. Artificial Intelligence, 165(1):91–134. find
  11. Jenny Rose Finkel and Christopher D Manning. 2009. Nested named entity recognition. In EMNLP, pages 141–150. Association for Computational Linguistics. our card
  12. Radu Florian, Abe Ittycheriah, Hongyan Jing, and Tong Zhang. 2003. Named entity recognition through classifier combination. In CONLL, pages 168–171. Association for Computational Linguistics. our card
  13. Radu Florian, Hany Hassan, Abraham Ittycheriah, Hongyan Jing, Nanda Kambhatla, Xiaoqiang Luo, H Nicolov, and Salim Roukos. 2004. A statistical model for multilingual entity detection and tracking. In HLT-NAACL, pages 1–8. DTIC Document. our card
  14. Stephen Guo, Ming-Wei Chang, and Emre Kiciman. 2013. To Link or Not to Link? A Study on End-to-End Tweet Entity Linking. In NAACL-HLT, pages 1020–1030. find
  15. Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S Weld. 2011. Knowledge-based weak supervision for information extraction of overlapping relations. In ACL, pages 541–550. Association for Computational Linguistics. find
  16. Dan Klein and Christopher D. Manning. 2001. Parsing and hypergraphs. In IWPT, pages 123–134. find
  17. John Lafferty, Andrew McCallum, and Fernando CN Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML. find
  18. Qi Li and Heng Ji. 2014. Incremental Joint Extraction of Entity Mentions and Relations. In ACL, pages 402–412. our card
  19. Qi Li, Heng Ji, and Liang Huang. 2013. Joint Event Extraction via Structured Prediction with Global Features. In ACL, pages 73–82. our card
  20. Dong C Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1-3):503–528. find
  21. Wei Lu. 2015. Constrained semantic forests for improved discriminative semantic parsing. In ACL. find
  22. Ryan McDonald and Fernando Pereira. 2005. Identifying gene and protein mentions in text using conditional random fields. BMC bioinformatics, 6(S6). find
  23. Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009. Distant supervision for relation extraction without labeled data. In ACL-IJCNLP, pages 1003–1011. Association for Computational Linguistics. find
  24. David Nadeau and Satoshi Sekine. 2007. A survey of named entity recognition and classification. Lingvisticae Investigationes, 30(1):3–26. find
  25. Arvind Neelakantan and Michael Collins. 2014. Learning Dictionaries for Named Entity Recognition using Minimal Supervision. In EACL, pages 452–461. find
  26. Panupong Pasupat and Percy Liang. 2014. Zero-shot Entity Extraction from Web Pages. In ACL, pages 391–401. find
  27. Slav Petrov and Dan Klein. 2007. Discriminative log-linear grammars with latent variables. In NIPS, pages 1153–1160. find
  28. Lev Ratinov and Dan Roth. 2009. Design challenges and misconceptions in named entity recognition. In CONLL, pages 147–155. Association for Computational Linguistics. our card
  29. Alan Ritter, Sam Clark, Mausam, and Oren Etzioni. 2011. Named entity recognition in tweets: an experimental study. In EMNLP, pages 1524–1534. Association for Computational Linguistics. our card
  30. Sunita Sarawagi and William W Cohen. 2004. Semi-markov conditional random fields for information extraction. In NIPS, pages 1185–1192. find
  31. Jun Suzuki, Erik McDermott, and Hideki Isozaki. 2006. Training conditional random fields with multivariate evaluation measures. In COLING/AC, pages 217–224. find
  32. Erik F Tjong Kim Sang and Fien De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In CONLL, pages 142–147. Association for Computational Linguistics. our card
  33. Mengqiu Wang, Wanxiang Che, and Christopher D Manning. 2013. Joint Word Alignment and Bilingual Named Entity Recognition Using Dual Decomposition. In ACL, pages 1073–1082. find
  34. GuoDong Zhou and Jian Su. 2002. Named entity recognition using an hmm-based chunk tagger. In ACL, pages 473–480. our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lu-2015-joint-mention-extraction-classification-mention/