Friday, September 7, 2012

Backward Chaining

Greetings:

A couple of years ago I blogged on this topic but I see that it still is running rampant across the internet. So, I thinks to myself, thinks I, one more time into the fray.


Backward Chaining (BC) Definitions

Level One BC: Goal Oriented
First Condition Element (CE) contains a goal that, basically, changes the focus of all of that particular rule set.  Until that goal is satisfied then, or no more rules are true that have that Goal as its first CE, then no other Goal can be considered.  Goals are usually inserted in reverse order of order of desired firing because most rulebased systems use a LIFO stack such that the last goal on the stack will be the first one to be considered.

Level Two BC-OoD: Backward Chaining Object On Demand
  • When Needed: This rule is not evaluated until there is a need for the status of this object that is being evaluated in another rule.
  • When Changed: This rule would fire ONLY when the value of the data element changed.
Level Two was/is used extensively in ND Advisor (later FICO Blaze Advisor) as part of the Nexpert additions to Advisor.


Level Three FOBC: Full-Opportunistic Backward Chaining
Condition Elements have the following constraints
  • True
  • False
  • Not Known (NK) – the fact is not known and there has not been an attempt to evaluate
  • Unknown (UK) – the fact is not known.  There has been at least one attempt to evaluate the True or False condition but it has failed.
Level Four BC:  
Level Three BC can be extended such that there could be either a first failure for AND statements as well as a first success in an OR statement or there could be an exhaustive evaluation of that rule or all rules regardless of the nature a predetermined outcome.  This is normally only done when there is a method (function) in one of the condition elements of one or more rules.  This was done in the Neuron Data Nexpert tool and copied in the early versions of Advisor.  The reasoning being that even though the rule did not fire you still wanted the function/method to be evaluated and possibly a value stored somewhere.  Really bad programming that was, nevertheless, used by some major clients.  Really, really bad programming.

Fuzzy Logic (FL) in a rulebase.
The probability of this outcome being true is xx% if all of the CEs are True.

Extended Fuzzy Logic (XFL) – sometimes called the MYCIN Approach
If the CEs all evaluate to True, then there is a certain confidence interval (CI) that the rule is true as well as a certain Doubt Interval (DI) that the rule is still not true because, in the opinion of the expert(s) this rule cannot be 100% verified.  For example, if the CI == 60% True and 20% false then there remains a 20% Space of Doubt (SD) that cannot be accounted for by ordinary means.  The complete description of this is contained in the seminal book on MYCN that dealt with this problem.

In the Level Three FOBC approach, as one leaf of the CE is evaluated and a condition is NK then the elements are evaluated to determine whether it is true or false or UK.  As each leaf is traversed and is marked if a leaf is found False then the rule is no longer evaluated.  If the rule is found UK then the rule is no longer evaluated.  If the CE if found True, the the next CE if evaluated until all of the CEs are evaluated and the rule can be determined to be True or False.

Any questions, comments or corrections would be appreciated.

Shalom
jco

3 comments:

jcaimbridge said...

Are there any free rules engines that support level 3 or level 4 FOBC? I know Drools claims to be a backward chaining engine through queries (not sure if it's full opportunistic, or what level it is), but I never really understood how their usage of queries fit the definition of backward chaining.

Mark Proctor said...

"but I never really understood how their usage of queries fit the definition of backward chaining."

Drools supports the backward chaining approach used in Prolog and Datalog, which are goal based. This approach with it's support for transititive closures proves to be particularly effective when reasoning over graphs of information. It further enhances the traditional prolog query approach with reactiveness.

Mark Proctor said...

"but I never really understood how their usage of queries fit the definition of backward chaining."

Drools supports the backward chaining approach used in Prolog and Datalog, which are goal based. This approach with it's support for transititive closures proves to be particularly effective when reasoning over graphs of information. It further enhances the traditional prolog query approach with reactiveness.