Generation as Dependency Parsing

Generation as Dependency Parsing Alexander Koller and Kristina Striegnitz Dept. of Computational Linguistics, Saarland University {koller|kris}@coli.uni-sb.de Abstract Natural-Language Generation from flat semantics is an NP-complete problem. This makes it necessary to develop al- gorithms that run with reasonable effi- ciency in practice despite the high worst- case complexity. We show how to con- vert TAG generation problems into de- pendency parsing problems, which is use- ful because optimizations in recent de- pendency parsers based on constraint pro- gramming tackle exactly the combina- torics that make generation hard. Indeed, initial experiments display promising run- times. 1 Introduction Existing algorithms for realization from a flat input semantics all have runtimes which are exponential in the worst case. Several different approaches to im- proving the runtime in practice have been suggested in the literature – e.g. heuristics (Brew, 1992) and factorizations into smaller exponential subproblems (Kay, 1996; Carroll et al., 1999). While these solu- tions achieve some measure of success in making re- alization efficient, the contrast in efficiency to pars- ing is striking both in theory and in practice. The problematic runtimes of generation algo- rithms are explained by the fact that realization is an NP-complete problem even using just context-free grammars, as Brew (1992) showed in the context of shake-and-bake generation. The first contribution of our paper is a proof of a stronger NP-completeness result: If we allow semantic indices in the grammar, realization is NP-complete even if we fix a single grammar. Our alternative proof shows clearly that the combinatorics in generation come from essen- tially the same sources as in parsing for free word order languages. It has been noted in the literature that this problem, too, becomes NP-complete very easily (Barton et al., 1987). The main point of this paper is to show how to encode generation with a variant of tree-adjoining grammars (TAG) as a parsing problem with depen- dency grammars (DG). The particular variant of DG we use, Topological Dependency Grammar (TDG) (Duchier, 2002; Duchier and Debusmann, 2001), was developed specifically with efficient parsing for free word order languages in mind. The mere exis- tence of this encoding proves TDG’s parsing prob- lem NP-complete as well, a result which has been conjectured but never formally shown so far. But it turns out that the complexities that arise in gener- ation problems in practice seem to be precisely of the sort that the TDG parser can handle well. Initial experiments with generating from the XTAG gram- mar (XTAG Research Group, 2001) suggest that our generation system is competitive with state-of-the- art chart generators, and indeed seems to run in poly- nomial time in practice. Next to the attractive runtime behaviour, our ap- proach to realization is interesting because it may provide us with a different angle from which to look for tractable fragments of the general realiza- tion problem. As we will show, the computation that takes place in our system is very different from that in a chart generator, and may be more efficient in some …

Content truncated to 500 words