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.