Why Synchronous Tree Substitution Grammars?

What it is about

Maletti compares synchronous tree substitution grammars (STSG), the translation model used in syntax-based MT, with a model from the theory of tree transducers: the extended multi bottom-up tree transducer (MBOT), which differs in one feature. The paper is formal and has no experiments. It compares the two models on four standard algorithms: binarization, regular restriction of the input language, composition and application. For each it gives the complexity bound. An STSG can be turned into an equivalent MBOT in linear time. An MBOT can be fully binarized in linear time, while an STSG admits only partial binarizations. The cost of regular restriction for STSG grows with the number of nonterminals per rule, while for MBOT it is a polynomial in the number of states with a fixed exponent. Only MBOTs can be composed. The conclusion is that MBOTs are better for the algorithms, with a caveat: they have the finite-copying property, which makes forward and backward application harder, so the full power should not be used.

Ideas

• I1. Count the nonterminals per rule of each translation table in tools/translate (the author delta and the encoder chunks). The paper's bounds say that the cost of a regular restriction grows with that number, so the count predicts which tables will be slow to restrict.
• I2. Composition of the standard table with an author delta. Where the delta is one more layer on the standard, a composed table would give one pass instead of two. Check on the Bible pairs that the composed output is byte-identical to the two-pass output before using it.
• I3. Keep rules small by splitting a long chunk into a chunk head and its dependents, each with its own rule. This is the same idea as open problem 3, and the paper gives the cost argument for it.
• I4. Copying limits. Mark any rule that copies a meta token's subtree into two places, and report how many there are. A copy is a source of the finite-copying cost, so the count is a measure to watch.

For Mova

The code is tools/translate (profile.rs and the delta rule). The paper's results are complexity bounds, not measurements, so the ideas need a test before any claim: count the rule sizes first, then time the restriction on the real tables. The model is not neural, so its counts can be kept in ordered maps.

Topics: Machine translation

Cite

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

@inproceedings{maletti2010why,
  title = {{Why Synchronous Tree Substitution Grammars?}},
  author = {Maletti, Andreas},
  booktitle = {Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/N10-1130/}
}

References

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

1. Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Prentice Hall. find
2. André Arnold and Max Dauchet. 1982. Morphismes et bimorphismes d’arbres. Theoret. Comput. Sci., 20(1):33–93. find
3. Y. Bar-Hillel, M. Perles, and E. Shamir. 1964. On formal properties of simple phrase structure grammars. In Language and Information: Selected Essays on their Theory and Application, pages 116–150. Addison Wesley. find
4. Jean Berstel and Christophe Reutenauer. 1982. Recognizable formal power series on trees. Theoret. Comput. Sci., 18(2):115–148. find
5. Björn Borchardt. 2004. A pumping lemma and decidability problems for recognizable tree series. Acta Cybernet., 16(4):509–544. find
6. Peter F. Brown, John Cocke, Stephen A. Della Pietra, Vincent J. Della Pietra, Fredrick Jelinek, John D. Lafferty, Robert L. Mercer, and Paul S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):79–85. find
7. Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. Mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–311. find
8. David Chiang and Kevin Knight. 2006. An introduction to synchronous grammars. In Proc. ACL tutorial. find
9. David Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. ACL, pages 263–270. find our card
10. John DeNero, Mohit Bansal, Adam Pauls, and Dan Klein. 2009a. Efficient parsing for transducer grammars. In Proc. NAACL, pages 227–235. find
11. John DeNero, Adam Pauls, and Dan Klein. 2009b. Asynchronous binarization for synchronous grammars. In Proc. ACL, pages 141–144. find
12. Samuel Eilenberg. 1974. Automata, Languages, and Machines. Academic Press. find
13. Joost Engelfriet, Grzegorz Rozenberg, and Giora Slutzki. 1980. Tree transducers, L systems, and two-way machines. J. Comput. System Sci., 20(2):150–202. find
14. Joost Engelfriet, Eric Lilin, and Andreas Maletti. 2009. Extended multi bottom-up tree transducers: Composition and decomposition. Acta Inform., 46(8):561–590. find
15. Zoltán Ésik. 1984. Decidability results concerning tree transducers II. Acta Cybernet., 6(3):303–314. find
16. Zoltán Fülöp and Heiko Vogler. 2009. Weighted tree automata and tree transducers. In Handbook of Weighted Automata, chapter IX, pages 313–403. Springer. find
17. Zoltán Fülöp. 1994. Undecidable properties of deterministic top-down tree transducers. Theoret. Comput. Sci., 134(2):311–328. find
18. Jonathan S. Golan. 1999. Semirings and their Applications. Kluwer Academic, Dordrecht. find
19. Jonathan Graehl, Kevin Knight, and Jonathan May. 2008. Training tree transducers. Computational Linguistics, 34(3):391–427. find
20. John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison Wesley. find
21. Liang Huang, Hao Zhang, Daniel Gildea, and Kevin Knight. 2009. Binarization of synchronous context-free grammars. Computational Linguistics, 35(4):559–595. find
22. Kevin Knight. 2007. Capturing practical natural language transformations. Machine Translation, 21(2):121–133. find
23. Eric Lilin. 1981. Propriétés de clôture d’une extension de transducteurs d’arbres déterministes. In CAAP, volume 112 of LNCS, pages 280–289. Springer. find
24. Andreas Maletti and Giorgio Satta. 2009. Parsing algorithms based on tree automata. In Proc. IWPT, pages 1–12. find
25. Andreas Maletti, Jonathan Graehl, Mark Hopkins, and Kevin Knight. 2009. The power of extended top-down tree transducers. SIAM J. Comput., 39(2):410–430. find
26. Mehryar Mohri. 2009. Weighted automata algorithms. In Handbook of Weighted Automata, pages 213–254. Springer. find
27. Mark-Jan Nederhof and Giorgio Satta. 2003. Probabilistic parsing as intersection. In Proc. IWPT, pages 137– 148. find
28. Mark-Jan Nederhof and Giorgio Satta. 2008. Computation of distances for regular and context-free probabilistic languages. Theoret. Comput. Sci., 395(2– 3):235–254. find
29. Jean-Claude Raoult. 1993. Recursively defined tree transductions. In Proc. RTA, volume 690 of LNCS, pages 343–357. Springer. find
30. Jacques Sakarovitch. 2009. Rational and recognisable power series. In Handbook of Weighted Automata, chapter IV, pages 105–174. Springer. find
31. Giorgio Satta. 2010. Translation algorithms by means of language intersection. Manuscript. find
32. Marcel Paul Schützenberger. 1961. On the definition of a family of automata. Information and Control, 4(2– 3):245–270. find
33. Wei Wang, Kevin Knight, and Daniel Marcu. 2007. Binarizing syntax trees to improve syntax-based machine translation accuracy. In Proc. EMNLP-CoNLL, pages 746–754. find
34. Hao Zhang, Liang Huang, Daniel Gildea, and Kevin Knight. 2006. Synchronous binarization for machine translation. In Proc. NAACL-HLT, pages 256–263. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/maletti-2010-why-synchronous-tree-substitution-grammars/