[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/filippova-2009-tree-linearization-english-improving-language/)

[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/) / [English](https://md.mova.elamur.ai/free/en/docs/papers/en/) / Tree Linearization in English: Improving Language Model Based Approaches

# Tree Linearization in English: Improving Language Model Based Approaches

**Authors:** Katja Filippova, [Michael Strube](https://md.mova.elamur.ai/free/en/docs/papers/authors/michael-strube/) · **Year:** 2009 · **Venue:** Proceedings of NAACL HLT 2009: Short Papers (Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, Companion Volume) **Link:** [aclanthology.org/N09-2057](https://aclanthology.org/N09-2057/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) (ACL Anthology, before 2016) — summary only

[**38** citations](https://openalex.org/works?filter=cites:W1965703460) openalex-snapshot · 2026-10-14[**18** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/filippova-2009-tree-linearization-english-improving-language/) of the 140673 papers whose bibliographies we read[Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Papers](https://aclanthology.org/volumes/N09-2/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/N09-2057/)
- [PDF](https://aclanthology.org/N09-2057.pdf)
- [DOI 10.3115/1620853.1620915](https://doi.org/10.3115/1620853.1620915)
- [OpenAlex](https://openalex.org/W1965703460)

**Authors (2)**

1. [Katja Filippova](https://openalex.org/A5037657908) [ORCID](https://orcid.org/0009-0007-5308-0904) · [Semantic Scholar](https://www.semanticscholar.org/author/3017324) · h 22 · 1855 citations · 54 works
2. [Michael Strube](https://openalex.org/A5020347604) [ORCID](https://orcid.org/0000-0002-4731-8142) · [Semantic Scholar](https://www.semanticscholar.org/author/31380436) · h 74 · 20622 citations · 483 works

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

## What it is about

The paper compares two ways of turning a dependency tree into a word string in English. The standard method ("overgenerate and rank") makes all permutations allowed by a few hard constraints and picks the one a trigram language model prefers. The second method keeps the trigram model for the order inside phrases, and uses two maximum-entropy classifiers over linguistic features (part of speech, syntactic role, length, pronominalisation) to order the clause constituents: one picks the first constituent, the other decides pairwise precedence. The data are about 5,000 phrases and 5,000 clauses from a Wall Street Journal subset of the TIPSTER corpus, parsed automatically. On phrases the trigram model reaches 76% accuracy for non-trivial phrases and 91% over all phrases. On clauses the trigram model reaches 49% and the combined method 67%, with Kendall's tau 0.49 against 0.71. The authors conclude that trigrams suit phrases, while clauses need a richer model.

## Ideas

- I1. `en/src/lin.rs`: split linearisation in two. Phrase order by a count-based n-gram table over the phrase tokens, with a cap on the number of permutations tried (the paper uses 20,000). Clause order by rules and a small classifier. Report phrase and clause accuracy separately, never pooled.
- I2. Hard ordering constraints as a rule table: determiners, possessives, quantifiers and modifiers precede the head; coordinated elements and prepositional objects follow it. Measure how many permutations each constraint removes on the UD EWT dev trees (the paper's example drops 96 to 2).
- I3. Clause level as a sorting problem: a "first constituent" scorer plus a pairwise precedence scorer, both as perceptron features in the style of `en/src/parse.rs`. The precedence scorer must be checked for transitivity before sorting, as the paper assumes.
- I4. Use the paper's own metrics for the linearizer: exact-order accuracy, Kendall's tau and the edit-distance measure d_i. Add the three-sentence example ("earlier today", "she", "him", "an email") as a unit test with a negative control, where the reordered sentence must score worse.

## For Mova

The linearizer is `en/src/lin.rs`; its data come from the parser in `en/src/parse.rs` and the UD trees of [20. Syntax: the Universal Dependencies frame](https://md.mova.elamur.ai/free/en/docs/languages/en/20-syntax-overview/). The word-order facts sit in [21. The simple clause](https://md.mova.elamur.ai/free/en/docs/languages/en/21-clause-structure/), [22. Phrases: noun, adjective, adverb and prepositional phrases](https://md.mova.elamur.ai/free/en/docs/languages/en/22-phrases/) and [29. Ellipsis, word order and information structure](https://md.mova.elamur.ai/free/en/docs/languages/en/29-ellipsis-word-order-information-structure/). Measures: `en` linearisation accuracy on UD EWT dev, split into phrase and clause, run twice for determinism. The corpus used in the paper is licensed by its publisher, so only the method and the measures are used, not the data.

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.3115/1620853.1620915](https://doi.org/10.3115/1620853.1620915)

```
@inproceedings{filippova2009tree,
  title = {{Tree Linearization in English: Improving Language Model Based Approaches}},
  author = {Filippova, Katja and Strube, Michael},
  booktitle = {Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Papers},
  year = {2009},
  doi = {10.3115/1620853.1620915},
  url = {https://doi.org/10.3115/1620853.1620915}
}
```

- [← previous Connectives of English Speech: the Correct Usage of Prepositions, Conjunctions, Relative Pronouns and Adverbs](https://md.mova.elamur.ai/free/en/docs/papers/fernald-1904-connectives-english-speech-correct/)
- [next → Using Lexical Dependency and Ontological Knowledge to Improve a Detailed Syntactic and Semantic Tagger of English](https://md.mova.elamur.ai/free/en/docs/papers/finch-2006-lexical-dependency-ontological-knowledge-improve/)
- [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/)

## References

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

1. Clarkson, P. & R. Rosenfeld (1997). Statistical language modeling using the CMU-Cambridge toolkit. In Proc. of EUROSPEECH-97, pp. 2707–2710. [find](https://scholar.google.com/scholar?q=Clarkson%2C+P%2E+%26+R%2E+Rosenfeld+%281997%29%2E+Statistical+language+modeling+using+the+CMU%2DCambridge+toolkit%2E+In+Proc%2E+of+EUROSPEECH%2D97%2C+pp%2E+2707%E2%80%932710%2E)
2. Filippova, K. & M. Strube (2007). Generating constituent order in German clauses. In Proc. of ACL-07, pp. 320– 327. [find](https://scholar.google.com/scholar?q=Filippova%2C+K%2E+%26+M%2E+Strube+%282007%29%2E+Generating+constituent+order+in+German+clauses%2E+In+Proc%2E+of+ACL%2D07%2C+pp%2E+320%E2%80%93+327%2E)
3. Goodman, J. T. (2001). A bit of progress in language modeling. Computer Speech and Language, pp. 403– 434. [↗](https://doi.org/10.1006/csla.2001.0174)
4. Jurafsky, D. & J. H. Martin (2008). Speech and Language Processing. Upper Saddle River, N.J.: Prentice Hall. [find](https://scholar.google.com/scholar?q=Jurafsky%2C+D%2E+%26+J%2E+H%2E+Martin+%282008%29%2E+Speech+and+Language+Processing%2E+Upper+Saddle+River%2C+N%2EJ%2E%3A+Prentice+Hall%2E)
5. Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30:81–93. [↗](https://doi.org/10.1093/biomet/30.1-2.81)
6. Klein, D. & C. D. Manning (2003). Accurate unlexicalized parsing. In Proc. of ACL-03, pp. 423–430. [find](https://scholar.google.com/scholar?q=Klein%2C+D%2E+%26+C%2E+D%2E+Manning+%282003%29%2E+Accurate+unlexicalized+parsing%2E+In+Proc%2E+of+ACL%2D03%2C+pp%2E+423%E2%80%93430%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2003-klein-accurate-unlexicalized-parsing/)
7. Langkilde, I. & K. Knight (1998). Generation that exploits corpus-based statistical knowledge. In Proc. of COLING-ACL-98, pp. 704–710. [find](https://scholar.google.com/scholar?q=Langkilde%2C+I%2E+%26+K%2E+Knight+%281998%29%2E+Generation+that+exploits+corpus%2Dbased+statistical+knowledge%2E+In+Proc%2E+of+COLING%2DACL%2D98%2C+pp%2E+704%E2%80%93710%2E)
8. Lapata, M. (2006). Automatic evaluation of information ordering: Kendall’s tau. Computational Linguistics, 32(4):471–484. [↗](https://doi.org/10.1162/coli.2006.32.4.471)
9. Marsi, E. & E. Krahmer (2005). Explorations in sentence fusion. In Proc. of ENLG-05, pp. 109–117. [find](https://scholar.google.com/scholar?q=Marsi%2C+E%2E+%26+E%2E+Krahmer+%282005%29%2E+Explorations+in+sentence+fusion%2E+In+Proc%2E+of+ENLG%2D05%2C+pp%2E+109%E2%80%93117%2E)
10. Ringger, E., M. Gamon, R. C. Moore, D. Rojas, M. Smets & S. Corston-Oliver (2004). Linguistically informed statistical models of constituent structure for ordering in sentence realization. In Proc. of COLING-04, pp. 673–679. [find](https://scholar.google.com/scholar?q=Ringger%2C+E%2E%2C+M%2E+Gamon%2C+R%2E+C%2E+Moore%2C+D%2E+Rojas%2C+M%2E+Smets+%26+S%2E+Corston%2DOliver+%282004%29%2E+Linguistically+informed+statistical+models+of+constituent+structure+for+ordering+in+sentence+realization%2E+In+Proc%2E+of)
11. Uchimoto, K., M. Murata, Q. Ma, S. Sekine & H. Isahara (2000). Word order acquisition from corpora. In Proc. of COLING-00, pp. 871–877. [find](https://scholar.google.com/scholar?q=Uchimoto%2C+K%2E%2C+M%2E+Murata%2C+Q%2E+Ma%2C+S%2E+Sekine+%26+H%2E+Isahara+%282000%29%2E+Word+order+acquisition+from+corpora%2E+In+Proc%2E+of+COLING%2D00%2C+pp%2E+871%E2%80%93877%2E)