Fast and Accurate Non-Projective Dependency Tree Linearization

What it is about

The paper treats linearization as a travelling-salesman problem. A biaffine model gives the cost of putting one token before another, and the costs are solved per subtree with a greedy TSP solver. The subtree orders are then combined into a projective tree. A transition system, borrowed from non-projective parsing, runs afterwards to restore the crossing edges. The method beats the previous best linearizer and is about ten times faster in training and decoding. The ablations are useful. Lemma and dependency relation carry most of the word-order signal, while UPOS and morphology add little. The greedy solver is almost as good as a more expensive metaheuristic, so speed costs little accuracy.

Ideas

• I1. Ablate the feature set of en/src/lin.rs. The paper finds that relation and lemma matter and the tags add little. Remove each POS and FEATS table in turn and report word-order accuracy on dev. This tells which tables are worth their size.
• I2. Count-based cost table. Set the cost of "a before b" to a smoothed count of that order for the same relation and head tag, drawn from the data. Solve each subtree greedily, then combine. This keeps the structure and drops the network, and it is fully deterministic.
• I3. Non-projective repair as a separate step. The paper's transition pass fixes crossing edges after projective decoding. The translator can use the same step when a meta token's head differs from the target tree (open problem 1), instead of re-attaching the token by hand.

For Mova

The paper bears most on en/src/lin.rs and on the target-side linearization of tools/translate. The biaffine scorer is not for Mova, but the cost-table form and the post-hoc repair are. Measure on dev, run twice for identical output, and keep the test set for the release run.

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/2020.acl-main.134

@inproceedings{yu2020fast,
  title = {{Fast and Accurate Non-Projective Dependency Tree Linearization}},
  author = {Yu, Xiang and Tannert, Simon and Vu, Ngoc Thang and Kuhn, Jonas},
  booktitle = {Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
  doi = {10.18653/v1/2020.acl-main.134},
  url = {https://doi.org/10.18653/v1/2020.acl-main.134}
}

References

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

1. David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. 2006. Concorde TSP Solver. find
2. 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 13th European Workshop on Natural Language Generation, pages 217–226, Nancy, France. Association for Computational Linguistics. find our card
3. Bernd Bohnet, Anders Björkelund, Jonas Kuhn, Wolfgang Seeker, and Sina Zarriess. 2012. Generating Non-Projective Word Order in Statistical Linearization. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 928–939, Jeju Island, Korea. Association for Computational Linguistics. find our card
4. 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. Association for Computational Linguistics. find our card
5. Timothy Dozat and Christopher D. Manning. 2016. Deep Biaffine Attention for Neural Dependency Parsing. ArXiv, abs/1611.01734. ↗ our card
6. Ulrich Germann, Michael Jahr, Kevin Knight, Daniel Marcu, and Kenji Yamada. 2001. Fast Decoding and Optimal Decoding for Machine Translation. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, pages 228– 235, Toulouse, France. Association for Computational Linguistics. find
7. Matic Horvat and William Byrne. 2014. A Graph-Based Approach to String Regeneration. In Proceedings of the Student Research Workshop at the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 85– 95, Gothenburg, Sweden. Association for Computational Linguistics. find
8. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations. Transactions of the Association for Computational Linguistics, 4:313–327. find our card
9. Kevin Knight. 1999. Decoding Complexity in Word-Replacement Translation Models. Computational Linguistics, 25(4):607–615. find
10. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columbia, Canada. Association for Computational Linguistics. find our card
11. 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 First Workshop on Multilingual Surface Realisation, pages 1–12, Melbourne, Australia. Association for Computational Linguistics. ↗ our card
12. Simon Mille, Anja Belz, Bernd Bohnet, Yvette Graham, and Leo Wanner. 2019. The Second Multilingual Surface Realisation Shared Task (SR’19): Overview and Evaluation Results. In Proceedings of the 2nd Workshop on Multilingual Surface Realisation (MSR 2019), pages 1–17, Hong Kong, China. Association for Computational Linguistics. find
13. Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul Michel, Yusuke Oda, Matthew Richardson, Naomi Saphra, Swabha Swayamdipta, and Pengcheng Yin. 2017. DyNet: The Dynamic Neural Network Toolkit. arXiv preprint arXiv:1701.03980. ↗
14. Joakim Nivre. 2009. Non-Projective Dependency Parsing in Expected Linear Time. 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, pages 351–359, Suntec, Singapore. Association for Computational Linguistics. find
15. Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajič, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016. Universal Dependencies v1: A Multilingual Treebank Collection. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16), pages 1659–1666, Portorož, Slovenia. European Language Resources Association (ELRA). find our card
16. Joakim Nivre and Jens 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. Association for Computational Linguistics. find
17. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a Method for Automatic Evaluation of Machine Translation. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics. find our card
18. 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
19. Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. 2005. Learning structured prediction models: A large margin approach. In Proceedings of the 22nd international conference on Machine learning, pages 896–903. ACM. find
20. Christoph Tillmann and Hermann Ney. 2003. Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation. Computational Linguistics, 29(1):97–133. find
21. Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. 2015. Order Matters: Sequence to Sequence for Sets. arXiv preprint arXiv:1511.06391. ↗
22. Christos Voudouris and Edward Tsang. 1999. Guided Local Search and its Application to the Traveling Salesman Problem. European journal of operational research, 113(2):469–499. find
23. Xiang Yu, Agnieszka Falenska, Marina Haid, Ngoc Thang Vu, and Jonas Kuhn. 2019a. IM-SurReal: IMS at the Surface Realization Shared Task 2019. In Proceedings of the 2nd Workshop on Multilingual Surface Realisation (MSR 2019), pages 50–58, Hong Kong, China. Association for Computational Linguistics. find
24. Xiang Yu, Agnieszka Falenska, Ngoc Thang Vu, and Jonas Kuhn. 2019b. Head-First Linearization with Tree-Structured Representation. In Proceedings of the 12th International Conference on Natural Language Generation, pages 279–289, Tokyo, Japan. Association for Computational Linguistics. find our card
25. Mikhail Zaslavskiy, Marc Dymetman, and Nicola Cancedda. 2009. Phrase-Based Statistical Machine Translation as a Traveling Salesman Problem. 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, pages 333–341, Suntec, Singapore. Association for Computational Linguistics. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/yu-2020-fast-accurate-non-projective-dependency/