Forward versus Backward Chaining

Dietrich Kappe, Tuesday, April 25, 2006 @ 9:00 am

As if choosing between different BRE vendors wasn't tough enough, there's an added consideration: is the problem you are trying to solve more amenable to a forward or backward chaining approach? Forward chaining, which is the default behavior of most commercial and open-source rule engines, is described as

An inference engine using forward chaining searches the inference rules until it finds one where the If clause is known to be true. When found it can conclude, or infer, the Then clause, resulting in the addition of new information to its dataset.

while backward chaining is described as

An inference engine using backward chaining would search the inference rules until it finds one which has a Then clause that matches a desired goal. If the If
clause of that inference rule is not known to be true, then it is added
to the list of goals (in order for your goal to be confirmed you must
also provide data that confirms this new rule).

So in other words one approach starts with some facts and applies rules to find all possible conclusions, the other starts with the desired conclusion(s) and works backwards to find supporting facts. You can sort of view these approaches as two variations on search, with each step forward or backward forming a tree, either spanning out forwards towards conclusions or spanning out backwards towards initial facts. In point of fact, most rule systems don't go about finding all possible branches in this tree but use some sort of planning or goal setting to guide their search.

What are the advantages of one approach over the other and when would you use each? As it turns out, they can both solve the same problems. Most computer science students have to show at one point in their studies that any backward chaining rule system can be rewritten as an equivalent forward chaining system. Showing the reverse isn't quite so easy, but can be done in a graduate course. So both forward and backward chaining approaches can solve the same problems, but they have somewhat different performance characteristics, and certain problems are much easier to express in one or the other. Charles Forgy put it very succinctly in one of his articles on backward versus forward chaining (sorry, no link. The articles don't appear to be available now that Rulespower has been acquired by Fair Isaac)

You might ask why you would want to use a forward chaining system if you have to write rules to manage subgoals. After all, backward chaining systems automatically manage the subgoals. There answer is very simple: Backward chaining systems are more limited than forward chaining systems. There are many kinds of tasks that can be handled easily with a forward chaining system that are either difficult or impossible with a backward chaining system. Backward chaining systems are good for diagnostic and classification tasks, but they are not good for planning, design, process monitoring, and quite a few other tasks. Forward chaining systems can handle all these tasks.

So, if you already know what you are looking for, e.g. a customer that might be committing fraud, a patient at risk for breast cancer, etc., then backward chaining may be a good solution. On the other hand, if you don't necessarily know the final state of your solution, e.g. improvements to a business process, suggesting next steps in a due diligence investigation, or directing data transformations in an ETL process, then a forward chaining approach my be preferrable.

On the design front, backward chaining product will often have better justification or explanation mechanisms, i.e. explanations on how you arrived at a particular goal. If this is important to you, as it might be if you are working in clinical medicine, then a backward chaining solution might be a good fit.

On the performance front, there are certain circumstances where backward chaining might be better. For instance, if you have a small number of rules and a huge number of facts, you might be able to lazy load only those facts that are relevant to fulfilling goals.

If you'd like to play around a bit with a backward chaining rule engine, give Mandarax a try. Also, some commercial BRE's provide backward chaining as well as some other rule execution algorithms.

Feeling pretty good about your grasp of backward and forward chaining? Did you know there are hybrid approaches that combine both backward and forward chaining? Yep, it's true. But we won't go there today.

Related posts:

1. Prova – Son of Mandarax (Backward Chaining Rule Engines)
2. Do You Really Need RETE?
3. JSR-94 – Getting Your Feet Wet
4. Conflict Resolution – Why BRE’s Give Different Results
5. BRE Patterns I: The Fact Harvest

Comments (2)

business rules engines

Comments: 2 so far

• Leave a comment
• Comment feed for this post
• TrackBack URL

1. 

   Speaking from a low level technical perspective, the wikipedia explanation of forward and backward chaining is wrong.

   Going by Miranker’s LEAPS paper and Batory’s P2 LEAPS paper, the primary difference with backward chaining is it delays evaluating joins for all rules. Instead, it sequentially evalutes the rules by querying the facts. I like Dr. Forgy’s interpretation of the differences between forward vs backward. In plain english, a subgoal is a join between 2 facts. A backward chaining engine manages the subgoals in that it takes the first rule off the stack and checks to see if it needs to evaluate the join. If no facts satisfied the literal conditions (aka alphaNodes), it doesn’t need to perform a join evaluation.

   Forward chaining in contrast pushes the facts through the network and filters it. If a fact satisfies the conditions a node, it propogates the fact down the network. Basically, it pushes it down.

   The real downside of backward chaining is that it is not good for scenarios where one wants to perform cross product matching. The best example I can think of is an OMS (order management system) application for large mutual fund companies. The goal is to match multiple transactions against each other to determine the optimal combination. Since leaps trade performance for thoroughness, it’s not appropriate for scenarios that need cross product matching.

   I’ve heard of companies using backward chaining for OMS and pre-trade compliance, but I generally think they haven’t got a clue.

   peter

   Comment by Peter Lin, Wednesday, April 26, 2006 @ 8:05 pm

2. [...] of the forward vs. backward articles is by Dietrich Kappe. In his posting, he includes a quote from Charles Forgy, including the following: Backward [...]

   Pingback by » On Chaining Karl Reinsch’s Blog, Thursday, January 7, 2010 @ 5:25 pm

Leave a comment