The Interaction with Incomplete Knowledge Bases: A Formal Treatment

1. INTRODUCTION

An important characteristic of any knowledge­ based system is its interaction with a knowledge base (or KB for short) that provides and maintains information about the application domain. In general, there are two distinct modes of inter­ action. between an expert system and its KB: the system will want to ask and to tell the KB about the application area-.--In this paper, I will examine what special expressive requirements are placed on the language(s) of interaction when a system must deal with a KB that is incomplete.

Loosely speaking , a KB is incomplete when it does not have all the information necessary to answer some question of interest to the system. When a knowledge-based system is forced to depend on an incomplete KB, its ability to make decisions or solve problems is seriously compromised. In some cases, the lack of knowledge can be circum­ vented using general defaults [1], while in other situations, special heuristics are required [2]. However, no matter how a system plans to deal with incompleteness, it must first be able to determine where this incompleteness lies. In other words, a system has to find out exactly where knowledge is lacking before it can decide what to do about it. This suggests that a KB must be .capable of provid­ ing information not only about the application area, but about itself as well. Thus, the language used to interac t with a KB must allow a user to define and inquire about what the KB does and does not know. The major issue of this paper, then, is what impact this capability will have on the language

of interaction.

* This work was sponsored in part by the Natural Sciences and Engineering Council of Canada and the Department of Computer Science, U. of Toronto.

THE INTERACTION WITH INCOMPLETE KNOWLEDGE BASES: A FORMAL TREATMENT*

Hector J. Levesque

Department of Computer Science University of Toronto Toronto, Ontario

The approach taken in my work [3] focuses primarily on the formal aspects of this issue. As described in section two, I will be dealing with KB's consisting of formulas of the first order predicate calculus. In section three, I examine what questions one would like to be able to ask such a KB and conclude that these questions are best phrased in a superset of the predicate calculus I call KL. In section four, I examine the language KL in detail and provide a semantics and proof theory. Given this analysis of KL, I then consider its use as a language to interact with a KB: in section five, the formulas of KL are used to ~ a KB and I show that this involves a non-monotonic version of the language; in section six, the formu­ las of KL are used to define a KB and I indicate why this requires converting the formulas into the

language of the KB.

Three areas of related research should be noted. First of all, my formalization of KL owes much to the work on the logic of knowledge and belief pioneered in [4] and continued in [5] and [6] (though my application is somewhat different). Secondly, there has been research on incompleteness from the database area ([7],[8]) concentrating primarily on efficient query evaluation. Finally, although the research here does not deal with defaults or assumptions, the work on non-monotonic reasoning ([9],[10],[11],[12]) has provided techni­

cal inspiration.

2. FIRST ORDER KNOWLEDGE BASES

As described in [13], a first order KB is a finite set of closed formulas of first order logic (FOL). I will restrict my attention to consistent sets of formulas that do not contain function symbols other than a (possibly infinite) set of 0-ary symbols called constants. Moreover, a bijection is assumed to exist between the set C of constants and the set D of entities in the domain of discourse.

A query in this framework is any formula of FOL and is answered by consulting the provability relation ~ to determine what does and does not follow from the KB. For each closed query there are three possible replies: yes, no or unknown, depending on whether the query, its negation or neither follow from what is available in the KB. A KB is incomplete when some query has an unknown answer and complete otherwise.

Consider a typical KB containing facts such as Teaches(john, bill), Student(bill), .·.

To avoid having to include within this KB all the "negative" facts about the application such as

~student(john), ~Teaches(bill,john), ···

an assumption is usually made (once and for all) that the negation of any atomic formula can be in­ ferred from the inability to infer the atomic formula. This is the closed world assumption (CWA) [14) which, along with~ssumption that there is a bijection between constants and entities in the domain, guarantees that any KB is complete.

If, on the other hand, we have a KB that con­ tains

[Student(mary) v Student(susan))

but does not contain either

Student(mary) or Student{susan),

the CWA cannot be used since it would allow us to conclude that neither Mary nor Susan are students, contradicting what is in the KB. This KB only partially describes a world, in that it specifies that one of Mary or Susan is a student but not which. Thus, there is a query that is true in the intended application but whose truth cannot be determined on the basis of what is available in the KB. The KB is, consequently, incomplete.

For the rest of this paper, I will say that a KB knows a formula if it answers yes to the query and, for any predicate p and constant c, that c is a known p when the formula p(c) is known.

3. THE KNOWLEDGE BASE QUERY LANGUAGE

Even though a KB is incomplete, there may be completeness in certain areas. For example, suppose

that KB f- (x)[Teacher{x)=: (x·john v x·jim))

In this case, not only are John and Jim teachers, but the KB knows that they are the only teachers. It therefore has a complete picture of the teachers. On the other hand, it may be the case that

KB 1- (Ex) Teacher (x)

without there being any known teachers. In this situation, the KB knows that there is a teacher but does not know who and so does not have a complete list of t .eachers. There is, moreover, a third possibility which is that it cannot be determined from what is available in the KB whether or not it has complete knowledge of the teachers. So just as the question

Is John a teacher?

may be answered yes, no or unknown, the question

Are all the teachers known?

may also be yes, no or unknown depending only on

what is in the KB.

If the purpose of a query language is to provide an accurate picture of what is and is not available in the KB, we should be able to for­ mulate queries that ask the KB about its in­ completeness. In FOL, a query that asks if there is a teacher apart from the known teachers might be expressed by

(Ex)[Teacher(x) ~ ~<x·cl v ··· v x·ck))

where the c's are constants ranging over all the teachers known to the KB.

There are a couple of problems with this method of asking if all the teachers are known. First of all, there could be a very large number of known teachers. In some applications and for some predicates, there may even be an infinite number. Secondly, we have to know what these constants are in the first place to be able to formulate the query. For a large and complex KB, it could happen that only the KB has this information. One can also imagine situations where the KB will not divulge this information for security reasons while still being willing and able to answer questions about its incompleteness.

This suggests that the KB itself should keep track of its incompleteness in the same way it maintains knowledge of the application area. One possibility, for example, is to have a predicate "Known-teacher" and to allow a KB containing the following:

Teacher{john), Known-teacher(john), [Teacher(jim) v Teacher(dan)), ~nown-teacher(jim), ~Known-teacher(dan).

The problem with this approach (and any other that involves a direct encoding into FOL) is the manage­ ment of this extended language. There is a very definite relationship between "Teacher" and "Known-teacher" that must be captured somehow. Among other things, we want that whenever

Teacher(c)

is in the KB, then

Known-teacher(c)

is as well. The closest we can come to expressing this is by an axiom stating that

(x)[Teacher(x) J Known-teacher(x)).

However, this does not work since this formula is inconsistent with the above KB. The correspondence between "Teacher" and "Known-teacher" is much more complex. In a nutshell, "Known-teacher" should not be a predicate for the simple reason that its truth or falsity does not depend on the domain being modelled but on the model (i.e. the KB) itself.

The solution, then, is to leave the KB as is but to extend the query language to allow questions that refer to the current state of knowledge of the KB. The query language I propose, called KL, contains all of FOL and, in addition, has formulas of the form Ka read as The KB knows that a.

This leaves us with a first order KB while still allowing us to query the KB regarding its in­ completeness. In particular, we have a new form of query evaluation

KB I r a

where II- is some (as yet to be specified) provabi­

lity relation and a is any formula of KL. For example, to find out if the KB has an incomplete list of teachers, we ask if

KB II- (Ex)[Teacher(x) A ~K[Teacher(x)]].

Similarly, while the query

(Ex) Teacher(¥)

can be used to find out if there are any teachers, the query

(Ex)K[Teacher(x)]

asks if the KB knows who any of them are. To be able to define the II- relation, we must first look at the semantics of the language KL itself.

4. THE LANGUAGE KL

The query language KL has the same formation rules as FOL but also includes the rule

If a E KL then Ka E KL.

There are, consequently, two kinds of formulas in

KL: the first, like

will be true or false depending only on how the world is, that is, on the interpretation of the constant and predicate symbols; the second, like

K[p(c) A (Ex)q(x)]

will be true or false depending only on how the KB is, that is, on what is and is not known. I will call the latter formulas pure. There are also formulas in KL that are mixtures of the two types and whose truth value depends both on the world and the KB. KL also allows for meta-knowledge in

formulas such as

K[ (Ex)Kp(x)]

which talk about the KB's knowledge of its own knowledge.

The semantic interpretation of a closed formu­ la of KL will depend on both a world description (or interpretation, in the Tarskian sense) and a description of a KB. In general, a KB can be view­ ed as a partial description of a world and can thus be characterized by a set of world descriptions. To make all of this more precise, first note that because of the assumed bijection between constants and entities in the domain, a world description need only assign a truth value to the atomic sen­ tences. Thus, we can define the set of world descriptions as

KB descriptions are, then, just non-empty sets of world descriptions:

The interpretation of any closed formula a is pro­ vided by the function V.

V £ [KL x WD x MD 4 {T,F}] is defined by V(a,w,m) · w(a) when a is atomic, V(~,w,m) · Tiff V(a,w,m) · F, V(avp,w,m) K T iff V(a,w,m) · T or V(p,w,m) = T, V((Ex)a,w,m) =Tiff for some c, V(a<x/c>,w,m) =T, V(Ka,w,m) · Tiff for every w 1 Em, V(a,w',m) = T.

A formula is valid when it is true with respect to every world and KB description. In the case where a is pure, I will use V(a,m) to refer to the truth value of a with respect to the KB described by m.

Turning now to the proof theory for KL, since the language includes FOL as a subset, we will need the axioms of FOL and its two inference rules: modus ponens and universal generalization. To account for the K operator, we have to realize that it behaves like a provability relation in that something is known when it "follows" from what is available in the KB. We will, therefore, insist that the axioms of FOL are known and that the KB is able to perform modus ponens and universal generalization based on what is known. This might be called the assumption of competence. As for meta-knowledge, it is convenient to assume that the KB knows the correct truth value of any pure formu­ la. In other words, there is never any reason to tell the KB about itself nor is there any reason to doubt what the KB knows about itself. No matter how incomplete or inaccurate a KB can be about the world, it is assumed to be the final authority on itself. This might be called the assumption of closure. Note that this assumption applies only to pure sentences. Fortunately, these can be given a syntactic characterization: a formula is pure iff every occurrence of a predicate symbol appears within the scope of a K operator. We therefore have the following axiomatization of the language KL:

Axiom Schemata

1. The axioms of FOL
2. Ka where a is an axiom of FOL
3. K(a~p) ~ (Ka~Kp)
4. (x)Ka ~ K(x)a
5. a:: Ka where a is pure

Rules of Inference

Modus Ponens and Universal Generalization

If we let ~ denote the provability relation for this axiomatization, then the key result here is that the proof theory is both sound and complete with respect to the semantics given above:

Theorem: 1- a iff a is valid.

One thing to notice is that by the closure property, we have that for any pure a

This is, however, not the case for arbitrary a in that, for example, the set

{,p(c), Kp(c)}

is satisfiable and, hence, logically consistent. This is a situation where the KB is behaving proper­ ly but just happens to be mistaken about the world. So, in some sense, the K operator should be read as "believe" rather than "know". On the other hand, the kind of belief involved here is very special in that a KB will always think it is dealing with knowledge since

f- K(Ka::J(l)

for any formula a, So there is an aspect of commit­ ment to what is believed in that a KB will ne~ believe it has mistaken beliefs.

5. QUERIES REVISITED

Having examined the semantics and proof theory of KL, we are still faced with the problem of specifying what is meant by

KB I~ a where KB ~ FOL and a E KL.

The idea here is that this should mean

"If I know only what is in KB, then I know a."

Semantically, this is saying that Ka is true with respect to the knowledge base that has the least amount of world knowledge consistent with knowing everything in KB. Thinking of a knowledge base as described by a set of world descriptions, we want the least amount of world knowledge and, thus, the largest possible set.

Let M(KB) · {w I w satisfies the KB}.

Any knowledge base that knows more than what is in the KB is described by a subset of M(KB) and, so, has a more refined view of the world. This suggests how query evaluation can be defined semantically:

Let KB I 1- a iff V(Ka,M(KB)) · T.

So, the answer to a question is yes exactly when it

is known to .be true in M(KB). For example, if then

KBl II- Teacher (john), KBl II- -,K(Student(bill) ], KBl II- (Ex)K[Teacher(x)],

KBl lf-K.,K[Student(bill)],

KBl II- .,K [(Ex) [Teacher (x) " .,KTeacher (x) ] ] ·

The last statement above confirms that KBl knows that it does not know if it has a complete list of teachers. Note that If- is a non-monotonic opera­ tor in that it is not the case that

KBl + Student (bill) II- -,K[ Student (bill)].

However, unlike a fully general non-monotonic logic as presented in [9) or [10], the If- operator here has been given a simple and natural semantic characterization. Below I will present a proof theoretic analogue of this operator and claim a soundness and completeness type result, but before doing so it is necessary to examine how KL can be used to specify a KB.

6. THE KNOWLEDGE BASE DEFINITION LANGUAGE

Since, for incomplete KB's, the CWA is not used uniformly, it would be extremely convenient to be able to tell the KB when (if ever) the assump­ tion could be used for special cases. Conversely, we should also be able to tell the KB when the CWA cannot be used. If we let

A · (Ex)[Teacher(x) 1\ .,KTeacher(x)]

then .,A states that if someone is not currently known to be a teacher then he is not a teacher. So .,A is the CWA relativized to teachers while A itself is a statement that this assumption cannot be used (because there are teachers other than the currently known ones). The question immediately arises as to whether or not we can add formulas such as A or .,A to a KB, thus generalizing a KB to be any consistent set of formulas from KL instead

of FOL.

There are a number of problems with this generalization but I will address only one of these relating to the formula A. The idea here is that we would start off with a KB such as KBl defined earlier. Since KBl does not know whether or not John is the only teacher, it is not the case that

either

Suppose we consider telling it that it does not have all the teachers and get

If we now want to tell the KB that Jim is a teacher, we get

KB3 = KB2 + Teacher(jim).

KBl · {Teacher(john)}

The problem here is that KB3 still contains A and, consequently, still thinks it is missing a teacher. In fact, no matter how many teachers we tell the KB about, it will still think it is missing at least one. Moreover, if we try to tell it that it finally has all of them by adding ~A, then we arrive at an

inconsistent KB since it also contains A.

What should have happened here is somewhat different. Once we arrived at KB2, the KB should know that it is missing a teacher and hence believe A. However, once a new teacher is added to the KB to produce KB3, the KB has no way of knowing whe ther or not this is the last teacher it was missing and so it should be the case (as with KBl) that neither

KB3 II- A nor KB3 I f- -,A.

In other words, after the introduction of Jim, the KB should no longer know whether or not it has all the teachers. In fact, the knowledge it had as KB2

is lost when it becomes KB3.

Th is is a strange kind of non-monotonicity. The usual symptom of a non-monotonic logic is that the addition of a new axiom invalidates a previous theorem. In our case, the addition of the new axiom invalidated a previous axiom. The curious puzzle here is that there is no "belief revision" going on in the sense of a realization that an axiom was incorrectly added to the KB. Similarly, there is no admission of the world having changed in the s ense of someone becoming or ceasing to be a teacher. In fact, the only change that has taken place is a change in what is known about the world. But this i s enough since A does make reference to the current state of the KB. So without admitting that the world has changed or that some previous state­ ment about the world needs revision, we can still maintain that the truth value of A can change by noting that the state of the KB has changed. Thus, A cannot be part of the KB since the state of knowledge it refers to disappears as information is acquired.

The solution to the problem of the addition of A to a KB is, therefore, to treat the formula as ordinary world knowledge where the K operator is used to refer to the current state of the KB. This is only natural since a KB is assumed to have com­ plete knowledge of itself. Consequently, any mention of what is known in a new piece of informa­ tion must be "referential" and not "attributive". Thus, the addition to the KB must be understood by first resolving these references. In other words, the solution to the problem is not to prohibit additions like A, but rather to allow A in the KB definition language but not the KB itself. For example, KB2 now becomes

where we have replaced the open formula

K[Teacher(x)]

by a fi rst order formula that resolves this reference with respect to KBl:

(xzjohn).

This produces the property that

KB2 II- A

and neither KB3 II- A nor KB3 II- ,A as desired.

The solution I have proposed above presupposes that there will always be a formula of FOL that can be used to resolve any reference to what is known. It is worth noting that this cannot be done independently of a KB in that there is no formula a of FOL such that

f- KA :: Ka .

Of course, all we really need is a formula for each KB and not a formula that works for every KB. Fortunately, if we assume the availability of an equality predicate and restrict ourselves to finite KB's, this can always be done. ---

Theorem: Assume KB is finite and a(xl, ··· ,xk) E KL. There is a formula /a/ E FOL (with equality)

such that KB If- (xl) .·· (xk) [Ka :: K/a/ ).

The formula required here can be defined by:

/a/ = a when a E FOL, /(a~p)/ z (/a/~/p/), /Ka/ = RESOLVE[/a/). f.,af = ~Ia/, /(x)a/ = (x)/a/ and

RESOLVE[a] = If a has no free variables then if KB 1- a then (x) (x=x) else -,(x) (x=x) ---/*Assume x~free in a and tha t cl, ··· ,ck but not care all the constants in a or KB */

else [(xzcl A RESOLVE[a<x/cl>) ) v .·. v (x·ck A RESOLVE(a<x/ck>]) v (x;cl A ··· A x;ck A RESOLVE( ~<x/c > ] <c/x>)]

The method of allowing all of KL to specify a KB i s thus to let

KB + a = KB u {/a/} for any a E KL.

Viewed more semantically in terms of world descrip­

tions, we have that

Note that although the function RESOLVE is not recursive, it is strictly proof-theoretic. More­

over, it can be shown that

Theorem: For any a € KL, KB If- a iff KB 1- /a/.

which defines a syntactic version of query evalua­ tion that is exactly equivalent to the semantic one defined earlier. Of course, the proof theory is not axiomatic but this is to be expected given that

{a € KL I I f- a}

is not recursively enumerable. So, to s ummarize, although the interaction with a first order KB should allow the language KL to be used, this inter­ action can be understood in first order terms when the KB is finite.

7. CONCLUSION

In this paper, I have considered from a formal standpoint the problem of interacting with an in­ complete KB. The motivation behind the research is that, to effectively deal with partial knowledge, a system must first be able to determine the exact limits to what is known. This, in turn, places certain requirements on the language used to inter­ act with a KB. In particular, the language has to be able to refer to the state of the KB as well as to the state of the application domain,

To this effect, I proposed a language KL for interacting with a first order KB and presented a proof theory and semantics which were direct exten­ sions of their FOL counterparts. KL was then applied to query evaluation and I showed that this required a non-monotonic operator. Semantic and syntactic interpretations of this operator were provided. Finally, KL was applied to KB definition and I demonstrated why this required reducing KL into the language of the KB, FOL. In fact, the net result was that the KB remained first order, but that interaction with it took place in a more expressive language.

Apart from the more practical implications of this work, there remain open questions · even within the formal framework. I have not mentioned, for example, what impact the presence of an equality relation or non-constant terms would have on KL. Also, a method of handling defaults (and exceptions) is a reasonable goal given that the framework allows one to determine where their application is needed. In summary, the framework provides not only a formal standard against which to measure representation languages, but also a basis for further exploration.