Automatic Construction of a Knowledge Base by Analysing Texts in Natural Language

ABSTRACT

We present a system which translates sentences from a subset of German into a database. This data­ base will function as the basis for a question-ans-. wering-system.

The system is applied to a complete text and not to isolated sentences. As an intermediate stage between the German text and the database we use the Discourse Representation Structures (DRS) invented by Hans Kamp . Kamp's system has been chosen because it handles intrasentential and intersentential re­ lations uniformly. Within Kamp's system one can account for certain types of anaphoric relations for which no other linguistic theory has provided a solution .

The input to our system is analysed by a par­ ser which is based on lexical functional grammar. This is the first attempt to combine research on discourse representation with lexical functional grammar with the help of the formalism of Definite Clause Grammar.

For the construction of the database out of the DRS 's , two solutions are proposed. First , a translation of the DRS's into a set of PROLOG clau­ ses enriched with some additional deductive princi-. ples. Second , the formulation of inference rules which operate directly on the DRS .

So far we have i mplemented the following com­ ponents: parser of German, translation rules which map syntactic trees into DRS 's and rules which translate DRS's into PROLOG-clauses .

I. The Fragment of German and the Parser

Our parser is based on the formalism of lexi­ cal functional grammar (LFG) . The implementation of the LFG-parser itself is described in (Reyle / Frey, 1983 ).

We have chosen LFG for four reasons:

1. LFG is based on research in theoretical and in computational linguistics .
2. LFG has already been applied to a variety of languages.

This report describes work done in the Depart­ ment of Linguistics at the University of Stuttgart. It was supported in part by the German Science Foun­ dation project Ro 245/12 .

Werner FREY , Uwe REYLE and Christian ROHRER

Dep. of Linguistics, University of Stuttgart

1. LFG does not require transformational rules.
2. The output of the parse (called 'f-structure') constitutes in form and content an excellent in­ put to our semantic component.

Our fragment of German comprises the following constructions : relative clauses, conditional clau­ ses, universally and existentially quantified noun phrases, sentence and constituent negation, perso­ nal pronouns and definite descriptions .

1. Semantic representation

A. Introduction

As semantic representation we use the discour­ se representation theory of Hans Kamp (Kamp, 1981 a).

Let D = s 1 , ... , S be a discourse of the fragment. A discourse reBresentation structure (DRS) for D is constructed by successively parsing the sentences and translating the resulting f-structures into a DRS . The translation of an f-structure of a sentence S. proceeds through the application of certain DRS-construction rules which operate, so t o speak, 'from the outside in ' on the f-values of the grammatical functions and features contained in the f-.structure of S . · Thus the order in which the rules are to be appliea is imposed by the hierarchy of the f-structures . I't is important to note that the con­ struction of the DRS for D at the stage of proces­ sing the sentence S. is done with respect to the DRS constructed for~the sentences s 1 , . . . , Si_ 1 .

A DRS for a discourse D consists of a partial­ l y ordered set of D(iscourse) R(epresentations) which in turn consist of:

• (i) a set of discourse referents: discourse indi vi­ duals, discourse states , discourse events and discourse times .
• (ii)a set of atomic conditions of the following types: Let u and v be discourse individuals. (a) 0( (u) , o< (u , v) , where o< is an I (ntransi ti­ ve) V(erb) or T (ransitive) V(erb) respecti­ vely.
• (b) ot (u), u = {1 , where « is a C(ommon) N(oun) and {l a P (roper) N (oun) .
• (c) conditions handling temporal relations , which we will ignore in this paper (see Kamp, 1981 b).
• Translation of f - structures into DRS's

The following natural language constructions of the fragment trigger via their encoding in the the £-structure the construction of the DRS in the following way: Universal quantifiers, conditional sentences and negation introduce subordinate DR's. Quantified common nouns and proper nouns introduce discourse referents. Pronouns do not introduce new discourse referents but must refer to a discourse referent which has already been introduced. Relative pronouns pick up the reference introduced by the nounphrase which dominates the relative clause. Per-. sonal pronouns and definite descriptions pick up a discourse referent which was introduced before and which is accessible in the partial order of DR's.

For the construction of the DRS out of the out­ put of our LFG-parser (for a detailed description of the parsing mechanism see Reyle/ Frey, 1983) consider the following example: (1) Every farmer who owns a donkey beats it. l

The names of the grammatical functions and features correspond to procedures in our program. In (1') this means that we will have the following procedures: PRED, SPEC, ADJ, NUM. The SPEC procedure builds up the DR configuration and introduces discourse refe­ rents. Furthermore it is responsible for the represen­ tation of quantifier scope ambiguities.(Scope ambi­ guities cannot be represented in £-structures (for good reasons). Scope ambiguity is a semantic phenome­ non and must be handled in the semantic representa­ tion.) The PRED procedure introduces atomic condi­ tions on the discourse referents. ADJ guarantees the correct semantic relationship between the relative clause and the common noun and NUM specifies the discourse referents to be discourse individuals or discourse sets. Crucial for the program is the abi­ lity to build up structures which are not fully in­ stantiated and leave unspecified parts as variables (see Pereira, Warren, 1980).

C. Truth conditions for DRS's

The DRS-construction rules are such that they allow for a uniform treatment of indefinite descrip­ tions in arbitrary contexts. Consider the sentences:

• (2 ) A farmer owns a donkey.
• If a farmer owns a donkey, he beats it.
• In (2) the indefinite phrase 'a donkey' is to be in­ terpreted as existentially quantified, whereas in (3) it has a universally quantified reading. By the DRS­ rules indefinite descriptions are interpreted as re­ ferential terms: they always introduce a discourse

referent.

The resulting DRS's are:

(3') the same as (1'') above.

Whether the discourse referent introduced by an inde­ finite description implies existence or not, depends on its position in the partial ordering of the DR's. Exactly those referents introduced in the main DR's imply existence; all other referents are to be'inter­ preted as universally quantified, if they occur in t .he antecedent-DR of a pair of sub-DR's, or as existentially quantified, if they occur in the con­ sequent-OR. Of course the interpretation of the lat­ ter, i. e., the existentially quantified referents depends on the interpretation of all universally quantified referents accessible from them. Thus the role of the partial ordering of the DR's is twofold. First it forms the base for the definition of truth­ -conditions on the DRS. Second it defines an accessi­ bility relation '-+-', which restricts the set of possible antecedents of a pronoun or definite des­ cription to the accessible ones. The truth conditions of a DRS are necessarily recursive. Recall that each DR consists of a set of individuals and atomic con­ ditions, i. e. , it can be ·considered as a partial model. A partial function f from a DR m into a mode l M is called a proper embedding, if it is a homomor­ phism of m into M with respect to the atomic condi­ tions of m. Suppose 1 satisfies the predecessor of a sub-DR m of k - if there is one; if not let 1 be the empty function. Then g is said to satisfy m, if it is a proper embedding of m that extends 1, and if m dominates two sub-DR's m and m then additionally every k that extends g aAd sati~fies m must be ex­ tendable to a h that satisfies m . Let 1 us call the union of the 'highest' DR's of a 2 DRS k the main DR of k. Then k is true in M, if there is a proper em­ bedding of the main DR of k into M (for an exact for­ mulation of the truth conditions see (Kamp, 1981 a)).

Two remarks are in order. First, the truth­ -definition of a DRS of a discourse D is defined for the whole discourse and not for the conjunction of the individual sentences that occur in D. This is necessary in order to account for intersentential dependencies like anaphorical relations. Second, in spite of the fact that we do not want to check the truth of a discourse D in a given model the exact model theoretic interpretation of the DRS's is cru­ cial for our aims to build up an (intentional) data­ base out of D. The reason is that in order to ~et correct answers to questions abaout such a database containing facts and rules, the structures upon whi~h it will be built up must be logically transparent.

D. Anaphoric pronouns and definite description

In analysing a pronoun one has to look for a suitable discourse referent which is to be substituted for the pronoun. The set of candidates is restric­ ted by the partial ordering of DR's. Only discourse referents, which are accessible from the DR under construction, are possible antecedents (see example (3)). Consider however sentence (4) :

1. Wenn kein Mann ein Auto besitzt, das ihm gefallt, dann ist er unglucklich.

(If no man owns a car he likes,then he is unhappy.) The corresponding DRS looks like:

(we represent negation by means of a DR f false I for which no proper embedding exists )

It is not possible to find an antecedent for the se­ cond pronoun in example (4). Therefore a text which consists only of this sentence is not wellformed.

Another problem which should be tackled inter­ sententially are definite descriptions. The senten­ ce "the mad ·hatter hates Alice" is only used cor­ rectly if a hatter was mentioned in the preceding discourse and if it is clear to the reader that there is only one mad hatter. Therefore , in order to analyse definite descriptions we have to take into account the preceding discourse and we have to check whether the existence and uniqueness condi­ tions are fulfilled . For the DRS Theory this means that we have to look for a discourse referent intro­ duced in the preceding DRS for which the description holds and we have to check whether this description holds for one referent only . Our algorithm proceeds as follows : First an intermediate stage is built up where the definite description is replaced by a va­ riable over discourse referents. The attributes of the definite description are given to a search pro­ cedure . This procedure succeeds if one and only one match with a subset of the attributes of an already introduced accessible discourse referent is possi­ ble.* A text is coherent only if all its variables over discourse referents can be resolved.

In our approach, contrary to others, it is not necessary to expand the representation of the sen­ tence containing the definite description with clau­ ses stating the existence and uniqueness conditions.

III . From DRS to database

From the model theoretic interpretation of the DRS it follows that the atomic conditions contained in the main DR express the facts asserted in the dis­ course . The information contained in the sub-DR's express the rules.

In order to answer queries about the content of the discourse represented by the DRS we consider two possibilities:

(I) translating the DRS into a PROLOG - database (II) formulating inference rules which operate di­ rectly on the DRS.

Both lead to a logical database.

The extensional part (i.e. the facts) and the in­ tensional part (i . e. the rules viewed as integrity constraints) are expressed in the same language.

~Surely this is a special case. The attributes of the definite description could be hyponomious to the ones with which the match works. Furthermore the required d.iscourse referent does not have to appear in the DRS representing the text; it could appear in a presupposed DRS which represents world knowledge .

ad (I): For the translation of the DRS's into PRO­ LOG-clauses we developped an algorithm which operates directly on the DRS 's. Thus it is not necessary to translate the DRS's first into predicate logic. If only the consequent-DR 's of a DRS introduce a new pair of sub-DR ' s the DRS is equivalent to a set of Horn-clauses . The translation procedure replaces the discourse referents introduced in the main DR and in the consequent-DR's by their corresponding Skolem f"clnctions. All other discourse referents are replaced by variables.

If the consequent-DR ' s contain more than one atomic formula , each of them gives rise to a separate Horn­ clause.

DRS

PROLOG-clauses

For arbitrarily branching DR's which are not equiva­ lent to Horn-clauses the algorithm is more complica­ ted. In this case it is not convenient to translate into clausal form , because the procedural interpre­ tation of the resulting clauses depends on the Sko­ lem function (appearing in the antecedents) the ex­ tension of which is not represented in the pro­ gramme. The clausal forms for the sentence Jede Frau, die jeden Mann liebt, den sie kennt , ist uberfordert .

(Every woman who loves every man she knows is stres­ sed).

are :

uberfordert (x) ~ Frau (x), not (Mann (f (x)) uberfordert (x) '*-Frau (x) , not (kennen (x,f (x))) uberfordert (x) +- Frau (x), lieben (x, f (x)) To get a programme we have to translate into

uberfordert (x) -+- Frau (x) , not (Mann (y) A

kennen (x,y) ....., not (lieben (x,y)))

(with 'not' interpreted as 'negation as failure') . Hence one has to take into account special PROLOG requirements and has to build up new representations. Furthermore the programme has to be enriched with special 'meta '-procedures to render adequate answers (e . g . a rule yielding the contraposition of a clause) . ad (II): Because of the problems mentioned under (I) we want to investigate the possibility of using the DRS itself - together with inference rules operating on it - as database . A set of inference rules has been proposed by Hans Kamp.