Compilation of Weighted Finite-State Transducers from Decision Trees

Compilation of Weighted Finite-State Transducers from Decision Trees Richard Sproat Bell Laboratories 700 Mountain Avenue Murray Hill, N J, USA rws@bell-labs, tom Michael Riley AT&T Research 600 Mountain Avenue Murray Hill, N J, USA riley@research, att. com Abstract We report on a method for compiling decision trees into weighted finite-state transducers. The key assumptions are that the tree predictions specify how to rewrite symbols from an input string, and the decision at each tree node is stateable in terms of regular expressions on the input string. Each leaf node can then be treated as a separate rule where the left and right contexts are constructable from the decisions made traversing the tree from the root to the leaf. These rules are compiled into trans- ducers using the weighted rewrite-rule rule-compilation algorithm described in (Mohri and Sproat, 1996). 1 Introduction Much attention has been devoted recently to methods for inferring linguistic models from data. One powerful inference method that has been used in various applications are decision trees, and in particular classification and regression trees (Breiman et al., 1984). An increasing amount of attention has also been focussed on finite-state methods for imple- menting linguistic models, in particular finite- state transducers and weighted finite-state trans- ducers; see (Kaplan and Kay, 1994; Pereira et al., 1994, inter alia). The reason for the renewed in- terest in finite-state mechanisms is clear. Finite- state machines provide a mathematically well- understood computational framework for repre- senting a wide variety of information, both in NLP and speech processing. Lexicons, phonological rules, Hidden Markov Models, and (regular) gram- mars are all representable as finite-state machines, and finite-state operations such as union, intersec- tion and composition mean that information from these various sources can be combined in useful 215 and computationally attractive ways. The reader is referred to the above-cited papers (among oth- ers) for more extensive justification. This paper reports on a marriage of these two strands of research in the form of an algorithm for compiling the information in decision trees into weighted finite-state transducers. 1 Given this al- gorithm, information inferred from data and rep- resented in a tree can be used directly in a system that represents other information, such as lexicons or grammars, in the form of finite-state machines. 2 Quick Review of Tree-Based Modeling A general introduction to classification and regres- sion trees ('CART') including the algorithm for growing trees from data can be found in (Breiman et al., 1984). Applications of tree-based modeling to problems in speech and NLP are discussed in (Riley, 1989; Riley, 1991; Wang and Hirschberg, 1992; Magerman, 1995, inter alia). In this section we presume that one has already trained a tree or set of trees, and we merely remind the reader of the salient points in the interpretation of those trees. Consider the tree depicted in Figure 1, which was trained on the TIMIT database (Fisher et al., 1987), and which models the phonetic realization of the English phoneme/aa/(/a/) in various en- vironments (Riley, 1991). When …

Content truncated to 500 words