Inference Engines: Forward and Backward Chaining

facts: dry, enclosed, smoky
rules:
  R1  IF smoky                  THEN fiery
  R2  IF fiery and enclosed     THEN hot
  R3  IF hot and dry            THEN fire-risk
  R4  IF wet                    THEN not-dry

FORWARD chaining: derive everything derivable
  R1 fires: smoky so fiery
  R2 fires: fiery and enclosed so hot
  R3 fires: hot and dry so fire-risk
  derived: fiery, fire-risk, hot

BACKWARD chaining: prove one goal, fire-risk
  goal fire-risk: try R3, which needs hot and dry
    goal hot: try R2, which needs fiery and enclosed
      goal fiery: try R1, which needs smoky
        goal smoky is a known fact
      goal fiery: established by R1
      goal enclosed is a known fact
    goal hot: established by R2
    goal dry is a known fact
  goal fire-risk: established by R3
  result: established

BACKWARD chaining on a goal that fails: not-dry
  goal not-dry: try R4, which needs wet
    goal wet: no rule concludes it, and it is not a fact
  goal not-dry: R4 did not establish it
  result: not established

how much work each does
  forward  fired 3 rule(s) and derived 3 new fact(s)
  backward took 9 step(s) to prove one goal

Reading the two traces

Forward chaining fired three rules and derived three facts. It did not fire R4, because its condition was never satisfied. It stopped when a whole pass added nothing.

Backward chaining took nine steps to establish one goal. It went down from fire-risk to hot to fiery to smoky, hit a known fact, and came back up. The indentation is the structure of the proof, and reading it upward gives the derivation in the order a person would present it.

And the failing goal is the useful one. Asking for not-dry finds R4, needs wet, finds no rule concluding wet and no such fact, and reports failure with the reason. An engine that says only "no" is unusable; one that says which subgoal it could not establish is a diagnostic tool.

Which direction to choose

The rule of thumb is about the ratio of facts to conclusions.

Choose forward chaining when the facts arrive and you want to know what they imply. A monitoring system receives events and must decide whether to alert. It has no goal in advance.

Choose backward chaining when there is a question. A diagnostic system is asked "is it the disk?" and should not derive everything derivable about the machine first.

And notice what the traces show about cost. Forward chaining derived three facts, all of which happened to be wanted. Add fifty rules whose conclusions nobody asked about and forward chaining derives all fifty; backward chaining touches none of them.

The Nyāya connection, stated exactly

Backward chaining is the shape of a Nyāya argument. You have a claim, you look for a vyāpti that would establish it, and you check whether the subject satisfies the vyāpti's condition. Goal, rule, subgoal.

And the trace is the five-member form, upside down. Read the backward trace from the innermost line outward and you get: this is smoky, whatever is smoky is fiery, so this is fiery, and so on up. [Nyāya Logic as an Inference Engine] builds an engine that emits exactly that, in the five members.

Forward chaining has no classical counterpart in Nyāya, because Nyāya is about establishing a claim somebody has made, not about generating claims. The nearest thing is Charaka's diagnostic procedure, which gathers evidence before forming a hypothesis, and even that is not the same.

Conflict resolution, and the connection to Module I

When two rules could fire at once a forward-chaining engine must choose. The classical strategies are these.

Specificity. Fire the rule with more conditions, that is, the more specific one. That is apavāda, from [Rule Precedence: The Four Principles].

Recency. Fire the rule whose triggering facts were added most recently.

Order. Fire the rule that appears first, or last, in the rule base. That is paratva, sūtra 1.4.2.

Refraction. Do not fire the same rule on the same facts twice, which is what the if conclusion in known: continue line in the listing achieves, and it is what stops the loop.

Two of the four strategies are Pāṇini's, and an answer that says so has made a real cross-module connection.

What an inference engine is NOT

It is not a theorem prover. It applies rules; it does not search for proofs in a logic with quantifiers, and the rules here have no variables at all.

It is not guaranteed to terminate. This one does, because refraction prevents a rule firing twice on the same facts and the set of derivable facts is finite. A rule base that can generate new terms need not terminate.

It does not handle uncertainty. Every fact is present or absent and every rule fires or does not. Real expert systems attach certainty factors, and [Expert Systems, and MYCIN as the Comparison] records what that cost.

It does not decide what the rules should be. Getting the rules out of an expert's head is knowledge acquisition, and it is the hard part.

Quick revision

• Three parts: working memory, rule base, control strategy.
• Forward chaining: from facts, derive everything, stop when a pass adds nothing. Good for monitoring.
• Backward chaining: from a goal, find rules concluding it, recurse on their conditions. Good for diagnosis.
• The backward trace, read outward, is a proof; a failing goal should report which subgoal failed.
• Conflict resolution strategies: specificity, recency, order, refraction. Specificity is apavāda and order is paratva.
• Refraction is what prevents the loop.
• Not a theorem prover, not guaranteed to terminate in general, and no notion of uncertainty.

Test yourself

1. Distinguish forward from backward chaining by what each starts from and what each derives.

Forward chaining starts from the facts and derives everything derivable, stopping when a whole pass adds nothing. Backward chaining starts from a goal and derives only what that goal needs, stopping when the goal is established or the possibilities are exhausted.

2. Which would you use for an alerting system, and which for a diagnostic tool?

Forward chaining for alerting, because events arrive and there is no goal in advance. Backward chaining for diagnosis, because there is a question and deriving everything about the system first would be wasteful.

3. Why must a failing backward-chaining query report more than "no"?

Because the useful information is which subgoal could not be established. An engine that reports only failure gives a user nothing to act on; one that names the missing fact or the missing rule is a diagnostic tool.

4. Name two conflict resolution strategies that correspond to Pāṇini's precedence principles.

Specificity, firing the rule with the narrower conditions, corresponds to apavāda. Rule order, firing by position in the rule base, corresponds to paratva, sūtra 1.4.2.