Generating Non-Projective Word Order in Statistical Linearization

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 928–939, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Generating Non-Projective Word Order in Statistical Linearization Bernd Bohnet Anders Bj¨orkelund Jonas Kuhn Wolfgang Seeker Sina Zarrieß Institut f¨ur Maschinelle Sprachverarbeitung University of Stuttgart {bohnetbd,anders,jonas,seeker,zarriesa}@ims.uni-stuttgart.de Abstract We propose a technique to generate non- projective word orders in an efficient statisti- cal linearization system. Our approach pre- dicts liftings of edges in an unordered syntac- tic tree by means of a classifier, and uses a projective algorithm for tree linearization. We obtain statistically significant improvements on six typologically different languages: En- glish, German, Dutch, Danish, Hungarian, and Czech. 1 Introduction There is a growing interest in language-independent data-driven approaches to natural language genera- tion (NLG). An important subtask of NLG is sur- face realization, which was recently addressed in the 2011 Shared Task on Surface Realisation (Belz et al., 2011). Here, the input is a linguistic representa- tion, such as a syntactic dependency tree lacking all precedence information, and the task is to determine a natural, coherent linearization of the words. The standard data-driven approach is to traverse the dependency tree deciding locally at each node on the relative order of the head and its children. The shared task results have proven this approach to be both effective and efficient when applied to English. It is what federal support should try to achieve SBJ ROOT OBJ NMOD SBJ PRD VC OPRD IM Figure 1: A non-projective example from the CoNLL 2009 Shared Task data set for parsing (Hajiˇc et al., 2009). However, the approach can only generate pro- jective word orders (which can be drawn with- out any crossing edges). Figure 1 shows a non- projective word order: the edge connecting the ex- tracted wh-pronoun with its head crosses another edge. Once what has been ordered relative to achieve, there are no ways of inserting intervening material. In this case, only ungrammatical lineariza- tions can be produced from the unordered input tree: (1) a. *It is federal support should try to what achieve b. *It is federal support should try to achieve what c. *It is try to achieve what federal support should Although rather infrequent in English, non- projective word orders are quite common in lan- guages with a less restrictive word order. In these languages, it is often possible to find a grammati- cally correct projective linearization for a given in- put tree, but discourse coherence, information struc- ture, and stylistic factors will often make speak- ers prefer some non-projective word order.1 Figure 2 shows an object fronting example from German where the edge between the subject and the finite verb crosses the edge between the object and the full verb. Various other constructions, such as extraposi- tion of (relative) clauses or scrambling, can lead to non-projectivity. In languages where word order is driven to an even larger degree by information struc- ture, such as Czech and Hungarian, …

Content truncated to 500 words