Tree Linearization in English: Improving Language Model Based Approaches

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. The word-order facts sit in 21. The simple clause, 22. Phrases: noun, adjective, adverb and prepositional phrases and 29. Ellipsis, word order and 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

@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}
}

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
2. Filippova, K. & M. Strube (2007). Generating constituent order in German clauses. In Proc. of ACL-07, pp. 320– 327. find
3. Goodman, J. T. (2001). A bit of progress in language modeling. Computer Speech and Language, pp. 403– 434. find
4. Jurafsky, D. & J. H. Martin (2008). Speech and Language Processing. Upper Saddle River, N.J.: Prentice Hall. find
5. Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30:81–93. find
6. Klein, D. & C. D. Manning (2003). Accurate unlexicalized parsing. In Proc. of ACL-03, pp. 423–430. find our card
7. Langkilde, I. & K. Knight (1998). Generation that exploits corpus-based statistical knowledge. In Proc. of COLING-ACL-98, pp. 704–710. find
8. Lapata, M. (2006). Automatic evaluation of information ordering: Kendall’s tau. Computational Linguistics, 32(4):471–484. find
9. Marsi, E. & E. Krahmer (2005). Explorations in sentence fusion. In Proc. of ENLG-05, pp. 109–117. find
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
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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/filippova-2009-tree-linearization-english-improving-language/