Page 201 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 10: Matching Techniques

10.6 The Rete Matching Algorithm Notes

One potential problem with expert systems is the number of comparisons that need to be
made between rules and facts in the database.

In some cases, where there are hundreds or even thousands of rules, running comparisons
against each rule can be impractical.

The Rete Algorithm is an efficient method for solving this problem and is used by a
number of expert system tools, including OPS5 and Eclipse.

The Rete is a directed, acyclic, rooted graph.
Each path from the root node to a leaf in the tree represents the left-hand side of a rule.
Each node stores details of which facts have been matched by the rules at that point in the
path. As facts are changed, the new facts are propagated through the Rete from the root
node to the leaves, changing the information stored at nodes appropriately.
This could mean adding a new fact, or changing information about an old fact, or deleting
an old fact. In this way, the system only needs to test each new fact against the rules, and
only against those rules to which the new fact is relevant, instead of checking each fact
against each rule.
The Rete algorithm depends on the principle that in general, when using forward chaining
in expert systems, the values of objects change relatively infrequently, meaning that
relatively few changes need to be made to the Rete.

In such cases, the Rete algorithm can provide a significant improvement in performance
over other methods, although it is less efficient in cases where objects are continually
changing.
The basic inference cycle of a production system is match, select and execute as indicated
in Figure 10.1. These operations are performed as follows:

Figure 10.1: Production System Components and Basic Cycle

I User Inference Match
Interface Engine
O

Select

Working Knowledge Execute
Memory Base

Match:

During the match portion of the cycle, the conditions in the LHS of the rules in
the knowledge base are matched against the contents of working memory to

LOVELY PROFESSIONAL UNIVERSITY 195