What is forward-chaining inference and where is it used?

Inference is the act or process of deriving logical conclusions from premises known or assumed to be true. Validating the assumption are based on some inference rules.
— Wikipedia

As we mentioned in the other post, inference rules can be used to determine the current state of structural business rules. On the other hand, forward chaining is one of the two methods of reasoning when using inference rules. Forward chaining starts with available data and executes inference rules against this in order to extract more data until a goal is reached. In this method, because the starting point is data and rules to reach a goal, it is called forward chaining. The second method is called Backward chaining, which means an inference method that starts from the goal and works backwards to find a solution.

Artificial intelligence has played a big part in the evolution of methods for inferring, which is used in expert systems, business systems and production systems. In a complex business system, when there is some data available and the system needs to conclude an agenda from that data, the forward-chain inference engine is really useful. This is especially true when the engine uses a RETE algorithm that allows the rules be defined as a pattern, and it finds a match from the existing data in order to conclude something. For example, in a sales system it could be used to determine whether a person is a preferred customer by running the sales information against some inference rules.

What is RETE?

“…Rete match algorithm is a method for comparing a set of patterns to a set of objects in order to determine all the possible matches…” Rete (usually pronounced either “REET” or “REE-tee” from the Latin word for “network”) is an efficient pattern matching algorithm that deals with a Production Memory (PM) and a Working Memory (WM) in which each of them may change over time.
Working Memory is a set of items that represent facts about the system's current situation or state. Each item in the WM is called a Working Memory Element (WME) that can be modeled as

Name: (identifier ^attribute value)

The production memory is a set of productions (i.e., rules). A production contains a set of conditions, collectively called the left-hand side (LHS), and a set of actions, collectively called the right-hand side (RHS). Productions are usually written in this form:

(name-of-production
Left-Hand-Side
-->
Right-Hand-Side
)

A simple Blocks problem:

Let's consider a Block problem. Some blocks are on top of or under each other on a table as shown below:

RETE-BlockSample

Blocks in 3 colors on the table

With the introduced notation, the above picture can be modeled as follows:

/* Block B1 */ /* Block B2 */ /* Block B3 */
W1: (B1 on B2) W4: (B2 on table) W7: (B3 left-of B4)
W2: (B1 on B3) W5: (B2 left-of B3) W8: (B3 on table)
W3: (B1 color red) W6: (B2 color blue) W9: (B3 color red)

Solving blocks problem

In this simple problem, let's say we are going to answer questions regarding the positioning of the blocks. In a procedural approach, in order to answer any questions regarding this positioning we need to iterate through the blocks and the evaluate the conditions. It becomes more complex when we want to figure out relative positioning information for each block (e.g., left of, on, under, etc.). It becomes an endless loop when the blocks positions change constantly, such as when one of them moves on top of the others.

Let's say we want to find a stack of two blocks that are located to the left of a red block. In a procedural approach, we would probably write a couple of nested loops and then figure out which are stacks of two blocks and which of them are placed to the left of a red block.

A better approach is using a forward-chain inference engine and writing production rules that answer the questions. We can simply write the following production rule to answer this question:

(find-stack-of-two-blocks-to-the-left-of-a-red-block
(?x ^on ?y)
(?y ^left-of ?z)
(?z ^color red)
-->
/*... RHS ...*/
)

In this definition, ?x, ?y and ?z are some variables where for example (?x ^on ?y) is a condition saying “find two blocks where block ?x is on block ?y”.

No loop, no iteration, no condition evaluation, and no reference check for the neighboring blocks needs to be written in your application code.

In our RETE-based forward chain inference rule engine, modeling productions and working memory elements can be achieved in three ways:

  1. S-Expression: This is similar to the notation we explained here. You can execute the model directly from your application code.
  2. XML format: A hierarchy of elements to model productions and working memory elements
  3. API: Using .NET types (e.g. C# language) to build your model programmatically in code

When API is used, a C# version of the sample production rule would be something like this:

var rule = new Production("find-stack-of-two-blocks-to-the-left-of-a-red-block");
rule.Conditions.Add(
new PositiveCondition(new VariableSymbol("x"), new ConstantSymbol("on"), new VariableSymbol("y"))
);
rule.Conditions.Add(
new PositiveCondition(new VariableSymbol("y"), new ConstantSymbol("left-of"), new VariableSymbol("z"))
);
rule.Conditions.Add(
new PositiveCondition(new VariableSymbol("z"), new ConstantSymbol("color"), new ConstantSymbol("red"))
);
The Network

RETE contains two parts: alpha network and beta network. Each of them have their own types of nodes (e.g., Alpha memory, beta memory, join node, negative node, etc.). When the engine creates the graph from the productions provided, it then pushes the elements to the graph.
The graph for this simple production rule and a couple of WMEs looks like this:
RETE-Blocks

In our Resource Hub site, we will post some articles about our forward chaining inference engine in future. We will show how you can model productions and working memory elements in .NET and how you can integrate them into your application with more practical examples. Stay tuned…

Last updated December 15th, 2020 at 09:04 am, Published September 26th, 2013 at 09:04 am