Generating Constituent Order in German Clauses

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 320–327, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Generating Constituent Order in German Clauses Katja Filippova and Michael Strube EML Research gGmbH Schloss-Wolfsbrunnenweg 33 69118 Heidelberg, Germany http://www.eml-research.de/nlp Abstract We investigate the factors which determine constituent order in German clauses and pro- pose an algorithm which performs the task in two steps: First, the best candidate for the initial sentence position is chosen. Then, the order for the remaining constituents is determined. The first task is more difficult than the second one because of properties of the German sentence-initial position. Ex- periments show a significant improvement over competing approaches. Our algorithm is also more efficient than these. 1 Introduction Many natural languages allow variation in the word order. This is a challenge for natural language gen- eration and machine translation systems, or for text summarizers. E.g., in text-to-text generation (Barzi- lay & McKeown, 2005; Marsi & Krahmer, 2005; Wan et al., 2005), new sentences are fused from de- pendency structures of input sentences. The last step of sentence fusion is linearization of the resulting parse. Even for English, which is a language with fixed word order, this is not a trivial task. German has a relatively free word order. This concerns the order of constituents1 within sentences while the order of words within constituents is rela- tively rigid. The grammar only partially prescribes how constituents dependent on the verb should be ordered, and for many clauses each of the n! possi- ble permutations of n constituents is grammatical. 1Henceforth, we will use this term to refer to constituents dependent on the clausal top node, i.e. a verb, only. In spite of the permanent interest in German word order in the linguistics community, most studies have limited their scope to the order of verb argu- ments and few researchers have implemented – and even less evaluated – a generation algorithm. In this paper, we present an algorithm, which orders not only verb arguments but all kinds of constituents, and evaluate it on a corpus of biographies. For each parsed sentence in the test set, our maximum- entropy-based algorithm aims at reproducing the or- der found in the original text. We investigate the importance of different linguistic factors and sug- gest an algorithm to constituent ordering which first determines the sentence initial constituent and then orders the remaining ones. We provide evidence that the task requires language-specific knowledge to achieve better results and point to the most diffi- cult part of it. Similar to Langkilde & Knight (1998) we utilize statistical methods. Unlike overgenera- tion approaches (Varges & Mellish, 2001, inter alia) which select the best of all possible outputs ours is more efficient, because we do not need to generate every permutation. 2 Theoretical Premises 2.1 Background It has been suggested that several factors have an in- fluence on German constituent order. Apart from the constraints posed by the grammar, information structure, surface form, and …

Content truncated to 500 words