Logic Programs With Uncertainties: A Tool for Implementing Rule-Based Systems

1. Introduction

One natural way to implement rule-based expert systems is via logic programs. The rules in such systems are usually definite clauses, or can easily be expressed as such, and the inference mechanisms used by such systems are built into the Prolog interpreter, or can be implemented in Prolog without much effort .

The one component of expert systems which is not readily available in logic programs is a language for specifying certainties of rules and data, and a mechanism for computing certainties of conclusions, given certainties of the premises. Clark and McCabe [1] suggest an implementation technique for solving this problem. They augment each predicate in the rule-language with an additional argument, whose value is the certainty of the solution returned in this predicate, and augment the condition of each clause with an additional goal, whose purpose is 'to compute the certainty of the conclusion of the clause, given the certainties of solutions to the goals in the condition of the clause.

In this paper we propose a different way of implementing rule-based expert systems within Prolog, in which evaluation of certainties of solutions is carried out at the meta-level, within the logic program interpreter itself. This resulting framework, called logic programs with uncertainties, has the following properties:

• It is amenable to theoretical analysis. In particular, a precise semantics can be given to logic programs with uncertainties.
• Standard logic programs are a special case of logic programs with uncertainties. If all certainty factors are 1, then the semantics defined and the interpreters developed degenerate to the standard semantics and the standard interpreter for logic programs.

1 This research was carried while the author was at Yale University, supported by the National Science Foundation, grant No. MCS8002447.

Logic Programs With Uncertainties: A Tool for Implementing Rule-Based Systems

Ehud Y. Shapiro 1 Department of Applied Mathematics The Weizmann Institute of Science Rehovot 76100, ISRAEL

• Since the semantics of logic programs with uncertainties is simple, it is easy to apply the debugging algorithms developed in [3].

We consider the last point to be of great importance. Algorithmic debugging can provide the essential link between the expert and the executable realization of his knowledge, and thus facilitate the process of knowledge transfer and debugging.

The paper defines the syntax and semantics of logic programs with uncertainties, develops an interpreter for such programs, and suggest how algorithmic debugging can be used by an expert to debug such rule-based systems. Examples are not included due to space limitations.

2. Logic programs with uncertainties

A definite clause is a clause of the form A+-B, where A is an atom and B is a conjunction of zero or more atoms. A certainty factor c is a real number, greater than zero and less than or equal to one. A certainty function f is a function from multisets of certainty factors to certainty factors . A logic program with uncertainties Pis a finite set of pairs <A+-B,[>, where A+-B is a definite clause and f is a certainty function .

The certainty function is used to compute the certainty of the conclusion of a clause, given the multiset of certainties of solutions to goals in the condition of the clause. We require from a certainty function f that for every multiset S, J(SU{l})=J(S) , and that f be monotonic increasing, which means that S~S' implies J(S)~J(S'), where ~ is the partial order over multisets, defined as follows. LetS and X {x 1 , x 2 , .. . , xn}, be two multisets, n~O. Then X~S iff there is a multiset Y {y 1 , y 2 , ... , Yn} such that S~Y and xi~yi, O~i~n. Our theoretical treatment is independent of the particular certainty functions chosen, as long as they satisfy these two requirements.

For every pair <A+-B,f> in P, the number !( {}) is called the certainty factor of A+-B in P.

We define semantics for logic programs with uncertainties. An interpretation M of a logic program with uncertainties Pis a set of pairs <A,c>, where A is a ground atom and c is a certainty factor. We require that M contains at most one pair <A,c> for any atom A.

A ground atom A is true in M with certainty c iff there is a pair <A,c'> in M such that c~c' . An atom A is true in M with certainty c iff for every ground instance A' of A, A' is true in M with certainty c (instances are taken over the Herbrand base of the program PJ.

Definition 2.1: Let A+-B 1 , B 2 , ... , Bn' n2:0 be a ground definite clause, f a certainty function and S the multiset of certainties {c 1 , c 2 , ... , en}, such that <Bi,ci> is in M, for every l~i~n (if no such pair exists for some atom Bi then S is considered undefined). Then A+-B is true in M with respect to f iff either S is undefined or A is true in M with certainty f(S) .

A definite clause A+-B is true in M with respect to f iff any ground instance A'+-B' of it is true in M with respect to f.

A logic program with uncertainties Pis true in Miff for any pair <A+-B,J> in P, A+-B is true in M with respect to f.

Note that if the certainty factors of all clauses in P are 1, the semantics thus defined is equivalent to the standard semantics of logic programs [2] .

We define a partial order on interpretations. Our goal is to define the analog of the minimal model of standard logic programs . Let M and M' be interpretations. Then M~M' iff for any pair <A,c> in M there is a pair <A,c' > in M' such that c~c'.

Definition 2.2: Let P be a logic program with uncertainties. Then M(P) is defined to be the minimal interpretation M under ~ such that P is true in M.

To see that a minimal interpretation exists, one can define intersect ion of interpretatio~s in the natural way, and verify that for any two interpretations M and M', if P is true in M and M' than P is true in MnM', and that MnM'~M. It is easy to see that M(P) is the intersection of all interpretations M such that P is true inM.

A less trivial exercise is to associate a transformation Tp with the program P, and to prove that the least fixpoint of Tp is M(P).

This completes the definition of the semantics of logic programs with uncertainties.

3. Interpreters for logic programs with uncertainties

We describe interpreters for logic programs with uncertainties, written as a logic program. First we show a standard meta-circular interpreter for logic programs. We use upper-case strings as variable symbols, and lower­ case strings for all other symbols. We assume that the conjunction B 1 , B 2 , ... ,Bn is represented as (Bl'(B 2 ,( ... ,(Bn,true) ... )) , that the atomic clause A is represented as A +- true, and that a program P is represented as set of clauses clause((A+-B)) for any clause A+-B in P. The semantics of solve(A), given P, is "A is provable from P'

An interpreter for logic programs with uncertainties solve( true).

solve((A,B)) +- solve(A), solve(B)

solve(A) +- clause((A+-B)), solve(B).

Figure 1: A meta-circular interpreter for logic programs

is an extension to this interpreter. It assumes that the program P is represented as clauses "clause( <A+-B,F>) +-" for any clause A+-B with certainty function Fin P. Also, multisets are represented using Prolog lists: [] is the empty list, which represents the empty set, and [X]Y] is the list whose head is X and tail is Y, which represents the multiset {X}UY

solve( true,[]). solve((A,B),[X]Y]) +- solve(A,X), solve(B,Y). solve(A,F{S)) +- clause( <A+-B,F> ), solve(B,S).

The semantics of solve(A,C) is "A is provable from P with certainty C". The interpreter returns in C an unevaluated expression with occurances of certainty function symbols in it. To compute the actual certainty factor one has to evaluate this expression. Note that, due to th e (nonlogical) way the certainty of solutions is computed, the second argument of solve can be used for output only, or, in other words, the interpreter is applicable only in case the certainty factor is not inst antiated in the input goal. Also, most Prolog implementations do not allow expressions of the form F{S), where F is a variable symbol. There are standard techniques to get around the problem.

Ideally, one would like to specify some certainty th reshold , with the intention that the interpreter will compute only solutions with certainty above this th reshold . We develop a special purpose pruning interpreter for a particular scheme of certainty functions, and then show how to generalize it.

Since the semantics defined for logic programs with uncertainties proves to be insensitive to the particular certainty funct ions chosen, we tend to believe that no theoretical argument will be able to decide between the reasonable alternatives. Sociologically speaking, this conjecture has proved itself so far . Each school of expert systems is using its own particular way of computing certainties, with no noticeable difference in the validity of their results.

So we pick our pick. The certainty functions we choose, cfc(S) , computes the product of c and the minimal element of S, in case Sis not empty, and returns c otherwise. These functions meets the requirements stated above. As the difference between the functions associated with the different clauses is just the constant c, we represent clauses as pairs <A+-B,c>, where c is the certainty factor of A+-B in P. The interpreter in Figure 3 below has this function scheme built-in. This interpreter receives as input a goal and a threshold of required certainty for solutions, and prunes computations for which it is evident that any solution found along them will not meet this threshold. The semantics of solve(A,T,C) is "A is provable from P with certainty C,and C?:. T'.

The · way the interpreter prunes low-certainty execution paths is via the call times(T' ,F,1). If the results of dividing T by F is greater than one, the call fails, as T' is not a certainty factor then. Note that times serves three functions in the interpreter: it computes multiplication and division, and prunes computation paths which fail to pass the desired certainty threshold. A similar interpreter can be built for most reasonable schemes of certainty functions.

This interpreter has the following interesting property: it always terminate if every clause in the solve( true, T,1 ).

solve((A,B) ,T,C) +-

solve(A,T,..\1 , solve(B,T,Y) , min(X,Y,C).

• solve(A , T,C) +- clause( <A+-B,F> ), times(T',F,1) , solve(B,T',C'), times(C',F,C).

times(X,Y,Z) +- "X times Y is Z, and they all are certainty fact ors (i .e. X , Y and Z are all less than or equal to 1 and greater than 0)".

min(X,Y,Z) +- "Z is the minimum of X andY" .

Figure 3: A specialized interpreter that accepts a certainty threshold

program it executes has certainty factor less than 1. More precisely, if the largest certainty factor of any clause in P is c*, c* < 1, and the interpreter is invoked with a certainty threshold t, O< t~ 1, then the number of goal reductions on any execution path of this interpreter would be no more than the the smallest positive integer n for which c*n < t.

A similar property holds for the following, more general interpreter, shown in 4. The semantics of solve(A,T,F,C) is "A is provable from P with certainty C, and F{ C)?:. T'. The variable T carries the input certainty threshold , F the express ion representing the certainty funct ion computed so far, and C the certainty of the solution to A, which is a certainty factor in case A is an atomic goal , and a multiset of certainty factors in case A is a conjunctive goal.

solve( true, T,F, []) . solve((A,B),T,F,["'\111) +­ solve(A,T,.>.S(F{S)),X), solve(B,T,.>.S(F{[X[S])) ,Y). solve(A,T,F,F'(C)) +- clause( <A+-B,F' > ), F{ F' ( [])) ?:. T, solve(B,T,.>.S(F{F'(S)));C).

The way the interpreter trims low certainty computation paths is via the goal F{F'([]))~T The maximum of any certainty function F is at [], by the monotonicity requirement. Hence if at its maximum the value of the function .>.X(F{F'(X))) is still less than the certainty threshold T, the computation is bound not to meet this threshold.

4. A Note on debugging logic programs with uncertainties

Since a logic program with uncertainties has semantics, one can debug it like any other program, if one knows its intended interpretation. That is, if one knows the input-output relations it is supposed to compute, and their associated certainties. In particular, the diagnosis algorithms described in [3] are applicable in such a situation .

Assume that a logic program .wJ.th uncertainties has (tft.-t..\"'tj a conclusion A whose computedAis judged by the expert to be too high. We can conclude that, according to the interpretation the expert has in mind, the program contains at least one false clause. Such a clause can be detected by querying the expert about the truth (or certainty) of intermediate conclusions obtained during the proof of A, as done in [3] .

The advantage of having such a diagnosis algorithm is more valuable for the debugging the rule-base of a system by an expert then for normal program debugging: In normal program debugging the debugger IS a programmer, who not only knows the intended declarative semantics of the program (i.e. what it should compute), but its procedural semantics (i.e. how it computes) as welL

This is not necessarily the case with experts and rule-based systems. One reason for expert systems being composed of a rule-base and an inference mechanism is to allow the expert to effectively transfer her knowledge in a declarative form to the system, even when she is ignorant of the particular inference mechanism used. The debugging algorithms allow the expert to maintain this appropriate ignorance even when she is debugging the rules she suggested, since these algorithms simulate the execution of the inference mechanism, and query the expert for declarative information only.

6. Conclusions

Logic programs with uncertainties provide a sound theoretical basis for systems which contain only an approximate description of a domain. Their clear declarative semantics allows the expert to tune the system to reflect his knowledge, while maintaining ignorance of the inference mechanism the system implements.