Saturday, October 4, 2008

Full Opportunistic Backward Chaining Rulebased Systems

Greetings:

In this blog I will try to dispel the myth you can do Full Opportunistic Backward Chaining (FOBC) with a Forward Chaining (FC) rulebased system without making significant changes to the FC system. Actually, you can do backward chaining with a forward chaining system - BUT it would take a drastic re-write of all of the FC logic to achieve this and even then probably it would not work properly. So, what do you call it when you want to do backward chaining (BC) with a FC engine? Most of those in this field call it Goal-Driven FC - a misnomer if ever there was one. Which is another good reason to drop the explanation of a Backward Chaining system as "goal-driven" and the Forward Chaining system as "data-driven." A BC engine is or can be just as data-driven as a FC engine.

Before discussing chaining, we have to discuss Conflict Resolution - CR. All forward-chaining rulebased systems have some kind of method that will determine which rule to fire if there are more than one rule wherein all of the condition elements are true. This CR varies from vendor to vendor but, for the most part, they all seem to have recency (whether MEA or LEX or something else) as the first or second element in the CR algorithm. Usually this means for any given set of rules, they are resolved in the following order:

1. Refraction
2. Priority
3. Recency
4. Specificity
5. Arbitrary

OPSJ, a Java version of other systems developed by PST (Dr. Forgy) uses a slightly different variation on this where recency takes a higher order than

1. Refraction
2. Rule Class
3. Recency
4. Priority
5. Specificity
6. Arbitrary

At one time, most vendors posted (documented) their CR Strategy but not many do any more. In Jess and CLIPS you can (or used to be able to) set whatever CRS you wanted - usually depth was sufficient for most applications.

First, for the uninitiated, let's discuss a Forward Chaining (FC) engine. In the normal FC engine all of the data are loaded into objects (either embedded or external to the engine itself) and the rules are instantiated, initialized, started, whatever you want to call it. The rules will interact with the data in a non-monotonic manner until there are no more rules left to "fire" - meaning, to execute the "then" part of the "IF - THEN" rule. This is normal FC and what has come to be called "data-driven" rulebase, which is a misnomer because all rulebased systems use data to drive the rules one way or the other.

Now, what if we use a Goal-Driven approach with a FC? In that case (what is normally done today) the first condition element (CE) of a rule would be something like "if the goal.name == (goalName) " and, due the the recency factor or the CR discussed above and elsewhere, then rules would be "clustered" into those that have the same goal name when a new goal is asserted by any rule. The "goalName" could be a String, Integer, whatever you like. This is NOT backward chaining - this is simply clumping rules together much in the same manner that you might run a sub-routine in C/C++ program. It is the same effect as using a "focus" command in CLIPS or Jess. If this were C++ or Java it would be leaving the main chain of thought to run a sub-routine that might or might not return some value but would operate on whatever objects it needed. Nothing fancy here; Goal-Driven is nothing more than regular old rulebase logic with a first CE that would follow the goal.

Now, on to true Full Opportunistic Backward Chaining: The first thing is that the objects themselves must support this by being able to report to a calling routine whether the value of the slots (attributes) are known, unknown, not known, true / false / value. If a slot is known, then the object returns the value of that slot. But now we have two more wrinkles in the system in that of "not-known" - meaning that we do not know the value and we have not tried to find the value - and "unknown" - meaning that we have tried to find the value and we could not find the value. (Sometimes these are reversed in meaning but, regardless, you should get the idea.) I have always used the rule, "unknown and unknowable" to mean that we cannot find the value. If it were the other kind of state system, then I would use "not-known and never-knowable."

Here is where the wicket gets a bit sticky: If the value is not-known, then there must be some mechanism that will allow the rulebase to try and find the value. This is normally done via question handlers that will either ask the user to enter a value or go back to the database for an answer. If the answer can not be found, then the status of the slot (and the object) is changed to unknown. If this is an AND, NAND, XOR, NXOR gate, it forces the whole object to become unknown. If the object is an OR or NOR gate then other slots have to be checked until all return unknown and then the entire object is unknown.

The bottom line here is that the engine itself must generate the goals to find the value (and state) of the slots, not the programmer. This CAN be done with a forward chaining engine IF and ONLY IF the engine is programmed to do this. Haley (at one time) said that the Haley Expert Rules engine did this for you and OPSJ at one time did this for you. I'm not sure that either does it any longer since it does tend so slow things down if you don't need this.

Why would you need FOBC? Mostly for problems involving diagnostics (medical, instrumentation, processing plants, etc.) or configuration (manufacturing, computers, etc.) where you need to find all of the possibilities for your system. As you can see, this gets to be quite complex with many objects but if answer can be found with just a few backward chains, then the result would be much faster than using a FC rulebase or a "Goal-Oriented" FC rulebase.

SDG
jco

9 comments:

woolfel said...

the challenge I see with FOBC in a business application situation is it's very hard to use. developers have a hard enough time understanding forward chaining. Once we get into strong negation, weak negation, unknown and not known, most people have a very hard time. I've been studying this stuff since 2000 and even I have a hard time.

every time I have to give an example and explain the differences, I struggle.

there are cases where I fell FOBC would be useful like data mining, and machine learning, but implementing it properly is far from trivial.

James Owen said...

The FOBC approach was used with the Neuron Data Nexpert (later the Expert) system for a long time - but maybe it was the GUI that made it so flexible and easy to use. Also, the program ran on 26 different platforms including VAX, mainframes, PCs, and Macs. It took over 6MB to load up just the system so until the mid-to-late 90's it could run only on servers that had lots (meaning 16MB or so) of memory.

If you can make it to October Rules Fest that is one of the topics that we will be discussing on Friday afternoon.

SDG
jco

woolfel said...

I have no plans to attend ORF. Too bad Neuron Data no longer exists and the tools are gone. It would be nice to study how Neuron data did it and try to glean lessons from it.

If only FI could be persuaded to contribute that software to open source. oh well.

James Owen said...

Peter:

Actually Nexpert / Expert is still available from Fair Isaac and, from what I was told a year or two ago, is available with source code for $25K or maybe a bit more now. I just don't have the extra $25K to toss around and I'm primarily doing Java stuff right now.

Maybe one day we'll learn that nothing worth while is easy and we'll all go back to using good old C/C++, put our logic in a rulebase in that language and deal with J2EE like a black art that affects or infects only web weenies and the like. :-)

SDG
jco

woolfel said...

thanks for the info. FI doesn't even talk about the neuron data stuff. Too bad they don't give it more visibility.

woolfel said...

Hi james,

I just looked on FI website this morning and I don't even see the neuron data stuff listed. did they change the name to something else?

Karl Reinsch said...

That's interesting that the tool is still available.

I'm guessing that the "with source code" means it is unsupported, but that rights to distribute derivative works are not being granted?

James Owen said...

Greetings:

Like I said originally - I "heard" that the old Neuron Data FOBC Nexpert / Expert was available. Please contact your Fair Isaac Sales Rep if you wish to purchase. The price that I heard about was also a rumour so you will need to contact them for that as well as any other questions about re-distribution rights, source code, etc.

SDG
jco

Anonymous said...

hello

can you please provide a list of rule engines available with backward chaining support. Most of the systems I have found are primarily intend o support forward chaining such as Jess, Drools.