Quantification in a Three-Valued Logic for Natural Language Question-Answering Systems

1. INTRO))UCTION

The idea of using Logic as a conceptual frame­ work in question-answering systems is not a new one. The fact that it can formally deal with the notion o~ logical consequence makes it particularly attractive to represent mean­ ing.

Nevertheless, efforts in this direction had been more or less abandoned in Artificial In­ telligence research, mainly because standard predicate calculus (~C) has been shown to be unsuitable for an accurate representation of NL. Its main inadequacies seem to relate to a general inability to incorporate relevant se­ mantic features into the lop,ical representa­ tion of a sentence.

Recent linp,uistic research ([ 1] ,[ 2]) has ar­ rived at interestinu, results concerninu, the extension of standard PC in order to provide a better formal model of language.

It is our thesis that research in this direc­ tion, tou,ether with the fact that pro~ramming in logic ([ 3] ,[ 4]) has become possible since the development of the PROLOG pro~ranuninp; lan­ guar,e [ 5], is likely to yield some very p;ood results concernin~ NL processin~.

On the other hand, the evolution in data base technolou,y has been drifting more and more to­ wards the use of logic, both for data descriotion and for queries [ 6] · Conseouentlv, it is temptin~ to explore the possibilities of using logic throup,hout a NL data base system, in the hope of reducinr. interfaces to a strict mini­ mum.

These considerations have led us to de,Telop a rigorous lop.ical system with a clearly defined semantics, which has heen successfully used as the internal query language into which a com­ puter translates NL input in order to consult different data bases ([ 7] ,[ 8] ,[ Q] ,[ 10]).

In our approach, a data base is actuaU.y an interpretation according to which a well­ formed formula in our logical system is eval­ uated. Its evaluation directly produces the answer, since it yields either a truth value , which corresponds to a yes-no question, or the extensional representation of a set, which cor responds to a wh-question.

This paper focusses on our treatment of quan­ tification within this logical system. The most important theoret ically related work is [ 1] ,[ 2] and [ 11] · Related computer systems are mentioned throu~hout the paper,

Section 2 discusses the need of t yping varia­ bles in connection with meanin~fulness and am­ biguity solving. Section 1 motivates our ap­ proach to quantification and the need of three logical values in connection with existential and number presuppositions, and then describes the process of translatinR NL quantifiers into logical ones. Section 4 discusses the results obtained in concrete applications.

For space limitations, we are forced to omit a formal and complete definition of our logi­ cal system. Those of its features that are rel­ evant to our subject, however, are intuitively described in Section 3.

Spanish is used throughout the paper as the concr e te point of reference with which to ex­ emplify our theoretical considerations.

2. MEANINGFULNESS, AMBIGUITY AND SEMANTIC TYPES

A NL processing system must have a means for checking semantic as well as syntactic accord, in order to reject anomalous sentences such as "Hhich dogs speak Latin?".

A widely spread solution to this problem con­ sists in first generating a "deep structure" of the sentence, taking only syntax into ac­ count, and then performing all the necessary semantic operations and checkups on it .

As has already been observed [ 12] , this often implies a tradeoff between syntactic and se­ mantic complexity, when it is overall simpli­ ci t y and efficiency that are important.

Moreover, linguists themselves are not unani­ mous as to whether the semantic component should be separate or intermingled with the syntactic one [ 13].

Where logic is concerned, there is a simple and elegant way of dealing with meaningfulness: by using types. Types, by the way, are also a useful means for associating the universe of PC to the relations in a particular data base. If we associate a type to each data base do­ main, and model the relations in a data base through predicates whose arguments are restric­ ted to values in specific domains, the analyser can check that the arguments in each predicate generated 'by an input sentence are of the ex­ pected type.

[ncidentally, types are also useful to improve efficiency: a) by narrowing the search space, since only those values in a variable's asso­ ciated domain need to be considered, and b) by avoiding sterile data base consultations, since absurd queries can be rejected by the analyser on the grounds of doma i n incompatibility.

Types have been proposed by other authors (e.g. [ 14) ,[ 15] ,[ 16] ,[ 17]) in connect ion with effi­ ciency and meaningfulness, but they have still another interest: they allow to automatically solve certain NL ambiguities. Take for instance the query:

iCual es el salario del empleado que vive en Lo­ mas?--Which is the salary of the employee who lives i n Lomas?

A priori, a machine has no way to decide whe­ ther the antecedent of the relative clause is "the salary of the employee" or "the employee". But in a type-checking system in which the first argument of the relation "live" is associated to the HUMAN domain, and in which employees-­ and not salaries-- are known to belong to this sa~e domain, the first alternative is not even possible.

Ambiguities concerning different aceptions of a word can generally also be solved through do­ main checking. This is particularly true in our implementation, in which variables are associa­ ted to a type contextually, durinp, the analysis of an input sentence (cf. Section 3.1).

3. PRESUPPOSITIONS, QUANTIFIERS AND~ THREE­ VALUED LOGIC

Typed calculus in itself is not enough to make all sentences meaningful. He actually need more than two logical values, since in NL there are two ways in which a statement may fail to be true: either because its negation holds, or be­ cause something presupposed by the statement fails to be satisfied. In the latter case, the statement is felt to be pointless rather than false.

There is another reason why it must not be con­ sidered false. Take for instance the statement:

El sombrerero loco odia a Alicia. The mad hatter hates Alice .

In a context in which no hatter is mad, it is obviously not true. However, we can not either consider it false, since then the statement

El sombrerero loco no odia a Alicia. The mad hatter does not hate Alice.

would have to be considered true.

The inexistence of a referent for the definite noun phrase makes the whole sentence meaning­ less. The existence of more than one referent would also make it meaningless, since we could not tell which of the referents the sentence is talking about. This is because the Spanish singular definite article induces a presupposi­ tion of existence and unicity upon the noun phrase's referent.

Our treatment of quantification has been de­ vised to account for those presuppositions in­ duced by NL quantifiers. We prefer to call them "determiners", since they include all ar­ ticles, cardinal numbers and words such as "some", "many", etc.

If a sentence contains a determiner, a quanti­ fication of the form "those(x,p)"is introduced, where x is a typed variable and p is a logical formula in our system. Its evaluation yields the set of all x's in x's associated domain which satisfy p.

According to the determiner's meaning, number and existence presuppositions on such a set are represented within the output formula. For instance, "Three blind mice run" is represen­ ted as

card(those(x,and(and(mice(x),blind(x)),run(x))) ,3)

(the cardinality of the set of those blind mice who run is 3)

Definite articles introduce the formula "if(f1 , fJ)", whose value is "undefined" whenever f 1 fails to be satisfied, and has the same value as f2 if ft is true. Here is an example, using the easier-to-picture tree representation:

The formula represented in Fig. 1 will evaluate to "undefined" if the set of mad hatters does not contain exactly one element.

3.1 Spanish determiners and their translations

We can now examine the general process by which a determiner introduces a "those" formula. Let us consider a sentence consistinp, of a ·noun phrase followed by a verb phrase, in which the noun phrase contains a noun introduced by a de­ terminer. 1-le can first represent it through a three-branched quantification of the form:

where q is a quantifier into which the deter ­ miner translates, x is a typed variable, f 1 is the noun phrase's translation, and f2 is the verb phrase's translation. Intuitively, f 1 spe­ cifies the domain of quantification, and q states what portion of the domain f2 holds for.

Our previous example, for instance, can first be represented:

In our implementation, a variable's associated domain depends both on f 1 and f2 in the follow­ ing manner: each predicate known to the data base system has a domain associated to each of its arguments. For instance, "mad" and "hatter" could require its arp,uments to belong to the HUMAN domain, while "hate" could require its first arp,ument to belong to the ANIMAL domain.

lfhen a three-branched quantificat i on is genera­ ted, the variable it cr eates is typed by the intersection of all those domains it has been associated with by the predicates appearing in either ft or f2. In our example, x's type would be HUMAN (the intersection between the HUMAN and the ANIMAL domains).

Instead of generating a different quantifier for each determiner, it is useful to represent all quantifications through a single one of the form para(x,p,c) for whose intuitive meaning is: "c holds for the set of all x's in x's domain which satisfy p".

Each quantification is thus assigned an equi­ valent "for" expression, in which the determi­ ner's meaning is represented. Here are the representations of the Spanish determiners "un" (a), "unos" (some), "el" (singular the), "los" (plural the), "ningiin" (no) and "i" (any cardinal number). The rest are considered in Section 3.1.2.

un(x,f1 ,f2 )=unos(x,ft ,f2 )=for(x,and(ft ,f2),

greater-than(card(x),O))

el(x,f1 ,f2 )=for(x,ft ,if(equal(card(x), 1) ,f2 ))

los(x,f1 ,f2 )·for(x,f1 ,if(greater-than(card(x),

1),f,))

ningiin(x,f1 ,f2 )·for(x,and(ft ,f2 ) ,equal(card(x),

0))

i(x,f1 ,f2 )a for(x,and(f1 ,f2 ) ,equal(card(x) ,i))

Note that we have chosen to identify "un" (a) and "unos" (some). This is because "un" is fre­ quently used to denote "at least one". In order to avoid ambiguity, "1" should be used to mean "exactly one". This convention is particularly useful when negation is involved. For instance, "No tengo un centavo" (I have not a cent) would have a wrong representation with the "exactly one" interpretation: it would state that the cardinality of the set of cents I possess is not 1, which means it can either be 0,2,3,etc.

Finally, any formula of the form "para(x,p,c)" can be replaced by just the formula c, in which all occurrences of x have been replaced by the formula:

aquellos(x,p) those

representing the subset of x's domain whose elements satisfy p.

The reader can now verify that the representa­ tions shown in Figs. 1 and 2 are equivalent.

3.1.1 ~uantifier hierarchy

Quantifier hierarchy obeys three perhaps too simplistic rules, but which have proved to be useful within our NL subset *·

• -Rule 1: A determiner in a verb's subject in­ troduces a quantification which dominates all quantifications introduced by the verb's com­ plement(s). For instance, "Toda rosa tiene (algunas) espinas" -- Every rose has (some) thorns-- is represented:

toda(x,rosa(x),algunas(y,espinas(y),tiene(x, every rose some thorns has

y)))

Note that the representation

some(y,thorn(y),every(x,rose(x),has(x,y)))

would be incorrect, since it rather means: "There exists a certain set of thorns which every rose has".

• Rule 2: 'oihenever a noun has a complement, the quantification introduced by the complement's determiner dominates the one introduced by the noun's deteminer. For instance, "Sabato auto­ p,raHa el libro de cada visitante"-- Sabato autographs the book of each visitor-- is repre­ sented:

cada(x2 ,visitante(x2 ) ,el(x1 ,libro-de(x2 ,x1), each visitor the book-of

autograf1a(Sabato,xt ))) autographs

• Rule 3: lolhen a referential word (that is, a verb, a noun or an adjective) has more than one complement, quantification takes place from right to left: the rightmost complement gener­ ates a quantification which dominates the quan-

* As a formal characterization of our NL subset is beyond the scope of this paper, we shall informally state that it has a fixed vo­ cabulary--determiners, prepositions, the con­ junction "y" (and), relative and interrogative pronouns and the word "no"; and a variable vo­ cabulary--nouns, proper names, adjectives and verbs in the third person of a simple tense · Sentences are either declarative or interroga­ tive, in the active voice, and restricted rela­ tive clauses are allowed and can be nested with no other limit than the computer's capacity.

tification(s) introduced by the leftmost corn­ plement(s), For instance, "Raul regala un es­ pejo a cada niii.o"-- Raul gives a mirror to each child-- is represented:

cada(x2 ,niii.o(x2) ,un(xt ,espejo(xt) ,regala(Raul, each child a mirror gives Xt ,x2 )))

3.1.2 Determiners with a negative implication

As a general rule, the negation introduced by "no" in a sentence is translated by placing the operator "no" (not) right after the quantifi­ cation introduced by the subject, For instance, "Los chicos no conocen al padre de Mart1n" (The children do not know Martin's father) is repre­ sented:

los(x1 ,chicos(x1 ) ,no(el(x2 ,padre-de(Martin,x2), the children not the father-of conoce(x1 ,x2 )))) know

But negation is not always explicit, The Spa­ nish determiner "ningiin" (no) can be regarded as an implicit negation, since it expresses that no portion of the domain of quantification

satisfies the statement involved,

In a non-inverted subject position (e.g,, "Nin­ giln elefante vuela"-- No elephant flies--), it generates a special quantifier called "ningun", whose representation takes this fact into ac­

count (see Section 3.1),

There are two other cases, however, in which "ningiin" coexists with an explicit negation, These cases require a different quantifier, since otherwise the negation would be repre­

sented twice. These cases are:

1. In a subject position, plus subject-verb in­ version: the "ningiin" determiner is assimilated to the "every" quantifier, For instance, "No vino ningiin hombre"-- No man came-- is repre­ sented:

todo(x,hombre(x),no(vino(x))) every man not came

1. In a position other than the subject: the "ningiin" determiner is assimilated to the in­ definite article's quantifier, For instance, "Carlos no tiene ningun hijo"-- Carlos has not any child-- is represented:

no(un(x,hijo(x),tiene(Carlos,x)))

not a child has Another special case is the ne~ation preceding the "todo" (every) determiner (e.g. "No todo pajaro canta"-- Not every bird sings--), The analyser considers "no todo" as a single deter­ miner generating its own associated quantifier:

no-todo(x, ft ,f2 )·for(x,and(ft ,not(f,)) ,greater­ than(card(x),O))

4 SOME PRACTICAL CONCLUSIONS

The ideas previously discussed have been con­ fronted with several successful PROLOG mini­ computer implementations of NL consultable data base systems, in which NL analysis is per­ formed through a metamorphose grammar [ 18] , a powerful PROLOG tool for defining context-sen­ sitive rewriting rules,

The first one concerned just one particular application: the representation of the hard­ ware and software catalogues for the SOLAR 16 series of computers, in order to generate, from a user's question in French, the characteris­ tics of a configuration suiting his particular needs ([ 7] ,[ 8] ) ·

Our first conclusions were reinforced and im­ proved by further research concerning a more general data base system implemented both for Spanish and French consultation ([ 9] ,[ 10]),The Spanish version of this system has been adapted to Portuguese by H. Coelho and L. Pereira (per­ sonal communication, 1Q78). Their work confirms our expectations regarding the generality of our ideas-- and of our implementation--, since remarkably few modifications of the program proved necessary, and they were strictly rela­ ted to lexical differences, whereas rules con­ cerning structure remained unchanged.

Similar ideas to the ones discussed above con­ cerning quantification have inspired other NL data base systems, namely LSNLIS [ 19] and PHLIQA1 ([ 17] ,[ 20]) ,But in spite of the points in common, our ~eneral approach is markedly different. 'Ye have tried to incorporate all relevant semantic as well as syntactic NL fea­ tures into a single formalism, in order to do without intermediate sublanguages and have a single process perform the analysis of an in­ put sentence, LSNLIS, on the contrary, first generates deep structures and then maps them into a semantic representation, PHLIQAl has several successive levels of semantic analysis, each requiring a special formal language, Some of them are meant to deal with ambiguity, which in our approach, as we have seen, is dealt with through the contextual typing of variables dur­ ing the quantification process, Another important point in our approach. which for reasons of space we must be content with just stating, is a high degree of formaliza­ tion through logic: because of the use of PRO­ LOG, important theoretical aspects such as a rigorous characterization of our NL subset and of the syntax and semantics of our internal query language need not be dissociated, as is generally the case, from those practical as­ pects concerning the implementation, From the performance point of view, no frustra­ ting delays in answering have been encountered so far in the systems we have implemented, and the conciseness obtained is rather great: the complete listing of our Spanish analyser, in­ cluding the vocabulary associated to a small sample data base, holds in just four pages, Among our limitations, let us mention the fact that we have not attempted to use NL for data base creation or modification, and that inter­ rogation is limited to the context of one iso­ lated sentence which can not refer to other previous questions or answers,

ACKNOI-lLF.DGEMENTS

The research partially reported here was con­ ducted at the Aix-Marseille II University, un­ der the supervision of A. Colmerauer.