ITR: Weighted Dynamic Programming for Statistical Natural Language Processing

动态规划是一种核心算法技术，通常用于寻找歧义数据(语言、语音、遗传学、音乐、视觉等)的最佳解释。或对数据的最佳响应(例如翻译、路线、计划或证明)。这个项目正在开发一个加权动态编程的编程语言和编译器。用户编写了一个简单的说明，说明如何从较小的假设构建更大的假设。编译后的代码自动处理许多问题，例如高效的表示、高效的索引、可训练参数的快速估计、假设修剪以及关于下一步尝试扩展哪个假设的决定(基于概率估计或学习的启发式)。编译器还执行自动程序转换，这可以提高动态程序的渐近效率。一般来说，该研究考虑了特定问题的算法技巧，并将其推广到任意动态程序中。该系统正被应用于各种自然语言任务，如句法分析、句法归纳和统计机器翻译。这样的任务得益于快速试验新的语言模型，从而试验新的动态程序的能力。具体的任务也为改进语言和编译器提供了试验台。该系统将被广泛共享。通过让研究人员和学生使用最有效的技术直接执行声明性规范，这项工作将使构建、培训和实验性修改大规模智能系统变得更加容易。

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.