Generating Hierarchical Semantic Networks Froma Natural Language Discourse

Introduction

The ultimate goal of the research described here is to develop a computer program that could con­ struct a hierarchically organized semantic network from natural language input text. This network con­ sists of a set of concepts and a set of many-place relations over this set. Examples of these rela­ tions are the relation between a term and its su­ perordinated term, called SUP, e.g. "mapping" SUP "homeomorphism", or the relation REF between an adjective and each noun that could be modified by this adjective e.g. "commutative" REF "group". Re­ lations among terms can expand to relations among terms and networks. For example, the relation REF holds between the adjective'l::ontinuous" and the noun "mapping". This can be described by the net­ work

Between the nouns "mapping", "set", and "field" there holds the three place relation PRPP giving rise to the network

Now it is possible to formulate a rule that re­ places the value of the one node "mapping" in this last network (:) by the first network (*) to ob­ tain the relation PRPP between the network (*) and the single terms "set" and "field". The resultant network

is called hieiarchical.

The mathematical structure of such a network is a

GENERATING HIERARCHICAL SEMANTIC NETWORKS FROM NATURAL LANGUAGE DISCOURSE+

Camilla Schwind

Technische Universitat, Mlinchen, Germany

hierarchical graph (see C3J). To construct such a network, one can use hierarchical network genera­ tion rules as described in C7J. The network ob­ tained from an input text should be able to repro­ duce the meaning of the text completely and pre­ cisely, that is to say, it should be the semantics of the appropriate text. So the coordination of natural language text to a network, being realized by a computer program, represents what we mean by understanding the text: the fitting computer pro­ gram understands natural language discourse. Com­ plete reproduction of discourse by a network means that no information is lost on the transduction of the text into the network and consequently that it should be possible to reconstruct the primary text from the network once generated. But the recon­ struction is not one-valued. There could be more than one text being reproduced from a network, for there might occur different texts to have the same meaning, and these must correspond to the same net­ work. So generally we obtain one single network for more than one text. Precise reproduction of discourse by a network means that for each text there could be at most one network into which that text is transduced. So the coordination texts-net­ works is a non-injective mapping. This mapping is realized in the following way: There has been written a formal grammar describing arbitrary nat­ ural language texts by which a phrase structure tree is built for each sentence (see [1J). The se­ mantic rules are formulated dependent on the syn­ tax trees following step-by-step transduction of a phrase structure tree into a semantic network frag­ ment*. The concatenation of all the fragments ob­ tained by a text is the final network. In the fol­ lowing we will demonstrate (for an example sen­ tence) the effect of the program, that is to say, how it understands a text. The example sentence stems from a mathematical text out of general top­ ology.

Definition. In a topological space X, a funda­ mental system of neighbourhoods of a point x is any set S of neighbourhoods of x such that for each neighbourhood V of x there is a neighbour­ hood W e: S such that W c V .

For this definition the program finds out:

1. What concept is defined?
2. What other concepts do help to accomplish the definition?
3. Which conceptual relations do exist among these concepts? (see Figure 1).

The names of the concepts (given to them in the text) are kept for further references. Later on they can be replaced by the concepts they design. The prepositional relation OF holds between a concept and its prepositional supplement. The re­ lations EPS and CONT belong to the mathemati­ cal signs e: and s;; ·

• This work has been supported by the SFB 49 of the Deutsche Forschungsgemeinschaft.
• see (C2J)

Hierarchical networks

A hierarchical network consists of a set of con­ cepts and a set of many-place relations among the concepts. The following conceptual relations have been sufficient to describe the semantics of ma­ thematical texts.

• N denotes the set of the nouns.

A denotes the set of the adjectives.

Av denotes the set of the adverbs.

Superordinated and subordinated terms:

For each noun defined in a text exists a superim­ posed term. Adjectives not always possess superim­ posed terms. Nouns that have no superordinated term are called primes (e.g. "set", "class", "ele­ ment"). Supterm 0, specified for a term B in the thesaurus, must always be a directly superordinat­ ed one, i.e. there is no other superordinated term for B subordinated for 0 .

This direct super-relation is noted SUPo.

SUP is the transitive closure of SUP0 · A term can have more than one superimposed term, e.g.:

injective SUP bijective

surjective SUP bijective.

Referential area for adjectives:

For every adjective C there is at least one noun B that can have the property described by the ad­ jective. B is called referential term for C . B is part of the referential area of C, i.e. the set of nouns to that C is applicable. The referential relation is noted REF .

e.g. "continuous" REF "mapping".

Prepositional relations:

Terms that occur in propositional adjuncts of a term B are said to be in prepositional relation with B . The prepositional relation cannot be specified quite exactly. We can state, however, that a. term is modified by its prepositional ad­ junct. The prepositional relation is noted PREP.

PREP s;; ( N X N) u (A X A )

e.g. "order" PREP "set" or "continuous" PREP ;'set".

We also have a three place prepositional relation noted PRPP. PRPP s;; N x N x N · e.g. "mapping" PRPP "set" PRPP "set".

Antonymy:

This relation exists between pairs of terms such as "greater" and "less".

It is noted ANT ·

ANTs;; (Ax A) U (NxN)

According to our hitherto knowledge, in all pairs of terms for which ANT takes place, ANT is based on the antonymy of "greater" and "less".

Synonymy:

Two terms are called synonymons if they are iden­ tical in meaning. Synonymy is noted SYN ·

Adverb-adjective relation: As mentioned above this relation holds between an adverb and an adjective which is modified by the adverb.

This relation is noted AVAJ

AVAJ s;; Av x A.

For each pair this relation is given in the the­ saurus entry of the adjective.

The verbal relation CONT :

This relation holds between the subject and the ob­ ject of a sentence with the verb contain.

For example: The set X contains any point x . Here we have ·set· CONT ·point·. CONT refers to the mathematical connective s;; ·

There exist connections among the relations which can be used to store them in a manner to save con­ siderable amounts of computer storage place. In the following, the set of the superimposed terms of term X is noted OBER(X) .

The class of elements synonymous to a term X is called the synonymy class of X , noted SYN(X) · As there -is at most one element antonymous to a term X , the antonymy class ANT(X) of a term only consists of this element and of X .

The set of terms occuring in the definition of a term X is noted DEFX .

Interrelations between relations:

• E1 SUP is an order relation.
• E2 If a noun B is a referential term for an ad­ jective C , then each subterm M of B be­ longs to the referential area of C , except C or a term antonymous to C belongs to the definition of M or of a term between B and M.

CC REF B A B SUP M A CVXC(B SUP X A X SUP M)

·-,(C f: DEFX v ANT(C) f: DEFX)JJJ · C REF M.

For example: "commutative" REF" "semigroup" and "semigroup" SUP "group" · "commutative" REF "group".

The additional condit ion excludes relations as "isomorph" REF "antiisomorphism" or "injective" REF "bijection" or "bijective" REF "bijection".

• E3 If a noun C is a prepositional adjunct for a term B , each subterm M of C is a prep­ ositional adjunct of B.

( B PREP C A C SUP M) ,. B PREP M ·

E.g.: "element" PREP "Set" and "set" SUP "field" · "element" PREP "field".

• E4 If two nouns L,M are prepositional adjuncts for a term B , then each subterm 0 of L and each subterm P of M is a prepositional adjunct for B .

(B,L,M) e PRPP A L SUP 0 A M SUP P ,. (B,O,P) e PRPP.

For example: ("mapping", "set", "set") e PRPP and "set" SUP "group" · ("mapping" "group" " ") , , set e PRPf, and ("mapping", "set", "group") e PRPP and ( mapping" , "group" , "group" ) e PRPP .

• E5 SYN is an equivalence relation. Sample network:

To describe the semantics of computer science texts, we must add more types of relations, e.g. some verbal relations, that is the relations that hold between a verb, its possible subjects and its possible object and prepositional supplements.

Syntactic and semantic description of texts

The texts which are to be transduced into semantic networks are anaiyzed by context-sensitive rules of a formal grammar G , together with a set of transformation rules T and a lexicon LEX . G is a type-2-language. G = (A, P, DEF). A is the alphabet consisting of grammatical categories like VP,NP (verbal phrase, nominal phrase) and lexical categories like pr'ep, art. The lexical categories are the terminals Ar of the grammar. P is a set of production rules and DEF e A the starting symbol. LEX is a set of type-2-produc­ tions. For each lexical category X e AT there is at least one production rule of the form X : := x . x is then called lexical entry for X. For example: art : : = the e: LEX . "the" is a lex­ ical entry fort art.

The following sample grammar is a typical part of the grammar describing the definitions of "Ele­ ments of mathematics" by N.Bourbaki. It is written using BNF-notation. Terminals are italicized. In some rules subscripts have been used to distin­ guish between occurrences of identical nontermi­ nals. These subscripts are irrelevant for syntax. They will be needed later by the semantic rules.

• ( 1) DEF : : = {S3lo { S} 1
• s .. - pp S2
• (2 ) s .. - pp S1
• S1 : := C be NPINP be called C
• ( 5) S2 : := NP be said to be PREDD if SS1
• (6 ) S3 : := let Nm be NP, {{and}J Mm NP2}0

1. c .. - DNB
2. c, .. - c2 pp
3. DNB : := {art}J ND
4. ( 11) ND .. - NB
5. ( 10) ND1 .. - AP ND2
6. ( 12) AP, : := adv AP2
7. ( 14) NP .. - NPO {SS}~
8. ( 13) AP .. - AB
9. ( 15) NP : := NPO such that SS1
10. ( 16) NPO : := NP1
11. ( 17) NPO : := NP1 PP
12. ( 18) NP1 : := art N
13. ( 19) N, : := AP N2
14. N : := NB
15. N : := NB A'm
16. (22 ) PP : := prep NPO
17. PREDD .. - DAB
18. PREDD : := DAB PP
19. DAB : := AD
20. AD, : := adv AD2
21. AD : := AB
22. ss : := NP VP
23. VP : := verb NP
24. SS1 .. - ss
25. SS1 : := for each NP, there be NP2 such that ss

Comments on the grammar:

• ad(1). A definition DEF consists of at least one s~nte~ce. It can begin with a sentence S3 llke let X be a topological space and A a subset of X" see ( 5) ·
• ad(2),(3). Every sentence can begin with a prep­ ositional phrase, e.g. fig. 2.
• ad( 4). Sentences like "A topological space is a set endowed with a topological structure" and fig. 1. The lexical entries of be a;e all morphological paraphrases of the verb "be" i.e. "is", "are", etc ·· In general by this construction nouns are defined.
• ad(5). Sentences like "an equivalence relation R on a topological space X is said to be open if the canonical mapping of X onto X/R is open". In general by this construc­ tion adjectives are defined.
• ad(7)-(11). C serves to expand the nominal phrase DNB which contains the defined concept ND · It is possiblY followed by a prepositional phrase PP or preceded by one or more adjective clauses AP ·
• ad(12),(13). An adjective can be modified by one or more adverbs adv.
• ad(14),(15). A NP can govern an embedded sen­ tence SS or SS 1 , e.g. a relative clause.
• ad(16)-(21). A NP can have a prepositional supplement PP . It consists of an article art, possibly followed by one or more ad­ jectives and a noun NB possibly followed by its proper name Mm. ·
• ad(22). Prepositional clause. The lexical entries for prep are all prepositions occuring in a text.
• ad( 23)-(27). PREDD serves to expand a defined ad­ jective DAB. It is possibly followed by a PP or preceded by one or more adverbs.
• ad(28) - (31). Sentence constructions as usual. Em­ bedded sentences like in the example in Fig. 1 are very frequent in mathematical texts.
• T consists of three types of transformations rules:

1. Transformation of a NP to a relative pronoun.

2. Transformation of a NP to a proper noun.

1. Transformation of an embedded sentence to a partipicial sentence.

We will not list transformations here in detail, for they are not relevant for the meaning of sen­ tences. They only generate surface structures from deep structures. LEX can be seen in detail in the program data.

The set of concepts occurring in a definition to­ gether with the hierarchical graph they form is built up in a step-by-step manner corresponding to the phrase structure of the definition. This can be done by assigning attributes to the nonterminal symbols and semantic rules to the production rules. Each attribute a corresponds to a set of vaLues Va · The semantic rules define all of the attrib­ utes of a nonterminal in terms of the attributes of its immediate descendants, so ultimately values are defined for each attribute.

For our purposes, we have used a set of attributes A= {d, c, g, lex, n} where

• Vd is the power set of the set of all concepts. The value of d within a definition will be the set of concepts defined.
• Vc is the power set of the set of all concepts. The value of c within a definition will be the set of all concepts occurring in the defi­ nition.
• Vg is the set of hierarchical graphs. The value err g within a definition will be the hierar­ chical graph that means this definition.

Vlex is the union set of all sets of lexical en­ tries of G.

• Vn is the set of relation names. The value of n within parts of a definition is an arc label belonging to the hierarchical graph being built up.

The attributes correspond to the nonterminal sym­ bols in the following way:

• g belongs to {DEF, S, 61, 62, 63, C, CNB, ND, AP, NP, NPO, NP1, N, AD, PP, PREDD, DAB, SS, VP, SS1}
• c belongs to the same symbols as g .
• d belongs to {DEF, S, 61, 62, C, DNB, ND, PREDD, DAB, AD}

lex belongs to {NB. AB. adv. verb. prep}

• n belongs to {VP, PP}.

Now the grammar may be augmented so, that semantic rules are given for each rule of the syntax.

(A 1) g(DEF)

g(S3) ·* g(S)

d(DEF) d(S)

c(DEF) c(S3) U c(S)

(A2) g(S)

g(PP)· g(S1)

d(S) d(S1)

c(S) c(S1)

• (A3) g(S) d(S) g(PP) · g(S2) d(S2)

c(S) c(S2)

• (A4) g(S1) d(S1) g(C) · g(NP) d(C)

c(S1) c(C) U c(NP)

• (A5) g(S2) d(S2) g(NP) · g(PREDD) · g(SS1) d(PREDD)

c(S2) c(NP) U c(PREDD) U c(SS1)

• (A6) g(S3) g(NP,) · g(NP2)

c(S3) c(NP,) U c(NP2)

• (A7) g(C) g(DNB)

d(C) d(DNB)

c(C) c(DNB)

(A8) g(C1 )

[;(-c2) n(PP) :> g(PP)I

d(C,) d(C2)

c(c2 ) U c(PP)

g(ND)

c( c,)

(A9) g(DNB)

d(DNB) d(ND)

c(DNB) c(ND)

(A10) g(ND1 )

d(ND,)

c(ND1 )

(All) g(ND)

d(ND)

c(ND)

· · is the concatenation of graphs. G1 · G2 is a graph which contains all nodes and edges of G 1 and G2 where nodes with the same value are identified.

lg(AP) __ ~F :> _ ~(;p~

Sample sentence recognition and network transducll2.!2

Definition. A base of the topology of a topologi­ cal space X is any set B of open subsets of X such that every open subset of X is the union of sets belonging to B ·

The re~uction and transduction into the network of the first part of this sentence is as follows:

(A9)

see (A 11)

(A7)

see (A11)

(A20) g = Ci~E~12Q]

The computer program that hes been written for the construction of a semantic network from the defini­ tion of "general topology" acts on the basis of a dictionary of trivial terms which - at the begin­ ning of a run - only contains articles, preposi­ tions, pronouns and verbs. There are only about seven verbs in this mathematical texts. These can be treated as terms not bearing conceptual informa­ tion because they generally do not act as concepts. (Exception: to converge. But for this verb there is an adjectival equivalent: convergent.) In perform­ ing the network construction, the program recog­ nizes ("learns") the terms occurring in the text as well as their grammatical category using these "learned facts" to analyse the further definitions . The grammar rules do not act as parameters of the program but are inserted as procedures. This makes the program more efficient but less indifferent to changes. The algorithm partly proceeds like a for­ mal language recognition algorithm, i.e. it attempts to match sentence parts with right hand sides of the grammar rules. But the sentence structure is determined only in so far as it is needed by the semantic rules.

Open questions

1. Embeddings of more than one prepositional clause. Production rule (17) allows to embed one preposi­ tional supplement for a noun phrase. By rule (22) and again (17) we can embed recursively another prepositional clause. Clauses like "an interior point of a subset A of X .·· " are correctly an­ alysed by these rules. But consider the clause "a mapping f of a topological space X into a set X' ..· ". The analysis of this clause by the rules described above is not adequate because the two NPO "a topological space X" and "a set X' " are both embedded parallelly into the NPO "a mapping f". To find the correct analysis in each case, we need the information that "mapping" gen­ erally requires two prepositional supplements whereas "point" and "subset" require only one.

2. If we embed a relative clause into a noun phrase containing a prepositional supplement we can not - on the basis of syntax rules - correctly determine to which noun the relative pronoun refers. In the clause·an interior point of the set which con­ tains ..· "the reference can be determined correct­ ly using the semantic information that only sets but not points can contain anything. But in the clause "a set of the filter which contains .·· " the correct coordination is not possible because a filter is a set too. With the exeption of failures like those described above the program correctly transduced all definitions of the compendium.

Further development

Actually we are developping an algorithm to work on definitions out of the area of computer science To perform this we will need more conceptual cate· gories and relations that is to ~ay we will need verbs as concepts and conceptual -relations betweet verbs and nouns. This program is intended to work with rules as parameters. So it can be used for more than one grammar later. We intend to imple­ ment it with the help of a compiler compiler.