Head-First Linearization with Tree-Structured Representation

What it is about

The paper linearises a dependency tree, that is, it finds the word order of an unordered tree. It has two parts. The encoder is a bidirectional Tree-LSTM that passes information first up the tree and then down, so that each token sees the whole tree. The decoder is head-first: it starts at the head and attaches dependents on the left and on the right in turn. On the SR'18 shallow data the combined system with a morphology step reached the best reported results and beat both the shared task participants and earlier state-of-the-art systems. A probing test shows that the encoder carries information from the entire tree. The authors also note that the earlier decoder of Bohnet and colleagues is still a strong baseline. The method is neural, so only its structure can be reused.

Ideas

• I1. Head-first ordering as a rule. In en/src/lin.rs, start from the head and place each dependent on the left or the right by a count table over (relation, side, head tag). Build the table from data with BTreeMap order. This keeps the decoder's order and drops the network.
• I2. Count-based whole-tree context. Replace the Tree-LSTM with a sum of counts over the subtree of each token (its relation, its head tag, its children's relations). Check whether this gives the same ordering accuracy on dev as the side tables that already exist.
• I3. For the translator's encoder, which should write trees and not strings (open problem 3), write the target tree in head-first order. The chunk of each meta token is then placed around its head, and the relation of the meta token decides the side.

For Mova

The paper fits en/src/lin.rs (the linearizer used on the target side) and the encoder of tools/translate (profile.rs). The neural encoder is not for Mova. The head-first decoding order and the probing idea carry over as count-based forms. Measure order accuracy on dev before and after, and run each twice to confirm identical output.

Topics: Machine translation

Cite

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

@inproceedings{yu2019head,
  title = {{Head-First Linearization with Tree-Structured Representation}},
  author = {Yu, Xiang and Falenska, Agnieszka and Vu, Ngoc Thang and Kuhn, Jonas},
  booktitle = {Proceedings of the 12th International Conference on Natural Language Generation},
  year = {2019},
  doi = {10.18653/v1/w19-8636},
  url = {https://doi.org/10.18653/v1/w19-8636}
}

References

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

1. 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. find
2. Henry Elder and Chris Hokamp. 2018. Generating High-Quality Surface Realizations Using Data Augmentation and Factored Sequence Models. In Proceedings of the First Workshop on Multilingual Surface Realisation, pages 49–53. find
3. 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. Association for Computational Linguistics. find
4. Michael Elhadad and Jacques Robin. 1992. Controlling Content Realization with Functional Unification Grammars. In International Workshop on Natural Language Generation, pages 89–104. Springer. find
5. Anja Belz, Michael 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 13th European workshop on natural language generation, pages 217–226. Association for Computational Linguistics. find our card
6. Thiago Castro Ferreira, Sander Wubben, and Emiel Krahmer. 2018. find
7. Surface Realization Shared Task 2018 (SR18): The Tilburg University Approach. In Irene Langkilde and Kevin Knight. 1998. Generation that Exploits Corpus-based Statistical Knowledge. In Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics-Volume 1, pages 704–710. Association for Computational Linguistics. Proceedings of the First Workshop on Multilingual Surface Realisation, pages 35–38. find
8. Katja Filippova and Michael Strube. 2009. Tree Linearization in English: Improving Language Model Based Approaches. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Papers, pages 225–228. Association for Computational Linguistics. find our card
9. Benoit Lavoie and Owen Rainbow. 1997. A Fast and Portable Realizer for Text Generation Systems. In Fifth Conference on Applied Natural Language Processing. find our card
10. Richard Futrell, Kyle Mahowald, and Edward Gibson. 2015. Quantifying Word Order Freedom in Dependency Corpora. In Proceedings of the third international conference on dependency linguistics (Depling 2015), pages 91–100. find
11. Haitao Liu. 2010. Dependency Direction as a Means of Word-Order Typology: A Method Based on Dependency Treebanks. Lingua, 120(6):1567–1578. find
12. 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. find our card
13. Edward Gibson. 1998. Linguistic Complexity: Locality of Syntactic Dependencies. Cognition, 68(1):1– 76. ↗
14. 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. Association for Computational Linguistics. find
15. Makoto Miwa and Mohit Bansal. 2016. End-to-End Relation Extraction using LSTMs on Sequences and Tree Structures. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1105– 1116. find
16. Alex Graves and Jürgen Schmidhuber. 2005. Frame-wise Phoneme Classification with Bidirectional LSTM and other Neural Network Architectures. Neural networks, 18(5-6):602–610. find
17. Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, et al. 2017. Dynet: The Dynamic Neural Network Toolkit. arXiv preprint arXiv:1701.03980. ↗
18. Kristina Gulordava. 2018. Word Order Variation and Dependency Length Minimisation: A Cross-Linguistic Computational Approach. Ph.D. thesis, University of Geneva. find
19. Joakim Nivre, Marie-Catherine De Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajic, Christopher D Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, et al. 2016. Universal Dependencies v1: A Multilingual Treebank Collection. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), pages 1659–1666. find our card
20. 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, pages 809–816. Association for Computational Linguistics. 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. find our card
22. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Comput., 9(8):1735– 1780. find
23. Katharina Kann and Hinrich Schütze. 2016. MED: The LMU system for the SIGMORPHON 2016 shared task on morphological reinflection. In Proceedings of the 14th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, pages 62–70. find
24. Ratish Puduppully, Yue Zhang, and Manish Shrivastava. 2017. Transition-Based Deep Input Linearization. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, volume 1, pages 643–654. find
25. David King and Michael White. 2018. The OSU Realizer for SRST ’18: Neural Sequence-to-Sequence Inflection and Incremental Locality-Based Linearization. In Proceedings of the First Workshop on Multilingual Surface Realisation, pages 39–48. find
26. Yevgeniy Puzikov and Iryna Gurevych. 2018. BinLin: A Simple Method of Dependency Tree Linearization. In Proceedings of the First Workshop on Multilingual Surface Realisation, pages 13–28. find our card
27. Linfeng Song, Yue Zhang, and Daniel Gildea. 2018. Neural Transition-based Syntactic Linearization. In Proceedings of the 11th International Conference on Natural Language Generation, pages 431–440, Tilburg University, The Netherlands. Association for Computational Linguistics. find our card
28. Kai Sheng Tai, Richard Socher, and Christopher D Manning. 2015. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), volume 1, pages 1556–1566. find
29. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer Networks. In Advances in Neural Information Processing Systems, pages 2692–2700. find
30. Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. 2018. Graph Neural Networks: A Review of Methods and Applications. arXiv preprint arXiv:1812.08434. ↗
31. Yao Zhou, Cong Liu, and Yan Pan. 2016. Modelling Sentence Pairs with Tree-structured Attentive Encoder. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 2912–2922. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/yu-2019-head-first-linearization-tree-structured/