Prolog/Ex 1, An Inference Engine Which Explains Both Yes and No Answers

ABSTRACT

The language Prolog owes much of its in creas ing populari ty to the fact that one can use it to write knowledge based systems in a declarative style, writing a specificat ion which is also executable . Whe n a system wr itt en in Prolog produces a yes answer t o a ques tion, it can be made to produce an exp lanation of its reasoning

PROLOG/EX1, AN INFERENCE ENGINE

WHICH EXPLAINS BOTH YES AND NO ANSWERS

Adrian Walker

IBM Research Laboratory San Jose, California, USA

are present, and a fact which is not li sted is considered to be unknown. For example, the Emyci n ( 1 0) confidence factors + 1 and - 1 can be considered as denoting True and False, respectively , in an open world knowledge base .

However, some reasonable spec ifi cations writte n in Prolog do not produce any answer when executed. Also, when a knowledge base answers no to a question , it does not explain why .

This paper describes a new inference engine, ca ll ed Prolog/ Ex1 . Many programs which do not p roduce any answer in Prolog do produce answers in Prolog/Ex1 . Prolog/ Ex1 prov ides exp lanations of both yes and no answers.

I INTRODUCT ION

It has been pointed out that advice from an expert system may on ly be useful if the sys t em can explain the reasons for the adv ice . For example , given the advice "your car cannot be repaired for less than the cost of a new one", most people would want to know why. Several ex isting expert sys t ems ca n exp lain their activ iti es t o some degree (e.g. 10 , 11), and Michie (5) has argued persuasivel y that expert systems should be understood by their users.

In many expert systems , the knowledge required for expertise is held in the fo rm of assertions and if - then rules (7, 10). Most such systems answer a question by chaining through rules t o reach assertions . In ( 13) it is proposed that it is useful to think of an explanation as an edited proof, and to think of a proof as an edited trace. (11) takes a

similar point of view .

The assertions and rules in a system can be used to represent a portion of the real world in two different ways . Under the "closed wo rld assumption " (8) only positive facts·are stored, and it is assumed that all facts which can not be deduced are false . The representation is the one used in relational data bases (3). Under the "open

world assumption", both positive and negative facts In the language Prolog (2), the closed world assumption prevails (un.less the language is used to simulate a system such as Emycin) , and the property that a fact is false if it can not be deduced is normally provided via a library definition of a "not" symbol . (1 , 8) have s hown that this leads to reasonable logical behavior under some assumptions which are acceptable in practice. Proof extraction can be used to cause any knowledge base written in Prolog to provide explanations of yes answers (13) . However , when such a knowledge base answers no to a question, it does so by failing to find a proof. Hence proof extraction ca nnot be used directly to explain why something is not so.

This paper describes how a modif ied interpreter·, called Prolog/ Ex1, assigns a procedural meanlng to some programs which lack this in present Prologs , and how explanations of both fa ilure and success a re generated.

II DECLARATIVE AND PROCEDURAL MEANI NGS

This section assumes some acquaintance with the Prolog language (2). Our notation for a Prolog clause follows (9) in using '<-' and '&' for 'if and 'and', respectively . Variables start with a capital letter, whereas constants do not . (14) describes the declarative and procedural ways of viewing a Prolog program.

The majority of Prolog programs whi c h are declaratively reasonable also behave as expected procedurally. However, under standard interpreters (6 , 9), some return no answer. By way of example, consider

Example 1 fly(Jfk, Chi) <- fly(Jfk, Bos) & fly(Bos, Chi). fly(Jfk , Bos) <- flight(Jfk, Bos) . flight(jfk, bos) . flight(bos, chi) . flight(bos, sfo) . flight(chi , sfo) . flight(sfo, lax).

Declaratively, this program states that, in addition to the assertions, fly(jfk, sfo) also holds. Procedurally, trying to show this yields an unbounded recursion on the first clause, so no answer is computed.

With present interpreters, such a program must normally be rewritten e.g. by interchanging the first two clauses, or as

Example 2 fly(Jfk, Bos) <- flight(Jfk, Bos). fly(Jfk, Chi) <­ flight(Jfk, Bos) flight(jfk, bos). flight(bos, sfo). flight(sfo, lax). & fly(Bos, Chi). flight(bos, chi) . flight(chi, sfo) .

The change is easy enough, and it fixes one pr·oblem. However, suppose we add the assertion flight(sfo, jfk) and ask for all of the possible pairs of endpoints of journeys . In standard Prolog no answer is found at all, because the interpreter keeps trying longer and longer proofs of the same journeys. Prolog/ Ex1 finds the correct answer.

While it is possible to now rewrite this program so that it terminates in standard Prolog, there are other more complicated programs which do not return answers. So it seems better to try to change the Prolog interpreter to deal with the problem (4). It turns out that this change is also needed for explaining 'no' answers, as described below.

As has been pointed out in (6), a Prolog interpreter in Prolog can be written as four clauses, one of which has the form

demo( G) <- rule(G<-B) & demo( B).

Prolog/ Ex1 keeps a record of the rules which it has used to arrive at its current point in the computation. The clause · above is replaced by clauses which test a rule before it is applied. A rule is only used if it has not already been used, or if it is a special case of a rule which has been used. Experimentally, this appears to assign the same procedural meaning to existing programs as does a standard interpreter, but it also assigns the expected meaning to a large number of programs (such as Example 1) which do not normally terminate.

Ill EXPLAINING YES AND NO ANSWERS

To explain a yes answer, a Prolog interpreter in Prolog can be adapted to accumulate a proof tree during execution, by adding one argument to the 'demo' predicate. The proof tree (or part of it) can then be used as an explanation (14) .

Now consider the question 'can one fly from lhr to lax ?' . Based on Example 2, the answer is no, as there are no flights out of lhr at all. Unfortunately, an interpreter which gathers explanations in the manner just outlined yields no explanation of this. The computation simply fails, so some other approach is needed.

To explain both yes and no answers , Prolog/ Ex1 proceeds as follows. First, it checks to see if the answer is yes, using the approach just outlined. If there is no proof, then, instead of failing, it proceeds to explore possible partial pr·oofs in which certain steps are assumed to succeed (even though in fact they fail). These s teps are marked as conditional, and are printed with a question mark in an explanation tree , to indi cate where the failur-es occur. Assuming that a failing goal has succeeded potentially opens up an unbounded computation. Hence the technique d escribed in Section II is used to limit the computation .

In finding explanations , Prolog/ Ex1 follows several guidelines about what kind of explanation is likely to be a help . For a yes answer, it finds a shortest explanation. For a no answer, it finds a conditional explanation in which the first assumption is as deep as pos s ible. Also, for a no answer, if there is a constant in the question, it makes sure that the con s tant is in the knowledge base and is reachable from the question ; otherwise it generalizes the question by changing all other constants to distinct variables .

To see how this works , consider the behavior of Example 2 when inter·preted by Prolog/ Ex1.

If we ask to fly from jfk to lax, we get

fly(jfk, lax) flight(jfk,bos) fly(bos, lax) flight(bos , sfo) fly(sfo, lax) flight(sfo, lax)

This can be read as explaining that we can fly from jfk to lax because: there is a flight from jfk to bos and we can fly from bos to lax, and so on. Note that this is the shorter of two possible proofs. The tree can be used to synthesize an explanation in English as in the work of Weiner (15), or can be directly mapped into quasi-English as in the SYLLOG system (12).

If we ask to fly from sfo to lhr , we get

fly(sfo, lhr) flight(sfo, lax) fly(lax,lhr) flight(lax, ? fly( , lhr) ?

which says that this would be possible, except that there are no flights out of there is no sequence of flights into !hr. to fly from lh r to lax, we get via lax, lax, and If we ask

fly(lhr, lax) flight(lhr, ? fly(sfo, lax) flight(sfo,lax)

indicating that there are no flights out of !hr . (14) gives the behavior of Prolog/ Ex1 on a knowledge base which is more realistic than Example 2 .

Th e combined techniques of section II and of this section lead to behavior that is reasonably helpful. This behavior is built in to the Prolog/Ex1 interpreter, so it is available to al l knowledge bases without extra effort on the part of the people who wr·ite the rules.

IV CONCLUSIONS

When a knowledge base answers a ques tion , its rules ar·e combined by patter·n matching, in ways that the writers of the rules may not have fores een in detail. So, both for th e people who prov ide the rules and for other users, it is important that the knowledge base be ab le t o explain the reasoning th at leads to its results, i.e. that it be able to provide some information about what instances of what rules have been used.

• If a knowledge base answers yes t o a quest ion under a standa rd interpreter, then an explanation can be produced ei t her by a compi led method (13), or by an interpreter modified to accumulate a proof tree. Howeve r , there are declaratively r·easonable programs which have no procedural meaning in s t anda rd Prolog, that is, certa in questions do not yield answers.

If , in standard Prolog, the answer to a question is no, then the answer is the result of a failure to find a proof of a yes answer. All of the rule matches made during the attempted pr·oof are d iscar·ded, and no explanatory information remains .

This paper has described Prolog/ Ex1, an inference engine which assigns a procedural meaning to many programs which do not produce an answer in standard Prolog. Prolog/Ex1 provides ex planations of both yes and no answers. A 'no' ex planation either indicat es that some object is mi ss ing from the knowledge base, or that while the necessary objects are present, some relationship between them is mi ssing.

Prolog/ Ex1 al lows one to write purely declaratively in many cases in which standa rd Prolog does not, and it provides exp lanations of both yes and no answers. When there are several expl ana tions for an answer , one which is likely to be useful is chosen.

V ACKNOWLEDGEMENTS

It is a pleasure to acknowledge that this work has benefited from conversations with Chin Chang, Se June Hong , Antonio Porto, David H. D. Warren , and Walter Wilson .