PRACTICAL EXERCISE: A SIMPLE EXPERT SYSTEM SHELL, WRITTEN IN PROLOG Peter Ross 1. INTRODUCTION This describes how to use a simple expert system shell, and gives a number of exercises based on it. The shell is modelled loosely on Teknowledge's KS-300 (and so is called ks299, since it's not quite the full shilling). The shell can be found in UNIX: /u4/peter/prolog/ks299/int EMAS: ECMI01.KS299_INT Neither version needs any external utilities. A sample knowledge base can be found in UNIX: /u4/peter/prolog/ks299/wine EMAS: ECMI01.KS299_WINE To load them, start up Prolog, load the files (load the shell first), and then ?- find wine. Answer the questions. Read on to find out what other possibilities there are. 2. CONSTRUCTING A KNOWLEDGE BASE The knowledge base is made up of rules of the general form RULE: if PREMISE then CONCLUSION. where [1] RULE is a Prolog atom (such as 'rule391'), [2] PREMISE is either [2.1] a simple proposition of the form THING = VALUE or THING is known or THING is unknown [2.2] a combination of simple propositions built up using 'and' and 'or', where 'or' binds more tightly than 'and' [3] CONCLUSION is either [3.1] a simple conclusion of the form THING = VALUE or THING = VALUE cf CONFIDENCE [3.2] a combination of simple conclusions built up using 'and' only. THING and VALUE can be any Prolog terms of precedence less than 600. They can be atoms, such as 'colour' or 'red', or they can be Prolog variables (the scope of such a variable being the rule within which it appears), or they can be compound terms. A Prolog operator 'of', with precedence 599 and associativity defined so that 'A of B of C' is regarded as 'A of (B of C)', has already been declared for convenience. This means that THING can take the very handy form 'ATTRIBUTE of OBJECT'. CONFIDENCE must be a number between 0 and 1000 inclusive (on EMAS it must be an integer); it expresses the degree of belief in the conclusion. A CONFIDENCE of 0 means "no confidence at all", and a CONFIDENCE of 1000 means "completely sure". The way in which the system manipulates these confidence factors is explained below. Here are some examples of rules (do not forget the full stop at the end of each rule): whizzo: if today=tuesday then shops_open=no. rule002: if age is unknown and texture of skin = wrinkled then estimated_age = old cf 600. x: if spiral_bound = yes and colour of cover = grey or colour of cover = red then type of document = departmental_paper cf 770 and type of document = private_paper cf 400 and source of document = dept_of_AI cf 910. You must also tell the system which of those THINGs that appear in the PREMISE parts of the rules it is allowed to ask the user about. To do this you must provide assertions of the form QUESTION finds THING. where QUESTION is a question (but without the final question mark), in the form of a Prolog atom. This usually takes the form of a string delimited by single quotes. The commonest mistake is to include an apostrophe, alias single quote, as part of the string. You can do so provided you double it. For example, 'What is the colour of the cover (red/grey/other)' finds colour of cover. 'What is the patient''s age (old/young/middling)' finds age. Note the doubled apostrophe in the second example. 3. HOW IT WORKS The system works by backward chaining. When asked to 'find THING' it looks for rules that conclude about the VALUE of THING and attempts to establish the PREMISE of each such rule by a depth-first recursive application of the rules. It looks at all the non-recursive rules first, taking those that conclude about the VALUE of THING in their order of appearance. Thereafter, it looks at all the recursive rules that conclude about the VALUE of THING. A recursive rule is one in which some THING is referred to both in the PREMISE and in the CONCLUSION. It looks at non-recursive rules first in the hope of establishing something about the THING in question, so that an attempt to use a recursive rule in due course will not trigger a recursive use of the rule. If the system is seeking the VALUE(s) of a THING, and finds that it is allowed to ask the user, then it will ask the user immediately and will never try to use any rule to establish the VALUE(s). If it is not allowed to ask the user it will use the rules in an attempt to find the VALUE(s). A premise of the form 'THING is known' will be satisfied if the system already knows or can deduce or can ask the VALUE(s) of thing. A premise of the form 'THING is unknown' will only be satisfied if the system knows no VALUE, cannot deduce one and cannot ask one. Either of these types of premise will trigger an attempt to find the VALUE(s). Thus 'THING is unknown' will always fail to hold if the user can be asked about it; this type of premise does not mean "THING is currently unknown", it means "THING is unknowable". The system uses the confidence factors in the following way. Given a rule, it determines the confidence factor of the premise of the rule. This is taken to be the confidence factor of each of the conclusions, possibly modified by any confidence factor specified in the conclusion. An example shows how this is worked out. Suppose that the system is looking at the rule rule71: if A then B cf b and C. It works out the cf of A. Suppose it is a. It takes this to be the cf of C, since C appears without any qualifying confidence factor. It also records B, but with a modified cf of a + b - a*b/1000. This odd expression is really 1000*(1 - (1-a/1000)*(1-b/1000)) - if you consider a and b to be probabilities scaled up to lie between 0 and 1000, then this is just the rescaled probability of the disjunction of A and B on the (wholly unreasonable) assumption that they are independent. This dreadful theoretical flaw is nevertheless used because it is simple and it works, provided that the depth of search through the rules is not too great. In attempting to determine a conjunction ('A and B') of premises, the system will work through them left to right. The confidence factor of a conjunction is taken to be the minimum of the confidence factors of the individual parts. In working left to right, however, the system will give up on the whole conjunction as soon as it finds that the confidence factor of the conjunction so far has fallen below 200. For instance, if it is trying to establish 'colour=green and weight=heavy' it will start trying to determine the colour. If it cannot establish that 'colour=green' with a confidence factor of at least 200, it will not go on to trying to determine the weight. In attemtping to determine a disjunction ('A or B') of premises, the system will work through them left to right. The confidence factor of a disjunction is taken to be the maximum of the confidence factors of the individual parts. In working left to right, however, the system will stop as soon as it has done enough to establish that the disjunction will have a confidence factor of 1000. The system assumes that anything it is told by the user has a confidence factor of 1000. One consequence of this is that if it is trying to establish a premise such as 'colour=green or smell=rotten', and the colour can be asked of the user, and the user says it is green, then the system will know that 'colour=green' with confidence factor 1000 and so will not go on immediately to investigate the smell. 4. USER INPUT When the system asks a question, it types it out, followed by a question mark and then a prompt ==>> on a new line. You can answer the question. Your answer must end with a full stop; the system expects your answer to be a valid Prolog term. It is a good idea to include a hint about what the expected answers are in the question (as in the examples above). Instead of answering the question, your reply can be one of: [1] help. to get a short text summarising the other possible responses [2] show THING. to get an account of what the system knows about THING so far. The information is given as a set of assertions of the form THING=VALUE cf CONFIDENCE because LIST_OF_REASONS or THING is unknown [3] show RULE. to have the system print out that rule for you [4] why. to get a short account of why the system is asking you that question, or [5] :- COMMAND. where COMMAND is any Prolog command at all, which will then be run. 5. UTILITIES A Prolog predicate tidy(OldFile,NewFile) is provided. It reads the knowledge base in OldFile and prints it out beautifully into NewFile in a standard format. All the RULE tags get changed into tags of the form 'ruleN' where N is a number counting upward from 1. OldFile and NewFile must be different file names; if not, you will get a message of complaint. Two Prolog predicates are provided to permit you to obtain a simple trace of the operation of the system. The command watch. switches the interpreter's tracing on. The tracing messages are of the form ****** Invoking RULE or +++ added THING=VALUE cf CONFIDENCE because LIST_OF_REASONS or --- deleted THING=VALUE cf CONFIDENCE because LIST_OF_REASONS In general there will be quite a lot of these additions and deletions, because the interpreter modifies its belief about 'THING=VALUE' by a process of deletion followed by addition of the new modified belief. The system does not explicitly tell you if the invocation of a rule was successful. If it was, of course, then you would see the conclusion(s) being added. The command nowatch. turns the interpreter's tracing off. 6. EXPERT SYSTEMS EXERCISES In this order: {a} Make up a simple knowledge base and try it. {b} Show that a recursive rule can trigger a recursive use of the rule (N.B. on UNIX you can interrupt by typing ctrl-C; on EMAS you can interrupt by typing ESC then A). {c} Can the order of the rules affect the final result? Produce an example to show that it can, or try to justify the claim that it cannot. Try to create a knowledge base that you could use to demonstrate that the system's use of confidence factors is unsound. It may help to make use of recursive rules (see the article "Inside an expert system" by Jadzia Cendrowska and Max Bramer, in 'Artificial Intelligence: Tools Techniques and Applications', eds. Tim O'Shea and Marc Eisenstadt, pub. Harper and Row). {d} Make up an elaborate knowledge base. In use, would the sequence of questions make sense to a user who knew nothing of the subject matter? Could you improve matters by judicious choice of the THINGs that the system tries to investigate? {e} What are the deficiencies of the system in use? {f} Design useful features to add to the system. Justify your choices. If they involve extensions to the syntax of the rules, design those extensions. 7. PROLOG EXERCISES Not necessarily in this order: {g} Explain how the code works. {h} It would be nice if the interpreter knew what the valid replies to a question could be, and checked a user's reply accordingly. Make changes in the interpreter and in the syntax of knowledge bases to do this. Test them. {i} It would be nice if the user were allowed to qualify the information he gives in reply to a question with a suitable confidence factor. The system should still assume a confidence of 1000 if the user does not give such a factor. Implement this change. Test it. {j} The system cannot make decent use of values which are numbers. For example, you cannot give a rule of the form ... if age > 40 and age < 65 then ... Design and implement suitable changes. Test them {k} It would be useful to allow premises which involved negation in some way, e.g. ... if colour is not green ... Designing this requires a bit of thought. Some things can only have one value (for example, if you know that a colour is red, then you know that it isn't green), but some things can have more than one value (for example, if a person has Canadian nationality, then you cannot deduce that he does not have British nationality too). Design and implement suitable changes. Test them. {l} Extend the interpreter and the syntax of knowledge bases to allow the system to do some forward chaining whenever the user replies to a question. Give an example or two to show that this can mean that the system asks fewer questions. {m} Extend the interpreter and the syntax of knowledge bases to allow for the provision of explanatory texts, so that a usr can reply 'explain.' to a question. Test it. {n} Extend the interpreter and the syntax of knowledge bases so that an arbitrary Prolog command (e.g. (write(X),nl)) can be included in the conclusion of a rule. Test it. {o} Make any other desirable improvements you can think of, such as wonderful natural language features allowing the user some flexibility in the format of his replies to questions. Test them.