[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/liu-2015-transition-based-syntactic-linearization/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/) / Transition-Based Syntactic Linearization

# Transition-Based Syntactic Linearization

**Authors:** [Yijia Liu](https://md.mova.elamur.ai/free/en/docs/papers/authors/yijia-liu/), [Yue Zhang](https://md.mova.elamur.ai/free/en/docs/papers/authors/yue-zhang/), [Wanxiang Che](https://md.mova.elamur.ai/free/en/docs/papers/authors/wanxiang-che/), [Bing Qin](https://md.mova.elamur.ai/free/en/docs/papers/authors/bing-qin/) · **Year:** 2015 · **Venue:** Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL 2015) **Link:** [aclanthology.org/N15-1012](https://aclanthology.org/N15-1012/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**34** citations](https://openalex.org/works?filter=cites:W2296207831) openalex · 2026-10-18[**18** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/liu-2015-transition-based-syntactic-linearization/) of the 140673 papers whose bibliographies we read[Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies](https://aclanthology.org/volumes/N15-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/N15-1012/)
- [PDF](https://aclanthology.org/N15-1012.pdf)
- [DOI 10.3115/v1/n15-1012](https://doi.org/10.3115/v1/n15-1012)
- [OpenAlex](https://openalex.org/W2296207831)

**Authors (4)**

1. [Yijia Liu](https://openalex.org/A5100704424) [ORCID](https://orcid.org/0000-0001-6311-9955) · h 23 · 2078 citations · 69 works
2. [Yue Zhang](https://openalex.org/A5100333729) [ORCID](https://orcid.org/0000-0002-5214-2268) · h 60 · 14466 citations · 344 works
3. [Wanxiang Che](https://openalex.org/A5019108029) [ORCID](https://orcid.org/0000-0002-3907-0335) · h 50 · 9312 citations · 360 works
4. [Bing Qin](https://openalex.org/A5017671620) [ORCID](https://orcid.org/0000-0002-2543-5604) · h 48 · 18986 citations · 399 works

Citations and author metrics from openalex (2026-10-18); authors with the same name are not always told apart.

## 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

- I1. Beam search in `en/src/lin.rs`. The current linearizer uses side tables and Markov chains over classes. A left-to-right transition beam of size K would give bounded time. Report dev exact match and time for K from 1 to 64 and keep the tie-breaking in `BTreeMap` order so runs are identical.
- I2. Input-constraint ablation. Give the linearizer the head and relation for each token, then remove one at a time and measure the loss. This is the same test the paper runs, and it maps onto the residual classes of the translator.
- I3. Guaranteed full output. Because the transition system always ends in a full sentence, the translator's linearization step never returns a fragment. Count any fragment in the current stack as a bug to fix, not a score.

## 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](https://md.mova.elamur.ai/free/en/docs/papers/topics/dependency-parsing/) · [Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/topics/machine-translation/)

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.3115/v1/n15-1012](https://doi.org/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}
}
```

- [← previous Tree-to-String Alignment Template for Statistical Machine Translation](https://md.mova.elamur.ai/free/en/docs/papers/liu-2006-tree-string-alignment-template-statistical/)
- [next → Text Generation from Discourse Representation Structures](https://md.mova.elamur.ai/free/en/docs/papers/liu-2021-text-generation-discourse-representation-structures/)
- [↑ back to Machine translation](https://md.mova.elamur.ai/free/en/docs/papers/mtrans/)

## 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](https://scholar.google.com/scholar?q=Anja+Belz%2C+Mike+White%2C+Dominic+Espinosa%2C+Eric+Kow%2C+Deirdre+Hogan%2C+and+Amanda+Stent%2E+2011%2E+The+first+surface+realisation+shared+task%3A+Overview+and+evaluation+results%2E+In+Proceedings+of+the+Generation+C) [our card](https://md.mova.elamur.ai/free/en/docs/papers/belz-2011-first-surface-realisation-shared-task/)
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](https://scholar.google.com/scholar?q=Bernd+Bohnet%2C+Leo+Wanner%2C+Simon+Mill%2C+and+Alicia+Burga%2E+2010%2E+Broad+coverage+multilingual+deep+sentence+generation+with+a+stochastic+multi%2Dlevel+realizer%2E+In+Proceedings+of+the+23rd+International+Conf) [our card](https://md.mova.elamur.ai/free/en/docs/papers/bohnet-2010-broad-coverage-multilingual-deep-sentence/)
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](https://scholar.google.com/scholar?q=Michael+Collins+and+Brian+Roark%2E+2004%2E+Incremental+parsing+with+the+perceptron+algorithm%2E+In+Proceedings+of+the+42nd+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%E2%80%9904%29%2C+Main+Volume%2C+pag) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2004-incremental-parsing-perceptron-algorithm/)
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](https://scholar.google.com/scholar?q=Michael+Collins%2E+2002%2E+Discriminative+training+methods+for+hidden+markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proceedings+of+the+2002+Conference+on+Empirical+Methods+in+Natura) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2002-discriminative-training-methods-hidden-markov/)
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](https://scholar.google.com/scholar?q=Adria%CC%80+de+Gispert%2C+Marcus+Tomalin%2C+and+Bill+Byrne%2E+2014%2E+Word+ordering+with+phrase%2Dbased+grammars%2E+In+Proceedings+of+the+14th+Conference+of+the+European+Chapter+of+the+Association+for+Computational+Li)
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](https://scholar.google.com/scholar?q=Wei+He%2C+Haifeng+Wang%2C+Yuqing+Guo%2C+and+Ting+Liu%2E+2009%2E+Dependency+based+chinese+sentence+realization%2E+In+Proceedings+of+the+Joint+Conference+of+the+47th+Annual+Meeting+of+the+ACL+and+the+4th+Internatio)
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](https://scholar.google.com/scholar?q=Terry+Koo+and+Michael+Collins%2E+2010%2E+Efficient+third%2Dorder+dependency+parsers%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+1%E2%80%9311%2C+Uppsala%2C+Sweden%2C+)
8. Ryan T McDonald and Fernando CN Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL. [find](https://scholar.google.com/scholar?q=Ryan+T+McDonald+and+Fernando+CN+Pereira%2E+2006%2E+Online+learning+of+approximate+dependency+parsing+algorithms%2E+In+EACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)
9. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2008%2E+Algorithms+for+deterministic+incremental+dependency+parsing%2E+Computational+Linguistics%2C+34%284%29%3A513%E2%80%93553%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/)
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](https://scholar.google.com/scholar?q=Kishore+Papineni%2C+Salim+Roukos%2C+Todd+Ward%2C+and+Wei%2DJing+Zhu%2E+2002%2E+Bleu%3A+a+method+for+automatic+evaluation+of+machine+translation%2E+In+Proceedings+of+40th+Annual+Meeting+of+the+Association+for+Computat) [our card](https://md.mova.elamur.ai/free/en/docs/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
11. Ehud Reiter and Robert Dale. 1997. Building applied natural language generation systems. Nat. Lang. Eng., 3(1):57–87, March. [find](https://scholar.google.com/scholar?q=Ehud+Reiter+and+Robert+Dale%2E+1997%2E+Building+applied+natural+language+generation+systems%2E+Nat%2E+Lang%2E+Eng%2E%2C+3%281%29%3A57%E2%80%9387%2C+March%2E)
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](https://scholar.google.com/scholar?q=Kenji+Sagae%2C+Alon+Lavie%2C+and+Brian+MacWhinney%2E+2005%2E+Automatic+measurement+of+syntactic+development+in+child+language%2E+In+Proceedings+of+the+43rd+Annual+Meeting+of+the+Association+for+Computational+Li)
13. Linfeng Song, Yue Zhang, Kai Song, and Qun Liu. 2014. Joint morphological generation and syntactic linearization. In AAAI, pages 1522–1528. [find](https://scholar.google.com/scholar?q=Linfeng+Song%2C+Yue+Zhang%2C+Kai+Song%2C+and+Qun+Liu%2E+2014%2E+Joint+morphological+generation+and+syntactic+linearization%2E+In+AAAI%2C+pages+1522%E2%80%931528%2E)
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](https://scholar.google.com/scholar?q=Stephen+Wan%2C+Mark+Dras%2C+Robert+Dale%2C+and+Ce%CC%81cile+Paris%2E+2009%2E+Improving+grammaticality+in+statistical+sentence+generation%3A+Introducing+a+dependency+spanning+tree+algorithm+with+an+argument+satisfactio)
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](https://scholar.google.com/scholar?q=Michael+White+and+Rajakrishnan+Rajkumar%2E+2009%2E+Perceptron+reranking+for+CCG+realization%2E+In+Proceedings+of+the+2009+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+410%E2%80%93419%2C+Singa)
16. Michael White. 2004a. Reining in CCG chart realization. In In Proc. INLG-04, pages 182–191. [find](https://scholar.google.com/scholar?q=Michael+White%2E+2004a%2E+Reining+in+CCG+chart+realization%2E+In+In+Proc%2E+INLG%2D04%2C+pages+182%E2%80%93191%2E)
17. Michael White. 2004b. Reining in ccg chart realization. In Natural Language Generation, pages 182– 191. Springer. [find](https://scholar.google.com/scholar?q=Michael+White%2E+2004b%2E+Reining+in+ccg+chart+realization%2E+In+Natural+Language+Generation%2C+pages+182%E2%80%93+191%2E+Springer%2E)
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](https://scholar.google.com/scholar?q=Wenduan+Xu%2C+Stephen+Clark%2C+and+Yue+Zhang%2E+2014%2E+Shift%2Dreduce+ccg+parsing+with+a+dependency+model%2E+In+Proceedings+of+the+52nd+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28Volume+1%3A+)
19. Yue Zhang and Stephen Clark. 2011a. Syntactic processing using the generalized perceptron and beam search. Computational Linguistics, 37(1):105–151. [find](https://scholar.google.com/scholar?q=Yue+Zhang+and+Stephen+Clark%2E+2011a%2E+Syntactic+processing+using+the+generalized+perceptron+and+beam+search%2E+Computational+Linguistics%2C+37%281%29%3A105%E2%80%93151%2E)
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](https://scholar.google.com/scholar?q=Yue+Zhang+and+Stephen+Clark%2E+2011b%2E+Syntax%2Dbased+grammaticality+improvement+using+CCG+and+guided+search%2E+In+Proceedings+of+the+2011+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+page)
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](https://scholar.google.com/scholar?q=Yue+Zhang+and+Joakim+Nivre%2E+2011%2E+Transition%2Dbased+dependency+parsing+with+rich+non%2Dlocal+features%2E+In+Proceedings+of+the+49th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+La)
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](https://scholar.google.com/scholar?q=Yue+Zhang%2C+Graeme+Blackwood%2C+and+Stephen+Clark%2E+2012%2E+Syntax%2Dbased+word+ordering+incorporating+a+large%2Dscale+language+model%2E+In+Proceedings+of+the+13th+Conference+of+the+European+Chapter+of+the+Associ)
23. Yue Zhang. 2013. Partial-tree linearization: Generalized word ordering for text synthesis. In IJCAI. [find](https://scholar.google.com/scholar?q=Yue+Zhang%2E+2013%2E+Partial%2Dtree+linearization%3A+Generalized+word+ordering+for+text+synthesis%2E+In+IJCAI%2E)