Efficient statistical parsing and decoding for expressive grammar formalisms based on tree automata

这个项目的目的是为表达语法形式化开发有效的算法。这种语法形式化描述了不是上下文无关的字符串语言；更复杂对象的语言，例如树或图；以及这些对象之间的关系。因此，它们可以处理语言表示，并捕获概率上下文无关文法(PCFG)无法处理的语言概括。这对于许多新兴的NLP任务非常有用，例如将字符串的语义解析为基于图的语义表示。该项目的关键思想是将各种表达文法形式编码为解释规则树文法(IRTG)，并指定用于IRTG的一般算法；然后它们将直接应用于所有更具体的形式化形式。在第一阶段，我们在扩大IRTG可以捕获的形式化范围方面取得了重大进展，包括图语言和集合语言的语法。我们还极大地提高了IRTG解析算法的性能：对编码为IRTG的PCFG的解析现在比以前快1000倍(与专用PCFG解析器大致相当)，我们的图形语法解析器比以前最好的专用图形解析器快1000倍以上。在理论层面上，我们已经阐明了表达文法形式化之间的形式关系；在实践层面上，从事这种文法形式化工作的研究人员可以直接使用我们的通用算法及其开源实现Alto。在第二阶段，我们希望将Alto扩展到实际规模和复杂性的数据集，用于自然语言处理任务，如分析、翻译和生成。即使在第一阶段取得了理论和基础上的进步，当我们将中音应用于日益复杂的领域时，一些挑战变得明显起来。这些挑战对所有基于语法的方法来说都是共同的，包括从语料库中归纳语法，在语料库中，语法信息只能不完全观察到，以及将我们的解析和翻译算法的速度扩展到真实世界的数据。我们将通过开发新的算法或使现有算法适应IRTG，从总体上解决这些挑战。该项目的总体成果将是一个端到端的工具链，在这个工具链中，用户只需要指定一个基于IRTG的表达语法形式，并提供一些数据，然后可以直接使用我们的算法和实现来归纳和训练统计语法，并将其用于高效的语法分析和翻译。

The aim of this project is to develop efficient algorithms for expressive grammar formalisms. Such grammar formalisms describe string languages that are not context-free; languages of more complex objects, such as trees or graphs; and relations between such objects. They can thus handle linguistic representations, and capture linguistic generalizations, that probabilistic context-free grammars (PCFGs) cannot. This is useful for many emerging NLP tasks, such as semantic parsing of strings into graph-based semantic representations.The key idea of the project is to encode a wide variety of expressive grammar formalisms as Interpreted Regular Tree Grammars (IRTGs), and to specify algorithms for IRTGs in general; they will then apply directly to all the more specific formalisms. In the first phase, we have made significant progress in widening the range of formalisms which can be captured by IRTGs, including grammars for graph languages and for languages of sets. We also improved the performance of IRTG parsing algorithms drastically: parsing for PCFGs encoded as IRTGs is now 1000x faster than before (and roughly on par with dedicated PCFGparsers), and our parser for graph grammars is over 1000x faster than the previously best dedicated graph parser. On a theoretical level, we have clarified the formal relationships between expressive grammar formalisms; and on a practical level, researchers working with such grammar formalisms can directly utilize our generic algorithms and their open-source implementation, Alto.In the second phase, we want to scale Alto to datasets of realistic size and complexity on NLP tasks such as parsing, translation, and generation. Even with the theoretical and foundational advances of the first phase, a number of challenges became visible as we applied Alto to increasingly complex domains. These challenges are common to all grammar-based approaches, and include the induction of grammars from corpora in which grammatical information is only incompletely observable, as well as scaling the speed of our parsing and translation algorithms to real-world data. We will tackle these challenges generally, by developing new algorithms or adapting existing ones to IRTGs. We will complement this grammar-based perspective with neural methods for parsing, which we will combine with the specific perspective on language offered by IRTGs.The overall outcome of the project will be an end-to-end toolchain in which a user only needs to specify an expressive grammar formalism in terms of IRTGs and provide some data, and can then directly use our algorithms and implementations to induce and train a statistical grammar and use it for efficient parsing and translation.