BACKWARD CHAINING PRODUCTION SYSTEMS ==================================== Introduction ------------ A backward chaining production system consists of (1) a production memory, containing if-then rules, (2) (optional) information about the predicates mentioned in the rules, (3) an inference engine, and (4) (optional) other data structures used to support justification of conclusions. Details of backward chaining systems often vary considerably, and range from Prolog interpreters to EMYCIN-based systems. ---------- Production Memory ----------------- PM consists of rules of the form IF condition THEN conclusion with the condition having the same syntax as that of rules in forward chaining systems. The conclusion of a rule is an atomic formula. ---------- Each predicate mentioned in the rules normally has several pieces of information associated with it, such as the values its variable may take, whether it may take more than one value simultaneously, whether the value of a variable should be deduced by the system using rules or the user should be asked to supply a value, and what the question should be when the user is asked. Example: temperature: ask user? -- YES multi-valued? -- NO question? -- "What is the patient's temperature?" possible values? -- real number in the range 35.0 to 45.0 ---------- Inference Engine ---------------- A backward chaining system is invoked by a command such as prove(goal, rules) where prove is a recursive function, goal is an atomic formula, and rules are the rules that may be tried when attempting to prove goal. If goal contains variables, the system returns the values of these variables if the proof is successful. When prove is called, rules are searched until one is found whose conclusion unifies with goal. There are two cases: (1) No such rule is found. (a) If the goal is askable, the system asks the user whether the goal is true or not, and, if there are any unbound variables in goal, to supply values for them. Whether the goal is proven or not depends on the user's response. (b) If the goal is not askable, then its proof fails. (2) A rule is found. In this case, values are substituted for the variables in the conditions of the rule, using the substitution list provided by unifying the goal with the rule's conclusion. Prove is then called recursively on all of the conditions of the rule. The proof succeeds if all of the conditions of the rule have been successfully proven, and fails otherwise. (a) If all of the conditions are proven, then the goal has been proven. (b) If at least one condition was proven false, then prove is restarted with the same goal, but will only try those rules which follow the rule which was tried and failed. ---------- Justification ------------- It is normally the case that backward chaining systems are able to some extent to justify their reasoning (an exception is Prolog interpreters). This means that they are able to explain how they arrived at a conclusion, or why they are asking a particular question, or what they have already deduced. The user, then, may, instead of answering a question posed by the system, type one of the following (the exact details of the user interface do not concern us here): (1) HOW conclusion? -- i.e., how did you prove conclusion? In this case, the system determines whether the conclusion has actually been deduced. If so, it displays the rule it used to deduce the conclusion. (2) WHY? -- i.e., why did you ask me that question? In this case, the system responds by displaying the rule it is currently using. The question asked relates to a particular predicate which is contained in the condition of the rule. (3) WHAT? -- i.e. what have you already deduced, or what do you already know? In this case, the system responds by displaying a list of all the conclusions it has made so far. In order to incorporate justification into a backward chaining production system, it is necessary to add at least two data structures. HOW and WHAT use the same data structure, a list of conclusions. Stored along with each conclusion is the rule the system used to prove it (unless the user was asked). WHY requires that the system stores the rule whose conditions it is currently pursuing; this might need to be passed as another parameter to prove. ---------- WHICH WAY TO CHAIN? =================== A decision tree for choosing direction is given. start | +-----------------+--------------------+ | | input from user input from instrumentation | | +--------+-------+ +------------+------------+ | | | | data data readings change readings change requested volunteered rapidly with time insignificantly by system by user | with time | | | | | USE FORWARD CHAINING | | | +--------------------------+---------------------------------+ | +--------------+--------------+ | | many solutions or few solutions and unexpected solutions all predictable | | USE FORWARD CHAINING USE BACKWARD CHAINING Exercise -------- (1) Convert the decision tree into a production system. (2) Should forward or backward chaining be used for deciding which direction of chaining should be used? (3) Explain why the choices were made, in terms of the different syntaxes and control structures of forward and backward chaining systems. ---------- Example ------- (1) body-segmented(X) ^ exoskeleton(X) ^ number-of-legs(X, 6) -> class(X, insects) (2) class(X, insects) ^ winged(X) ^ number-of-wings(X, 2) ^ halteres(X) -> order(X, flies) (3) class(X, insects) ^ winged(X) ^ has-wings-covered-with(X, scales) -> order(X, moths) (4) order(X, moths) ^ ~ has-frenulum(X) ^ has-antennae(X, clubbed) -> superfamily(X, butterflies) (5) superfamily(X, butterflies) ^ wing-colour(X, copper) -> family(X, lycaenidae) Supposing we wish to determine the family to which an animal belongs. We type family(foo, X) This matches with the conclusion of rule (5), and so its conditions superfamily(butterflies) wing-colour(copper) are set up as subgoals.