A Continuation Semantics for A bstract M eaning R epresentation (2020)

Abstract: Abstract Meaning Representation (AMR) is a simple, expressive semantic framework whose emphasis on predicate-argument structure is effective for many tasks. Nevertheless, AMR lacks a systematic treatment of projection phenomena, making its translation into logical form problematic. We present a translation function from AMR to first order logic using continuation semantics, which allows us to capture the semantic context of an expression in the form of an argument. This is a natural extension of AMR’s original design principles, allowing us to easily model basic projection phenomena such as quantification and negation as well as complex phenomena such as bound variables and donkey anaphora.

## introduction abstract meaning representation (amr) is a general-purpose meaning representation that has become popular for its simple structure, ease of annotation and available corpora, and overall expressiveness @xcite . specifically, amr focuses on representing the predicative core of a sentence as an intuitive representation of the semantics of a sentence, advantageous for parsing and matching algorithms. as an example, the amr for the english sentence "everyone in the room listened to a talk." is given in example (1), in three equivalent formats. for the sentence in (1a), the predicate and its arguments are represented as nodes in the amr graph in (1b), while the edges represent the relations between the predicate and each of its arguments. penman notation in (1c) provides a more readable version of the amr @xcite . by design, amr emphasizes argument structure over logical structure, distinguishing it from several other meaning representations based on formal semantic frameworks @xcite . although amrs can be represented as conjunctions of logical triples, as seen in (1d), such representations cannot be used directly for drawing valid inferences such as textual entailment or contradiction. quantifiers, for example, are not given any special semantics, being represented as simple modifiers. furthermore, amr does not represent quantifier scope in any way, leaving open the question in (1) of how many talks were listened to in the room. several proposals have been put forth to provide amrs with more meaningful logical forms, driven both by parsing and theoretical concerns. @xcite present a ccg-based grammar induction technique for amr parsing; a learned joint model integrates classical lambda calculus and underspecification to improve search for compositional and non-compositional elements of amr, respectively. semantically speaking, each amr variable gets its own lambda term (scoped as low as possible) and each amr role becomes a binary predicate that is applied to those variables. more strictly theoretical work also provides systematic mappings from amr into logic. @xcite defines a syntax of amr and provides a recursive translation function into first-order logic (fol) that is able to handle scope phenomena. in a similar vein, @xcite adds tense and number information into amr leaves and makes explicit quantificational determiners as a basis for a mapping to a higher order, dynamic logic. finally, @xcite add scope itself to amr graph structure, representing it relationally in the form of a scope node that attaches to the predicative core when necessary. adding to the discussion about the expressive capacity of amr, @xcite argue that any purely graphical representation of meaning is unable to capture basic natural language semantics such as boolean operators. instead, the authors propose layering graphs based on the resource description framework (rdf) @xcite and named graphs @xcite such that the interaction between different layers can capture booleans (such as negation and disjunction), modals and irrealis contexts, distributivity and quantifier scope, co-reference, and sense selection @xcite . however, in this work, we will show how we can give amr a semantics expressive enough to handle at least some of these phenomena, namely quantification and negation, without needing to introduce additional graph structure. here, we build on previous work and present a translation function from amr to fol using continuations. a continuation of an expression encodes surrounding contextual information relevant to its interpretation. more specifically, the continuation hypothesis assumes that some natural language expressions denote functions that take their own semantic context as an argument @xcite . in the present discussion, continuations have interesting consequences for the representations associated with the predicative core in an amr graph structure. namely, the continuation effectively allows the graph to be rooted at the predicate level, while treating the continuation as an associated argument to the relation associated with that predicate. thus, our methods allow us to work with standard amrs without adding features or modifying the graphs, yet still permit us to draw valid inferences. we take as our starting point the work presented in @xcite , as it is the most similar to ours in translating amr to fol without significantly altering the amr feature inventory. we consider the semantics of basic amrs and show how bos (2016)'s translations can be naturally formulated in terms of continuations (section 2). we then demonstrate how continuations allow us to give a simpler, more transparent semantics that can handle scope phenomena (section 3). we go on to discuss our treatment of universal quantification (section 4) and negation (section 5) before examining how our continuation semantics deals with "donkey sentences" (section 6). finally we discuss implications of our work and conclude (sections 7 and 8). ## a basic continuation semantics continuations capture important contextual information surrounding an expression useful for disambiguating the expression's interpretation. in the same way that the generalized quantifier interpretation of an entity is the set of properties true of that entity, the continuation of an expression is the set of contexts that, when combined with that expression, result in a true sentence. alternatively, in terms of the characteristic function of that set of contexts, the continuation of a word or phrase is the entire future of the computation of that expression, packaged as a function over the expression itself @xcite . with the goal of integrating continuations into our methodology, we begin in the same way bos (2016) does, by considering the semantics of basic amrs. basic amrs are comprised of constants c (used in, e.g., proper names) and instance assignments (x/p ) where a variable x is declared to be an instance of a predicate p . instance assignments may also have out-going roles r i a i , where the instance denoted by the amr a i fills the role r i of its parent. we provide a semantics for these basic amrs below in definition 1: the above definition is nearly identical to that given by @xcite for basic amrs, and also, in turn, very similar to that of @xcite . in fact, our definition can be seen as a notational variant (namely, an eta-conversion) of bos' definition: where our translations have the general functional form @xmath0.f (φ), bos' translations have a, φ = f (φ). bos describes φ as a "λ-expression for roles"; the purpose of φ is to "delay the translation of roles" until we have evaluated the meaning of the instance to which we are assigning the role. but it is also possible to consider φ from another perspective: in a formula such as φ(c), φ contains contextual information, namely, about the role c plays in relation to its parent node. in other words, φ is a continuation. in definition 1, we thus define the meanings of amrs directly, as functions of their continuations. we note that the first two meanings in definition 1 are those of generalized quantifiers @xcite , or continuized noun phrases (nps) @xcite , for "c" and "some p", respectively. a very simple example is given below. an amr for the sentence "a dog barked" is given in example (2). the calculation of the fol formula from the amr is then shown in (3). as an example, the sentence in (4a), "a dog scratched itself", contains a reflexive pronoun. in its amr in (4b), (d \ dog) must project over (s / scratch-01), in order for its quantifier to bind the reentrant :arg1 d (following bos (2016), we use the backslash "\" to mark projection phenomena). one way to look at the above procedure is to note that the projective semantics translates the projective concepts (here, (d \ dog)), while the assertive semantics translates everything else. then, applying the projective meaning to the assertive meaning ensures that the projective concepts take scope over the rest of the sentence. an alternative viewpoint notes that the projective meaning λp.∃d.dog(d) ∧ p is an expression that, when applied to the assertive meaning p, yields the meaning of the sentence. this is extremely similar to how an expression is applied to its continuation to yield a sentence meaning in a continuation semantics. in fact, we can write a single translation function that makes this connection explicit, and dispenses with the need for separate projective and assertive semantics. to do so, we revisit the meaning (x/p : r 1 a 1 . . . : r n a n ) . instead of giving a direct translation as in definition 1, we decompose it into two parts: an out-going role :r 1 a 1 and the rest of the amr (x/p :r i a i ) , where :r i a i is a (possibly empty) list of the rest of the out-going roles. from definition 1, we find that the part of the meaning corresponding to :r 1 a 1 is a 1 (λy.r 1 (x, y)), i.e., the meaning a 1 being applied to the continuation λy.r 1 (x, y). now we can consider the rest of the amr, in particular, its continuation. if we take the continuation to represent the rest of the sentence, then this also has two parts: the out-going role meaning a 1 (λy.r 1 (x, y)), and φ(x), the original continuation. we can conjoin them, and bind the x with a λ, to get λx. a 1 (λy.r 1 (x, y)) ∧ φ(x). then we can apply the meaning of the rest of the amr, namely (x/p : r i a i ) , to this continuation (with a couple of α-conversions to avoid name collisions), to get a recursive semantics for an amr with out-going roles: in a continuation semantics, scope and application order are inextricably linked. as such, to make an argument scope over its predicate, we can reverse the order of the role and the rest of the amr. now (x/p : r i a i ) only gets the λ-expression for r 1 and the original continuation φ(m), while the projective concept (y\q . . .) is fed the rest of the sentence as its continuation: we can apply the two rules above recursively until :r i a i becomes empty, i.e., we run out of arguments. then we can use our previous rule (x/p ) = λφ.∃x.p (x) ∧ φ(x), as the base case of our recursion. we also adopt the rule @xmath1.φ(x) to handle re-entrant nodes, such as d in example (4b). finally, it is important to note that the application order depends solely on whether the argument a 1 is a projective concept (y\q . . .) or not, and not at all on whether the parent node (x/p ) is projective or not. we can use a vertical bar "|" to denote that a rule applies regardless of whether a concept is projective or not. we summarize our work thus far in definition 2: as an example, we calculate the meaning of the sentence in (4a), "a dog scratched itself" below. we already know that the meaning of "a dog" is λφ.∃d.dog(d) ∧ φ(d), so in (5) we focus on the meaning of "scratched itself": ## universal quantification as previously mentioned, quantifiers in amr are treated as simple modifiers of their head concepts. in a logical form like (1d), all variables are assumed to be existentially quantified. nevertheless, it is possible to give amr a proper semantics of quantification. @xcite , for example, is able to translate a number of different kinds of quantifiers into a higher-order logic. in this paper, to stay within the setting of fol, we will focus on the universal quantifier. one way of introducing universal quantification into a semantics for amr, as noted by @xcite , is to include a rule such as (x/p : quant ∀) = λφ.∀x.p (x) → φ(x), where ":quant ∀" denotes any expression that can be interpreted as a universal quantifier. one can verify that, for a simple sentence like "every dog scratched itself", combining the meaning of "every dog", i.e., λψ.∀d.dog(d) → ψ(d), and "scratched itself", from (5), one arrives at ∀d.dog(d) → ∃s.scratch-01(s) ∧ arg1(s, d) ∧ arg0(s, d), the correct meaning of the sentence. however, for more complex nps, including those that are modified by relative clauses, or even simply by a pre-nominal adjective, the above rule will not provide the right semantics. consider the sentence "every brown dog scratched itself" in (7) below: again, we will not give the full derivation here, but the meaning we get if we use the above rule is ∀d.dog(d) → ∃b(brown(b) ∧ mod(d, b)) ∧ ∃s.scratch-01(s) ∧ arg1(s, d) ∧ arg0(s, d), i.e., "every dog is brown and scratched itself". the problem arises from the fact that in the formula λφ.∀x.p (x) → φ(x), only the predicate p is allowed to appear in the restriction; everything else is forced into the continuation φ, which is interpreted in the nuclear scope. our solution to this problem is inspired by @xcite 's treatment of the universal quantifier, and is also similar to the dynamic meaning of "every" given by de @xcite . we will use the below rule for universal quantification: to understand how this rule works, note that the meaning (x|p :r i a i ) will have a logical form like λψ.∃x.p (x) ∧ . . . ∧ ψ(x). applying this meaning to the continuation λm.¬φ(m) eventually results in ∃x.p (x) ∧ . . . ∧ ¬φ(x), which we then negate to get ¬∃x.p (x) ∧ . . . ∧ ¬φ(x). using the logical identity ¬∃x.φ(x) ∧ ¬ψ(x) ≡ ∀x.φ(x) → ψ(x), we finally get the meaning λφ.∀x.(p (x) ∧ . . .) → φ(x), with the ". . . " representing material introduced by an adjective or in a relative clause, correctly interpreted in the restriction of the quantifier. this can be seen in the derivation of the meaning of "every brown dog" below in ( 8 we can then combine this meaning of "every brown dog" with the meaning of "scratched itself" from (5) below in (9) to get the correct meaning of the sentence: definition 3 (semantics of amrs with projection and universal quantification) @xmath2.φ(c) @xmath3.φ(x) (x|p :quant ∀ :r i a i ) = λφ.¬ (x|p :r i a i ) (λm.¬φ(m)) (x|p :r 1 (y\q . . .) :r i a i ) = λφ. (y\q . . .) (λn. (x|p :r i note that, like other continuation-passing rules, the order in which the rules apply is critical to deriving the correct interpretation. if we interpret the universal quantifier after "brown", rather than before, then "brown" will become part of the continuation of "every dog", and we get the previous incorrect meaning. we will discuss ways to specify the application order in section 7, but for now, we will process nodes in linear order, i.e., the order they are written in the amr. ## negation negation is central to sentence-level meaning, as it directly impacts the assignment of truth values to propositions. in amr, negation is represented as a predicate rather than a scope operator: a fixed polarity relation is given between the negated concept and negation constant "-". as a result, amr makes wrong predictions for inferences based on negated sentences; for example, it will allow the inference "a dog barked" from "a dog did not bark." both @xcite and @xcite reformulate amr semantics to allow polarity to act on propositions instead of concepts; here, we expand on the work of @xcite and show the need for two kinds of negation to allow for distinct readings in ambiguous contexts. @xcite proposes a translation of amr to fol in which negation attaches to the quantifier that binds its concept. for example, the amrs in ( 10a ) and (11a) receive the respective interpretations in (10b) and ( 11b note that a logical form such as ∃m.meow-01(m) ∧ ∃d.¬dog(d) ∧ arg0(m, d), with the negation attached directly to the predicate, rather than the quantifier, can also give rise to the interpretation in (11b). in fact, assuming that the meowing event has exactly one arg0, the two forms are equivalent. it may then seem that any formula with predicate negation can be given an equivalent formula with quantifier negation, and that therefore quantifier negation is sufficient for the semantics of amrs. however, there are meanings that cannot be represented with negation only attaching to quantifiers, particularly involving the interaction of negation and universal quantification. for example, a meaning such as "every non-dog meowed", i.e., ∀d.¬dog(d) → ∃m.meow-01(m) ∧ arg0(m, d), cannot be generated from any amr using the rules in @xcite . for this reason, we introduce the following two rules for negation: we adopt the same backslash/forward slash syntax as for projective and non-projective concepts, here simply meaning "wide-scope" (i.e., negation attaching to the quantifier) and "narrow-scope" (i.e, negation attaching to the predicate), respectively. an example amr for the sentence "every non-dog meowed", with narrow-scope negation, is shown in (12), and the derivation of its meaning is given in (13). . . . one can verify that reversing the direction of the slash, i.e., changing the polarity to (n \ -), results in the meaning ¬∀d.dog(d) → ∃m.meow-01(m) ∧ arg0(m, d), i.e., "not every dog meowed". definition 4 shows the final version of our translation function: definition 4 (semantics of amrs with projection, universal quantification, and negation) @xmath4.φ(c) @xmath5.φ(x) (x|p :polarity (n\-) :r i a i ) = λφ.¬ (x|p :r i a i ) (φ) (x|p :polarity (n/-) :r i a i ) = λφ. (x|¬p :r i a i ) (φ) (x|p :quant ∀ :r i a i ) = λφ.¬ (x|p :r i a i ) (λm.¬φ(m)) (x|p :r 1 (y\q . . .) :r i a i ) = λφ. (y\q . . .) (λn. (x|p :r i we now derive the meaning of the subject np "every farmer who owns a donkey" below in (15). using the translation rules we defined earlier, we eventually get the meaning λφ.¬∃d.donkey(d) ∧ . . .. while it may seem odd for the meaning of "every farmer..." to begin with "there does not exist a donkey...", we can use a few logical identities to transform the meaning into a more intuitive form. first, just as in example (8), we can use the identity ¬∃x.φ(x) ∧ ¬ψ(x) ≡ ∀x.φ(x) → ψ(x) to rewrite the meaning in terms of universal quantifiers and material conditionals. then, we can take advantage of the facts that φ → ∀x.ψ ≡ ∀x(φ → ψ) (if x is not free in φ) and φ → (ψ → χ) ≡ (φ ∧ ψ) → χ to move all the universal quantifiers to the beginning (i.e., write the formula in prenex normal form), and move all the terms except φ(f ) into the antecedent of a single conditional. at that point, we can rearrange the quantifiers and the conjuncts to get the more natural-looking meaning at the end of ( 15 ). one can verify that the meaning of "loves it" is λφ.∃l.love-01(l) ∧ arg1(l, d) ∧ φ(l), similar to the meaning of "scratched itself" in (5). then we can combine the two meanings to get the meaning of the entire sentence in ( 16 ## discussion continuations are a natural solution to the challenge of translating amr to fol: by treating the continuation of an expression as an associated argument to the relation associated with that predicate, we maintain amr's focus on the predicative core while still allowing valid inferences from projection phenomena to fall out. our method avoids the pitfalls of underspecification, allowing us to prioritize the most plausible interpretation of a scope ambiguity yet also to capture less common interpretations when necessary @xcite . our method also does not modify standard amr nodes, leaves, or edges, which allows us to utilize existing amr corpora. formalizing basic projection phenomena in amr paves the way for more comprehensive meaning representation, allowing simple translation of complex phenomena such as negative raising that evidence speaker belief and intent. another interesting advantage of the continuation-passing style semantics introduced here for sentence or utterance level expressions, is the natural way it can be extended to model how amrs have recently been used in human-robot interaction dialogues @xcite . the model presented here can easily adopt the dynamic semantics of "discourse moves as continuations", as introduced by de groote (2001), and extended by @xcite . as previously mentioned, in a continuation semantics, the order of application determines the relative scope of a predicate and each of its arguments. in this paper, we take the out-going roles of a predicate to be ordered, and the order of application to be the order the arguments are written in the amr. in contrast, @xcite attach an optional scope node to the predicate, that explicitly marks the arguments of a predicate with a relative scope ordering. ease of annotation is considered one of the major advantages of amr compared to other meaning representations @xcite . it is possible that introducing a new backslash notation for projective concepts and wide-scope negation may increase annotators' cognitive load. we believe, though, that this effect can be mitigated by specifying default interpretations of projection and negation where possible. for example, @xcite notes that arguments of an event should be projective in general, and @xcite comments that negation should take wide scope over event quantifiers by default. in addition to providing guidance to annotators, such defaults can also be used on existing corpora, another area where amr excels. we plan to conduct a corpus study to evaluate the feasibility of using these defaults to generate logical forms from amrs in the future. although our semantics is able to handle many different kinds of scope phenomena, much more work is needed to capture the plethora of meanings possible in natural language. extending the translation we present here to logical connectives, conditionals, modality, non-declarative sentences that depend on notions of common ground, and other types of quantifiers (e.g. "most") are all possible next steps. in recent years, there have been a number of proposals to extend amr to handle definiteness @xcite , tense and aspect @xcite , and discourse relations @xcite . we look forward to seeing how these proposals and others can be integrated with our semantics. ## conclusion in this paper, we presented a continuation semantics for amr, building off previous work in translating amrs to logical forms. we showed that our semantics is powerful enough to handle a wide variety of scope phenomena, including quantification, negation, bound variables, and donkey anaphora. code for this paper, combining a penman parser based on goodman (2020), with a computational implementation of our translation function, is available at https://github.com/klai12/amr2fol .