Hybrid grammars for discontinuous phrase structure trees

自然语言句子的句法结构通常由上下文无关语法给出。该语法可用于解析给定的句子并构建其解析树。每个解析树在以下意义上是连续的：如果i小于j，则第i个子树的边界，即从左到右的叶子标签的连接被放置在第j个子树的边界的左侧。对于具有相对自由词序的语言（例如德语和荷兰语）也会出现不连续的解析树。例如，在“Sie hat oft geschrieben”这句话中，动词短语的“hat”和“geschrieben”这两个词在句子中不是连续出现的，而是不连贯的，或者说：不连续的。此外，荷兰语中的交叉序列依赖现象导致了不连续的解析树。例如，在“omdat ik Peter Cecilia de nijlpaarden zag helpen even”这句话中，“ik”和“zag”两个词属于一起，例如，必须同时屈折，但它们在句子中被不连续地放置；这同样适用于“Peter-helpen”和“Cecilia-voeren”这对单词组合。在这个简短的研究项目中，我想介绍一种新的语法形式，称为混合语法，它产生不连续的解析树。混合语法的每个规则都有一个概率，以便计算给定句子在所有可能的解析树中的排名。特别是，我想找出混合语法在多大程度上是一种适合自然语言处理的工具。为此，出现了以下问题：如何从语料库中提取混合语法的规则？如何将概率训练成规则？解析器的效率如何？理论问题应该伴随着实际的实施。

The syntactic structure of sentences of a natural language is usually given by a context-free grammar. This grammar can be used to parse a given sentence and to build its parse tree. Each parse tree is continuous in the sense that for each node the following holds: the frontier, i.e., the concatenation of the leaf labels from left to right, of the i-th subtree is placed to the left of the frontier of the j-th subtree provided i is smaller than j. For languages with relative free word ordering (e.g. German and Dutch) also discontinuous parse trees occur. For instance, in the sentence "Sie hat oft geschrieben" the two words "hat" and "geschrieben" of the verb phrase do not occur consecutively in the sentence but disconnected, or: discontinuous. Also the phenomenon of cross-serial dependencies in Dutch leads to discontinuous parse trees. For instance, in the sentence "omdat ik Peter Cecilia de nijlpaarden zag helpen voeren" the two words "ik" and "zag" belong together and, e.,g, have to be inflected simultaneously, but they are placed discontinuously in the sentence; the same applies to the word pairs "Peter-helpen" and "Cecilia-voeren". In this short research project I would like to introduce a new grammar formalism, called hybrid grammars which generates discontinuous parse trees. Each rule of a hybrid grammar has a probability in order to calculate a ranking among all the possible parse trees of one given sentence. In particular, I want to find out to which extent hybrid grammars are an appropriate tool for natural language processing. For this the following questions arise: How can one extract rules for a hybrid grammar from a corpus? How can one train probabilities to the rules? How efficient is a parser? The theoretical questions should be accompanied by practical implementations.