Mova0.5 pre-release⌕
☰
home / docs / papers / Machine translation / Transition-Based Syntactic Linearization

Transition-Based Syntactic Linearization

What it is about

Syntactic linearization takes a bag of words and optional syntactic constraints and builds the sentence and its tree together. The usual search is best-first over bottom-up steps, which is slow and has no bound on time. The paper instead builds the output from left to right with beam search, using a transition system that extends incremental parsing, so that word ordering and parsing happen in the same actions. Because of this design the running time is bounded, quadratic in the length, and every run yields a full sentence. On the Penn Treebank the system gave higher accuracy than the best-first baseline and decoded faster. Constraints on the input, such as known heads, improve the result, and the authors also study how the beam size changes accuracy.

Ideas

For Mova

The paper fits en/src/lin.rs on the English side and the target-side stack of tools/translate. The beam over transitions is a plain deterministic search that Mova can implement without a neural model. Measure the accuracy against time curve on dev, and do not touch the release test.

Topics: Dependency parsing · Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/v1/n15-1012

@inproceedings{liu2015transition,
  title = {{Transition-Based Syntactic Linearization}},
  author = {Liu, Yijia and Zhang, Yue and Che, Wanxiang and Qin, Bing},
  booktitle = {Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2015},
  doi = {10.3115/v1/n15-1012},
  url = {https://doi.org/10.3115/v1/n15-1012}
}

References

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

  1. Anja Belz, Mike White, Dominic Espinosa, Eric Kow, Deirdre Hogan, and Amanda Stent. 2011. The first surface realisation shared task: Overview and evaluation results. In Proceedings of the Generation Challenges Session at the 13th European Workshop on Natural Language Generation, pages 217– 226, Nancy, France, September. Association for Computational Linguistics. find our card
  2. Bernd Bohnet, Leo Wanner, Simon Mill, and Alicia Burga. 2010. Broad coverage multilingual deep sentence generation with a stochastic multi-level realizer. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 98–106, Beijing, China, August. Coling 2010 Organizing Committee. find our card
  3. 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), Main Volume, pages 111– 118, Barcelona, Spain, July. find our card
  4. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pages 1–8. Association for Computational Linguistics, July. find our card
  5. Adrià de Gispert, Marcus Tomalin, and Bill Byrne. 2014. Word ordering with phrase-based grammars. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 259–268, Gothenburg, Sweden, April. Association for Computational Linguistics. find
  6. Wei He, Haifeng Wang, Yuqing Guo, and Ting Liu. 2009. Dependency based chinese sentence realization. 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 809–816, Suntec, Singapore, August. Association for Computational Linguistics. find
  7. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1–11, Uppsala, Sweden, July. Association for Computational Linguistics. find
  8. Ryan T McDonald and Fernando CN Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL. find our card
  9. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. find our card
  10. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA, July. Association for Computational Linguistics. find our card
  11. Ehud Reiter and Robert Dale. 1997. Building applied natural language generation systems. Nat. Lang. Eng., 3(1):57–87, March. find
  12. Kenji Sagae, Alon Lavie, and Brian MacWhinney. 2005. Automatic measurement of syntactic development in child language. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 197–204, Ann Arbor, Michigan, June. Association for Computational Linguistics. find
  13. Linfeng Song, Yue Zhang, Kai Song, and Qun Liu. 2014. Joint morphological generation and syntactic linearization. In AAAI, pages 1522–1528. find
  14. Stephen Wan, Mark Dras, Robert Dale, and Cécile Paris. 2009. Improving grammaticality in statistical sentence generation: Introducing a dependency spanning tree algorithm with an argument satisfaction model. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009), pages 852– 860, Athens, Greece, March. Association for Computational Linguistics. find
  15. Michael White and Rajakrishnan Rajkumar. 2009. Perceptron reranking for CCG realization. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 410–419, Singapore, August. Association for Computational Linguistics. find
  16. Michael White. 2004a. Reining in CCG chart realization. In In Proc. INLG-04, pages 182–191. find
  17. Michael White. 2004b. Reining in ccg chart realization. In Natural Language Generation, pages 182– 191. Springer. find
  18. Wenduan Xu, Stephen Clark, and Yue Zhang. 2014. Shift-reduce ccg parsing with a dependency model. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 218–227, Baltimore, Maryland, June. Association for Computational Linguistics. find
  19. Yue Zhang and Stephen Clark. 2011a. Syntactic processing using the generalized perceptron and beam search. Computational Linguistics, 37(1):105–151. find
  20. Yue Zhang and Stephen Clark. 2011b. Syntax-based grammaticality improvement using CCG and guided search. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1147–1157, Edinburgh, Scotland, UK., July. Association for Computational Linguistics. find
  21. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 188–193, Portland, Oregon, USA, June. Association for Computational Linguistics. find
  22. Yue Zhang, Graeme Blackwood, and Stephen Clark. 2012. Syntax-based word ordering incorporating a large-scale language model. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 736– 746, Avignon, France, April. Association for Computational Linguistics. find
  23. Yue Zhang. 2013. Partial-tree linearization: Generalized word ordering for text synthesis. In IJCAI. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/liu-2015-transition-based-syntactic-linearization/