Computing All Quantifier Scopes with CCG (2021)

Abstract: We present a method for computing all quantifer scopes that can be extracted from a single CCG derivation. To do that we build on the proposal of Steedman (1999, 2011) where all existential quantifiers are treated as Skolem functions. We extend the approach by introducing a better packed representation of all possible specifications that also includes node addresses where the specifications happen. These addresses are necessary for recovering all, and only, possible readings.

## introduction quantifiers often introduce a peculiar type of semantic ambiguity. take for instance the following sentence: every farmer owns a donkey. this sentence has two readings: a wide reading where there is one donkey that all farmers share and narrow reading where each farmer has a different donkey. if we express these readings as first-order logic they would look as follows: wide: ∃a [donkey (a) ∧ ∀b [farmer (b) ⇒ own (b, a)]] narrow: ∀b @xcite ∧ (farmer (b) ⇒ own (b, a))]] from these formulas it is clear where the name for different readings come from. in the wide reading the existential quantifier takes the wide scope i.e. it contains the universal quantifier. in the narrow reading the existential quantifier's scope does not cover the universal quantifier. any theory of the syntax-semantics interface needs to account for the fact that quantifiers can introduce scope ambiguity. early approaches to this problem involved either representing the two meanings with distinct logical forms like the above, obtained from the surface string either by treating every farmer and a donkey as generalized quantifiers or "quantifying in" in either order to a proposition containing distinguished variables @xcite , or via equivalent structure-changing operations of "quantifier raising" @xcite . later approaches decoupled scope from syntactic derivation by the use of "storage" to pass scope information @xcite . however, all of these approaches overgenerate unattested readings for certain examples involving coordination, first noted by @xcite and considered in section 3 below. the approach of @xcite can be thought of as reuniting a storage-like account with surface-compositional syntactic derivation. here, sk α β represents the skolem function whose arguments are variables of type α and whose result is of type β . in the wide scope reading sk {} donkey is a skolem constant (skolem function with no arguments). this means that it will produce only a unique value of type donkey , somewhat like a proper name. in the narrow scope reading sk {b} donkey is a skolem function that has the variable b bound by the universal as its argument. this function will produce a different value for each b, in other words there will be a different donkey for each farmer . other non-universal generalized quantifiers are also treated as skolem terms. @xcite also discusses negation which we do not present here, but our approach naturally extends to it. we do not deal with intentionality. this view of quantifiers allows for a simple every farmer owns a donkey s/(s\np) (s\np)/np s\(s/np) λ a. ∀b [ f armer (b) ⇒ (a b)] λ a. λ b. own (b, a) λ a. a(sk {} donkey ) >b s/np :λ a. ∀b [ f armer (b) ⇒ own (b, a)] < s :∀b f armer (b) ⇒ own (b, sk {} {b} donkey ) figure 2: packed representation. in order to prevent overgeneration of unattested readings, we must impose a further rather natural constraint on skolem specification requiring that any embedded unspecified skolem terms are specified at the same time in the same environment. thus we get the following readings for "every farmer owns a donkey that ate a hat": to ensure that all available readings are obtained, it is inefficient to choose all possible specification points in the derivation, because most of them yield duplicate results where there has been no change in the set of scoping variables. to eliminate such redundancy, @xcite proposed a packed representation presented in figure 2 where the skolem term is associated with multiple bindings. at points in the derivation where the binding environment of the function changes, a new argument combination is introduced. ## problems with taking scope over coordination the proposal of @xcite was implemented by @xcite and it works quite well for examples that we have seen so far. however, coordination poses some challenges for the packed representation. consider coordination of two universal quantifiers in figure 3a . here np ↑ is a shorthand for a type-raised np. for a moment ignore additional annotations in the arguments of the skolem functions. in this example, the specification of an apple will either happen before it is combined with the universals, or after. this means that either it will be in the scope of both or none. the only two readings are given in figure 3b . however, if we were to unpack the packed formula by computing all combinations of skolem arguments we would get four readings, including the impossible reading of an apple being within scope of one universal quantifier but not the other. we stress that this is a problem arising from the packed representation, not the theory of scope itself. it may look like the solution to this problem is simple: take all skolems stemming from the same noun phrase and combine their arguments in order i.e. first arguments of both skolems go together and second arguments of both skolems go together. while this solves the example in figure 3 , it does not work on that in figure 4 where we coordinate one universal and one existential quantifier. here there is no clear correspondence between arguments of two skolem functions: one of them has two different arguments ({} and {a}) while the other one has only one possible argument ({}). of course, in principle the difference in the number of possible combinations could be significantly larger and it may not be clear how to combine them. to solve this problem we need a more principled solution that directly reflects the mechanism of the non-packed derivations. ## proposed solution the packed representation can be seen as a dynamic programming approach to computing all possible orders of specifications of skolem terms. however, the packed representation of @xcite that we considered so far is incomplete: from a given packed representation we cannot reconstruct the non-packed representations that are encoded in it. that is caused by the missing information of the location in the tree where the specification was done. we extend the packed representation with this information: whenever a new argument combination is added, together with it we add the gorn address of the current node. for instance sk {} trrl {a} t apple from figure 4a signifies that there are two possible arguments for this skolem function: an empty argument list specified at gorn address trrrl (@xmath0. we know that all the gorn addresses for a given skolem function will be on a single path from the root of the tree to the determiner that introduced it into derivation. this means that, for a given function, we can sort all addresses by their height in the tree. assume we have a skolem function with k possible argument sets e 1 , e 2 , . . . , e k sorted by the height of their gorn addresses g 1 , g 2 , . . . , g k such that g k is closest to the root of the tree. we can say that every argument set e i corresponds to the specializations done on any node g for which it holds g @xmath1. 2 in other words g can be any node between g i and g i+1 , including g i but excluding g i+1 . if we take again sk {} trrl {a} t apple as an example we can say that the argument {} corresponds to specialization of skolem function for nodes trrl, trr and tr. additional important point is that we know for certain that g 1 is the address of the leaf of the tree because that is the first point in the derivation where the specification can be done. this is important because in the cases of coordination the logical formula can have copies of the skolem term that comes from the same noun phrase. we can use the gorn address of the leaf to identify the skolem terms that originate in the same noun phrase. steedman (2011) uses a special index to keep track of this information, but that index is not necessary in our representation due to the existance of gorn addresses. now we can define unpacking of the new version of the packed representation. we will illustrate it with the example packed formula from the top node of figure 4a : ∀a man (a) ⇒ eat a, sk let us consider how we extract the reading for entry (tlrrl,t). filtering arguments for the first noun phrase skolem term {sk {} tlrrl woman } with tlrrl is easy because there is only one entry that matches it exactly. filtering arguments for the second noun phrase is more interesting because there are two copies of it. we need to λ a. a sk {} trrl @xmath2. λ b. (a b) ∧ b sk {} tlrrl woman λ a. eat a, sk {} trrl @xmath3. ∀b [man (b) ⇒ (a b)] ∧ a sk {} tlrrl @xmath4, sk {} trrl {a} t apple ∧ eat sk {} tlrrl woman , sk {} trrl apple (a) packed derivation. ∀a man (a) ⇒ eat a, sk {} trrl apple ∧ eat sk {} tlrrl woman , sk {} trrl apple ∀a man (a) ⇒ eat a, sk {a} t apple ∧ eat sk {} tlrrl woman , sk {} trrl apple (b) readings. select for specification on node t. in the first copy sk {} trrl {a} t apple we just select argument {a} since it corresponds to node t. in the second copy sk {} trrl apple we select for {} because it covers all nodes from trrl to the root including t. ## conclusion this approach is really just a full dynamic programming representation of the unpacked representations that could easily be extracted from this representation. we do not have to explicitly encode all the nodes where specification happens, but only for the places where that specification changes the existing result and we also encode exactly at which places in the tree this happens. here we have described how to get all possible readings from a single ccg derivation. however, in some cases there can be alternative ccg derivations that can provide additional readings. to get those readings we can apply the same method on all alternative derivations either by chart parsing, as described in @xcite , or by recovering alternative derivations with the tree-rotation operation @xcite evang and bos (2013) show that there is a strong preference for subject to take scope over object. our representation of skolem terms could be extended to encode the information of the type of noun phrase they originate from. with this extension we could rank the extracted readings by @xmath5. the implementation of our approach is available at https://github.com/stanojevic/ ccg-quantifiers .