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

基于树自动机的表达语法形式的高效统计解析和解码

• 批准号: 252303250
• 负责人: Professor Dr. Alexander Koller
• 金额: --
• 依托单位: Faculty of Science
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/252303250?language=en
• 关键词: Efficient; statistical; parsing; decoding; expressive

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.

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