Bayesian Inference for Finite-State Transducers

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 447–455, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Bayesian Inference for Finite-State Transducers∗ David Chiang1 Jonathan Graehl1 Kevin Knight1 Adam Pauls2 Sujith Ravi1 1Information Sciences Institute University of Southern California 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 2Computer Science Division University of California at Berkeley Soda Hall Berkeley, CA 94720 Abstract We describe a Bayesian inference algorithm that can be used to train any cascade of weighted finite-state transducers on end-to- end data. We also investigate the problem of automatically selecting from among mul- tiple training runs. Our experiments on four different tasks demonstrate the genericity of this framework, and, where applicable, large improvements in performance over EM. We also show, for unsupervised part-of-speech tagging, that automatic run selection gives a large improvement over previous Bayesian ap- proaches. 1 Introduction In this paper, we investigate Bayesian infer- ence for weighted finite-state transducers (WFSTs). Many natural language models can be captured by weighted finite-state transducers (Pereira et al., 1994; Sproat et al., 1996; Knight and Al-Onaizan, 1998; Clark, 2002; Kolak et al., 2003; Mathias and Byrne, 2006), which offer several benefits: • WFSTs provide a uniform knowledge represen- tation. • Complex problems can be broken down into a cascade of simple WFSTs. • Input- and output-epsilon transitions allow compact designs. • Generic algorithms exist for doing inferences with WFSTs. These include best-path de- coding, k-best path extraction, composition, ∗The authors are listed in alphabetical order. Please direct correspondence to Sujith Ravi (sravi@isi.edu). This work was supported by NSF grant IIS-0904684 and DARPA contract HR0011-06-C0022. intersection, minimization, determinization, forward-backward training, forward-backward pruning, stochastic generation, and projection. • Software toolkits implement these generic al- gorithms, allowing designers to concentrate on novel models rather than problem-specific in- ference code. This leads to faster scientific ex- perimentation with fewer bugs. Weighted tree transducers play the same role for problems that involve the creation and transforma- tion of tree structures (Knight and Graehl, 2005). Of course, many problems do not fit either the finite- state string or tree transducer framework, but in this paper, we concentrate on those that do. Bayesian inference schemes have become popu- lar recently in natural language processing for their ability to manage uncertainty about model param- eters and to allow designers to incorporate prior knowledge flexibly. Task-accuracy results have gen- erally been favorable. However, it can be time- consuming to apply Bayesian inference methods to each new problem. Designers typically build cus- tom, problem-specific sampling operators for ex- ploring the derivation space. They may factor their programs to get some code re-use from one problem to the next, but highly generic tools for string and tree processing are not available. In this paper, we marry the world of finite-state machines with the world of Bayesian inference, and we test our methods across a range of natural lan- guage problems. Our contributions are: • We describe a Bayesian inference algorithm …

Content truncated to 500 words