Training Tree Transducers

What it is about

The paper argues that probabilistic models of language should be written as tree transducers, since the theory of tree automata is well developed and gives tools that string models have. It defines extended-LHS tree transducers (xR), in which a rule may match a pattern of several nodes and may copy input subtrees, and a tree-to-string variant (xRS). Parsing a tree transduction is done through regular tree grammars: the set of derivations of a transducer on a pair of trees is itself a regular tree grammar, and inside-outside weights over it give the expected rule counts. EM training then runs as in the forward-backward method for string transducers, with each iteration guaranteed to raise the likelihood. A worked example shows the rules learned on a small tree pair. The paper contains no large-scale experiment. It states the algorithms and the training procedure, and says that its method generalises the forward-backward EM of finite-state transducers.

Ideas

• I1. Train expected rule counts of a tree-to-tree reader on verse pairs with inside-outside over the derivations, so that the head decisions of the parse become hidden choices weighted by the data. Run a fixed number of iterations and keep the counts in ordered maps, so the result is the same on every run.
• I2. Check encoder outputs against a counted tree grammar. Count the local subtree patterns of the English UD trees produced by the standard stack, and reject an output tree that uses a pattern never seen. This is a cheap well-formedness test for open problem 3, the encoder that writes trees.
• I3. Allow copying in the xRS rules only where it is declared. A meta token that feeds two places (a pronoun repeated in a clause) is a copy and should be marked, so that the residual can show where copies come from.

For Mova

The code is tools/translate (the encoder in profile.rs, the reader in meta.rs). The EM method is probabilistic, but its output is a table of counts, which Mova can keep in ordered maps and check for identical runs. The paper has no results, so the first measure is the pattern rejection rate on the Bible outputs before any claim.

Topics: Machine translation

Cite

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

@inproceedings{graehl2004training,
  title = {{Training Tree Transducers}},
  author = {Graehl, Jonathan and Knight, Kevin},
  booktitle = {Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HLT-NAACL 2004},
  year = {2004},
  url = {https://aclanthology.org/N04-1014/}
}

References

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

1. Aho, A. V. and J. D. Ullman. 1971. Translations of a context-free grammar. Information and Control, 19:439–475. find
2. Alshawi, Hiyan, Srinivas Bangalore, and Shona Douglas. 2000. Learning dependency translation models as collections of finite state head transducers. Computational Linguistics, 26(1):45–60. find
3. Baker, J. K. 1979. Trainable grammars for speech recognition. In D. Klatt and J. Wolf, editors, Speech Communication Papers for the 97th Meeting of the Acoustical Society of America. Boston, MA, pages 547–550. find
4. Bangalore, Srinivas and Owen Rambow. 2000. Exploiting a probabilistic hierarchical model for generation. In Proc. COLING. find
5. Baum, L. E. and J. A. Eagon. 1967. An inequality with application to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematicians Society, 73:360–363. find
6. Charniak, Eugene. 2001. Immediate-head parsing for language models. In Proc. ACL. find
7. Chelba, C. and F. Jelinek. 2000. Structured language modeling. Computer Speech and Language, 14(4):283–332. find
8. Collins, Michael. 1997. Three generative, lexicalised models for statistical parsing. In Proc. ACL. find
9. Comon, H., M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. 1997. Tree automata techniques and applications. Available on www.grappa.univ-lille3.fr/tata. release October, 1st 2002. find
10. Corston-Oliver, Simon, Michael Gamon, Eric K. Ringger, and Robert Moore. 2002. An overview of Amalgam, a machine-learned generation module. In Proc. IWNLG. find
11. Dempster, A. P., N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39(1):1–38. find
12. Eisner, Jason. 2003. Learning non-isomorphic tree mappings for machine translation. In Proc. ACL (companion volume). find our card
13. Engelfriet, J. 1975. Bottom-up and top-down tree transformations—a comparison. Math. Systems Theory, 9(3):198–231. find
14. Gécseg, F. and M. Steinby. 1984. Tree Automata. Akadémiai Kiadó, Budapest. find
15. Gildea, Daniel. 2003. Loosely tree-based alignment for machine translation. In Proc. ACL. find
16. Joshi, A. and Y. Schabes. 1997. Tree-adjoining grammars. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages (Vol. 3). Springer, NY. find
17. Klein, Dan and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proc. ACL. find our card
18. Knight, K. and Y. Al-Onaizan. 1998. Translation with finite-state devices. In Proc. AMTA. find
19. Knight, K. and D. Marcu. 2002. Summarization beyond sentence extraction— a probabilistic approach to sentence compression. Artificial Intelligence, 139(1). find
20. Kumar, S. and W. Byrne. 2003. A weighted finite state transducer implementation of the alignment template model for statistical machine translation. In Proceedings of HLT-NAACL. find
21. Langkilde, I. 2000. Forest-based statistical sentence generation. In Proc. NAACL. find
22. Langkilde, I. and K. Knight. 1998. Generation that exploits corpus-based statistical knowledge. In Proc. ACL. find
23. Lari, K. and S. J. Young. 1990. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4. find
24. Nederhof, Mark-Jan and Giorgio Satta. 2002. Parsing non-recursive CFGs. In Proc. ACL. find
25. Pang, Bo, Kevin Knight, and Daniel Marcu. 2003. Syntax-based alignment of multiple translations extracting paraphrases and generating new sentences. In Proc. HLT/NAACL. find our card
26. Rounds, William C. 1970. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257–287. find
27. Schabes, Yves. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, Department of Computer and Information Science, University of Pennsylvania. find
28. Thatcher, J. W. 1970. Generalized 2 sequential machine maps. J. Comput. System Sci., 4:339–367. find
29. Viterbi, A. 1967. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Information Theory, IT-13. find
30. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–404. find our card
31. Yamada, Kenji and Kevin Knight. 2001. A syntax-based statistical translation model. In Proc. ACL. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/graehl-2004-training-tree-transducers/