Generating Non-Projective Word Order in Statistical Linearization

What it is about

A projective linearizer can only produce word orders in which no two edges cross, and many languages need crossings. The paper handles this by lifting. A classifier predicts, for each dependent in an unordered tree, how far it should be moved up toward the root. The lifted tree is then linearized by an ordinary projective algorithm. The method is tested on six languages, including English, German, Dutch, Danish, Hungarian and Czech. It gives significant gains on all of them, and the largest gains are in the V2 languages, where the finite verb takes second position. A human study on German found that judges preferred the lifted outputs for sentences that were originally non-projective. The incorrect liftings did not always make a bad sentence.

Ideas

• I1. Lifting as a counted rule. For each triple of relation, head tag and dependent tag, count how often the gold edge was lifted, and lift by the most frequent step. This needs no classifier and is fully deterministic with BTreeMap tables.
• I2. Count the crossing edges. For each language in the data the team uses, report the share of sentences with a non-projective edge. A projective linearizer can never reproduce those sentences, so this share is a hard ceiling to state beside any score.
• I3. Use lifting on the target side. When a meta token's head differs between two translations (open problem 1), lift the dependent instead of attaching it by hand. Test on the verse pairs whether lifting fixes more tokens than it breaks.

For Mova

The fit is en/src/lin.rs, where word order is decided, and the head-attachment problem of tools/translate (meta.rs). The classifier is not needed. The lifting table is the idea to try, and the crossing-edge ceiling is the measure to report first. Run each measure twice for identical output.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{bohnet2012generating,
  title = {{Generating Non-Projective Word Order in Statistical Linearization}},
  author = {Bohnet, Bernd and Björkelund, Anders and Kuhn, Jonas and Seeker, Wolfgang and Zarriess, Sina},
  booktitle = {Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning},
  year = {2012},
  url = {https://aclanthology.org/D12-1085/}
}

References

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

1. A. Belz and E. Kow. 2011. Discrete vs. Continuous Rating Scales for Language Evaluation in NLP. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 230–235, Portland, Oregon, USA, June. Association for Computational Linguistics. find
2. A. Belz, M. White, D. Espinosa, D. Hogan, E. Kow, and A. Stent. 2011. The First Surface Realisation Shared Task: Overview and Evaluation Results. In ENLG’11. find our card
3. A. Böhmová, J. Hajič, E. Hajičová, and B. Hladká. 2000. The Prague Dependency Treebank: A Three-level annotation scenario. In A. Abeillé, editor, Treebanks: Building and using syntactically annotated corpora., chapter 1, pages 103–127. Kluwer Academic Publishers, Amsterdam. find
4. B. Bohnet, L. Wanner, S. Mille, and A. Burga. 2010. Broad coverage multilingual deep sentence generation with a stochastic multi-level realizer. In Coling 2010, pages 98–106. find our card
5. B. Bohnet, S. Mille, B. Favre, and L. Wanner. 2011. <stumaba>: From deep representation to surface. In Proceedings of the Generation Challenges Session at the 13th European Workshop on NLG, pages 232–235, Nancy, France. find
6. B. Bohnet. 2004. A Graph Grammar Approach to Map Between Dependency Trees and Topological Models. In IJCNLP, pages 636–645. find
7. N. Bröker. 1998. Separating Surface Order and Syntactic Relations in a Dependency Grammar. In COLING-ACL 98. find
8. S. Buchholz and E. Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of the Tenth Conference on Computational Natural Language Learning, pages 149–164, Morristown, NJ, USA. Association for Computational Linguistics. find our card
9. A. Cahill, M. Forst, and C. Rohrer. 2007. Stochastic realisation ranking for a free word order language. ENLG ’07, pages 17–24. find
10. K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2006. Online Passive-Aggressive Algorithms. Journal of Machine Learning Research, 7:551–585. find
11. D. Duchier and R. Debusmann. 2001. Topological dependency trees: A constraint-based account of linear precedence. In Proceedings of the ACL. find
12. R. Fan, K. Chang, C. Hsieh, X. Wang, and C. Lin. 2008. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9:1871–1874. find
13. K. Filippova and M. Strube. 2007. Generating constituent order in german clauses. In ACL, pages 320– 327. find
14. K. Filippova and M. Strube. 2009. Tree linearization in English: improving language model based approaches. In NAACL, pages 225–228, Morristown, NJ, USA. Association for Computational Linguistics. find our card
15. M. Gamon, E. Ringger, R. Moore, S. Corston-Olivier, and Z. Zhang. 2002. Extraposition: A case study in German sentence realization. In Proceedings of Coling 2002. Association for Computational Linguistics. find
16. K. Gerdes and S. Kahane. 2001. Word order in german: A formal dependency grammar using a topological hierarchy. In Proceedings of the ACL. find
17. Y. Guo, D. Hogan, and J. van Genabith. 2011. Dcu at generation challenges 2011 surface realisation track. In Proceedings of the Generation Challenges Session at the 13th European Workshop on NLG, pages 227– 229. find
18. J. Hajič, M. Ciaramita, R. Johansson, D. Kawahara, M.-A. Martı́, L. Màrquez, A. Meyers, J. Nivre, S. Padó, J. Stepánek, P. Stranák, M. Surdeanu, N. Xue, and Y. Zhang. 2009. The CoNLL-2009 shared task: Syntactic and Semantic dependencies in multiple languages. In Proceedings of the 13th CoNLL Shared Task, pages 1–18, Boulder, Colorado. find our card
19. E. Hajičová, J. Havelka, P. Sgall, K. Veselá, and D. Zeman. 2004. Issues of projectivity in the prague dependency treebank. Prague Bulletin of Mathematical Linguistics, 81. find
20. W. He, H. Wang, Y. Guo, and T. Liu. 2009. Dependency Based Chinese Sentence Realization. In Proceedings of the ACL and of the IJCNLP, pages 809–816. find
21. S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In COLING-ACL, pages 646– 652. find
22. A. Kathol and C. Pollard. 1995. Extraposition via complex domain formation. In Meeting of the Association for Computational Linguistics, pages 174–180. find
23. R. Kneser and H. Ney. 1995. In In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, pages 181–184. find
24. E. Kow and A. Belz. 2012. LGRT-Eval: A Toolkit for Creating Online Language Evaluation Experiments. In Proceedings of the 8th International Conference on Language Resources and Evaluation (LREC’12). find
25. I. Langkilde and K. Knight. 1998. Generation that exploits corpus-based statistical knowledge. In COLING-ACL, pages 704–710. find
26. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 99–106, Ann Arbor, Michigan, June. Association for Computational Linguistics. find
27. O. Rambow and A. K. Joshi. 1994. A formal look at dependency grammars and phrase-structure grammars, with special consideration of word-order phenomena. In Leo Wanner, editor, Current Issues in Meaning-Text Theory. Pinter, London, UK. find
28. M. Reape. 1989. A logical treatment of semi-free word order and bounded discontinuous constituency. In Proceedings of the EACL, EACL ’89, pages 103–110. find
29. E. Ringger, M. Gamon, R. C. Moore, D. Rojas, M. Smets, and S. Corston-Oliver. 2004. Linguistically informed statistical models of constituent structure for ordering in sentence realization. In COLING ’04, pages 673– 679. find
30. W. Seeker and J. Kuhn. 2012. Making Ellipses Explicit in Dependency Conversion for a German Treebank. In Proceedings of LREC 2012, Istanbul, Turkey. European Language Resources Association (ELRA). find
31. A. Stent. 2011. Att-0: Submission to generation challenges 2011 surface realization shared task. In Proceedings of the Generation Challenges Session at the 13th European Workshop on Natural Language Generation, pages 230–231, Nancy, France, September. Association for Computational Linguistics. find
32. V. Vincze, D. Szauter, A. Almási, G. Móra, Z. Alexin, and J. Csirik. 2010. Hungarian Dependency Treebank. In Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC 2010), pages 1855–1862, Valletta, Malta. find
33. S. Wan, M. Dras, R. Dale, and C. Paris. 2009. Improving grammaticality in statistical sentence generation: Introducing a dependency spanning tree algorithm with an argument satisfaction model. In EACL, pages 852– 860. find
34. M. White and R. Rajkumar. 2009. Perceptron reranking for CCG realization. In EMNLP’09, pages 410–419, Singapore, August. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/bohnet-2012-generating-non-projective-word-order/