Judgmental Reasoning for Expert Systems

1. Introduclion

Some kind of judgemental or probabilistic reasoning forms an essential part of many expert systems. The need for such reasoning arises whenever knowledge is incomplete or data uncertain. This is the case in many of the problem domains to which expert systems are applied. In this paper we present a system for judge­ mental reasoning which differs in two respects from the more usual approaches. It uses a non-numeric represen­ tation for belief, and assigns certainties to logical formu­ lae rather than events. It is an extension to the work described in (Shapiro 1983).

We shall argue that this system meets the following criteria which should be fulffiled by any system of plausi­ ble reasoning used in expert systems.

(1) Clear semantics

We should be able to provide a clear semantics for our reasoning system. Both the knowledge engineer building an expert system and the end user of the system should know what certainties are and the run-time behaviour of the system should retl.ect these meanings in a well defined manner. If this requirement is not met it is difficult to develop gen­ eral purpose debugging and maintenance tools for knowledge bases.

(2) Ease of explanation

A determining feature of an expert system is its ability ·to explain its reasoning on demand. We require that the derivation of certainties be easily explainable. This entails that the mechanism by which certainties are combined be itself capable of explanation.

(3) Expressive power

The system should be powerful enough to express an expert's knowledge about uncertainty tl.exibly and naturally.

We distinguish two sources of uncertainty. Firstly, uncertainty about observations (or facts) in the applica­ tion domain. Secondly, uncertain rules (or heuristics) which express an expert's general knowledge about the domain. Our system, following the approach of Shapiro (Shapiro 1983) uses an extension of the Horn clause sub- The fundamental idea is to extend the the range of truth values assigned to atoms from the set !false ,true J to certainties. Certainties are lattices and have opera­ tions of least upper bound (U) and greatest lower bound ( n ) defined on them. We are relaxing the restriction that certainties be totally ordered, and specifying that they are partially ordered. This permits the use of non­ numeric certainlies to express knowledge aboul uncer­ tainty. The defined operations allow us to combine cer­ tainties duing the inference process. The rules used by the system are of the form <A<--B ,f > where A<--B is a Horn clause and f is a certainty function specifying how the certainties of the atoms in B are combined to pro­ vide a certainty for A . The ability to specify a combina­ tion function for each rule provides flexibility, although in practice we find that most rules use a general combi­ nation function.

In the next section we describe the formal apparatus underlying our system. Both a model theoretic and fixpoint semantics are 1rovided in the manner of (van Emden & Kowalski 1976 . This {>rovides evidence that we can satisfy criteria (1 and (2) above . We then describe a simple application of the system, which has been implemented in Prolog as part of a com­ plete expert system shell. This provides evidence that we can satisfy criterion (3) above.

2. The formal apparatus

2 1. Basic definitions

/Jefinition

A certainty space C is a complete lattice. This is a par­ tially ordered (under~) set C, with operations U and n (least upper bound and greatest lower bound respec­ tively) defined for every subset of C.

/Jefinition

We extend ~ to sequences over C by defining: <c 1, ... ,en> ~ <c\, .. . ,c'n> iti c 1~c' 1 and ... and Cn~C 'n ·

/Jefinition

A function f from sequences of certainties to certainties in some certainty space C is monotone itl' for all sequences s 1 and s 2 of length n over C. s 1~s2 implies /(sl)~/(s2) ·

/Jefinition

A logic program with uncertainties is a finite (non­ empty) set P of pairs of the form <A<-B,f> where A<-B is a definite (or Horn) clause, and f is a monotone function from sequences of certainties to certainties.

2.2. Semantics

We can now define the semantics of logic programs with uncertainties as an extension of that given by van Emden and Kowalski (van Emden and Kowalski 1976) for definite clause programs without uncertainties.

Definition

The Herbrand Universe U(P) is defined recursively as,

1. The set of constant symbols in P (or the constant symbol a if there are none) .
2. All atoms of the form p(t1, · · · ,t,) where the t; are in U(P).

Definition

The Herbrand base H(P) of a logic program P is the set of all ground atoms formed by usin,g predicate symbols from P with ground terms from the Herbrand Universe U(P).

Definition

An interpretation of a logic program with uncertainties Pis a function from H(P) to a certainty space C.

Definition

An interpretation 11 is ~ an interpretation I:! iff I 1 (a),;;J 2 (a) for all a in H(P).

Definition

A model .M of P is an interpretation of P satisfying the following condition:

For any clause <A<-B,f> in P and any ground instance A'<-B\& · · · &B'n of the clause, then II(A')~/(M(B'I), · · · ,.M(B'n))

2. 2.1 Model theoretic semantics

Definition

Given two models M1 and M2 for Pwe define the intersec­ tion ( n) of the two models pointwise as M1nM2(a) = M1(a)nM2(a)

Proposition

Given two models M and M' for P, the intersection of the two models M nM' is a model.

Proof

(omitted)

Theorem

M(P) = n M exists and is the least model of P. //mmo<iol

Proof

The proof is straightforward.

The meaning of the logic program Pis defined to be the least model M(P) of P

2.2.2 Fixpoint semantics

We now provide a constructive definition of .M(P) by show­ ing it to be the least fixpoint of a function Tp from interpretations to interpretations.

Definition

Let Tp(f) be defined pointwise on an interpretation I as follows :

Proposition

Tp is monotone over the lattice of interpretations, and moreover the lattice of interpretations (with po ,;;) is complete.

Proposition

Tp has a least fixpoint.

Proof

Since Tp is a monotone function on a complete lattice, Tp has a complete lattice of fixpoints and therefore a least fixpoint.

We can elaborate on this result by provin,g that Tp is con­ tinuous as well as monotone if the underlying certainty functions we use are continuous.

Definition

A certainty function r from sequences of certainties to certainties is continuous iff f( U x) = U f(x) for all ... x ... x

chains X.

Proposition

If the underlying certainty functions f are continuous then the correspondin,g functions r~. are continuous .

Proposition

If the underlyin,g certainty functions f are continuous then Tp is a continuous function, that is : U Tp(Jn) = Tp( U In) for all chains lin I n d 1j of nell nell interpretations .

Proof

(omitted)

Proofs omitted above can be obtained from the author on request .

This completes our discussion of the semantics of logic programs with uncertainties, and shows that the mean­ ing of a logic program with uncertainties can be approxi­ mated computationally. The certainty computed at run­ time is a lower bound on the true certainty.

3. An example

To illustrate the practical application of the above we shall describe an implementation in current use at the Turin,g Institute . This is only one possible application of the system, experience with alternative implementa­ tions would be very useful.

Certainties

A certainty is a basic certainty or an ordered tuple of certainties. A basic certainty is a pair A-J where A is an atom and J is its justification, or the empty certainty []. A justification is a conjunction of literals . It is con­ venient to represent a certainty as an ordered tuple of trees where the leaves of the trees are basic certainties. An example is shown in Figure 1 where an en,glish "trans­ lation" of the certainty is provided. In the following we shall refer to this certainty or its translation inditlerently. The application domain is that of claimin,g travel expenses for trips by car for someone employed in Holland.

The certainty illustrated is the certainty of the atom entitlerLto(john, 120) and can be regarded as a structure of assumptions that are necessary to establish the truth of the assertion. These assumptions are :

justified by the fact that John travelled less

• ( 1) The trip was in Holland. than300km.
• John did not travel by boat (unjustified)
• It would cost less to travel by car than by plane This assumption rests in turn on the assumption

that the trip was in Holland (see (1) above), and the assumption that it costs less to travel by car in Hol­ land than by plane.

John is entitled to 120 guilders subject to:

The trip was in Holland justified. by the distance was less than 300km John didnt travel by boat (default assumption) It cost more to travel by car than plane justified. by The trip was in Holland (see above .. .)

The plane costs more in Holland (default assumption)

The English translation of a. certainty figure 1

This example has been chosen to illustrate both the general nature of certainties and that our system can be applied to domains where a numerical measure of cer­ tainty would be inappropriate. We now turn our atten­ tion to the combination of certainties, and the possibility of interaction between certainties.

Combination of certainties

Our default combination function for certainties is concatenation. Given certainties <c 1, . .. , c, 1 > <ci,+l· .. . ,cn> the combination function combines these to give <c 1 , ···,en>· This reflects a default assumption that there is no interaction between different assump­ tions, similar in some ways to the assumptions of condi­ tional independence of events made by Prospector (Gaschnig 1960). It is possible for different assumptions to interact and our system provides an elegant mechan­ ism for describing such interaction. We illustrate with an example based on Figure 1. Let us assume that we

wish to combine that certainty with the following one

The triiJ was abroad justified by the lmgth of the trip was more than 3 days

These certainties are incompatible, since a trip cannot both be in Holland and abroad (by definition). The cer­ tainty function can be set up to provide the combined certainty with value false . In our current implementa­ tion this can be done in a general way by specifying via a meta-logical assertion that the values hoUand. and abroad. are exclusive for the predicate location. In gen­ eral our implementation allows a threshold to be esta­ blished for certainties, and the proof mechanism rejects all solutions which fall below the threshold.

We wish to emphasise that the plausible reasoning mechanism can handle interactions or constraints between certainties in a knowledge based way. Con­ straints can be explicitly represented and reasoned with, and suitable explanations supplied to the user. This is not possible with a system using numeric certainties.

4. Implementation

The mechanism described above has been imple­ mented as part of an expert system shell, called YAPES, wrillen in Prolog.YAPES is an interpreter for logic pro­ grams, either in normal Horn clause logic or in Horn clause logic extended with the judgemental reasoning mechanism. The shell contains all the normal facilities for explanation and justification, implemented via meta­ logical predicates. In addition the Y APES interpreter can call the underlying Prolog interpreter if desired.

We should note finally that the use of numeric cer­ tainty factors is not ruled out in our system. The interval (0, 1] (a lattice whose order is total) used by Shapiro (Shapiro 1963) is an obvious candidate. More interesting perhaps is a combination of numeric and non-numeric certainties. This is the idea advocated by Keynes (Keynes 1921 pp 20-40) in his Treatise on Probability, where he asserted that some though not all probabilities were inherently non-comparable.

5. Conclusion

We have presented a system for plausible reasoning which is a conservative extension of the Horn clause sub­ set of first order logic. We have argued that this system can provide the clear semantics, ease of explanation and expressive power necessary in expert systems.

Our approach embeds the plausible reasoning mechanism within logic, and in particular logic program­ ming systems. This has the advantage that all the nor­ mal debugging tools can be used immediately, and pro­ vides a smooth interface between "normal" programs and programs with uncertainties. This work can be seen as an extension of the work of Shapiro (Shapiro 1963) in three ways

1. Certainties can be non-numeric but also amenable to combination and comparison.
2. The scope of certainty functions has been extended to ordered sequences of certainties rather than multisets. This allows the certainty function to dis­ tinguish between literals in a clause.
3. A fixpoint semantics has been presented for con­ tinuous certainty functions. This provides a compu­ tational characterisation of the behaviour of the system.

The system can be considered as performing a con­ densation of a proof. In Horn clause logic the condensa­ tion is either true or false; using numertc certamtles extends this to the set (0,1]. With a lattice as our cer­ tainty structure the condensation can be as large as the proof itself, although normally we are concerned w1th the assumptions that made during the proof.

From this perspective the system can be seen as eerforming a top-down version oftruth maintenance (Doyle 1979). We are currently investigating the exten­ sion of the allowable certainly funct10ns to provtde com­ bination functions for procedures rather than individual clauses. This will allow for proof condensation at the level of all proofs for a goal, rather than for single proofs. In this way meta-level statements such as "if this goal can be proved in these two ways then ... " can be represented.

6. References

1. Doyle, J." A truth maintenance system." Artificial Intelligence 12 (1979) 231-272.
2. van Emden, M.H. and R.A.Kowalski, "The semantics. of predicate logic as a programmmg language." JACM 23:4 (Oct) (1976) 733-742
3. Gaschnig, J. "Development of uranium exploration models for the Prospector consultant sys­ tem," Final Report, SRI International, Menlo Park,California, March 1960.
4. Keynes, J.M. A Treatise on Probability. London, Eng­ land: MacMillan,1921 .
5. Shapiro,E.Y." Logic programs with uncertainties" In Proc . IJCAI-63. Karlsruhe, West Germany, August, 1963, pp. 529-532.