Elamur Research⌕
☰
home / papers / 2017 / In-Order Transition-based Constituent Parsing

In-Order Transition-based Constituent Parsing

Summary

Transition-based constituent parsers usually build trees in one of two orders. Bottom-up parsers (post-order traversal) can use features from subtrees they have already built, but they have no lookahead about structure still to come. Top-down parsers (pre-order traversal) give global guidance, but they must commit to a phrase label before seeing its contents, so they depend heavily on the input encoder.

Liu and Zhang propose a third option: a transition system based on in-order traversal. The parser first shifts a phrase's leftmost child, then projects the parent label, then attaches the remaining children before closing the constituent. This mirrors how human readers anticipate upcoming phrases, and it avoids the language-specific binarization rules that bottom-up parsing requires. The authors compare all three strategies inside one stack-LSTM framework that follows Dyer et al. (2016).

On the English WSJ benchmark, the in-order parser outperforms both baselines and sets state-of-the-art results when combined with reranking. The work matters as the first controlled neural comparison of traversal orders, and it offers a simple, portable way to combine bottom-up and top-down evidence.

Key points

  • The system uses four actions: SHIFT, PJ-X (project nonterminal X), REDUCE and FINISH. It generalizes to "k-in-order" variants, where top-down corresponds to k=0 and bottom-up to k=∞; only k=1 is studied.
  • Greedy fully-supervised parsing scores 91.8 F1 on WSJ (English) and 86.1 F1 on Chinese. Reranking raises the English score to 93.6 F1 (supervised, Choe and Charniak 2016) and 94.2 F1 (semi-supervised).
  • After conversion to Stanford dependencies, the output achieves 96.2% UAS and 95.2% LAS, state-of-the-art at the time.
  • Per-label analysis shows the in-order parser is best on every constituent type. Among the baselines, top-down does better on WHNP because these phrases begin with a predictable question word.
  • Code is released at github.com/LeonCrashCode/InOrderParser.

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 Syntax & grammar formalisms

 Institutions

🎓Singapore University of Technology and DesignSingapore · Singapore20 works · 8,193 citations

Cite

Cite as Jiangming Liu and Yue Zhang. 2017. In-Order Transition-based Constituent Parsing. Transactions of the Association for Computational Linguistics.

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

@article{liu2017order,
  title = {{In-Order Transition-based Constituent Parsing}},
  author = {Jiangming Liu and Yue Zhang},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2017},
  doi = {10.1162/tacl\_a\_00070},
  url = {https://doi.org/10.1162/tacl_a_00070}
}

References

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

  1. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. In ACL, pages 2442–2452. our card
  2. Miguel Ballesteros, Yoav Goldberg, Chris Dyer, and Noah A Smith. 2016. Training with exploration improves a greedy stack-LSTM parser. In EMNLP, pages 2005–2010. find
  3. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine n-best parsing and MaxEnt discriminative reranking. In ACL, pages 173–180. our card
  4. Eugene Charniak. 2000. A maximum-entropy-inspired parser. In NAACL, pages 132–139. our card
  5. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In EMNLP, pages 740–750. our card
  6. Hao Cheng, Hao Fang, Xiaodong He, Jianfeng Gao, and Li Deng. 2016. Bi-directional attention with agreement for dependency parsing. In EMNLP, pages 2204–2214. find
  7. Do Kook Choe and Eugene Charniak. 2016. Parsing as language modeling. In EMNLP, pages 2331–2336. find
  8. Michael Collins. 2003. Head-driven statistical models for natural language parsing. Computational linguistics, 29(4):589–637. our card
  9. James Cross and Liang Huang. 2016. Span-based constituency parsing with a structure-label system and provably optimal dynamic oracles. In EMNLP, pages 1–11. our card
  10. Timothy Dozat and Christopher D. Manning. 2017. Deep biaffine attention for neural dependency parsing. In ICLR. our card
  11. Greg Durrett and Dan Klein. 2015. Neural CRF parsing. In ACL, pages 302–312. find
  12. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. In ACL, pages 334–343. our card
  13. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. 2016. Recurrent neural network grammars. In NAACL, pages 199–209 find
  14. Liang Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In ACL, pages 586– 594. find
  15. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632. our card
  16. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional LSTM feature representations. Transactions of the Association of Computational Linguistics, 4:313–327. our card
  17. Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, Graham Neubig, and Noah A. Smith. 2017. What do recurrent neural network grammars learn about syntax? In EACL, pages 1249–1258. find
  18. Mike Lewis, Kenton Lee, and Luke Zettlemoyer. 2016. LSTM CCG parsing. In NAACL, pages 221–231. our card
  19. Jiangming Liu and Yue Zhang. 2017. Shift-Reduce Constituent Parsing with Neural Lookahead Features. Transactions of the Association of Computational Linguistics, 5:45–58. find
  20. 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. our card
  21. Brian Roark and Mark Johnson. 1999. Efficient probabilistic top-down and left-corner parsing. In ACL, pages 421–428. find
  22. Brian Roark, Asaf Bachrach, Carlos Cardenas, and Christophe Pallier. 2009. Deriving lexical and syntactic expectation-based measures for psycholinguistic modeling via incremental top-down parsing. In EMNLP, pages 324–333. find
  23. Brian Roark. 2001. Robust probabilistic predictive syntactic processing: motivations, models, and applications. In Ph.D. thesis. find
  24. Daniel J. Rosenkrantz and Philip M. Lewis. 1970. Deterministic left corner parsing. In IEEE Conference Record of 11th Annual Symposium on Switching and Automata Theory, pages 139–152. find
  25. Kenji Sagae and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In IWPT, pages 125–132. our card
  26. William Schuler, Samir AbdelRahman, Tim Miller, and Lane Schwartz. 2010. Broad-coverage parsing using human-like memory constraints. Computational Linguistics, 36(1):1–30. find
  27. Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, and Masaaki Nagata. 2012. Bayesian symbol-refined tree substitution grammars for syntactic parsing. In ACL, pages 440–448. find
  28. Richard Socher, John Bauer, Christopher D. Manning, and Andrew Y. Ng. 2013. Parsing with compositional vector grammars. In ACL, pages 455–465. find
  29. Mark Steedman. 2000. The syntactic process, volume 24. find
  30. MIT Press. Marten Van Schijndel and William Schuler. 2013. An analysis of frequency-and memory-based processing costs. In HLT-NAACL, pages 95–105. find
  31. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In ICLR. find
  32. Zhiguo Wang and Nianwen Xue. 2014. Joint POS tagging and transition-based constituent parsing in Chinese with non-local features. In ACL, pages 733–742. find
  33. Zhiguo Wang, Haitao Mi, and Nianwen Xue. 2015. Feature optimization for constituent parsing via neural networks. In ACL-IJCNLP, pages 1138–1147. find
  34. Taro Watanabe and Eiichiro Sumita. 2015. Transition-based neural constituent parsing. In ACL, pages 1169– 1179. find
  35. Wenduan Xu. 2016. LSTM shift-reduce CCG parsing. In EMNLP, pages 1754–1764. find
  36. Naiwen Xue, Fei Xia, Fu-dong Chiou, and Martha Palmer. 2005. The Penn Chinese treebank: Phrase structure annotation of a large corpus. Natural Language Engineering, 11(2):207–238. find
  37. Yue Zhang and Stephen Clark. 2009. Transition-based parsing of the chinese treebank using a global discriminative model. In IWPT, pages 162–171. our card
  38. Muhua Zhu, Yue Zhang, Wenliang Chen, Min Zhang, and Jingbo Zhu. 2013. Fast and accurate shift-reduce constituent parsing. In ACL, pages 434–443. our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/liu-2017-order-transition-based-constituent-parsing/