ITR: Weighted Dynamic Programming for Statistical Natural Language Processing

Johns Hopkins University, Baltimore MD

Investigators

Abstract

Dynamic programming is a core algorithmic technique that is commonly used to find the optimal interpretation of ambiguous data (language, speech, genetics, music, vision, etc.) or an optimal response to data (such as a translation, route, plan, or proof). This project is developing a programming language and compiler for weighted dynamic programming. The user writes a simple specification of how to build bigger hypotheses from smaller ones. The compiled code automatically handles many issues such as efficient representation, efficient indexing, fast estimation of trainable parameters, hypothesis pruning, and decisions about which hypothesis to try extending next (based on probability estimates or learned heuristics). The compiler also carries out automatic program transformations that can improve the asymptotic efficiency of a dynamic program. In general, the research considers algorithmic tricks known for particular problems, and generalizes them so that they can be applied to arbitrary dynamic programs. The system is being applied to various natural-language tasks such as parsing, syntax induction, and statistical machine translation. Such tasks benefit from the ability to experiment quickly with new models of language and hence with new dynamic programs. Concrete tasks also provide a testbed for improving the language and compiler. The system will be widely shared. By letting researchers and students execute declarative specifications directly, using the most efficient techniques available, this work will make it much easier to build, train, and experimentally modify large-scale intelligent systems.