BinLin: A Simple Method of Dependency Tree Linearization

What it is about

The paper is a system report for the shallow track of SR'18. The input is a bag of lemmatised UD nodes with their tags and morphology. The system works in two stages: it first orders the lemmas, and then it conjugates and inflects each word. The contribution is a sequential way of ordering lemmas. It is simple and it gives promising scores for its size. The authors name its limits: the result depends on the order in which the input is read, and the method only produces projective orders, which drops the long-range crossings that some languages need. The paper is short and its value is the simplicity of the design, not a new model.

Ideas

• I1. Count-based sequential ordering. Place the next lemma by a table of counted precedence between a candidate and the lemmas already placed, conditioned on the relation to the head. The table is built from UD data with BTreeMap order, and decoding is greedy and deterministic.
• I2. Order-invariance control. Shuffle the input node list and check whether the output changes. The paper reports order sensitivity, which the design should not have. A non-zero change is a red flag, and this test works as a negative control for any sequential ordering rule Mova adds.
• I3. Separate the errors. Run the paper's split: first score the order alone, then score the inflection alone, using en/src/morph.rs for the second. Stratify errors by whether the lemma was seen in training, which tells whether a failure is in the rules or in the coverage.
• I4. Measure the projective ceiling. Count the share of non-projective sentences in the English dev data. That share is the upper bound on any projective linearizer, the same point the paper makes.

For Mova

The paper fits en/src/lin.rs (ordering) and en/src/morph.rs (inflection). The sequential, count-based ordering is the part that carries over, with the order-invariance control added to the tests. Report exact match on dev, run twice, and state the projective ceiling beside the score.

Topics: Dependency parsing · Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/w18-3602

@inproceedings{puzikov2018binlin,
  title = {{BinLin: A Simple Method of Dependency Tree Linearization}},
  author = {Puzikov, Yevgeniy and Gurevych, Iryna},
  booktitle = {Proceedings of the First Workshop on Multilingual Surface Realisation},
  year = {2018},
  doi = {10.18653/v1/w18-3602},
  url = {https://doi.org/10.18653/v1/w18-3602}
}

References

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

1. pages 1724–1734, Doha, Qatar. Association for Computational Linguistics. find
2. Roee Aharoni and Yoav Goldberg. 2017. Morphological Inflection Generation with Hard Monotonic Attention. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2004–2015, Vancouver, Canada. Association for Computational Linguistics. find
3. George Doddington. 2002. Automatic Evaluation of Machine Translation Quality Using N-gram Co-occurrence Statistics. In Proceedings of the Second International Conference on Human Language Technology Research, pages 138–145, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc. find
4. Malin Ahlberg, Markus Forsberg, and Mans Hulden. 2015. Paradigm Classification in Supervised Learning of Morphology. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1024–1029, Denver, Colorado. Association for Computational Linguistics. find
5. Markus Dreyer and Jason Eisner. 2011. Discovering Morphological Paradigms from Plain Text Using a Dirichlet Process Mixture Model. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 616–627, Edinburgh, Scotland, UK. Association for Computational Linguistics. find
6. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014. Neural Machine Translation by Jointly Learning to Align and Translate. CoRR, abs/1409.0473. ↗
7. Greg Durrett and John DeNero. 2013. Supervised Learning of Complete Morphological Paradigms. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1185–1195, Atlanta, Georgia. Association for Computational Linguistics. find our card
8. Srinivas Bangalore and Owen Rambow. 2000. Exploiting a Probabilistic Hierarchical Model for Generation. In Proceedings of the 18th Conference on Computational Linguistics: Volume 1, pages 42–48, Saarbrücken, Germany. Association for Computational Linguistics. find
9. Michael Elhadad and Jacques Robin. 1992. Controlling Content Realization with Functional Unification Grammars. In Proceedings of the 6th International Workshop on Natural Language Generation: Aspects of Automated Natural Language Generation, pages 89–104, London, UK, UK. Springer-Verlag. find
10. 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. Association for Computational Linguistics. find our card
11. Manaal Faruqui, Yulia Tsvetkov, Graham Neubig, and Chris Dyer. 2016. Morphological Inflection Generation Using Character Sequence to Sequence Learning. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 634–643, San Diego, California. Association for Computational Linguistics. find
12. Böhmová, Alena and Hajič, Jan and Hajičová, Eva and Hladká, Barbora. 2003. The Prague Dependency Treebank: a Three-level Annotation Scenario, chapter 7. Kluwer Academic Publishers. find
13. Yoav Goldberg and Michael Elhadad. 2010. An Efficient Algorithm for Easy-first Non-directional Dependency Parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750, Los Angeles, California. Association for Computational Linguistics. find
14. Bernd Bohnet, Leo Wanner, Simon Mille, 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, pages 98– 106, Beijing, China. Association for Computational Linguistics. find our card
15. Yuqing Guo, Josef van Genabith, and Haifeng Wang. 2008. Dependency-based N-gram Models for General Purpose Sentence Realisation. In Proceedings of the 22nd International Conference on Computational Linguistics (COLING 2008), pages 297–304, Manchester, UK. COLING 2008 Organizing Committee. find
16. John Carroll, Ann Copestake, Dan Flickinger, and Victor Poznanski. 1999. An Efficient Chart Generator for (Semi-)Lexicalist Grammars. In Proceedings of the 7th European Workshop on Natural Language Generation, pages 86–95, Toulouse, France. find
17. 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: Volume 2 - Volume 2, ACL ’09, pages 809–816, Suntec, Singapore. Association for Computational Linguistics. find
18. Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning Phrase Representations Using RNN Encoder-decoder for Statistical Machine Translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. 2017. Automatic Differentiation in PyTorch. In NIPS 2017 Workshop Autodiff, Long Beach, California, USA. find
19. Ronald M. Kaplan and Martin Kay. 1994. Regular Models of Phonological Rule Systems. Computational Linguistics, 20(3):331–378. find
20. Kimmo Koskenniemi. 1983. Two-level Morphology: a General Computational Model for Word-form Recognition and Production. Publications, 11:1– 160. find
21. Ratish Puduppully, Yue Zhang, and Manish Shrivastava. 2016. Transition-based Syntactic Linearization with Lookahead Features. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 488– 493, San Diego, California. Association for Computational Linguistics. find our card
22. Matthias Trautner Kromann. 2003. The Danish Dependency Treebank and the DTAG Treebank Tool. In Proceedings of the 2nd Workshop on Treebanks and Linguistic Theories, pages 217–220. find
23. Gerasimos Lampouras and Andreas Vlachos. 2016. Imitation Learning for Language Generation from Unaligned Data. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 1101–1112, Osaka, Japan. find
24. The COLING 2016 Organizing Committee. find
25. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to Sequence Learning with Neural Networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 3104–3112. Curran Associates, Inc. find
26. Irene Langkilde-Geary. 2002. An Empirical Verification of Coverage and Correctness for a General-purpose Sentence Generator. In Proceedings of the 2nd International Natural Language Generation Conference, pages 17–24, Harriman, New York, USA. find
27. Ramakrishna Vedantam, C. Lawrence Zitnick, and Devi Parikh. 2015. CIDEr: Consensus-based Image Description Evaluation. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4566–4575, Boston, MA, USA. IEEE Computer Society. find
28. Yijia Liu, Yue Zhang, Wanxiang Che, and Bing Qin. 2015. Transition-based Syntactic Linearization. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 113–122, Denver, Colorado. Association for Computational Linguistics. find our card
29. Michael White, Rajakrishnan Rajkumar, and Scott Martin. 2007. Towards Broad Coverage Surface Realization with CCG. In Proceedings of the 2007 Workshop on Using Corpora for NLG: Language Generation and Machine Translation (UCNLG+MT), pages 22–30, Copenhagen, Danmark. find our card
30. Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. 2013. Rectifier Nonlinearities Improve Neural Network Acoustic Models. In ICML Workshop on Deep Learning for Audio, Speech and Language Processing, Atlanta, USA. find
31. Richard Wicentowski. 2004. Multilingual Noise-robust Supervised Morphological Analysis Using the Wordframe Model. In Proceedings of the 7th Meeting of the ACL Special Interest Group in Computational Phonology: Current Themes in Computational Phonology and Morphology, SIGMorPhon ’04, pages 70–77, Barcelona, Spain. Association for Computational Linguistics. find
32. Simon Mille, Anja Belz, Bernd Bohnet, Yvette Graham, Emily Pitler, and Leo Wanner. 2018. The First Multilingual Surface Realisation Shared Task (SR’18): Overview and Evaluation Results. In Proceedings of the 1st Workshop on Multilingual Surface Realisation (MSR), 56th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1–10, Melbourne, Australia. find our card
33. David Yarowsky and Richard Wicentowski. 2000. Minimally Supervised Morphological Analysis by Multimodal Alignment. In Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, ACL ’00, pages 207–216, Hong Kong. Association for Computational Linguistics. find
34. Joakim Nivre. 2006. Constraints on Non-Projective Dependency Parsing. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 73–80, Trento, Italy. Association for Computational Linguistics. find
35. Yue Zhang and Stephen Clark. 2011. Syntactic Processing Using the Generalized Perceptron and Beam Search. Computational Linguistics, 37(1):105–151. find
36. 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. Association for Computational Linguistics. *Figure 7: Data statistics computed for the Arabic data.* *Figure 8: Data statistics computed for the Czech data.* *Figure 9: Data statistics computed for the English data.* *Figure 10: Data statistics computed for the Spanish data.* *Figure 11: Data statistics computed for the Finnish data.* *Figure 12: Data statistics computed for the French data.* *Figure 13: Data statistics computed for the Italian data.* *Figure 14: Data statistics computed for the Dutch data.* *Figure 15: Data statistics computed for the Portuguese data.* *Figure 16: Data statistics computed for the Russian data.* find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/puzikov-2018-binlin-simple-method-dependency-tree/