The Internet Encyclopedia (Volume 3)

P1: IML/FFX P2: IML/FFX QC: IML/FFX T1: IML

WL040-Schalkoff WL040/Bidgolio-Vol I WL040-Sample.cls July 16, 2003 15:52 Char Count= 0

THEINFERENCEENGINE(IE) 239

as

p→q. (1)

Modus ponens (MP) is one logical basis for chaining

and is based on the axiom

{(p∩(p→q))→q}=T. (2)

Thus, given a rule (which itself is assumed to be TRUE)

of the formp→q, to proveq(=T), we must verifyp(=T)

in the database. Typically, Equation 2 is shown with the

following notation:

p

p→q

q

(3)

Rules typically involve variables to enable a more gen-

eral representation. For example, a rule indicating “Xis

the grandparent ofC” in the form of Equation 1 might

look like this:

[(parentXY)∩(parentYZ)]→(grandparentXZ). (4)

In this example, notice the use of variables that appear

multiple times (i.e., are shared) in the antecedent (i.e.,

variable Y) and those that are shared across the an-

tecedent and consequent (i.e., variablesXandZ). Assign-

ment of a value to a variable is called binding. Given a

database of clauses of the form (parent tom sally) and so

on, it is necessary to find a consistent set of bindings for

variablesX,Y, andZto use the rule in Equation 4. Such

a set of bindings is called a unifying substitution. When

rules involve variables, as in the preceding example, MP

is revised as follows:

p^1 (statement(s) without variables)

p→q (rule with variables)

(∃θ)(p^1 =pθ)

q^1 =qθ

(unifying substitution). (5)

THE CONCEPT OF CHAINING AND

INFERENCE DIRECTIONS

Chaining is an important concept in the implementation

of a rule-based system. It is typical that the consequents

of some rules are the antecedents to others (using unify-

ing substitutions, where necessary). These links form po-

tential “chains,” which are logical links or paths through

the system rulebase. A forward chaining (or antecedent-

driven) production system attempts to form chains from

the initial fact base to a database containing the goal.

A backward or consequent-driven paradigm attempts

to form (conditionally) chains backward from a goal

database to the initial facts database. Hybrid strategies

involve both forward and backward chaining. Whether

a production system is implemented through a forward,

backward, or hybrid chaining paradigm, the IE searches

for one or more paths through the problem state space

and may therefore explore a large number of redundant

or unsuccessful paths in the process. A good IE design

uses all available a priori information (such as properties

of commutativity and decomposability, if applicable), to

avoid needless or unproductive searching.

Potential Complexities in Chaining

Referring to Equation 2, rule-based inference becomes

complicated in a number of realistic situations, includ-

ing the following:

1. There exist many rules to choose from, that is, the
   database contains multiple rules of the form

p 1 →q (=T)

p 2 →q (=T)

..

.

pn →q (=T). (6)

Thus, we have the initial problem of choosing a rule.

2. The antecedentpin a rule is not a simple statement,
   but a compound expression in logic, for example,

p=p 1 ∩p 2 ∩p 3 ...∩pn. (7)

Thus, it is necessary for the IE to verify p 1 ∩p 2 ∩

p 3 ...∩pn.

3. Assuming (shared) variables are involved, there are
   multiple bindings that would satisfy all antecedents in
   the structure of the antecedent in Equation 7.

All of these circumstances may occur in realistic prob-

lems.

THE INFERENCE ENGINE (IE)

The heart of a rule-based production system is a

database (facts and rules) and the corresponding infer-

ence mechanism or inference “engine” that manipulates

this database. As noted, the inference engine (IE) is re-

sponsible for

1. Selection of relevant rules (or sets of rules), which may
   pertain to a specific reasoning scenario that the control
   mechanism determines should be focused on.


2. Determining the suitability of a given rule, using the
   criteria listed here, given the current database.


3. Execution or firing of the rule(s) and subsequent mod-
   ification of the database.


4. Determination if the overall goal has been satisfied.

In practice, the control strategies used to implement

conflict resolution (rule selection) are diverse. They may

range from tests as simple as “fire the first rule found to

be applicable” to “fire the rule that (according to some

heuristic) gets the system closest to the desired goal state.”

It is entirely possible for the IE to be formed from a

production system in which meta-rules (rules about rules)

are used to guide the selection of production system rules.