Training Tree Transducers

Training Tree Transducers Jonathan Graehl Information Sciences Institute University of Southern California 4676 Admiralty Way Marina del Rey, CA 90292 graehl@isi.edu Kevin Knight Information Sciences Institute University of Southern California 4676 Admiralty Way Marina del Rey, CA 90292 knight@isi.edu Abstract Many probabilistic models for natural language are now written in terms of hierarchical tree structure. Tree-based modeling still lacks many of the standard tools taken for granted in (finite- state) string-based modeling. The theory of tree transducer automata provides a possible frame- work to draw on, as it has been worked out in an extensive literature. We motivate the use of tree transducers for natural language and address the training problem for probabilistic tree-to- tree and tree-to-string transducers. 1 Introduction Much of natural language work over the past decade has employed probabilistic finite-state transducers (FSTs) operating on strings. This has occurred somewhat under the influence of speech recognition, where transducing acoustic sequences to word sequences is neatly captured by left-to-right stateful substitution. Many conceptual tools exist, such as Viterbi decoding (Viterbi, 1967) and forward-backward training (Baum and Eagon, 1967), as well as generic software toolkits. Moreover, a surprising variety of problems are attackable with FSTs, from part- of-speech tagging to letter-to-sound conversion to name transliteration. However, language problems like machine transla- tion break this mold, because they involve massive re- ordering of symbols, and because the transformation pro- cesses seem sensitive to hierarchical tree structure. Re- cently, specific probabilistic tree-based models have been proposed not only for machine translation (Wu, 1997; Alshawi, Bangalore, and Douglas, 2000; Yamada and Knight, 2001; Gildea, 2003; Eisner, 2003), but also for This work was supported by DARPA contract F49620-00- 1-0337 and ARDA contract MDA904-02-C-0450. summarization (Knight and Marcu, 2002), paraphras- ing (Pang, Knight, and Marcu, 2003), natural language generation (Langkilde and Knight, 1998; Bangalore and Rambow, 2000; Corston-Oliver et al., 2002), and lan- guage modeling (Baker, 1979; Lari and Young, 1990; Collins, 1997; Chelba and Jelinek, 2000; Charniak, 2001; Klein and Manning, 2003). It is useful to understand generic algorithms that may support all these tasks and more. (Rounds, 1970) and (Thatcher, 1970) independently introduced tree transducers as a generalization of FSTs. Rounds was motivated by natural language. The Rounds tree transducer is very similar to a left-to-right FST, ex- cept that it works top-down, pursuing subtrees in paral- lel, with each subtree transformed depending only on its own passed-down state. This class of transducer is often nowadays called R, for “Root-to-frontier” (Gécseg and Steinby, 1984). Rounds uses a mathematics-oriented example of an R transducer, which we summarize in Figure 1. At each point in the top-down traversal, the transducer chooses a production to apply, based only on the current state and the current root symbol. The traversal continues until there are no more state-annotated nodes. Non- deterministic transducers may have several productions with the same left-hand side, and therefore some free choices to make during transduction. An R transducer compactly represents a potentially- infinite set of input/output tree pairs: exactly those pairs (T1, …

Content truncated to 500 words