Elamur Research
☰
home / papers / 2016 / Globally Normalized Transition-Based Neural Networks

Globally Normalized Transition-Based Neural Networks

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/P16-1231.pdf

Summary

The authors from Google test whether recurrence, as in LSTMs, is really necessary for strong results on classic NLP tasks. They consider three tasks: POS tagging, dependency parsing, and sentence compression. The model is a simple feed-forward network on top of a transition-based system in the style of Chen and Manning. The main difference lies in training. Instead of a local softmax at each step, they use global normalization with a CRF loss. The normalization term is approximated by a sum over the hypotheses in the beam, early updates are applied, and the gradient is backpropagated through all layers down to the embeddings. On the theoretical side, the authors show (following Smith and Johnson) that because of the label bias problem, globally normalized models can represent a strictly larger class of distributions than locally normalized ones. In practice, the model achieved state-of-the-art results on all three tasks. It matches LSTMs while running faster, and on WSJ it obtained a record UAS. The SyntaxNet code and a ready-to-use parser were released together with the paper. The paper concludes that the choice of normalization may matter more than a recurrent architecture.

Key points

  • On WSJ the model obtained a UAS of 94.61%, the highest published result at the time.
  • Ablation on WSJ dev (UAS/LAS): local greedy model — 92.85/90.59; local with beam 16 — 93.32/91.09; global with training of the top layer only — 93.45/91.21; global with full backpropagation — 94.38/92.17. Full training also converges more than 4 times faster.
  • Parsing without lookahead (the model sees only a prefix of the sentence): the greedy model yields 76.96% UAS, the local model with beam 81.35%, and the global model 93.60%. With full lookahead the gap is smaller (94.01% vs. 93.07%) but does not disappear.
  • In sentence compression, the local model with beam sometimes outputs an empty compression. This is not a search error: that output really does have a higher probability under p_L. The global model assigns it a probability close to zero.
  • Open resource: SyntaxNet, integrated into TensorFlow, and the pretrained English parser Parsey McParseface. It is tuned to balance speed, simplicity, and accuracy.

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: Linguistics & languages

Topics: Dependency parsing

Cited by

204 papers of our library cite it (of the 140673 whose bibliographies we read); 25 of them have a page here, 179 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p16-1231 · arXiv 1603.06042

@inproceedings{andor2016globally,
  title = {{Globally Normalized Transition-Based Neural Networks}},
  author = {Andor, Daniel and Alberti, Chris and Weiss, David and Severyn, Aliaksei and Presta, Alessandro and Ganchev, Kuzman and Petrov, Slav and Collins, Michael},
  booktitle = {Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2016},
  doi = {10.18653/v1/p16-1231},
  eprint = {1603.06042},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p16-1231}
}

References

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

  1. Steven Abney, David McAllester, and Fernando Pereira. 1999. Relating probabilistic grammars and automata. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages 131–160. find
  2. Chris Alberti, David Weiss, Greg Coppola, and Slav Petrov. 2015. Improved transition-based parsing and tagging with neural networks. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1354–1359. find
  3. Miguel Ballesteros, Chris Dyer, and Noah A. Smith. 2015. Improved transition-based parsing by modeling characters instead of words with LSTMs. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 349–359. find
  4. Bernd Bohnet and Joakim Nivre. 2012. A transition-based system for joint part-of-speech tagging and labeled non-projective dependency parsing. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1455–1465. find
  5. Léon Bottou and Yann LeCun. 2005. Graph transformer networks for image recognition. Bulletin of the International Statistical Institute (ISI). find
  6. Meeting of the Association for Computational Linguistics, pages 334–343. Léon Bottou, Yann Le Cun, and Yoshua Bengio. 1997. Global training of document processing systems using graph transformer networks. In Proceedings of Computer Vision and Pattern Recognition (CVPR), pages 489–493. find
  7. Katja Filippova, Enrique Alfonseca, Carlos A. Col-menares, Łukasz Kaiser, and Oriol Vinyals. 2015. Sentence compression by deletion with lstms. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 360–368. find
  8. Léon Bottou. 1991. Une approche théorique de lap-prentissage connexionniste: Applications à la reconnaissance de la parole. Ph.D. thesis, Doctoral dissertation, Universite de Paris XI. find
  9. Yoav Goldberg and Joakim Nivre. 2013. Training deterministic parsers with non-deterministic oracles. Transactions of the Association for Computational Linguistics, 1:403–414. find
  10. Danqi Chen and Christopher D. Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pages 740–750. find our card
  11. Jan Hajič, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Antònia Martı́, Lluı́s Màrquez, Adam Meyers, Joakim Nivre, Sebastian Padó, Jan Štěpánek, Pavel Straňák, Mihai Surdeanu, Nianwen Xue, and Yi Zhang. 2009. The conll-2009 shared task: Syntactic and semantic dependenc… find our card
  12. Zhiyi Chi. 1999. Statistical properties of probabilistic context-free grammars. Computational Linguistics, pages 131–160. find
  13. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), pages 111–118. find our card
  14. Michael Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  15. Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. The Journal of Machine Learning Research, 12:2493–2537. find our card
  16. Hal Daumé III, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine Learning Journal (MLJ), 75(3):297–325. find
  17. Marie-Catherine De Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of Fifth International Conference on Language Resources and Evaluation, pages 449– 454. find our card
  18. Trinh Minh Tri Do and Thierry Artires. 2010. Neural conditional random fields. In International Conference on Artificial Intelligence and Statistics, volume 9, pages 177–184. find
  19. Greg Durrett and Dan Klein. 2015. Neural crf parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 302–312. find
  20. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. In Proceedings of the 53rd Annual James Henderson. 2003. Inducing history representations for broad coverage statistical parsing. In Proceedings… find our card
  21. James Henderson. 2004. Discriminative training of a neural network statistical parser. In Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL’04), pages 95–102. find
  22. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  23. 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, Short Papers, pages 57–60. find
  24. Zhiheng Huang, Wei Xu, and Kai Yu. 2015. Bidirectional LSTM-CRF models for sequence tagging. arXiv preprint arXiv:1508.01991. find our card
  25. John Judge, Aoife Cahill, and Josef van Genabith. 2006. Questionbank: Creating a corpus of parse-annotated questions. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 497–504. find
  26. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 282–289. find
  27. Yann Le Cun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient based learning applied to document recognition. Proceedings of IEEE, 86(11):2278–2324. find
  28. Tao Lei, Yu Xin, Yuan Zhang, Regina Barzilay, and Tommi Jaakkola. 2014. Low-rank tensors for scoring dependency structures. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1381–1391. find
  29. 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. find
  30. Wang Ling, Chris Dyer, Alan W Black, Isabel Trancoso, Ramon Fermandez, Silvio Amir, Luis Marujo, and Tiago Luis. 2015. Finding function in form: Compositional character models for open vocabulary word representation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Proc… find our card
  31. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
  32. Andre Martins, Miguel Almeida, and Noah A. Smith. 2013. Turning on the turbo: Fast third-order non-projective turbo parsers. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 617–622. find our card
  33. Joakim Nivre. 2006. Inductive Dependency Parsing. Springer-Verlag New York, Inc. find
  34. Joakim Nivre. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 351–359. find our card
  35. Jian Peng, Liefeng Bo, and Jinbo Xu. 2009. Conditional neural fields. In Advances in Neural Information Processing Systems 22, pages 1419–1427. find
  36. Slav Petrov and Ryan McDonald. 2012. Overview of the 2012 shared task on parsing the web. Notes of the First Workshop on Syntactic Analysis of Non-Canonical Language (SANCL). find
  37. Stéphane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell. 2011. No-regret reductions for imitation learning and structured prediction. AISTATS. find
  38. Noah Smith and Mark Johnson. 2007. Weighted and probabilistic context-free grammars are equally expressive. Computational Linguistics, pages 477– 491. find
  39. Ashish Vaswani and Kenji Sagae. 2016. Efficient structured inference for transition-based parsing with neural networks and error states. Transactions of the Association for Computational Linguistics, 4:183–196. find
  40. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In Advances in Neural Information Processing Systems 28, pages 2755– 2763. find
  41. Taro Watanabe and Eiichiro Sumita. 2015. Transition-based neural constituent parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1169–1179. find
  42. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics, pages 323–333. find
  43. Kaisheng Yao, Baolin Peng, Geoffrey Zweig, Dong Yu, Xiaolong Li, and Feng Gao. 2014. Recurrent conditional random field for language understanding. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP ’14). find
  44. Majid Yazdani and James Henderson. 2015. Incremental recurrent neural network dependency parser with search-based discriminative training. In Proceedings of the Nineteenth Conference on Computational Natural Language Learning, pages 142–152. find
  45. Hao Zhang and Ryan McDonald. 2014. Enforcing structural diversity in cube-pruned dependency parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 656–661. find
  46. Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes, Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip H. S. Torr. 2015. Conditional random fields as recurrent neural networks. In The IEEE International Conference on Computer Vision (ICCV), pages 1529–1537. find
  47. Jie Zhou and Wei Xu. 2015. End-to-end learning of semantic role labeling using recurrent neural networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1127–1137. find
  48. Hao Zhou, Yue Zhang, and Jiajun Chen. 2015. A neural probabilistic structured-prediction model for transition-based dependency parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics, pages 1213–1222. find