tailieunhanh - Báo cáo khoa học: "Generation as Dependency Parsing"

Natural-Language Generation from flat semantics is an NP-complete problem. This makes it necessary to develop algorithms that run with reasonable efficiency in practice despite the high worstcase complexity. We show how to convert TAG generation problems into dependency parsing problems, which is useful because optimizations in recent dependency parsers based on constraint programming tackle exactly the combinatorics that make generation hard. Indeed, initial experiments display promising runtimes. . | Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics ACL Philadelphia July 2002 pp. 17-24. Generation as Dependency Parsing Alexander Koller and Kristina Striegnitz Dept. of Computational Linguistics Saarland University koller kris @ Abstract Natural-Language Generation from flat semantics is an NP-complete problem. This makes it necessary to develop algorithms that run with reasonable efficiency in practice despite the high worstcase complexity. We show how to convert TAG generation problems into dependency parsing problems which is useful because optimizations in recent dependency parsers based on constraint programming tackle exactly the combinatorics that make generation hard. Indeed initial experiments display promising runtimes. 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 improving the runtime in practice have been suggested in the literature - . heuristics Brew 1992 and factorizations into smaller exponential subproblems Kay 1996 Carroll et al. 1999 . While these solutions achieve some measure of success in making realization efficient the contrast in efficiency to parsing is striking both in theory and in practice. The problematic runtimes of generation algorithms 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 essentially 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 . .