Semantic Expressive Capacity with Bounded Memory

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 65–79 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 65 Semantic expressive capacity with bounded memory Antoine Venant and Alexander Koller Department of Language Science and Technology Saarland University {venant|koller}@coli.uni-saarland.de Abstract We investigate the capacity of mechanisms for compositional semantic parsing to describe re- lations between sentences and semantic repre- sentations. We prove that in order to represent certain relations, mechanisms which are syn- tactically projective must be able to remem- ber an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not. This is the first result of this kind, and has consequences both for grammar-based and for neural systems. 1 Introduction Semantic parsers which translate a sentence into a semantic representation compositionally must recursively compute a partial semantic represen- tation for each node of a syntax tree. These partial semantic representations usually contain placeholders at which arguments and modifiers are attached in later composition steps. Ap- proaches to semantic parsing differ in whether they assume that the number of placeholders is bounded or not. Lambda calculus (Montague, 1974; Blackburn and Bos, 2005) assumes that the number of placeholders (lambda-bound variables) can grow unboundedly with the length and com- plexity of the sentence. By contrast, many meth- ods which are based on unification (Copestake et al., 2001) or graph merging (Courcelle and En- gelfriet, 2012; Chiang et al., 2013) assume a fixed set of placeholders, i.e. the number of placeholders is bounded. Methods based on bounded placeholders are popular both in the design of hand-written gram- mars (Bender et al., 2002) and in semantic parsing for graphs (Peng et al., 2015; Groschwitz et al., 2018). However, it is not clear that all relations be- tween language and semantic representations can be expressed with a bounded number of place- holders. The situation is particularly challenging when one insists that the compositional analysis is projective in the sense that each composition step must combine adjacent substrings of the in- put sentence. In this case, it may be impossible to combine a semantic predicate with a distant argu- ment immediately, forcing the composition mech- anism to use up a placeholder to remember the ar- gument position. If many predicates have distant arguments, this may exceed the bounded “memory capacity” of the compositional mechanism. In this paper, we show that there are relations between sentences and semantic representations which can be described by compositional mech- anisms which are bounded and non-projective, but not by ones which are bounded and projective. To our knowledge, this is the first result on expressive capacity with respect to semantics – in contrast to the extensive literature on the expressive capacity of mechanisms which describe just the string lan- guages. More precisely, we prove that tree-adjoining grammars can describe string-graph relations us- ing the HR graph algebra (Courcelle and En- gelfriet, 2012) with two sources (bounded, non- projective) which cannot be described using linear monadic context-free tree …

Content truncated to 500 words