Backward Chaining in Rule-Based Expert Systems

Backward Chaining in Rule-Based Expert Systems

A common method for building expert systems is to use a rule-based system with backward chaining. Typically, a user enters a set of facts into the system, and the system tries to see if it can prove any of the possible hypotheses using these facts.

In some cases, it will need additional facts, in which case the expert system will often ask the user questions, to ascertain facts that could enable further rules to fire.

The algorithm is applied as follows:

To prove a conclusion, we must prove a set of hypotheses, one of which is the conclusion. For each hypothesis, H:

If H is in the facts database, it is proved.

Otherwise, if H can be determined by asking a question, then enter

the user’s answer in the facts database. Hence, it can be determined

whether H is true or false, according to the user’s answer.

Otherwise, find a rule whose conclusion is H. Now apply this algorithm

to try to prove this rule’s antecedents.

If none of the above applies, we have failed to prove H.

Typically, backward chaining is used in combination with forward chaining. Whenever a new fact is added to the database, forward chaining is applied to see if any further facts can be derived.

Backward chaining is then used to try to prove each possible hypothesis.

Let us imagine a simple medical expert system that is designed to diagnose and treat patients’ diseases. The rules might be as follows:

Rule 1: If headache then prescribe painkiller

Rule 2: If headache and sore throat and coughing then diagnose flu

Rule 3: If tired and headache then diagnose glandular fever

Rule 4: If tired and sore throat then diagnose tonsillitis

Rule 5: If tired then diagnose stress

Now we might imagine a session between the user (the patient) and the expert system as follows:

Patient: I have a headache

System: I suggest you take a painkiller. Do you have a sore throat?

Patient: Yes, I do.

System: Have you been coughing?

Patient: No, why do you ask?

System: If you had a headache and a sore throat and had been

coughing, I would have concluded you might have flu. It

doesn’t sound as though you have flu. Have you been feeling

tired recently?

Patient: Yes, I have.

System: It sounds as though you may have glandular fever or tonsillitis.

This was a rather simplistic example, but it illustrates the way that the system uses forward chaining to derive new facts and asks questions in order to carry out its backward chaining analysis.

For example, having been told that the patient has a headache, the system first applies forward chaining with Rule 1 and, as a result, adds “prescribe painkiller” to its database of facts.

This fact has an action, or a recommendation, associated with it, and so the system advises the patient that she should take a painkiller.

Next, the system tries to see if it can prove any other hypotheses. The possible hypotheses are flu, tonsillitis, glandular fever, and stress. First, the system uses backward chaining to try to prove the hypothesis that the patient has the flu.

To prove this hypothesis, the antecedents of Rule 2 must be proved: that the patient has a headache and a sore throat and has been coughing. The patient has already said that she has a headache, so this fact is already in the fact database. Next, the system must establish whether the patient has a sore throat. She says that she does, so this fact is added to the fact database. She has not been coughing, though, so the system concludes that she does not have flu.

At this point also note that the patient asks why the system asked the last question. The system is able to use its explanation facility to provide an explanation for why it asked the question and what conclusion it was able to draw from the answer.

Finally, the patient says that she has been feeling tired, and as a result of this fact being added to the database, Rules 3, 4, and 5 are all triggered.

In this case, conflict resolution has been applied in a rather simplistic way, such that Rules 3 and 4 both fire, but 5 does not.

In a real medical expert system, it is likely that further questions would be asked, and more sophisticated rules applied to decide which condition the patient really had.