Compiling Comp Ling: Weighted Dynamic Programming and the Dyna Language

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 281–290, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Compiling Comp Ling: Practical Weighted Dynamic Programming and the Dyna Language∗ Jason Eisner and Eric Goldlust and Noah A. Smith Department of Computer Science / Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218 USA {jason,goldlust,nasmith}@cs.jhu.edu Abstract Weighted deduction with aggregation is a powerful theoretical formalism that encompasses many NLP algorithms. This pa- per proposes a declarative specification language, Dyna; gives general agenda-based algorithms for computing weights and gradients; briefly discusses Dyna-to-Dyna program transforma- tions; and shows that a first implementation of a Dyna-to-C++ compiler produces code that is efficient enough for real NLP re- search, though still several times slower than hand-crafted code. 1 Introduction In this paper, we generalize some modern prob- abilistic parsing techniques to a broader class of weighted deductive algorithms. Our implemented system encapsulates these implementation tech- niques behind a clean interface—a small high-level specification language, Dyna, which compiles into C++ classes. This system should help the HLT com- munity to experiment more easily with new models and algorithms. 1.1 Dynamic programming as deduction The “parsing as deduction” framework (Pereira and Warren, 1983) is now over 20 years old. It provides an elegant notation for specifying a variety of pars- ing algorithms (Shieber et al., 1995), including algo- rithms for probabilistic or other semiring-weighted parsing (Goodman, 1999). In the parsing commu- nity, new algorithms are often stated simply as a set of deductive inference rules (Sikkel, 1997; Eisner and Satta, 1999). It is also straightforward to specify other NLP al- gorithms this way. Syntactic MT models, language models, and stack decoders can be easily described using deductive rules. So can operations on finite- state and infinite-state machines. ∗We thank Joshua Goodman, David McAllester, and Paul Ruhlen for useful early discussions; pioneer users Markus Dreyer, David Smith, and Roy Tromble for their feedback and input; John Blatz for discussion of program transformations; and several reviewers for useful criticism. This work was supported by NSF ITR grant IIS-0313193, ONR MURI grant N00014-01-1-0685, and a Hertz Foundation fellowship to the third author. The views expressed are not necessarily endorsed by the sponsors. 1.2 The role of toolkits One might regard deductive inference as merely a helpful perspective for teaching old algorithms and thinking about new ones, linking NLP to logic and classical AI. Real implementations would then be carefully hand-coded in a traditional language. That was the view ten years ago of finite-state machines—that FSMs were part of the theoretical backbone of CL, linking the field to the theory of computation. Starting in the mid-1990’s, how- ever, finite-state methods came to the center of ap- plied NLP as researchers at Xerox, AT&T, Gronin- gen and elsewhere improved the expressive power of FSMs by moving from automata to transduc- ers, adding semiring weights, and developing pow- erful new regular-expression operators and algo- rithms for these cases. They also developed soft- …

Content truncated to 500 words