tailieunhanh - Báo cáo khoa học: " A Declarative Language for Implementing Dynamic Programs∗"

We present the first version of a new declarative programming language. Dyna has many uses but was designed especially for rapid development of new statistical NLP systems. A Dyna program is a small set of equations, resembling Prolog inference rules, that specify the abstract structure of a dynamic programming algorithm. It compiles into efficient, portable, C++ classes that can be easily invoked from a larger application. | Dyna A Declarative Language for Implementing Dynamic Programs Jason Eisner and Eric Goldlust and Noah A. Smith Department of Computer Science Johns Hopkins University Baltimore MD 21218 . jason eerat nasmith @ Abstract We present the first version of a new declarative programming language. Dyna has many uses but was designed especially for rapid development of new statistical NLP systems. A Dyna program is a small set of equations resembling Prolog inference rules that specify the abstract structure of a dynamic programming algorithm. It compiles into efficient portable C classes that can be easily invoked from a larger application. By default these classes run a generalization of agendabased parsing prioritizing the partial parses by some figure of merit. The classes can also perform an exact backward outside pass in the service of parameter training. The compiler already knows several implementation tricks algorithmic transforms and numerical optimization techniques. It will acquire more over time we intend for it to generalize and encapsulate best practices and serve as a testbed for new practices. Dyna is now being used for parsing machine translation morphological analysis grammar induction and finite-state modeling. 1 Introduction Computational linguistics has become a more experimental science. One often uses real-world data to test one s formal models grammatical statistical or both . Unfortunately as in other experimental sciences testing each new hypothesis requires much tedious lab work writing and tuning code until parameter estimation training and inference over unknown variables decoding are bug-free and tolerably fast. This is intensive work given complex models or a large search space as in modern statistical parsing and machine translation . It is a major effort to break into the field with a new system and modifying existing systems even in a conceptually simple way can require significant reengineering. Such lab work mainly .