A toy distributional model for fuzzy generalised quantifiers (2020)

Abstract: Recent work in compositional distributional semantics showed how bialgebras model generalised quantifiers of natural language. That technique requires working with vector space over power sets of bases, and therefore is computationally costly. It is possible to overcome the computational hurdles by working with fuzzy generalised quantifiers. In this paper, we show that the compositional notion of semantics of natural language, guided by a grammar, extends from a binary to a many valued setting and instantiate in it the fuzzy computations. We import vector representations of words and predicates, learnt from large scale compositional distributional semantics, interpret them as fuzzy sets, and analyse their performance on a toy inference dataset.

## introduction the work of @xcite showed how one can reason about generalised quantifiers using bialgebras over the category of sets and relations over a fixed powerset object (powerset of a universe of discourse). this provides us with an abstract categorical semantics, which when instantiated to category of sets and relations, one will obtain a truth-theoretic semantics. the abstract setting, however, can also be instantiated to category of vector spaces and linear maps, in which one obtains a compositional distributional semantics, in the style of @xcite . the downside is that the resulting vector spaces span over powersets of the usual set of bases and the complexity of reasoning in the setting explodes. it is also not very clear how can one learn the new basis vectors, consisting of sets of vectors, rather than just one vectors. one solution would be to move to a fuzzy setting, as done in @xcite . the rationale behind this move is as follows: fuzzy sets have been encoded in the category of sets and many valued relations and the categorical set-ting of @xcite also instantiates to these categories. we demonstrate the details of this construction in the springer outstanding contributions volume in honor of m. ardeshir. in that paper, we show that the categorical version of fuzzy sets v-rel of sets and many valued relations, is compact closed and define over it the necessary bialgebras to encode zadeh's fuzzy generalised quantifiers. in this paper, we spare the categorical technicalities, and review the definitions of generalised quantifiers in a compositional relational setting (sets and relations) guided by an elementary generative grammar. independently, we also review the definitions of fuzzy generalised quantifiers of zadeh, using the notions of fuzzy sets and possibility distributions. we then explain how fuzzy sets can be modelled by many valued relations and define a compositional semantics for sentences with fuzzy generalised quantifiers in this setting. finally, we interpret vectors as fuzzy sets and show how the many valued semantic computations can be done over vectorial data. we demonstrate the workings of our model on toy vectors extracted from real data and compute a degree of truth for quantified sentences containing them. in order to ground our semantics, i.e. conclude that these computations are sound, we use the results in a toy inference task and analyse the results. finally, although fuzzy concepts are often motivated by vague predicates such as short and tall, fuzzy generalised quantifiers have a large, if not full, overlap with natural language generalised quantifiers. most of the latter are non-logical and consider words such as "almost, many, most, few", and these are exactly the fuzzy generalised quantifiers that zadeh deals with. further, and as we will see in the examples that have been worked out in the paper, one can apply our methodology to deal with logical part of generalised quantifiers, i.e. words such as "all" and "some". ## generalised quantifiers as relations we briefly review the theory of generalised quantifiers in natural language as presented in @xcite . consider the fragment of english generated by the following context free grammar. @xmath0, mary, ... @xmath1, dog, man, ... @xmath2, sleep, ... @xmath3, kiss, ... @xmath4, all, no, most, almost all, several, ... a model for the language generated by this grammar is a pair (u, [[ ]]), where u is a universal reference set and [[ ]] is an inductively defined interpretation function. in order to keep the semantic simple, we will not fully follow formal semantics guidelines and shall not treat noun phrases as general quantifiers. noun phrases and nouns are treated similarly and by sets. the [[ ]] of terminals is thus defined via the following cases: it assigns to each a ⊆ u , a family of subsets of u . the images of these interpretations are referred to as generalised quantifiers. for logical quantifiers, these are: a similar method is used to define nonlogical quantifiers, for example "most a" is defined to be the set of subsets of u that has 'most' elements of a, "few a" is the set of subsets of u that contain 'few' elements of a, and similarly for 'several' and 'many'. generalising the two cases above, provides us with the following definition for semantics [[d]](a) of any generalised quantifier d: {x ⊆ u | x has d elements of a} 2. the interpretation of a terminal @xmath5, n, vp} generated by either of the rules '@xmath6, @xmath7, @xmath8. that is, noun phrases, nouns and verb phrases are interpreted as subsets of the reference set. 3. the interpretation of a terminal y generated by the rule @xmath9. that is, verbs are interpreted as binary relations over the reference set. the semantics of [[ ]] on non-terminals is defined according to the following cases: 1. the interpretation of expressions generated by the rule '@xmath10: [[det n]] = [[d]]([[n]]) where @xmath11, for @xmath12. this condition is often referred to as conservativity or the living on property of generalised quantifiers. 2. the interpretations of expressions generated by other rules are as usual: [[v np]] = [[v]]([[np]]) [[np vp]] = [[vp]]([[np]]) here, for r ⊆ u × u and a ⊆ u , by r(a) we mean the forward image of r on a, that is r(a) = {y | (x, y) ∈ r, for @xmath13. to keep the notation unified, for r a unary relation r ⊆ u , we use the same notation and define r(a) = {y | @xmath14, for @xmath15, i.e. r ∩ a. the 'meaning' of a sentence in this setting is its truth value. so we have that a sentence is true iff [[np vp]] = ∅ and false otherwise. for the cases of quantified sentences considered in this paper, i.e. sentences with quantified subject and object phrases, a truth value is defined as follows: 1. a sentence of the form 'det n vp' is true iff [[det n vp]] = [[vp]] ∩ [[n]] ∈ [[det n]] and false otherwise. 2. a sentence of the form 'np v det n' is true iff [[np v det n]] = [[n]] ∩ [[v]]([[np]]) ∈ [[det n]] and false otherwise. for example, the sentence 'some cats slept' with a quantifier at the subject phrase is true iff [[slept]]∩ [[cats]] ∈ [[some cats]], that is, whenever the set of things that sleep and are cats is a non-empty set. similarly, a sentence with a quantified phrase at its object position, for instance, 'cats like some rats' is true iff [[rats]] ∩ [[likes]]([[cats]]) ∈ [[some rats]], that is, whenever, the set of things that are liked by cats and are rats is a non-empty set. similarly, the sentence 'cats liked three rats' is true iff the set of things that are liked by cats and are rats has three elements in it. ## zadeh's fuzzy generalised quantifiers in this section we review definitions of fuzzy sets and quantifiers, as done by zadeh @xcite . a fuzzy set is a set whose elements have a corresponding weight associated to them. for a set a, the weight µ i of element u i is interpreted as the degree of membership of u i in a. the fuzzy set a with n elements is represented symbolically by a sum: the cardinality of a fuzzy set is defined via the notion of sigma-count, defined below: terms whose degrees of membership fall below a certain threshold, may be omitted from the sum. this is to avoid a situation where a large number of terms with low degrees become equivalent to a small number of terms with high degrees. the quantified sentences zadeh considers are built from two basic forms: "there are q a's" and "q a's are b's". each of these propositions induces a possibility distribution. zadeh provides the following insights for the analysis of these quantified propositions. "there are q a's" implies that the probability of event a is a fuzzy probability equal to q. "q a's are b's" implies that the conditional probability of event b given event a is a fuzzy probability which is equal to q. most statements involving fuzzy probabilities may be replaced by semantically equivalent propositions involving fuzzy quantifiers and this is the statement we work with in this paper. the fuzzy semantics of a proposition p is interpreted as "the degree of truth of p", or the possibility of p, where possibility is treated in an elementary way, i.e. a function from a set to the unit interval. in order to compute this, one translates p into a possibility assignment equation, denoted by π (x 1 ,••• ,xn) = f , where f is a fuzzy subset of the universe of discourse u and π (x 1 ,••• ,xn) is the joint possibility distribution over (explicit or implicit) variables x 1 , • • • , x n of p. for instance, the proposition "vickie is tall" is translated as: here, t all is a fuzzy subset, height(v ickie) is a variable implicit in "vickie is tall", and π height(v ickie) is the possibility distribution of this variable. following zadeh, we use @xmath16, but are aware that this makes the reading awkward. the reader is encouraged to treat (as we did) = as an informal assignment. the above possibility assignment equation implies that suppose that 4 is compatible with the meaning of "several" with degree 0.8, then the above implies that, for instance, the possibility that vickie has 4 credit cards is in order to analyse sentences of the general forms "there are q a's" and 'q a's are b's", zadeh assumes that they are semantically equivalent to the following: here, p oportion(b|a) is the proportion of elements of b that are in a, aka the relative cardinality of b in a, formally defined as follows: both p roportion(b|a) and σcount(a) may be fuzzy or non-fuzzy counts. zadeh then formalises the above counts as possibility assignment equations as follows in the spirit of truth-conditional semantics, the weight of each of the elements of the set can be interpreted as the degree of truth of the proposition denoted by the element. this weight is q(σcount(a)) for sentences of the form "there are q a's" and q(p roportion(b|a)) for sentences of the form "q a's are b's". writing µ a (u) for the degree of membership of u in the fuzzy set a, we define the intersection of two fuzzy sets a and b as example. let's say we have a universe @xmath17, u 2 , u 3 , u 4 , u 5 } and fuzzy sets kp for "kind people" and bp for "big men", defined as follows: the quantified sentence "most big men are kind", is translated to the following possibility assignment equation π p roportion(kp |bm ) = m ost . the intersection of kp and bm is computed as follows: the proportion of big men that are kind, i.e. p roportion(kp |bm ), is computed as follows: suppose that proportions between 0.6 and 0.7 are compatible with the meaning of m ost with degree 0.75. then, since 1.5 3.1 = 0.48, the degree of truth of our sentence is below 0.75. for the crisp quantifier all, the sentence "all big men are kind" is, since only the proportion 1 is compatible with the meaning of all with degree 1, which is not the case here. possibility distributions can be learnt, e.g. zadeh develops a test-score procedure by sampling from a database of related data. we refer to sets and many valued relations on them as v-rel. ## fuzzy generalised quantifiers as many valued relations a non-fuzzy generalised quantifier d is interpreted as a relation d over the power set of the universe of discourse p (u ), where it relates a subset a ⊆ u to subsets b ⊆ u , based on the cardinalities of a and b. the fuzzy version of this quantifier is interpreted as a many valued relation over p (u ), where, in fuzzy set notation, it relates a to subsets u i ⊆ u and assigns to each such subset a degree of membership µ i . the result is a fuzzy set whose weights come from a possibility distribution over the relative cardinalities of a and u i 's. in zadeh's notation: for @xmath18, 1] and given a fuzzy generalised quantifier for which we have π p roportion(b|a) = d , we define its v-rel encoding to be the many valued relation d : p (u ) p (u ), with values coming from the possibility distribution of d , defined as follows: in order to obtain a many valued relation in v-rel, we need a numerical value assigned to subsets a and b of universe. this number is nothing but the weight of [[d]](p roportion(b|a)). the semantics of a sentence of our grammar extends from sets and relations to sets and many valued relations. we define a v-rel model to be the tuple (v-rel, p (u ), ) over a universe of discourse u . in this model, the language constructions are interpreted as follows: here, µ a and µ @xcite ] are degrees of memberships of elements of fuzzy sets a and [[v]], respectively. using the above interpretation, a quantified sentence s gets a a degree of truth @xmath19, 1] as its semantics iff [[s]] = r in (v-rel, p(u ), [[ ]]). using this definition, we compute the semantics of the sentence "several cats sleep" with a fuzzy quantifier at subject position becomes as follows: suppose that the possibility distribution [[several]] will map low values to low values and very high values to low values, but intermediate values would be mapped to a high number as they still represent "several". thus the proportion 9 13 , which is a high number, will evaluate to a high number. thus the many valued relation of this statement will be high (a number close to 1). for examples of possibility distributions of some other fuzzy quantifiers, see @xcite . the semantics of a sentence "mice eat several plants" with a fuzzy quantifier at object place is computed as follows. suppose we have fuzzy sets finally, for the case where we have fuzzy quantifiers at both subject and object places, e.g. in the sentence "several mice eat most plants", a semantics is computed as follows. given that the fuzzy sets representing mice and plants are as before and taking the same fuzzy relation for [[eat]], we compute the meaning of this sentence. suppose further that [[most]] is a possibility distribution that assigns the value 0 to numbers below 0.5, and gradually increasing the value for numbers from 0.5 to 1. in this case, first, we compute the application of the quantifiers to their respective noun phrases: ## from many valued relations to vectors spaces and linear maps by transferring our natural language semantics of quantified sentences from sets and relations to sets and many valued relations, we generalised our boolean-valued true-false semantics to a many valued semantics with degrees of truth from the unit interval [0, 1]. transferring sets and many valued relations to vector spaces and linear maps enables us to compute the meaning of our sentences via quantitative reasoning on the statistical data provided in distributional semantics. a distributional vector for a target word w is seen as a fuzzy set whose degrees of membership are the degrees of co-occurrences of w with a set of context words c, or the degrees of contextual relevance of w to c, or other similar readings. in this section we use this interpretation and implement the formulae for obtaining the degrees of truth of fuzzy generalised quantifiers on vectors obtained from the combined ukwac/wackypedia corpus @xcite , extracted using normalised co-occurrence counts, to ensure that the vectors indeed represent fuzzy sets. as zadeh only provides semantics for a set of two atomic quantifiers without invoking grammatical compositionality, we use the many valued semantics of the previous section to compute the semantics of our quantified sentences compositionally. we start with the sentence entailment dataset of @xcite and later combine it with the entailed generalised quantifiers of @xcite . the former dataset is a small dataset of 12 pairs of sentences, classified in three bands: high entailment, medium entailment, and low entailment. each band is annotated with human judgements with a number in the range 1-7, representing the degree of entailments between each pair of sentences. the bands of entailment are decided upon based on the averages of the annotations. for the purpose of this paper, we only work with clear (non-)entailments and thus only present data for the high and low bands. in the high band, both subjects/objects and verbs/verb phrases/intransitive verbs entail each other. these got an average annotation of 4 and above. in the low band are the non-entailing entries, i.e. neither of the subjects/objects or verbs/verb phrases/intransitive verbs entail each other. these got an average annotation of 2 or under. the entries of the dataset and their annotated degrees of entailment are given in we implement our fuzzy semantics on the sentences of each entry and obtain degrees of truth. these degrees are given in ## conclusion and future work we showed how the compositional semantics of the generalised quantifiers of natural language extends from a binary setting to a many valued setting and how this latter can be used to model fuzzy generalised quantifier. in a quest to relate these developments to large scale data learnt from distributional semantics, we interpreted vectors as fuzzy sets and computed degrees of truth for the sentences of a toy dataset. we then extended the dataset with quantifiers and showed how these computations can be used for an inference task. one essential piece of work is experimenting with the model on main stream inference datasets such as snli and fracas. we mainly chose to work with this small dataset since the details of its high and low bands and the annotations for them where published and we could use them to provide a detailed case by case analysis. a theoretical direction is to use the logic of fuzzy sets, e.g. that of @xcite , to develop a logic for distributional data. quantifiers are known to impose contextual restrictions on their domains, e.g. in the donkey sentences. in previous work @xcite authors have shown how compositional distributional semantics deals with these issues. finding out the added value of working in a fuzzy setting for such examples remains to be worked out. finally, we are aware of the tension that exists between the membership values of fuzzy sets and the probabilities that come from the normalised distributional vector representations. in their simplest forms, the latter probabilities are log likelihood estimates resulting from co-occurrence counts of a corpus of text. fuzzy values, however, are obtained from distribution of the individuals in the domain of vague predicates in a model. relating these two should be possible by machine learning and alongside recent work on bayesian inference semantics @xcite , unified functional distributional models @xcite , and distributional model theoretic approach @xcite @xcite .