From OpenCCG to AI Planning: Detecting Infeasible Edges in Sentence Generation

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 1524–1534, Osaka, Japan, December 11-17 2016. From OpenCCG to AI Planning: Detecting Infeasible Edges in Sentence Generation Maximilian Schwenger⋄ and ´Alvaro Torralba⋄ and J¨org Hoffmann⋄ David M. Howcroft∗ and Vera Demberg⋄ ⋄ Department of Computer Science, Saarland Informatics Campus ∗ Department of Language Science and Technology Saarland University, Saarbr¨ucken, Germany schwenger@stud.uni-saarland.de, {torralba,hoffmann}@cs.uni-saarland.de {howcroft,vera}@coli.uni-saarland.de Abstract The search space in grammar-based natural language generation tasks can get very large, which is particularly problematic when generating long utterances or paragraphs. Using surface real- ization with OpenCCG as an example, we show that we can effectively detect partial solutions (edges) which cannot ultimately be part of a complete sentence because of their syntactic cate- gory. Formulating the completion of an edge into a sentence as finding a solution path in a large state-transition system, we demonstrate a connection to AI Planning which is concerned with this kind of problem. We design a compilation from OpenCCG into AI Planning allowing the detection of infeasible edges via AI Planning dead-end detection methods (proving the absence of a solution to the compilation). Our experiments show that this can filter out large fractions of infeasible edges in, and thus benefit the performance of, complex realization processes. 1 Introduction Surface generation is an NP-complete problem (Koller and Striegnitz, 2002). This is particularly prob- lematic in practical terms when the sentence or text paragraph to be generated is long. Our aim in this paper is to improve the efficiency of surface realization in OpenCCG (White, 2006; White and Rajkumar, 2012), by detecting, early on during search, infeasible partial solutions (which can never be completed into a full sentence), through a new connection to techniques from AI Planning. OpenCCG is based on combinatory categorial grammar (CCG), where words from a lexicon are an- notated with syntactic categories, and simple rules (e. g., forward/backward application) dictate category combination. The target of the realization process is a text that conveys the desired meaning, formalized as a conjunction of elementary predicates, where each must be covered exactly once. The search space (following a chart realization algorithm, e. g. (Kay, 1996; Cahill and van Genabith, 2006; Carroll and Oepen, 2005)) traverses collections of partial sentences (edges). We say that an edge is infeasible if it is not part of any complete sentence. This happens when the edge cannot be combined with other edges to a sentence in a way covering exactly the remaining semantic items. Our contribution is a new technique to automatically identify, and prune, such infeasible edges. AI Planning (e. g. (Russell and Norvig, 1995; Ghallab et al., 2004)) is one of the oldest sub-areas of Artificial Intelligence (AI). It investigates general problem description languages, and general prob- lem solving algorithms, where a “problem” comes in the form of an “initial state”, a “goal”, and a set of “actions” that can be applied to change states and thus, eventually, reach the goal. In other words, AI Planning is concerned …

Content truncated to 500 words