ITR-(NHS)-(dmc)-TREEWORLD: Probabilistic Tree Transducers for Machine Translation and Natural Language Processing

自然语言处理(如语音识别和信息提取)的许多最新进展都是由于有限状态自动机的广泛使用。这些自动机概率地将输入字符串转换为输出字符串，它们可以通过合成和向前应用等通用数学运算快速组装起来，以处理新的工作。然而，这些自动机不适合于许多重要的问题，这些问题需要语法敏感的转换和大规模的重新排序(如语言翻译和摘要)。我们正在研究树自动机作为新的自然语言系统的替代构建块。这些自动机遍历输入树并产生输出树。幸运的是，与这些设备相关的有广泛的数学理论。这些自动机也适用于最近在自然语言研究中提出的许多特别模型。然而，仍然有几个关键的缺失：(1)如何设计有效的计算机科学算法来进行泛型树运算；(2)如何设计有效的机器学习算法来从语言数据中产生树自动机和概率；(3)如何使用自动机来准确地建模自动语言翻译中的问题。我们希望这项研究能产生一些好处。许多目前使用有限状态工具的研究人员将转向功能更强大的基于树的自动机，从而获得更准确的语言处理系统。此外，树自动机将使人们能够更好地理解如何更深入、更准确地建模语言翻译，并且--重要的是--以这样一种方式--即机器仍然可以完全自动地从文本语料库获取句法和词汇翻译知识。

Many recent advances in natural language processing (e.g., speech recognition and information extraction) are due to widespread use of finite-state automata. These automata probabilistically transform input strings into output strings, and they can be quickly assembled to tackle new jobs via generic mathematical operations like composition and forward application. However, these automata are a bad fit for many important problems that require syntax-sensitive transformations and large-scale re-ordering (such as language translation and summarization).We are investigating tree automata as an alternative building block for new natural language systems. These automata walk over input trees and produce output trees. Fortunately, there is an extensive mathematical theory associated with these devices. These automata also fit many of the ad hoc models recently proposed in natural language research. However, there are several critical missing pieces: (1) how to design efficient computer science algorithms for generic tree operations, (2) how to design efficient machine learning algorithms for inducing tree automata and probabilities from linguistic data, and (3) how to use automata to accurately model problems in automatic language translation.We expect this research to yield several benefits. Many researchers who currently use finite-state tools will switch to more powerful tree-based automata and obtain more accurate language processing systems. Also, tree automata will enable better understanding of how to model language translation more deeply and accurately, and -- importantly -- in such a way that syntactic and lexical translation knowledge can still be acquired fully automatically by the machine from text corpora.