Elamur Research⌕
☰
home / papers / 2017 / Fast and Accurate Entity Recognition with Iterated Dilated Convolutions

Fast and Accurate Entity Recognition with Iterated Dilated Convolutions

Summary

Bi-LSTM encoders, often paired with a CRF, are the standard approach to sequence tagging, but they process tokens one after another and cannot fully use GPU parallelism. Strubell et al. propose Iterated Dilated CNNs (ID-CNNs) as a faster token encoder for English NER. Dilated convolutions skip over inputs at a growing rate, so the context each token sees expands exponentially with depth without reducing output resolution. To avoid the overfitting that comes from simply stacking more layers, the model reuses one small dilated block several times with shared weights. It is trained so that the output after every iteration should already give correct labels. The authors evaluate on CoNLL 2003 and OntoNotes 5.0 English NER, using both independent per-token prediction and CRF/Viterbi decoding. ID-CNNs reach accuracy close to a Bi-LSTM-CRF while running 14–20× faster at test time. When applied to whole documents, they match or exceed it and are still almost 8× faster. This matters for large-scale tagging, where both compute time and energy use are real costs.

Key points

  • Effective input width (receptive field) grows exponentially with depth. Four dilated layers of width 3 already cover 31 tokens, more than the 23-token average sentence in the Penn TreeBank. With radius 2 and 8 layers, coverage exceeds 1,000 tokens, which is enough for a full newswire document.
  • On document-level CoNLL 2003, the greedy ID-CNN scores 90.65 F1, compared with 90.60 for the Bi-LSTM-CRF and 89.09 for the Bi-LSTM. It decodes 7.96× faster than the Bi-LSTM-CRF, while the greedy Bi-LSTM is only 4.60× faster.
  • Ablations on CoNLL show that both design choices help:
    • untying block parameters drops F1 to 89.81;
    • applying the loss only at the final layer drops F1 to 90.06.
  • On OntoNotes 5.0, the authors' Bi-LSTM-CRF reaches 86.99 F1, ID-CNN-CRF reaches 86.84, and the greedy ID-CNN with 3 blocks reaches 85.27. The greedy ID-CNN still beats the Bi-LSTM (83.76) and Durrett and Klein (2014).
  • Adding document context helps the ID-CNN on OntoNotes (85.76). It slightly hurts the Bi-LSTM-CRF (86.81). The implementation is in TensorFlow at github.com/iesl/dilated-cnn-ner.

Interesting ideas

  • I1. Weight tying across repeated blocks. Applying one shared dilated block several times, instead of building a deeper network, gives wide context without adding parameters or overfitting. This could suit small-data settings, such as low-resource Ukrainian corpora, where deep models overfit easily.
  • I2. Supervision after every iteration. Each pass is pushed to produce good labels, and later passes can then fix inconsistencies left by earlier ones. This acts as a cheap form of iterative refinement and could be added to other stacked or recurrent encoders.
  • I3. Doubling the dilation rate. Starting with dilation 1 and doubling it at each layer gives full coverage of the input with no gaps, and the parameter count grows only linearly. The same layout could serve any long-sequence task where per-position output must keep full resolution.
  • I4. Document-level context at low cost. Because the runtime of the convolutions does not depend on sequence length, feeding whole documents becomes practical. The paper also shows that the gain varies by dataset: it is larger on CoNLL, which has many ambiguous entities. This is a useful reminder to check, per corpus, whether extra context actually helps.
  • I5. Deciding between greedy and CRF decoding. The paper finds that the greedy-vs-Viterbi gap widens when entities are longer and more varied, as in OntoNotes. Looking at entity length statistics before choosing a decoder could save compute when structured decoding is unlikely to add much.

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: Named entity recognition

Cited by

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

Cite

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

@inproceedings{strubell2017fast,
  title = {{Fast and Accurate Entity Recognition with Iterated Dilated Convolutions}},
  author = {Strubell, Emma and Verga, Patrick and Belanger, David and McCallum, Andrew},
  booktitle = {Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing},
  year = {2017},
  doi = {10.18653/v1/d17-1283},
  url = {https://doi.org/10.18653/v1/d17-1283}
}

References

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

  1. Martın Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, According to the ACL Wiki page on CoNLL-2003: “The corpus contains a very high ratio of metonymic references (city names standing for sport teams)” Andy Davis, Jeffrey Dean, Matthieu Devin, et al. 20… find
  2. Razvan Bunescu and Raymond J. Mooney. 2004. Collective information extraction with relational markov networks. In ACL, pages 439–446. find
  3. Liang-Chieh Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. 2015. Semantic image segmentation with deep convolutional nets and fully connected crfs. In ICLR. find
  4. Jason PC Chiu and Eric Nichols. 2016. Named entity recognition with bidirectional lstm-cnns. Transactions of the Association for Computational Linguistics, 4:357–370. find our card
  5. Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. Journal of Machine Learning Research, 12(Aug):2493–2537. find our card
  6. Hal Daumé III, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine Learning, 75(3):297–325. find
  7. Greg Durrett and Dan Klein. 2014. A joint model for entity analysis: Coreference, typing and linking. Transactions of the Association for Computational Linguistics, 2:477–490. find our card
  8. Jenny Rose Finkel, Trond Grenager, and Christopher Manning. 2005. Incorporating non-local information into information extraction systems by gibbs sampling. In ACL, pages 363–370. find our card
  9. Xavier Glorot, Antoine Bordes, and Yoshua Bengio. 2011. Deep sparse rectifier neural networks. In AIS-TATS. find
  10. Çalar Gülçehre and Yoshua Bengio. 2016. Knowledge matters: Importance of prior information for optimization. Journal of Machine Learning Research, 17(8):1–32. find
  11. James Hammerton. 2003. Named entity recognition with long short-term memory. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL, pages 172–175. Association for Computational Linguistics. find
  12. Sepp Hochreiter. 1998. The vanishing gradient problem during learning recurrent neural nets and problem solutions. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 6(02):107–116. find
  13. Sepp Hochreiter and J urgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735–1780. find
  14. Eduard Hovy, Mitchell Marcus, Martha Palmer, Lance Ramshaw, and Ralph Weischedel. 2006. Ontonotes: the 90% solution. In Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers, pages 57–60. find
  15. Xuezhe Ma and Eduard Hovy. 2016. End-to-end sequence labeling via bi-directional lstm-cnns-crf. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, page 10641074. find our card
  16. Zhiheng Huang, Wei Xu, and Kai Yu. 2015. Bidirectional lstm-crf models for sequence tagging. arXiv preprint arXiv:1508.01991. find our card
  17. Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. 2016. Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499. find our card
  18. Nal Kalchbrenner, Lasse Espeholt, Karen Simonyan, Aaron van den Oord, Alex Graves, and Koray Kavukcuoglu. 2016. Neural machine translation in linear time. arXiv preprint arXiv:1610.10099. — [arXiv:1610.10099](https://arxiv.org/abs/1610.10099) find
  19. Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom. 2014. A convolutional neural network for modelling sentences. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. find our card
  20. Yoon Kim. 2014. Convolutional neural networks for sentence classification. In EMNLP. find our card
  21. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning (ICML), pages 282–289. find
  22. Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and Chris Dyer. 2016. Neural architectures for named entity recognition. In NAACL. find
  23. Chen-Yu Lee, Saining Xie, Patrick W Gallagher, Zhengyou Zhang, and Zhuowen Tu. 2015. Deeply-supervised nets. In AISTATS, volume 2, page 5. find
  24. Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2015. Molding cnns for text: non-linear, non-consecutive convolutions. Empirical Methods in Natural Language Processing. find
  25. Percy Liang, Hal Daumé III, and Dan Klein. 2008. Structure compilation: trading structure for features. In Proceedings of the 25th international conference on Machine learning, pages 592–599. ACM. find
  26. Wang Ling, Tiago Luı́s, Luı́s Marujo, Ramón Fernandez Astudillo, Silvio Amir, Chris Dyer, Alan W Black, and Isabel Trancoso. 2015. Finding Function in Form: Compositional Character Models for Open Vocabulary Word Representation. In EMNLP. find our card
  27. Ben London, Bert Huang, and Lise Getoor. 2016. Stability and generalization in structured prediction. Journal of Machine Learning Research, 17(222):1– 52. find
  28. Xuezhe Ma, Yingkai Gaom, Zhiting Hu, Yaoliang Yu, Yuntian Deng, and Eduard Hovy. 2017. Dropout with expectation-linear regularization. In ICLR. find
  29. Alexandre Passos, Vineet Kumar, and Andrew McCallum. 2014. Lexicon infused phrase embeddings for named entity resolution. In CoNLL. find our card
  30. Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Hwee Tou Ng, Anders Bj orkelund, Olga Uryupina, Yuchen Zhang, and Zhi Zhong. 2006. Towards robust linguistic analysis using ontonotes. In Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 143–152. find
  31. Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. 2012. Conll-2012 shared task: Modeling multilingual unrestricted coreference in ontonotes. In Proceedings of the Joint Conference on EMNLP and CoNLL: Shared Task, pages 1–40. find our card
  32. Lance A Ramshaw and Mitchell P Marcus. 1999. Text chunking using transformation-based learning. In Natural language processing using very large corpora, pages 157–176. Springer. find
  33. Lev Ratinov and Dan Roth. 2009. Design challenges and misconceptions in named entity recognition. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning, pages 147– 155. Association for Computational Linguistics. find our card
  34. Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, Carlo Gatta, and Yoshua Bengio. 2014. Fitnets: Hints for thin deep nets. arXiv preprint arXiv:1412.6550. find
  35. Nitish Srivastava, Geoffrey E Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929–1958. find
  36. Charles Sutton and Andrew McCallum. 2004. Collective segmentation and labeling of distant entities in information extraction. In ICML Workshop on Statistical Relational Learning. find
  37. Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. 2015. Going deeper with convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1–9. find
  38. Erik F Tjong Kim Sang and Fien De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003-Volume 4, pages 142–147. Association for Computational Linguistics. find
  39. Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. 2015. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1499–1509. Association for Com… find our card
  40. Joseph Turian, Lev Ratinov, and Yoshua Bengio. 2010. Word representations: a simple and general method for semi-supervised learning. In Proceedings of the 48th annual meeting of the association for computational linguistics, pages 384–394. Association for Computational Linguistics. find our card
  41. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Annual Meeting of the Association for Computational Linguistics. find
  42. Zhilin Yang, Ruslan Salakhutdinov, and William Cohen. 2016. Multi-task cross-lingual sequence tagging from scratch. In arXiv preprint arXiv:1603.06270. — [arXiv:1603.06270](https://arxiv.org/abs/1603.06270) find
  43. Fisher Yu and Vladlen Koltun. 2016. Multi-scale context aggregation by dilated convolutions. In International Conference on Learning Representations (ICLR). find
  44. Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems 28 (NIPS). find our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/strubell-2017-fast-accurate-entity-recognition-iterated/