TEACH JAVAEXPERT Sharon Wood
(xemacs version) August 1999
(modified November 1999)


Contents


This Teachfile

This teachfile describes a simple rule-based expert system. It is intended as a demonstration of rule-based inferencing/reasoning techniques for introductory AI courses, and not as a serious application. The program is written in JAVA, making use of features which might typically be covered in a single term introductory JAVA programming course.


Quick Start

Want to get started quickly? Then run the program package on my demo files.

Open up xemacs on the main class file, as follows:

xemacs /local/javateach/packages/foundai/ES/RunES.java

From here, you can run the demo by clicking on the JDE icon from the xemacs toolbar, and selecting RunApp from the menu.

The program will ask you for a few inputs. To run the demo files, simply press the <return> button on your keyboard in response to each question, and the program will use the default settings.

Of course, you will need to answer the questions posed by the expert system itself with yes/no answers!

If you want more of an explanation, or to find out how to run the program on your own examples/applications, read on... (read the list of CONTENTS above to see what is in this teach file).


Expert Systems

Expert systems are computer programs that carry out reasoning or problem solving tasks in a specific domain of application. Typical examples are systems that perform diagnosis in the domains of medicine or car mechanics; classification of plants, butterflies, etc.; even the design of rooms according to the principles of feng shui! They are called 'expert' systems because, as well as incorporating information about the domain of application, they include additional information about how to do the problem solving task; this information is obtained by asking or observing human experts solving similar tasks.


Why Expertise?

Addressing problems requiring expertise involves addressing the two big issues of artificial intelligence: knowledge representation and search. The search space for a typical expert domain is very large. One of the characteristics of human experts is their efficiency in finding solutions to problems quickly and efficiently with the minimum of false tracks. To become expert in this way usually requires years of practical experience, during which the expert learns to associate characteristics of the problems to be solved with the most appropriate interpretation. These associations comprise the expert's expertise. They enable the expert to go very quickly from a description of the problem to the solution: the diagnosis of a medical ailment based on the symptoms of the patient, for example; or the classification of a plant based on its botanical features, and so on.

By incorporating the expertise of the human expert into a computer program, we can reduce the size of the search space for solving problems. The expertise describes the valid inferences which can be deduced from the known problem features. For example, for an animal classification problem, if an animal has hair we can infer it is a mammal; more importantly (by default) we can ignore all interpretations and solutions which involve the animal being a bird, or anything else, and vice versa. Sometimes this is referred to as 'partitioning' the search space. The search can now focus on a much reduced number of solutions. Similarly, if an animal chews the cud and has hooved feet, the animal may be inferred to be an ungulate and the number of possible solutions is narrowed-down further still. Eventually, the remaining search space may comprise only one solution - the answer! That is usually the case for classifications tasks; however, you should be aware that for some problems there may not be a single answer - patients and cars can have more than one thing wrong with them at any given time, for example, so several answers may apply. Also, the performance of a program is limited by the knowledge of the expert; for example, medical knowledge is notoriously incomplete - new conditions may arise, tests may not be sufficiently refined to differentiate adequately between conditions, and so on.

Of course, we are all very adept at classifying animals, so we hardly think of ourselves as 'expert' at this task (although we are!), but try replacing replacing animal characteristics with the geological features of rock formations, and the valuable role of expertise becomes more apparent.


Expert Rules

We now come to the knowledge representation issue: how is information about the problem, and expertise in how to solve it, to be described so that the program can carry out the problem solving task in a way that best emulates the human expert?

One method is to explicitly link inferences, such as 'is a mammal', with the conditions under which the inference would be valid, for example, 'animal gives milk' or 'animal has hair'. This can be done in the form of 'if...then...' rules, for example;

Rule 1: if..... the animal has hair
then... the animal is a mammal
Rule 2: if..... the animal gives milk
then... the animal is a mammal
Rule 3: if..... the animal has feathers
then... the animal is a bird

The rules state explicitly which valid inferences follow on from what is known about the problem. These inferences provide new information about the problem which can itself be used in making further valid inferences. For example:

Rule 4: if..... the animal is a mammal
and.... the animal chews the cud
then... the animal is an ungulate

This rule has a condition which may be derived from another rule. In this way, the system's reasoning makes use of earlier discoveries until eventually it may be possible to identify the solution. For example,

Rule 5: if..... the animal is an ungulate
and.... the animal is white
and.... the animal has black stripes
then... the animal is a zebra

The conditions of a rule are often referred to jointly at its 'antecedent', and the inferences or actions to be carried out, as its 'consequent'.

Throughout the reasoning process, the system makes use of only those rules whose conditions are satisfied, discarding all others. The association between features of the problem and likely solution explicitly encoded in the rules enables expertise to be applied to the problem solving process. In this way, the expertise 'guides' the search process and, for this reason, expertise is often referred to as 'heuristics' and 'heuristic rules of thumb'.


Knowledge States

If expert reasoning is a problem solving task, then we need to consider the nature of 'states' in the search space. Solution or goal states are clearly states in which problem solving task is complete; the solution is 'known'. Start states are states in which we have a description of the problem, based on some initial observations, but no more: the solution is not known, but some aspects of the problem are. Both of these states, goal states and start states, are 'knowledge' states; in the former we have complete knowledge (ideally) about the problem and, in the latter, partial knowledge. Reasoning about the problem through making inferences adds to this partial knowledge. The search space, therefore, is made up of states of partial knowledge. Each move between states is effected by satisfying the conditions of a rule, drawing its associated inference and so, effectively 'moving' into a new partial knowledge state. Pathways through these states lead to a range of potential solutions.


Rules comprise the expertise in an expert system. To apply this expertise to a specific problem the system goes through a cyclical reasoning process, often called the inference cycle (the program that implements it being the 'inference engine'). It is a simple 3-step process:

(i) identify the set of rules whose conditions are satisfied;
(ii) select one rule from the set;
(iii) carry out the actions of the selected rule.

This process is repeated iteratively until a solution is arrived at, at which point it halts. If a situation arises where no progress can be made with the reasoning task, the process should be abandoned in failure.

Identifying the set of rules whose conditions are satisfied and considering only those effectively partitions the search space and prevents the system from considering unfruitful options in its search for a solution. However, in a single cycle, the system may still be left with several rules whose conditions are satisfied. To make progress with problem solving, the system must choose between them. The localised heuristic knowledge contained in the rules is of no further use here; its role in identifying a given rule as appropriate in the problem solving context is achieved, but it can do no more. We require further techniques to select the best rule to apply or 'fire'.


Conflict Resolution Strategies

The set of rules whose conditions are satisfied is known as the 'conflict set' (for set of conflicting rules); they conflict because they each push the reasoning process in different, presumably conflicting, directions. The process of selecting one rule from this set is known as 'conflict resolution'. There are a variety of techniques or strategies for making this selection. The simplest is to simply chose the first rule whose conditions are found to be satisfied.

This technique assumes that the rules are organised into some kind of data structure, and that discovering whether a rule's conditions are satisfied will involve considering each rule in turn. On each cycle the rules are taken in turn, from first to last, halting as soon as a rule is found whose conditions match the problem. In consequence, some rules may never be looked at. Of course, this technique must be combined with a method to prevent the same rule being selected over and over again, or no progress will be made! At first glance, this strategy seems simple and straghtforward, however, there is a catch - the order of the rules will have a direct bearing on the search process. This is because choosing one rule out of many corresponds to choosing which move to make in finding the solution to a problem. The onus is therefore on the knowledge engineer (programmer) to place the rules in the best possible order for all possible problems...! (This strategy is available in the demonstration program.)

Other strategies for conflict resolution take more account of the problem solving context by being comparative. For example, a rule may be selected because it is the hardest to satisfy compared to the other rules that just happen to be in the conflict set for that specific inference cycle; if, for another problem,if a rule that is yet harder to satisfy should appear in the conflict set, then this technique determines that this more difficult rule would be applied. (This technique requires some criterion of 'difficulty'.)

A variation on the previous technique selects rules with the higher number of conditions to satisfy. Where there is more than one such rule, one may be selected arbitrarily. (This variation is available in the demonstration program.)

An alternative strategy selects rules which make use of the most recently acquired piece of information, perhaps the inference derived in the previous inference cycle. (Again, where there is more than one such rule, one may be selected arbitrarily. This technique is available in the demonstration program.)

Numerical techniques for rule selection are also available. They function on the basis of 'preferring' one rule over another by giving it a higher 'weighting' than the competing rules. The technique simply involves selecting the rule with the highest weighting; however, it also allows for backtracking to a less preferred option at a later stage, if the current line of reasoning results in a deadend. The weightings themselves are based on combining the weightings of the individual conditions in the rule antecedent, along with their significance (again numerical) in drawing the associated inference in the rule conseqent, and require sophisticated numerical reasoning techniques (not described further here, but look in any general AI or expert systems textbook under the headings of 'probabilistic reasoning', 'certainty factors' and 'Bayes theorem').

The role of conflict resolution strategies in the search process corresponds to the generalised heuristic techniques you may have already encountered in other contexts. They are generalised because each 'move' (denoted by each rule) is evaluated according to the same criterion, of antecedent length, etc., as the others. (This contrasts with rule conditions which vary for each rule and are therefore 'localised' heuristics applying to that 'move' only.)

I believe that the appropriateness of specific conflict resolution strategies varies according to the domain of application and problem solving task and that, therefore, the choice of strategy should be an empirical one based on performance criteria. The demonstration program allows the user to select the conflict resolution strategy for each problem.


Reasoning Strategies

There are two basic reasoning strategies for expert systems: forward chaining and backward chaining. Forward chaining generally constitutes a data-driven search, taking whatever information is available about a problem (the data) and attempting to draw inferences and conclusions from it in the inference cycle. Classification systems are well-suited to this approach. Forward chaining is usually the standard reasoning technique implemented in expert systems and is implemented in the demonstration program.

The alternative, backward, chaining constitutes a goal-driven or hypothesis driven search; a potential solution is taken (from a rule consequent) and the evidence required to support it (the conditions in the rule antecedent) are examined and either confirmed or denied, thus confirming or denying the original hypothesis. This technique is sometimes used in medical diagnostic systems because doctors tend to reason in this way: confirming or denying one hypothesis before moving on to another. Backward chaining is not currently implemented in the demonstration program.


Interaction and Explanation

A final feature of expert systems to be discussed is their interactivity with the user and their ability to provide an explanation of how a solution to a problem is arrived at. The latter feature is thought to be crucial to the acceptibility of the solution offered to the user; it also offers a means of evaluating the integrity of the system when it is to be used by the experts themselves. Minimally, explanations consist of the sequence of inferences that were made by the system in arriving at a conclusion. (There are no explanation facilities in the demonstration program; however, see the 'chatty' option.)

In the discussion above, I have referred to the 'problem description'. This description is acquired incrementally by the system from the user. As the system evaluates the conditions of rules, to assess whether they are satisfied or not in deriving the conflict set, it will come across some which it can only confirm by asking the user. For example, "Does the patient have a high temperature?", or, "Does the animal have pointed teeth?". In principle, the user is asked questions that are relevant to the line of enquiry only, rather than every possible question the system could ask; although on very small systems this is hard to demonstrate. Additional features may include explanations of why a question has been asked and additional information on how it should be answered (neither of which are implemented in the demonstration program).


Running the Expert System Demo

The Expert System demonstration program is written in JAVA 1.1. You can access the relevant class files by providing the pathway to the ES package in the foundai directory, when the program is called. To run the program, open a window and type:

xemacs /local/javateach/packages/foundai/ES/RunES.java

then click on the JDE icon in the xemacs toolbar, and select RunApp from the menu.

When the program runs, it expects four inputs which it obtains interactively from the user: (1) the name of a text file containing domain facts for the application domain, (2) a flag stating whether you want minimal 'nochat' output or detailed 'chatty' output, (3) the chaining technique to be used, and (4) the conflict resolution technique to be used.

The animal classification facts in the demonstration program are defined in the accompanying file: zooFacts.txt (see Domain Facts File below for explanation). If you wish to use your own domain facts/rules file, you will need to specify the filename and its location within your own user directory. For example:

~myusername/mydomainfactsfile.txt


Defining your own Domain Facts File

It is easy to write your own facts files so you can run the expert system in the domain of your choice. Just follow the format described below. You can call the files whatever you wish, but a .txt suffix helps identify them in your directory.

Text files get read by the program one line at a time. Each line in the facts file is processed as a new fact instance, so it is important that a complete fact description fits on each line The only exception is the first line, this simply specifies the number of rules (not facts) in the expert system.

The format for a fact description is:

<antecedent numbers> end <consequent numbers> end <property> <value> <prompt> <question text> ?

The format assumes that, prior to constructing this file, you have identified all the rules for your system, involving identifying which facts appear in each rule antecedent and which in each rule consequent. The rules should then be numbered in sequence. For example, in zooFacts.txt, the first rule happens to be:
if..... the animal has hair
then... the animal is a mammal

These rules do not appear explicitly in the text file. Only facts appear in the text file. The fact: has hair will be described as appearing in the antecedent of rule 1, and the fact: isa mammal will be described as appearing in the consequent of rule 1. In this way, rules are described implicitly (and can be constructed internally by the expert system).

The total number of rules appears on the first line of the file. In the demonstration program there are 15 rules.

These are the constraints for fact description:

<antecedent numbers> any amount of numbers in which the fact appears as an antecedent. Each number must be separated by a space. The sequence of numbers must be followed by a space and the word 'end'.

If a fact is a negated condition for any rule, the rule number should be preceded by the word 'neg' followed by a space (and then the number).

<consequent numbers> any amount of numbers in which the fact appears as a consequent. Each number must be separated by a space. The sequence of numbers must be followed by a space and the word 'end'.

If a fact is also a solution, the consequent number should be followed by a space and then the word 'solution', also followed by a space.

<property> a single word constituting the property described by the fact. This must be followed by a space.

<value> a single word constituting the value of the property described by the fact. This must be followed by a space.

<prompt> a single word used to identify the prompt to be used in asking the user questions. The demonstration program asks questions only requiring 'yes' or 'no' answers. This field is omitted for facts whose confirmation does not involve asking a question of the user.

<question text> any number of words which are to be used verbatim in asking the user a question. This must be followed by a space and a question mark. This field is omitted for facts whose confirmation does not involve asking a question of the user.

For example, here are some facts defined in zooFact.txt

15
1 end end has hair yesno Does the animal have hair ?
3 end end has feathers yesno Does the animal have feathers ?
4 neg 13 neg 14 15 end end can fly yesno Can the animal fly ?
5 6 7 8 end 1 2 end isa mammal
13 14 15 end 3 4 end isa bird end 14 solution end isa ostrich

The first line gives the total number of rules: 15 in total. Then appear the facts. The first fact is: has hair. It appears only in the antecedent of rule 1 and does not appear in the consequents of any other rules. The fact can be confirmed or denied by asking the user. The user should be prompted to answer with a 'yes' or 'no', and the text to be asked is "Does the animal have hair ?".

The next fact: has feathers appears only in the antecedent of rule 3. The following fact: can fly appears in the antecedent of rule 4 and as a negative condition in the antecedent of rules 13 and 14 (that is, the condition is satisfied only if the fact is not confirmed). As you can see, the fact: isa ostrich is the consequent of rule 14, and ostriches cannot fly!

The fact: isa mammal appears in the antecedents of rules 5, 6, 7 and 8, and in the consequents of rules 1 and 2, so we can see it is a consequent of the fact: has hair. Similary, the fact: isa bird appears in the antecedents of rules 13, 14 (the ostrich!) and 15, and in the consequents of rules 3 and 4, and again we can see it is a consequent of the fact: has feathers.

See the whole zooFacts.txt file to get a complete picture of all the facts. The rules are specified indirectly through the facts, but you should begin to see the patterns, as in the examples shown above.

A fact file is all you need to implement your own application domain. The program is also written in such a way that, as you become more competent with java, you can copy and modify the code files to implement your own conflict resolution strategies, implement backward chaining, if you wish (and tell me about it if you manage it!), or simply to ask different question formats.

$poplocal/local/teach/javaexpert
Copyright University of Sussex 1999. All rights reserved.