Some Relations Between Predicate Calculus and Semantic Net Representations of Discourse

SOME RELATIONS BETWEEN PREDICATE CALCULUS* AND SEMANTIC NET REPRESENTATIONS OF DISCOURSE

Robert F. Simmons and Bertram C. Bruce

Department of Computer Sciences The University of Texas Austin, Texas u.s.A.

ABSTRACT

Networks can be used to represent syntactic trees of the semantic relations that hold between words in sentences. They can be alternately symbolized as association lists or conjoined seu of triples. A semantic net represents a sentence as a conjoined set of binary predicates . An alg~­ ithm is presented that converts a semantic net­ work into predicate calculus formalism. The simpler syntax of semantic network representa­ tions in contrast of ordinary predicate logic conventions is taken as an argument for their use in computational applications.

Descriptive Terms: Semantic networks, Predicate logic, Natural language, Computational linguis­ tics, Association lists.

I. INTRODUCTION

In approaches to natural language question answering, it is generally agreed that question and text are to be transformed to some formal language representation. After this has been accomplished, answering a question phrased in a formal language from a data base represented in the same formal language is a process of theorem proving where the data are taken as axioms and the questions as theorems to be proved .

At this point two approaches are commonly found in the literature. One represents question and data in the syntactic conventions of the predicate calculus and uses standard theorem proving techniques such as Robinson's resolution algorithm supported by heuristic selection of relevant axioms (see Green & Raphael (4), Sande­ wall (9), Darlington (2)). The other represents question and text as attribute value lists or semantic nets (which will shortly be shown to be equivalent) and uses a matching algorithm guided by heuristic choices of relevant data. This approach is seen in Quillian (6), Raphael (7), Colby~ !l (1), Schwarcz ~ !l (11).

In the recent literature Sandewall (10) and Palme (5) have each presented more or less for ­ mal developments of semantic network representa­ tions as predicate logics. Thompson (13) shows the similarity of a linguistic case-structure analysis to predi'cate calculus statements.

From yet another point of view, this paper informally shows the similarity of semantic net­ works to predicate calculus representations and argues that the semantic net syntax is computa­ tionally simpler and therefore to be preferred.

*This research was supported by: The National Science Foundation, Grant GJ 509 X

II. THE CORRESPONDENCE AMONG TREE, NETWORK AND ATTRIBUTE VALUE REPRESENTATIONS ·oF DISCOURSE

Linguists are accustomed to representing the structure of natural language sentences as trees. The following sentence El could be represented as in Figure 1.

• El) John made chairs with tools on October 20th in Austin.

For computational convenience Figure 1 can be represented also as an attribute-value list as in Table 1.

Another linguistic representation for El sug­ gested by Fillmore (3) is shown in Figure 2. An attribute-value representation of this structure is also shown there. If the node values "John" , "chairs", "tools", etc. are taken as symbols with unambiguous denotation, and AGT, OBJ, etc . as semantic relations, then Figure 2 is a semant ic ne~ork. The implied definition is that ~ semant i c ne~ork is a system of unambiguous symbo ls interconnected by definable semantic relations .

This is a s imple and convenient representation for computational purposes. Its logic is explaUEd l a t er.

From this discussion it can be seen that the "node -arc-node" structure of networks is a syn­ tax of symbolic notation that can equally well re present a syntactic tree structure or the semantic relations among elements of a sentence.* In e ither case, the net can be symbolized as an a ttribute-value list where the attributes are re l a t i ons and the values are whatever is repre­ sented on the nodes. The attribute-value list, in turn, can be represented as a set of triples whe r e each value may be another set of triples .

Before proceeding into the next section con­ s idering the logical notation for this structure, it is worth mention that Williams (14) developed a network representation for predicate calculus statements following original graphic notations she attributes to Frege. We take this as support of our eventual conclusion that semantic nets can be a fully valid representation of the under­ lying logic of a discourse where the nodes are unambiguous in their denotation and the relati~ arcs are fully defined.

*In Simmons & Slocum (12) the representation is developed for multi-sentence discourse and a ne twork is formall y de fined.

III. SOME LOGICAL ASPECTS OF SEMANTIC NETWORKS

The principal value of using semantic nets for the structure underlying natural language sen­ tences is that they are closer to both the form and the meaning of natural language than other proposed structures, such as first order predi­ cate calculus . In this and the following sections we show that simple semantic nets can be mapped directly into ordinary first order predicate calculus, yet they have several computational advantages because of their proximity to natural language.

One particularly illuminating interpretation of semantic nets is that which considers each node as the name of a set of processes and each relational arc as a restriction on the sets named by the nodes it connects. Thus the set of all "makings" includes all events or processes in which an agent A makes an object B, with an instrument C, on time D, at location E. A, B, C, D and E must satisfy certain restrictions based on their participation in deep case relations, to the verb "make". For example, A, as an agent, must be an animate instigator . Simi la r l y "make " itself is restricted to that subclass of all verbs which have agent, ob j ect, instrument, time and locative cases.

In a specific sentence the set of "makings" may be restricted further . For example in sen­ tence El we have the small subclass of "makings" :

"makings by John, of chai rs , wi th tools, on Oct . 20, at Austin"

Referring to Figure 3 we see that· each node i n the semantic network is also restr i cted by its relations to other nodes. Thus C3 r e fers to a subset of processes wh i ch is conta i ned in the set called "chairs" and in add i t ion serves i n the object relation to a certa i n semanticall y restricted subset of "makings" represented by node Cl .

In this scheme the relations AGT, OBJ, TIM and LOC are defined in two ways. The first is in terms of their logical import; i .e. (A AGT B) where A is a token of make and B of John, indi­ cates that "John" is an argument of the predicatl! "make" . The second is by the restrictions they impose on the nodes they connect. It is these restrictions as well as the interconnections of nodes which determines the semantically restric­ ted sets.

A consequence of this viewpoint is that the statement "John made chairs with tools .· · " can be tested for truth value with reference to a data base (or model) by successive intersections of members from the set of binary predicates !flat represent it, with the set of binary predicates that make up the data base. To produce such a data base, every sentence describing an instance of a "making" is cross-referenced by its semantic relations of AGT, OBJ, INST, etc. to particular specifiers, e.g . , "John", "tools", "chairs", etl:. thus implying the set restrictions that have been described. And each nominal participant in a "making" is cross-referenced by -AGT, -OBJ, etc. to its token of the verb .

In the simplest case such successive inter­ sections are performed by a simple matching al­ gorithm. To answer a question simply find the set of triples matching each triple in the ques­ tion . Methods similar to this are used in many question answering programs. A more sophisticated algorithm could incorporate various axioms for set theory and heuristics based on such informa­ tion as the size of the sets being intersected or the list of semantic relations which determine the sets.

It appears that most questions can be answered efficiently by the recursive use of a simple matching algorithm. More complicated questions may require extensive use of the concept of set restrictions and intersections . Semantic nets are well suited for this kind of question answer­ ing, but they have the additional virtue of being easily transformed into more familiar logics such as first order predicate calculus. Following a more formal discussion of semantic nets and the representation of quantifiers we give an algorithm for converting simple nets into the predicate calculus.

A semantic net is a set of triples, (ARB), where A and B are nodes and R is a semantic relation. Nodes must be elements of a set of unambiguous symbols and semantic relations may be any of several defined or definable relations falling into one of the following categories:

1. Connectives such as OR, NOT, SINCE, etc.
2. Deep case relations such as AGT, OBJ, OAT, etc.
3. Attributive relations such as HOD, POSSESSIVE, HASPART, ASSOC, etc.
4. 4 . "TOK" meaning "is a token of"
5. "Q" meaning "is quantified"
6. Set relations such as SUP, SUB , EQUAL, etc.

Some of these relations are discussed elsewhere (see (12)).

Because of the special significance of the relation Q and its consequences for the transla ­ tion algorithm, some discussion is warranted here. For the purposes of the algorithm which i s to follow we give, in Table 2, a preliminary analysis for some of the kinds of quantification which are needed. Note that such quantifiers a s

"many", "most of the" and "almost all" are omitted from the table although they might be used in semantic nets .

Notes:

1. In the predicate calculus formula, above, F represents the portion of the formula which does not contain x as a free variable, while P(x) is the portion which does.
2. Equivalent predicate calculus expressions.
3. Alternate logical meanings of "SOME-INDEF".

Table 2. Examples of Quantifiers in Semantic Nets

We do not need a complete logical definition for a concept in order to use it in the semantic net. As an example of the complexity which may be avoided · consider the phrase "some fish". This may mean some one fish, several fish, or parts of one or more fish. In a semantic net we use the quantifier "SOME-INDEF" which allows any of these meanings. In predicate calculus we would be forced to select one of the formulas given in Table 2 or perhaps a complicated dis­ junction of all the possible formulas . The consequence for question answering of such vagueness in the semantic net is of course a reduced pre­ cision in the correspondence between question and answer. Thus answering the question "Did John eat a fish?"

from

"John ate some fish." leads to an answer of "maybe" reflecting the imprecision of the match.

IV. TilE TRANSLATION ALGORITHM

The algorithm given here is designed to con­ vert one representation of semantic nets to predicate calculus. Several restrictions are made to simplify the presentation. No higher order predications are handled by the algorithm (such as would normally be required to handle "he moves slowly"). It is assumed that connec­ tives can be treated like verbs, while, in fact, certain connectives may require complex transla­ tion algorithm in themselves. Also, relative clauses are not allowed. In sum, we are dealing with a subset of semantic nets which could not serve as a semantic structure for natural lan­ guage.

Nevertheless, the algorithm does show that simple semantic nets have a sound logical structure, i.e., first order predicate calculus. An algorithm for more complex semantic nets appears to be dependent only upon our understand­ ing of the concepts we wish to allow.

The algorithm handles, in turn, connectives, verbs, nouns, and noun modifiers. It uses push­ down stacks in the customary way. We start with pushdown stacks for the variables G, J, J', F and F', all empty. Capital letter variables (A) denote specific formulas, nodes or arcs under consideration, while small ~etter variables (a) indicate any node or arc.

Algorithm for converting semantic nets to predicate calculus:

1. Start with a conjoined list of triples representing the semantic net of a dis­ course. Call this list, G. Go to step 2.
2. Set J to nil. Go to step 3.
3. If there are any triples in G of the form (A TOK B) such that B is a connective, and such that there are no triples (c r A) where (c TOK d) is in G and d is a connec­ tive, then select the first such triple, call it H, and go to step 4. Otherwise go to step 12.
4. For each connective (or verb) there is a prescribed ordering for its arguments. For example, the verb "give" has the order­ ing AGT, OBJ, DAT. This ordering, specified in the lexicon, is called the "case argu­ ment description for the connective (or verb)". Collect and order (by case argu­ ment description) all triples of the form (A r c) such that A is the first member of H. Form ann-tuple (B c1 c2·· .cn-1) such that B is the third member of H and the triple . (A ri ci is the ith triple in the
5. prescribed ordering. Call this n-tuple, J. Set J' equal to J with the first member removed. Remove from G and all values of G on its stack all triples whose first member is A. Go to step 5.
6. If J' has no members then set G-GAJ and go to step 6. Otherwise go to step 7.
7. If the pushdown stack for G is empty then go to step 2. Otherwise set J and J' to equal the top members of their respective stacks. Substitute G, in J, for the first element of J'. Remove the first member of J'. Set G to equal the top member of its pushdown stack. Remove the top member of the stacks G, J and J'. Go to step 5.
8. If there is a triple in G of the form (a TOK b) such that a is the first element of J' and b is a verb then call this triple K and go to step 8. Otherwise select the triple H·(a TOK b) such that a is the first element of J' and b is a connective. Push G, J and J' onto their respective stacks. Set G to nil and go to step 4.
9. Paralleling the procedure used for connec­ tives in step 4, form an n-tuple (B c1 c 2 ..· cn-l) such that B is the third member of K and ci is the third member of the ith triple in the ordering prescribed by the case argument description of the verb. Call this n-tuple, F. Set F' equal to F with its first member removed. Remove from G and all values of G on its stack every triple whose first member is the first member of K. Go to step 9.
10. If F' has no members then go to step 11. Otherwise go to step 10.
11. Call the last element ofF', D. Form a conjoined list, call it P', of all tri­ ples in G of the form (D r a) except the triples for which r·TOK or r·Q. Convert the triples in P' to prefix notation, (r D a). Set P·P/-.. (E D) where (D TOKE) is in G. Locate the form specified for the X of (D Q X) in the table of quantifiers (Table 2). Let the value of D be the bound variable in that form and substitute P and F as they have been constructed. Call the result, F. Remove all triples whose first member is D, from G. Remove D from F'. Go to step 9.
12. If J is nil, set �~F and go to step 12. Otherwise substitute F, in J, for the first element of J'. Remove the first member of J' and go to step 5.
13. If there are any triples in G of the form (A TOK b) such that b is a verb then select the first such triple, call it K, and go to step 8 . Otherwise, stop.

As an example application of the algorithm we take the sentence:

"The old man give a book to John." The numbering below corresponds to steps in the algorithm. The value of each variable is written out when it changes.

1. G · (Cl TOK GIVE),..(Cl AGT C2),..(Cl OBJ C3) A(Cl DAT C4)A(C2 TOK MAN)A(C2 MOD OLD) A(C2 Q SOME)A(C3 TOK BOOK)A(C3 Q SOME) I\(C4 TOK JOHN}I\(C4 Q PROPER) 2. J · nil 3. no connectives 12. K · (Cl TOK GIVE) 8. B · GIVE F · (GIVE C2 C3 C4) F' · (C2 C3 C4) G · (C2 TOK MAN),..(C2 MOD OLD)A(C2 Q SOME) A(C3 TOK BOOK)A(C4 TOK JOHN} A(C4 Q PROPER)A(C3 Q SOME) 9. F' is non-empty 10. D · C4 P' · ( ) P · (JOHN C4) F · (3C4) ((JOHN C4)/\(GIVE C2 C3 C4)) G · (C2 TOK MAN)A(C2 MOD OLD)A(C2 Q SOME) A(C3 TOK BOOK)A(C3 Q SOME) F' · (C2 C3) 9. F' is non-empty 10. D · C3 p' - ( ) P · (BOOK C3) . F · G C3) ((BOOK C3),..(JC4) ((JOHN C4) "(GIVE C2 C3 C4))) G · (C2 TOK MAN)A(C2 MOD OLD)A(C2 Q SOME) F' · (C2) 9. F' is non-empty 10. D · C2 P' · (MOD C2 OLD) P · (MOD C2 OLD)"(MAN C2) F · (3C2) ((MAN C2)A(MOD C2 OLD),...(3C3) ((BOOK C3)/\(3C4) ((JOHN C4) A(GIVE C2 C3 C4)))) G · ( ) F' · ( ) 9. F' is empty 11. G · (3C2) ((MAN C2)A(MOD C2 OLD)"(3C3) ((BOOK C3)A(3C4)((JOHN C4) A(GIVE C2 C3 C4)))) 12. stop

The final result of the translation algorithm is given in step 11. A simple transformation of the given formula can be make to conform to the particular conventions one wishes to follow, such as infix vs. prefix, the method for hand­ ling proper names, modifications, and other language features.

V. DISCUSSION AND CONCLUSIONS

We have mentioned some of the reasons for using semantic nets as the struction underlying natural language discourse. These may be summar­ ized as follows:

1. Vague or partially undefined concepts may be used in a semantic net by giving rules governing their operation. Many questions will not require the full specification of functions used in predicate calculus. For example, the dialogue:

"The old man ate some fish." "Did the old man eat some fish?" "Yes."

·

does not presume a precise understanding of the meaning of "some", but we would expect a compu­ ter question answerer to be capable of it . The earlier similar example showed that a "maybe" answer is the consequence of vagueness in criti­ cal aspects of the meaning represented in the semantic net.

2. Simple questions will be answered by a simple matching procedure which ~s easily performed in a semantic net. More complex questions will take advantage of the set restriction principles of semantic nets. It is also possible to convert some parts of the net to first order predicate calculus and use some form of Robinson's (8) resolution algorithm.

3. A semantic net seems closer than predicate calculus to natural language form and meaning . For example the nesting of natural language expressions such as

"The man who caught the fish ate it." is easily handled in semantic nets (see (12)) . Lest, however, we be too happy at this situa­ tion, it must be mentioned that there are alter­ nate specifications for process~s, such as "the 20th day of the lOth month" for "October 20" and "a lathe, a saw, a plane and a chisel" for "tools", or "furniture" for "chairs". Managing the possible logical, lexical and syntactic paraphrases of a statement in testing its truth value adds a significant transformational and implicational complexity that must be accommo­ dated if the semantic nets are to be useful in language processing.

These complexities are provided for by addi­ tional relations in a lexicon and graamar . The lexicon shows, for example, that the process named "tools" includes as subsets the processes named "planes", "lathes", "hammers", "saws", etx:.; that "chairs" are a subset of "furniture"; and that there is a transformation that maps "Octo­ ber 20" into "20th day of the lOth month" and the converse. If this additional information is present, it is possible but difficult, to dis­ cover the approximate paraphrastic equivalence of El to E3 in the following two examples:

• El) "John made chairs with tools on October 20."
• E3) "John made furniture with a lathe, a saw, a plane and a chisel on the 20th day of the lOth month . "

1 AGT(make John) 2 OBJ (make X) 3 INST (make Y) 4 TIME (make Z) 5 TOK(X chairs) 6 TOK(Y tools) 7 TOK(Z Oct. 20) 8 SUP(X furniture) El 9 SUB(Y, {lathe, saw, plane, etc.)) 10 IMPLY(201il O:t., (ORDER(day 20~0RDER(month 10)) 11 (TOK(X,Y)ASUB(X,V)~TOK(X,V)) 12 (TOK(X.Y)~SUP(X,V)~OK(X,V)) 13 (TOK(X,Y)AIMPLY(Y,V)~V)

In Figure 4, by augmenting the (partial) seman­ tic representation of El (lines 1-7), with the r elevan t lexical information of lines 8-10 and the inference rules of lines 11-13, it is pos­ sib le to find a correspondence with the represen­ tation of E3. But the selection of the appropri­ ate aug'mentation of El with respect to E3 intro­ duces the need for heuristics to guide the pro­ cess, and algorithms to accomplish the indicated transformations as a part of the comparison procedure.

In conclusion, this paper has shown that net­ work formalisms can be used to represent syntac­ tic structures of sentences or to represent the semantic relations that hold between word mean­ ings in discourse. In the latter case the net­ work is called a semantic network . Networks can be written as graphs, as attribute-value lists, or as lists of triples for the sake of computa­ t ional convenience.

Semantic nets were defined formally and shown to have a se t theoretic interpretation as a structure of relations that restricts the range of a set of events such as all "makings" to some small subset occurring at a particular place and time with a particular agent, object and i nstrument. An approach for handling quanti­ fication in the nets was described and shown to have some advantage over the predicate calculus for representing such vague expressions as "some fish" . An algorithm was presented for translating from a subset of the network formal­ ism to first order logic and there is no par­ ticular reason why algorithms for translating to higher order logics cannot be developed as the convent i ons are established for representing more complex meanings both in the networks and the higher order calculi.

The several representations of structure that have been used widely in question answer­ ing include triples, attribute-value lists, graphs and logical predicates. We have shown the relation of semantic networks to each of these forma lisms to demonstrate the generality and log ica 1 ade.quacy of the semantic network approa:h to representing meanings of natural language discourse . These findings in conjunction with those of Sandewall (10) and Palme (5) support our belief that semantic network structures are a well-formed logic with computational advantages deriving from the similarity of their notational conventions to those of natural languages.